Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении)

2017-07-17 20:10

новости квантовых компьютеров, искусственный интеллект

Сегодня мы снова поговорим про протокол Диффи-Хеллмана, но уже построенный на более необычных конструкциях — изогениях, которые признаны устойчивыми к атакам на будущем квантовом компьютере. Квантовый компьютер, который сможет удержать в связанном состоянии порядка нескольких тысяч кубит, позволит находить закрытые ключи по открытым ключам у всех используемых сейчас асимметричных криптосистем. Число кубит для взлома RSA равно удвоенному числу бит в модуле (т.е. для разложения на множители модуля RSA длиной 2048 бит потребуется 4096 кубит). Для взлома эллиптических кривых необходимы более скромные мощности «квантового железа»: для решения задачи ECDLP для кривых над простым полем (такие кривые есть и в отечественном стандарте подписи ГОСТ Р 34.10-2012 и в американском ECDSS) c модулем кривой длиной n бит требуется 6n кубит (т. е. для модуля в 256 бит надо ~ 1536 кубит, а для 512 бит ~ 3072 кубит). На днях российско-американская группа ученых установила мировой рекорд, удержав в связанном состоянии 51 кубит. Так что у нас есть еще немного времени для изучения изогений (а также решеток, кодов, multivariate и подписей, основанных на хэшах).
Кстати, изогении считаются одним из наиболее вероятных кандидатов на победу на конкурсе NIST постквантовых алгоритмов для замены RSA и эллиптических кривых в ближайшие несколько лет. Предыдущую статью про прошлое и настоящее Диффи-Хеллмана можно почитать тут .

Что такое изогении?

Отображение, которое переводит точки одной кривой E1 в точки другой кривой E2 (либо в саму себя (тогда считаем E2 = E1)) следующим образом: если на кривой E1 мы выберем любые две точки A1 и B1 и отобразим их в точки A2 и B2 на кривой E2, тогда то же самое отображение обязательно переведет их сумму — точку С1 = A1 + B1 именно в точку С2 = A2 + B2 – сумму их отображений. Это замечательное свойство называется сохранением операции, а такое отображение является гомоморфизмом. Изогению можно выразить с помощью рациональной функции: точка (x, y) отображается в точку с координатами

$inline$(frac{f1(x, y)}{f2(x, y)}, frac{g1(x, y)}{g2(x, y)})$inline$

