<< Предыдущая

стр. 10
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Обратите внимание, что здесь нет ни одной операции деления, кро­
ме деления на 2, которая легко заменяется умножением на заранее
вычисленное число 2˜^ (modp).
Удвоение точек (Хз,Уз,^з) = [2](A'i,yi,Zi) упрощается с помо­
щью формул
X^ = 3Xf + aZf, Zs = 2YiZi,
А2 = 4Х1УД ХЗ = А 2 - 2 А 2 ,

Аз = 8УД Уз = А 1 ( А 2 - Х з ) - А з .
2.5. Сэюатие точек

2.4.2. Четная характеристика
Уравнение эллиптической кривой над полем четной характеристики
записывается в виде
у2 + XYZ = Х^ + a2X^Z'^ + aeZ^.
Сложение точек
(Хз,Уз,^з) = {Xi,Yi,Zi) + {X2,Y2,Z2)
В этом случае осуществляется по рецепту:

Ai = X1Z2J Л2 = X2Z1,
A3 = Ai + А2, А4 = Y1Z2,
А5 = 5^2^17 Аб = А4 Н- Аз,
Xj = Z1A3, Ag = Аб-Х'2 + A7I2)
Za = A7Z27 А9 = Аб + Zs^,
Xs = a2Zl + АбАд + \ l Уз = A9X3 + AgA?.
И, наконец, координаты удвоенной точки определяются по правилу:
Z^ = X^Zl Xз = № + a 6 Z 2 ) ^
\ = Z^ + Xl + YiZi, Уз = XfZ^ + XXs.
Итак, в обоих интересных случаях — при большой и четной харак­
теристиках поля — мы исключили дорогостоящую операцию деле­
ния.


2.5. Сжатие точек
Во многих криптографических протоколах возникает необходимость
хранить в памяти или передавать по сети отдельные точки элли­
птической кривой. В аффинных координатах это можно сделать с
помощью двух элементов поля: координат х и у. Однако экономнее
применять так называемую технику сжатия точек.
Метод сжатия точек работает благодаря тому, что уравнение
кривой в аффинных координатах при фиксированном значении х
превращается в квадратное уравнение относительно координаты у.
Поэтому каждому возможному значению координаты х точки кри­
вой соответствует не более двух значений координаты у. Значит,
вместо двух координат для идентификации точки кривой можно
хранить в памяти компьютера только координату х и еще некий
Глава 2, Эллиптические кривые

двоичный параметре 6, сообщающий о том, какое именно значение
координаты у нужно брать. Остается только решить, как вычислять
параметр b и как по нему и данному х восстановить у-координату
нужной точки.

