Lecture_09
.pdf
Эллиптические кривые над вещественными числами приводит нас к проблеме округления (тексты представляются целыми числами)
Поэтому в криптографии используются только кривые над конечными полями, т.е. координаты точек кривой принадлежат конечному полю
В криптографии рассматривается два вида эллиптических кривых:
над конечным полем - кольцо вычетов по модулю простого числа p
над полем (2 ) - бинарное конечное поле. В этом случае элементы поля могут быть легко представлены в виде n-битных кодовых слов, это позволяет увеличить скорость аппаратной реализации эллиптических алгоритмов
GF(p)
Элементами данной эллиптической кривой являются пары неотрицательных целых чисел, которые меньше р (p>3) и удовлетворяют частному виду эллиптической кривой
2 = (3+ax + )
Такую кривую будем обозначать ( , ). При этом числа а и b должны быть меньше р и должны удовлетворять условию (43 +
( ,)
Р + 0 = Р; P+Q=Q+P (коммут.); (P+Q)+R=P+(Q+R) (ассоциат.)
Если Р = (x,y), то Р + (x,-y) = 0. Точка (x,-y) является отрицательным значением точки Р и обозначается -Р. Точка -Р лежит на эллиптической кривой, т.е. принадлежит Ep (a,b).
Если Р = ( 1, 1) и Q = ( 2, 2), то P + Q = ( 3, 3) определяется по
следующим формулам: |
|
|
|
|
||
3 = (2−1 − 2 ) |
3 |
= ( 1 − 3 |
− 1) |
|||
= |
(2 − 1)/ 2 |
− 1 , |
≠ |
|||
( 32 |
+ )/2 , |
= |
||||
|
||||||
|
1 |
|
|
1 |
|
|
- угловой коэффициент секущей, проведенный через точки
P и Q
Задана кривая 13(1,1)
Проверить принадлежность кривой точек P(4, 2), R(2,5) и Q(7,0)
Если две точки принадлежат кривой, то вычислить их сумму
S( 3, 3)
Проверить принадлежность суммарной точки S( 3, 3) кривой 13(1,1)
Даны точки P и Q на эллиптической кривой Ep (a,b). Необходимо найти коэффициент k < p такой, что P = k x Q
Относительно легко вычислить P по данным k и Q, но вычислительно трудно вычислить k, зная P и Q
Получатель выбирает кривую , , точку е1 на кривой, выбирает секретной число d и вычисляет еще одну точку 2 = × 1
Открытый ключ |
, |
, |
|
|
|
1, |
2 |
Отправитель сопоставляет открытому тексту точку P на кривой и создает шифровку 1, 2
Получатель выполняет расшифровку:
2 − ( × 1)=+ × × 1 − × × 1 =
Возведение в степень в алгоритме Эль-Гамаля заменено умножением точки на константу в модели
Умножение в алгоритме Эль-Гамаля заменено сложением точек в модели
Инверсия в алгоритме Эль-Гамаля — мультипликативная инверсия заменяется аддитивной инверсией точки на кривой
Вычислительные затраты, поэтому, обычно меньше в модели
Для того же самого уровня безопасности (вычислительные затраты на атаки) модуль p, может быть меньшим в эллиптической системе (ECC), чем в RSA. Например, ECC с модулем, состоящим из 160 битов, может обеспечить тот же уровень безопасности, как RSA с модулем 1024 битов