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

введение.

глава 1. постановка задачи.

1.1. Задачи, положенные в основу двухключевой криптографии.

1.2. Криптосистемы на эллиптических кривых и их сравнительный анализ. Постановка задачи.

Выводы.

глава 2. разработка алгоритмов генерации эллиптической кривой.

2.1. Криптографические требования к выбору эллиптической кривой.

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

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

2.3.1. Случай трех корней кубической части.

2.3.2. Случай одного корня кубической части.

2.3.3. Случай неприводимой кубической части.

2.3.4. Алгоритмы генерации эллиптической кривой над полем произвольной характеристики.

Выводы.

глава 3. разработка алгоритмов арифметики.

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

3.1.1. Разработка алгоритмов арифметики для простого поля.

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

3.1.3. Разработка алгоритма умножения точки на число с использованием комплексного умножения.

3.2. Сравнение разработанных алгоритмов умножения точки на число с известными алгоритмами (для эллиптической кривой над простым полем).

Выводы.

Глава 4. Исследование безопасности, функциональные возможности и практическое использование.

4.1. Исследование влияния комплексного умножения на сложность логарифмирования.

4.2. Исследование функциональных возможностей.

4.2.1. Шифрование с открытым ключом.

4.2.2. Цифровая подпись.

4.2.3. Аутентификация на основе доказательств с нулевым разглашением знаний.

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

4.2.5. Скрытый канал.

4.2.6. Передача информации со стиранием.

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

4.3.1. Управление ключами.

4.3.2. Подпись "вслепую" для электронных платежей.

Выводы.

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

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

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

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

Низкая производительность криптоалгоритмов с открытым ключом вызвала необходимость разработки специализированных вычислителей для персональных компьютеров, выполненных, как правило, на быстрых процессорах цифровой обработки сигналов (см., например, [26]).

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

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

Данная работа посвящена вопросам создания криптосистем с открытым ключом на основе эллиптических кривых над конечными полями. Использовать эллиптические кривые над конечными полями для криптографических целей предложили В.Миллер [39] и Н.Коблиц [32]. В настоящее время многие страны (США, Франция, Канада, Япония, Австралия и др.) ведут интенсивные исследования в области эллиптических кривых и их применения в криптографии. Многие направления исследований поддерживаются правительственными грантами.

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

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

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

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

Таким образом, возникают четыре основные задачи:

1. Разработать алгоритмы генерации общего открытого ключа.

2. Разработать быстрые алгоритмы арифметики эллиптической кривой.

3. Исследовать функциональную полноту данного класса кривых.

4. Исследовать безопасность криптосистем на кривых данного класса.

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

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

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

3. Алгоритмы вычислений на эллиптической кривой над Г „, р р = 2т ± С, позволяющие ускорить обработку информации в разработанной криптосистеме.

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

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

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

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

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

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

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

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

1. На основе разработанной методики составлены таблицы неизоморфных общих ключей для поля характеристики 216+1, позволяющие выбрать общий ключ при построении криптосистемы с заданным уровнем стойкости.

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

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

4. Разработан комплекс лабораторных работ для курсов специальности 22.06.00 — "Организация и технология защиты информации".

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

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

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

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

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

Приложение 1 содержит значения простых порядков факторгруппы Е(¥рП)!Е{¥р) для различных степеней расширения п, полученных разработанными алгоритмами выбора числа точек эллиптической кривой для поля характеристики 216+1. В приложениях 2-4 приведены результаты генерации общих открытых ключей, полученные с помощью разработанных методик, для криптосистем на эллиптических кривых над полем характеристики 216+1 с широким диапазоном уровня стойкости. В приложении 5 даны таблицы предвычислений, позволяющие ускорить обработку информации в рассмотренной криптосистеме. В приложение 6 включены некоторые характеристики поля, удобные для построения криптосистем с использованием разработанной методики для процессоров различной разрядности.

Выводы

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

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

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

Заключение

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

- разработаны алгоритмы генерации общих открытых ключей, в том числе методика выбора порядка группы эллиптической кривой над F „, удовлетворяющей условиям БПД и НСВ. Предложен метод нахождения неизоморфных канонических общих открытых ключей с одним параметром и на его основе разработан алгоритм генерации эллиптической кривой над Ер с требуемым числом точек;

- разработаны алгоритмы арифметики, позволяющие значительно ускорить криптографические алгоритмы по сравнению с эллиптическими кривыми над простым полем того же уровня стойкости; в качестве неприводимого полинома, задающего ЕПЕ „), предложено иср пользовать трехчлен вида Г + £ + а; для ускорения умножения точки на число показатель предложено представлять во "фробениусовой" системе счисления (п - 2)-разрядным числом;

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

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

С помощью разработанной методики построена криптосистема на Е(Р „) с/? = 216+1,и = 11ч-19 для реализации на отечественном р

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

