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

• Пылин, Владислав Владимирович
• кандидат технических наук
• 2008

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

ГЛАВА 1. ОБОСНОВАНИЕ НЕОБХОДИМОСТИ РЕШЕНИЯ ЗАДАЧИ ГЕНЕРАЦИИ КРИПТОГРАФИЧЕСКИ СТОЙКОЙ ЭЛЛИПТИЧЕСКОЙ КРИВОЙ ДЛЯ АСИММЕТРИЧНОЙ КРИПТОСИСТЕМЫ.

1.1. Симметричные и асимметричные криптографические системы.

1.1.1. Понятие асимметричной криптографической системы.

1.1.2. Сравнительный анализ свойств асимметричной и симметричной криптосистем.

1.2. Оценка криптографической стойкости асимметричных криптосистем.

1.2.1. Базовые параметры асимметричной криптосистемы на основе модульного возведения в степень.

1.2.2. Базовые параметры асимметричной криптосистемы на базе эллиптической кривой.

1.2.3. Алгоритмы дискретного логарифмирования для оценки стойкости асимметричных криптосистем.

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

1.3. Разработка алгоритма определения факта криптографической стойкости эллиптической кривой.

1.3.1. Сравнительный анализ требований, предъявляемых к криптографически стойкой эллиптической кривой согласно стандартам асимметричного шифрования ЕСЭЗА и ГОСТ Р 34.10

1.3.2. Алгоритм определения факта криптографической стойкости эллиптической кривой.

1.4. Обоснование необходимости решения задачи генерации криптографически стойких ЭК для асимметричной криптосистемы на базе ЭК.

1.4.1. Обоснование необходимости использования комплексного подхода для решения задачи генерации криптографически стойкой ЭК.

1.4.2. Разработка метода сравнительной оценки стойкости эллиптических кривых.

Выводы.

ГЛАВА 2. МЕТОДИКА ВЫБОРА/ГЕНЕРАЦИИ КРИПТОГРАФИЧЕСКИ СТОЙКОЙ ЭЛЛИПТИЧЕСКОЙ КРИВОЙ ДЛЯ АСИММЕТРИЧНОЙ КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ.

2.1. Определение индексов стойкости ЭК для метода оценки сравнительной стойкости эллиптических кривых.

2.2. Общая модель выбора криптографически стойкой эллиптической кривой для асимметричной криптосистемы на эллиптических кривых

2.3. Методика выбора/генерации криптографически стойкой эллиптической кривой.

2.3.1. Методы генерации эллиптической кривой.

2.3.2. Метод выбора эллиптической кривой.

2.4. Рекомендации по использованию методики выбора/генерации криптографически стойкой эллиптической кривой.

Выводы.

ГЛАВА 3. РАЗРАБОТКА АЛГОРИТМОВ ГЕНЕРАЦИИ КРИПТОГРАФИЧЕСКИ СТОЙКИХ ЭЛЛИПТИЧЕСКИХ КРИВЫХ.

3.1. Разработка стратегии «случайного выбора» эллиптической кривой

3.1.1. Общее описание алгоритма расчёта числа точек ЭК над конечным полем.

3.1.2. Алгоритм Чуфа для расчёта числа точек ЭК.

3.1.3. Алгоритм SEA для расчёта числа точек ЭК.

3.1.4. Алгоритм раннего обнаружения нестойкой ЭК.

3.2. Разработка стратегии «детерминированной генерации» эллиптической кривой.

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

Выводы.

ГЛАВА 4. АНАЛИЗ РЕЗУЛЬТАТОВ ИСПОЛЬЗОВАНИЯ МЕТОДИКИ ВЫБОРА/ГЕНЕРАЦИИ КРИПТОГРАФИЧЕСКИ СТОЙКОЙ

ЭЛЛИПТИЧЕСКОЙ КРИВОЙ ДЛЯ АСИММЕТРИЧНОЙ КРИПТОСИСТЕМЫ НА ЭЛЛИПТИЧЕСКИХ КРИВЫХ.

