Метод повышения производительности криптосхем, основанных на конечных некоммутативных группах тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат технических наук Горячев, Александр Андреевич

• Горячев, Александр Андреевич
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Горячев, Александр Андреевич

Содержание

Введение

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

1.1 Понятие криптографического протокола

1.2 Схема открытого распределения ключей

1.3 Электронная цифровая подпись

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

1.5 Примитивы двухключевых алгоритмов и протоколов

1.6 Задача скрытого дискретного логарифмирования в криптосхемах с открытым ключом

1.7 Постановка задачи диссертационного исследования

Глава 2. Строение некоммутативных конечных групп и полей векторов

2.1 Общий способ задания конечных колец векторов

2.2 Конечные некоммутативные группы векторов над кольцом 2р<х

2.3 Конечные некоммутативные группы векторов над полем СТ7^5)

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

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

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

3.2 Синтез методом внесения несимметричного распределения структурных коэффициентов

Выводы к главе 3

Глава 4. Повышение производительности криптосхем над конечными некоммутативными группами векторов

4.1 Общая схема ЭЦП для некоммутативных групп векторов

4.2 Алгоритм ЭЦП для конечных некоммутативных групп векторов размерности 4

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

4.4 Протоколы с нулевым разглашением

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

4.4.2 Использование протокола с нулевым разглашением для синтеза схем ЭЦП

4.5 Скоростной алгоритм коммутативного шифрования с разовым использованием ключей шифрования

4.6 Повышение производительности криптосхем методом распараллеливания операций

Заключение

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

Список терминов

Литература

Введение диссертации (часть автореферата) на тему «Метод повышения производительности криптосхем, основанных на конечных некоммутативных группах»

Введение

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

В последнее время большой интерес представляют криптосхемы, основанные на новой трудной задаче, - задаче скрытого дискретного логарифмирования[1]. Она объединяет в себе задачу поиска сопрягающего элемента[2] и дискретного логарифмирования в скрытой коммутативной подгруппе[3], которые перспективны для построения протоколов открытого согласования секретного ключа и открытого шифрования повышенной криптостойкости. Однако, криптосхемы, построенные с использованием задачи скрытого дискретного логарифмирования, имеют серьезный недостаток - низкую производительность. Этот недостаток обусловлен необходимостью использования в таких криптосхемах некоммутативных групп, операции в которых требуют больших вычислительных затрат. В связи с этим проблема повышения производительности криптосхем, основанных на некоммутативных конечных группах является актуальной.

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

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

1. Вывод значения порядка конечных некоммутативных групп векторов размерности 4, построенных над кольцом целых чисел;

2. Вывод значения порядка конечных некоммутативных групп векторов размерности 4, построенных над полем многочленов;

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

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

5. Оценка производительности криптосхем с распараллеливанием операций.

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

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

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

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

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

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

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

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

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

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

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

3) Исследовано строение конечных некоммутативных групп векторов размерности 4.

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

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

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

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

Структура и объем диссертации.

Диссертационная работа изложена на 103 страницах и содержит 4 главы, 18 таблиц, 6 рисунков и список использованной литературы из 49 наименований.

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

В главе 2 описан общий способ задания конечных групп векторов и детально рассмотрено задание некоммутативных конечных групп четырехмерных векторов. Выведены формулы порядков элементов таких групп при задании над кольцом целых чисел и полем многочленов. Экспериментально проверена корректность полученных формул. Даны рекомендации по выбору параметров задания конечных некоммутативных векторов размерности 4 для построения криптосхем на их основе.

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

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

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

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

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

Основные результаты диссертационного исследования:

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

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

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

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

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

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

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

8. Предложен способ реализации алгоритма ЭЦП над некоммутативными конечными группами векторов на основе протокола с нулевым разглашением.

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

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

Вопросы защиты информации. 2011. № 1. С. 19-23.

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

3. Аль-Рахми Р.Я., Борков П.В., Галанов А.И., Горячев A.A. Синтез криптосхем с использованием автоморфизмов конечных коммутативных групп // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. С. 88

