Применение эллиптических кривых в криптографии. Жданов О.Н - 17 стр.

UptoLike

ВУЗ: 

СибГАУ | Красноярск

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

Рубрика: 

Однако такое сведение полезно, лишь если степень k расширения мала. Фактически
единственный вид эллиптических кривых, для которых
k мало, – это так называемые «су-
персингулярные» эллиптические кривые, наиболее известными примерами которых явля-
ются кривые вида
azxy +=
32
над полем
q
F
, характеристики
)4(mod1−≡p
и кривые ви-
да
bxy +=
32
над полем
q
F , когда )3(mod1
−
≡
p . Как правило, эллиптические кривые не
являются суперсингулярными. Для них такое сведение почти никогда не приводит к суб-
экспоненциальным алгоритмам.
Таким образом, основные преимущества криптосистем на эллиптических кривых
заключаются в том, что неизвестны субэкспоненциальные алгоритмы вскрытия этих сис-
тем, если в них не используются суперсингулярные кривые, а также кривые, порядки ко-
торых делятся на большое простое число.
Теперь мы опишем аналоги некоторых широко распространенных систем с откры-
тым ключом, основанные на задаче дискретного логарифмирования на эллиптической
кривой, определенной над конечным полем
q
F
.
Аналог ключевого обмена Диффи-Хеллмана.
Предположим, что абоненты А и Б хотят договориться о ключе, которым будут
впоследствии пользоваться в некоторой классической криптосистеме. Прежде всего, они
открыто выбирают какое-либо конечное поле
q
F и какую-либо эллиптическую кривую Е
над ним. Их ключ строится по случайной точке
Р на этой эллиптической кривой. Если у
них есть случайная точка
Р, то, например, ее x-координата дает случайный элемент
q
F ,
который можно затем преобразовать в
r-разрядное целое число в р-ичной системе счисле-
ния (где
r
pq = ), и это число может служить ключом в их классической криптосистеме
(здесь мы пользуемся словом «случайный» в неточном смысле; мы лишь хотим сказать,
что выбор из некоторого большого множества допустимых ключей произволен и непред-
сказуем). Они должны выбрать точку
Р так, чтобы все их сообщения друг другу были от-
крытыми и все же никто, кроме них двоих, ничего бы не знал о
Р.
Абоненты (пользователи) А и Б первым делом открыто выбирают точку
В
∈
Е в
качестве «основания»;
B играет ту же роль, что образующий q в системе Диффи-Хеллмана
для конечных полей. Мы, однако, не требуем, чтобы
B была образующим элементом в
группе точек кривой
E. Эта группа может и не быть циклической. Даже если она цикличе-
ская, мы не хотим тратить время на проверку того, что
В – образующий элемент (или даже
на нахождение общего числа
N точек, которое нам не понадобится в последующем). Нам
хотелось бы, чтобы порожденная
В подгруппа была большой, предпочтительно того же
порядка величины, что и сама
Е. Позже мы обсудим этот вопрос. Пока что предположим,
что
В – взятая открыто точка на Е весьма большого порядка (равного либо N, либо боль-
шому делителю
N).
Чтобы образовать ключ, А вначале случайным образом выбирает целое число
а,
сравнимое по порядку величины с
q (которое близко к N); это число он держит в секрете.
Он вычисляет
аВ
∈
Е и передает эту точку открыто. Абонент Б делает то же самое: он вы-
бирает случайно
b и открыто передает bB
∈
Е. Тогда используемый ими секретный ключ
– это
Р = abВ ∈ Е. Оба пользователя могут вычислить этот ключ. Например, А знает bB
(точка была передана открыто) и свое собственное секретное а. Однако любая третья сто-
рона знает лишь
аВ и bB. Кроме решения задачи дискретного логарифмирования – нахож-
дения
а по В и аВ (или нахождения b по B и bB) по-видимому, нет способа найти аbВ, зная
лишь
аВ и bВ.
Пример 2.
Возьмем р = 211, )4,0(
−
p
E (что соответствует кривой 4
32
−= xy ) и B =
(2, 2). Можно подсчитать, что 241
B = О. Личным ключом пользователя А является a =
121, поэтому открытым ключом А будет
aB
= 121(2, 2) = (115, 48). Личным ключом поль-

Страницы