(где

$inline${f1, f2, g1, g2}$inline$

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

Каким свойством должны обладать две кривые, чтобы быть изогенными?

Теорема Tate:
Две кривые над одним конечным полем изогенны тогда и только тогда, когда порядки их групп равны.

Пример 1 (изогения кривой на саму себя):

Эндоморфизм: скалярное умножение точки на число:

$inline$ n*P $inline$

на кривой

$inline$ y^2 = x^3 + Ax + B$inline$

например, для n = 2 и

$inline$P = (x, y)$inline$

$inline$2*P = (frac{x^4 - 2Ax^2 - 8Bx - A^2}{4(x^3+Ax+B)}, frac{(x^6+5Ax^4+20Bx^3-5A^2x^2-4ABx - 8B - A)y}{8(x^3+Ax+B)^2}) $inline$

Для произвольного n аналогичная (но более длинная) формула может быть получена рекуррентно для при помощи так называемых полиномов деления (division polynomials)

Пример 2 (изогения между разными кривыми):

Пусть есть кривая

$inline$ E1 : y^2 = x^3+x+1 $inline$

над полем

$inline$ GF(19) $inline$

и кривая

$inline$ E2 : y^2 = x^3+4x+13 $inline$

над тем же полем.

Порядки групп (т.е. число точек на кривой) у E1 и E2 равны: #E1 = #E1 = 21

По теореме Тейта равенство #E1 = #E1 означает, что между E1 и E2 существует изогения.
j–инвариант E1 = 6, а j–инвариант E2 = 4. Т.е группы точек кривых не изоморфны.
(изоморфизм — это частный случай гомоморфизма, когда каждому элементу в отображении соответствует только один элемент образа (т.е. несколько элементов не переходят в один: отображение только «один в один»))

Изогения, которая отображает точки с E1 на E2 (откуда она взялась мы покажем в Примере 3) может быть представлена с помощью следующего рационального отображения:

Отображение

$inline$ ? : (x, y) $inline$

$inline$(frac{x^3-4x^2-8x-8}{x^2-4x+4}, frac{x^3y-6x^2y+5xy-6y}{x^3-6x^2-7x-8}) $inline$

Рассмотрим, к примеру, точки A1 (9, 6) и B1 (14, 2) кривой E1. Их сумма — точка С1 с координатами (5, 6). Если подставить их в формулу выше, то получим их отображение на кривую E2, Соответствующие им точки на E2 — A2, B2, C2:

A1 (9, 6) ? A2 (14, 1)
B1 (14, 2) ? B2 (17, 4)
C1 (5, 6) ? C2 (8, 5)

Легко проверить, что С2 = A2 + B2. Т.е. точка С1 = A1 + B1 переходит в точку С2 = A2 +B2. Если не лень, то можно перебрать все комбинации из любых двух точек E1 A и B и их отображений ?(A) и ?(B) и убедиться, что они ведут себя аналогично:

$inline$ ?(A + B) = ?(A) + ?(B) $inline$

А что будет, если подставить точки (2, 12) или (2, 7)? Знаменатель правой дроби будет равен нулю! Это всего лишь означает, что эти точки переходят в точку на бесконечности для E2.
Осталось рассмотреть точку на бесконечности на E1. Она «по умолчанию» переходит в точку на бесконечности на E2. Это фундаментальное свойство гомоморфизма: нейтральный элемент (в случае эллиптических кривых — это точка на бесконечности) отображается в нейтральный элемент. Иначе “сломается” сохранение операции для случая, когда один двух элементов – нейтральный.
Степенью изогении называется степень полинома

$inline$ f1 $inline$

в формуле отображения

$inline$(frac{f1(x, y)}{f2(x, y)}, frac{g1(x, y)}{g2(x, y)})$inline$

В Примере 2

$inline$ f1 = x^3 - 4x^2 - 8x - 8$inline$

Т.е. степень изогении равна 3. Степень означат то, во сколько раз отображение “сжимает” образ. Т.е. 3 разных точки E1 отображаются при такой изогении в одну точку на E2. Множество точек, которые отображаются в точку на бесконечности называются ядром изогении.

Вычисление изогений

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

Вход:
кривая

$inline$ E1: y^2 = x^3 + Ax + B$inline$

и одна из ее подгрупп

$inline$ C $inline$

(isogeny kernel)

Выход:
кривая

$inline$ E2: y^2 = x^3 + A'x + B'$inline$

, изогенная

$inline$ E1$inline$

и рациональное отображение

$inline$(frac{f1(x, y)}{f2(x, y)}, frac{g1(x, y)}{g2(x, y)})$inline$

Сложность алгоритма:

$inline$ O $inline$

$inline$ C $inline$

) шагов, где #

$inline$ C $inline$

– порядок

$inline$ C $inline$

Обозначение:

$inline$ E ? E/C $inline$

, где

$inline$ E/C $inline$

кривая, изогенная

$inline$ E $inline$

, полученная с помощью подгруппы

$inline$ C $inline$

На выходе мы получаем коэффициенты

$inline$A'$inline$

$inline$B'$inline$

для изогенной кривой и формулу с дробями. Подгруппа С – любая из подгрупп кривой. C является ядром изогении: все ее элементы переходят в точку на бесконечности. Если кривая E1 изогенна кривой E2, то верно и обратное: E2 изогенна E1: существует гомоморфное отображение и в обратную сторону.

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

Сложная задача для изогений:
Даны две изогенные кривые

$inline$ E1 $inline$

$inline$ E2 $inline$

с различными

$inline$ j $inline$

— инвариантами. Требуется найти изогению между ними.

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

Алгоритм Velu':

Вход:
кривая

$inline$ E1: x^3 + Ax + B$inline$

и одна из ее подгрупп

$inline$ C $inline$

(ядро изогении)

1. Отбрасываем точку на бесконечности
2. Находим

$inline$ C_2$inline$

— множество точек четного порядка из

