Криптографические протоколы на эллиптических кривых
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?вского-Якоби позволяет сбалансировать операции удвоения точки и сложения двух точек. Мы получаем небольшой выигрыш в скорости сложения и платим за это проигрышем в скорости удвоения. Однако схожий подход может быть использован и для того, чтобы дополнительно ускорить операцию удвоения за счет еще большего замедления операции сложения. Для этого в системе координат Якоби добавим четвертую координату (X, Y, Z, aZ4). Возьмем две проективные точки P1 = (X1, Y1, Z1, aZ14), P2 = (X2, Y2, Z2, aZ24), принадлежащие нашей кривой. Тогда координаты точки P3:
P3 = P1 + P2 = (X3, Y3, Z3, aZ34)
вычисляются по следующим формулам:
Если P1 ? P2 ,
u1 = X1Z22, u2 = X2Z12,
s1 = Y1Z23, s2 = Y2Z13,
h = u2 - u1, r = s2 - s1,
X3 = -h3 - 2u1h2 + r2,
Y3 = -s1h3 + r(u1h2 - X3),
Z3 = Z1Z2h,
aZ34 = aZ34.
Если P1 = P2 (удвоение точки):
s = 4X1Y12, u = 8Y14,
m = 3X12 + (aZ14),
X3 = -2s + m2,
Y3 = m(s - X3) - u,
Z3 = 2Y1Z1,
aZ34 = 2u(aZ14).
При P1 = ?P2 получаем P3 = O.
Для этой системы координат получаем:
t(Jm + Jm) = 13M + 6S, (2Jm) = 4M + 4S.
Таким образом, мы получили систему координат, в которой очень выгодно производить операцию удвоения точки (при этом на кривую не накладывается никаких ограничений). Однако операция сложения в данной системе координат требует еще больше времени, чем в обычной системе координат Якоби. Рассмотрим далее метод, который позволит нам использовать преимущества различных систем координат.
Смешанные координаты
Из изложенной выше теории можно сделать вывод, что на данный момент не обнаружено универсальной системы координат. Некоторые системы координат позволяют быстро производить удвоение точки, другие - сложение двух точек. Однако при реализации алгоритмов на эллиптических кривых вовсе не обязательно использовать только одну систему координат. Если нам требуется складывать различные точки, можно использовать одну систему координат, а если нужно производить удвоения точки - другую. При этом в некоторых случаях мы можем даже складывать точки, которые представлены в разных системах координат. Рассмотрим пример использования этого метода.
Будем строить алгоритм умножения точки эллиптической кривой P на число k. Возьмем в качестве базы алгоритм, в котором k представляется в NAF (Non-adjacent form), и читается справа налево. На каждом шаге алгоритма происходит удвоение точки P и, возможно, сложение точки P с результирующей точкой P*.
Добавим теперь в этот алгоритм использование смешанных координат. Удвоение точки P каждый раз будем производить в модифицированной системе координат Якоби, то есть в самой выгодной для этого системе координат. Теперь нам нужно подобрать такую систему координат X, которая бы позволяла производить сложение вида Jm + X = X и при этом затраты на эту операцию были бы минимальными. На роль такой системы подходит обычная система координат Якоби. При этом для сложения вида Jm + J = J не требуется выполнять никаких преобразований координат (четвертая координата Jm просто игнорируется). Затрачивать это сложение будет столько же операций, сколько и сложение вида J + J = J. Таким образом, мы можем использовать преимущество модифицированной системы координат Якоби (минимальные затраты операций на удвоение точки) и не расплачиваться за это существенным замедлением операции сложения двух точек. Подробное описание алгоритма:
Вход: точка P = (X1 : Y1 : Z1) в системе координат Якоби, лежащая на кривой y2 = x3 + ax + b и целое число k > 0.
Выход: kP = (Xk : Yk : Zk) в системе координат Якоби.
Алгоритм: 1. P* < (1, 1, 0); T < (X1 : Y1 : Z1 : aZ14)
2. Пока k > 1 выполнять:
.1 Если k mod 2 = 1 то P* = P* + T.
иначе P* = P* - T.
.2 k = k/2
.3 T = 2T
3. P* = P* + T
Вернуть: P*
В данной работе реализованы операции сложения и удвоения точек в системе координат Якоби (метод pointAddJacobi класса eCurve), операция удвоения точки в модифицированной системе координат Якоби (метод pointDoubleJacobiM класса eCurve) и алгоритм умножения точки на число, описанный выше (метод pointMultiplyModifie класса eCurve). Также написана программа, позволяющая увидеть, какое преимущество в скорости дает использование в этом алгоритме проективных координат (test.java, метод compModStd).
Сравнение алгоритмов производилось для эллиптических кривых над полями характеристик p длины 192, 224, 256, 384, 521 бит (то есть те значения длины p, которые используются в стандарте NIST). Все параметры кривой, точка P и большое число k генерировались случайным образом. В результате сравнения были получены следующие результаты:
Длина p192 бита224 бита256 бит384 бита521 битt(A), мс 14.382 19.172 28.668 78.562 175.43t(Am), мс 8.257 10.564 15.74 42.888 106.46t(A) / t(Am) 1.742 1.815 1.821 1.832 1.648
где t(A) - время работы алгоритма, который не использует проективные координаты;
t(Am) - время работы алгоритма, который использует смешанные координаты (J и Jm).
Таким образом, использование смешанных координат увеличивает скорость основных операций эллиптических кривых в ~1.7-1.8 раз. При этом не накладывается никаких ограничений на параметры кри?/p>