Протоколы аутентификации информации на основе вычислений в конечных некоммутативных группах векторов тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат технических наук Захаров, Дмитрий Викторович

• Захаров, Дмитрий Викторович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Захаров, Дмитрий Викторович

Оглавление

Оглавление

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение диссертации (часть автореферата) на тему «Протоколы аутентификации информации на основе вычислений в конечных некоммутативных группах векторов»

Введение

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

В качестве технологии аутентификации электронных сообщений применяется электронная цифровая подпись (ЭЦП). В настоящее время существует большое количество различных протоколов и алгоритмов ЭЦП [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 наименований.

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

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

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

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

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

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

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Захаров, Дмитрий Викторович

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

1) Доказано утверждение об условиях, которым удовлетворяет вектор порядка р (р — характеристика поля, над которым задано шестимерное векторное пространство).

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Петербург, 28-30 октября. СПб.: СПОИСУ, 2009. С.103

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

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

Список литературы диссертационного исследования кандидат технических наук Захаров, Дмитрий Викторович, 2013 год

Литература

1. Венбо Мао. Современная криптография. Теория и практика. - М., СПб, Киев. Издательский дом «Вильяме», 2005. - 763 с.

2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке СИ. - М.: ТРИУМФ, 2002. - 816 с.

3. Болотов A.A., Гашков С.Б., Фролов А.Б. Элементарное введение в эллиптическую криптографию. Протоколы криптографии на эллиптических кривых. М., КомКнига, 2006.- 274 с.

4. Алферов А.П., Зубов А.Ю., Кузьмин A.C., Черемушкин A.B. Основы криптографии. - М.: Гелиос АРВ, 2002. - 480 с.

5. Menezes A.J., Van Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1997. - 780 c.

6. Черемушкин А. В. Лекции по арифметическим алгоритмам в криптографии - М.: МЦНМО, 2002 - 104 с.

7. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии - М.: МЦНМО, 2003 - 326 с.

8. Молдовян H.A. Практикум по криптосистемам с открытым ключом. -СПб.: БХВ-Петербург, 2005. - 286 с.

9. Молдовян H.A. Теоретический минимум и алгоритмы цифровой подписи. - СПб.: БХВ-Петербург, 2010. - 290 с.

10.Moldovyan N.A. Digital Signature Scheme Based on a New Hard Problem // Computer Science Journal of Moldova. 2008, Vol. 16, No.2(47), pp. 163182.

11.Молдовян A.A., Молдовян H.A. Коллективная ЭЦП - специальный криптографический протокол на основе новой трудной задачи // Вопросы защиты информации. 2008. № 1. С. 14-18.

12.Ко К. Н., Lee S. J., Cheon J. H., Han J. W., Kang J. S., Park С. New Public-

Key Cryptosystems Using Braid Groups // Advances in Cryptology — Crypto 2000 / Lecture Notes in Computer Science. Springer-Verlag, 2000. Vol. 1880. P. 166—183.

1 З.Баженов А. А., Костина А. А., Молдовян H. А., Молдовяну П. A. Реализация схем цифровой подписи на основе сложности извлечения корней в группах известного порядка // Вопросы защиты информации. 2009. № 1(84). С. 12—18.

14.Молдовяну П.А., Дернова Е.С., Молдовян Д.Н. Синтез конечных расширенных полей для криптографических приложений // Вопросы защиты информации // Вопросы защиты информации. 2008. № 3(82). С. 2-7.

15.Moldovyan N.A., Moldovyanu Р.А. New primitives for digital signature algorithms // Quasigroups and related systems. 2009. Vol. 17. P. 271-282.

16.Moldovyan N.A. Fast Signatures Based on Non-Cyclic Finite Groups // Quasigroups and related systems. 2010. Vol. 18. P. 83-94.

17. Доронин С. E., Молдовян Н. А., Синев В. Е. Конечные расширенные поля для алгоритмов электронной цифровой подписи // Информационно-управляющие системы. 2009. № 1. С. 33—40.

18.Moldovyan N.A. Acceleration of the Elliptic Cryptography with Vector Finite Fields // Int. Journal of Network Security. 2009. V.9, No 2. PP. 180185.

19. Дернова E.C., Костина А.А., Молдовян H.A., Молдовяну П. A. Направления применения конечных векторных пространств в криптографии // Вопросы радиоэлектроники, сер. ОТ, 2009, вып. 2. С. 165-174.

20.Молдовян Н.А. Аутентификация информации в АСУ на основе конечных групп с многомерной цикличностью // Автоматика и телемеханика. 2009. № 8. С. 177-190.

21.Курош А.Г. Курс высшей алгебры. - М.: Наука, 1971. - 431с.

22.Молдовян Н.А. Вычисление корней по простому модулю как криптографический примитив // Вестник СПбГУ. Серия 10. 2008, вып. 1, с. 101-106.

