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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Итак, при данном m для каждого j = 1,2,…,
κ
мы получаем элемент х из
q
F , соот-
ветствующий
j
m
+
κ
. Для такого х вычисляем правую часть уравнения
baxxxfy ++==
32
)(
и пытаемся найти квадратный корень из
)(xf
. Извлечение квадратного корня в поле
q
F
–
это отдельная интересная задача, которой уделено достаточное внимание в соответст-
вующей литературе (см. список литературы).
Если мы находим такое
у, что )(
2
xfy = , то берем ),( yxP
m
=
. Если )(xf не оказы-
вается квадратом, то увеличиваем
j на 1 и повторяем попытку с соответствующим значе-
нием
х. Если мы находим х, для которого )(xf – квадрат прежде, чем j превысит
κ
, то мы
можем восстановить
т по известной точке (х, у) с помощью формулы
[]
κ
/)
~
( jxm
−
= , где
x
~
– целое число, соответствующее х при установленном взаимно однозначном соответст-
вии между целыми числами и элементами
q
F . Так как )(xf – квадрат приблизительно в
50% случаев, то вероятность того, что метод не приведет к результату и мы не найдем
точки
т
P с x-координатой, соответствующей целому числу
x
~
между
1+
κ
т
и
κ
κ
+
т ,
равна примерно
x−
2 (точнее, вероятность того, что )(xf есть квадрат, фактически равна
N/(2q), однако N/(2q) очень близко к 1/2).
Дискретный логарифм на Е.
Определение. Пусть Е – эллиптическая кривая над
q
F
, и В – точка на Е. Задачей
дискретного логарифмирования на
Е (с основанием В) называется задача нахождения для
данной точки
Р ∈ Е такого целого числа х
∈
Z (если оно существует), что хВ = Р.
Вполне возможно, что задача дискретного логарифмирования на эллиптической
кривой окажется более трудной для решения, чем задача дискретного логарифмирования
в конечных полях. Наиболее сильные методы, разработанные для конечных полей, по-
видимому, не работают в случае эллиптических кривых. Это обстоятельство особенно от-
четливо проявляется в случае полей характеристики 2. Специальные методы решения за-
дачи дискретного логарифмирования в
r
F
2
позволяют сравнительно легко вычислять дис-
кретные логарифмы и, следовательно, вскрывать соответствующие криптосистемы, если
r
не выбрано очень большим. Аналогичные системы, использующие эллиптические кривые
над
q
F (см. ниже), судя по всему, являются столь же надежными при значительно
меньших значениях r. Так как имеются практические причины (связанные с устройством
ЭВМ и программированием) предпочтительности арифметических операций над полями
r
F
2
, криптосистемы с открытым ключом, рассматриваемые ниже, могут оказаться более
удобными для практического применения, чем системы, основанные на задаче дискретно-
го логарифмирования в
∗
q
F
До 1990 г. единственными известными алгоритмами дискретного логарифмирова-
ния на эллиптических кривых были те, которые работают в любой группе и не используют
особенности ее строения. Эти алгоритмы с экспоненциальным временем работы приме-
нимы к случаям, когда порядок группы делится на большое простое число. Однако впо-
следствии Менезес (Menezes), Окамото (Okanoto) и Вэнстон (Vanstone) предложили
новый
подход к задаче дискретного логарифмирования на эллиптической кривой
Е, определен-
ной над
q
F
. А именно, они использовали спаривание Вейля для вложения группы Е в
мультипликативную группу некоторого расширения
k
q
F поля
q
F . Это вложение сводит
задачу дискретного логарифмирования на
Е к соответствующей задаче для
∗
k
q
F
.

Страницы