ВУЗ:
Составители:
155
рассматривать промежуточные результаты по модулю N. Это делает
вычисления практически выполнимыми.
О стойкости RSA
Безопасность алгоритма RSA основана на трудоемкости разложения на
множители больших чисел. Современное состояние технических средств
разложения на множители таково, что число, содержащее 193 десятичных
знака, факторизовано в 2005 году. Следовательно, выбираемое N должно
быть больше. Большинство общепринятых алгоритмов вычисления простых
чисел p и q носят вероятностный характер.
О выборе чисел p и q.
Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым
является генерация случайных чисел и последующая проверка их на
простоту. Существуют вероятностные тесты, определяющие с заданной
степенью достоверности факт простоты числа. Возникает вопрос: что
произойдет, если числа окажутся составными? Можно свести вероятность
такого
события до приемлемого минимума, используя тесты на простоту.
Кроме того, если такое событие произойдет, это будет быстро обнаружено —
шифрование и расшифрование не будут работать.
Кроме разрядности p и q, к ним предъявляются следующие
дополнительные требования:
1. Числа не должны содержаться в списках известных больших
простых чисел.
2. Они не должны быть близкими, так
как иначе можно
воспользоваться для факторизации N методом Ферма и решить
уравнение
22
)
2
()
2
(
qp
N
qp
−
=−
+
.
3. В алгоритме RSA всегда есть эквивалентные по расшифрованию
показатели степеней, например d и
]1,1[' −−
+
=
qpdd . При этом
эквивалентных решений тем больше, чем больше (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 г. Райвест сформулировал наиболее сильные требования. Числа
2
1
,
2
1
,
2
1
,
2
1
2121
+
=
−
=
+
=
−
=
q
q
q
q
p
p
p
p должны быть простыми, причем p
1
-1 и
q
1
-1не должны разлагаться в произведение маленьких простых.
О выборе параметров e и d
Рассмотрим теперь вопрос о выборе экспонент шифрования и рас-
шифрования. Так как значения е и d определяют время зашифрования и
Страницы
- « первая
- ‹ предыдущая
- …
- 153
- 154
- 155
- 156
- 157
- …
- следующая ›
- последняя »
