Нуралиев Д.С.

Евразийский Национальный университет им. Л.Н.Гумилева, Казахстан

Эллиптические кривые

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

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

· системы разложения целых чисел на множители (система RSA — самая известная из них);

· дискретные логарифмические системы (например, DSA — американская правительственная система);

· дискретные логарифмические системы эллиптических кривых (криптосистемы эллиптических кривых).

Эллиптические кривые (Elliptic Curve Cryptography, ЕСС) — математические объекты, которые математики интенсивно изучают начиная с 17-го века. В 1985 году Нил Коблиц и Виктор Миллер независимо друг от друга предложили системы криптозащиты с открытым ключом, использующие для шифрования свойства аддитивной группы точек на эллиптической кривой. Эти работы легли в основу криптографии на основе алгоритма эллиптических кривых. Множество исследователей и разработчиков испытывали алгоритм ЕСС на прочность. Сегодня ЕСС предлагает более короткий и быстрый открытый ключ, обеспечивающий практичную и безопасную технологию, применимую в различных областях.

Сравнительная характеристика алгоритмов

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

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

На практике обычно используют комбинированную схему шифрования:

1) сообщение кодируют разовым секретным ключом;

2) секретный ключ кодируют открытым ключом получателя и пересылают вместе с сообщением;

3) получатель своим личным ключом восстанавливает секретный ключ отправителя;

4) сообщение расшифровывается секретным ключом.

По оценкам специалистов компании Certicom, криптосистемы на основе ЕСС обеспечивает самую высокую надежность на 1 бит ключа из всех известных систем с открытым ключом. Это достигается благодаря сложности базового алгоритма — вычисления дискретных логарифмов эллиптических кривых (ECDLP). При этом меньший по размеру ключ обеспечивает эквивалентный уровень безопасности. В табл. 2 приведены сравнения размеров ключей, необходимых для обеспечения эквивалентных уровней безопасности. Производительность вычислительных устройств с недавнего времени принято оценивать в MIPS (Million Instructions Per Second): 1 MIPS = 10 ⁶ onep./c. По отношению к эллиптическим кривым производительность 1 MIPS соответствует примерно 4*10 ⁴ операций сложения, поскольку длина ключа существенно превышает длину единицы данных. Устойчивость алгоритмов криптографии принято оценивать в MIPS-годах. Иначе говоря, устойчивость — это число лет непрерывной работы, необходимое вычислителю с производительностью 1 MIPS, чтобы взломать данный шифр.

Немного истории

История эллиптических кривых уходит в глубокую древность. А началось все с классической задачи нахождения конгруэнтных чисел. Натуральное число n является конгруэнтным, если существует прямоугольный треугольник, имеющий рациональные длины сторон и площадь, равную n. Так, например, конгруэнтно число 6.

Еще в Древнем Египте была известна дружественная тройка — 3, 4, 5, — которую использовали для построения прямых углов. А наименьшее конгруэнтное число — это 5 (1 ¹ / ₂ , 6 ² / ₃ , 6 ⁵ / ₆ ).

Уже древние арабские математики поставили задачу по данному натуральному n отыскать такое рациональное число х, чтобы числа (х ² - n) и (x ² + n) являлись квадратами рациональных чисел, что эквивалентно задаче нахождения конгруэнтных чисел.

Эйлер впервые показал, что 7 — конгруэнтное число, а Ферма доказал, что 1 — неконгруэнтное. Со временем были найдены многие конгруэнтные числа, однако попытки найти критерий конгруэнтности так и не увенчались успехом.

Сложность задачи иллюстрирует конгруэнтное число 157, вычисленное Доном Цагером, нашим современником. Его катеты выражаются числами:

6803298487826435051217540/411340519227716149383203 и 411340519227716149383203/21666555693714761309610

А гипотенуза:
224403517704336969224557513090674863160948472041/8912332268928859588025535178967163570015480830

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

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

у² = х³ - n² x

Алгоритм цифровой подписи ECDSA (Elliptic Curve Digital Signature Algorithm) строится на базе эллиптической кривой Е, заданной уравнением более общего вида: у ² = х ³ + ax + b, с дискриминантом (4а ³ + 27b ² )mod n <> 0. 

Процесс генерации ключей включает следующие процедуры:

1. Задаются параметры а и b эллиптической кривой.

2. Задаются параметры исходной точки Р(хр, ур). 
3. Выбирается достаточно большое простое число n, например из интервала 2¹⁵⁰ < n < 2 ¹⁶⁰ , в зависимости от требований к надежности.

4. Генерируется секретный ключ d, как число из интервала [ 1,1 -n], отвечающее ряду дополнительных требований.

5. Вычисляется вторая точка эллиптической кривой Q = (d*P)mod n. В качестве открытого ключа берется совокупность (а, b, хр, ур, xq, yq)

Литература:

1. Библиотека MSDN Library for Visual Studio 2008

2. Elliptic Curve Cryptosystem. Remarks on the security of the elliptic curve cryptosystem. Certicom whitepaper. http://www.certicom.com/resources/download/EccWhite3.pdf

3. Bruce Schneier, "Applied Cryptography, Second edition: Protocols, Algorithms, and Source Code in C". John Wiley & Sons, 1996