Математические основы защиты информации. Ишмухаметов Ш.Т - 91 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 3. Эллиптические кривые 92
эллиптической кривой более громоздкие, чем в конечных полях. А это
значит, что для произвольной точки G вычисление множителя k такого, что
G = kP , где P генератор точек кривой, т.е. решение проблемы, аналогичной
вычислению дискретного логарифма в конечных полях, решается более
трудоемко. Поэтому на группах точек эллиптических кривых можно
строить криптографические протоколы типа протокола Диффи-Хеллмана
выработки общего секретного ключа, электронной цифровой подписи или
шифрования информации, выбирая размерность ключа (определяемую
здесь размерностью поля F
p
k
) меньшей длины. Было подсчитано, что длина
ключа в 160 бит на эллиптических кривых соответствует ключу длины 1024
бита в методе RSA (см.[54], с.132).
5.5. Алгоритм факторизации Ленстры ECF
Будем обращаться к методу Ленстры факторизации на эллиптических
кривых, используя аббревиатуру ECF (Elliptic Curves Factorization). Пусть
n – составное число. Этот метод имеет много общего с (p − 1)–методом
Полларда, и производительность метода Ленстры зависит только от размера
наименьшего делителя n, а не от размерности n.
Рассмотрим множество Z
n
= {0, 1, 2, ..., n−1} как основное множество
для координат точек эллиптической кривой EC(Z
n
) : y
2
= x
3
+ ax + b. В
строгом математическом смысле эта кривая не будет эллиптической кривой
(Ленстра назвал такую кривую псевдокривой), т.к Z
n
не является полем,
и, значит, в нем не всегда выполнимы операции нахождения обратного
элемента, необходимые для нахождения суммы точек кривой. Однако
Ленстра заметил, что невозможность вычисления суммы двух точек P (x
1
, y
1
)
и Q(x
2
, y
2
) означает, что разность первых координат x
2
− x
1
должны
равняться 0 по модулю одного из делителей n, тогда, вычисляя наибольший
общий делитель Н.О.Д. (n, x
2
− x
1
), мы легко найдем искомый делитель.
Суть алгоритма Ленстры заключается в выборе на псевдокривой
EC(Z
n
) произвольной базовой точки P
0
и домножении ее на всевозможные
Глава 3. Эллиптические кривые                                            92

эллиптической кривой более громоздкие, чем в конечных полях. А это
значит, что для произвольной точки G вычисление множителя k такого, что
G = kP , где P генератор точек кривой, т.е. решение проблемы, аналогичной
вычислению дискретного логарифма в конечных полях, решается более
трудоемко. Поэтому на группах точек эллиптических кривых можно
строить криптографические протоколы типа протокола Диффи-Хеллмана
выработки общего секретного ключа, электронной цифровой подписи или
шифрования информации, выбирая размерность ключа (определяемую
здесь размерностью поля Fpk ) меньшей длины. Было подсчитано, что длина
ключа в 160 бит на эллиптических кривых соответствует ключу длины 1024
бита в методе RSA (см.[54], с.132).


5.5. Алгоритм факторизации Ленстры ECF
      Будем обращаться к методу Ленстры факторизации на эллиптических
кривых, используя аббревиатуру ECF (Elliptic Curves Factorization). Пусть
n – составное число. Этот метод имеет много общего с (p − 1)–методом
Полларда, и производительность метода Ленстры зависит только от размера
наименьшего делителя n, а не от размерности n.
      Рассмотрим множество Zn = {0, 1, 2, ..., n−1} как основное множество
для координат точек эллиптической кривой EC(Zn ) : y 2 = x3 + ax + b. В
строгом математическом смысле эта кривая не будет эллиптической кривой
(Ленстра назвал такую кривую псевдокривой), т.к Zn не является полем,
и, значит, в нем не всегда выполнимы операции нахождения обратного
элемента, необходимые для нахождения суммы точек кривой. Однако
Ленстра заметил, что невозможность вычисления суммы двух точек P (x1 , y1 )
и Q(x2 , y2 ) означает, что разность первых координат x2 − x1 должны
равняться 0 по модулю одного из делителей n, тогда, вычисляя наибольший
общий делитель Н.О.Д. (n, x2 − x1 ), мы легко найдем искомый делитель.
      Суть алгоритма Ленстры заключается в выборе на псевдокривой
EC(Zn ) произвольной базовой точки P0 и домножении ее на всевозможные

Страницы