$inline$ C $inline$

$inline$ R $inline$

— все остальные
3. Разбиваем

$inline$ R $inline$

на две части —

$inline$ R_+ $inline$

$inline$ R_- $inline$

: если точка P – в

$inline$ R_+ $inline$

, то обратная ей – в

$inline$ R_- $inline$

4. Множество

$inline$ S = C_2 ? R_+$inline$

Для каждой точки

$inline$ Q = (x_Q, y_Q) $inline$

из

$inline$ S $inline$

$inline$ g_Q^x = 3x_Q^2 + A $inline$

$inline$ g_Q^y = -2y_Q $inline$

$inline$ if (Q = -Q) $inline$

$inline$ v_Q = g_Q^x$inline$

$inline$ else $inline$

$inline$ v_Q = 2g_Q^x $inline$

$inline$ u_Q = (g_Q^y)^2 $inline$

$inline$ v = sum_{Q ? S}(v_Q) $inline$

$inline$ w = sum_{Q ? S}(u_Q + x_Qv_Q) $inline$

Коэффициенты

$inline$ A' $inline$

$inline$ B' $inline$

для уравнения изогенной кривой

$inline$ E' $inline$

$inline$ A' = A - 5v $inline$

$inline$ B' = B - 7w $inline$

Итак, изогенную кривую мы знаем. Как вычислить отображение

$inline$ (x, y) $inline$

$inline$ (?, ?) $inline$

$inline$ ? = x + sum_{Q ? S}(frac{v_Q}{(x-x_Q)} + frac{u_Q}{(x-x_Q)^2}) $inline$

$inline$ ? = y - sum_{Q ? S}(u_Qfrac{2y}{(x-x_Q)^3} + v_Q frac{y - y_Q}{(x-x_Q)^2} - frac{g_Q^xg_Q^y}{(x-x_Q)^2}) $inline$

Выход алгоритма Velu':
Коэффициенты

$inline$ A' $inline$

$inline$ B' $inline$

изогенной кривой и формула для отображения точек

$inline$ (x, y) $inline$

$inline$ (?, ?) $inline$

Пример 3 (Алгоритм Velu'. Как была получена изогения в Примере 2):

Вход :

$inline$ y^2 = x^3+x+1 $inline$

над полем

$inline$ GF(19) $inline$

и подгруппа

$inline$ C $inline$

: {

$inline$O$inline$

$inline$(2, 7)$inline$

$inline$(2, 12)$inline$

}

1. Отбрасываем точку на бесконечности
2. Точек четного порядка нет в

$inline$ C $inline$

нет
3. Выбираем для

$inline$R_+$inline$

точку

$inline$(2, 7)$inline$

. Точка

$inline$(2, 12)$inline$

– ей обратна ( т.к.7 = -12 mod 19 )
4. Множество

$inline$ S $inline$

= {

$inline$(2, 7)$inline$

}

Цикл из одного шага: (т.к. в

$inline$ S $inline$

только один элемент: точка

$inline$ Q = (2, 7) $inline$

$inline$ Q = (2, 7) $inline$

, ее координаты

$inline$ x_Q = 2, y_Q = 7 $inline$

$inline$ g_Q^x = 3*2^2 + 1 = 13 $inline$

$inline$ g_Q^y = -2*7 = -14 = 5 $inline$

$inline$ mod $inline$

$inline$ 19 $inline$

$inline$ v_Q = 2*13 = 26 $inline$

$inline$ mod $inline$

$inline$ 19 = 7 $inline$

$inline$ u_Q = 5^2 $inline$

$inline$ mod $inline$

$inline$ 19 = 6 $inline$

$inline$ v = 7 $inline$

$inline$ w = 6 + 2*7 = 20 = 1 $inline$

$inline$ mod $inline$

$inline$ 19 $inline$

$inline$ A' = A - 5v= 1 – 5*7 = - 34 $inline$

$inline$ mod $inline$

$inline$ 19 $inline$

$inline$ 4$inline$

$inline$ B' = B - 7w = 13$inline$

Осталось только посчитать рациональное отображение:

$inline$ (x, y) ? (?, ?) $inline$

$inline$ ? = x + frac{7}{x-2} + frac{6}{(x-2)^2} = frac{x^3-4x^2-8x-8}{x^2-4x+4}$inline$

Аналогично приводим формулу для ? к общему знаменателю:

$inline$ ? = frac{x^3y-6x^2y+5xy-6y}{x^3-6x^2-7x-8} $inline$

Выход:
Коэффициенты изогенной кривой:

$inline$ A' = 4, B' = 13 $inline$

Отображение

$inline$ (x, y) ? (?, ?) $inline$

(см. выше).

Вычисление изогений большой степени

Легко видеть, что в алгоритме Velu имеются подводные камни: он работает в цикле, пока не пройдется по всем точкам из множества

$inline$S$inline$

. Это значит, что число шагов будет больше половины порядка ядра изогении (подгруппы

$inline$ C $inline$

, которая подается на вход) и меньше порядка

$inline$ C $inline$

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

$inline$ C $inline$

имеет большой порядок #

$inline$ C $inline$

, но имеет определенную структуру: если #

$inline$ C $inline$

— степень небольшого числа

$inline$ l $inline$

, т.е.

$inline$ l^e $inline$

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

$inline$ l $inline$

по Velu' и одно скалярное умножение точки на число. В качестве

$inline$ l $inline$

обычно выбирают 2 или 3.

Обозначение: Кривую

$inline$E'$inline$

, изогенную

$inline$E$inline$

, полученную при помощи подгруппы

$inline$C$inline$

, вместо

$inline$ E$inline$

$inline$ C $inline$

, иногда гораздо удобнее обозначать при помощи точки

$inline$G$inline$

— генератора

$inline$C$inline$

$inline$ E/<$inline$

$inline$G$inline$

$inline$>$inline$

.

Пусть

$inline$G$inline$

— точка порядка

$inline$ l^e $inline$

. Необходимо вычислить изогению

$inline$ ?: E ? E/<$inline$

$inline$G$inline$

$inline$>$inline$

.
Разложим изогению

$inline$ ? $inline$

на последовательность из изогений, где каждая имеет степень

$inline$ l $inline$

$inline$ ?_{e-1}*?_{e-2}*...*?_{0} $inline$

$inline$ ?_0 : E, G_0 = G $inline$

$inline$ ?_i : E_{i+1} = E_i/<$inline$

$inline$l^{e-1-i}G_i$inline$

$inline$>$inline$

$inline$ G_{i+1} = ?_i( G_i )$inline$

Пример 4
Мы хотим вычислить изогению для циклической группы порядка

$inline$ l^4 $inline$

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

$inline$ l $inline$

и 3 раза умножим точку на число. Пусть

$inline$ G_0 $inline$

— генератор этой группы, точка порядка

$inline$ l^4 $inline$

$inline$ ?_{3}*?_{2}*?_{1}*?_{0} $inline$

$inline$ ?_0 : E_1 = E_0/<$inline$

$inline$l^{3}*G_0$inline$

$inline$ >$inline$

$inline$ G_1 = ?_0(G_0) $inline$

$inline$ ?_1 : E_2 = E_1/<$inline$

$inline$l^{2}*G_1$inline$

$inline$ >$inline$

$inline$ G_2 = ?_1(G_1) $inline$

$inline$ ?_2 : E_3 = E_2/<$inline$

$inline$l^{1}*G_2$inline$

$inline$ >$inline$

$inline$ G_3 = ?_2(G_2) $inline$

$inline$ ?_3 : E_4 = E_3/<$inline$

$inline$G_3$inline$

$inline$ >$inline$

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

$inline$ 2^{256} $inline$

и мы знаем ее генератор, то мы пройдем алгоритм за 256 шагов.

Практика: изогении между суперсингулярными кривыми

Напомним, что у двух изоморфных кривых одинаковый j-инвариант и для кривой

$inline$y^2 = x^3 + Ax + B $inline$

он равен

$inline$frac{4A^3}{4A^3+27B^2}$inline$

Из за того, что найти преобразование между изоморфными кривыми особой сложности не представляет, задача изогений по сути является задачей про нахождение изогений между различными классами изоморфных кривых (а каждый из этих классов можно представить в виде соответствующего j-инварианта).
Какие кривые представляют интерес для изогений? Ведь мы знаем, что существуют запрещенные семейства кривых для эллиптических Диффи-Хеллмана и ЭЦП: суперсингулярные, аномальные и гладкого порядка и.т.д. — для всех относительно легко решается задача ECDLP. Такие неприятные классы должны существовать и для изогений. Только тут ситуация совершенно иная, ведь трудная задача не ECDLP. Очевидно, что надо использовать кривые гладкого порядка, чтобы было больше подгрупп. Кроме того, в 2010 году исследователи из университета Ватерлоо выяснили, что использование обычных кривых небезопасно с «квантовой» точки зрения: был получен результат, который утверждал, что для криптосистем, использующих изогении безопасно использовать только суперсингулярные кривые. Напомним, что это кривые, у которых след Фробениуса t такой что t mod p = 0, где p — характеристика поля кривой (сам след Фробениуса связан с порядком группы кривой #

$inline$ E(GF(p^n))$inline$

и полем соотношением #

$inline$ E(GF(p^n)) = p^n + 1 - t $inline$

). Далее мы будем рассматривать только их.

Какое поле для кривой оптимальнее было бы использовать? Сразу напрашивается ответ — старое доброе простое поле

$inline$ GF(p) $inline$

. Но к сожалению, у суперсингулярных кривых над

$inline$ GF(p) $inline$

существует слишком мало разных j-инвариантов: ~

$inline$sqrt{p}$inline$

. Тогда как для поля

$inline$ GF(p^2) $inline$

, число j-инвариантов #

$inline$ S_{p^2} = lfloor p/12  floor + a $inline$

, где

$inline$a ? $inline$

{

$inline$1, 2, 3 $inline$

}

У таких кривых есть интересные свойства:
Граф изогений фиксированной степени — правильный. (т.е у каждой вершины имеется одинаковое число ребер)
Для любого простого числа

$inline$ l $inline$

, которое делит порядок группы точек кривой существует

$inline$ l+1 $inline$

изогений с ядром порядка

$inline$ l $inline$

. (т.е. существует

$inline$ l+1 $inline$

подгруппа порядка

$inline$ l $inline$

, при помощи которой можно получить изогению)

Пример 5 (пример и изображения графов — Dr. Fre Vercauteren)
Рассмотрим поле

$inline$ GF({241^2}) $inline$

Выберем неприводимый многочлен:

$inline$ x^2 - 3x +7 $inline$

Множество j-инвариантов будет таким:

$inline$ S_{241^2} $inline$

= { 93, 51w + 30, 190w + 183, 240, 216, 45w + 211, 196w +
105, 64, 155w + 3, 74w + 50, 86w + 227, 167w + 31, 175w + 237, 66w + 39, 8, 23w + 193, 218w + 21, 28, 49w + 112, 192w + 18 }
Их число #

$inline$ S_{241^2} $inline$

= 20

Для кривых порядка #

$inline$ E $inline$

= 57600 =

$inline$ 2^8*3^2*5^2 $inline$

:

Для изогении степени

$inline$ l = 2 $inline$

:
Каждая кривая имеет 3 изогении степени 2

Для изогении степени

$inline$ l = 3 $inline$

:
Каждая кривая имеет 4 изогении степени 3

Аналогично для

$inline$ l = 11 $inline$

.
Каждая кривая имеет 12 изогении степени 11. (Картинки нет — нарисовать, когда поеду в отпуск)

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

$inline$ E1 $inline$

$inline$ E2 $inline$

(т.е. зная два

$inline$j$inline$

-инварианта

$inline$ j1 $inline$

$inline$ j2 $inline$

), найти путь в графе изогений между ними. По сути — найти метод получения изогении между кривой c

$inline$ j1 $inline$

и кривой c

$inline$ j2 $inline$

Supersingular Isogeny Diffie-Hellman (SIDH)

Определение:
Если при умножении точки

$inline$P$inline$

кривой

$inline$E(GF(p^m))$inline$

при умножении на n получается точка на бесконечности, то такая точка называется точкой n-кручения (n-torsion point)
Подгруппа n-кручения (n-torsion subgroup)

$inline$ E[n] $inline$

$inline$ E[n] = $inline$

{

$inline$ P ? E(GF(p^m)) : n*P = O $inline$

}
Эта подгруппа состоит из точки на бесконечности и всех точек n-кручения.
Очевидно, что точкой n-кручения является точка, если ее порядок делит n без остатка.

$inline$ E[n] $inline$

изоморфна прямому произведению

$inline$(Z/nZ)?(Z/nZ)$inline$

при n взаимно простом с p. (т.е порядок

$inline$ E[n] $inline$

равен

$inline$ n^2 $inline$

)

Выбор поля

$inline$ GF(p^2) $inline$

для кривых для SIDH:
Пусть

$inline$ f $inline$

— небольшое число, а

$inline$ l_a, l_b$inline$

— небольшие простые числа.
При характеристике поля

$inline$ p = l_a^{e_a}*l_b^{e_b}*f±1 $inline$

порядок кривой

$inline$E$inline$

: #

$inline$E = (l^{e_a}*l^{e_b}*f)^2 $inline$

$inline$E[l^{e_a}] $inline$

содержит

$inline$l_a^{e_a - 1}(l_a+1)$inline$

циклических подгрупп порядка

$inline$l_a^{e_a}$inline$

Итак, пусть

$inline$ l_a = 2, l_b = 3$inline$

характеристика поля

$inline$ p = 2^{m}*3^{n}*f±1 $inline$

, а n и m подберем так, чтобы

$inline$ 2^{m} $inline$

приблизительно было равно

$inline$ 3^{n} $inline$

Подгруппы кручения

$inline$ E[2^m] $inline$

$inline$ E[3^n] $inline$

$inline$ E[p^2] $inline$

$inline$ E[2^m] $inline$

содержит

$inline$ 2^{m?1}*3 $inline$

циклических подгрупп порядка

$inline$2^m$inline$

$inline$ E[3^n] $inline$

содержит

$inline$ 3^{n?1}*4 $inline$

циклических подгрупп порядка

$inline$3^n$inline$

Выберем точки

$inline$ P_a, Q_a $inline$

— базис для

$inline$ E[2^m] $inline$

(т.е. при помощи комбинации

$inline$ x*P_a + y*Q_a$inline$

можно получить любую точку

$inline$ E[2^m] $inline$

) и точки

$inline$ P_b, Q_b $inline$

— базис для

$inline$ E[3^n] $inline$

Итак доменные параметры для SIDH (аналог доменных параметров для обычных эллиптических кривых):
кривая

$inline$ E $inline$

и два базиса {

$inline$ P_a, Q_a $inline$

} и {

$inline$ P_b, Q_b $inline$

}. Они известны Алисе, Бобу и злоумышленнику.

(Примечание:

$inline$ E_{ab} = E_{ba} $inline$

c точностью до изоморфизма: коэффициенты у кривых могут быть разные, но j-инвариант будет одинаковый)

Тот, кто начинает (Алиса) использует для генерации пары базис

$inline$ P_a, Q_a $inline$

.
Алиса генерирует случайные

$inline$ a1, a2: 0< a1, a2 < 2^m $inline$

(

$inline$ a1, a2 $inline$

оба не кратны 2)

$inline$ a1, a2 $inline$

— это закрытый ключ Алисы.
Затем она вычисляет вычисляет точку

$inline$G_a = a1*P_a + a2*Q_a$inline$

И вычисляет с ее помощью изогению

$inline$ ?A: $inline$

$inline$ E ? E_a = E $inline$

/ <

$inline$G_a$inline$

>,
после чего преобразует c помощью изогении

$inline$ ?A $inline$

базис Боба на кривую

$inline$ E_a $inline$

$inline$ ?A({P_b}), ?A({Q_b}) $inline$

Закрытый ключ Алисы:

$inline$ a1, a2 $inline$

Открытый ключ Алисы: кривая

$inline$ E_a $inline$

и точки

$inline$ ?A({P_b}), ?A({Q_b}) $inline$

Аналогичные шаги делает Боб (см. диаграмму):
Закрытый ключ Боба:

$inline$ b1, b2 $inline$

Открытый ключ Боба: кривая

$inline$ E_b $inline$

и точки

$inline$ ?B({P_a}), ?B({Q_a}) $inline$

Алиса отправляет открытый ключ Бобу
Боб вычисляет точку

$inline$ b1*?A({P_b}) + b2*?A({Q_b})$inline$

и с ее помощью
изогенную кривую

$inline$E_{ba} = E_a$inline$

$inline$b1*?A({P_b}) + b2*?A({Q_b})$inline$

>

Далее, Боб отправляет Алисе открытый ключ и Алиса подобным образом вычисляет кривую

$inline$ E_{ab}: $inline$

$inline$E_{ab} = E_b$inline$

$inline$a1*?B({P_a}) + a2*?B({Q_a})$inline$

>

Для получения общего секрета Алиса вычисляет j-инвариант от

$inline$E_{ab}$inline$

а Боб от

$inline$E_{ba}$inline$

Безопасность и размеры ключей

Для успешной атаки надо найти путь хотя бы на одном из графов (Алисы или Боба). Эта задача имеет разные степени сложности для классического и квантовых компьютеров:
Классическая сложность: Алиса

$inline$ sqrt{2^m} $inline$

, Боб

$inline$ sqrt{3^n} $inline$

Квантовая сложность: Алиса

$inline$ sqrt[3]{2^m} $inline$

, Боб

$inline$ sqrt[3]{3^n} $inline$

Поэтому:
Классический уровень безопасности =

$inline$ min (sqrt{2^m}, sqrt{3^n} ) ? sqrt[4]{p} $inline$

операций
Квантовый уровень безопасности =

$inline$ min ( sqrt[3]{2^m}, sqrt[3]{3^n} ) ? sqrt[6]{p} $inline$

операций

Размеры ключей:

Открытый ключ:
точки P и Q
коэффициенты A и B кривой

~ 8 *

$inline$ log_2(p) $inline$

бит
~ 6 *

$inline$ log_2(p) $inline$

бит (оптимизация: Costello, Crypto 2016 )

Длина характеристики поля = 768 бит:
768/6 = 128-битный квантовый уровень безопасности
768/4 = 192-битный классический уровень безопасности
Длина ключа 6

$inline$ log_2(p) $inline$

бит = 4608 бит = 576 байт

Длина характеристики поля = 1536 бит:
1536/6 = 256-битный квантовый уровень безопасности
1536/4 = 384-битный классический уровень безопасности
Длина ключа 6

$inline$ log_2(p) $inline$

бит = 9216 бит = 1152 байт

Производительность

Лучшие результаты для 128-битного квантового уровня безопасности (характеристика поля

$inline$ p = 2^{372}3^{239} - 1$inline$

т.е

$inline$p$inline$

$inline$2^{768} $inline$

):

Для Intel Haswell на частоте 3,4 Ггц:
вычисляется за ~100 млн. тактов для одной из сторон (Алисы или Боба)
(используются кривые Монтгомери и проективные координаты)

Для чипа ARM7 Beagle Board Black Cortex-A8 на частоте 1 Ггц:
время выполнения — 1,5 сек. Если задействовать SIMD-инструкции NEON, то 0,2 сек.

Литература:

1. «Public-Key Cryptosystem Based on Isogenies», Alexander Rostovtsev, Anton Stolbunov, 2006

2. «Constructing elliptic curve isogenies in quantum subexponential time» Andrew M. Childs, David Jao, Vladimir Soukharev, 2010

3. «Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies» David Jao, Luca De Feo, 2011

4. «Efficient algorithms for supersingular isogeny Diffie-Hellman» Craig Costello and Patrick Longa and Michael Naehrig, 2016

5. «NEON-SIDH: Efficient implementation of supersingular isogeny Diffie-Hellman Key Exchange protocol on ARM» R. Azarderaksh, D. Jao, 2016

6. «Mathematics of Public Key Cryptography» Steven D. Galbraith, Cambridge University Press

Источник: habrahabr.ru

Постквантовая реинкарнация алгоритма Диффи-Хеллмана: вероятное будущее (изогении)

Комментарии: