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

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

Гончаров Сергей Михайлович

ПОСТРОЕНИЕ ПРОТОКОЛОВ КЛЮЧЕВОГО СОГЛАШЕНИЯ КРИПТОКОНФЕРЕНЦИИ НА ОСНОВЕ к-МУЛЬТИЛИНЕЙНЫХ ОТОБРАЖЕНИЙ

Специальность: 05.13.18- Математическое моделирование, численные методы

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

Автореферат

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

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

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

Научный руководитель: доктор физико-математических наук,

профессор Корнюшин П.Н.

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

профессор Катрахов В.В.

кандидат технических наук, доцент Волошина В.Н.

Ведущая организация: Томский государственный университет систем

управления и радиоэлектроники

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

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

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

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

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

А.В.Лебедев

имя

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

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

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

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

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

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

В 2000 году Джо предложил однораундовый трехсторонний протокол ключевого согла-

шения. Протокол Джо - аналог протокола Дифщи-вОЛйЛЛШИ общий ключ не

БИБЛИОТЕКА ./ 1

ШИШЬКА »

"9Ш !

СП»

•а ______

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

В протоколе Джо используются билинейные отображения. Наличие практических алгоритмов для построения п-мультилинейных форм позволило бы построить однораундовый протокол (п+1)-стороннего ключевого соглашения. В 2002 году Боне и Сильверберг описали такой протокол, а несколько позже корейские авторы предложили первую аутенти-фицированную версию такого протокола.

Однораундовый протокол многостороннего ключевого соглашения Боне-Силверберг, основан на существовании п-мультилинейных отображений для больших значений «п» («п» определяется размером группы и может достигать нескольких тысяч). Предполагается маловероятным появление алгоритмов генерации п-мультилинейных отображений для таких значений п в ближайшие годы. В тоже время представляется вполне реальным появление эффективно-вычислимых п-мультилинейных преобразований для малых значений п (п=3,4,5). В связи с этим возникает задача разработки протоколов Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующих преимущества к-мультилинейных отображений для малых значений к.

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

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

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

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

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

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

5. Исследование эффективности разработанных протоколов и их сравнение с протоколами, известными ранее.

На защиту выносятся следующие положения.

1. Алгоритм базового неаутентифицированного протокола группового соглашения со структурой дерева (МГКССД), реализующий преимущества использования к-мультилинейных отображений и безопасный по отношению к атакам пассивного противника.

2. Элементы теории мультилинейной криптографии (с использованием 1с-мультилинейных отображений), включающие:

- схему мультиподписи;

- схему объединенной подписи;

- криптосистему на основе идентификационных данных (КСОИД);

- обобщение протокола Ченга-Лиу-Кима.

3. Доказуемо безопасная в условиях стандартной модели безопасности аутентифици-рованная версия протокола МГКССД с использованием мультилинейной объединенной подписи.

4. Аутентифицированная версия протокола МГКССД в условиях мультилинейной криптосистемы на основе идентификационных данных.

Научная новизна работы

1. Разработан оригинальный протокол Мультилинейного Группового Ключевого Соглашения со Структурой Дерева (МГКССД), использующий преимущества к-мультилинейных отображений для малых значений к и обладающий более высокой связной эффективностью по сравнению с протоколами соответствующего класса.

2. Разработаны для случая к-мультилинейных отображений: схемы мультиподписи и объединенной подписи, криптосистемы на основе идентификационных данных (КСОИД), обобщения протокола Ченга-Лиу-Кима.

3. Разработана аутентифицированная версия протокола МГКССД с использованием впервые описанной мультилинейной КСОИД.

4. Разработана доказуемо безопасная в условиях стандартной модели безопасности версия протокола МГКССД с использованием описанной схемы мультилинейной объединенной подписи.

