RSA: математические ловушки и атаки на реализацию

RSA держится на одной асимметрии: умножить два простых числа легко, разделить произведение — нет. Всё остальное — детали реализации, и именно в них живут атаки. За тридцать лет RSA ломали не через факторизацию 2048-битного модуля, а через то, что кто-то взял маленькую экспоненту, забыл дополнение, переиспользовал простые числа или оставил оракул в обработке ошибок.

Тема идёт от конструкции к ловушкам. Сначала честная схема: генерация ключей, шифрование, подпись, китайская теорема об остатках. Потом — почему «учебный RSA» (без дополнения) нестоек: он мультипликативен, детерминирован и позволяет перемножать шифртексты. Затем четыре классические атаки: малая экспонента без дополнения, широкая атака Хастада по китайской теореме, общий модуль с двумя экспонентами и общий простой множитель у двух модулей. Завершается разбор дополнений: PKCS#1 v1.5 и оракул Блейхенбахера, OAEP и правило «не расшифровывать вслепую».

Конструкция RSA

Ключи

Выбираются два простых числа p и q, модуль n = p·q, функция Эйлера φ(n) = (p−1)(q−1). Открытая экспонента e взаимно проста с φ(n), закрытая d = e^(−1) mod φ(n). Открытый ключ — (n, e), закрытый — (n, d) плюс простые числа для ускорения ¹.

Шифрование: c = m^e mod n. Расшифрование: m = c^d mod n. Корректность следует из теоремы Эйлера: m^(ed) = m^(1 + kφ(n)) = m mod n для m, взаимно простого с n; для остальных случаев работает китайская теорема об остатках.

Подпись и КТО

Подпись — та же операция с закрытым ключом: s = H(m)^d mod n, проверка — s^e = H(m) mod n. Дополнение обязательно, и схемы для шифрования и подписи разные: для шифрования — PKCS#1 v1.5 (устаревшее, но всё ещё встречается) или OAEP, для подписи — PKCS#1 v1.5 или PSS. PSS для шифрования не применяется, OAEP — для подписи. Подпись «сырого» хеша без структуры ломается мультипликативностью ².

Китайская теорема об остатках ускоряет расшифрование в четыре раза: вместо одного возведения в степень по модулю n выполняются два по модулям p и q, а результат собирается обратно. Это стандартная оптимизация во всех библиотеках.

Атака на сбой при КТО

Ускорение через КТО создаёт отдельную уязвимость — атаку Белкора. Если при вычислении m_p = c^{d_p} mod p или m_q = c^{d_q} mod q происходит сбой (перегрев, пониженное напряжение, облучение, ошибка в оборудовании), то одна из половин результата оказывается неверной, а сборка по КТО даёт значение s, для которого s^e ≠ c mod n. При этом s^e − c делится на один из простых множителей и не делится на другой, поэтому gcd(s^e − c mod n, n) мгновенно выдаёт p или q — и весь закрытый ключ. Защита: проверять результат возведения в степень до выдачи (s^e = c mod n), использовать проверяемые схемы дополнения и защиту от сбоев на уровне платформы. Это пример того, что оптимизация реализации — самостоятельная поверхность атаки, а не деталь.

Почему учебный RSA нестоек

Детерминированность

c = m^e mod n — детерминированная функция. Одинаковые сообщения дают одинаковые шифртексты, и противник может проверить гипотезу о содержимом, просто зашифровав её открытым ключом. Это нарушение семантической стойкости, и лечится оно рандомизированным дополнением.

Мультипликативность

(m_1·m_2)^e = m_1^e · m_2^e mod n. Значит, c_1·c_2 — валидный шифртекст произведения. Противник, зная c = m^e, может вычислить c·2^e = (2m)^e и получить шифртекст удвоенного сообщения, не зная ключа. На рисунке 1 показана схема.

Именно поэтому в реальных схемах перед шифрованием укладывается структурированное дополнение, а проверка при расшифровании строгая. Учебный RSA годится только для демонстрации математики.

Малая экспонента и атака Хастада

e = 3 без дополнения

