Генерація простих чисел

На випадкові прості числа і накладаються наступні додаткові обмеження:

• і не повинні бути занадто близькі один до одного, інакше можна буде їх знайти, використовуючи метод факторизації Ферма. Однак, якщо обидва простих числа і були згенеровані незалежно, то це обмеження з величезною ймовірністю автоматично виконується.

• Необхідно вибирати «сильні» прості числа, щоб не можна було скористатися p-1 методом Полларда.

Схема із загальним модулем n

Початкові дані: Щоб уникнути генерування різних модулів для кожного користувача, захищений сервер використовує єдиний n для шифрування всіх повідомлень. Сторона використовує цей сервер для отримання повідомлення

Завдання: противник хоче розшифрувати повідомлення сторони.

Здавалося б, шифротекст відправлений стороні, не може бути розшифрований стороною, якщо вона не володіє секретним ключем. Однак сторона може використовувати свої експоненти, щоб розкласти модуль, і після цього, знаючи, обчислити секретну експоненту.

Захист: для кожного користувача повинен використовуватися свій модуль.