Научная и практическая ценность. В диссертации разработан необходимый аппарат, позволяющий реализовывать преимущества £-мультилинейных отображений для малых значений к при обеспечении безопасности конференцсвязи. Описанный в диссертации протокол МГКССД имеет преимущества в связной эффективности по сравнению с известными протоколами ключевого соглашения со структурой дерева. Для частного случая к=2 протокол МГКССД дает сокращение до 40 % от суммарного объема передаваемой по каналам связи информации и проводимых экспоненциирований по сравнению с единственным описанным на настоящий момент протоколом конференцсвязи, использующим билинейные спаривания (протокол Баруа-Дутга-Саркара - «ВТЭ»). Эффективность протокола МГКССД при к>2 определяется сложностью вычисления конкретных реализаций к-мультилинейного отображения. С учетом предложенной процедуры действий участников при динамическом изменении состава группы, а также возможностей, которые дает структура (к+1)-ичного дерева, протокол МГКССД может дать преимущества в сравнении с любым известным протоколом группового ключевого соглашения. Разработанный в диссертации аппарат, касающийся использования мультилинейных отображений в области информационной безопасности, имеет самостоятельное значение и может быть использован для дальнейших разработок в области информационной безопасности.

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

Апробация работы, публикации. Основные результаты работы докладывались на специальной научно-практической конференции (Москва, 1984г.), Всероссийских межвузовских научно-технических конференциях (Владивосток, 2002-2004гт.), региональной конференции студентов, аспирантов и молодых ученых (Владивосток, 2003-2004гг.).

Всего опубликовано 15 статей, из них по теме диссертации 14 работ.

Реализация результатов. Результаты диссертации использовались при проведении специальных работ в в/ч 69171, что подтверждено актом внедрения. Часть материалов использована при разработке учебной программы по курсу «Дополнительные главы криптографических протоколов».

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

писного текста, содержит 10 рисунков и 3 таблицы. Список литературы содержит 74 наименования.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении рассматриваются задачи разработки протоколов группового ключевого соглашения с использованием к-мультилинейных отображений для малых значений к.

Глава 1 Проблема многостороннего ключевого соглашения и мультилинейные

отображения

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

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

В параграфе 1.3 рассматривается однораундовый протокол (п+1)-стороннего ключевого соглашения на основе п-мультилинейного отображения. Описан однораундовый (п+1)-сторонний протокол ключевого обмена на основе генератора п-мультилинейных отображений.

Глава 2 Неаутентифицированный Протокол Мультилинейного Группового Ключевого Соглашения со Структурой (к+1)-ичного Дерева (МГКССД)

В параграфе 2.1 приводится описание базового протокола МГКССД - неаутентифи-цированной версии Протокола Мультилинейного Группового Ключевого Соглашения со Структурой (к+1)-ичного Дерева. Выполнение протокола заключается в построении ключевого (к+1)-ичного дерева участников криптоконференции. Безопасность протокола основана на сложности ОНМОН-проблемы - решающей мультилинейной проблемы Диф-фи-Хэллмана для случая хеширования. Схема ключевого дерева приведена на рис. 1.

Основу протокола МГКССД составляют 2 подпротокола (к+1)-стороннего и I-сторонний (/<к+1) ключевого соглашения. Данные подпротоколы разработаны на базе протокола Боне-Сильверберг (к+1) -стороннего ключевого соглашения на основе к-мультилинейного отображения.

/-сторонний вариант протокола позволяет вырабатывать общий ключ между т пользователями на основе к-мультилинейного отображения. При этом первые с2= к+1-с1т {с!=\(к + \)1 т\) пользователей вырабатывают и рассылают дополнительные ключи gг

g°', &+я=Вй('').....g,tc¡m -gй',м, выступая в роли недостающих виртуальных наборов

пользователей с номерами /+тя,...,/+С//и, а последние т-с2 пользователей вырабатывают и рассьшают дополнительные ключи g|Hc¡^)m (на один ключ меньше).

Уровни Я

Я-1

11 I 2 И-1

1 2 Ш

...2 в^Тгъс

1 2 3.... Мл 1 2 ... . М, I 2 ки 1 2 к+1 -----' V__У4-

I 2 к+1 _

Мл-участников астников М„—полных наборов пользователей (левая подгруппа) (средняя подгруппа)_(правая подгруппа)_

Рис.1. Схема ключевого дерева на основе к-мультилинейного отображения