Если e = 3 и сообщение короткое (m^3 < n), возведение в куб не «заворачивается» по модулю, и c = m^3 как целое. Тогда m = c^(1/3) вычисляется целочисленным корнем — без факторизации. Защита: либо e ≥ 65537, либо дополнение, удлиняющее сообщение до размера модуля ⁵.

Широкая атака Хастада

Пусть одно сообщение отправлено e получателям с разными модулями n_i и одной экспонентой e. Тогда c_i = m^e mod n_i, и по китайской теореме об остатках восстанавливается m^e mod (n_1·…·n_e). Если m^e меньше произведения модулей, корень извлекается точно ⁴. Схема на рисунке 2.

Условия атаки нужно перечислять полностью, иначе она выглядит применимой всегда, а это не так: одно и то же сообщение m (или разные сообщения, но с известным линейным соотношением), одна и та же малая экспонента e у всех получателей, попарно взаимно простые модули n_i — иначе китайская теорема даёт не m^e mod N, а систему с ограничениями, — и отсутствие рандомизированного дополнения. Если выполнено хотя бы одно из условий «нет», атака не работает: разные дополнения дают разные m_i, и общее m из них не собирается.

Защита — рандомизированное дополнение: даже одно и то же сообщение даёт разные m_i, и атака рассыпается.

Общий модуль и общий простой

Общий модуль

Если два пользователя используют один n, но разные e_1, e_2, противник, зная c_1 = m^(e_1) и c_2 = m^(e_2), находит a·e_1 + b·e_2 = 1 расширенным алгоритмом Евклида и вычисляет c_1^a·c_2^b = m mod n. Никакой факторизации не нужно. Тот же приём работает и тогда, когда известно часть сообщения: методы Копперсмита находят малые корни полиномиальных сравнений ⁷. Защита: у каждого свой модуль, и это проверяется при генерации.

Общий простой множитель

Если у двух модулей есть общий простой множитель, gcd(n_1, n_2) мгновенно даёт его, а значит, и разложение обоих. При плохом генераторе это не редкость: исследование 2012 года нашло десятки тысяч таких пар в Интернете ⁶. Проверка проста: при генерации ключей нужно использовать качественный источник случайности и проверять gcd с уже выданными модулями.

Ферма для близких простых

Если p и q близки, n = a^2 − b^2, где a = (p+q)/2, и перебор a от √n находит разложение за несколько шагов. Защита — генерировать простые независимо, а не «рядом».

Дополнение и оракул Блейхенбахера

PKCS#1 v1.5

Дополнение PKCS#1 v1.5: 00 02 || случайные ненулевые байты || 00 || сообщение. Оно рандомизирует шифртекст, но проверка при расшифровании имеет особенность: сервер должен решить, корректен ли формат. Если он сообщает об ошибке по-разному — «плохое дополнение» против «плохой формат», — возникает оракул.

Атака

Блейхенбахер показал, что одного бита «дополнение корректно» достаточно, чтобы расшифровать любой шифртекст за несколько тысяч запросов ³. Атака работает с интервалами: каждый ответ сужает множество возможных m, и после достаточного числа запросов остаётся одно значение. Именно так ломали SSL в 1998 году и позже — реализации в библиотеках и на смарт-картах.

Защита

OAEP заменяет v1.5: дополнение строится через две хеш-функции и проверяется целиком, а ошибка обработки дополнения неотличима от ошибки формата. Плюс правило: не расшифровывать данные, пришедшие от противника, без проверки целостности на уровне протокола; использовать постоянное время и единый ответ ⁸.

Итоги темы

• RSA стоек как конструкция, но ломается на деталях реализации.
• Без дополнения схема детерминирована и мультипликативна.
• Малая экспонента без дополнения даёт целый корень; Хастад собирает m^e по CRT.
• Общий модуль ломается расширенным Евклидом, общий простой — одним gcd.
• Близкие простые разлагаются методом Ферма.
• PKCS#1 v1.5 с оракулом — атака Блейхенбахера; OAEP и единообразные ошибки закрывают её.

Литература

1. Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. 1978. — исходная статья RSA.
2. RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2. 2016. — OAEP, PSS, v1.5 и требования к проверкам.
3. Bleichenbacher D. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. CRYPTO 1998. — атака на оракул дополнения.
4. Håstad J. Solving Simultaneous Modular Equations of Low Degree. SIAM Journal on Computing, 1988. — широкая атака на малую экспоненту.
5. Boneh D. Twenty Years of Attacks on the RSA Cryptosystem. Notices of the AMS, 1999. — обзор атак и их причин.
6. Lenstra A., Hughes J., Augier M., Bos J., Kleinjung T., Wachter C. Ron was Wrong, Whit is Right. 2012. — общие простые множители в реальных ключах.
7. Coppersmith D. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. 1997. — атаки на частично известное сообщение.
8. Manger J. A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP). CRYPTO 2001. — почему OAEP тоже требует аккуратной обработки ошибок.

Дополнительные материалы к апокрифу 9

Вопросы для самопроверки

1. Какие два числа образуют открытый ключ RSA?
2. Почему e и φ(n) должны быть взаимно просты?
3. Зачем нужны p и q при расшифровании?
4. Что ускоряет китайская теорема об остатках?
5. Почему e=3 опасен без дополнения?
6. Сколько шифртекстов нужно для атаки Хастада при e=3?
7. Как из двух шифртекстов с общим модулем восстановить сообщение?
8. Почему общий простой множитель ломает сразу два ключа?
9. Как метод Ферма использует близость простых?
10. Почему учебный RSA мультипликативен?
11. Что проверяет OAEP и почему он рандомизирован?
12. Почему оракул дополнения работает даже при стойком шифре?
13. Что такое постоянное время и зачем оно в обработке ошибок?
14. Какие проверки при генерации ключей предотвращают общий простой?
15. Почему 2048 бит считаются минимумом, а не целью?

Глоссарий темы

Шпаргалка

cp rsa_template.py rsa.py            && python3 check_rsa.py rsa
cp attacks_template.py attacks.py    && python3 attacks.py && python3 check_attacks.py

Что почитать и посмотреть

• Rivest, Shamir, Adleman 1978 — исходная статья.
• RFC 8017 — PKCS#1: OAEP, PSS, v1.5.
• Bleichenbacher 1998 — атака на оракул дополнения.
• Håstad 1988 — широкая атака.
• Boneh. Twenty Years of Attacks on RSA — лучший обзор.
• Lenstra et al. Ron was Wrong, Whit is Right (2012) — общие простые в реальности.
• Coppersmith 1997 — атаки на частично известное сообщение.
• Документация cryptography по RSA — https://cryptography.io/en/latest/hazmat/primitives/asymmetric/rsa/.

Углубление: почему факторизация — не главная угроза

За тридцать лет 2048-битный RSA не был разложен. Все громкие взломы шли через реализацию: слабая случайность (общие простые), малая экспонента без дополнения, оракулы, утечки по времени. Это важный сдвиг перспективы: криптографический примитив может быть стойким, а система — нет.

Практический вывод для разработчика: не изобретать схему, использовать стандартные дополнения (OAEP, PSS), проверять источник случайности, не переиспользовать модули, обрабатывать ошибки единообразно, не расшифровывать чужие данные без проверки целостности. Каждый из этих пунктов закрывает целый класс атак.

Углубление: почему оракул дополнения так разрушителен

Оракул даёт один бит: «дополнение корректно». На первый взгляд это почти ничего. Но Блейхенбахер показал, что этот бит позволяет проверять гипотезы о старших байтах сообщения. Каждый запрос сужает интервал возможных значений, и после нескольких тысяч запросов остаётся одно.

Формально атака использует то, что m умножается на случайные s: c·s^e = (m·s)^e. Сервер сообщает, попадает ли m·s в диапазон корректного дополнения. Это даёт неравенства на m, а последовательность запросов сходится к единственному значению. Ключ не извлекается; эксплуатируется оракул.

Отсюда правило: обработка ошибок расшифрования — часть криптографического дизайна. Единый ответ, постоянное время, проверка целостности до разбора — не «хорошие практики», а условия стойкости.

