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

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

ЗАХАРОВ ДМИТРИЙ ВИКТОРОВИЧ

ПРОТОКОЛЫ АУТЕНТИФИКАЦИИ ИНФОРМАЦИИ НА ОСНОВЕ ВЫЧИСЛЕНИЙ В КОНЕЧНЫХ НЕКОММУТАТИВНЫХ ГРУППАХ

ВЕКТОРОВ

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

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

1 я МАЙ 2013

005058635

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

005058635

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

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

Молдовян Николай Андреевич

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

начальник кафедры «Системы сбора и обработки информации» Военно-Космической Академии им. А.Ф.Можайского Еремеев Михаил Алексеевич

кандидат технических наук, старший научный сотрудник, Санкт-Петербургский институт информатики и автоматизации РАН Новикова Евгения Сергеевна

Ведущая организация: Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «СанктгПетербургский национальный исследовательский университет информационных технологий, механики и оптики» (СПбНИУ ИТМО)

Защита диссертации состоится «16» мая 2013 г. в 15.00 часов на заседании диссертационного совета Д 218.008.06 на базе Петербургского государственного университета путей сообщения по адресу: 190031, Санкт-Петербург, Московский пр., д. 9. (ауд. 1-217).

С диссертацией можно ознакомиться в библиотеке Петербургского государственного университета путей сообщения. Автореферат разослан «16» апреля 2013 г.

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

диссертационного совета Д 218.008.06 кандидат технических наук,

профессор //¿уа-/ я Кудряшов Владимир Александрович

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

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

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

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

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

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

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

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

• Изучение известных подходов к синтезу протоколов и алгоритмов аутентификации информации на основе вычислений в конечных группах векторов;

• Разработка протоколов аутентификации информации на основе вычислений в конечных некоммутативных группах векторов;

• Разработка протокола слепой ЭЦП с использованием вычислений в конечных группах векторов с многомерной цикличностью;

• Разработка алгоритмов генерации четырехмерных и шестимерных векторов заданного порядка р.

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

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

На защиту выносятся:

• Протокол открытого распределения ключей на основе вычислений в конечных группах четырехмерных векторов;

• Алгоритм открытого шифрования на основе конечных групп векторов;

• Протокол слепой электронной цифровой подписи на основе конечных групп векторов;

• Алгоритмы вычисления четырех- и шестимерных векторов заданного порядка.

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

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

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

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

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

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

Практическая реализация и внедрение результатов работы.

Результаты диссертационного исследования использованы при выполнении научно-исследовательских работ на тему «Новый подход к построению схем электронной цифровой подписи, стойких к квантовым атакам» по гранту РФФИ № 11-07-00004-а и научно-исследовательских работ по гранту Санкт-Петербурга для студентов, аспирантов молодых ученых и кандидатов наук Правительства Санкт-Петербурга, 2011г. Результаты диссертационного исследования внедрены на кафедре комплексного обеспечения информационной безопасности Санкт-Петербургского государственного университета водных коммуникаций в учебный процесс по специальности «Комплексное обеспечение информационной безопасности автоматизированных систем» по дисциплинам «Теоретические основы криптографии» и «Криптографические методы защиты информации».

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались на следующих конференциях:

1) Инновационная деятельность в Вооруженных силах Российской Федерации, Санкт-Петербург, 10-11 декабря 2009 г.

2) «Информационная безопасность регионов России (ИБРР-2009)». Санкт-Петербург, 28-30 октября.

3) Водный транспорт России: инновационный путь развития: международная научно практическая конференция. 6-7 октября 2010.

Публикации. По теме диссертации опубликованы 8 научных работ, 3 из которых опубликованы в журналах из списка ВАК, 5 работ в сборниках трудов научно-технических конференций.

Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Диссертационная работа изложена на 118 страницах, работа содержит 18 таблиц, 27 рисунков и список литературы из 53 наименований.

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

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

Конечное множество m - мерных векторов задается следующим образом:

ае + ЪЛ+ ... + с\, где е, i, ... j — базисные векторы, которые можно представить также и в виде набора координат (а,Ь,...,с), являющихся элементами конечного поля GF(p), где р - простое число. Так как рассматриваемая алгебраическая структура должна обладать свойствами кольца и группы, необходимо определить на этом множестве две операции — сложение векторов и умножение векторов. Сложение векторов определяется как сложение одноименных координат по формуле:

(а,Ь,... ,с) + (х у, ,..¿) = {a + x,b+y,...,c + z). Операция умножения векторов определяется по правилам умножения многочленов, с учетом того, что умножение двух базисных векторов выполняется по некоторым правилам: каждая пара умножаемых базисных векторов заменяется на третий базисный вектор (который может совпадать с одним из перемножаемых базисных векторов) или базисный вектор, умноженный на некоторый коэффициент. Таким образом, в равенстве

(а-е + ЬЛ + ... + c-j)(x-e +уЛ + ... +z-j) = oxee + ay-ei + ... + azej + bx-ie + byn + ... + bz\\ + ... + ex-je + cy-ji + ... + cz-jj, каждое из произведений ее, ei, ej, ie, ii, ...ij, ...je, ji, ...jj следует заменить на значение sv, где е — некоторый коэффициент, являющийся элементом поля GF(p), v - некоторый базисный вектор, принадлежащий множеству базисных векторов, в соответствии с таблицей умножения базисных векторов (ТУБВ).

Рассматриваются варианты атак на криптосистемы над конечными некоммутативными группами. Показано, что в ряде случаев задача

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

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

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

У = С*1 ,

где си((7/) = ¿7 и Сь Ст - базис, позволяющий выразить любой элемент порядка <7 группы векторов, обладающей ш-мерной цикличностью. Секретным ключом является набор целых чисел хи хъ..., хт, каждое из которых не превышает значение q - 1. Вычисление секретного ключа по открытому связано с решением задачи дискретного логарифмирования по многомерному основанию 0\,02,...0т. При этом вычисление всех элементов секретного ключа должно осуществляться одновременно, т.е. вычислить секретный ключ по частям нельзя. Приводится сравнительная оценка быстродействия различных алгоритмов ЭЦП.

Таблица 1 - Производительность алгоритмов ЭЦП, основанных на сложности задачи дискретного логарифмирования

Алгоритм Группа Г Размер ЭЦП Размер открытого ключа Производительность, отн. Ед.

ГОСТ 34.10-1994 Ге 512 1024 1

Схема Шнорра Ге СДр) 320 1024 2

Б8А Ге ОДр) 320 1024 2

ЕСББА ЭК 320 320 5

На основе групп векторов Ге 01-(р") 320 200 >20

В случае четырехмерных векторов для построения протокола слепой подписи могут быть использованы два вектора Gi и G2 порядка q, размер которого составляет от 80 до 128 бит.

Открытым ключом пользователя А является пара векторов = G*>G2x2; У2 ~ Gi*3G2*4 , где хх , х2, х^, х4 - ¿-битовые секретные ключи (6=64-100 бит). Генерация ЭЦП осуществляется следующим образом:

1. Подписывающий (пользователь А) выбирает два случайных 80-битовых числа t] и t2, затем вычисляется вектор R = G,'1 ° G2, который отправляется пользователю В.

2. На стороне пользователя В вычисляется значение

R'= O'i || г'2) = R ° Gj"4' о G~22 ° Tj-7' ° Y^2 (ei ti и е2 т2 - случайные числа, не превосходящие простое число q). Затем, с помощью некоторой специфицированной 160-битовой хэш-функции FH, вычисляется значение

e'=e\\\e'2 = FH{M\\r\\\r<2), и значения

в) = e'i+Г] modр ие2 - s'2+T2 гпо<^ Р

3. На стороне подписывающего (пользователь А) вычисляются значения ,s'i и s2 по следующим формулам

si =ij — — x^e2 mod p

s2=t2~ x2el ~ xAe2 ni0(J P

4. На стороне пользователя В вычисляется подпись (е', ,s'i', s2'), где

e'l = е\ — Г[ mod/; е2'= е2 -т2 modр

-Ei mod/? Л'2'-.v2 -s2 modр, которая удовлетворяет процедуре проверки подлинности ЭЦП, в которой используются следующие шаги:

1. По открытому ключу ОьУ2) вычислить вектор

R* = (г *! || г *2 ) = Yf1 о Y(2 о о G®'2 .

2. Вычислить значение е* = е *! || е *2 = FH (М || г || г *2).

3. Сравнить е' и е*. Если с '= с *, то подпись верна.

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

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

Базисные векторы Базисные векторы

с 1 к

е уе V* ук

1 VI —ту-1е к

] V) -к 1

