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

Косолапов Дмитрий Олегович

ПОСТРОЕНИЕ МНОГОСТОРОННИХ МУЛЬТИЛИНЕЙНЫХ

АЛГОРИТМОВ В УСЛОВИЯХ РАЗЛИЧНЫХ МОДЕЛЕЙ

БЕЗОПАСНОСТИ

05.13.18 - математическое моделирование, численные методы и

комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Владивосток 2010

Работа выполнена на кафедре информационной безопасности Дальневосточного государственного университета

Научный руководитель : доктор физико-математических наук, профессор КОРНЮШИН Павел Николаевич

Официальные оппоненты: доктор физико-математических наук, профессор НУРМИНСКИЙ Евгений Алексеевич доктор физико-математических наук, профессор СТЕПАНОВА Алёна Андреевна

Ведущая организация: Морской государственный университет имени адмирала Г.И. Невельского (г. Владивосток)

Защита состоится « 10 » декабря 2010 г. в 10:00 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

Автореферат разослан « 2 » ноября 2010 г.

Ученый секретарь диссертационного совета Д 005.007.01, к.т.н. А.В. Лебедев

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

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

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

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

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

Появление в 1976 г. асимметричной криптографии (У. Диффи и М.

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

В 90-е гг. XX в. получили распространение асимметричные криптоалгоритмы на основе эллиптических кривых. Данные алгоритмы строятся с помощью преобразования семейства алгоритмов Эль-Гамаля, а их стойкость основана на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Известно, что задача дискретного логарифмирования в конечном поле не сложнее задачи дискретного логарифмирования в группе точек эллиптической кривой, заданной над конечным полем.

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

К настоящему времени разработан ряд билинейных криптографических алгоритмов, таких как: алгоритм шифрования на основе идентификационных данных (Д. Боне, М. Франклин), алгоритм избирательного шифрования (Д.

Боне, Г. Крещенцо, Р. Островски, Г. Персиано), алгоритм подписи (Д. Боне, Б.

Линн, Х. Шахем), алгоритм слепой подписи (А. Болдырева), алгоритм мультиподписи (А. Болдырева), алгоритм короткой подписи (Ф. Занг, Р.

Сафави-Наини, В. Сусило), алгоритм распределения ключа (Р. Сакаи, К.

идентификационных данных (Д. Мэлони-Ли и Б. Либерт, Д. Квисквотер).

Данные алгоритмы обеспечивают безопасность информации при её обмене несколькими абонентами.

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

Для решения задачи обеспечения безопасного группового информационного обмена в 2002 г. Д. Боне и А. Сильверберг были предложены первые мультилинейные алгоритмы – алгоритм ключевого соглашения и алгоритм широковещательного шифрования. В данных алгоритмах было использовано мультилинейное отображение, являющееся обобщением билинейного спаривания до случая n аргументов. Также в 2002 г. Х.К. Ли, Х.С.

Ли, Я.Р. Ли было предложено семейство мультилинейных алгоритмов ключевого соглашения. Стойкость данных алгоритмов основана на сложности решения мультилинейных проблем Диффи-Хеллмана.

Предложенные мультилинейные алгоритмы имеют ряд недостатков, связанных со стойкостью, а именно: для алгоритма широковещательного шифрования Д. Боне и А. Сильверберг не показана стойкость к адаптивным атакам с выбором шифротекста, для алгоритмов ключевого соглашения Х.К.

Ли, Х.С. Ли, Я.Р. Ли не предусмотрена возможность выявления злоумышленника. Также, для ряда криптографических примитивов (таких, как шифрование на основе идентификационных данных, избирательное шифрование и шифроподпись) до настоящего времени не было предложено групповых (многосторонних) алгоритмов, что усложняет использование данных примитивов для групп абонентов.

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

Таким образом, тема проводимого в данной работе исследования является актуальной. Из актуальности темы работы следует ее цель.

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

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

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

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

3) доказательство стойкости и оценка сложности разработанных многосторонних алгоритмов.

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

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

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

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

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

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

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

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

Апробация результатов. Полученные результаты докладывались на региональной научно-технической конференции «Знание, творчество, профессионализм» (Владивосток, 2005), 3-й и 4-й Международных научнопрактических конференциях «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2006-2007), Региональной конференции студентов, аспирантов и молодых ученых по физике (Владивосток, 2006), конференции «Информационная безопасность в открытом образовании»

(Магнитогорск, 2007), 48-й, 50-й и 51-й Всероссийских научных конференциях ТОВМИ (Владивосток, 2005, 2007-2008), Российской школе-семинаре «Синтаксис и семантика логических систем» (Владивосток, 2008), Всероссийских конференциях студентов, аспирантов и молодых ученых по физике ДВГУ (Владивосток, 2007, 2009), XXXIII Дальневосточной математической школе-семинаре имени академика Е.В. Золотова (Владивосток, 2008), Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых (Томск, 2009), семинаре кафедры информационной безопасности ДВГУ (Владивосток, 2009), семинаре Института автоматики и процессов управления ДВО РАН (Владивосток, 2009).

Публикации. По материалам диссертации опубликовано 18 работ, в том числе 2 в журналах, рекомендуемых ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего наименований. Содержание работы изложено на 138 страницах текста. Работа содержит 2 таблицы и 2 рисунка.

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

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

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

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

Во втором разделе рассматриваются базовый и полный билинейные алгоритмы шифрования Боне и Франклина на основе идентификационных данных, алгоритм избирательного шифрования, алгоритм подписи Боне, Линна и Шахема, алгоритм слепой подписи, алгоритм мультиподписи, алгоритм подписи Занга, Сафави-Наини и Сусило, однораундовый алгоритм выработки общего ключа А. Жу, алгоритм распределения ключа Сакаи, Огиши и Казахара, алгоритм шифроподписи Мэлони-Ли и алгоритм шифроподписи Либерта и Квисквотера.

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

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

n -сторонняя проблема распознавания Диффи-Хеллмана, n -сторонняя вычислительная проблема Диффи-Хеллмана, мультилинейная проблема Диффи-Хеллмана (MDH), проблема инверсии Диффи-Хеллмана и общая проблема Диффи-Хеллмана.

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

n -сторонняя слабая проблема Диффи-Хеллмана заключается в сложности получения набора s1Q,..., snQ по заданному набору P, Q, s1 P,..., sn P, где P, Q G, P - образующий элемент аддитивной циклической группы G простого порядка q, а s1,..., sn *.

Обратная n -сторонняя вычислительная проблема Диффи-Хеллмана заключается в сложности нахождения bP, b Z q, удовлетворяющего равенству a1...an = rb mod q по заданному набору P, a1 P,..., an P, rP, где a1,..., an, r,а P q образующий элемент аддитивной циклической группы G простого порядка q.

Обобщенная мультилинейная проблема Диффи-Хеллмана (GMDH – General Multilinear Diffie-Hellman problem) заключается в сложности получения набора Q, µ (Q, P2,..., Pn +1 )a...a по заданному набору P, a2 P, a3 P,..., an +1 P, где элементы a2, a3,..., an +1 *q выбираются случайно, Q, P2,..., Pn +1 - произвольные элементы аддитивной циклической группы G простого порядка q, P образующий элемент группы G1, а µ - n -мультилинейное отображение.

Мультилинейная проблема распознавания Диффи-Хеллмана (DMDH – Decisional Multilinear Diffie-Hellman problem) заключается в сложности P, a1 P, a2 P,..., an +1 P, r, где элементы a1, a2,..., an +1, r * выбираются случайно, P q образующий элемент аддитивной циклической группы G простого порядка q, а µ - n -мультилинейное отображение.

Мультилинейная проблема распознавания Диффи-Хеллмана для случая хеширования (DHMDH – Decisional Hash Multilinear Diffie-Hellman problem) заключается в сложности проверки равенства r = H ( µ ( P, P,..., P)a a...a ) по n+ заданному набору P, a1 P, a2 P,..., an +1 P, r, где a1, a2,..., an +1, r *q выбираются циклическая группа простого порядка q, P - образующий элемент аддитивной циклической группы G1 простого порядка q, а µ - n -мультилинейное отображение.

Во второй главе предложены мультилинейные алгоритмы, полученные с помощью обобщения соответствующих билинейных алгоритмов на мультилинейный случай, рассмотрены возможности построения данных алгоритмов в модели k -ичного дерева и возможности их использования в случае отсутствия мультилинейных отображений для всех значений n. Вторая глава состоит из 3-х разделов.

В первом разделе построены многосторонние мультилинейные алгоритмы.

Построен базовый мультилинейный алгоритм широковещательного шифрования на основе идентификационных данных (MulBasicIdent). Данный алгоритм решает задачу шифрования сообщения для n абонентов с идентификаторами ID1,..., IDn. Алгоритм представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования.

Пусть k - принимаемый алгоритмом на этапе инициализации параметр стойкости. Этап инициализации представлен следующими процедурами.

1. На основе k Центром генерации закрытых ключей (PKG) генерируется простой порядок q групп G1 и G2, 2n -мультилинейное отображение µ : G1 G1... G1 G2 и произвольный образующий элемент группы P G1, где G1 - аддитивная циклическая группа, а G2 - мультипликативная циклическая группа.

3. Центром PKG выбираются криптографические хеш-функции H1 :{0,1} G1* и H 2 : G2 {0,1}l для некоторого l, где {0,1}* - множество двоичных векторов произвольной длины, а {0,1}l - множество двоичных векторов длины l.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества = {0,1}l и C = G1* {0,1}l соответственно, элементы s1,..., sn *q являются мастер-ключами абонентов, а системными Особенностью алгоритмов на основе идентификационных данных является необходимость получения абонентом закрытого ключа у Центра PKG.

На этапе получения закрытого ключа проводятся следующие вычисления:

1) для идентификаторов абонентов ID1,..., IDn {0,1}* Центром PKG вычисляются QID = H1 ( ID1 ) G1*,..., QID = H1 ( IDn ) G1* ;

2) Центром PKG вычисляются и передаются абонентам по s1,..., sn - мастер-ключи.

На этапе шифрования сообщения M с помощью идентификаторов ID1,..., IDn {0,1}* абонентом выполняются следующие операции:

g = µ (QID1,..., QIDn, Ppub1,..., Ppubn ) G2.

открытый текст следующим образом:

V H 2 ( µ (QID,..., QID, d ID, QID,..., QID, Ppub,..., Ppub, U, Ppub,..., Ppub )) = M.

Корректность алгоритма подтверждается выполнением следующего равенства, смысл которого сводится к подстановке в аргумент функции H 2 на U = rP :

µ (QID1,..., QIDi1, d IDi, QIDi+1,..., QIDn, Ppub1,..., Ppubi1, U, Ppubi+1,..., Ppubn ) = = µ (QID1,..., QIDn, Ppub1,..., P,..., Ppubn ) si r = µ (QID1,..., QIDn, Ppub1,..., Ppubn ) r = g r.

На основе алгоритма MulBasicIdent с помощью метода ФуджисакиОкамото построен полный алгоритм широковещательного шифрования на основе идентификационных данных (MulFullIdent, МКШОИД).

МКШОИД также представлен этапами инициализации, получения закрытого ключа, шифрования и расшифрования.

Пусть k - принимаемый алгоритмом на этапе инициализации параметр стойкости. Этап инициализации представлен следующими процедурами.

1. На основе k Центром PKG генерируется простой порядок q групп G1 и G2, 2n -мультилинейное отображение µ : G1 G1... G1 G2 и произвольный образующий элемент группы P G1, где G1 - аддитивная циклическая группа, а G2 - мультипликативная циклическая группа.

2. Центром PKG случайным образом выбираются элементы s1,..., sn *q 3. Центром PKG выбираются криптографические хеш-функции H1 :{0,1} G1*, H 2 : G2 {0,1}l для некоторого l, H 3 :{0,1}l {0,1}l * и H 4 :{0,1}l {0,1}l.

В данном алгоритме пространства сообщений и шифротекстов представляют собой множества = {0,1}l и C = G1* {0,1}l {0,1}l соответственно, элементы s1,..., sn *q являются мастер-ключами абонентов, а системными параметрами является набор G1, G2, µ, l, P, Ppub,..., Ppub, H1, H 2, H 3, H 4.

На этапе получения закрытого ключа проводятся следующие вычисления:

1) для идентификаторов абонентов ID1,..., IDn {0,1}* Центром PKG вычисляются QID = H1 ( ID1 ) G1*,..., QID = H1 ( IDn ) G1* ;

2) Центром PKG вычисляются и передаются абонентам по защищенному каналу закрытые ключи d ID = s1QID,..., d ID = snQID, d ID G1, где s1,..., sn - мастер-ключи.

На этапе шифрования сообщения M с помощью идентификаторов ID1,..., IDn {0,1}* абонентом выполняются следующие операции:

g = µ (QID1,..., QIDn, Ppub1,..., Ppubn ) G2.

идентификатором IDi выполняются следующие процедуры.

1. Если U G1*, то шифротекст не принимается. В противном случае, с помощью закрытого ключа d ID G1* вычисляется: i V H 2 ( µ (QID1,..., QIDi1, d IDi, QIDi+1,..., QIDn, Ppub1,..., Ppubi1,U, Ppubi+1,..., Ppubn )) =.

Если равенство не выполняется, то шифротекст не принимается, в противном случае полагается, что M - открытый текст.

Корректность алгоритма подтверждается аналогично MulBasicIdent.

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

Во втором разделе мультилинейный алгоритм подписи построен в модели k -ичного дерева.

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

В третьей главе построены математические модели безопасности широковещательного шифрования, доказана стойкость предложенных алгоритмов MulBasicIdent и MulFullIdent (МКШОИД) в условиях данных моделей и проведена оценка вычислительной сложности всех предложенных в главе 2 криптографических алгоритмов. Третья глава состоит из 3-х разделов.

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

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

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

Во время инициализации запросчик принимает параметр стойкости k, запускает процедуру инициализации алгоритма, передает атакующему алгоритму параметры params и сохраняет мастер-ключи master keys в секрете.

Определены G1 - аддитивная циклическая группа простого порядка q с образующим элементом P, и G2 - мультипликативная циклическая группа простого порядка q.

На этапе 1 атакующий алгоритм генерирует запросы q1,..., qm и отправляет их запросчику, где qi является:

запросом закрытого ключа IDi. В данном случае запросчик запускает процедуру генерации закрытого ключа di G1, соответствующего открытому ключу IDi, и передает di атакующему алгоритму.

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

Данные запросы проводятся адаптивно, т.е. каждый запрос qi может зависеть от ответов на запросы q1,..., qi 1.

После завершения этапа 1 атакующий алгоритм генерирует 2 открытых текста M 0, M 1 равной длины и набор идентификаторов абонентов ID1,..., IDn, для которых он проводит атаку, где - множество открытых текстов произвольной длины. Единственным ограничением является тот факт, что IDi IDj при i = 1,..., n, j = 1,..., m во время этапа 1.

Постановка задачи запросчика атакующему алгоритму имеет следующий Cb = Encrypt ( params, ID1,..., IDn, M b ) алгоритму.

На этапе 2 атакующий алгоритм генерирует и отправляет запросчику дополнительные запросы qm+1,..., ql, где qi является:

i = 1,..., n, j = m + 1,..., l. Запросчик отвечает так же, как и во время этапа 1.

i = 1,..., n, j = m + 1,..., l. Запросчик отвечает так же, как и во время этапа 1.

Данные запросы могут проводиться адаптивно, как и во время этапа 1.

В качестве результата атакующий алгоритм возвращает бит b {0,1} и выигрывает игру, если b = b.

Выигрышем при проведении атаки злоумышленника A на алгоритм E совпадении значений битов b и b.

Атакующий алгоритм в определенной выше игре называется IND-IDBCCA злоумышленником. Если для всех полиномиальных во времени IND-IDBCCA злоумышленников A, способных проводить запросы закрытого ключа и расшифрования на алгоритм E, функция AdvE, A (k ) является пренебрежимо малой, то определенная выше игра является математической моделью безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста, а алгоритм E в условиях данной модели является INDIDB-CCA стойким (семантически стойким к адаптивной атаке с выбором шифротекста). В современной криптографии при построении алгоритмов шифрования проводится доказательство их стойкости в модели безопасности при адаптивной атаке с выбором шифротекста. Данная атака является самой сильной среди существующих атак на алгоритмы шифрования.

Злоумышленник A, способный проводить только запросы закрытого ключа, называется IND-IDB-CPA злоумышленником. Если для всех полиномиальных во времени IND-IDB-CPA злоумышленников A, способных проводить запросы закрытого ключа на алгоритм E, функция AdvE, A (k ) является пренебрежимо малой, то игра атакующего алгоритма и запросчика является математической моделью безопасности широковещательного шифрования при адаптивной атаке с выбором открытого текста, а алгоритм E в условиях данной модели является IND-IDB-CPA стойким (семантически стойким к адаптивной атаке с выбором открытого текста).