Лабораторная работа 9. RSA и его ловушки

• Раздел курса: апокриф 9 «RSA: математические ловушки и атаки на реализацию»

Введение

«Сейф» выдаёт сертификаты и шифрует служебные сообщения через RSA. Ключи настоящие, 2048 бит, библиотека правильная. Ломается всё равно: один сервис использует экспоненту e=3 без дополнения, второй принимает сообщения от нескольких получателей с одним и тем же коротким текстом, третий переиспользует модуль с разными экспонентами, а у четвёртого при генерации ключей нашлись два модуля с общим простым множителем.

Работа идёт от конструкции к ловушкам. Сначала честный RSA: генерация, шифрование, подпись, китайская теорема об остатках. Потом четыре атаки, каждая из которых обходится без факторизации: целый корень при малой экспоненте, широкая атака Хастада, общий модуль и общий простой. В продвинутой части — мультипликативность учебного RSA и разбор оракула Блейхенбахера.

Части: конструкция, малая экспонента, Хастад, общий модуль и общий простой, мультипликативность и дополнения, продвинутая.

Цель работы

Научиться показывать, что RSA ломается не через факторизацию, а через неверные решения в реализации, и формулировать, какое именно решение закрывает каждую атаку.

После выполнения работы получится:

• реализовывать генерацию ключей, шифрование, расшифрование и подпись;
• ускорять расшифрование через китайскую теорему об остатках;
• извлекать целый корень и восстанавливать сообщение при e=3;
• собирать m^e по CRT и применять широкую атаку Хастада;
• ломать общий модуль расширенным алгоритмом Евклида;
• находить общий простой множитель и раскладывать близкие простые методом Ферма;
• объяснять мультипликативность и роль дополнения.

Теоретический минимум

Разделы «Конструкция RSA», «Почему учебный RSA нестоек», «Малая экспонента и атака Хастада», «Общий модуль и общий простой», «Дополнение и оракул Блейхенбахера» апокрифа 9. Соотношения:

c = m^e mod n;   m = c^d mod n;   e·d ≡ 1 (mod φ(n))
s = H(m)^d mod n;   проверка: s^e ≡ H(m) (mod n)
m^3 = c        при e = 3 и m^3 < n
m^e ≡ CRT(c_1 … c_e)   при разных модулях и одной экспоненте
a·e_1 + b·e_2 = 1  =>  m = c_1^a · c_2^b mod n
gcd(n_1, n_2) = p  =>  оба модуля раскрыты
n = a^2 − b^2      близкие простые: перебор a от √n

Перечень оснащения

Ubuntu 24.04, Python 3.10+, cryptography. Права root не нужны. Архив lr-env.

mkdir -p ~/lab-apocrypha-09 && cd ~/lab-apocrypha-09
unzip ~/lr-env.zip
cp rsa_template.py rsa.py
python3 check_rsa.py rsa

Заготовки копируются в файлы без суффикса _template: rsa.py, attacks.py.

Порядок выполнения работы

В журнал записывайте: время генерации ключа, время расшифрования с КТО и без, число шагов CRT, число шагов перебора Ферма. Для каждой атаки — что именно позволило её выполнить и какое решение разработчика её закрывает.

Часть 1. Конструкция

Задание

1. Реализуйте is_probable_prime (тест Миллера — Рабина) и gen_prime с двумя старшими единичными битами.
2. Реализуйте keygen, encrypt, decrypt, decrypt_crt, sign, verify.
3. Запустите python3 check_rsa.py rsa: проверки простоты, игрушечного примера, генерации 2048 бит и совпадения с cryptography.
4. Замерьте время расшифрования обычным способом и через КТО. Объясните, откуда ускорение примерно в четыре раза.
5. Ответьте: почему e=65537 считается хорошим выбором, а e=3 — рискованным.

Что должно получиться

Работающий RSA, совпадающий с библиотекой, и замеры, показывающие выигрыш КТО.

Часть 2. Малая экспонента

Задание

