автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Расширение функциональности алгоритмов аутентификации и механизмы защиты информации над конечными группами векторов

На правах рукописи

Молдовян Дмитрий Николаевич

РАСШИРЕНИЕ ФУНКЦИОНАЛЬНОСТИ АЛГОРИТМОВ АУТЕНТИФИКАЦИИ И МЕХАНИЗМЫ ЗАЩИТЫ ИНФОРМАЦИИ НАД КОНЕЧНЫМИ ГРУППАМИ ВЕКТОРОВ

Специальность: 05.13.19 -Методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2012

Работа выполнена на кафедре автоматизированных систем обработки информации и управления Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" им. В.И.Ульянова (Ленина)

Научный руководитель: Академик Российской академии образования

доктор технических наук, профессор Советов Борис Яковлевич

Официальные оппоненты: доктор технических наук, профессор

Воробьев Владимир Иванович

доктор технических наук, профессор Максимов Роман Викторович

Ведущая организация: Санкт-Петербургский государственный университет водных коммуникаций

Защита диссертации состоится июня 2012 г. в _ на заседании

совета по защите докторских и кандидатских диссертаций Д 002.199.01 Санкт-Петербургского института информатики и автоматизации РАН по адресу: 199178, Россия, Санкт-Петербург, 14 линия, дом 39.

С диссертацией можно ознакомиться в библиотеке СПИИРАН

Автореферат разослан мая 2012 г.

Ученый секретарь

диссертационного совета Д 002.199.01

Нестеру к Ф. Г.

РОССИЙСКАЯ ГОСУДАРСТВЕННАЯ

БИБЛИОТЕКА ___201?_

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы диссертации. В настоящее время информационные технологии (ИТ) широко используют компьютерную обработку, хранение и передачу информации в компьютерных сетях, построенных с использованием скоростных телекоммуникационных каналов. Широко применяются ИТ практически во всех областях общественной деятельности - управленческой, экономической, финансовой, производственной, дипломатической, военной. Во многих случаях обеспечение информационной безопасности имеет критическое значение, что обусловливает необходимость применения механизмов аутентификации, защиты и контроля целостности информации и непрерывного их совершенствования. Проблема защиты ИТ связана с задачами обеспечения доступности информационных ресурсов, аутентичности, целостности и конфиденциальности информации. Эта проблема решается на основе комплексного подхода и с применением различных средств и механизмов. Алгоритмические средства защиты ИТ, базирующиеся на современной криптографии являются гибкими и эффективными, а также лежат в основе ИТ, связанных с обработкой юридически значимых документов и сообщений.

Основными требованиями к криптографическим алгоритмам и протоколам, используемым в качестве алгоритмических механизмов защиты информации являются их стойкость и безопасность, которые определяются лежащими в их основе вычислительно трудными задачами и уровнем развития теории, методов и алгоритмов решения задач данного типа. Наиболее широко применяемые криптографические схемы (алгоритмы и протоколы) имеют практическую стойкость и безопасность, т. е. их применение основано на экспертных оценках. Развитие алгоритмов решения трудных задач и вычислительной техники делает крайне актуальным выполнение периодических оценок стойкости и безопасности алгоритмических механизмов защиты информации с учетом новых достижений теории и нового уровня вычислительной техники. При этом к алгоритмическим механизмам предъявляются и технологические требования, состоящие в удобстве встраивания в программные и технические средства защиты информации, высокого быстродействия и достаточно низкой стоимости аппаратной реализации. Это обусловливает актуальность развития алгоритмических средств обеспечения информационной безопасности. Ожидание появления практически действующих квантовых компьютеров заставило разработчиков таких средств обратиться к поиску новых трудных задач в качестве криптографических примитивов, для которых не известны эффективные методы решения с использованием квантовых вычислителей. Значительное число исследований в этой области связано с использованием трудных задач, формулируемых над некоммутативными группами. Недавно был предложен подход к заданию конечных групп векторов и их применению при разработке криптографических схем. В основе этого подхода лежит идея использовать

возможность эффективного распараллеливания групповой операции, за счет чего может быть обеспечено повышение производительности алгоритмов защиты информации. Однако для синтеза криптосхем на основе конечных групп векторов требуется найти подходы к построению конечных групп векторов различных типов, включая некоммутативные группы векторов, изучению их строения и особенностей их использования при разработке алгоритмов шифрования, электронной цифровой подписи (ЭЦП) и открытого распределения ключей.

Другим важным аспектом практического применения алгоритмов аутентификации является принципиальная возможность придания специальных свойств алгоритмам аутентификации информации, т.е. расширение функциональности последних. Это позволяет сократить время выполнения специальных процедур и уменьшить количество и суммарный объем вспомогательной информации при решении специальных практических задач, связанных с аутентификацией.

В связи с ранее сказанным, тема диссертационного исследования, связанная с расширением функциональности алгоритмов аутентификации информации и развитием алгоритмических механизмов защиты информации на основе применения конечных групп векторов и исследованием как самих групп векторов, так и криптосхем на их основе представляется актуальной и своевременной.

Цель диссертационного исследования состоит в повышении производительности, уровня безопасности и расширение функциональности механизмов алгоритмической защиты информации. Для достижения данной цели исследуются и применяются конечные группы векторов, а также разрабатываются механизмы аутентификации информации, взлом которых требует одновременного решения трудных задач факторизации и дискретного логарифмирования.

Задачами диссертационного исследования являются разработка способов задания конечных коммутативных и некоммутативных групп векторов с вычислительно эффективной групповой операцией, анализ их строения, оценка стойкости криптосхем, синтезируемых на их основе, и разработка алгоритмов аутентификации информации с расширенной функциональностью.

Для достижения поставленной цели в ходе выполнения диссертационных исследований решались следующие частные задачи:

1) разработка способов задания коммутативных конечных групп векторов различной размерности;

2) разработка способов задания некоммутативных конечных групп векторов различной размерности;

3) исследование строения конечных групп векторов различной размерности и связи строения со способом их задания;

4) синтез криптосхем на основе конечных трупп векторов;

5) оценка стойкости синтезируемьгх криптосхем;

6) разработка схемы коллективной электронной цифровой подписи (ЭЦП) с восстановлением сообщения;

7) разработка схемы слепой ЭЦП с восстановлением сообщения, основанной на сложности задачи дискретного логарифмирования;

8) разработка схемы слепой ЭЦП, взлом которой требует одновременного решения задачи факторизации и дискретного логарифмирования.

Методы исследования. При выполнении диссертационного исследования использованы аппарат и методы теории вероятности, алгебры, теории чисел, теории сложности и криптографии.

Объектом исследования являются системы и средства защиты и аутентификации информации в информационно-коммуникационных технологиях.

Предметом исследования являются механизмы, примитивы, алгоритмы и протоколы криптографической защиты и аутентификации информации в средствах и системах информационной безопасности.

Основные положения, выносимые на защиту:

1. Схема слепой электронной цифровой подписи (ЭЦП), основанная на вычислительно трудных задачах факторизации и дискретного логарифмирования.

2. Схема открытого распределения ключей на основе трудности задачи дискретного логарифмирования в скрытой подгруппе.

3. Алгоритм коммутативного шифрования-

4. Протокол коллективной ЭЦП с восстановлением сообщения.

Научная новизна:

1. Схема слепой электронной цифровой подписи (ЭЦП), основанная на вычислительно трудных задачах факторизации и дискретного логарифмирования, отличающаяся тем, что для ее взлома требуется одновременно решить обе указанные задачи, благодаря чему повышается уровень безопасности схемы.

2. Схема открытого распределения ключей над задачей скрытого дискретного логарифмирования в конечных некоммутативных группах, отличающаяся использованием групп векторов и заданием коммутативной подгруппы как множества степеней элемента достаточно большого простого порядка, благодаря чему уменьшается время формирования общего секретного ключа двух удаленных абонентов.

