Криптография с использованием эллиптических кривых

Криптография с использованием эллиптических кривых.

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

Использование эллиптических  кривых для создания криптосистем было независимо предложено Нило Коблицем(англ.) иВиктором Миллером (англ.) в 1985 году.

 

Введение

Асимметричная криптография основана на сложности решения некоторых  математических задач. Ранние криптосистемы  с открытым ключом, такие как алгоритм RSA, безопасны благодаря тому, что сложно разложить составное число на простые множители. При использовании алгоритмов на эллиптических кривых полагается, что не существует субэкспоненциальных алгоритмов для решения задачи дискретного логарифмирования в группах их точек. При этом порядок группы точек эллиптической кривой определяет сложность задачи. Считается, что для достижения такого же уровня безопасности как и в RSA требуются группы меньших порядков, что уменьшает затраты на хранение и передачу информации. Например, на конференции RSA 2005 Агентство национальной безопасности объявила о создании “Suite B”, в котором используются исключительно алгоритмы эллиптической криптографии, причём для защиты информации классифицируемой до “Top Secret” используются всего лишь 384-битные ключи.

Эллиптические кривые над конечными полями

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

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

В криптографии эллиптические  кривые рассматриваются над двумя  типами конечных полей: простыми полями нечётной характеристики ( , где   — простое число) и полями характеристики 2 ( ).

Эллиптические кривые над полями нечётной характеристики

Над полем   характеристики   уравнение эллиптической кривой E можно привести к виду:

где   — константы, удовлетворяющие  .

Группой точек эллиптической  кривой E над полем   называется множество пар  , лежащих на E, объединённое с нулевым элементом  :

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

Пример

Рассмотрим эллиптическую  кривую   над полем  . На этой кривой в частности лежит точка  , так как  .

Теорема Хассе

Теорема Хассе об эллиптических  кривых утверждает, что количество точек на эллиптической кривой близко к размеру конечного поля:

что влечёт:

Аналог  алгоритма Диффи-Хеллмана обмена ключами

Обмен ключами с использованием эллиптических кривых может быть выполнен следу-ющим образом. Сначала выбирается простое число p ' 2180 и параметры a и b для уравне-

ния эллиптической кривой. Это задает множество точек Ep(a, b). Затем в Ep(a, b) выбира-

ется генерирующая точка G = (x1, y1). При выборе G важно, чтобы наименьшее значение

n, при котором n × G = 0, оказалось очень большим простым числом. Параметры Ep(a, b)

и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями A и B производится по следующей схеме.

1. Участник A выбирает целое  число nA, меньшее n. Это число является закрытым клю-

чом участника A. Затем участник A вычисляет открытый ключ PA = nA × G, который

представляет собой некоторую  точку на Ep(a, b).

2. Точно так же участник B выбирает закрытый ключ nB и вычисляет открытый ключ

PB.

3. Участники обмениваются  открытыми ключами, после чего  вычисляют общий секрет-

ный ключ K.

Участник A: K = nA × PB

Участник B: K = nB × PA

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

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

симметричного шифрования, то из этой пары необходимо создать одно значение.

Эллиптические кривые над полями характеристики 2

Над полем характеристики 2 рассматривают два вида эллиптических  кривых:

Суперсингулярная кривая

Несуперсингулярная кривая

Особое удобство суперсингулярных эллиптических кривых в том, что для них легко вычислить порядок, в то время как вычисление порядка несуперсингулярных кривых вызывает трудности. Суперсингулярные кривые особенно удобны для создания самодельной ЕСС-криптосистемы. Для их использования можно обойтись без трудоёмкой процедуры вычисления порядка.

Проективные координаты

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

в проективной системе координат каждая точка   представляется тремя координатами  , которые удовлетворяют соотношениям:

,  .

в системе координат Якоби точка также представляется тремя координатами   с соотношениями:  ,  .

в системе координат López-Dahab выполняется соотношение:  ,  .

в модифицированной системе  координат Якоби используются 4 координаты   с теми же соотношениями.

в системе координат Чудновского-Якоби используется 5 координат  .

Важно отметить, что могут  существовать различные именования — например, IEEE P1363-2000 называет проективными координатами то, что обычно называют координатами Якоби.

Шифрование/дешифрование с использованием эллиптических  кривых

Рассмотрим самый простой  подход к шифрованию/дешифрованию с  использованием

эллиптических кривых. Задача состоит в том, чтобы зашифровать  сообщение M, которое

может быть представлено в  виде точки на эллиптической кривой Pm(x, y).

Как и в случае обмена ключом, в системе шифрования/дешифрования в качестве па-

раметров рассматривается эллиптическая кривая Ep(a, b) и точка G на ней. Участник B

выбирает закрытый ключ nB и вычисляет открытый ключ PB = nB × G. Чтобы зашифро-

вать сообщение Pm используется открытый ключ получателя B – PB. Участник A выби-

рает случайное целое положительное число k и вычисляет зашифрованное сообщение Cm,

являющееся точкой на эллиптической кривой.

Cm = {k × G, Pm + k × PB}

100Чтобы дешифровать сообщение,  участник B умножает первую координату  точки на свой

закрытый ключ и вычитает результат из второй координаты:

Pm + k × PB − nB × (k × G) = Pm + k × (nB × G) − nB × (k × G) = Pm.

Участник A зашифровал сообщение  Pm добавлением к нему kxPB. Никто не знает значе-

ния k, поэтому, хотя PB и является открытым ключом, никто не знает k × PB. Противнику

для восстановления сообщения  придется вычислить k, зная G и k × G. Сделать это будет

нелегко.

Получатель также не знает  k, но ему в качестве подсказки посылается k × G. Умно-

жив k × G на свой закрытый ключ, получатель получит значение, которое было добавлено

отправителем к незашифрованному сообщению. Тем самым получатель, не зная k, но имея

свой закрытый ключ, может  восстановить незашифрованное сообщение.

Набор параметров

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

Итак, для поля характеристики 2 набор параметров:  , а для конечного поля  , где  , набор параметров:  .

Существует несколько  рекомендованных наборов параметров: NIST, SECG

Для создания собственного набора параметров необходимо:

-Выбрать набор параметров.

-Найти эллиптическую кривую, удовлетворяющую этому набору параметров.

Для нахождения кривой для  заданного набора параметров используются два метода:

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

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

Существует несколько  классов криптографически «слабых» кривых, которых следует избегать:

Кривые над  , где   - не простое число. Шифрование на этих кривых подвержено атакам Вейля.

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