Ключевое дерево состоит нескольких уровней, начиная с уровня 0. На каждом уровне располагаются наборы пользователей (НП), которые имеют (или собираются выработать) общий секретный ключ. Наверху (на уровне Я) находится единственный общий ключ конференцсвязи. Уровнем ниже находятся к+1 ключей наборов пользователей уровня Н-1. И так далее, при понижении уровня количество ключей (и соответственно количество наборов пользователей увеличивается в (к+1) раз). Исключение составляет нулевой

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

Все участники делятся на 3 подгруппы Л (левая), С (средняя) и П (правая). Некоторые подгруппы могут быть пустыми. Каждый из участников, входящих в левую подгруппу, сам формирует набор пользователей (т.е. набор состоит лишь из одного пользователя). Участники, входящие в правую подгруппу формируют лишь полные наборы пользователей (т.е. наборы, состоящие ровно из к+1 пользователей). Участники, входящие в среднюю подгруппу, формируют неполный набор пользователей (т.е. количество участников в этом наборе 1< Мс< к+1) . .

Количество уровней (раундов алгоритма) R(mj=["logitl гп\.

Утверждение 2.1 Для окончательного общего ключа KEY для m участников в процедуре TREE KEY справедливо следующее

KEY= s\R) = S=H(e (g, g.....g)^^),

где R ~R(m), m>k+l.

При этом все пользователи могут вычислить общий ключ KEY= if1.

В параграфе 2.2 обсуждаются вопросы безопасности протокола МГКССД против пассивного противника.

Решающая мулътилинейная проблема Диффи-Хеллмана для случая хеширования в {в„вг,е) (DHMDH):

Для g.g"1.....g"'" е Gi {a,, ...,a„+Je Z\), односторонней хэш-функции Н: Z* и re Z*

проверить равенство r-Щe(g,...,g)°' ""') mod q.

Сформулирована Проблема решения группового ключевого соглашения на основе (к+1)-ичного дерева (ПРГКСОД) для протокола МГКССД и показано, что эта проблема сложна для пассивного противника, сведением сложности этой проблемы к сложности DHMDH-проблемы.

Решающая групповая хешированная мулътилинейная проблема Диффи-Хеллмана на основе дерева в (Gt,G2,e):

Определить, является ли данное число общим ключом криптоконференции, вычисляемым по протоколу МГКССД.

Теорема 2.2 Если DHMDH проблема в (G,,G2,e) - сложна, тогда общий ключ криптоконференции, сгенерированный в процессе выполнения неаутентифицированного протокола МГКССД, невозможно отличить от случайного числа полиномиальным алгоритмом.

В параграфе 2.3 обсуждаются вопросы динамического изменения членства группы. Определены операции добавления и удаления участников криптоконференции. Утверждение 2.3 Пусть ключ криптоконференции для m пользователей вычисляется по (к+1)-ичному ключевому дереву с количеством уровней R(m). При добавлении участника необходимо вычислить новые общие ключи лишь для R наборов пользователей в случае m < (k+l)R, или для R+1 НП в случае m = (k+l)R. ( Заметим, что общее количество НП в ключевом дереве Nm >2(k+l)R'1).

Следствие 2.4 При добавлении нового участника доля НП, для которых необходимо произвести вычисления общего ключа заново, не превышает (R+1)/ 2(k+l)R"'.

Утверждение 2.5 В протоколе МГКССД операция удаления участника требует проведения до 2 раз большего объема вычислений по сравнению с операцией добавления участника.

Глава 3 Аутентифицированные версия протокола МГКССД В параграфе 3.1 описаны следующие схемы:

- k-мультилинейной мультиподписи;

- к-мультилинейной объединенной подписи

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

Утверждение 3.1 Если существует ¿-мультилинейное отображение е: G" -*G1 , то для кортежа (а, а*, J3, р1") имеем:

a=bmodq о еф, a", g,..„ g)= a, g,..., g), где q - порядок группы G/, g - генератор группы G/.

Следствие 3.2 Если существует fc-мультилинейное отображение е: G" -> G2, то £Ю#-проблема в G/ - легка.

Следствие 3.3 Если существует £-мультилинейное отображение е: б" й2,

то б; - ОБН-группа.

Следствие 3.3 позволяет использовать безопасную схему мультиподписи для ОБН-групп, предложенную Болдыревой в протоколе МГКССД.

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

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