4. Борков П.В., Горячев A.A., Костина A.A., Сухов Д.К. Ускорение алгоритмов открытого и коммутативного шифрования над конечными некоммутативными группами // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. С. 93-94

5. Куприянов И.А., Горячев A.A., Костина A.A., Сухов Д.К. Варианты алгоритмов коммутативного шифрования с использованием конечных некоммутативных групп // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. С. 117-118

6. Головачев Д.А., Горячев A.A., Молдовяну П.А. Методические аспекты задания конечных колец над конечными векторными пространствами при изучении теоретических основ криптографии. // XVII Международная научно-методическая конференция «Современное образование: содержание, технологии, качество», 20 апреля 2011г. Материалы конференции. Том 2. С. 174-176

7. Горячев A.A., Кишмар Р.В., Хо Нгок Зуй Методические аспекты изложения протоколов с нулевыми знаниями: толкование термина «нулевое разглашение» в дисциплине «Криптографические протоколы» // XVII Международная научно-методическая конференция «Современное образование: содержание, технологии, качество», 20 апреля 2011г. Материалы конференции. Том 2. С. 238-240

8. Васильев И.Н., Горячев A.A., Кишмар Р.В. Протокол аутентификации на основе двух трудных задач. // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 24-25 ноября 2011, - СПб.: ВАС, 2011, С. 61-65

9. Аль-Рахми Р.Я., Горячев A.A., Латышев Д.М. Синтез хэш-функций на основе операций над конечными некоммутативными группами //

Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 25-56 ноября 2010 года, Санкт-Петербург. СПб.: ВАС, 2010. С. 57-62

Ю.Горячев A.A. Построение и анализ криптосхем над конечными некоммутативными группами векторов. // Вторая межвузовская научная конференция по проблемам безопасности СПИСОК-2011, 28-29 апреля 2011г. Материалы конференции. СПб.: ВВМ, 2011. С. 448-450

11 .Горячев A.A. Методы увеличения быстродействия криптосхем, основанных на скрытой задаче дискретного логарифмирования. //

Сборник тезисов докладов конгресса молодых ученых, Выпуск 1. - Спб: НИУ ИТМО, 2012, С. 185

Заключение

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

Список литературы диссертационного исследования кандидат технических наук Горячев, Александр Андреевич, 2013 год

Литература

1. Sakalauskas Е., Tvarijonas P., Raulynaitis A. Key Agreement Protocol (КАР) Using Conjugacy and Discrete Logarithm Problems in Group Representation Level // INFORMATICA Vol. 18. N. 1,2007. C. 115-124.

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

3. Moldovyan D.N. Non-Commutative Finite Groups as Primitive of Public-Key Cryptoschemes // Quasigroups and Related Systems. Vol. 18, 2010. С. 11-24.

4. Информатика: введение в информационную безопасность // М.М Вус, B.C. Гусев, Д.В. Долгирев, A.A. Молдовян - СПб.: Изд. Р. Асланова «Юридический центр Пресс», 2004. - 204с.

5. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. - М.: Радио и связь, 1999. 328 с.

6. Фергюсон Н., Шнайер Б. Практическая криптография. // М., СПб, Киев. Издательский дом «Вильяме», 2005. - 424 с.

7. Молдовян A.A., Молдовян H.A., Советов Б.Я. Криптография. / СПб.: Лань, 2000. 218 с.

8. G. Ateniese, М. Steiner, G. Tsudik Authenticated Group Key Agreement and Friends // ACM Symposium on Computer and Communication Security, 1998.

9. M. Steiner, G. Tsudik, M. Waidner Diffie-Hellman key distribution extended to groups // ACM Press: ACM Conference on Computer and Communications Security, 1996. C.31-37

10. Diffie W., Hellman M. New directions in cryptography // IEEE Information Theory Society. — New York: Institute of Electrical and Electronics Engineers, Vol. 22, 1976. C. 644-654.

11. Федеральный закон Российской Федерации от 6 апреля 2011 г. N 63-ФЗ «Об электронной подписи» // Российская газета. Федеральный выпуск №5451 М.: ФГБУ «Редакция „Российской газеты"» 2011. 12 С.

12. Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черёмушкин А.В. "Основы криптографии: учебное пособие" / М.. Гелиос АРВ, 2005. 480 с.

13. ElGamal Т. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Transactions on Information Theory. V. IT 31. N. 4., 1985. C. 469-472.

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

15. Соколов А. В., Шаньгин В. Ф. Защита информации в распределенных корпоративных сетях и системах //М.: ДМК, 2002. 328 с.

16. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems (англ.) // Communications of the ACM. — New York, NY, USA: ACM, 1978. — T. 21. — № 2, Feb. 1978. C. 120—126.

17. Schnorr C. P. Efficient signature generation by smart cards // J. Cryptology. -1991.-V. 4. C. 161-174.

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

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

20. 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. C. 417-426.

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

22. ГОСТ P 34.10-2001. Информационные технологии. Криптографическая защита информации. Процессы формирования и проверки цифровой подписи. / М.: ИПК Издательство стандартов, 2001. 16 С.

23. Federal information processing standards publication 186-3 / National Institute of Standards and Technology, 2009. 160 C.

24. Дернова E.C., Костина A.A., Молдовяну П.А. Конечные группы матриц как примитив алгоритмов цифровой подписи // Вопросы защиты информации.

2008. №3. С. 8-12.

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

26. Ко Kihyoung, Lee Sangjin, Cha Jaechoon, Choi Dooho. Cryptosystems Based on Non-commutativity // Patent Application #W02001KR01283., 2003.

27. Ко K.H., Lee S.J., Cheon J.H., Han J.W., Kang J.S., Park C. New Public-Key Cryptosystems Using Braid Groups / Advances in Cryptology - Crypto 2000 // Lecture Notes in Computer Science. Springer-Verlag, 2000. C. 166-183.

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

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

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

31. Moldovyan D.N., Moldovyan N.A. A New Hard Problem over Non-Commutative Finite Groups for Cryptographic Protocols // Springer Verlag LNCS. 2010. C. 183-194

32. Молдовян H.A. Аутентификация информации в АСУ на основе конечных групп с многомерной цикличностью // Автоматика и телемеханика.

2009. №8. С. 177-190.

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

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

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

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

37. Горячев А.А., Захаров Д.В., Куприянов И.А., Сухов Д.К. Генерация элементов специального порядка в конечных некоммутативных группах // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции. 2010, г.Санкт-Петербург. СПб.: ВАС, 2010. С. 169-174.

38. Саломаа А. Криптография с открытым ключом. / М.: Мир, 1995. — 318 с

39. A. J. Menezes, Р. С. van Oorschot, S. A. Vanstone. Handbook of Applied Cryptography / CRC Press, 1997. 816 C.

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

41.FeigeU., Fiat A., Shamir A. Zero-knowledge proofs of identity // J. of Cryptology, V. 1, No 2, 1988. C. 77-94.

42. Goldreich O., Krawczyk H. On the composition of zero-knowledge proof systems // SIAM J. Comput. V. 25, No 1, 1996. C. 169-192.

43. Горячев A.A., Кишмар P.B., Xo Нгок Зуй Методические аспекты изложения протоколов с нулевыми знаниями: толкование термина «нулевое разглашение» в дисциплине «Криптографические протоколы» // XVII Международная научно-методическая конференция «Современное образование: содержание, технологии, качество», 20 апреля 2011г. Материалы конференции. Том 2. С. 238-240

44. Куприянов И.А., Горячев A.A., Костина A.A., Сухов Д.К. Варианты алгоритмов коммутативного шифрования с использованием конечных некоммутативных групп // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. С. 117-118

45. Hellman М.Е., Pohling S.С. Exponentiation Cryptographie Apparatus and Method // U.S. Patent # 4,424,414. 3 Jan. 1984.

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

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

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

49. Борков П.В., Горячев A.A., Костина A.A., Сухов Д.К. Ускорение алгоритмов открытого и коммутативного шифрования над конечными некоммутативными группами // XII Санкт-Петербургская международная конференция Региональная информатика «РИ-2010» СПб, 20-22 октября 2010г. Материалы конференции. СПб, 20. С. 93-94