Шаги генерации ключей и шифрования (суть, в формулах):
- Случайно выбрать два больших простых числа $p,q$.
- Вычислить модуль $n=pq$.
- Вычислить функцию Эйлера (или показатель Ламберта): например $\phi (n)=(p-1)(q-1)$ (или $\lambda (n)=\mathrm{lcm}(p-1,q-1)$).
- Выбрать публичную экспоненту $e$, такую что $1<e<\phi (n)$ и $\gcd (e,\phi (n))=1$.
- Вычислить секретную экспоненту $d\equiv e^{-1}(\mathrm{mod}\phi (n))$.
- Публичный ключ: $(n,e)$. Приватный ключ: $(n,d)$ (обычно с дополнительными параметрами $p,q,d_p,d_q,q^{-1}$ для ускорения CRT-расчёта).
Шифрование/дешифрование:
- Перед шифрованием применить паддинг к сообщению $m$ (см. ниже). После паддинга получить число $m\in [0,n-1]$.
- Шифротекст: $c\equiv m^e(\mathrm{mod}n)$.
- Дешифрование: $m\equiv c^d(\mathrm{mod}n)$ (или с CRT для ускорения).
Распространённые ошибки реализации и как они компрометируют безопасность
1) Малые значения публичного показателя $e$ (например $e=3$ или вообще маленькие)
- Уязвимости:
- Если одно и то же сообщение $m$ отправлено без паддинга нескольким получателям с разными модульными $n_i$ и одинаковым малым $e$, то по теореме Хастада можно собрать системы $c_i\equiv m^e(\mathrm{mod}{n}_i)$. С помощью CRT получить $M\equiv m^e(\mathrm{mod}N)$ с $N=\prod n_i$. Если $m^e<N$, то можно взять целый $e$-ый корень и восстановить $m$.
- Если сообщение маленькое так что $m^e<n$, то $c=m^e$ без редукции по модулю, и можно восстановить $m$ вычислением $m=\sqrt[e]{c}$.
- Как предотвращать: использовать стандартное значение $e=65537$ ($2^{16}+1$) или другое достаточно большое простое, всегда применять стойкий паддинг (OAEP/PKCS#1 v2) перед шифрованием.
2) Отсутствие паддинга (или использование устаревшего/ошибочного паддинга)
- Уязвимости:
- Отсутствие паддинга делает RSA детерминированным и умножаемым: $E(m_1)E(m_2)=E(m_1{m}_2)$. Это даёт возможности для множества атак (перехват и подстановка, манипуляция сообщениями).
- Неприменение современного паддинга делает возможными прямые восстановления при малых $e$ (см. выше) и выбранно-текстовые атаки.
- Неправильно реализованные старые схемы паддинга (PKCS#1 v1.5) подвержены атакам типа Блейхенбахера — наличие побочного орaкульного ответа (например, успешная/неуспешная проверка формата) позволяет по итерациям восстановить секретный текст.
- Как предотвращать: применять проверенные схемы паддинга и протоколы — RSA-OAEP (PKCS#1 v2+) для шифрования; для подписи — PSS. Не давать оракулы формат-проверки, использовать проверенные криптобиблиотеки.
3) Слабые генераторы простых чисел / плохая энтропия
- Уязвимости:
- Повторное использование тех же простых в разных ключах: если два модуля $n_1=n_2=p{q}_1$ и $n_2=p{q}_2$ имеют общий простой множитель $p$, то $\gcd (n_1,n_2)=p$ и ключи фактически ломаются мгновенно.
- Плохая энтропия (предсказуемые или малоразмерные случайные числа) позволяет атакующему перебрать или восстановить $p,q$ по известному генератору/примитиву или по словарю — результат: факторизация $n$.
- Слишком маленькие простые или простые, близкие друг к другу (если $|p-q|$ маленькое) — эффективна факторизация Ферма: берут $a=\lceil \sqrt{n}\rceil$, ищут $b^2=a^2-n$.
- Специальные свойства $p-1$ или $q-1$ (очень гладкие числа) делают возможным Pollard p-1 атаку.
- Как это компрометирует: знание либо восстановление одного простого делителя даёт немедленный доступ к приватному ключу (факторизация $n$ позволяет восстановить $\phi (n)$ и $d$). Плохой RNG в прошлом приводил к миллионам уязвимых ключей (пример: Debian OpenSSL).
- Как предотвращать: использовать криптографически стойкие генераторы случайных чисел, проверять уникальность/primality (Miller–Rabin с достаточным числом итераций), гарантировать минимальную разницу по длине и статистическую независимость $p,q$, проверять, что ни одно случайное $p$ не употребляется повторно.
Короткие дополнительные замечания (часто встречуются)
- Малый приватный показатель $d$ (не в списке, но часто встречается) — уязвим к атаке Винера, если $d<n^{0.25}$.
- Всегда хранить приватный ключ защищённо, применять механизмы защиты от боковых каналов при вычислениях (CRT без защиты даёт утечки по времени/электромагнитным/ошибочным подсказкам).
Резюме (практические предписания)
- Генерируйте $p,q$ с крипто-RNG и полноценно проверяйте простоту.
- Используйте $e=65537$ или эквивалент и убедитесь, что $\gcd (e,\phi (n))=1$.
- Обязательно применять OAEP (для шифрования) и PSS (для подписей); не используйте "сырой" RSA.
- Проверяйте ключи на коллизии (gcd с другими модулями), достаточную длину и отсутствие слабых свойств (слишком близкие p и q, гладкость p-1/q-1).