Алгоритм RSA. Жданов О.Н - 7 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

7
произойдет, это будет быстро обнаружено — шифрование и расшифрование не
будут работать.
Кроме разрядности p и q, к ним предъявляются следующие дополнитель-
ные требования:
– числа не должны содержаться в списках известных больших простых чи-
сел;
– они не должны быть близкими, так как иначе можно воспользоваться для
факторизации N методом Ферма и
решить уравнение
22
() ()
22
p
qpq
N
+
−
−=
.
– в алгоритме RSA всегда есть эквивалентные по расшифрованию показа-
тели степеней, например d и '[1,1]dd p q
=
+− −. При этом эквивалентных реше-
ний тем больше, чем больше (p – 1, q – 1). В лучшем случае (p – 1, q – 1) = 2,
p = 2t + 1, q = 2s + 1, где s, t – нечетные числа с условием (s, t) = 1.
Чтобы исключить возможность применения методов факторизации накла-
дывают следующее ограничение: числа p – 1, p + 1, q – 1, q + 1 не должны раз-
лагаться в произведение маленьких простых множителей, должны содержать в
качестве сомножителя хотя бы одно большое простое число. В 1978 г. Райвест
сформулировал наиболее сильные требования. Числа
12 1 2
111 1
,,,
22 2 2
p
pq q
pp q q
−+− +
== = = должны быть простыми, причем
числа p
1
– 1 и q
1
– 1 не должны разлагаться в произведение маленьких простых.
О выборе параметров e и d
Рассмотрим вопрос о выборе экспонент шифрования и расшифрования.
Так как значения е и d определяют время зашифрования и расшифрования, то
можно назвать ряд ситуаций, в которых желательно иметь малое значение е и d.
Например, при использовании системы RSA при защите электронных платежей
с применением кредитных карточек естественным является требование исполь-
зования небольших
значений экспоненты d у владельца карточки и большого
значения экспоненты e у центрального компьютера.
Однако выбор малых параметров е или d представляется небезопасным по
ряду соображений. Если малым является секретный параметр d, то можно при-
менить метод перебора малых значений до получения искомого числа d. А если
малым является параметр
е, то достаточно большое число открытых сообще-
ний, удовлетворяющих неравенству
,
e
x
N< будут зашифровываться простым
возведением в степень
mod()
e
yx N= и поэтому их можно найти путем извлече-
ния корня степени е.
Другая аналогичная ситуация может сложиться, когда у нескольких або-
нентов используется одинаковая экспонента е. Тогда становится возможна ата-
ка на основе китайской теоремы об остатках (см. ниже).

Страницы