23.Каргалов М.И., Мерзляков Ю.И. Основы тоерии групп. - М.: Физматлит, 1996. - 287с.

24.Hellman М.Е., Pohlig S.C. Exponentiation Cryptographic Apparatus and Method // U.S. Patent # 4, 424,414, 3 Jan. 1984.

25.Moldovyan N.A., Moldovyanu P.A. New Primitives for Digital Signature Algorithms: Vector Finite Field, QRS. 2009. V. 17. P. 271-282 c.

26.Молдовян Н.А. Молдовян A.A. Введение в криптосистемы с открытым ключом.- С-Петербург, Петербург-БХВ, 2005.- 288 е.; см. с. 190-196

27.Tobias С.; Security analysis of the MOR cryptosystem, in Proceedings of PKC 2003, Lecture Notes in Comput. Sci., 2567, Springer-Verlag, 2003, pp. 175-186.

28.Молдовян Н.А. Алгоритмы аутентификации информации в АСУ на основе структур в конечных векторных пространствах // АиТ. 2008. №12. С. 163-177.

29.ElGamal Т. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. - 1985. -V. IT 31. - N. 4. - P. 469^172.

30.Moldovyan D.N. Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes, QRS. 2010. V. 18. P. 11-24.

31.Молдовян H. А., Молдовян А. А., Еремеев M. А. Криптография: от примитивов к синтезу алгоритмов. - Спб.: БХВ - Петербург, 2004. - 446 с.

32. Дернова Е.С. Построение алгоритмов электронной цифровой подписи на основе групп матриц малой размерности // Известия СПбГЭТУ «ЛЭТИ». 2009. №4. С. 16-20.

33. V. Miller. Use of elliptic curves in cryptography // Advances in cryptology: Proceedings of Crypto'85. Lecture Notes in Computer Sciences. Berlin. Springer-Verlag. 1986. Vol. 218. PP. 417-426.

34. Koblitz N. A. Elliptic curve cryptosystems // Mathematics of Computation Advances. 1987. Vol. 48. PP. 203-209.

35. Koblitz N. A. Course in Number Theory and Cryptography. —Berlin, Heidelberg, New York: Springer, 1994. —235 p.

36. Болотов А. А., Гашков С. Б., Фролов А. Б.,Часовских А. А. Элементарное введение в эллиптическую криптографию. Алгебраические и алгоритмические основы. —М., КомКнига, 2006. — 324 с.

37. Б .Я. Рябко, А.Н. Фионов. Криптографические методы защиты информации. М., Горячая линия - Телеком, 2005.-229 с.

38. Л.Б.Шнеперман. Курс алгебры и теории чисел в задачах и упражнениях.- Минск, «Вышэйшая школа», 1986.- 272 с.

39. Дернова Е.С., Костина А.А., Молдовяну П.А. Конечные группы матриц как примитив алгоритмов цифровой подписи // Вопросы защиты информации. 2008. № 3(82). С. 8-12.

40. Бухштаб А.А. Теория чисел. - М. Просвещение, 1966. -384с.

41. Курош А.Г. Курс высшей алгебры,- М., «Наука», 1971.-431 с.

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

43.Доронин С.Е., Молдовяну П.А., Синев В.Е. Векторные конечные поля: задание умножения векторов большой четной размерности // Вопросы защиты информации. 2008. № 4(83). С.2-7.

44.Moldovyanu Р.А., Moldovyan N.A.Vector Form of the Finite Fields GF(pAm) // Bulletinul Academiei de Stiinte a Republicii Moldova. Matematica. 2009. No 3 (61). P. 1-7.

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

46.Молдовяну П. А., Молдовян Д. Н., Дернова Е. С. Гомоморфизм и многомерная цикличность конечных групп векторов в синтезе алгоритмов ЭЦП // Вопросы защиты информации. 2009. № 3. С. 2-8.

47.Moldovyan N.A., Moldovyan А.А. Vector Finite Groups as Primitives for Fast Digital Signature Algorithms // 4th Int. Workshop IF&GIS'09 Proc. St.Petersburg, May 17-20, 2009. St. Petersburg, Russia / Springer-Verlag LNGC. 2009. PP. 301-315.

48.Молдовян A.A., Молдовян H.A. Новые алгоритмы и протоколы для аутентификации информации в АСУ // Автоматика и телемеханика. 2008. № 7. С.157-169.

49.Молдовян Н.А. Вычисление корней по простому модулю как криптографический примитив // Вестник СПбГУ. Серия 10. 2008, вып. 1, с. 101-106.

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

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

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

53.Молдовян Д.Н., Молдовяну П.А., Щербаков В.А. Синтез таблиц умножения базисных векторов для задания некоммутативных групп векторов // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 10-11 декабря 2009, г. Санкт-Петербург. СПб.: ВАС, 2009. С. 355-360.