3. Алгоритм коммутативного шифрования, отличающийся использованием конечных полей, заданных в явной векторной форме, благодаря чему обеспечивается эффективное распараллеливание операции умножения и повышение быстродействия алгоритма.

4. Протокол коллективной ЭЦП с восстановлением сообщения, отличающийся использованием задачи дискретного логарифмирования на эллиптической кривой, благодаря чему обеспечивается уменьшение размера ЭЦП и повышение быстродействия протокола.

Обоснованность и достоверность научных положений обеспечены математическими доказательствами сформулированных утверждений и корректности предложенных схем аутентификации, результатами вычислительных экспериментов, апробацией основных теоретических результатов в печатных трудах и докладах конференций, а также анализом состояния исследований в данной области на сегодняшний день.

Практическая ценность работы. Протоколы электронной цифровой подписи и алгоритм коммутативного шифрования, разработанные в данной диссертационной работе, обеспечивают повышение быстродействия и безопасности механизмов аутентификации информации.

Реализация результатов. Результаты диссертационной работы внедрены в учебный процесс СПбГЭТУ при преподавании дисциплин «Теоретические основы криптографии», «Криптографические методы защиты информации» и «Криптографические протоколы» на кафедре Автоматизированных систем обработки информации и управления.

Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на V международной конференции Mathematical Methods, Models, and Architectures for Computer Network Security, «MMM-ANCS 2010» (Санкт-Петербург, 8-11 сентября 2010 г.); всеармейской научно-практической конференции «Инновационная деятельность в Вооруженных силах Российской Федерации» (Санкт-Петербург, 25-26 ноября 2010; 24-25 ноября 2011); VI Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2009)» (Санкт-Петербург, 28-30 октября).

Публикации. Основные результаты диссертации изложен в 17 публикациях, в том числе, в 12 статьях, из которых 11 опубликованы в ведущих рецензируемых журналах, входящих в перечень ВАК, в 1 докладе на международной конференции и 3 докладах на российских конференциях. По результатам исследования получен 1 патент.

Структура и объем работы. Диссертационная работа изложена на 138 машинописных страницах, включает введение, 4 главы, заключение и список литературы (52 наименования).

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована своевременность и актуальность темы диссертации, сформулированы цели исследования и решаемые задачи, определена научная новизна и приведено краткое содержание работы по главам.

В первой главе диссертации рассмотрены алгоритмы и протоколы криптографии с открытым ключом, обеспечивающие возможность аутентификации электронной информации и ее источника. Рассмотрены известные трудные задачи, используемые для построения алгоритмов и

протоколов электронной цифровой подписи (ЭЦП). Отмечается интерес к построению криптографических алгоритмов и протоколов с использованием некоммутативных конечных групп и трудных задач, связанных с такими группами. Одной из проблем использования некоммутативных групп для синтеза криптосхем является поиск таких групп, в котрых групповая операция имела бы достаточную вычислительную эффективность. Перспективными представляются конечные мультипликативные группы векторов, задаваемые над конечными полями. Группы такого типа изучены для малых значений размерности векторов и для коммутативного случая. Представлены известные результаты по заданию конечных коммутативных групп двухмерных и трехмерных векторов и формулируются задачи диссертационного исследования.

Во второй главе рассматриваются способы задания коммутативных и некоммутативных конечных групп многомерных векторов с операцией умножения векторов как групповой операцией. Для задания операции умножения векторы (аь а2,..., ат), в которых координатами являются элементы конечного поля GF(p), представляются в виде суммы одномерных векторов (компонентов): a¡e + a2i + ... + amw, где е, i, ,.., w - формальные базисные векторы. Операция умножения векторов определяется по правилу покомпонентного перемножения. Это сводит определение результата умножения векторов aie + a2¡ + ■•• + amW и b¡e + b2\ + ... + bmw к определению результата умножения однокомпонентных векторов вида a(v, и bjVj , где v„v, е {е, i,..., w}. Таким образом следует определить результат произведения a¡v¡°bj\j. По определению принимаем ay¿>bj\] = a¡b/y¡°Vj), где произведение в последней скобке берется из специально определяемой таблицы умножения базисных векторов (ТУБВ). Пусть из ТУБВ имеем v,°v= svb тогда a¡\fbj\j = a¡bjiyi°\j) = a¡bj{ev*) = (a,bfi)yk. С помощью ТУБВ можно определить результат умножения любых двух однокомпонентных векторов, например, aie + a2i + ... + атw и ¿>ie + b2i + ... + ¿>mw:

(aje + a2 i + ... + amw)°(í>,e + ¿>2i + ... + bm w) = = a!¿>i(e°e) + ai¿>2(e°i) + ...+ ai¿>m(e°w) + a2¿i(i°e) + a2b2( i°i) + ... + вгМИ) + ... + amb i(w°e) + amb2(w°i) + ... + ambm(w°w),

где произведения всех возможных пар базисных векторов заменяются по ТУБВ на однокомпонентные векторы. Суммирование всех однокомпонентных векторов дает некоторый /и-компонентный вектор, являющийся результатом умножения. Ассоциативность операции умножения достигается выбором ТУБВ, для которой имеет место (v,°v¡)°vk = v^v/v*) для всех возможных троек базисных векторов v„ v¡ и vk. Таблица 1, где е, т, А, е GF(p) - структурные коэффициенты (X * 0), представляет собой ТУБВ, задающую ассоциативное и коммутативное умножение векторов произвольной конечной размерности.

Таблица 1. Общий тип ТУБВ (X Ф 0).

о е 1 j к и V г

е Хе М Хк А.и Х\ X... X... Хг

1 М ч ек ей ЕУ Е... Б... Ег ет^Г'е

Л м ек ви ЕУ Е... Е... ег ЕтЯ,_1е т1

к Хк ей ЕУ Б... Б... Ег Т1 Ч

и Хи еу е... Е... ЕХ ЕтА._1е II Ч тк

V Ху 8... е... ег етА._1е т1 Ч тк ти

X... е... ЕХ етАГ'е Ч тк ти ТУ

X... ег Т1 Ч тк ти ТУ т...

X Хг Ч тк ти ТУ т... т...

Множество обратимых векторов образуют конечную мультипликативную группу с единичным элементом Е - (Х~\ 0,0,..., 0) - векторную конечную группу (ВКГ). Существуют различные распределения структурных коэффициентов в ТУБВ, за счет чего может быть уменьшено число операций умножения в поле GF(p) при выполнении операции умножения векторов. Этот способ уменьшения сложности векторного умножения состоит в применении двух взаимно обратных значений растягивающих коэффициентов, которые имеют близкие распределения в том смысле, что эти два коэффициента попадают одновременно в одни и те же клетки ТУБВ достаточно большое число раз.

Для различных значений и распределений структурных коэффициентов было исследовано экспериментально строение групп векторов (под строением понимается таблица, показывающая число векторов для каждого возможного значения их порядка). Для интерпретации экспериментальных результатов по изучению строения ВКГ была выведена формула, описывающая строение коммутативных примарных подгрупп в общем случае, когда базис примарной подгруппы Г включает ц, элементов 2у (/' = 1,2,..., ц,) порядка рщ, / = 1,2, ...,/. Порядок такой примарной подгруппы выражается формулой вида

Без потери общности рассмотрения можно считать, что а.) < а.г <...< щ <...< а,. Очевидно, что элементы примарной подгруппы могут иметь значения порядков ру, где а, < у < а,. Для случая у = а1 Для числа элементов порядка р' легко