Автором работы доказана стойкость алгоритма MulBasicIdent в условиях математической модели безопасности широковещательного шифрования при адаптивной атаке с выбором открытого текста и предположении сложности мультилинейной проблемы Диффи-Хеллмана (MDH).

Для доказательства IND-IDB-CCA стойкости алгоритма MulFullIdent доказана IND-CPA стойкость связанного алгоритма MulBasicPub - алгоритма широковещательного шифрования с открытым ключом (не использующего идентификационных данных). MulBasicPub состоит из 3-х процедур – генерации ключа, шифрования и расшифрования.

На этапе генерации ключа по заданному параметру стойкости k + алгоритмом выполняется:

1) запускается генератор G и на основе k генерируются 2 группы µ : G1 G1... G1 G2, выбирается произвольный образующий элемент группы вычисляются Ppub = s1P,..., Ppub = sn P, далее случайным образом выбираются QID1,..., QIDn G ;

3) выбирается криптографическая хеш-функция H 2 : G2 {0,1}w для некоторого w ;

4) возвращается открытый ключ абонента с индексом i - набор q, G1, G2, µ, w, P, Ppub, QID, H 2 и закрытый ключ d ID = si QID G1*.

Для шифрования сообщения M {0,1} выбирается случайный элемент * g = µ (QID1,..., QIDn, Ppub1,..., Ppubn ) G2.

закрытого ключа d ID G1* вычисляется:

V H 2 ( µ (QID1,..., QIDi1, d IDi, QIDi+1,..., QIDn, Ppub1,..., Ppubi1, U, Ppubi+1,..., Ppubn )) = M.

Доказательство стойкости алгоритма MulBasicPub следует из следующей леммы.

Лемма 3.4 Пусть H 2 : G2 {0,1}w - случайный оракул, где w, а A - INDCPA злоумышленник, имеющий выигрыш (k ) при атаке на MulBasicPub.

Предположим, что A выполняет в общем qH > 0 запросов к H 2 для каждого абонента, qH. Тогда существует алгоритм B, решающий проблему MDH более O(n * time( A)), где n - количество абонентов, а time( A) - время работы злоумышленника A.

С помощью данной леммы и ряда утверждений доказана стойкость алгоритма MulFullIdent (МКШОИД) в условиях математической модели безопасности широковещательного шифрования при адаптивной атаке с выбором шифротекста и предположении сложности MDH. Следующая теорема представляет собой один из основных результатов диссертации.

Теорема 3.7 В предположении, что хеш-функции H1, H 2, H 3, H 4 являются случайными оракулами, алгоритм MulFullIdent является IND-IDB-CCA стойким при предположении сложности проблемы MDH в генерируемых генератором G группах. Пусть существует IND-IDB-CCA злоумышленник A, имеющий для каждого абонента выигрыш (k ) при атаке на MulFullIdent, и A проводит атаку за время, не превышающее t (k ), где k - параметр стойкости. Пусть A выполняет не более qE запросов закрытого ключа, не более qD H 2, H 3, H 4 соответственно. Тогда существует алгоритм B, решающий MDH для генератора G, со временем выполнения t1 (k ), при этом для его выигрыша и времени выполнения справедливы следующие неравенства:

n - количество абонентов, w Доказательство теоремы основано на последовательном применении доказанных утверждений и леммы. Возможность проведения атаки IND-IDBCCA злоумышленником на алгоритм MulFullIdent с выигрышем (k ) и временем t (k ) приводит к возможности проведения атаки IND-CCA временем t O(t ) (утверждение 3.9). В свою очередь, возможность проведения атаки IND-CCA злоумышленником на алгоритм MulBasicPubhy с выигрышем и временем t приводит к возможности проведения атаки IND-CPA FOadv (, qH, qH, qD ) и временем t FOtime (t, qH, qH ) (утверждение 3.8).

Возможность проведения атаки IND-CPA злоумышленником на алгоритм MulBasicPub с выигрышем и временем t приводит к возможности решения временем t O(nt ) (лемма 3.4).

Из приведенных выше утверждений получена оценка выигрыша злоумышленника при решении проблемы MDH и его времени работы:

Теорема доказана.

В сравнении с предложенным Боне и Сильверберг алгоритмом мультилинейного широковещательного шифрования предложенный алгоритм МКШОИД является более безопасным, т.к. обладает стойкостью к самому сильному типу атак злоумышленника.