4.1. Описание базы криптографически стойких ЭК.

4.1.1. Количественные характеристики базы.

4.1.2. Разделение базы ЭК по уровням криптостойкости.

4.2. Анализ результатов использования стратегии «случайного выбора» эллиптической кривой.

4.2.1. Анализ количества перебираемых ЭК до нахождения искомой.

4.2.2. Анализ продолжительности генерации ЭК.

4.3. Анализ результатов использования стратегии «детерминированной генерации» эллиптической кривой.

4.4. Защита базы криптографически стойких эллиптических кривых от несанкционированного доступа.

4.4.1. Использование встроенного метода шифрование mdb-файлов Microsoft Access.

4.4.2. Метод прозрачного шифрования для защиты базы криптографически стойких эллиптических кривых.

Выводы.

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

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

Диссертационная работа опирается на результаты исследований таких ученых как Н.Коблиц, Р.Чуф, Дж.Сильверман, А.Аткин, Ф.Моран, С.Ванстоун, А.Менезес, Т.Окамото. В работе получили развитие отдельные положения этих исследований применительно к задаче создания методики генерации криптографически стойкой ЭК и задаче оценки стойкости ЭК.

Проблема выбора криптографически стойкой ЭК для асимметричной КС, связанная, прежде всего, с трудоёмкостью вычислений и сложностью реализации соответствующих алгоритмов, вызвала необходимость разработки методики выбора/генерации криптографически стойкой ЭК, доступной для использования в реальных КС. В работе показано, что наиболее перспективным является подход на основе сочетания стратегий «случайного выбора» ЭК и «детерминированной генерации» ЭК, основанных на использовании метода комплексного умножения и алгоритма SEA, соответственно. Предложенная автором методика позволяет накапливать базу ЭК, предоставляя возможность либо выбрать из уже имеющихся ЭК, либо сгенерировать новую. Использование данной методики повышает криптостойкость всей системы.

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

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

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

-— разработка метода сравнительной оценки стойкости ЭК; разработка метода защиты mdb-файлов СУБД Microsoft Access, содержащих базу криптографически стойких ЭК; разработка программного обеспечения, реализующего методику выбора/генерации криптографически стойкой ЭК для асимметричных КС на ЭК.

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

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

Положения, выносимые на защиту: модифицированный алгоритм раннего обнаружения нестойкой ЭК, позволяющий сократить число перебираемых ЭК в процессе поиска искомой при использовании стратегии «случайного выбора»; метод сравнительного анализа стойкости ЭК, позволяющий получить сравнительную оценку криптографической стойкости ЭК; методика выбора/генерации криптографически стойкой ЭК для асимметричной криптосистемы на ЭК, сочетающая в себе методы генерации ЭК с помощью стратегий «детерминированной генерации» и «случайного выбора», а также метод сравнительной оценки стойкости ЭК и метод выбора ЭК; метод защиты mdb-файлов Microsoft Access на основе шифрования заголовка файла.

Научная новизна работы состоит в следующем: предложена модификация алгоритма раннего обнаружения нестойкой ЭК, используемого в рамках алгоритма расчёта точек ЭК SEA; разработан метод сравнительного анализа стойкости ЭК, позволяющий получить сравнительную оценку их криптографической стойкости; предложена методика выбора/генерации криптографически стойкой ЭК для асимметричной криптосистемы на ЭК, сочетающая в себе методы генерации ЭК с помощью стратегий «детерминированной генерации» и «случайного выбора», а также метод сравнительной оценки стойкости ЭК и метод выбора ЭК; предложен метод защиты mdb-файлов Microsoft Access на основе шифрования заголовка файла.