Подпись. Каждый участник данной схемы по имеемому секретному ключу х и сообщению Мб {0,1}*, вычисляет к-Н(М) и а=\?. Подписью является <ге С/.

Проверка. По имеемому открытому ключу пользователярк, сообщению Ми подписи а, вычисляется И-Н(М). Подпись считается истинной, если выполняется равенство е(а, g, ¿)=е(Ь рк, ж).

Объединение. Для подмножества пользователей ¿с V, участвующих в генерации объединенной подписи, каждому участнику приписывается индекс / из диапазона 1< г < I, где 1=Щ. Каждый пользователь С/,еХ, генерирует подпись «туе О/для сообщения М(е {0,1}* по своему выбору. Сообщения М1 должны быть попарно различны. Вычисляется •

Объединенной подписью является сге б/.

Проверка объединения. Даны: объединенная подпись еге б/ для объединяемого подмножества пользователей Ь , проиндексированных, как указано выше, набор подписываемых сообщений М(е {0,1}" и открытые ключи е 01 для всех участников и,еЬ.

Для проверки подписи выполняются следующие действия:

1. Убедиться, что сообщения М< все различны, отвергнуть подпись в противном случае.

2. Вычислить А¡=Н(М$ для 1< /' < I, где 1=\Ц. Подпись считается истинной, если выполняется равенство е(а, & е(Иь рк„ ¿>.

Вкратце, суть мулътилинейных объединенных подписей следующая. Каждый участник и, секретный ключ х, е 2'ч и открытый ключ рк,=

Подпись пользователя U¡ есть сг,=И'', где А, - хеш-функция от сообщения М1, выбранного пользователем. Объединенная подпись а = А*' . Используя свойства муль-

тилинейного отображения, левосторонней проверкой объединенной подписи является следующая процедура (представлено в развернутом виде):

Ф. & В.-. еЩЛ*' ¿=Ц Ф- е(Ь & ш

=Г1 Фь ркь &

Безопасность схемы мультилинейной объединенной подписи.

Следующее утверждение свидетельствует о безопасности схемы мультилинейной объединенной подписи.

Утверждение 3.4 Пусть дано мультилинейное отображение е: в" ->С?2 и для группы в! не существует алгоритма решающего вычислительную проблему Диффи-Хеллмана за время Г с вероятностью не менее е\ Тогда схема мультилинейной объединенной подписи (^Чн.Ч5.Не)-безопасна против существенной подделки в условиях модели с выбранным ключом для всех I и е, удовлетворяющих условиям:

е>е(я3+Ы)е' и 1< 1'-СС| ( я^2<15+Ы+4) -(N+1),

где е-основание натурального логарифма, а экспоненциирование и инверсия в в; требуют времени СС|.

В параграфе 3.2 описана аутентифицированная версия протокола с использованием мультиподписи. Данная версия нашего протокола использует мультиподписи представителей наборов пользователей под общими ключами, которые они вырабатывают. Процедура построения ключевого дерева и вычисления общего ключа остается такой же, как в неау-тентифицированной версии протокола. Элементы аутентификации с использованием мультиподписи добавляются лишь в подпротоколы выработки общего ключа для (к+1) сторон и ш сторон (ш< к+1).

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

тилинейной КриптоСистемы на Основе Идентификационных Данных (МКСОИД). Приведено описание построения и функционирования МКСОИД.

МКСОИД отличается от КСОИД Боне-Франклина использованием:

- мультипликативной группы (общий случай) вместо аддитивной; мультилинейного отображения вместо билинейного спаривания; генератора группы g на добавляемых координатах мультилинейного отображения.

Проведено обобщение протокола Ченга-Лиу-Кима (использующего билинейные спаривания на эллиптических кривых) на случай мультилинейных КСОИД.

Пусть [/={1?!, ...,£/*+- группа из (к+1) участника, которая собирается выработать общий ключ конференцсвязи. Идентификаторы 17/,..., 1/к+1 обозначим через Ш;, соответственно. В соответствии с инфраструктурой мультилинейной КСОИД открытыми ключами участников будут £?/=#/ (Ю/),..., (2к+/= Н1 (Ю а секретными - Я5/= Q', ...,

Пары (04 5() (где /=1,...,к+1) служат долговременными ключами (открытыми и секретными соответственно) участников.

Протокол выработки общего ключа:

1. Каждый участник и, (/=/, ...,к+1) случайным образом вырабатывает кратковременный секретный ключ д(е 2\ .

2. Каждый С/, (1=1, ...,к+1) широковещательно рассылает остальным участникам конференцсвязи : gl= Т,=

3. Каждый £// (/=/,....к+1) проверяет

<РцГК >

11 11 11

Вычисляет К,=е&,..., £«,£/+/.еО

Общим ключом криптоконференции является К]= /Сг=... = K^-ц=!e(g,...,g)°,

Утверждение 3.5. В схеме мультилинейного варианта протокола Ченга-Лиу-Кима для вычисления произведения ]П[е (д,, g¡, g, требуется вычислить лишь два мультилиней-

ных отображения.

В аутентифицированной версии протокола МГКССД для мультилинейных КСОИД процедура построения ключевого дерева и вычисления общего ключа остается такой же, как в неаутентифицированной версии протокола. Для аутентификации в процедурах выработки общего ключа для m сторон

и (к+1) сторон используется мультилинейный вариант протокола Ченга-Лиу-Кима.

Показано, что аутентифицированная версия протокола МГКССД^ для случая мульти-линейной КСОИД, удовлетворяет следующим основным свойствам

безопасного протокола ключевого соглашения (против активного противника):

- неявная ключевая аутентификация;

- безопасность при скомпрометированном сеансовом ключе; ^

- (совершенная) безопасность «будущего»;

- отсутствие деперсонализации ключевой компрометации;

- отсутствие ключевого контроля.

В параграфе 3.5 описана доказуемо безопасная схема ключевого соглашения со структурой дерева на основе k-мультилинейных отображений. Данная версия протокола (МГКССДлг) использует объединенные подписи всех участников набора пользователей под их краткосрочными открытыми ключами.

Общая структура данного протокола совпадает со структурой неаутентифицированной версии протокола UP. Добавления и изменения касаются процедур Key и КеуТ, а также форматов сообщений.

Производятся следующие изменения.

Пусть П'ц - 1-ое выполнение протокола пользователем U. j-oe сообщение М, отравляемое для случая П'и имеет вид

С/1/|А/]Ш1[/|МНП[/, где НП^ обозначает набор пользователей с представителем U, который отправляет сообщение М в качестве своего /-го сообщения, а МНПц обозначает множество наборов пользователей, которым [/отправляет свое j-oe сообщения М.

Участники группы выполняют неаутентифицированную версию протокола со следующими добавлениями:

- Предположим, что в случае П'ц сообщение U\j\ М\ НПу |МНПс/ (где U- это представитель набора пользователей НПу для случая П'и) посылается как часть протокола неаутен-

тифицированного ключевого соглашения. В аутентифицированной версии это действие заменяется следующими операции:

- каждый пользователь U/ НПу вычисляет a^-SiSK^, l\j\ M \ги)\

- каждый пользователь Ui* Uв НПу посылает Щ <ти\ ги\ {Ui}\fU}\f\ M, где Л/есть j-ot сообщение пользователя U;

- пользователь U (представитель) вычисляет объединенную подпись

a=AS ({РК[/„ /1/| Щг^щ : С/еНП^}) и посылает

и\}\М\а\Ш1и |МНПи|/' : ¡У/еНПу}. Подпись от пользователей Ui* U не проверяется пользователем U. Если такая подпись неверна, это выяснится во время проверки объединенной подписи. Заметим, что сообщение, подписанное пользователем £//еНПу, есть l\j\M\rUr Следовательно, для h*h, сообщения, подписанные £7/, и 17/, - различны.

Когда П'у (VeМНПу) получает сообщение Щ\Ща\Ш1и [МНГУ{ги;. £/,бНПс/}, он проверяет:

- С/е pid'v ;

- j есть следующий по порядку ожидаемый номер (в неаутентифицированной версии протокола) для сообщения от U;

-^({РК^: и,еШ1и}, {/ \]\Щги, : и,еШи},оГ\.

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

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

Теорема 3.6. Протокол МГКССД« с использованием объединенной подписи является протоколом группового ключевого соглашения безопасным против активного противника. При этом справедливы следующие неравенства:

с2

Усж.с^(иСвДо) < Успех%{t,+t2, KB+Ko/2)+ I9\+\9\Успехш^,}±\Р\ Успех^Ь)

где ti+t2< t+(| 9 | Кв+ Ко) tAP, tAf - время необходимое для выполнения протокола АР произвольным пользователем, Кв, Ко - количество запросов к оракулам «Выполнить» и «Отправить» соответственно.

Глава 4 Обсуждение эффективности протокола МГКССД

В параграфе 4.1 оценивается эффективность различных версий протокола МГКССД. Рассматривается связная и вычислительная эффективность. Общее количество раундов, общее количество пересылаемых групповых элементов, общий обмен сообщениями определяют связную эффективность; в то время как общее количество вычисляемых к-мультилинейных отображений и экспоненциирований определяет вычислительную эффективность.

Пусть R(m) обозначает общее количество раундов. М(т) - общее количество вычисляемых k-мультилинейных отображений; В(т) - суммарный объем, передаваемой по каналам связи, информации; Е(т) - общее количество экспоненциирований в группе ¿7/. Если пользователь открыто посылает элемент G; всем или некоторым пользователям, то это засчитывается как единица информации в суммарном объеме В(т). Таким образом, В(т) - общее количество таких групповых элементов.

Утверждение 4.1 Для т>к справедливы следующие соотношения и границы для R(m), В(т), Е(т), Р(т):

1. Ä(mj=[l<>g,w ml»

Ä—1

2. В(т^ ^(т); вР(т)= (к+1)ы для i=l, ...,R-1;

1-0

Bf»(mh

Для ключевого дерева высотыR(m)=\logt+1 т\

k+^fi <В(т)< £ßm к к

3. Е(т)=В(т); < Е(т)< ^^-т

16

(к+1),

4. М(т)=% Мр>(т)=т для ¡=1.....Я-1;

1-0

М"»(тУ=Мп(к+1)+Мс, от-(* + !/-'

где Мп =

к

М(т) <т\\о%мт\.

, Мс=т-кМп-(к+1)К-'.

Пусть Яа1(т), Ва](т), Е„1(т) и Ра1(т) обозначения аналогичные неаутентифицирова-ной версии, используемые для случая МКСОИД.

Утверждение 4.2 Для т>к справедливы следующие соотношения и границы для Яа1(т), Ва,(т), Еа,(т)иМа,(т):

1. т].

2. Ва,(т) = 2В(т). Следовательно

Для ключевого дерева высоты Я(т)=\\о%м т\

3. Количество различных экспоненциирований Е'а,(т)=4Е(т) т

Для количества экспоненциирований с учетом повторяемых вычислений различными пользователями справедливо следующее: Еа,(т)< т(к\\о%м т\+4+1/к)+сот¡(к).

При т»к асимптотической границей сверху для Еа,(т) является km(log¡l¥¡m).

4. Ма,(т) = § Ма®(т);

1-0

Ма,с,)(т)=5М°>(т)=5т для ¡=1,...,Я-1; Ма;°>(ту= Ма,„т (к+1)+ Ма,с<°>; Ма,(т) < 5 т\\о%м т~\+соги1; Сою(= Ма1пГ0>(к+1)+Ма1С(0>-5т . При т»к асимптотической границей сверху для М„,(т) является 5m(log|l+¡m).

При анализе эффективности протокола МГКССДдг ограничимся подсчетом количества специальных подписей, так как конкретное число экспоненциирований, мультилиней-ных отображений и других операций определяется конкретной схемой реализации объединенной подписи.

Утверждение 4.3 Для доказуемо безопасной аутентифщированной версии (случай использования объединенной подписи) справедливо следующее :

1. Количество раундов в протоколе равно: Яа] (т) = 2Щт)-\= 2ро8м 1н"|-1.

2. В данном протоколе дополнительно (по сравнению с неаутентифицированной версией) передаются п[Щт)-1] подписей под соответствующими сообщениями, содержащими

(к + Г)я — 1

общий открытый ключ НП. Из них [-----1] являются мультилинейными объединен-

к

(к +1)" -1

ными подписями, остальные [тЩт) - ----] являются индивидуальными подписями.

к

В параграфе 4.2 производится сравнение версий протокола МГКССД с известными протоколами выработки общего секретного ключа группы участников по открытым каналам связи.

Таблица 1: Сравнение протоколов (неаутентифицированные версии)

Я(п) В(п) Е(п) М(п),Р(п) 1пу

ВО 2 2п п(п+1) - п

оон-з п+1 3(п-1) 5п-6 - -

тсон Г1°ё2 "1 ПГ10Й2 "1 пП08г "1 - -

вое П°ёз"1 <5/2(п-1) <5/2(п-1) <п[к^3 п\ -

МГКССД к <<* + 1>п

Замечания по поводу неаутентифицированных протоколов:

Связная (коммуникационная) сложность измеряется посредством Щп) и В(п), и протокол МГКССД достигает минимума для обеих функций среди всех известных протоколов, кроме ЕЮ протокола. Вычислительная сложность протокола МГКССД состоит из двух частей - экспоненцирования и к-мультилинейного отображения. Количество экспоненции-рований меньше, чем в других протоколах, но требуется дополнительно п и"] к-мультилинейных отображений. В значительной степени вычислительная сложность МГКССД определяется сложностью вычисления к-мультшшнейных отображений.

Для частного случая к=2 протокол МГКССД дает сокращение до 40 % от суммарного объема передаваемой по каналам связи информации и проводимых экспо-ненциирований по сравнению с единственным протоколом конференцсвязи, использующим билинейные спаривания (протокол Баруа-Дутга-Саркара - «ВББ»).

Таблица 2. Сравнение аутентифицированных версий протоколов

Щп) В(п) Е(п) М(п),Р(п) 1ПУ Ми1

ЗА-ОБШ п И4 п' - п 2пг-2п

Ю-АОКА Г1о82 "1 п\ пГ1оё2 "1 2п[1о§2 «1 - -

ВБвл Г1о8з "1 <5(п-1) <9(п-1) <5п[1о§3 л~|+3 - -

МГКССДм П°8м "1 <2п(* + 1> к к ~ 5пГ1ое^1 "1

Замечания по поводу аутентифицированных протоколов:

Количество раундов и суммарный объем сообщений в нашем протоколе меньше с сравнении с другими протоколами. Количество экспоненциирований (и скалярных умножений на эллиптических кривых для соответствующих протоколов) в МГКССДд! также меньше, чем в других протоколах. При этом требуется вычисление = 5п п \ к-мультилинейных отображений, что для больших п существенно меньше количества спариваний необходимых для протоколов ГО-АОКА и ВБЗА.

В отношении вычислительной сложности доказуемо безопасных версий протоколов: ВО требует от каждого участника выполнения О(п\о&%) модульных умножений

и проверки 0(п) подписей, ЕШЭд требует от каждого участника вычисления "1 подписей, МГКССДлг требует от каждого участника вычисления т1 подписей.

Таблица 3. Сравнение протоколов по связной сложности для доказуемо безопасных в стандартной модели версий (СТ-стандартая передача, ШВ-широковещательная передача)

Щп) Объем в сообщениях (на пользователя) Объем в битах (на пользователя)

СТ ШВ СТ ШВ

ви 3 0(п) 3 0(п) 0(1)

ВОБд 0(п /о&п) О (Ь?3п) 0(п 1о§.¿1) 0(1о8зп)

МГКССДдг 0{п /о£*+/п) 0{logk+,тi) 0(п /ОЙ*+/П)

Как видим, протокол МГКССД и для доказуемо безопасных версий выглядит весьма конкурентоспособно, потенциально имея минимальную вычислительную сложность среди рассматриваемой группы протоколов. Окончательная эффективность протокола МГКССДа2, как и других версий, определяется сложностью вычисления к-мультилинейных отображений.

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

РЕЗУЛЬТАТЫ

1. Разработан алгоритм базового неаутентифицированного протокола группового соглашения со структурой дерева (МГКССД), реализующий преимущества использования к-

мультилинейных отображений. Доказана безопасность данного протокола по отношению к атакам пассивного противника при условии сложности £>ЯМОЯ-проблемы в используемой структуре.

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

- схема мультиподписи;

- схема объединенной подписи;

- криптосистемы на основе идентификационных данных (КСОИД);

- обобщение протокола Ченга-Лиу-Кима;

3.Разработана аутентифицированная версия протокола МГКССД с использованием мультилинейной объединенной подписи. Доказана безопасность данного протокола в условиях стандартной модели безопасности.

4. Разработана аутентифицированная версия протокола МГКССД в условиях мультилинейной КСОИД. Показано, что данная версия протокола удовлетворяет всем основным свойствам безопасного протокола группового ключевого соглашения.

Основное содержание диссертации изложено в следующих работах:

1. Гончаров С.М., Скуратов В.А. Статья по спецгеме, секретно, НТС № 20 ГРУ ГШ, Москва, 1984.- С.138-152.

2. Гончаров С.М., Скуратов В.А. Статья по спецтеме, секретно, НТС № 20 ГРУ ГШ, Москва, 1984. С.153-161.

3. Гончаров С.М., Корнюшин П.Н. Методы работы с паролями шифра РКгГР // Материалы ХЬУ Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2002.-Т.2.-С.58-60.

4. Гончаров С.М., Корнюшин П.Н. О перспективах криптосистемы «ЫПШ» // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1,- С.55-57.

5. Гончаров С.М., Корнюшин П.Н. О методах асимметричного шифрования, перспективных для малоресурсной криптографии // Материалы ХЬУ1 Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1,- С.51-54.

6. Гончаров С.М., Корнюшин П.Н. О преимуществах криптосистемы «XTR» // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.- С.61-62.

7. Гончаров С.М., Корнюшин П.Н. Алгоритмы решения проблемы дискретного логарифмирования на эллиптической кривой // Материалы XLVI Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2003.-Т.1.- С.55-57.

8. А.П. Гончаров, С.М. Гончаров. Стойкость цифровой подписи «NTRUSIGN»// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докла-дов.-Владивосток, 2003,- С.58-59.

9. А.В. Надеин, С.М. Гончаров. Цифровая подпись «NTRUSIGN»// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2003,- С.60.

10. А.М. Стаценко, С.М. Гончаров. Направления развития асимметричной криптографии// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2003.- С.61.

И. М.С. Гончаров, С.М. Гончаров. Криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2003.- С.62.

12. М.С. Гончаров, С.М. Гончаров. Мультилинейные криптосистемы на основе идентификационных данных// Региональная конференция студентов, аспирантов и молодых ученых по физике. Тезисы докладов. Владивосток, 2004.- С. 109.

13. Гончаров С.М., Корнюшин П.Н. Совместная выработка ключа криптоконференции на основе k-мультилинейных отображений // Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1,- С.43-45.

14. Гончаров С.М., Корнюшин П.Н. Динамическое изменение состава группы для протокола МГКССД // Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1,- С.46-47.

15. Гончаров С.М., Корнюшин П.Н. Доказуемо безопасный протокол мультилинейного группового ключевого соглашения со структурой дерева// Материалы XLVII Всероссийской межвузовской научно-технической конференции. Владивосток, ТОВМИ, 2004.-Т.1.-С.48-49.

Гончаров Сергей Михайлович

ПОСТРОЕНИЕ ПРОТОКОЛОВ КЛЮЧЕВОГО СОГЛАШЕНИЯ КРИПТОКОНФЕРЕНЦИИ НА ОСНОВЕ к-МУЛЬТИЛИНЕЙНЫХ ОТОБРАЖЕНИЙ

АВТОРЕФЕРАТ

Подписано к печати 10.11.2005 Формат 60x84 1/16 Усл. печ. л. 1,39 Уч.-изд. л. 1,16

Тираж 100 экз.

Издательство Дальневосточного университета 690950, г. Владивосток, ул. Октябрьская, 27

Отпечатано на множительной технике ДВРУНЦ ДВГУ 690950, г. Владивосток, ул. Суханова, 8

Ш22407.

РНБ Русский фонд

2006-4 22647