(а -1)УУ ц- ( У' ц- ^ выводится формула N _ г = р 1 /> '=1 ' -1

о1=р

\

Пусть а,_! < у < а,. Элементы рассматриваемой примарной подгруппы, порядок которых равен или меньше рт, образуют некоторую подгруппу Гу порядка

...(„ту .

Элементы рассматриваемой примарной подгруппы, порядок которых равен или меньше ру~образуют некоторую подгруппу Гу_1 порядка

Число элементов порядка со =ру найдем как разность значений П(ГУ) и 0(ГУ _,), что дает следующую формулу:

N = рЕ'к=1ак\1кНУ- ( „11=/и* _!

^ \ Строение коммутативных групп векторов в общем случае является нециклическим - их базис включает от 1 до т векторов в зависимости от вида ТУБВ и выбранных значений структурных коэффициентов при заданной ТУБВ.

В частных случаях мультипликативная В КГ имеет циклическое строение - это случай формирования расширенных конечных полей, заданных в явной векторной форме (операцией сложения в таком поле является стандартная операция сложения векторов, определяемая как сложение одноименных координат). Другой важный случай представлен В КГ, обладающими многомерной цикличностью, относящейся к случаю групп, порождаемых базисом, все элементы которого обладают одним и тем же значение порядка. Над ВКГ с многомерной цикличностью задача дискретного логарифмирования формулируется следующим образом. Пусть векторы (5ь Сг,..., образуют базис группы. Тогда любой вектор У может быть представлен как произведение некоторых степеней элементов, входящих в рассматриваемую систему образующих. Нахождение этих степеней, т. е. решение уравнения

У = С^1 о(З^2 °0относительно набора неизвестных хих2,...,хГ составляет содержание задачи дискретного логарифмирования при заданном базисе (Сь С/2, ...,СГ). Если порядок элементов С?г-, г =1,2,...,г, содержит

большой простой делитель Ч размером |<?| ^ 160/г бит, то нахождение многомерного логарифма является вычислительно трудной задачей. Для нахождения многомерного дискретного логарифма может быть применен адаптированный метод больших и малых шагов, имеющий трудоемкость

Ш = оШ}, где <7 ~~ максимальный простой делитель порядка группы с

многомерным циклическим строением. Анализ экспериментальных результатов

позволил получить следующее правило для случая использования ТУБВ, заданной табл. 1, которое позволяет при синтезе алгоритмов ЭЦП задавать требуемую структуру групп векторов.

Правило задания строения группы векторов: при условии т\р-\, т = 5г, НОД(8, г) = 1, X, = V = 1 и значении т, таком, что уравнение х* = т не имеет решение в поле СР(р) для всех делителей с! \ т, где 1 < с! < 5, но имеет решение для й = г, группа является циклической при г = 1 или обладает г-мерной циклической структурой при г >2, причем порядок группы равен

Максимальный порядок циклических подгрупп в таких группах равен П' = ^5-1| = . Группы векторов с многомерным циклическим

строением представляют интерес для построения схем ЭЦП с открытым ключом У = "...«б^ , где V/ е {1,2,...,г}; векторы

имеют простой порядок д достаточно большого размера и составляют базис

у

подгруппы порядка Ц . Секретным ключом является набор чисел х1,х2,...,хг, каждое из которых не превышает значение д-1. При этом открытым ключом пользователя является набор векторов У}, г =1,2,...,г:

", а секретным ключом - т наборов чисел: ХМ'Х21 >—'Хп'' —1,2,. Проверочное уравнение имеет вид

Л = У~е' О Ур О ... О У'*2 о в? ° в? О ... о в1/ ,

где наборы чисел еь е2,..., ег и «1, ..., являются элементами ЭЦП. При Г =2 генерация ЭЦП к сообщению М выполняется следующим образом.

1. Выбрать случайные числа ^ и и вычислить вектор Л = = ° С^2.

2. Используя хэш-функцию ¥н, вычислить значение е, представляемое в виде конкатенации чисел ех и е2: е = е11| ег = Fff (М || г, || г2).

3. Вычислить значения ^ и по формулам = ¿1 + х\£\ + х1х2е2 Я и

52 = + х2е\ + (Х1 + хЪе2 тос1 Ч ■

Подписью является четверка чисел ^, ег, и • Процедура проверки ЭЦП по открытому ключу (^,^2) состоит в выполнении следующих шагов:

1. Вычислить вектор К = (г{ || = У"*1 о у^2 ° в^1 ° .

2. Вычислить значение е' = || ег = РН(М || г[|| г2').

3. Сравнить значения е и е'. Если е,' || = е, || , то подпись к сообщению М признается подлинной. В противном случае подпись отвергается.

Для четных значений размерности векторов т >6 предложен общий способ построения ТУБВ, задающих ассоциативную некоммутативную

операцию умножения. В первой строке слева направо записываются базисные векторы в некоторой исходной последовательности. В первом столбце сверху вниз записывается та же последовательность базисных векторов. В каждой четной (нечетной) строке базисные векторы записываются, начиная с элемента, указанного в первом столбце, в обратной (прямой) последовательности (относительно исходной последовательности). В построенную таким образом ТУБВ вносится структурный коэффициент е в каждую клетку, находящуюся на пересечении четной строки и четного столбца. Такое распределение обеспечивает свойство ассоциативности умножения при произвольном значении е е (р). Для значений т = 4 некоммутативные группы задавались с помощью ТУБВ, представленных в виде табл. 2.

Таблица 2. Правила умножения базисных векторов для случая т = 4.

о е i j k

е е i j k

i i -ее ek -j

j j -ek -ее i

k k J —i —e

Доказаны следующие утверждения о порядке таких групп.

Утверждение 1. Для простого числа р вида р = 4к + 1 при любом s * 0 и для простого р вида р = 4к + 3 при е, являющемся квадратичным невычетом порядок некоммутативной группы четырехмерных векторов, групповая операция которой задана по таблице 2, равен Q = р(р - 1 )(р2 - 1).

Утверждение 2. При 8 = 0 порядок некоммутативной группы четырехмерных векторов равен Q = р2(р2 - 1), если простое число р представляется в виде р = 4к+3, и равен Q = р2(р - I)2, если простое число р представляется в виде р = 4к+1.

В третьей главе рассматриваются трудные задачи и критггосхемы над конечными некоммутативными группами. Утверждения 1 и 2 определяют возможные значения простых порядков векторов и позволяют найти векторы требуемого порядка для синтеза протоколов открытого распределения ключей с использованием трудности задачи, предложенной в 2007 г. (Sakalauskas Е. И др.), которую можно назвать задачей дискретного логарифмирования в скрытой циклической подгруппе конечной некоммутативной группы или скрытой задачей дискретного логарифмирования, формулируемой следующим образом. Пусть задан некоторый элемент G. Из некоторой коммутативной подгруппы Г2 с Г, элементы которой неперестановочны с G, выбирается элемент X. Также выбирается произвольное число х и вычисляется элемент Y = Х^ОУХГ1. По заданным К и G требуется вычислить сопрягающий элемент X и число х.

Пусть пара (X), Х]) является секретным ключом первого абонента и пара (Х2, х2) является секретным ключом второго абонента. Воспользуемся формулой У = Х°0'°Х~1 для вычисления открытого ключа. Тогда открытым ключом первого (второго абонента) является элемент группы Г, равный У]=Х1 оС'1«!,"1 (У2=Х2°0Х* °Х2~}). В силу выбора элементов Х1 и Х2 из коммутативной подгруппы и взаимной коммутативности операций вычисления сопряженного элемента и возведения в степень первый и второй абоненты могут сформировать общий секретный ключ используя только свой личный секретный ключ и открытый ключ другого абонента. Первый абонент выполняет следующее вычисление:

Ки = Хх° У? = Хг о (х2 ° й*1 о Х2 оХг'г = Х1 °Х2 об^' оХ2~г °Х{~1, Второй абонент выполняет следующее вычисление:

К{2 = Х2 ° У*2 ° Х2~г = Х2 о (хг о в"1 о Хх~1 ^ о Х21 = Х2°Х1° в*2* о Х^1 о Х2'К Поскольку Х\°Х2 — Х2°Х\, то К]2 = К\2 = 2. Последнее значение использовано в качестве общего секрета. Для построения вычислительно эффективной схемы открытого согласования общего секретного ключа предлагается использовать конечные некоммутативные группы четырехмерных векторов и аналитический способ выбора векторов Х\ и Х2 из одной и той же коммутативной подгруппы, который состоит в генерации случайных чисел и уу2 и вычисления векторов

= и Х2 = , где Q - вектор, порядок которого делится на

достаточно большое простое число, причем такой, что имеет место Q°G*G°Q. Доказано следующее утверждение, условиям которого должны удовлетворять параметры й и 0 предлагаемого протокола открытого распределения ключей.

Утверждение 3. Пусть О и 0 элементы некоммутативной группы, имеющие простые порядки g и д, соответственно, такие что и 2 ° С Ф С ° 2,

где 2- 0 о б о ¡2"1. Тогда все элементы 2{] = Q■' о б' ° б ^, гДе ' = 1, 2, 1

иу = 1, 2,..., <7, попарно различны.

В соответствии с этим утверждением число различных неединичных элементов 2{] составляет (£-1)<7 и они образуют вместе с единичным элементом N = ц различных подгрупп порядка g, причем каждый неединичный элемент принадлежит только одной из этих подгрупп.

Предложенная схема открытого согласования общего секретного ключа может быть использована для построения следующего алгоритма открытого шифрования, в котором используется некоторая функция симметричного шифрования Ек, где секретный ключ К представляет собой 4х-мерный вектор:

1. Отправитель генерирует пару случайных чисел (и, г), вычисляет элементы Я = " и К = (/°У°(2 " некоммутативной группы Г, где У -

открытый ключ получателя. Элементы Ли К играют роль разового открытого ключа и разового общего секрета. Они будут использованы для шифрования только одного сообщения (или текущего блока длинного сообщения, которое

разбивается на блоки приемлемого размера). Для шифрования следующего сообщения (блока сообщения) будут сгенерированы новые значения разового открытого ключа и разового общего секрета.

2. Используя значение К в качестве ключа шифрования, отправитель зашифровывает сообщение М\С-ЕК {М).

3. Отправитель направляет получателю, которому принадлежит открытый ключ У = , криптограмму С и значение разового открытого ключа /?.

4. Получатель вычисляет значение К'= = К, где (и>, х) - личный секретный ключ получателя, и расшифровывает криптограмму С: М-Ок (С), где Дс - функция расшифрования, обратная к Ек.

Оценка стойкости. В описанных схемах открытого согласования ключа и открытого шифрования используется открытый ключ У, вычисляемый по личному секретному ключу (м>, х) по формуле У - где 0 и С -

известные элементы некоммутативной группы достаточно большого простого порядка д и g, соответственно. Сложность вычисления секретного ключа по открытому задает верхнюю границу стойкости предложенных криптосхем. Рассмотрим вычисление секретного ключа в случае

1. Для всех значений м> = \,2,...,ц вычислить таблицу значений Д™) = в (Трудоемкость этого шага равна групповых операций.)

2. Упорядочить таблицу, вычисленную на шаге 1. (Трудоемкость этого шага составляет операций сравнения элементов группы.)

3. Установить счетчик г = 1 и значение вектора V = Е, где Е - единичный элемент некоммутативной группы.

4. Вычислить вектор V - У°С.

5. По отсортированной таблице проверить имеется ли в ней значение V. Если в таблице имеется значение Т(м>')= V, то вывести значение секретного ключа (н», х) = (и-г) и СТОП, в противном случае перейти к шагу 6.

6. Если / Ф g, то прирастить значение счетчика г <— г + 1 и перейти к шагу 4, в противном случае СТОП и вывести сообщение «условия некорректны».

Трудоемкость шагов 5 и 6 составляет не более д групповых операций и д\о%гЧ операций сравнения. Трудоемкость алгоритма 5 составляет Зд операций умножения плюс 2д1о§2д операций сравнения, т.е. 5 = 0{д), где 0(д) -обозначение порядка. При д > 280 верхняя граница стойкости соответствует 80-битовой стойкости.

Дано обоснование дополнительным требованиям к выбираемым параметрам криптосхем, основанных на задаче дискретного логарифмирования в скрытой подгруппе некоммутативной групп векторов. Векторное пространство над конечным, в котором определена ассоциативная операция умножения векторов, образует конечное кольцо К. Доказано утверждение 4 о существовании гомоморфизма мультипликативной группы векторов Ы* в мультипликативную группу конечного поля СГ(р), над которым задаются векторы. Этот гомоморфизм можно обозначить как Ы*—> Р*, где Г* -мультипликативная группа поля .

Утверждение 4. Главный определитель системы линейных уравнений, записанной для вычисления обратного вектора А ] к заданному вектору А определяет гомоморфизм К*—> Г*.

Установленный гомоморфизм, который далее будем обозначать как А (А) = Ал , может быть положен в основу следующей атаки на схемы открытого шифрования и открытого распределения ключей, основанных на задаче дискретного логарифмирования в скрытой коммутативной подгруппе, заданной над некоммутативными группами векторов. В таких схемах используется открытый ключ вида У = , где пара чисел х и м>

составляет секретный ключ. Применение гомоморфизма И*—»Р* к уравнению вычисления открытого ключа дает следующее соотношение:

ДА ™ А *А -М А *А И'А А * А

У=Ад ДС Ад =ДС Ад Ад = Ав = Аа , которое представляет собой уравнение над полем (//'(р). Нахождение значения х' из последнего уравнения представляет собой задачу дискретного логарифмирования в поле ^(р), решение которой позволит найти значение х = хтос1<у', где д' - порядок элемента АдвОР(р). Если значение д' достаточно велико, то решение задачи дискретного логарифмирования в поле СР(р) позволит определить значительную часть секретного ключа.

Общим способом предотвращения такой атаки является использование в качестве параметра С вектора, имеющего порядок, не являющийся нетривиальным делителем числа р -1. В этом случае значения А у и Л0 равны единичному элементу поля ОР(р) и уравнение, получаемое с помощью

гомоморфизма И*—принимает вид 1 = 1* в силу следующего утверждения. Утверждение 5. Если вектор С имеет порядок сос, такой что

НОд(шс,^-1)=1,то Д(С) = 1.

Рассмотренная атака фактически состоит в обеспечении возможности вычисления секретного ключа по частям. Она применима к случаю использования задачи дискретного логарифмирования в скрытой подгруппе, заданной над конечной некоммутативной группой векторов произвольного вида. Однако, как правило, для любой группы векторов достаточно легко найти вектор С , удовлетворяющий условию утверждения 5, что предотвращает возможность выполнения этой атаки. По аналогии с атакой, основанной на гомоморфизме 11*—>Р*, можно предложить атаку на основе потенциально возможного гомоморфизма К*->Р'*, где ¥'* - мультипликативная группа

расширенного поля ОР(рк), где 1 <к<т. Однако второй вид общей атаки связан с необходимостью установления возможных гомоморфизмов вида Ы*—>Г'*. Можно ожидать, что решение последней задачи будет иметь специфику для различных групп векторов и потребует выполнения самостоятельных исследований в случае различных значений размерности векторов и различных видов ТУБВ. При этом по значению порядка группы

векторов, выраженному через характеристику конечного поля, над которым заданы векторы, можно уменьшить число вариантов возможных значений к > 1.

Наиболее простым случаем является случай некоммутативных групп четырехмерных векторов, для которых порядок равен Q = р(р - 1 )(р2 - 1). Из данной формулы легко видеть, что множитель (р- 1) показывает на потенциальную возможность гомоморфизма R*—>F*, а множитель (р2 - 1) - на потенциальную возможность гомоморфизма R*—>F'* при к = 2. Это единственно возможное значение к > 1. Если такой гомоморфизм будет найден, то это будет означать, что некоммутативные группы четырехмерных векторов не могут обеспечить достаточную стойкость криптосхем с открытым ключом

вида Y = Qw °GX о Q~w при сравнительно малых значениях размера порядка поля GF{p), над которым задаются векторы. Рассмотренные атаки должны быть учтены при разработке криптосхем с использованием задачи дискретного логарифмирования в скрытой циклической подгруппе.

В четвертой главе приводятся разработанные протоколы ЭЦП с расширенной функциональностью и алгоритм коммутативного шифрования, использующий вычисления в конечной мультипликативной группе.

Протокол коллективной цифровой подписи с восстановлением сообщения. Схемы ЭЦП с восстановлением сообщения и протоколы коллективной ЭЦП, основанные на трудности задачи дискретного логарифмирования (ЗДЛ) в конечном простом поле или ЗДЛ на эллиптической кривой (ЭК), используются для аутентификации информации при решении специальных задач информационных технологий. В ряде практических случаев возникает задача объединения указанных двух типов криптосхем в едином криптографическом протоколе, который можно назвать схемой коллективной ЭЦП с восстановлением сообщения. Использование коллективной ЭЦП в технологии защиты бумажных документов от подделки для подписи уникального цифрового образа бумаги, на которой изготовлен документ, значительно снижает вероятность подделки, выполняемой внутренними нарушителями, т.е. лицами, вовлеченными в санкционированную процедуру изготовления документов. В то же время в данной технологии актуально сокращение размера машиночитаемой метки, наносимой на бумажный документ. Это делает актуальным восстановление эталонного цифрового образа бумаги по значению ЭЦП, что позволит существенно сократить размер машиночитаемой метки.

Системными параметрами протокола являются коэффициенты уравнения ЭК и некоторая точка G, порядок которой равен достаточно большому простому числу q. Открытым ключом - точка Qt = dfi, где d, - личный секретный ключ /-го пользователя. Формирование коллективной подписи (г, s) к сообщению М <q, осуществляется по коллективному открытому ключу, являющемуся суммой открытых ключей всех подписывающих в соответствии со следующим алгоритмом:

1. Каждый пользователь генерирует случайное целое число А, (0 < к < q) и вычисляет точку Ci = ktG (i =1,2,..., m). Значения С, (i = 1, 2,..., m) рассылаются всем пользователям.

2. Пользователи вычисляют коллективный открытый ключ Q = Ql+Q2+~ + Qm=(xQ>yQ)> Т0ЧКУ С = С1+С2+... + Ст и значение г = MxqKc mod q, где Хс ~ координата точки С.

3. Каждый / ый пользователь вычисляет значение s, = /с, -rdt mod q. Значения s, (i =1,2,..., m) рассылаются всем пользователям.

4. Пользователи вычисляют значение s = si + s2+... + sm mod q.

Проверка подлинности коллективной ЭЦП (г, î) осуществляется по

коллективному открытому ключу Q = Qi + Q2+ — + Qm' равному сумме открытых ключей подписывающих по следующему алгоритму:

1. Вычисляется точка С* = rQ + sG и значение M* = HxqKc•)"' niod q.

3. Если M* = M, то ЭЦП признается подлинной, иначе отвергается.

Протокол слепой ЭЦП с восстановлением сообщения. Протоколы слепой ЭЦП и схемы ЭЦП с восстановлением сообщения решают специальные задачи по аутентификации электронной информации в автоматизированных информационных системах. Информационные технологии, известные как системы электронных денег и тайного электронного голосования, используют криптографические механизмы, называемые протоколами слепой ЭЦП или просто слепой подписи. Они позволяют подписать электронный документ M таким образом, что подписывающий не может ознакомиться с сообщением в процессе генерации ЭЦП, а в будущем при получении значения Ми ЭЦП он не может идентифицировать пользователя, который представлял для подписявания документ М.

Схема слепой подписи Чаума, основанная на трудности задачи факторизации и построенная путем расширения функциональности криптосистемы RSA, соединяет в себе свойства двух указанных типов криптосхем. Однако размер подписи в схеме Чаума составляет 1024 бит, что в 3-4 раза превышает размер подписи в схемах ЭЦП, основанных на сложности задачи дискретного логарифмирования при обеспечении уровня 80-битовой стойкости. Практический интерес представляет задача разработки протоколов слепой ЭЦП с восстановлением сообщения, основанных на трудности ЗДЛ. Следующий протокол предоставляет возможность решения этой задачи.

1. Подписывающий выбирает разовый случайный секретный ключ число к, затем вычисляет D = gk mod р и предоставляет это значение пользователю А.

2. Пользователь А генерирует случайные значения параметров е и т, вычисляет R = (M^Dy Lgx mod р) mod q и R = R - e mod q. Затем A направляет значение R подписывающему.

3. Подписывающий вычисляет второй элемент слепой ЭЦП S = (к + xR) mod q и направляет s пользователю А.

4. Пользователь А вычисляет второй элемент подписи к сообщению М по формуле S = S + т mod q.

Уравнение проверки ЭЦП имеет вид М - (у RgS mod р) R'] mod q .

Протокол слепой подписи, основанный на трудности одновременного решения задач факторизации и дискретного логарифмирования использует простой модуль р со структурой р = 2п + 1 (п = qr, где q и г - сильные простые числа), два ослепляющих множителя вида у^тойр и а,:modр, где т и е-случайные числа (т < и и в < и). Секретным ключом является четверка чисел (q, г, х, d), где х - случайное значение (х < п); d - число, вычисляемое по формуле d = е mod (р(и) после предварительного выбора сравнительно малого значения е, взаимно простого с <р(я) = (q - 1)(г -1). Открытым ключом является четверка чисел (р, а, у, е), где а - число порядка п = qr по модулю р; у- число,

вычисляемое по формуле у = ах mod р. Пусть некоторый пользователь желает получить подпись владельца открытого ключа (р, а, у, ё) к сообщению М. Для этого выполняются следующие шаги:

1. Подписывающий вычисляет и отправляет пользователю значение R = a* mod р, где к — случайное число (к < п).

2. Пользователь вычисляет значения R= RazyT modр и Е'= Fn(M\\R), генерирует случайное число X (К < п), вычисляет значение Ё =Е"ке mod« и направляет Ё подписывающему.

3. Подписывающий вычисляет значение D-Ed mod п и направляет D пользователю.

4. Пользователь вычисляет значения Е = ОГ1 = E'd mod п и E = E + i mod и, после чего направляет £ подписывающему. (Значение £ является первым элементом слепой подписи, а Е - первый элемент подписи к сообщению М.)

5. Подписывающий вычисляет значение S = к + хЕ mod п и направляет второй элемент слепой подписи S пользователю. (Заметим, что имеют место

— — _ U л_уг о _ L7

соотношения к = S - хЕ mod и и R = а = а = а у mod р).

. 6. Пользователь вычисляет второй элемент подписи (Е, S) к сообщению М: S = S + е mod п.

Проверка подлинности подписи (Е, S) осуществляется следующим образом:

1. Вычислить значения R = y~Eas mod р, Ё = Fh{m || л) и Е* = Ее mod«.

2. Сравнить значения Е" и Е. Если Е =Е, то подпись признается подлинной. В противном случае подпись отвергается.

Разработанный алгоритм коммутативного шифрования использует операцию возведения в степень в конечных полях GF((ps)m), заданных в явной векторной форме, где GF(p*) - конечное поле над которым задано векторное пространство (s > 1). Представление шифруемого сообщения в виде вектора М позволяет существенно повысить производительность процедур коммутативного шифрования за счет распараллеливания операции умножения.

В случае векторного поля в качестве ключа зашифрования выбирается

достаточно большое число е, удовлетворяющее условию НОД(е, рт — 1) = 1 (НОД - наибольший общий делитель), по которому вычисляется значение

с1 =е^{то&рт-\). Зашифрование описывается формулой С = Ме, где С -

вектор, представляющий шифртекст, а расшифрование - формулой М = С^.

С некоторой вероятностью сообщение М будет соответствовать элементу поля, порядок которого является малым числом. В этом случае по М и С принципиально атакующий может вычислить некоторую информацию о секретном ключе, поэтому снижение вероятности появления таких сообщений является целесообразным. Для заданного значения т и размера характеристики поля [р>| это достигается выбором такого числа р, что число

д = [рт 1 + рт ^ + ...+ р + А^/т является простым. В этом случае практически все возможные сообщения как элементы поля 0/г(рт) будут иметь порядок, содержащий в качестве своего делителя большое простое число д, имеющего размер « (/л - 1)|р|. Пренебрежимо малое число сообщений М будет иметь порядок <л(М) < т(р-1). Вероятность случайного выбора сообщения, имеющего малый порядок Рг(ш < т(р - 1)) может быть вычислена, используя известное положение, что число элементов конечного поля у(со), имеющие порядок со, равно функции Эйлера от со, т. е. у(со) = ф(со):

Р,(Ш<т(р-1)) = (р--1У ■ Л.

¿Мр-1) Р Р +Р +- + Р +1 <7 В заключении представлены основные результаты диссертационного исследования:

1. Предложен способ уменьшения количества умножений на структурные коэффициенты при задании параметризуемой ассоциативной операции умножения векторов в конечном векторном пространстве произвольной размерности, заданном над конечным полем. Способ позволяет снизить сложность групповой операции в мультипликативных группах векторов, за счет чего повышается производительность протоколов с открытым ключом, реализуемых над трудными задачами в конечных группах векторов.

2. Показано, что если размерность векторного пространства т делит нацело порядок мультипликативной группы базового конечного поля, над которым задано векторное пространство, то при соответствующем выборе значения структурных коэффициентов образуются векторные конечные поля, представляющие собой расширение поля, над которым задано векторное пространство.

3. Установлено строение нециклических мультипликативных групп векторов в случае делимости порядка мультипликативной группы базового поля на размерность векторов и дано его описание в терминах многомерной цикличности.

4. Выведена формула, описывающая строение -примарных подгрупп, позволяющая в общем случае получить аналитические соотношения,

описывающие строение коммутативных конечных групп векторов при заданном базисе.

5. Предложены схемы построения алгоритмов ЭЦП на основе конечных групп с многомерной цикличностью и разработаны конкретные алгоритмы в рамках предложенной схемы.

6. Предложена схема открытого распределения ключей над задачей скрытого дискретного логарифмирования в конечных некоммутативных группах, отличающаяся способом генерации сопрягающего вектора и реализацией над конечными группами векторов.

7. Установлен общий гомоморфизм конечных коммутативных и некоммутативных групп векторов в базовое конечное поле, над которым заданы векторы. Показано влияние этого гомоморфизма на выбор безопасных параметров криптосхем, задаваемых над группами векторов.

8. Разработан алгоритм коммутативного шифрования с использованием конечного поля, заданного в явной векторной форме.

9. Построен протокол коллективной ЭЦП с восстановлением сообщения, перспективный для применения в технологии криптографической защиты бумажных документов.

10. Построен протокол слепой ЭЦП с восстановлением сообщения, основанный на трудности задачи дискретного логарифмирования, обеспечивающий существенное сокращение размера ЭЦП по сравнению с известным протоколом данного типа, который основан на трудности задачи факторизации.

11. Построен протокол слепой ЭЦП, взлом которой требует одновременного решения двух независимых трудных задач дискретного логарифмирования и факторизации целых чисел специального вида.

Публикации в журналах, входящих в перечень ВАК

1. Молдовян Д.Н. Конечные некоммутативные группы как примитив криптосистем с открытым ключом // Информатизация и связь. 2010. №1. С. 61-65.

2. Молдовян Д.Н. Примитивы схем цифровой подписи: строение мультипликативных конечных групп векторов // Вопросы защиты информации. 2009. №4. С. 18-24.

3. Молдовян Д.Н. Примитивы криптосистем с открытым ключом: конечные некоммутативные группы с четырехмерных векторов // Информационно-управляющие системы. 2010. № 5. С. 43—50.

4. Горячев A.A., Молдовян Д.Н., Куприянов И.А. Выбор параметров задачи скрытого дискретного логарифмирования для синтеза криптосхем // Вопросы защиты информации. 2011. № 1. С. 19-23.

5. Молдовян Д.Н., Молдовян H.A. «Особенности строения групп векторов и синтез криптографических схем на их основе» // Вестник СПбГУ. Серия 10: прикладная математика, информатика, процессы управления. 2011. Вып. 4. С. 84-93.

6. Модцовян Д.Н., Горячев A.A., Борков П.В. Варианты задания конечных некоммутативных групп четырехмерных векторов для синтеза криптосхем // Вопросы защиты информации. 2011. № 1. С. 23-28.

7. Молдовян Д.Н., Дернова Е.С., Сухов Д.К. Расширение функциональности стандартов электронной цифровой подписи // Информационно-управляющие системы. 2011. № 2. С. 63-67.

8. Молдовяну П.А., Молдовян Д.Н., Хо Нгок Зуй. Конечные группы с четырехмерной цикличностью как примитивы цифровой подписи // Информационно-управляющие системы. 2010. № 3. С. 61-68..

9. Галанов А.И., Захаров Д.В., Молдовян Д.Н., Синев В.Е. Протоколы слепой подписи на основе двух вычислительно трудных задач // Вопросы защиты информации. 2009. № 4. С.2-7.

10. Молдовян Д.Н., Молдовяну П.А.. Задание умножения в полях векторов большой размерности // Вопросы защиты информации. 2008. № 3(82). С. 12-17.

11. Молдовяну П. А., Молдовян Д.Н., Морозова Е.В., Пилькевич C.B. Повышение производительности процедур коммутативного шифрования // Вопросы защиты информации. 2009. № 4. С.24-31.

Прочие публикации

12. Молдовян Д.Н. Способ формирования общего секретного ключа двух удаленных абонентов // Патент РФ № 2420892 по заявке № 2009139874/09(056586) от 28.10.2009. / Бюл. № 16 от 10.06.2011.

13. Moldovyan D.N., Moldovyan NA. A New Hard Problem over Non-Commutative Finite Groups for Cryptographic Protocols // Springer Verlag LNCS. 2010. Vol. 6258. P. 183-194 / 5th Int. Conference on Mathematical Methods, Models, and Architectures for Computer Network Security, MMM-ANCS 2010 Proceedings. St.Petersburg, September 8-11,2010.

14. Moldovyan D.N. Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes // Quasigroups and Related Systems. 2010. Vol. 18. P. 165-176.

15. Молдовян Д.H. Выбор параметров криптосхем, основанных на сложности дискретного логарифмирования в скрытой подгруппе // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 25—26 ноября 2010, г. Санкт-Петербург. СПб.: ВАС, 2010. С. 326-330.

16. Галанов А.И., Молдовян Д.Н. Схема коллективной цифровой подписи с восстановлением сообщения // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 25-26 ноября 2011, г. Санкт-Петербург / СПб.: ВАС, 2011. С. 70-73.

17. Молдовян Д.Н., Дернова Е.С. Криптографические примитивы над конечными векторными пространствами // Труды VI Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР-2009)». Санкт-Петербург, 28-30 октября. СПб.: СПОИСУ, 2010. С. 191-197.

Подписано в печать 14.05.12. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Тирах 100 экз. Заказ 52.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Пеггербург, ул. Проф. Попова, 5

12- 17 150

-л

2012091812

61 12-5/3048

Санкт-Петербургский государственный электротехнический

университет «ЛЭТИ»

РАСШИРЕНИЕ ФУНКЦИОНАЛЬНОСТИ АЛГОРИТМОВ АУТЕНТИФИКАЦИИ И МЕХАНИЗМЫ ЗАЩИТЫ ИНФОРМАЦИИ НАД КОНЕЧНЫМИ ГРУППАМИ ВЕКТОРОВ

05.13.19 - методы и системы защиты информации, информационная безопасность

Диссертация на соискание ученой степени кандидата технических

наук

На правах рукописи

Молдовян Дмитрий Николаевич

Научный руководитель доктор технических наук профессор Советов Б .Я.

Санкт-Петербург 2012

Оглавление

Обозначения и сокращения 4

Введение 5

Глава 1. Защита и аутентификация информации в проблематике информационной безопасности 12

1.1. Методы обеспечения аутентификации 13

1.2. Алгоритмы электронной цифровой подписи 18

1.3. Некоммутативные группы и группы векторов как криптографические примитивы 26

1.4. Постановка задачи 37 Глава 2. Конечные группы и поля многомерных векторов для построения криптосхем 39

2.1. . Коммутативные группы многомерных векторов 39 2.1.1 Общий способ задания коммутативного умножения векторов для произвольных значений размерности 39

2.1.2. Условия образования конечных векторных полей и групп в случае произвольных значений размерности 41

2.1.3. Экспериментальное подтверждение условий образования векторных конечных полей 44

2.1.4. Частный случай конечных векторных групп 46

2.2. Подходы и схемы построения алгоритмов аутентификации информации на основе групп векторов 48

2.2.1. Особенности реализации классических криптосхем на основе векторных конечных полей 48

2.2.2. Способы уменьшения сложности операции умножения в векторном конечном кольце 50

2.2.3. Векторные конечные группы с многомерным циклическим строением 51

2.2.4. Схемы ЭЦП на основе векторных конечных групп с многомерной цикличностью 56 2. 3. Задание конечных некоммутативных групп векторов 58

2.3.1. Группы четырехмерных векторов. 58

2.3.2. Задание некоммутативных групп векторов четной размерности 60

2.3.3. Порядок и строение конечных некоммутативных групп четырехмерных векторов 63

2. 4. Строение примарных коммутативных подгрупп векторов 71

Выводы к главе 2 81

Глава 3. Трудные задачи и криптосхемы над конечными некоммутативными группами 83

3.1. Задача дискретного логарифмирования 83

3.2. Задача поиска сопрягающего элемента 85

3.3. Задача дискретного логарифмирования в скрытой циклической подгруппе (скрытая задача поиска сопрягающего элемента) 87

3.4. Выбор параметров криптосхем, основанных на задаче дискретного логарифмирования в скрытой подгруппе 89

3.5. Дополнительное требование к выбору параметров криптосхем, основанных на задаче дискретного логарифмирования в скрытой подгруппе 94 Выводы к главе 3 98

Глава 4. Расширение функциональности протоколов аутентификации информации 99

4.1. Протокол коллективной цифровой подписи с восстановлением сообщения 99

4.2. Протокол слепой цифровой подписи с восстановлением сообщения, основанный на сложности дискретного логарифмирования 107

4.3. Протокол слепой цифровой подписи, основанный на двух независимых трудных задачах 111

4.4. Коммутативные шифры на основе конечных групп векторов: повышение производительности процедур коммутативного шифрования

117

Выводы к главе 4 129

Список публикаций по теме диссертационного исследования 130

Заключение 132

Список литературы 134

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

Обозначение #S

Z

aeS

\а\ а\Ъ

Описание

Мощность множества 8, т.е. количество элементов в множестве 8

Множество натуральных, целых чисел

Элемент а принадлежит множеству £

Длина целого числа а или модуль числа а

Число а делит число Ъ

Операция умножения векторов

а\\Ъ

ЖЩа,Ь) a=b mod п

GF(q)

Ф)

от)

ЭЦП

ЗДЛ

эк

Конкатенация чисел (двоичных векторов) а и b Наибольший общий делитель чисел аи b Множество целых чисел по модулю п

Число а сравнимо с числом b по модулю п, т .е. а = b + Qn, где QeZ

Конечное кольцо классов вычетов по модулю п Мультипликативная группа кольца Zn

Конечно поле или поле Голуа, где q =ps, где р - просто число, называемое характеристикой конечного поля, s - натуральное число, называемое степенью поля, q - порядок поля (количество элементов поля) Функция Эйлера

Функция g(n), такая что для всех достаточно больших п выполняется|^(и)|<с|/(и)|, где с>0 - некоторая константа электронная цифровая подпись

задача дискретного логарифмирования

эллиптическая кривая

вкг

векторная конечная группа

Введение

В настоящее время информационные технологии (ИТ) широко используют компьютерную обработку, хранение и передачу информации в компьютерных сетях, построенных с использованием скоростных телекоммуникационных каналов. Широко применяются ИТ практически во всех областях общественной деятельности - управленческой, экономической, финансовой, производственной, дипломатической, военной. Во многих случаях обеспечение информационной безопасности имеет критическое значение, что обусловливает необходимость применения механизмов аутентификации, защиты и контроля целостности информации и непрерывного их совершенствования. Проблема защиты ИТ связана с задачами обеспечения доступности информационных ресурсов, аутентичности, целостности и конфиденциальности информации. Эта проблема решается на основе комплексного подхода и с применением различных средств и механизмов. Алгоритмические средства защиты ИТ, базирующиеся на современной криптографии, являются не только гибкими и эффективными, но также лежат в основе ИТ, связанных с обработкой юридически значимых документов и сообщений (управленческая, экономическая и финансовые области применения ИТ).

Основными требованиями к криптографическим алгоритмам и протоколам, используемым в качестве алгоритмических механизмов защиты информации являются их стойкость и безопасность, которые определяются лежащими в их основе вычислительно трудными задачами и уровнем развития теории, методов и алгоритмов решения задач данного типа. Наиболее широко применяемые криптографические схемы (алгоритмы и протоколы) имеют практическую стойкость и безопасность, т. е. их применение основано на экспертных оценках. Развитие алгоритмов решения трудных задач и вычислительной техники делает крайне актуальным выполнение периодических оценок стойкости и безопасности

алгоритмических механизмов защиты информации с учетом новых достижений теории и нового уровня вычислительной техники. При этом к алгоритмическим механизмам предъявляются и технологические требования, состоящие в удобстве встраивания в программные и технические средства защиты информации, высокого быстродействия и достаточно низкой стоимости аппаратной реализации. Это обусловливает актуальность развития алгоритмических средств обеспечения информационной безопасности. Ожидание появления практически действующих квантовых компьютеров заставило разработчиков таких средств обратиться к поиску новых трудных задач в качестве криптографических примитивов, для которых не известны эффективные методы решения с использованием квантовых вычислителей. Значительное число исследований в этой области связано с использованием трудных задач, формулируемых над некоммутативными группами. Недавно был предложен подход к заданию конечных групп векторов и их применению при разработке криптографических схем. В основе этого подхода лежит идея использования возможности эффективного распараллеливания групповой операции, за счет чего может быть обеспечено повышение производительности алгоритмов защиты информации. Однако для синтеза криптосхем на основе конечных групп векторов требуется найти подходы к построению конечных групп векторов различных типов, включая некоммутативные группы векторов, изучению их строения и особенностей их использования при разработке алгоритмов шифрования, электронной цифровой подписи (ЭЦП) и открытого распределения ключей.

Другим важным аспектом практического применения алгоритмов аутентификации является принципиальная возможность придания специальных свойств алгоритмам аутентификации информации, т.е. расширение функциональности последних. Это позволяет сократить время выполнения специальных процедур и уменьшить количество и суммарный объем вспомогательной информации при решении специальных

практических задач, связанных с аутентификацией.

6

В связи с ранее сказанным тема диссертационного исследования, связанная с расширением функциональности алгоритмов аутентификации информации и развитием алгоритмических механизмов защиты информации на основе применения конечных групп векторов и исследованием как самих групп векторов, так и криптосхем на их основе представляется актуальной.

Объектом исследования являются системы и средства защиты и аутентификации информации в информационно-коммуникационных технологиях.

Предметом исследования являются механизмы, примитивы, алгоритмы и протоколы криптографической защиты и аутентификации информации в средствах и системах информационной безопасности.

При выполнении диссертационного исследования использованы аппарат и методы математической статистики, теории вероятности, алгебры, теории чисел, теории сложности и криптографии.

Цель диссертационного исследования - повышение уровня безопасности и производительности криптографических механизмов защиты информации, а также расширение их функциональности.

Задачи работы включают разработку способов задания конечных коммутативных и некоммутативных групп векторов, анализ их строения, оценку криптосхем, синтезируемых на их основе, и разработку протоколов аутентификации информации с расширенной функциональностью. Решались следующие частные задачи:

1) разработка способов задания коммутативных конечных групп векторов различной размерности;

2) разработка способов задания некоммутативных конечных групп векторов различной размерности;

3) исследование строения конечных групп векторов различной размерности и связи строения со способом их задания;

4) синтез криптосхем на основе конечных групп векторов;

5) оценка стойкости синтезируемых криптосхем;