к ук Ч -ху"'е

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

Утверждение 1. Векторы вида (Ьл/^Т, Ь, ¿л/—1, й)необратимы для всех значений Ъ е ОР(р) и д. е СР(р).

Доказательство. Выполним следующие вычисления:

ОлРТ.МЛ/^О2 = =

= 2ЬлРТ(ЬлРТ, Ь, й)

Пусть имеет место соотношение

(Ьл/=1, ь, й^Гл, Л)' = (2ЬуГлу-\Ь^1, Ь, й^Л, 4) (1)

Тогда имеем

(Ьл/=Т,Мл/=Т,сгУ+1 = =

То есть формула (1) имеет место для всех натуральный значений г. Это значит, что никакая степень рассматриваемого вектора не равна единичному вектору, т.е. вектор (Ь\РТ, Ъ, ¿л/11!, й) необратим.

Утверждение 1 доказано.

Утверждение 2. Четырехмерные векторы над конечным полем СГ\р) с умножением, заданным по таблице 1, вида (у-1, Ь, с, с!) обладают порядком, равным р, если координаты Ь, с и й удовлетворяют условию

-ей2 + с2 + тс/2 = 0шо(1 р

Доказательство. В соответствии с правилами умножения четырехмерных векторов возведение вектора (у-1, Ь, с, с1) в квадрат дает

вектор (V 2Ь, 2с, 2с1). Действительно, по формуле умножения векторов имеем

(V-1, Ь, с, с1) ° (V-1, Ь,с,с1) = (у'1 - ту"1 б2 - у-'с2 - +

+ (Ь + Ь - йс + сО)\ + (с + тсй + с - тйсЭД + (с1-сЬ + Ьс + фк = = (V-1 - у_1(тг>2 + с2 + таР))е +2 Ы + 2 с) + 2с1к.

С учетом условия (1) получаем (у~\Ь,с, с1)г = (хг\2Ь,2с,2с{). Допустим (V-1, Ь, с, с1)к = (V-1, кЬ, кс, М). (2)

Тогда получаем

(у'1,Ь,с,фк+1 = (у~\Ь,с,с1)ко(у-\ Ъ,с,0) = (у-\кЬ,кс,Щ ° (у'\Ъ,с,с1) = = (V"1, (к+ 1)6, (к+ 1)с, (к+ 1 )£/).

В соответствии с методом математической индукции формула (2) верна при произвольных натуральных к. Утверждение 2 доказано.

Используя данное утверждение можно составить следующий алгоритм генерации векторов порядка р.

1. Генерировать случайные числа бис.

I----£-

2. ВЫЧИСЛИТЬ (¡ = ±<-Ь2-с2 =±(-Ь2-с2) 4 тойр

3. Координаты вектора Л будут равны 1, Ъ, с, (1.

4. Вычислить У=РР

5. Если V = 1 то конец, иначе - шаг 1.

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

У = ,

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

1 .Пользователи А и В обмениваются своими цифровыми сертификатами: УА = Ги'лКХлТ'Н>А и Гв =Т^"МХвТ~Ко .

2. На стороне пользователя А вычисляется общий секретный ключ по формуле гАВ = ТКл У*А т~№л .

3. На стороне пользователя В вычисляется общий секретный ключ по формуле гАВ = Т»«У*»Т-"'в.

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

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

Допустим, существует некоторая функция шифрования Ек, которая управляется секретным ключом К. (К - элемент некоммутативной группы

Г).

1. Отправитель генерирует пару случайных чисел (и,г), затем вычисляются элементы Я = ТиИ2Т~и и К = ТиУгТ " некоммутативной группы Г, где У = Т™ЫХТ~™ - открытый ключ получателя. Элемент Я - разовый открытый ключ, К - разовый общий секрет. Элементы Ли К используются для шифрования только одного сообщения. Для шифрования следующего сообщения необходимо генерировать новые значения /? и К.

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

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

4. На стороне получателя вычисляется значение К =ТМЯХТ~14 = К, где (и-\ х) — личный секретный ключ получателя, затем криптограмма С расшифровывается: М = Ок (С), где Ок — функция дешифрования, обратная к Ек.

Также в главе приведены оценки быстродействия алгоритмов. Показано, что для случая четырехмерных векторов разработанный алгоритм обеспечивает повышение быстродействия в 2,44 раз при использовании однопроцессорного вычислительного устройства, и до 9,76 раз при использовании многопоточных вычислений. В случае шестимерных векторов алгоритм обеспечивает повышение производительности в 2 раза, и до 12 раз при использовании многопоточных вычислений.

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

Таблица 3 - Таблица умножения базисных векторов для случая шестимерного векторного пространства

Базисные векторы Базисные векторы

e i i k u V

e ve vi vj vk vu vv

i vi v~'Ae Au Av i k

i v,|' Av v'Ue Au k i

k vk Au Av v~lAe i i

u vu k i j V v_1e

V vv i k i v"'e u

Шестимерные векторы над конечным полем GF{p) с умножением, заданным по таблице 3 вида (v_1, b, с, d,f,g) обладают порядком, равным р, если координаты b,c,d,fng удовлетворяют условию

• b2+c2+d2 = -2fgmoàp A(bc + bd + cd) = -f2 mod p

Доказательство. В соответствии с правилами умножения векторов возведение вектора (v_1, b, с, d, / g) в квадрат дает вектор (V1, 2Ъ, 2с, 2d, 2/ 2g) Действительно, по формуле умножения векторов имеем =v~ Vve + v~'vi + v'cvj + v~'i/vk + v~'/vu + v~'gvv + + v"'vi + v-1Ae + cAu + dAv +f\ + gk + + cv"'vj + cAv + ccv'1 Ae + cdAu + cjk + cgi + + dv"lv\i + dAu + dcAv + ddv~l Ae + dfi+ dgj + +Jv'\u +Jk+fci + fdj + fj\ + fgv'1 Ae + + gv"'vv + gj + gck + gdi + gfv^Ae + ggu = = (v~Vv+ v_1A +ccv'1 A +ddv~l A +fgv'1A + ф~х A)e+ +(v"'v + v"'v + cg + df+fc + gd)i + (V've +/+ с v"'v + dg +fd + g)j + (v~W + g + cf+d v'lv +/+ gc)k + (v-1v/ +cA +cdA + dA + /v_,v + gg)u + +(v"'vg + Ad + Ac + A de +//' + g v"'v)v

Так как ся +с1/ + /с +&с1 = ^с+О) + /№с) = (с+Ф(8+А bf+dg+fd +ёЪ =АЪ+0) + ё{с1Щ = и Ьё +с/ + А> +8с =Лс+Ь) + ^с+Ь) =

(Ь+с)(я+/), то с учетом условия (3) получаем (V , Ь, с, с/, / £) = =(\Г\ 2Ь, 2с, 2(1, 2/ 2в). Допустим

(V"1, Ь, с, ё)" = (V1, кЬ, кс, Ы, к/, к§). (3)

Тогда получаем

(V-1, ъ, с, 4/, Е)к+1 = (V-1, ъ, с, ° (V"1, Ь, с, а,/, )=

= (V"1, кЪ, кс, Ы, к!, к£) о (V-1, Ь,с,с1,/,ё) = = (у"1, {к + 1 )Ь, 0к + 1 )с, (к + Щ (к+\у, {к+ 1)0.

В соответствии с методом математической индукции формула (3)

Рисунок 1 - Алгоритмы генерации четырехмерных и шестимерных

векторов порядка р

Далее приводится протокол ЭЦП над некоммутативными группами векторов, использующие в качестве параметров векторы специального вида. Формирование открытого ключа в виде трех векторов Е/, У, и У2 группы Г может быть осуществлено следующими двумя альтернативными

вариантами: 1) путем генерации вектора и группы Г и формирования векторов У1 = ЖРУУ'1 и У2 = 1/~11УРх1>У~1и или 2) путем генерации вспомогательного элемента V группы Г и формирования векторов ^ = \VPW~1, У2 = УРхУ~г и и = И>У~Х группы Г. Второй вариант идентичен первому, что явно видно, если из формулы и = У/У~х вычислить V-1 = IVII и V = и~1¥/ и подставить последние два выражения в формулу У2 = УРхУ~г, что дает У2 = и~1[У Рх1У~ги. Последнее показывает, что оба альтернативных варианта формирования открытого ключа дают набор трех элементов группы Г, удовлетворяющих одним и тем же формулам.

Электронная цифровая подпись формируется путем генерации случайного числа / и элемента Я = \¥Р(УУ~1и группы Г, формирования числа е в зависимости от принятого электронного документа и от элемента Я группы Г и формирования числа 5 в зависимости от е и к.

Формирование 5 в зависимости от / и к, которые неизвестны потенциальному нарушителю, обеспечивает вычислительную невозможность вычислить к по известным е и .V. Число е формируется по формуле е = где / - сжимающая функция, аргументами которой

являются число к и элемент Я группы Г; .у формируется по формуле 5 = (г-е^'тос^, где ц — значение порядка элемента Р группы Г. Проверку ЭЦП выполняют путем формирования чисел В = е и А = /(И,Я*), где

Л* = У{ и У^". Подставляя в выражение для Я" значения е, 5, У1 и У2, получим

Я* = У,Ъ'У;е = (И'Р1¥~]у и(и~Н¥Рк1У~]иуе = = ¡УРхИ/->ии~11Г(Рк Г' \У~1и = 1ГР"-кЧ¥~'и = = ТГР^и = Я=>А = /(И, Я*) = /(И, Я) = е = В

Таким образом, доказано, что сформированная по секретному ключу ЭЦП проходит процедуру проверки подлинности ЭЦП.

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

Рисунок 2 - Протокол ЭЦП на основе конечных некоммутативных групп векторов: а) алгоритм генерации ключей; Ь) алгоритм

Рисунок 3- Протокол ЭЦП на основе конечных некоммутативных групп четырехмерных векторов: алгоритм проверки подписи (е, в) к сообщению М.

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

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

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

3. Разработаны протоколы ЭЦП над конечными некоммутативными группами четырехмерных векторов.

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

5. Доказаны утверждения о виде четырехмерных и шестимерных векторов порядка р.

6. Доказано утверждение о виде необратимых 4-мерных векторов.

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

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

Список публикаций по теме работы Публикации в изданиях, рекомендованных ВАК Мпнобрнауки России:

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

2. Молдовян Д.Н., Куприянов А.И., Костина A.A., Захаров Д.В. Задание некоммутативных конечных групп векторов для синтеза алгоритмов цифровой подписи // Вопросы защиты информации. 2009. № 4. С. 12-18.

3. Захаров Д.В., Молдовян H.A. Криптосхемы над задачей скрытого дискретного логарифмирования для защиты информации в инфотелекоммуникационных системах водного транспорта II Журнал Университета водных коммуникаций. 2011. No. 11. С. 89-92.

В других научных изданиях:

4. Заболотный A.A., Захаров Д.В. , Мирин А.Ю., Пилькевич C.B. Протокол с нулевым разглашением на основе сложности вычисления автоморфизма в конечной некоммутативной группе // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции, 10-11 декабря 2009, г. Санкт-Петербург. СПб.: ВАС, 2009. С. 219-222.

5. Захаров Д.В., Куприянов И.А., Синев В.Е., Цехановский В.В. Схемы разделения секрета на основе конечных колец векторов // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции, 10-11 декабря 2009, г. Санкт-Петербург. СПб.: ВАС, 2009. С. 228-233.

6. Захаров Д.В., Хо Нгок Зуй, Молдовян Д.Н., Молдовяну П.А. Способ задания некоммутативных конечных групп векторов четной размерности // Материалы VI Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР-2009)». Санкт-Петербург, 28-30 октября. СПб.: СПОИСУ, 2009. С. 103

7. Цехановский ВВ., Захаров Д.В., Дернова ЕС., Гортинска* Л.В. Протоколы слепой подписи, основанные на двух независимых трудных задачах // Материалы VI Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР-2009)». Санкт-Петербург, 28-30 октября. СПб.: СПОИСУ, 2009. С.126.

8. Захаров Д.В. Протокол слепой подписи на основе конечных некоммутативных групп векторов // Водный транспорт России, инновационный путь развития: международная научно практическая конференция. 6-7 октября 2010. Материалы конференции СПБГУВК -СПБ ФГОУВПО СПБГУВК, 2011.Т..З С. 101-104.

Подписано к печати 09.04.2013 г.

Печать-ризография Бумага для множит, апп. Формат 60x84, 1/1 ь

Тираж 100 экз. Заказ 393. Печ л. - 1.0

Отпечатано в типографии «ПГУПС» (190031, г. Санкт-Петербург, Московский пр., 9)

Федеральное агентство морского и речного транспорта

Федеральное бюджетное образовательное учреждение высшего профессионального

образования

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

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

ПРОТОКОЛЫ АУТЕНТИФИКАЦИИ ИНФОРМАЦИИ НА ОСНОВЕ ВЫЧИСЛЕНИЙ В КОНЕЧНЫХ НЕКОММУТАТИВНЫХ ГРУППАХ

ВЕКТОРОВ

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

04201358832

Захаров Дмитрий Викторович

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

Научный руководитель

доктор технических наук,

профессор Молдовян Н.А.

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

Оглавление

Оглавление...............................................................................................................2

Введение...................................................................................................................4

Глава 1. Криптосистемы с открытым ключом над конечными векторными пространствами.......................................................................................................9

1.1. Задание конечных групп и колец над конечными векторными пространствами.......................................................................................................9

1.2. Протоколы открытого распределения ключей и открытого шифрования над некоммутативными группами.......................................................................20

1.3. Атаки на криптосистемы над конечными некоммутативными группами28

1.4. Постановка задачи..........................................................................................33

Глава 2. Двухключевые криптосхемы над конечными коммутативными группами четырехмерных векторов....................................................................35

2.1. Задание конечных коммутативных групп четырехмерных векторов.......35

2.2. Схемы электронной цифровой подписи......................................................38

2.3. Схема слепой электронной цифровой подписи..........................................46

2.4. Сравнение производительности с группами других типов.....................51

2.5. Выводы ко второй главе................................................................................53

Глава 3. Генерация элементов со специальными свойствами в конечных некоммутативных кольцах четырехмерных векторов......................................54

3.1. Задание конечных некоммутативных колец четырехмерных векторов над расширенными полями.........................................................................................54

3.2 Алгоритм нахождения /»-векторов.................................................................64

3.3. Необратимые четырехмерные векторы.....................................................68

3.4. Протокол открытого распределения ключей..............................................70

3.4. Протокол открытого распределения ключей..............................................70

3.5. Алгоритм открытого шифрования...............................................................72

3.6. Программы, разработанные для проведения вычислительных экспериментов.......................................................................................................75

3.6. Выводы к третьей главе.................................................................................88

Глава 4. Генерация элементов со специальными свойствами в конечных некоммутативных кольцах шестимерных векторов..........................................89

4.1 Алгоритм нахожденияр-векторов.................................................................89

4.2. Программы, разработанные для проведения вычислительных экспериментов.......................................................................................................94

4.3. Схемы ЭЦП над некоммутативными группами векторов.........................98

4.4. Выводы к четвертой главе...........................................................................109

Заключение..........................................................................................................110

Список опубликованных работ по теме диссертационного исследования... 111 Литература...........................................................................................................113

Введение

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

В качестве технологии аутентификации электронных сообщений применяется электронная цифровая подпись (ЭЦП). В настоящее время существует большое количество различных протоколов и алгоритмов ЭЦП [1-9]. В сравнении с другими методами криптографической защиты информации, алгоритмы ЭЦП имеют относительно низкую производительность, так как для обеспечения безопасного уровня стойкости ЭЦП параметры алгоритмов, а также открытые и секретные ключи должны иметь достаточно большой размер[33-38]. Один из способов повышения быстродействия алгоритмов ЭЦП состоит в применении новых вычислительно трудных задач, лежащих в основе алгоритмов ЭЦП [10-12]. Другой способ - использование конечных алгебраических структур с вычислительно эффективными операциями, допускающими многопоточное выполнение[13-18]. Важность для практики задачи повышения быстродействия алгоритмов аутентификации информации обусловливает интерес к разработке новых алгоритмов ЭЦП. В последнее время активно разрабатываются алгоритмы ЭЦП, основанные на вычислениях в нециклических конечных группах[19,20,47,48]. Было разработано несколько протоколов ЭЦП, основанных на вычислениях в конечных группах векторов и матриц малой размерности[32,39,48], однако вопрос о целесообразности применения подобных схем на практике остается открытым ввиду наличия

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

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

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

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

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

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

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

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

2) Разработка протоколов аутентификации информации на основе

вычислений в конечных группах некоммутативных векторов;

3) Разработка протоколов слепой ЭЦП с использованием вычислений в конечных группах векторов с многомерной цикличностью;

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

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

1) Разработаны потенциальные атаки на схемы ЭЦП, основанные на вычисления в конечных группах векторов;

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

3) Разработана сема слепой ЭЦП над конечными группами векторов с многомерной цикличностью;

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

Положения, выносимые на защиту.

1) Протокол открытого распределения ключей на основе конечных групп четырехмерных векторов.

2) Алгоритм открытого шифрования на основе конечных групп векторов.

3) Протокол слепой электронной цифровой подписи.

4) Алгоритмы вычисления четырех- и шестимерных векторов заданного порядка.

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

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1. Криптосистемы с открытым ключом над конечными векторными пространствами

1.1. Задание конечных групп и колец над конечными векторными пространствами

В настоящее время на практике широко применяются алгоритмы ЭЦП, основанные на следующих вычислительно сложных задачах:

1. Факторизация составных чисел вида п = рц, где р ид- два больших простых числа, удовлетворяющих специальным требованиям [1,5];

2. Нахождение дискретного логарифма в конечной группе достаточно большого простого порядка [5, 6].

При этом наиболее разнообразные и практически значимые алгоритмы ЭЦП относятся ко второму типу[28]. Среди различных алгебраических структур, используемых для построения алгоритмов ЭЦП, наибольшую производительность обеспечивают конечные группы точек эллиптической кривой (ЭК). Групповая операция на ЭК - композиция (сложение) точек, для выполнения которой осуществляется одна операция инверсии и несколько операций умножения координат [3]. Операция инверсии вносит основной вклад в ограничение производительности алгоритмов аутентификации информации, построенных с использованием ЭК. В работе [14] в качестве примитивов алгоритмов ЭЦП предложены конечные группы векторов.

Рассмотрим конечное множество т-мерных векторов

ае + Ъл + ... + с

где е, ¡, ... ] - базисные векторы, и а,Ь,...,с - координаты, являющиеся элементами конечного поля где р - простое число. Так как

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

(ia,b,...,c) + (x,y,...,z) = (a + x,b + y,...,c + z).

Операция умножения векторов определяется по правилам умножения многочленов, с учетом того, что умножение двух базисных векторов выполняется по некоторым правилам: каждая пара умножаемых базисных векторов заменяется выражением вида ev, где е - некоторый коэффициент, называемый структурным коэффициентом, или коэффициентом растяжения, являющийся элементом поля GF(p), v - некоторый базисный вектор. Отметим, что этот вектор может совпадать с одним из перемножаемых базисных векторов. Таким образом, в равенстве

(ае + ЬЛ + ... + c-j)(jc-e +_y-i + ... + z-j) = ах-ее + aye i + ... + flz-ej + bx-ie + by-ii + ... + bz-ij + ... + cx-je + cy-ji + ... + cz-jj, каждое из произведений ее, ei, ej, ie, ii, ...ij, ...je, ji, ...jj необходимо заменить на произведение ev, в соответствии с таблицей умножения базисных векторов (ТУБВ). Таблицей умножения базисных векторов определяется тип алгебраической структуры, формируемой в конечном пространстве m-мерных векторов при заданном поле GF(p).

Таблица умножения базисных векторов определяет над их множеством некоторую операцию. Интересен случай образования конечных групп и колец в пространстве m-мерных векторов, поэтому указанные таблицы должны быть составлена таким образом, чтобы операция умножения была ассоциативна. Ниже будет показано, что при определенных соотношениях между размерностью векторов т и порядком поля р в частных случаях задания операции умножения векторов формируются конечные расширенные поля GF(pm)[\l].

Как было сказано выше, повышение производительности алгоритмов ЭЦП является актуальной задачей. В связи с этим необходимо сравнить сложность операции умножения элементов поля GF(p"')(BeKTopoB) со сложностью умножения в простом поле Zp>, где \р'\ = т\р\ и \р\ обозначает количество бит, необходимых для записи числа в двоичной системе

счисления. Операция умножения векторов включает т2 операций умножения в поле СР(р) и т2 операций сложения. Поскольку вычислительная сложность операции умножения в поле СР{р) растет пропорционально квадрату размерности \р\, то сложность выполнении операции умножения в поле GF(^зm), представленном в векторной форме, примерно равна сложности умножения в поле 1Р'. (в данном случае операциями арифметического сложения можно пренебречь, так как их вклад достаточно мал). В криптографических алгоритмах операция умножения выполняется по некоторому модулю, то есть присутствует операция деления (в случае

О и

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

Сра