О стойкости криптосистемы RSA
Безопасность алгоритма RSA основана на трудоемкости разложения на большие простые множители больших целых чисел. Современное состояние технических средств разложения на множители таково, что число, содержащее в записи 193 десятичных знака, факторизовано в 2005 г. Следовательно, выбираемое значение N должно быть больше. Большинство общепринятых алгоритмов вычисления простых чисел p и q носят вероятностный характер. О выборе чисел p и q Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым является генерация случайных чисел и последующая проверка их на отношение к простым числам. Существуют вероятностные тесты, определяющие с заданной степенью достоверности факт простоты числа. Возникает вопрос, что произойдет, если числа окажутся составными? Можно свести вероятность такого события до приемлемого минимума, используя тесты на простоту. Кроме того, если такое событие произойдет, это будет быстро обнаружено — шифрование и расшифрование не будет осуществлено. Кроме разрядности p и q, к ним предъявляются следующие дополнительные требования: – числа не должны содержаться в списках известных больших простых чисел; – они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение – в алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например d и В лучшем случае (p – 1, q – 1) = 2, p = 2 t + 1, q = 2 s + 1, где s, t – нечетные числа с условием, - НОД (s, t) = 1. Чтобы исключить возможность применения методов факторизации накладывают следующее ограничение: числа p – 1, p + 1, q – 1, q + 1 не должны разлагаться на сомножители в виде произведения малых простых множителей, должны содержать в качестве сомножителя хотя бы одно большое простое число. В 1978 г. Райвест сформулировал наиболее сильные требования. Числа О выборе параметров e и d Рассмотрим вопрос о выборе экспонент шифрования и расшифрования. Так как значения е и d определяют время зашифрования и расшифрования, то можно назвать ряд ситуаций, в которых желательно иметь малое значение е и d. Например, при использовании системы RSA при защите электронных платежей с применением кредитных карточек естественным является требование использования небольших значений экспоненты d у владельца карточки и большого значения экспоненты e у центрального компьютера. Однако выбор малых параметров е или d представляется небезопасным по ряду соображений. Если малым является секретный параметр d, то можно применить метод перебора малых значений до получения искомого числа d. А если малым является параметр е, то достаточно большое число открытых сообщений, удовлетворяющих неравенству Другая аналогичная ситуация может сложиться, когда у нескольких абонентов используется одинаковая экспонента е. Тогда становится возможна атака на основе китайской теоремы об остатках.
|
.
. При этом эквивалентных решений тем больше, чем больше (p – 1, q – 1).
должны быть простыми, причем числа p 1 – 1 и q 1 – 1 не должны разлагаться в произведение малых простых чисел.
будут зашифровываться простым возведением в степень y = xe (mod N) и поэтому их можно найти путем извлечения корня степени е.