7

6) разработка схемы коллективной электронной цифровой подписи (ЭЦП) с восстановлением сообщения;

7) разработка схемы слепой ЭЦП с восстановлением сообщения, основанной на сложности задачи дискретного логарифмирования;

8) разработка схемы слепой ЭЦП, взлом которой требует одновременного решения задачи факторизации и дискретного логарифмирования.

В результате выполнения диссертационной работы получены следующие новые научные результаты:

1) получены формулы описывающие строение коммутативных групп векторов;

2) предложен способ задания некоммутативных конечных групп векторов различной размерности;

3) выведена формула для порядка некоммутативных конечных групп четырехмерных векторов;

4) разработан алгоритм коммутативного шифрования, отличающийся использованием конечных групп векторов и обладающий высокой производительностью;

5) предложена новая схема открытого распределения ключей, отличающаяся способом задания автоморфного отображения некоммутативной группы;

6) предложены подходы к синтезу алгоритмов ЭЦП с использованием конечных групп векторов;

7) установлен и доказан гомоморфизм конечных групп векторов в поле, над которым они задаются, который был использован для формулирования требований в выбору параметров криптосхем, основанных на вычислениях в некоммутативных группах;

8) построена схема слепой ЭЦП с восстановлением сообщения, основанной на сложности задачи дискретного логарифмирования;

