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

UptoLike

ВУЗ: 

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

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

Рубрика: 

177
)x(fy
2
= . то берем )y,x(P
m
= . Если f(x) не оказывается квадратом, то
увеличиваем j на 1 и повторяем попытку с соответствующим значением х. Если
мы находим х, для которого j(x) — квадрат, прежде, чем j превысит
κ
, то мы
можем восстановить т по известной тетке (х, у) с помощью формулы
[]
κ
/)jx
~
(m −=
, где x
~
— целое число, соответствующее х при установленном
взаимно однозначном соответствии между целыми числами и элементами
q
F .
Так как f(x) — квадрат приблизительно в 50% случаев, то вероятность того, что
метод не приведет
κ
результату и мы не найдем точки
т
P с x-координатой,
соответствующей целому числу
x
~
между
1т
+
κ
и
κ
κ
+
т , равна примерно
x
2
−
.
(Точнее, вероятность того, что f(x) есть квадрат, фактически равна N/(2q),
однако N/(2q) очень близко к 1/2.)
Дискретный логарифм на Е.
Определение. Пусть Е — эллиптическая кривая над
q
F , и В — точка на Е.
Задачей дискретного логарифмирования на Е (с основанием В) называется
задача нахождения для данной точки Р
∈
Е такого целого числа х ∈ Z (если оно
существует), что хВ = Р.
Вполне возможно, что задача дискретного логарифмирования на
эллиптической кривой окажется более трудной для решения, чем задача
дискретного логарифмирования в конечных полях. Наиболее сильные методы,
разработанные для конечных полей, по-видимому, не работают в случае
эллиптических кривых. Это обстоятельство поособенному отчетливо
проявляется в случае
полей характеристики 2. Как объясняется в обзорной
статье Одлыжко, упомянутой в списке литературы, специальные методы
решения задачи дискретного логарифмирования в
r
2
F
позволяют сравнительно
легко вычислять дискретные логарифмы и, следовательно, вскрывать
соответствующие криптосистемы, если r не выбрано очень большим.
Аналогичные системы, использующие эллиптические кривые над
q
F (см. ниже),
судя но всему, являются надежными при значительно меньших значениях r. Так
как имеются практические причины (связанные с устройством ЭВМ и
программированием) предпочтительности арифметических операций над
полям
r
2
F , криптосистемы с открытым ключом, рассматриваемые ниже, могут
оказаться более удобными для практического применения, чем системы,
основанные на задаче дискретного логарифмирования в
∗
q
F
Основные преимущества криптосистем на эллиптических кривых
заключаются в том, что не известны субэкспоненциальные алгоритмы Е

Страницы