Практическая полезность и реализация результатов работы состоит в следующем: разработано программное обеспечение, реализующее указанную методику и позволяющее получать ЭК, отвечающие различным требованиям стойкости, в том числе и требованиям ГОСТ Р 34.10 — 2001, которое может использоваться как отдельно, так и в рамках асимметричной КС; в результате использования разработанного программного обеспечения получена база, содержащая 5944 криптографически стойких ЭК; разработанный метод защиты данных, содержащихся в mdb-файлах СУБД Microsoft Access, может быть применён в любом приложении, использующем указанную СУБД.

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

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

Международная научно-техническая конференция по интеллектуальным системам AIS'06 (Дивноморское, 2006);

Региональная научно-техническая конференция «Информационные технологии в образовании» (Марийский государственный технический университет, г. Йошкар-Ола, 2006);

Международная научно-техническая конференция по интеллектуальным системам AIS'07 (Дивноморское, 2007);

Всероссийская научно-техническая конференция «Информационные технологии в образовании» (Марийский государственный технический университет, г. Йошкар-Ола, 2007);

Международная конференция «РусКрипто2008» (Ассоциация «РусКрипто», г. Москва, 2008);

Всероссийская научно-техническая конференция с международным участием «Информационные технологии в образовании» (Марийский государственный технический университет, г. Йошкар-Ола, 2008).

Публикации. Основные результаты диссертационной работы изложены в 16 публикациях, в том числе 1 статья в центральном научно-техническом журнале, рекомендуемом ВАК РФ, 4 статьи в трудах международных научных конференций, 1 свидетельство об отраслевой регистрации программы для ЭВМ.

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

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

Выводы

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

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

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

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

5. Обоснована большая продуктивность стратегии «детерминированной генерации» и вместе с тем ограничения её использования.

6. Предложено решение вопроса защиты базы криптографически стойких ЭК на основе шифрования заголовка mdb-файлов Microsoft Access.

ЗАКЛЮЧЕНИЕ

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

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

3. Предложена модификация алгоритма раннего обнаружения нестойкой ЭК в процессе вычисления её числа точек алгоритмом SEA.

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

5. Разработан метод защиты mdb-файлов Microsoft Access на основе шифрования заголовка файла.

6. Разработано программное обеспечение, реализующее методику выбора/генерации криптографически стойкой ЭК для асимметричной криптосистемы на ЭК и позволяющее получать ЭК, отвечающие различным требованиям стойкости, в том числе и требованиям ГОСТ Р 34.10 - 2001, которое может использоваться как отдельно, так и в рамках асимметричной криптографической КС.

7. В результате использования разработанного программного обеспечения получена база, содержащая 5944 криптографически стойких ЭК.

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

1. Алгоритмические основы эллиптической криптографии / A.A. Болотов, С.Б. Гашков, А.Б. Фролов и др. -М.: МЭИ, 2000. 100 с.

2. Анализ криптографической стойкости алгоритмов асимметричного шифрования информации / А.О. Воробьев, А.Г. Коробейников, В.В. Пылин и др. // Известия вузов. Приборостроение. 2007. - Т.50, №8. - С. 28-32.

3. Баричев С.Г. Основы современной криптографии / С.Г Баричев, P.E. Серов. -М.: «Горячая линия Телеком», 2001. - 120 с.

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

5. ГОСТ Р 34.10 — 94. Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма. — М.: Госстандарт России, 1994.

6. ГОСТ Р 34.10 — 2001. Информационная технология. Криптографическая защита информации. Процедуры выработки и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма. — М.: Госстандарт России, 2001.

7. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. — М.: Госкомитет СССР по стандартам, 1989.

8. Коробейников А.Г. Математические основы криптологии / А.Г. Коробейников, Ю.А.Гатчин. Учебное пособие. СПб: СПб ГУ ИТМО, 2004. 109 с.

9. Лунин, A.B. Перспективы развития и использования асимметричных алгоритмов в криптографии / A.B. Лунин, A.A. Сальников // Защита информации. Конфидент. 1998. - №6. - С. 12-23