9) разработана схема слепой ЭЦП, взлом которой требует одновременного решения задачи факторизации и дискретного логарифмирования;

10) разработана схема коллективной ЭЦП с восстановлением сообщения.

Основные положения, выносимые на защиту:

1. Схема слепой электронной цифровой подписи (ЭЦП), основанная на вычислительно трудных задачах факторизации и дискретного логарифмирования.

2. Схема открытого распределения ключей на основе трудности задачи дискретного логарифмирования в скрытой подгруппе.

3. Алгоритм коммутативного шифрования.

4. Протокол коллективной ЭЦП с восстановлением сообщения.

Научная новизна положений:

1. Схема слепой электронной цифровой подписи (ЭЦП), основанная на вычислительно трудных задачах факторизации и дискретного логарифмирования, отличающаяся тем, что для ее взлома требуется одновременно решить обе указанные задачи, благодаря чему повышается уровень безопасности схемы.

2. Схема открытого распределения ключей над задачей скрытого дискретного логарифмирования в конечных некоммутативных группах, отличающаяся использованием групп векторов и заданием коммутативной подгруппы как множества степеней элемента достаточно большого простого порядка, благодаря чему уменьшается время формирования общего секретного ключа двух удаленных абонентов.

3. Алгоритм коммутативного шифрования, отличающийся использованием конечных полей, заданных в явной векторной форме, благодаря чему обеспечивается эффективное распараллеливание операции умножения и повышение быстродействия алгоритма.