В третьем разделе проведена оценка вычислительной эффективности предложенных в главе 2 мультилинейных алгоритмов. Показано, что МКШОИД является вычислительно и связно более эффективным, чем последовательное применение аналогичного по стойкости билинейного алгоритма Боне и Франклина.

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

В первом разделе рассмотрены результаты Х.К. Ли, Х.С. Ли, Я.Р. Ли, полученные в 2002 г.

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

На этапе инициализации проводится генерация параметров алгоритма.

Пусть G1 и G2 - мультипликативные циклические группы одинакового простого порядка p, а g - образующий элемент группы G1. Пусть заданы 2 хеш-функции H1 :{0,1}* G1* и H 2 : G1* *p. Пусть ID1,..., IDn - идентификаторы n абонентов A1,..., An, вырабатывающих общий секретный ключ. Пусть en 1 : G1n 1 G2 - (n 1) мультилинейное отображение.

На этапе генерации и рассылки закрытых ключей для каждого абонента с идентификатором IDi (1 i n ) Центром PKG вычисляется открытый ключ QID = H1 ( IDi ) G1. Далее Центром PKG генерируется набор случайных целых чисел s1,..., sn [1, p 1], являющихся мастер-ключами абонентов. По данным мастер-ключам Центром PKG вычисляется набор открытых ключей Ppub = g H ( H ( ID ) ),..., Ppub = g H ( H ( ID ) ) G1, набор долгосрочных закрытых ключей d ID1 = H1 ( ID1 ) s1,..., d IDn = H1 ( IDn ) sn G долгосрочный закрытый ключ по защищенному каналу.

На этапе публикации каждым абонентом Ai выбирается случайное целое На этапе выработки ключа по полученным значениям и идентификаторам i -м абонентом вычисляется набор открытых ключей QID = H1 ( IDi ) G1 (1 i n ). Далее вычисляется ключ следующего вида Процедура верификации заключается в следующем. Выработанный ключ каждый абонент зашифровывает с помощью своего идентификатора (например, билинейным алгоритмом шифрования Боне и Франклина) и отправляет полученное значение Центру генерации закрытых ключей PKG. Центр PKG расшифровывает полученные значения и проверяет равенство всех выработанных ключей. В случае равенства Центр PKG широковещательно рассылает всем абонентам сигнальное сообщение одобрения передачи. В случае обнаружения одного или более ключей, не совпадающих с другими ключами, Центр PKG широковещательно рассылает сообщение отказа передачи и идентификаторы абонентов, являющихся злоумышленниками.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Доказано, что алгоритм МКШОИД обладает стойкостью к адаптивным атакам с выбором шифротекста при предположении сложности проблемы MDH. Для обеспечения безопасного группового обмена информацией алгоритм МКШОИД является вычислительно и связно более эффективным, чем многократное применение билинейного алгоритма Боне и Франклина.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Гончаров С.М., Косолапов Д.О., Харин Е.А. Выработка уникальных псевдослучайных последовательностей на основе клавиатурного почерка // Научно-практическая конференция «Информационная безопасность в открытом образовании». Тезисы докладов. - Магнитогорск: МаГУ, 2007. – С.

65-66.

2. Гончаров С.М., Косолапов Д.О., Харин Е.А. Мультилинейная схема шифрования Боне-Франклина на основе идентификационных данных // Научнопрактическая конференция «Информационная безопасность в открытом образовании». Тезисы докладов. - Магнитогорск: МаГУ, 2007. – С. 67-69.

3. Гончаров С.М., Косолапов Д.О. Использование мультилинейных отображений для построения безопасных систем группового обмена данными // Российская школа-семинар «Синтаксис и семантика логических систем».

Тезисы докладов. - Владивосток: Изд-во Дальнаука, 2008. – С. 13-16.

4. Корнюшин П.Н., Гончаров С.М., Косолапов Д.О. Схема короткой групповой подписи в модели k-ичного дерева // Материалы 51-й всероссийской научной конференции. - Владивосток: ТОВМИ, 2008. - С. 79-81.

5. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Хеш-цепи в многосторонних платежах // Материалы XLVIII Всероссийской межвузовской научно-технической конференции. - Владивосток: ТОВМИ, 2005. - C. 75-76.