2 . 5 . 1 . С л у ч а й болыыой х а р а к т е р и с т и к и поля
Заметим, что если р > 2, то квадратные корни ±(5 из элемента
а € Fp представляются натуральными числами разной четности из
промежутка 1, . . . , р — 1, поскольку
—/3 = р — ^ (modp).
Таким образом, в качестве параметра b можно выбрать четность
у-координаты соответствующей точки. Покажем теперь, как вос­
становить полную информацию о координатах точки по паре (ж, Ь).
Сначала вычисляется^
/3 = ух^ + ах -\-Ь (modp),
а затем переменной у присваивают значение /3, если четность /3 со­
впадает с четностью Ь, и р — /3, когда четности разные. Если же
оказалось, что ^9 = О, то, не обращая внимания на параметр 6, мож­
но положить у = 0.
В качестве примера рассмотрим кривую
Е: Y^ = Х^-\-Х-{-3
над полем F j . Для представления каждой из ее точек (4,1) и (4,6) в
двоичной системе счисления нам потребуется шесть разрядов:
{Ob 100,06001) и (06100,06110),
в то время как при использовании метода сжатия точек всего че­
тыре:
(06100,061) и (06100,060).

В реальных криптографических протоколах получается более
существенная экономия компьютерной памяти. Рассмотрим, напри­
мер, ту же кривую, но над полем Fp с
р = 1125 899 906 842 679 = 2^^ + 55.

^Не путать с коэффициентом Ь в уравнении (2.3). — Прим. перев.
^Напомним, что кривая в случае большой характеристики поля определяется
уравнением (2.3). — Прим. перев.
2.5. Cotcamue точек

На ней есть точка с координатами
(1125 899 906 842 675,245 132 605 757 739),
для записи которой нам потребовалось 102 разряда. При сжатии
информации эту точку можно представить в виде
(1125 899 906 842 675,1),
где использовано только 52 разряда.

2.5.2. Четная характеристика
В случае четной характеристики необходимо проявить больше изо­
бретательности. Предположим, что нам дана точка Р(а;, у) на элли­
птической кривой
F^ + Х Г = Х^ + а2Х2 + а^. (2.5)
Если у = О, то можно положить 6 = 0. в противном случае вычисля­
ют Z = у/х и присваивают переменной b самый младший двоичный
разряд числа z. Для восстановления у по данной паре (ж, Ь) в случае
а; 7^ О вычисляют
а = ж + а2 + -5"
и обозначают через ^ одно из решений уравнения
z'^ -h Z = а.
Если наименьший двоичный разряд числа /3 совпадает с 6, то у = ж/З.
В противоположной ситуации у = х{/3 -i-l).
Для объяснения того, почему этот метод правильно восстанавли­
вает ^/-координату точки, напомним, что координаты (ж, у) точки
Р — решение уравнения (2.5). Поэтому пары (х^у/х) и {х^1 + у/х)
удовлетворяют соотношению

Z^ + Z = X^a2 + ^.

Краткое содержание главы

- Эллиптическая кривая над конечным полем — еш;е один при­
мер конечной абелевой группы. Существует очень много та­
ких групп, поскольку мы вольны в выборе как коэффициентов
кривой, так и поля, над которым она определена.
- В криптографии необходимо уметь вычислять порядок груп­
пы. Хотя это делается с помощью сложного алгоритма, о ко-
Глава 2. Эллиптические кривые

тором здесь не рассказывалось, вычисления занимают полино­
миальное время.
Как правило, суперсингулярные и аномальные кривые не ис­
пользуются в криптографических приложениях.
Скорость алгоритмов, реализуюш;их групповой закон на кри­
вой, можно увеличить, если использовать проективные коор­
динаты.
Для увеличения пропускной способности и экономии памяти
координаты точки эллиптической кривой (ж, у) успешно сжи­
маются до X и отдельного бита Ь. Полная информация восста­
навливается также довольно эффективно.

Дополнительная литература
Тем, кто хочет аккуратно выучить общую теорию эллиптических
кривых, можно порекомендовать учебник Сильвермана (предназна­
ченный студентам математических факультетов). Интересуюш;иеся
лишь криптографическими приложениями эллиптических кривых и
соответствующими алгоритмами могут просмотреть книгу Блэка,
Сироуси и Смарта.
I. F. Blake, G. Seroussi and N. P. Smart. Elliptic Curves in Cryptography.
Cambridge University Press, 1999.
J.H. Silverman. The Arithmetic of Elliptic Curves, Springer-Verlag,
1985.

Контрольные вопросы
2.1.1. Когда эллиптическая кривая особа?

2.1.2. Что означает совпадение j-инвариантов у двух эллиптиче­
ских кривых?

2.1.3. Опишите метод хорд и касательных и объясните, как с его
помощью реализуется групповой закон на эллиптической кри­
вой.

2.1.4. Что такое след отображения Фробениуса, и какому неравен­
ству он удовлетворяет?

2.1.5. В каком случае эллиптическую кривую называют аномаль­
ной?

2.1.6. Для чего нужны проективные координаты?
2.5. Сжатие точек

2.1.7. Объясните, как сжатие точек экономит память и увеличива­
ет скорость при передаче точек эллиптической кривой.

Лабораторные работы
2.2.1. Создайте электронную библиотеку программ, складывающих и
удваивающих точки эллиптической кривой по модулю р.

2.2.2. Расширьте Вашу библиотеку, включив в нее программы ра­
боты с проективными координатами, сжимающие и восста­
навливающие точки.

Упражнения
2.3.1. Выведите формулы леммы 2.2 из геометрического описания
группового закона.

2.3.2. Пусть Е — эллиптическая кривая, заданная уравнением


над полем характеристики р > 3. Опишите возможные точки
порядка три^ на кривой Е.

2.3.3. Покажите, что кривые
Е: У^ = X^ + aX + 6 и Е': Y'^ = Х^ + ad^X+ bS,
определенные над полем if, изоморфны над алгебраическим
замыканием К. Когда они будут изоморфны над исходным
полем К1




^То есть точки Р, удовлетворяющие условию [3]Р = О. — Прим. перев.
ЧАСТЬ II


СИММЕТРИЧНОЕ
ШИФРОВАНИЕ



Кодирование в большинстве случаев опирается на блочные и группо­
вые шифры, которые служат типичными примерами симметричных
алгоритмов шифрования. Кроме того, исторические (т. е. использо­
вавшиеся до 1960 г.) шифры, симметричные по своей природе, слу­
жат основой многих современных криптосистем.
Главный недостаток симметричного шифрования связан с про­
блемой распределения секретных ключей между пользователями.
В следуюш;их главах будет рассказано о теории и практике симме­
тричных криптосистем, но сначала мы познакомимся с докомпью­
терными шифрами.
ГЛАВА 3
ИСТОРИЧЕСКИЕ
ШИФРЫ

Цели главы
• Рассказать о некоторых докомпьютерных шифрах, таких, как
шифр Цезаря, шифр замены и машине «Энигма».
• Показать ненадежность этих шифров ввиду наследования ши-
фротекстом статистики подлежаш;его языка.
• Ввести понятия замены и перестановки как основных компо­
нентов шифра.
• Описать несколько атак на шифры, например, атаку с выбо­
ром открытого текста.


3.1. Введение
Алгоритм шифрования (или шифр) — это перевод открытого тек­
ста в текст зашифрованный (или шифротекст, шифрограмму, кри­
птограмму) с помощью секретного ключа. Этот процесс называют
шифрованием. Мы будем писать


где т — открытый текст^ Е — шифрующая функция, к — сек­
ретный ключ и С — шифротекст.
Обратный процесс называют расшифрованием и пишут
m = Dk{C).
Заметим, что алгоритмы шифрования и расшифрования Е и D от­
крыты, и секретность исходного текста т в данном шифротексте С
зависит от секретности ключа к. Обе части этого процесса исполь­
зуют один и тот же ключ, в связи с чем такие алгоритмы принято
называть симметричными криптосистемами, или криптосистема­
ми с секретным ключом, Суш;ествуют алгоритмы шифрования, за­
висящие от двух разных ключей. Первый из них открыт и нужен для
шифрования, в то время как второй — секретный и употребляется
Глава 3. Исторические шифры


при восстановлении текста из шифровки. Эти последние криптоси­
стемы называются асимметричными^ или криптосистемами с от­
крытым ключом. Мы их будем изучать в следующих главах.
Стороны, обменивающиеся шифрованной информацией, обычно
обозначаются Л и Б . Довольно часто, однако, употребляют более
дружественные имена: Алиса и Боб. Но не следует думать, что сто­
роны, участвующие в процессе, обязательно люди. Используя эти
имена, мы вполне можем описывать обмен секретной информацией
между двумя автономными механизмами. Подслушивающей сторо­
не, «плохой девочке», которая взламывает шифротекст, обычно дают
имя Ева.
В этой главе мы познакомимся с несколькими ранними шифра­
ми, применявшимися для защиты информации в докомпьютерную
эпоху. Мы покажем, что эти шифры легко взламываются с помо­
щью статистических исследований языка, на котором они написа­
ны (такой язык принято называть подлежащим), в нашем случае
английского^. В главе 4 мы обсудим связь между стойкостью ши­

<< Предыдущая

стр. 10
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>