4. Протокол коллективной ЭЦП с восстановлением сообщения, отличающийся использованием задачи дискретного логарифмирования на эллиптической кривой, благодаря чему обеспечивается уменьшение размера ЭЦП и повышение быстродействия протокола.

Новыми являются также следующие частные результаты:

1) способ построения конечных некоммутативных групп векторов произвольной четной размерности;

2) формула для порядка некоммутативной конечной группы четырехмерных векторов;;

3) формула, описывающая строение произвольной примарной подгруппы по ее базису;

4) схема ЭЦП на основе конечных групп с многомерной цикличностью, отличающая использованием порождающих нескольких элементов одного порядка, принадлежащих базису группы;

5) алгоритм коммутативного шифрования, отличающийся использованием представления блоков сообщения элементами конечной группы векторов;

6) протокол слепой ЭЦП с восстановлением сообщения, основанной на сложности задачи дискретного логарифмирования;

7) протокол слепой ЭЦП, взлом которой требует одновременного решения задачи факторизации и дискретного логарифмирования;

8) протокол коллективной ЭЦП с восстановлением сообщения..

Реализация результатов. Результаты диссертационной работы

внедрены в учебный процесс СПбГЭТУ при преподавании дисциплин «Теоретические основы криптографии», «Криптографические методы защиты информации» и «Криптографические протоколы» на кафедре Автоматизированных систем обработки информации и управления.