Разработанные методики использованы при создании комплекса лабораторных работ для курсов специальности 22.06.00 — "Организация и технология защиты информации". Основные теоретические и практические результаты работы использованы в научно-исследовательских и опытно-конструкторских работах, проводимых Санкт-Петербургским региональным центром защиты информации.

Разработанный подход позволяет создавать криптосистемы на эллиптических кривых, заданных над полями различных простых характеристик вида р = 2т ± С. Некоторые возможные характеристики приведены в приложении 6, табл. П6.1.

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. —М.: Мир, 1979.2. ван дер Варден. Алгебра. — М.: Наука, 1979.

2. Вейль А. Основы теории чисел. — М.: Мир, 1972.

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

4. ГОСТ 34.11-94. Информационная технология. Криптографическая защита информации. Функция хэширования. М.: Госстандарт России, 1994.

5. Карацуба А., Офман Ю. Умножение многозначных чисел на автоматах. —Доклады АН СССР. т. 145, № 2, 1961. С. 293-294.

6. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. — М.: Мир, 1976; Т.2. Получисленные алгоритмы. — М.: Мир, 1977.

7. Коблиц Н. Введение в эллиптические кривые и модулярные формы. — М.:Мир, 1988.

8. Ленг С. Алгебра. — М.: Мир, 1968.

9. Ю.Лидл Р., Нидеррейтер X. Конечные поля. — М.: Мир, 1988.

10. П.Прасолов В.В., Соловьев Ю.П. Эллиптические функции и алгебраические уравнения. — М.: Изд-во "Факториал", 1997.

11. Ростовцев А.Г., Буренкова А.П. О невозможности улучшения алгоритма Полларда для шифров, образующих группу. — Конференция "Региональная информатика" РИ-96, СПб., 1996. С. 121.

12. Семаев И.А. Быстрый алгоритм вычисления спаривания А. Вейля на эллиптической кривой. — Международная конференция

13. Современные проблемы теории чисел". Тезисы докладов. Тула, 1993.

14. Степанов С.А. Арифметика алгебраических кривых. — М.: Наука, 1991.

15. Шафаревич И.Р. Основы алгебраической геометрии. — М.: Наука, 1972.

16. Шенхаге А., Штрассен В. Быстрое умножение больших чисел. — Кибернетический сборник, нов. сер., вып. 10. М., Мир, 1973. С. 8798.

17. Adleman L.M., DeMarrais J., Huang M.-D. A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. — Algorithmic Number Theory, LNCS, v. 877, 1994, pp. 28-40.

18. Bach E., Shallit J. Algorithmic number theory, v. 1. Efficient algorithms. Mit Press, Cambridge, Massachusetts, 1996.

19. Balasubramanian R. The improbability that an elliptic curve has subexponential discrete log problem under the Menezes Okamoto - Van-stone algorithm. —Journal of Cryptology. v. 11, 1998, pp. 141-145.

20. Bengio S., Brassard G., Desmedt Y.G., Goutier C., Quisquater J.-J. Secure implementation of identification systems. — Journal of Cryptology, v. 4, n. 3, 1991, pp. 175-184.

21. Bleichenbacher D., Bosma W., Lenstra A.K. Some remarks on Lucas-based cryptosystems. Advances in Cryptology CRYPTO '95, LNCS, v. 963, 1995, pp. 386-396.

22. Buchmann J., Williams H.C. A key-exchange system based on imaginary quadratic fields. —Journal of Cryptology, v. 1, 1988, pp. 107-118.

23. Chaum D. Blind signatures for untraceable payments. — Advances in Cryptology: Proceedings of Crypto '82, Plenum Press, 1983, pp. 199203.

24. Coppersmith D. Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory, v. 30, 1984. pp. 587594.

25. Diffie W., Hellmann M.E. New directions in cryptography. IEEE Transactions on Information Theory, v. 22, 1976, pp. 644-654.

26. Dussé S.R., Kaliski B.S. Jr. A cryptographic library for the Motorola DSP 56000. — Advances in Cryptology EUROCRYPT '90, LNCS, v. 473,1991, pp. 230-244.

27. ElGamal T. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, IT-31, 1985, pp. 469-472.

28. Gallant R., Lambert R., Vanstone S. Improving the parallelized Pollard lambda search on binary anomalous curves. 1998.

29. Gordon D.M. Discrete logarithms in GF(p) using the number field sieve. SIAM Journal of Computing, v. 6, № 1, Feb 1993, pp. 124-138.

30. Husemôller D. Elliptic Curves. — Springer-Verlag, 1986.

31. Koblitz N. A course in number theory and cryptography. — SpringerVerlag, 1987.