1. Реализуйте iroot(x, k) — целый корень бинарным поиском.
2. Реализуйте attack_e3(n, c): восстановите m как c^(1/3).
3. Запустите python3 attacks.py: должно напечататься сообщение.
4. Проверьте, что m^3 mod n = c, и объясните, почему модуль не участвовал.
5. Ответьте: при какой длине сообщения атака перестаёт работать и что делает дополнение.

Что должно получиться

Восстановленное сообщение и понимание границы: атака работает, пока m^e < n.

Часть 3. Широкая атака Хастада

Задание

1. Реализуйте crt(residues, moduli) для взаимно простых модулей.
2. Реализуйте attack_hastad(recipients, e): соберите m^e по CRT, извлеките корень.
3. Запустите проверку: сообщение должно удовлетворять всем трём сравнениям.
4. Ответьте: почему нужны именно e получателей и что произойдёт при e+1.
5. Объясните, почему рандомизированное дополнение ломает атаку, хотя сообщение одно и то же.

Что должно получиться

Восстановленное сообщение и понимание, что одинаковый текст при разных модулях — не защита.

Часть 4. Общий модуль и общий простой

Задание

1. Реализуйте расширенный алгоритм Евклида и attack_common_modulus.
2. Реализуйте shared_prime(n1, n2) и покажите, что одного gcd достаточно.
3. Реализуйте fermat(n) и разложите модуль из data/factor.json.
4. Запустите python3 check_attacks.py — все четыре атаки должны проходить.
5. Ответьте: какая проверка при генерации ключей предотвращает общий простой и почему она дешёвая.

Что должно получиться

Четыре работающие атаки и список проверок, которые их закрывают.

Часть 5. Мультипликативность и дополнения

Задание

1. Реализуйте malleate(n, e, c, factor): получите шифртекст сообщения, умноженного на factor.
2. Проверьте на игрушечном примере, что расшифрование даёт 2m.
3. Объясните, почему детерминированный RSA не даёт семантической стойкости: как проверить гипотезу о содержимом без ключа.
4. Соберите «правильный» вариант: OAEP через cryptography и покажите, что подмена шифртекста отвергается.
5. Ответьте: почему PKCS#1 v1.5 с разными сообщениями об ошибках даёт оракул и как это связано с Блейхенбахером.

Что должно получиться

Работающая подмена, сравнение с OAEP и понимание, что дополнение — не украшение, а часть схемы.

Часть 6. Продвинутая: оракул и постоянное время

Задание

1. Разберите атаку Блейхенбахера по шагам: интервалы, запросы, сужение множества.
2. Реализуйте упрощённый оракул: сервер отвечает «дополнение верно» или «неверно», и покажите, что одного бита достаточно для сужения интервала.
3. Соберите вариант с единым ответом и постоянным временем; покажите, что оракул исчезает.
4. Сформулируйте чек-лист: дополнение, обработка ошибок, порядок проверок, длина ключа, источник случайности.
5. Оцените, какие из атак темы остаются возможными при корректном OAEP и своих модулях у каждого пользователя.

Что должно получиться

Разобранная атака, нейтрализованный оракул и чек-лист для ревью.

Журнал работы

Фиксируйте: параметры ключей, шаги CRT, время атак, восстановленные сообщения. Провал проверки — с причиной: неверный обратный элемент, перепутан порядок CRT, потеряна целочисленность корня.

Контрольные вопросы

1. На чём держится стойкость RSA?
2. Зачем нужна китайская теорема об остатках и сколько она даёт?
3. Почему учебный RSA детерминирован и чем это плохо?
4. Что такое мультипликативность и как она эксплуатируется?
5. Как работает атака при e=3 без дополнения?
6. Сколько получателей нужно для атаки Хастада и почему?
7. Как ломается общий модуль с двумя экспонентами?
8. Как найти общий простой множитель двух модулей?
9. Почему близкие простые разлагаются методом Ферма?
10. Что даёт OAEP по сравнению с PKCS#1 v1.5?
11. Почему оракул дополнения опасен даже при стойком RSA?
12. Какой набор решений закрывает все атаки темы?