Диссертационная работа изложена на 138 страницах, включает 4 главы, 1 рисунок, 18 таблиц и список литературы из 52 наименований.

В главе 1 рассмотрены механизмы алгоритмической защиты и аутентификации информации в ИТ. Описаны основные типы трудных задач, используемых в качестве примитивов криптографических алгоритмов и протоколов, и известные криптосхемы. Рассмотрены типы конечных алгебраических структур, используемых при построении криптосхем. Ставится задача диссертационного исследования.

В главе 2 предложены подходы к построению коммутативных и некоммутативных конечных групп векторов. Изучается их строение. Детально рассмативаются случаи коммутативных и некоммутативных групп четырехмерных векторов. Выводятся формулы описывающие строение групп векторов. Получена формула, описывающая строение примарной группы в общем случае. Формулируется задача скрытого дискретного логарифмирования для построения схем открытого распределения ключей и открытого шифрования.

В главе 3 рассматриваются потенциальные атаки на криптосхемы, построенные с использованием конечных групп векторов, в том числе атаки, связанные со сводимостью задачи дискретного логарифмирования в конечных группах векторов к задаче дискретного логарифмирования в конечном поле. Показан общий гомоморфизм групп векторов в конечное поле, над которым они заданы. Обсуждается использование данного гомоморфизма для взлома криптосхем и его влияние на выбор безопасных параметров криптоалгоритмов.

В главе 4 предложены протоколы аутентификации информации, обладающие расширенной функциональностью. Рассмотрены сценарии их практического применения, показана корректность их функционирования и обсуждается их стойкость.

В заключении представлены основные результаты диссертационного исследования.

Глава 1.

Защита и аутентификация информации в проблематике информационной безопасности

Широкое применение информационных технологий практически во всех сферах общественной деятельности сделало задачу обеспечения информационной безопасности компьютерных и телекоммуникационных систем чрезвычайно актуальной практической задачей. Эта задача решаетс