32. KoblitzN. Elliptic curve cryptosy stems. Mathematics of Computation, v. 48, n. 177, 1987, pp. 203-209.

33. Koblitz N. Hyperelliptic cryptosystems. — Journal of Cryptology, v. 1, n. 3,1989, pp. 139-150.

34. Koyama K., Maurer U., Okamoto T., Vanstone S. New public-key schemes based on elliptic curves over the ring Zn. — Advances in Cryptology CRYPTO '91, LNCS, v. 576, 1992, pp. 252-266.

35. Koyama K., Tsuruoka Y. Speeding up elliptic cryptosystems by using a signed binary window method. — Proceedings of Crypto '92, LNCS, v. 1993, pp. 345-357.

36. Lercier R. Finding good random elliptic curves for cryptosystems defined over F2„. Advances in Cryptology — EUROCRYPT '97, LNCS, 1997,pp. 479-491.

37. Menezes A., Okamoto T., Vanstone S.A. Reducing elliptic curve logarithms to logarithms in a finite field. IEEE Transactions on Information Theory, v. 39,1993. pp. 1639-1646.

38. Menezes A., van Oorchot P., Vanstone S.A. Handbook on applied cryptography. — CRC press, 1997.

39. Miller V.S. Use of elliptic curves in cryptography. — Advances in Cryptology CRYPTO '85, LNCS, v. 218, 1986, pp. 417-426.

40. Miyaji A. Elliptic curves over Fp suitable for cryptosystems. — Advances in Cryptology AUSCRYPT '92, LNCS, v. 718, 1993, pp. 479491.

41. Montgomery P.L. Modular multiplication without trial division. — Mathematics of Computation, v. 44, № 170, April 1985, pp. 519-521.

42. Morain F. Building cyclic elliptic curves modulo large primes. — Advances in Cryptology EUROCRYPT '91, LNCS, v. 547, 1991, pp. 328336.

43. Miiller V. Fast multiplication on elliptic curves over small fields of characteristic two. —Journal of Cryptology, v. 11,1998, pp. 219-234.

44. Pollard J.M. Monte Carlo methods for index computation (mod p). Mathematics of Computation, v. 32, № 143, 1978, pp. 918-924.

45. Rabin M.O. Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, Laboratory for Computer Science, MIT, 1979.

46. Rabin M.O. How to exchange secrets by oblivious transfer. — Technical Memo TR-81, Aiken Computer Laboratory, Harvard University, 1981.

47. Reitwiesner G. Binary arithmetic. Advances in Computers, n. 1, 1960, pp. 231-308.

48. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems. CACM, v. 21, № 2, 1978, pp. 120126.

49. Schneier B. Applied cryptography, second edition. Protocols, algorithms and source code in C. — J. Wiley, 1997.

50. Schnorr C.P. Efficient identification and signatures for smart cards. Advances in Cryptology — CRYPTO '89. LNCS, v. 435, Springer-Verlag, 1990, pp. 239-251.

51. Schoof R. Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of Computation, n. 44, 1985, pp. 483-494.

52. Schoof R. Counting points on elliptic curves over finite fields. Journal de Théorie des Nombres de Bordeaux, n. 7, 1995. pp. 219-254. http://www.emath.fr/Math/Jtnb/jtnbl 995-1 .html.

53. Schroeppel R., Orman H., O'Malley S., Spatscheck O. Fast key exchange with elliptic curve cryptosystems. Advances in Cryptology -CRYPTO '95, LNCS, v. 963, 1995, pp. 43-56.

54. Semaev I.A. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curves in characteristic p. —Mathematics of Computation. v. 67, n. 221,1998, pp. 353-356.

55. Shanks D. Class number, a theory of factorization, and genera. 1969 Number Theory Institute, Proceedings of Symposia in Pure Mathematics, v. 20, AMS, New-York, 1971, pp. 415-440.

56. Silverman J.H. The arithmetics of elliptic curves. — Springer-Verlag, 1986.

57. Simmons G. The subliminal channel and digital signatures. In Advances in Cryptology Proceedings of EUROCRYPT' 84, pp. 364-378.

58. Smart N.P. Elliptic curve cryptosystems over small fields of odd characteristic. — Journal of Cryptology, v. 12, 1999, pp. 141-151.

59. Smith P., Skinner C. A public-key cryptosystem and a digital signature system based on the Lucas function analogue to discrete logarithms. Advances in Cryptology — ASIACRYPT '94. LNCS, v. 917, SpringerVerlag, 1995, pp. 357-364.

60. Solinas J. An improved algorithm for arithmetic on a family of elliptic curves. — Advances in Cryptology — CRYPTO '97. LNCS, v. 1294, Springer-Verlag, 1997, pp. 357-371.

61. Wiener M.J., Zuccerato R.J. Faster attack on elliptic curve cryptosystems. 1998.