10. Погорелов, Б.А. Об определении основных криптографических понятий / Б.А. Погорелов, A.B. Черемушкин, С.И. Чечета // Доклад на конференции "Математика и безопасность информационных технологий" (МаБИТ-03, МГУ, 23-24 октября 2003 г.)

11. Программа сравнительного криптоанализа CryptoTest v. 1.0 Текст.: свидетельство об отраслевой регистрации разработки №5879 / В.В. Пылин. №50200600400 от 20.03.2006; Инновации в науке и образовании № 3(14). - 1 с.

12. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учетом специфики 64-разрядной версии Windows / Дж.Рихтер. — Пер, англ 4-е изд. - СПб; Питер; М.: 2001. -752 е.

13. Ростовцев, А.Г. Подпись и шифрование на эллиптической кривой: анализ безопасности и безопасная реализация / А.Г. Ростовцев, Е.Б. Маховенко// Проблемы информационной безопасности. Компьютерные системы. 2003. - №1. - С. 64-73.

14. Ростовцев А.Г. Теоретическая криптография / А.Г. Ростовцев, Е.Б. Маховенко. Спб.: AHO НПО «Профессионал», 2005. - 480 с.

15. Семенов, Г. Цифровая подпись. Эллиптические кривые /Г. Семенов // Открытые системы. 2002. - №7;8.

16. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. — М.: Издательство ТРИУМФ, 2002.-816 с.28., ACC: How Microsoft Access Uses Encryption. Microsoft Knowledge Base Article No. 140406, May 2003.

17. ANSI. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm, ANSI X9.62, 1998.

18. Atkin, A.O. Elliptic curves and primality proving / A.O. Atkin, F. Morain // Mathematics of Computation. 1993. - Vol. 61. - P. 29-68.

19. Bektemirov, B. Average ranks of elliptic curves / B. Bektemirov, B. Mazur, W. Stein and others // Bull. Amer. Math. Soc. 2007. - №44. -P.233-254

20. Buchmann, J. Efficient Construction of Cryptographically Strong Elliptic Curves / J. Buchmann, H. Baier // Lecture Notes in Computer Science. — 2001.-Vol.2138

21. Brent, R.P. An improved Monte Carlo factorization algorithm / R.P. Brent//BIT. 1980.-V. 20.-P. 176-184.

22. Broker, R. Constructing elliptic curves of prime order / R.Broker, P.Stevenhagen // Contemporary Mathematics. 2008. - №463. - P. 1728.

23. Computing Hilbert Class Polynomials / R. Broker, J. Belding, A. Enge and others // Lecture Notes in Computer Science. 2008. - Vol. 5011. -P. 282-295.

24. Coppersmith, D. Discrete logarithms in GF(p) / D. Coppersmith, A. Od-lyzhko, R. Schroeppel // Algorithmica. 1986. - Vol.1. - P. 1-15.

25. Csirik J. A. An exposition of the SEA algorithm, preprint, 2000.

26. Dewaghe, L., Remarks on the Schoof-Elkies-Atldn algorithm / L. De-waghe // Mathematics of Computation. 1998. - Vol. 67(223). - P. 12471252.

27. Galbraith, S. The probability that the number of points on an elliptic curve over a finite field is prime / S. Galbraith, J. McKee. preprint CORR 99-51, University of Waterloo, Centre for Applied Cryptographic Research. -1999.

28. Gaudry, P. Fast algorithms for computing the eigenvalue in the Schoof-Elkies-Atkin algorithm / P. Gaudry, F. Morain // International Conference on Symbolic and Algebraic Computation. — 2006. — P. 109-115.

29. Hankerson D. Guide to Elliptic Curve Cryptography / D. Hankerson, A. Menezes, S.A. Vanstone. Springer-Verlag, 2004. - 358 p.

30. Howe, E.W. On the group orders of elliptic curves over finite fields / E.W. Howe// Comp. Math. 1993. - Vol. 85. - P.229-247.

31. IEEE 1363, Standard Specifications for Public-Key Cryptography, 2000.

32. Koblitz N. A Course in Number Theory and Cryptography / N. Koblitz. — Springer-Verlag New York Inc., 1987.

33. Koblitz, N. CM-curves with good cryptographic properties / N. Koblitz // Advances in Cryptology — Crypto '91, Lecture Notes in Computer Science. 1992. - Vol.576. - P. 279-287.

34. Koblitz, N. Primality of the number of points on an elliptic curve over a finite field / N. Koblitz // Pacific J. Math. 1988. - Vol. 131(1). - P. 157165.

35. Konstantinou, E. On the Efficient Generation of Elliptic Curves over Prime Fields / E. Konstantinou, C. Stamatiou, C. Zaroliagis // Lecture Notes In Computer Science. 2002. - Vol.2523. - P.333-348.

36. Lehmann, F. Counting the number of points on elliptic curves over finite fields of characteristic greater than three / F. Lehmann, M. Maurer, V. Miiller, V. Shoup // Lecture Notes In Computer Science. 1994. - Vol. 877. - P.60-70.

37. Lencier, R. Counting the number of points on elliptic curves over finite fields: strategies and performances / R. Lencier, F. Morain // Lecture Notes in Computer Science. 1995. - Vol. 921. - P. 79-94.

38. Lencier, R. Finding good random elliptic curves for cryptosystems defined F2n / R. Lencier // Lecture Notes in Computer Science. 1997. -Vol.1233.-P.379-392.

39. Madsen, M. S. A general framework for p-adic point counting and application to elliptic curves on Legendre / M. S. Madsen. // Aarhus Univ. Mat. Inst, (prepr.ser) 2004. - N 2-04. - 18 p.

40. Menezes, A. Reducing elliptic curve logarithms to logarithms in a finite field / A. Menezes, T. Okamoto, S. Vanstone // IEEE Transactions on Information Theory. 1993. - Vol.39. -P.1639-1646.

41. Menezes A., Elliptic Curve Public Key Cryptosystems / A.Menezes. Kluwer Academic Publishers, Boston, 1993.

42. Miller, V. Elliptic Curve and their Use in Cryptography / V. Miller // Proc. of PKC'97, Springer-Verlag, 1997.

43. Mueller, V. On the generation of Cryptographically Strong Elliptic Curves / V. Mueller, S. Paulus. Technical Report, Technical University of Darmstadt, 1997.

44. Oorschot, P.C. Parallel collision search with cryptanalitic application / P.C. van Oorschot, M.J. Wiener // J. Cryptology. 1999. - Vol.12. - P. 1-28.

45. Pollard, J.M. Monte Carlo methods for index computation (mod p) / J.M. Pollard //Math. Comp. 1978. -V. 32 (143). - P. 918-924.

46. Popov, V. Additional Cryptographic Algorithms for Use with GOST 28147-89, GOST R 34.10-94, GOST R 34.10-2001, and GOST R 34.1194 Algorithms / V. Popov, I. Kurepkin, S. Leontiev. RFC 4357, January 2006.

47. Robinson G. Real World Microsoft Access Database Protection and Security / G.Robinson. Berkeley, CA.: Apress, 2003.

48. Schoof, R. Counting points on elliptic curves over finite fields R. Schoof // J. Theorie des Nombres des Bordeaux. 1995. - Vol.7. - P. 219-254.

49. Schoof, R. Elliptic curves over finite fields and the computation of square roots mod p / R. Schoof// Math. Comp. 1985. - Vol.44. - P. 483-494.

50. Shanks, D. Class number, a theory of factorization and genera / D. Shanks // Proc. Symp. Pure Math. 1971. - Vol. 20. - P. 415-440.

51. Stein, W. A. A database of elliptic curves first report / W.A. Stein, M. Watkins // Lecture Notes in Comput. Sci. - 2002. - Vol. 2369. - P.267-275.