6. Косолапов Д.О. Многосторонние микроплатежи и ведение счета клиента в мобильной сети // Сборник докладов региональной научнотехнической конференции «Знание, творчество, профессионализм». Владивосток: МГУ им. адм. Г.И. Невельского, 2005. - C. 418-422.

7. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Криптосистемы на основе идентификационных данных для обеспечения безопасности информационного обмена в мобильной телефонии // Материалы 3-й Международной Научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении». - Воронеж: ВИЭСУ, 2006. - С. 271-273.

8. Косолапов Д.О., Гончаров С.М. Оптимизация билинейного Тейтспаривания в группе точек эллиптической кривой на базе алгоритма Миллера // Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. - Владивосток: ДВГУ, 2006. - С. 168-169.

9. Косолапов Д.О. Возможности построения криптосистем на основе мультилинейных форм // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 14-16 ноября 2007. Материалы конференции. Владивосток: ДВГУ, 2007. – C. 120-121.

10. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Мультилинейные отображения и возможности построения новых криптосистем // Материалы 50й Всероссийской научной конференции. Т. 2. - Владивосток: ТОВМИ, 2007. – С. 39-40.

11. Косолапов Д.О., Корнюшин П.Н. Обобщение билинейных криптосистем шифрования и подписи // Материалы IV международной научнопрактической конференции «Интеллектуальные технологии в образовании, экономике и управлении 2007». - Воронеж: ВИЭСУ, 2007. - С. 285-288.

12. Косолапов Д.О., Гончаров С.М. Групповая мультилинейная схема электронно-цифровой подписи // XXXIII Дальневосточная математическая школа-семинар имени академика Е.В. Золотова: тезисы докладов. Владивосток: Изд-во Дальнаука, 2008. – С. 18.

13. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н.

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

научных статей. - Барнаул: Изд-во Алт. Ун-та, 2008. - С. 145-150.

14. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н.

Использование рисунка радужной оболочки глаза для генерации ключевой пары // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 30-31.

15. Косолапов Д.О., Харин Е.А., Гончаров С.М., Корнюшин П.Н.

Мультилинейные протоколы в асимметричной криптографии // Доклады Томского государственного университета систем управления и радиоэлектроники, 2(18), часть 1. - Томск: Изд-во ТГУСУР, 2008. - С. 51-53.

16. Косолапов Д.О., Харин Е.А., Корнюшин П.Н. Мультилинейные криптосистемы шифрования, подписи и распределения ключей // Проблемы правовой и технической защиты информации: сб. научных статей. - Барнаул:

Изд-во Алт. Ун-та, 2008. - С. 116-120.

17. Косолапов Д.О., Гончаров С.М., Корнюшин П.Н. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Всероссийская конференция студентов, аспирантов и молодых ученых по физике. 27-29 апреля 2009. Материалы конференции. – Владивосток: ДВГУ, 2009. – C. 109-111.

18. Косолапов Д.О. Протокол ключевого соглашения на основе идентификационных данных с возможностью выявления злоумышленника // Материалы докладов Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых 12-15 мая 2009 г, Тематический выпуск «Системная интеграция и безопасность», ч. 3. – Томск: В-Спектр, 2009.

- С. 277-283.

Личный вклад автора. Все основные результаты, представленные в диссертационной работе, получены автором самостоятельно. Работы [6, 9, 18] выполнены автором самостоятельно. В работах [2-5, 7, 8, 10-12, 15-17] автор участвовал в постановке проблемы, провел необходимые теоретические исследования, связанные с построением математических моделей безопасности и разработкой мультилинейных алгоритмов, и соответствующие вычисления, связанные с доказательством стойкости предложенных алгоритмов для решения задачи обеспечения безопасности группового информационного обмена. В работах [1, 13, 14] автор сформулировал возможность использования в многосторонних алгоритмах ключевых последовательностей на основе клавиатурного почерка и рисунка радужной оболочки глаза.

ПОСТРОЕНИЕ МНОГОСТОРОННИХ МУЛЬТИЛИНЕЙНЫХ

АЛГОРИТМОВ В УСЛОВИЯХ РАЗЛИЧНЫХ МОДЕЛЕЙ

БЕЗОПАСНОСТИ

Подписано в печать Усл. печ. л. 1,0. Уч.-изд. л. 0, Издано ИАПУ ДВО РАН, г. Владивосток ул. Радио, Отпечатано участком оперативной печати ИАПУ ДВО РАН г. Владивосток ул. Радио,