Методы и средства криптографической защиты информации. Жданов О.Н - 176 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

176
большого числа точек произвольной эллиптической кривой E над
q
F . Однако,
как мы увидим далее, существуют вероятностные алгоритмы с малой
вероятностью неудачи. Во-вторых, порождать случайные точки на Е
недостаточно: чтобы закодировать большое число возможных сообщений т,
необходим какой-то систематический способ порождения точек, которые были
бы связаны с т определенным образом например, чтобы x-координата имела с т
простую
связь.
Приведем один возможный вероятностный метод представления
открытых текстов как точек на эллиптической кривой Е, определенной над
q
F ,
где
r
pq = предполагается большим (и нечетным (см ниже упражнение 8
при
r
pq = )). Пусть
κ
- достаточно большое целое число, настолько, что можно
считать допустимым, если попытка представить в нужном нам виде элемент
(«слово») открытого текста m оказывается неудачной в одном случае из
κ
2 ;
практически достаточно
κ
= 30 или, на худой конец,
κ
= 50. Пусть элементы
нашего сообщения m - целые числа,
Mm0
≤
≤
. Предположим также, что
выбранное нами конечное толе имеет q элементов, q > М
κ
. Записываем петые
числа от 1 до М
κ
в виде
j
m
+
κ
, где
κ
≤
≤
j1 устанавливаем взаимно
однозначное соответствие между такими числами и некоторым множеством
элементов из
q
F . Например, можно записать такое число как r -значное числе в
р-ичной системе счисления и, отождествляя цифры в этой записи с элементами
pZ/ZF
p
≅ , рассматривать их как коэффициенты многочлена степени не выше r
- 1 над
p
F . соответствующего элементу поля
q
F . Таким образом, числу
(
012r1r
aa...aa
−−
) ставится в соответствие многочлен
∑
−
=
1r
0i
i
i
Xa который, будучи
рассмотрен по модулю некоторого фиксированного неприводимого многочлена
степени r над
p
F , дает элемент
q
F .
Итак, при данном m при каждом j = 1,2,... ,
κ
мы получаем элемент х из
q
F ,
соответствующий
j
m +
κ
. Для такого х вычисляем правую часть уравнения
baxx)x(fy
32
++==
и пытаемся найти квадратный корень из f(x), используя метод, изложенный в
конце § II. 2. Хотя этот алгоритм был приведен для простого поля
p
F , он
дословно переносится на любое конечное поле
q
F . Чтобы воспользоваться им,
нужно иметь элемент g в этом поле, не являющийся квадратом; его можно легко
найти с помощью вероятностного алгоритма.) Если мы находим такой у, что

Страницы