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

UptoLike

ВУЗ: 

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

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

Рубрика: 

1. Оценки времени работы в предложении 2.1 не являются наилучшими, особенно
для конечных полей характеристики р = 2. Нам, однако, достаточно этих оценок, которые
следуют из наиболее очевидных алгоритмов арифметики в конечных полях.
2. Если известно число N точек на эллиптической кривой Е и если k > N, то в силу
равенства NP = О мы можем
заменить k его наименьшим неотрицательным вычетом по
модулю N (k mod N); в этом случае временная оценка заменяется на O( q
4
log ) (напомним,
что
)(21 qOqqN =++≤ ). Рене Шуф (R. Schoof) предложил алгоритм, вычисляющий N
за O( qlog
8
) двоичных операций.
Представление открытого текста.
Мы намереваемся кодировать наши открытые тексты точками некоторой заданной
эллиптической кривой Е, определенной над конечным полем
q
F Мы хотим это осущест-
вить простым и систематическим способом так чтобы открытый текст m (который можно
рассматривать как целое число из некоторого интервала) можно было легко прочитать,
зная координаты соответствующей точки
m
P . Заметим, что это «кодирование» – не то же
самое, что засекречивание. Позднее мы будем рассматривать способы шифрования точек
m
P открытого текста. Однако законный пользователь системы должен быть в состоянии
восстановить т после расшифрования точки шифртекста.
Следует сделать два замечания. Во-первых, не известно детерминированного поли-
номиального (по log q) алгоритма для выписывания большого числа точек произвольной
эллиптической кривой E над
q
F .В приведенном примере мы выписали все точки, проведя
полный перебор всех возможных вариантов, но это невозможно(по крайней мере, за ра-
зумное время) для p порядка 2
160
,
а именно таков должен быть размер p для обеспечения
надежности приформировании цифровой подписи.
Однако, как мы увидим далее, сущест-
вуют вероятностные алгоритмы с малой вероятностью неудачи. Во-вторых, порождать
случайные точки на Е недостаточно: чтобы закодировать большое число возможных со-
общений т, необходим какой-то систематический способ порождения точек, которые бы-
ли бы связаны с т определенным образом, например, чтобы x-координата имела
с т про-
стую связь.
Приведем один возможный вероятностный метод представления открытых текстов
как точек на эллиптической кривой Е, определенной над
q
F , где
r
pq = предполагается
большим (и нечетным – см. упражнение 8 при
r
pq = ). Пусть
κ
– достаточно большое
целое число, настолько, что можно считать допустимым, если попытка представить в
нужном нам виде элемент («слово») открытого текста m оказывается неудачной в одном
случае из
κ
2; практически достаточно
κ
= 30 или, на худой конец,
κ
= 50. Пусть элемен-
ты нашего сообщения m – целые числа,
Mm
≤
≤
0 . Предположим также, что выбранное
нами конечное поле имеет q элементов, q > М
κ
. Записываем целые числа от 1 до М
κ
в
виде
j
m +
κ
, где
κ
≤≤ j1 и устанавливаем взаимно однозначное соответствие между та-
кими числами и некоторым множеством элементов из
q
F
. Например, можно записать та-
кое число как r-значное числе в р-ичной системе счисления и, отождествляя цифры в этой
записи с элементами pZZF
p
/≅ , рассматривать их как коэффициенты многочлена степе-
ни не выше
r - 1 над
p
F , соответствующего элементу поля
q
F . Таким образом, числу
()
0121
... aaaa
rr −−
(здесь Pa
i
<≤0) ставится в соответствие многочлен
∑
−
=
1
0
r
i
i
i
Xa который,
будучи рассмотрен по модулю некоторого фиксированного неприводимого многочлена
степени
r над
p
F , дает элемент
q
F .

Страницы