Научная литература
booksshare.net -> Добавить материал -> Криптография -> Венбо Мао -> "Современная криптография" -> 80

Современная криптография - Венбо Мао

Венбо Мао Современная криптография. Под редакцией Клюшиной Д.А. — М. : Издательский дом Вильямс, 2005. — 768 c.
ISBN 5-8459-0847-7
Скачать (прямая ссылка): sovremennaya_kriptografiya.djvu
Предыдущая << 1 .. 74 75 76 77 78 79 < 80 > 81 82 83 84 85 86 .. 311 >> Следующая

Некоторые приложения закона сложения: (3,0)"+"(3,0) = О, (3,0)"+"(4,1) = = (1,2) и (1,2)"+"(152) = (0,2). Читатели могут сами убедиться, что точка (1,2) является элементом, порождающим группу. Следовательно, группа F(F?) является циклической. ?
Группы, порожденные эллиптической кривой Е, введены в простейшем случае — над простым полем Fp при р > 3. В общем случае группу Е можно определить над полем ?д, где q — простая степень. Случаи р = 2 и р = 3 немного сложнее, но принципы доказательства остаются неизменными. Пытливые читатели могут найти интересующую их информацию в книге [272].
5.5.2 Умножение точек
С этого момента мы больше не будем брать символы + и — в кавычки. Пусть m — целое число, а Р 6 Е. Введем следующее обозначение.
[т]Р
Р + Р Ч-----h Р для m > 0,
т
О, для m = 0,
[—т] — Р, для т < 0.
Глава 5. Алгебраические основы
211
Вычисление величины [т]Р (результата га-кратного выполнения групповой операции в любой аддитивной группе) является аналогом возведения в степень в мультипликативной группе. Эта операция описывается следующим алгоритмом.
Алгоритм 5.2. Умножение точек эллиптической кривой ВВОД: точка Р € Е; целое число га > 0; ВЫВОД: [т]Р.
EC_Multiply(F, га)
1. ifm = 0remrn(C>).
2. if ra(mod 2) = 0 retom(EC_Multiply(F + F,ra-=-2));
(* -г- означает целочисленное деление, т.е. га ч- 2 = [т/2] *).
3. return(P + EC_Multiply(F + F, га 2)).
Например, вычисляя величину EC_Multiply(F, 14), алгоритм 5.2 выполняет четыре рекурсивных вызова.
EC_Multiply(F, 14) =
= EC_exp(F + F, 7) = (на шаге 2)
= [2] F + EC_Multiply([2] F + [2] F, 3) = (на шаге 3)
= [2]F + [4]F + EC_Multiply([4]F + [4]F, 1) = (на шаге 3)
= [2]F + [4]F + [8]F + EC_Multiply([8]F + [8]F, 0) = (на шаге 3)
= P]P + [4]F + [8]F + О (на шаге 1)
Результат равен [14]F.
Поскольку т « р и вычисления по формулам (5.5.4) и (5.5.5) предусматривают возведение в квадрат величин порядка р, временная сложность алгоритма 5.2 имеет порядок Os((logp)3). Следует заметить, что алгоритм 5.2 не использует никаких свойств поля, которому принадлежит точка Р. По этой причине его нельзя считать эффективным. Этот алгоритм представляет собой всего лишь краткое описание процесса умножения точки. Более эффективные алгоритмы умножения точки, использующие предварительные вычисления и особые свойства поля, изложены в работе [35].
5.5.3 Дискретное логарифмирование на эллиптической кривой
Операция, обратная к умножению точки, определяет по заданной паре [F, [т]Р] целое число т. Она имеет совершенно иную природу. В литературе эта операция называется дискретным логарифмированием на эллиптической кривой
212
Часть II. Математические основы
(elliptic-curve discrete logarithm problem — ECDLP). Считается, что задача ECDLP является трудноразрешимой (неразрешимой с вычислительной точки зрения), если порядок точки Р — большое простое число. Теорема Хассе (Hasse) утверждает, что
#E{Fg) = q + l-t при - ^ t ^ 2y/q. (5.5.6)
Здесь число t называется "следом Фробениуса" ("trace of Frobenius") числа q. Отсюда следует, что числа #Е(?д) и q имеют одинаковый порядок. Для кривой, определенной над полем ?д (общий случай), легко сконструировать большое простое число р, размер которого немного меньше числа q, такой что группа E(?q) содержит подгруппу порядка р. Временная сложность наилучшего из всех известных алгоритмов решения задачи ECDLP имеет порядок 0(y/q) (поскольку pra q). Этот результат достигнут путем применения лобового поиска на основе парадокса дней рождений. Он относится к дискретному логарифмированию в любой абелевой группе, размер которой имеет порядок q. Действительно, Л-метод Полларда (раздел 3.6.1) можно легко модифицировать для решения ECDLP. Следовательно, можно утверждать, что решение задачи ECDLP, порядок сложности которой равен 0(x/q), вообще не является решением, поскольку совершенно не учитывает структуру группы, рассматриваемой в задаче.
Существуют арифметические методы дискретного логарифмирования в конечном поле (см. определение 8.2) — методы индексного исчисления. Временная сложность таких методов дискретного логарифмирования в конечном поле ?q имеет субэкспоненциальный порядок subexp(c), определенный выражением (8.4.2).
Выражение 0(y/q) экспоненциально зависит от порядка о. При одних и тех же исходных данных выражение 0(y/q) представляет собой функцию, которая возрастает намного быстрее, чем функция subexp(c). Это значит, что при решении задачи ECDLP размер исходного поля можно уменьшить, не увеличивая временной сложности решения. Как правило, в задаче ECDLP рассматривается число q Ft 2160. Это позволяет повысить уровень сложности лобового поиска до 280. Для того чтобы получить аналогичный порядок сложности при вычислении дискретного логарифма в конечном поле необходимо, чтобы число q в субэкспоненциальном выражении (8.4.2) имело порядок 21000. Следует, однако, заметить, что прогресс вычислительных технологий вынуждает постоянно повышать порядок числа о. Поскольку асимптотическое поведение величин ^Jq и subexp(c) резко отличается друг от друга, в группе точек эллиптической кривой число q может расти намного медленнее, чем в произвольном конечном поле.
Предыдущая << 1 .. 74 75 76 77 78 79 < 80 > 81 82 83 84 85 86 .. 311 >> Следующая

Реклама

Морской круиз Вокруг Европы

круиз на современном комфортабельном корабле

mosturflot.ru

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed