О выборе чисел p и q

Для работы алгоритма RSA нужны простые числа. Наиболее приемлемым является генерация случайных чисел и последующая проверка их на простоту. Существуют вероятностные тесты, определяющие с заданной степенью достоверности факт простоты числа. Возникает вопрос, что произойдет, если числа окажутся составными? Можно свести вероятность такого события до приемлемого минимума, используя тесты на простоту. Кроме того, если такое событие произойдет, это будет быстро обнаружено — шифрование и расшифрование не будут работать.

Кроме разрядности p и q, к ним предъявляются следующие дополнительные требования:

– числа не должны содержаться в списках известных больших простых чисел;

– они не должны быть близкими, так как иначе можно воспользоваться для факторизации N методом Ферма и решить уравнение .

– в алгоритме RSA всегда есть эквивалентные по расшифрованию показатели степеней, например d и . При этом эквивалентных решений тем больше, чем больше (p – 1, q – 1). В лучшем случае (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 г. Райвест сформулировал наиболее сильные требования. Числа должны быть простыми, причем
числа p ₁ – 1 и q ₁ – 1 не должны разлагаться в произведение маленьких простых.