RSA: шифрование и подпись

RSA — первая практическая схема шифрования с открытым ключом, опубликованная в 1977 году и названная по именам авторов: Ривеста, Шамира и Адлемана ¹. Её идея проста настолько, что удивляет: возведение в степень по модулю легко выполнить и трудно обратить без знания разложения модуля на множители. Из этой асимметрии вырастают и шифрование, и электронная подпись, и — что важно для практики — множество способов всё это сломать.

За почти пятьдесят лет RSA прошёл путь от «математического курьёза» до рабочей лошадки инфраструктуры. Он всё ещё используется в сертификатах, в подписи кода, в SSH-ключах, в шифровании почты. При этом «голый» RSA небезопасен во всех применениях: он детерминирован, ковок, гомоморфен и без дополнения ломается тривиальными алгебраическими приёмами. Практический RSA — это RSA плюс схема дополнения (OAEP или PSS) плюс аккуратная реализация, устойчивая к атакам по времени и по сбоям.

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

Паспорт темы. Нужно знать: темы 4, 10. Освоите: доказывать корректность RSA; объяснять, почему «учебный» RSA непригоден; применять OAEP и PSS; проводить атаки при малом показателе, общем модуле и оракуле дополнения; описывать KEM/DEM и форматы ключей. Проверяет: ЛР 12. Минимум: разделы 1–4. Углубление: разделы 5–6.

Схема RSA

Генерация ключей

Генерация состоит из пяти шагов.

1. Выбрать два больших простых p и q, желательно одинаковой длины.
2. Вычислить модуль n = p·q.
3. Вычислить функцию Эйлера φ(n) = (p − 1)(q − 1).
4. Выбрать показатель шифрования e, взаимно простой с φ(n); обычно e = 65537.
5. Вычислить показатель расшифрования d = e⁻¹ mod φ(n).

Открытый ключ — пара (n, e), закрытый — d (и, как правило, p, q для ускорения). Простые числа после генерации уничтожаются, хотя на практике их хранят в закрытом ключе для ускорения через КТО.

Выбор e = 65537 (простое число Ферма 2^16 + 1) объясняется компромиссом: в двоичной записи две единицы, поэтому возведение в степень требует 17 умножений вместо сотен; при этом e достаточно велико, чтобы избежать атак с малым показателем. Исторически использовали и e = 3, что и породило целое семейство атак.

Шифрование и корректность

Шифрование: c = m^e \bmod n. Расшифрование: m = c^d \bmod n.

Корректность опирается на теорему Эйлера: поскольку e \cdot d \equiv 1 \pmod{\varphi(n)}, существует целое k, при котором e \cdot d = 1 + k \cdot \varphi(n), и тогда

c^d \equiv m^{e \cdot d} = m^{1 + k \cdot \varphi(n)} = m \cdot \big(m^{\varphi(n)}\big)^k \equiv m \pmod n

для m, взаимно простого с n. Если m не взаимно просто с n, то m делится на p или на q, и сравнение проверяется отдельно по каждому модулю: по модулю p обе части равны нулю, по модулю q работает теорема Эйлера; по китайской теореме об остатках сравнение верно и по модулю n. Вероятность попасть на такое m равна 1/p + 1/q, что для больших простых пренебрежимо мала, но в доказательстве этот случай нужно разобрать.

Схема ниже показывает преобразования.

Числовой пример

Возьмём p = 61, q = 53. Тогда n = 3233, φ(n) = 60·52 = 3120. Выберем e = 17 (взаимно просто с 3120), тогда d = 17⁻¹ mod 3120 = 2753, поскольку 17·2753 = 46801 = 15·3120 + 1.

Шифруем m = 65: c = 65^17 mod 3233 = 2790. Расшифровываем: 2790^2753 mod 3233 = 65. Всё сходится.

p, q = 61, 53
n = p * q
phi = (p - 1) * (q - 1)
e = 17
d = pow(e, -1, phi)          # 2753
c = pow(65, e, n)            # 2790
assert pow(c, d, n) == 65

Разумеется, с n = 3233 ключ вскрывается факторизацией за микросекунды. Пример нужен, чтобы увидеть арифметику, а не стойкость.

Ускорение через КТО и атака Белкора

Расшифрование c^d mod n дорого: показатель d имеет ту же длину, что и n. Стандартное ускорение — вычислять по модулям p и q отдельно, где числа вдвое короче, а затем собирать результат по китайской теореме об остатках. Выигрыш примерно в четыре раза, потому что стоимость возведения в степень квадратична по длине модуля.

Схема ниже показывает ускорение и место возможного сбоя.

Побочный эффект — уязвимость к сбоям. Если одно из двух вычислений выполнено с ошибкой (аппаратный сбой, скачок напряжения, облучение, ошибка в коде), результат m' удовлетворяет сравнению m' ≡ m (mod p), но не по модулю q. Тогда gcd(m'^e − c, n) даёт либо p, либо q — то есть разложение модуля и полный закрытый ключ. Атака опубликована Бонэ, Демилло и Липтоном в 1997 году ⁷ и известна как атака Белкора (по имени исследовательского центра, где её демонстрировали).

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

Почему учебный RSA не годится

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

Учебный RSA детерминирован: одинаковые сообщения при одном ключе дают одинаковые шифртексты. Это нарушает IND-CPA точно так же, как детерминированное блочное шифрование в теме 7: противник может сравнить шифртексты и узнать, совпадают ли сообщения.

Кроме того, RSA мультипликативен: E(m₁)·E(m₂) = E(m₁·m₂). Из двух шифртекстов можно получить шифртекст произведения, не зная ключа. Это свойство называют гомоморфностью, и оно позволяет атаки: например, если противник хочет расшифровать c = m^e, он может запросить расшифрование c' = c·2^e mod n, получить 2m и разделить на 2.

Гомоморфность же ломает «учебную» подпись: если подпись — это σ = m^d mod n, то σ₁·σ₂ = (m₁·m₂)^d, то есть из двух подписей получается подпись произведения. Об этом ниже.

Малый показатель и кубический корень

Пусть e = 3 и сообщение m таково, что m³ < n. Тогда c = m³ mod n = m³ без приведения по модулю, и m находится извлечением обычного кубического корня.

Проще говоря, при малом показателе и коротком сообщении модуль вообще не участвует: шифрование сводится к возведению в кубическую степень, а обращение — к корню. Именно поэтому дополнение обязательно: оно делает m длинным и случайным, так что m³ заведомо больше n.

Широковещательная атака Хастада

Хуже: если одно и то же сообщение отправлено нескольким получателям с одним и тем же малым e, атакующий восстанавливает сообщение без всякого ключа. Пусть e = 3 и три получателя имеют модули n₁, n₂, n₃. Противник знает cᵢ = m³ mod nᵢ. По китайской теореме об остатках он восстанавливает x = m³ mod (n₁·n₂·n₃), а если m³ меньше произведения модулей — то и точное m³, из которого берётся кубический корень.

Схема ниже показывает атаку.

Демонстрация: сообщение OK (число 20299), три 1024-битных модуля, e = 3. Тогда m³ имеет 43 бита, что гораздо меньше произведения модулей, и корень извлекается точно. Атака описана Хастадом в 1988 году ⁵; обобщение на случай, когда получателей больше, чем e, и сообщения различны, но связаны линейно, также работает.

Защита: дополнение (делает сообщения разными и длинными) и достаточно большой e. Именно поэтому e = 65537, а не 3.

Общий модуль

Если два пользователя имеют один и тот же модуль n, но разные показатели e₁ и e₂ с gcd(e₁, e₂) = 1, то любой из них может восстановить закрытый ключ другого. Причина: по расширенному алгоритму Евклида находятся a и b, для которых a·e₁ + b·e₂ = 1, и тогда для любого шифртекста c = m^e₁:

c^a · (c')^b = m^(a·e₁ + b·e₂) = m

где c' — тот же открытый текст, зашифрованный вторым ключом. Если известен только один шифртекст, атакующий может попросить второго пользователя расшифровать его и получить m. Практическая рекомендация проста: один модуль — одна пара ключей; никогда не выдавать два ключа с общим модулем.

Другие атаки на «учебный» RSA

Отдельно стоит упомянуть атаку Винера на малый закрытый показатель: если d < n^(1/4)/3, то d восстанавливается по непрерывной дроби разложения e/n ⁶. Отсюда правило: d должен быть большим, а значит e не должен быть слишком большим. e = 65537 удовлетворяет обоим требованиям.

Ещё одна классическая ошибка — использовать простые p и q, близкие друг к другу. Тогда n близко к квадрату, и метод Ферма факторизует n за O(|p − q|) шагов. Это разбирается в лабораторной работе.

Дополнение

PKCS#1 v1.5 и атака Блейхенбахера

Исторически первым стандартом дополнения стал PKCS#1 v1.5: к сообщению добавляются байты 00 02, затем случайные ненулевые байты, затем 00 и само сообщение. Случайность делает шифрование недетерминированным, а длина блока — достаточной, чтобы m было большим.

Схема ниже сравнивает PKCS#1 v1.5 и OAEP.

Проблема v1.5 в том, что проверка корректности дополнения при расшифровании даёт оракул. Атака Блейхенбахера (1998) использует именно это: противник отправляет модифицированные шифртексты и по тому, принят ли результат («дополнение корректно»), шаг за шагом сужает множество возможных сообщений, пока не восстановит его целиком ³. Число запросов — порядка миллиона для 1024-битного ключа, что вполне практично.

Атака переоткрывалась много раз в реальных библиотеках. В 2017 году проект ROBOT показал, что через двадцать лет после публикации уязвимость воспроизводится в популярных TLS-стеке, почтовых серверах и библиотеках ⁴. Урок: если протокол позволяет отличить «дополнение корректно» от «некорректно», атака возвращается, сколько бы лет ни прошло.

OAEP

OAEP (англ. Optimal Asymmetric Encryption Padding, RFC 8017) решает проблему структурно ². Схема: сообщение вместе со случайной солью пропускается через две хеш-функции с маскированием (сеть Фейстеля на хешах), и результат подаётся на вход RSA.

Свойства OAEP: дополнение нельзя проверить частично (все биты зависят от всех), случайность полная, есть доказательство стойкости в модели случайного оракула (с уточнениями Шупа ¹²). Практически: любая ошибка расшифрования выглядит одинаково, и оракул исчезает.

from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes

ct = public_key.encrypt(
    message,
    padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                 algorithm=hashes.SHA256(), label=None),
)
pt = private_key.decrypt(ct, padding.OAEP(...))   # одинаковые параметры обязательны

Важно, что параметры OAEP (хеш и MGF1) должны совпадать у отправителя и получателя; расхождение даёт ошибку расшифрования, неотличимую от подделки.

ROBOT и практические выводы

История ROBOT показательна тем, что атака не была «теоретической». Библиотеки возвращали разные коды ошибок, разные сообщения, разное время — и этого хватало. Вывод для разработчика: при работе с RSA-шифрованием нельзя использовать PKCS#1 v1.5 в новых системах; при выборе библиотеки нужно проверять, что ошибки расшифрования унифицированы; при проектировании протокола — не давать противнику различать причины отказа.

Вторая часть вывода: RSA-шифрование в новых системах вообще используется редко. Гибридные схемы (RSA-KEM или ECDH) передают только ключ, а данные шифруются симметрично, и это снимает большинство проблем с дополнением.

Подпись

Учебная подпись и её подделка

«Учебная» подпись — это σ = m^d mod n, проверка — σ^e ≡ m (mod n). Она ломается мультипликативностью: из подписей σ₁ и σ₂ получается подпись произведения σ₁·σ₂ для m₁·m₂. Более того, противник может выбрать случайное σ, вычислить m = σ^e mod n и объявить σ подписью для m — это «экзистенциальная подделка», потому что сообщение m бессмысленно, но подпись под ним валидна.

Отсюда два обязательных требования: подписывать не сообщение, а его хеш, и использовать схему с дополнением, которая делает подпись неотделима от сообщения.

Хеширование перед подписью

Подпись вычисляется от H(m), а не от m, по трём причинам. Первая: RSA может подписать только число меньше n, а сообщение может быть длиннее. Вторая: хеш связывает подпись с сообщением целиком, и изменение любого бита ломает проверку. Третья: хеш скрывает структуру сообщения, что снимает часть алгебраических атак.

Формально подпись — это схема с дополнением: σ = (pad(H(m)))^d mod n, где pad — схема вроде PKCS#1 v1.5 или PSS. Проверка восстанавливает pad(H(m)) и сверяет.

PKCS#1 v1.5 и PSS

Две схемы подписи стандартизованы в RFC 8017.

PKCS#1 v1.5: к хешу добавляется идентификатор алгоритма и фиксированные байты, затем дополнение до длины модуля. Схема детерминирована — одинаковое сообщение даёт одинаковую подпись. Она всё ещё широко используется (сертификаты, старые протоколы), но у неё есть известные тонкости: например, атаки на неполную проверку структуры дополнения.

PSS (англ. probabilistic signature scheme): дополнение включает случайную соль, поэтому подпись рандомизирована и у схемы есть доказательство стойкости в модели случайного оракула. PSS — рекомендуемая схема для новых применений.

from cryptography.hazmat.primitives.asymmetric import padding
from cryptography.hazmat.primitives import hashes

sig = private_key.sign(
    message,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    hashes.SHA256(),
)
public_key.verify(sig, message, padding.PSS(...), hashes.SHA256())

Требование: параметры дополнения и хеш-функции фиксируются протоколом. Если проверяющая сторона принимает несколько вариантов, это может стать оракулом или ослабить схему.

Стойкость и параметры

Факторизация и рекорды

Стойкость RSA опирается на трудность факторизации. Лучший известный метод — решето числового поля (GNFS) с субэкспоненциальной сложностью. Рекорды показывают масштаб:

RSA-250 — последний опубликованный рекорд для 829-битного модуля ¹⁰. «Ядро-годы» в таблице — оценка авторов по их собственной модели оборудования: она показывает порядок совокупных затрат, но не переводится напрямую в «часы на одном современном GPU» и не является прогнозом для другого железа. Для 2048-битного модуля аналогичная оценка на 2026 год — астрономические величины, однако горизонт пригодности определяется не только перебором: он зависит от прогресса в алгоритмах факторизации. 2048-битный модуль на много порядков сложнее: оценка для него — миллиарды лет на современных мощностях, но с учётом роста вычислительных возможностей он считается достаточным только до определённого горизонта.

Отсюда рекомендации: 2048 бит — минимум, 3072 бита — для новых систем с горизонтом после 2030 года, 4096 — с запасом. NIST SP 800-57 задаёт соответствие уровней стойкости и длин ключей ¹¹.

Генерация ключей и общие простые множители

Генерация RSA-ключа — самая уязвимая часть схемы, потому что она зависит от случайности. Если два устройства сгенерировали ключи с общим простым множителем (например, из-за слабого генератора), то gcd(n₁, n₂) даёт этот множитель, а значит — разложение обоих модулей.

Исследование 2012 года просканировало миллионы открытых ключей и нашло тысячи с общими множителями ⁸. Причина — плохая случайность на встраиваемых устройствах и виртуальных машинах: снимок состояния генератора, недостаточная энтропия при первой загрузке, повторное использование seed.

Вторая история — ROCA (2017): библиотека Infineon генерировала простые числа по формуле, которая делала их структуру предсказуемой, что позволяло факторизовать ключ за часы ⁹. Уязвимыми оказались миллионы смарт-карт, токенов и TPM. Урок: происхождение простых чисел должно быть проверяемым, а генератор — криптографически стойким.

Форматы ключей

RSA-ключи хранятся в нескольких форматах, и путаница между ними — частая причина ошибок.

PEM — текстовая обёртка (base64 между строками -----BEGIN ...-----). DER — двоичное представление ASN.1. PKCS#1 описывает «голые» структуры RSA (RSAPrivateKey, RSAPublicKey), PKCS#8 — общий контейнер для закрытых ключей (PrivateKeyInfo), SubjectPublicKeyInfo — общий контейнер для открытых.

Разобрать структуру можно командами OpenSSL:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out key.pem
openssl rsa -in key.pem -text -noout | head -40
openssl asn1parse -in key.pem -i | head -20
openssl pkey -in key.pem -pubout -out key.pub.pem
openssl rsa -in key.pem -pubout -out key.pkcs1.pub.pem -RSAPublicKey_out

Первая команда создаёт ключ, вторая показывает параметры в читаемом виде, третья — структуру ASN.1. Обратите внимание: -RSAPublicKey_out даёт PKCS#1, а -pubout — SubjectPublicKeyInfo; это разные заголовки и разные способы разбора.

Что выбирать в новых системах

Сводка, которая понадобится в темах 14–16. «Голый» RSA не применяется ни для шифрования, ни для подписи: без дополнения схема детерминирована и мультипликативна. Для шифрования используется RSA-OAEP и только там, где нужна совместимость; в новых протоколах предпочтительнее ECDH или KEM (тема 13, тема 16). Для подписи — RSA-PSS или Ed25519; PKCS#1 v1.5 остаётся для проверки старых подписей и сертификатов, но не для выпуска новых. Длина ключа: 2048 бит — до 2030 года, 3072 бита и больше — для систем, которые должны пережить этот горизонт ¹¹.

Отдельно стоит запомнить, что длина ключа не компенсирует ошибку в дополнении. Атака Блейхенбахера работает против 2048-битного ключа ровно так же, как против 1024-битного: уязвимость не в размере модуля, а в различимости ошибок. И наоборот, корректный OAEP с унифицированными ошибками не становится нестойким от того, что ключ «всего» 2048 бит.

Гибридное шифрование

KEM/DEM

RSA медленный и ограничен по длине сообщения. Поэтому на практике используют гибридную схему: асимметричный примитив передаёт короткий симметричный ключ, а данные шифруются быстрым AEAD.

Формально это описывается как KEM/DEM: механизм инкапсуляции ключа (англ. key encapsulation mechanism, KEM) выдаёт пару «ключ, инкапсуляция», а механизм инкапсуляции данных (англ. data encapsulation mechanism, DEM) шифрует данные этим ключом. Такая структура удобна тем, что позволяет менять части независимо и корректно описывать стойкость.

RSA-KEM — простейший вариант: генерируется случайное r, ключ выводится как KDF(r), а r передаётся зашифрованным через RSA (обычно с OAEP). Длина сообщения не ограничена, потому что RSA шифрует только r.

Что выбирать

Для новых систем RSA-шифрование почти не используется: ECDH (тема 13) быстрее и даёт меньшие ключи, а для постквантовой стойкости применяют ML-KEM (тема 16). RSA остаётся для подписи — в сертификатах, в подписи кода, в совместимости с существующей инфраструктурой, — и там рекомендуются PSS и ключи не короче 3072 бит.

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

Итоги темы

RSA строится на асимметрии между возведением в степень и факторизацией. Схема проста, корректность следует из теоремы Эйлера и китайской теоремы об остатках, а ускорение через КТО даёт четырёхкратный выигрыш — и уязвимость к сбоям, которую закрывает проверка результата.

Учебный RSA непригоден: он детерминирован, ковок и гомоморфен, а при малом показателе ломается кубическим корнем и широковещательной атакой Хастада; обзор семейства таких атак дан Бонэ ¹³. Общий модуль у двух ключей позволяет восстановить закрытый ключ второго пользователя. Поэтому в практическом RSA обязательны дополнение и большой показатель.

PKCS#1 v1.5 дал миру атаку Блейхенбахера, которая переоткрывается двадцать лет спустя в проекте ROBOT. OAEP закрывает проблему структурно, а PSS — для подписи. Подпись всегда вычисляется от хеша, иначе мультипликативность позволяет подделать её без ключа.

Стойкость определяется факторизацией: 2048 бит — минимум, 3072 — для новых систем. Слабое место — генерация ключей: общие простые множители и структурные дефекты вроде ROCA ломают не алгоритм, а его реализацию. Форматы ключей (PEM, DER, PKCS#1, PKCS#8) различаются, и это нужно учитывать при интеграции.

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

Литература

1. Rivest R. L., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. — Communications of the ACM, 1978, Т. 21, № 2, С. 120–126. DOI: 10.1145/359340.359342
2. Moriarty K., Kaliski B., Jonsson J., Rusch A. PKCS #1: RSA Cryptography Specifications Version 2.2. — RFC 8017, IETF, 2016. https://www.rfc-editor.org/rfc/rfc8017
3. Bleichenbacher D. Chosen Ciphertext Attacks Against Protocols Based on the RSA Encryption Standard PKCS #1. — Advances in Cryptology — CRYPTO '98, Springer, 1998, С. 1–12. DOI: 10.1007/BFb0055716
4. Böck H., Somorovsky J., Young C. Return Of Bleichenbacher's Oracle Threat (ROBOT). — 27th USENIX Security Symposium, 2018, С. 817–849. https://www.usenix.org/conference/usenixsecurity18/presentation/bock
5. Håstad J. Solving Simultaneous Modular Equations of Low Degree. — SIAM Journal on Computing, 1988, Т. 17, № 2, С. 336–341. DOI: 10.1137/0217015
6. Wiener M. J. Cryptanalysis of Short RSA Secret Exponents. — IEEE Transactions on Information Theory, 1990, Т. 36, № 3, С. 553–558. DOI: 10.1109/18.54902
7. Boneh D., DeMillo R. A., Lipton R. J. On the Importance of Checking Cryptographic Protocols for Faults. — Advances in Cryptology — EUROCRYPT '97, Springer, 1997, С. 37–51. DOI: 10.1007/3-540-69053-0_4
8. Heninger N., Durumeric Z., Wustrow E., Halderman J. A. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. — 21st USENIX Security Symposium, 2012, С. 205–220. https://www.usenix.org/conference/usenixsecurity12/technical-sessions/presentation/heninger
9. Nemec M., Sýs M., Svenda P., Klinec D., Matyas V. The Return of Coppersmith's Attack: Practical Factorization of Widely Used RSA Moduli. — Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security (CCS), 2017, С. 1631–1648. DOI: 10.1145/3133956.3133969
10. Zimmermann P., et al. Factorization of RSA-250. — Announcement, 2020. https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html
11. NIST. Recommendation for Key Management, Part 1: General. — SP 800-57 Part 1 Rev. 5, 2020. https://doi.org/10.6028/NIST.SP.800-57pt1r5
12. Shoup V. OAEP Reconsidered. — Advances in Cryptology — CRYPTO 2001, Springer, 2001, С. 239–259. DOI: 10.1007/3-540-44647-8_15
13. Boneh D. Twenty Years of Attacks on the RSA Cryptosystem. — Notices of the American Mathematical Society, 1999, Т. 46, № 2, С. 203–213.

Дополнительные материалы

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

1. Почему n = p·q позволяет публиковать модуль открыто, а φ(n) — нет?
2. Почему выбор e = 65537 считается компромиссом между скоростью и стойкостью?
3. Как из теоремы Эйлера следует корректность расшифрования?
4. Почему ускорение через КТО создаёт уязвимость к сбоям и как от неё защищаются?
5. Что означает ковкость RSA и как она проявляется в атаке на шифртекст?
6. Почему при e = 3 и коротком сообщении модуль не участвует в вычислениях?
7. Сколько получателей нужно для атаки Хастада при e = 3 и почему?
8. Как два ключа с общим модулем компрометируют друг друга?
9. Почему «учебная» подпись подделывается без ключа двумя способами?
10. Что именно проверяет получатель при расшифровании PKCS#1 v1.5 и почему это оракул?
11. Чем OAEP отличается от PKCS#1 v1.5 структурно и какие гарантии даёт?
12. Почему ROBOT показал, что старые атаки возвращаются?
13. Почему PSS считается более надёжной схемой подписи, чем v1.5?
14. Что означает «общий простой множитель» у двух ключей и как его найти?
15. Чем PEM отличается от DER и что такое PKCS#8?

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

Шпаргалка по инструментам

# генерация и разбор
openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out key.pem
openssl rsa -in key.pem -text -noout
openssl asn1parse -in key.pem -i
openssl rsa -in key.pem -check -noout

# открытый ключ в двух форматах
openssl pkey -in key.pem -pubout -out spki.pem
openssl rsa -in key.pem -RSAPublicKey_out -out pkcs1.pem

# шифрование OAEP
openssl pkeyutl -encrypt -pubin -inkey spki.pem -pkeyopt rsa_padding_mode:oaep \
  -pkeyopt rsa_oaep_md:sha256 -in msg.bin -out ct.bin
openssl pkeyutl -decrypt -inkey key.pem -pkeyopt rsa_padding_mode:oaep \
  -pkeyopt rsa_oaep_md:sha256 -in ct.bin -out msg.out

# подпись PSS
openssl dgst -sha256 -sign key.pem -sigopt rsa_padding_mode:pss -out sig.bin msg.bin
openssl dgst -sha256 -verify spki.pem -sigopt rsa_padding_mode:pss -signature sig.bin msg.bin

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
ct = key.public_key().encrypt(m, padding.OAEP(mgf=padding.MGF1(hashes.SHA256()),
                                              algorithm=hashes.SHA256(), label=None))
sig = key.sign(m, padding.PSS(mgf=padding.MGF1(hashes.SHA256()),
                              salt_length=padding.PSS.MAX_LENGTH), hashes.SHA256())

Типичные ошибки:

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

• Rivest R., Shamir A., Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (1978). Первоисточник. Читается легко и показывает, как авторы сами понимали ограничения схемы.
• RFC 8017 (PKCS #1 v2.2). Полная спецификация RSA: OAEP, PSS, PKCS#1 v1.5. Единственный источник, по которому стоит реализовывать дополнение. https://www.rfc-editor.org/rfc/rfc8017
• Boneh D. Twenty Years of Attacks on the RSA Cryptosystem (1999). Обзор атак: от элементарных до тонких. Лучший стартовый текст для понимания, почему «голый» RSA не работает.
• Bleichenbacher D. Chosen Ciphertext Attacks Against PKCS #1 (1998). Первоисточник атаки на оракул дополнения. Плотный текст, но именно он объясняет, откуда берётся миллион запросов.
• Böck H., Somorovsky J., Young C. ROBOT (2018). Как атака 1998 года переоткрылась в 2017-м в реальных библиотеках. Хороший пример того, что «исправлено в стандарте» не значит «исправлено в коде». https://robotattack.org/
• Håstad J. Solving Simultaneous Modular Equations of Low Degree (1988). Широковещательная атака и её обобщения. Короткая и ясная работа.
• Heninger N. et al. Mining Your Ps and Qs (2012). Массовый анализ открытых ключей и обнаружение общих множителей. Показывает, что слабая случайность — не теория.
• Nemec M. et al. The Return of Coppersmith's Attack (2017). ROCA: как структурный дефект генератора простых чисел ломает миллионы ключей. https://crocs.fi.muni.cz/public/papers/rsa_ccs17
• Cryptopals, Set 5 (задачи 39–42). RSA с нуля, общий модуль, кубический корень, широковещательная атака. Прямое продолжение частей 4–6.

Углубление (по желанию)

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

Асимметрия стоимости и гибридные схемы. RSA-шифрование 2048-битным ключом стоит порядка миллисекунды, AES-GCM шифрует гигабайты в секунду. Отношение — миллионы. Поэтому все практические протоколы гибридные: асимметричная часть передаёт 32 байта ключа, симметричная шифрует данные. Это же объясняет, почему KEM/DEM стал стандартной рамкой описания: он формализует разделение труда между частями.

Что будет с RSA в постквантовую эпоху. Алгоритм Шора факторизует модуль за полиномиальное время на квантовом компьютере, поэтому RSA (как и DH и ECC) не является постквантово стойким. Переход на ML-KEM и ML-DSA (тема 16) идёт медленно, потому что RSA встроен в сертификаты, в подпись кода и в прошивки. Практическая рекомендация на переходный период — гибридные схемы: классический и постквантовый алгоритм вместе, чтобы стойкость сохранялась, пока один из них не сломан.

Лабораторная работа 12. RSA своими руками и атаки на учебный RSA

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

Введение

Тема 12 показала, что RSA опасен не сам по себе, а в применении: без дополнения он детерминирован и ковок, при малом показателе ломается кубическим корнем, при общем модуле — расширенным алгоритмом Евклида, при общем простом множителе — вычислением НОД. Лабораторная работа проходит эти атаки по очереди на учебных данных, а начинается с разбора настоящего ключа: структура, параметры, сверка n = p·q и d·e ≡ 1.

Работа опирается на темы 4 (арифметика и проверка простоты) и 9 (AEAD, поскольку гибридное шифрование соединяет RSA с симметричным шифром). Она готовит тему 14: сертификаты X.509 содержат именно те структуры, которые здесь разбираются командой asn1parse.

Все атаки выполняются против ключей и данных из окружения, сгенерированных для этой работы. Атака на чужой ключ без разрешения запрещена законом; здесь учебная среда, и это единственное, что делает работу допустимой.

Цель работы

Реализовать учебный RSA, разобрать структуру настоящего ключа, применить шифрование и подпись с корректным дополнением и провести четыре атаки, показывающие, почему «учебный» RSA непригоден.

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

• разобрать ключ командами openssl rsa -text и openssl asn1parse и сверить параметры самостоятельно;
• реализовать генерацию ключа, шифрование и расшифрование на Python с проверкой простоты;
• зашифровать и подписать данные через cryptography с OAEP и PSS и через openssl pkeyutl;
• провести атаку кубического корня и широковещательную атаку Хастада;
• восстановить ключ при общем модуле и найти общий простой множитель у двух ключей через НОД;
• факторизовать 128-битный модуль методом Ферма и ро-методом Полларда;
• подделать «учебную» подпись, используя мультипликативность.

Уровни работы

• Минимум (обязательно): части 1–3. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 4–5.
• Углубление (по желанию): 6 (подделка учебной подписи).

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

Нужны разделы «Схема RSA», «Почему учебный RSA не годится», «Дополнение» и «Подпись».

ключи       n = p·q,  φ(n) = (p−1)(q−1),  e·d ≡ 1 (mod φ(n))
шифрование  c = m^e mod n,  m = c^d mod n
КТО         m_p = c^d mod p,  m_q = c^d mod q  →  сборка
OAEP        дополнение с маскированием, стойкое к оракулам
PSS         вероятностная подпись с солью

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

• Ubuntu 24.04 (или WSL2), Python 3.10+, cryptography 3.4 или новее, OpenSSL 3.0 или новее. Права root не нужны.
• Архив окружения: lr-env.zip.

Ограничения ресурсов

Факторизуется модуль 128 бит методом Ферма или ро-методом; генерация ключей — 1024–2048 бит; памяти требуется единицы мегабайт. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-12; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

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

mkdir -p ~/lab12 && cd ~/lab12
unzip /path/to/lr-env.zip
cd lr-env
python3 check_rsa.py -v
openssl rsa -in keys/key01.pub.pem -pubin -text -noout

Начинать нужно с части 1: без понимания структуры ключа дальнейшие атаки превращаются в запуск готовых скриптов.

Часть 1. Разбор ключа

Задание

1. Сгенерируйте ключ и посмотрите его параметры:

openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:2048 -out key.pem
openssl rsa -in key.pem -text -noout | head -40
openssl asn1parse -in key.pem -i | head -20

2. Выпишите n, e, d, p, q из вывода. Проверьте в Python, что n = p·q и e·d ≡ 1 (mod φ(n)).
3. Разберите структуру ASN.1: какие поля идут в каком порядке, какие длины.
4. Сравните форматы: openssl pkey -pubout (SubjectPublicKeyInfo) и openssl rsa -RSAPublicKey_out (PKCS#1). Найдите разницу в заголовках.
5. Объясните, зачем в закрытом ключе хранятся p и q, если они не нужны для расшифрования по определению.

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

Разобранный ключ с проверенными параметрами и понимание, как он устроен. Ответ на пункт 5 — ускорение через КТО.

Часть 2. Учебный RSA на Python

Задание

1. Заполните в заготовке генерацию простого (используйте тест Миллера — Рабина из темы 4), генерацию ключа, шифрование и расшифрование.
2. Проверьте на малых числах: p = 61, q = 53, e = 17 должны дать n = 3233, d = 2753, c = 2790 для m = 65.
3. Убедитесь, что расшифрование возвращает исходное сообщение для ста случайных m.
4. Реализуйте расшифрование через КТО и сравните время с прямым вычислением на 2048-битном ключе.
5. Добавьте проверку результата КТО (возведение в e и сравнение с c) и объясните, от какой атаки она защищает.

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

Работающая учебная реализация, совпадающая с примером, и понимание, что КТО ускоряет вчетверо, но требует проверки.

Часть 3. Правильное шифрование и подпись

Задание

1. Зашифруйте сообщение через cryptography с OAEP и расшифруйте. Убедитесь, что два шифрования одного сообщения дают разные шифртексты.
2. Подпишите сообщение через PSS и проверьте подпись. Убедитесь, что две подписи одного сообщения различаются (из-за соли).
3. Повторите те же операции через OpenSSL:

openssl pkeyutl -encrypt -pubin -inkey key.pub.pem -pkeyopt rsa_padding_mode:oaep \
  -pkeyopt rsa_oaep_md:sha256 -in msg.bin -out ct.bin
openssl pkeyutl -decrypt -inkey key.pem -pkeyopt rsa_padding_mode:oaep \
  -pkeyopt rsa_oaep_md:sha256 -in ct.bin -out msg.out
openssl dgst -sha256 -sign key.pem -sigopt rsa_padding_mode:pss -out sig.bin msg.bin
openssl dgst -sha256 -verify key.pub.pem -sigopt rsa_padding_mode:pss -signature sig.bin msg.bin

4. Проверьте, что подмена одного байта шифртекста приводит к ошибке расшифрования, а не к «мусору».
5. Объясните, почему параметры OAEP и PSS должны совпадать у отправителя и получателя.

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

Работающие шифрование и подпись с корректным дополнением и понимание, что именно дополнение делает RSA пригодным.

Часть 4. Атаки на учебный RSA

Задание

1. Кубический корень. В data/e3.json — шифртекст, полученный с e = 3 без дополнения, для короткого сообщения. Извлеките кубический корень целочисленно (iroot) и восстановите сообщение.
2. Хастад. В data/hastad.json — три шифртекста одного сообщения с тремя разными модулями и e = 3. Соберите x = m³ по китайской теореме и извлеките корень.
3. Общий модуль. В data/common_modulus.json — два ключа с одинаковым n и разными e₁, e₂. Найдите a, b с a·e₁ + b·e₂ = 1 и восстановите сообщение.
4. Для каждой атаки запишите условие, при котором она работает.
5. Сформулируйте, какая мера закрывает все три атаки сразу.

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

Три восстановленных сообщения и понимание, что все атаки исчезают при правильном дополнении и большом e.

Часть 5. Слабые ключи и факторизация

Задание

1. Загрузите двенадцать открытых ключей из keys/. Вычислите попарные НОД модулей: math.gcd(n_i, n_j).
2. Найдите пару с общим множителем и восстановите закрытые ключи обоих (для учебных ключей это возможно).
3. В data/factor.json — 128-битный модуль с близкими p и q. Факторизуйте его методом Ферма: a = ⌈√n⌉, затем ищите a² − n = b².
4. Если метод Ферма не срабатывает, примените ро-метод Полларда. Сравните время.
5. Объясните, почему близкие p и q опасны и как этого избежать.

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

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

Часть 6. Подделка учебной подписи

Задание

1. Реализуйте «учебную» подпись σ = H(m)^d mod n без дополнения.
2. Покажите мультипликативность: из подписей σ₁ и σ₂ постройте подпись для m₁·m₂.
3. Покажите экзистенциальную подделку: выберите случайное σ, вычислите m = σ^e mod n, объявите σ подписью для m.
4. Объясните, почему хеширование перед подписью и дополнение PSS закрывают обе возможности.
5. Проверьте, что подпись PSS не подделывается ни одним из этих способов.

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

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

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

По каждой части: предсказание, команда, результат, объяснение. Для части 4 предсказание — какое условие должно выполниться, чтобы атака сработала; для части 5 — сколько шагов потребует метод Ферма. В конце полезно свести таблицу «атака — условие — защита» и проверить, что каждая строка подтверждена запуском.

Критерии проверки

Работа считается выполненной, если:

• проверки check_rsa.py завершаются без ошибок;
• структура ключа разобрана и сверена (n = p·q), OAEP и PSS воспроизведены, атаки при e = 3, общем модуле и общем множителе выполнены;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

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

1. Почему корректность RSA требует разбора случая, когда сообщение не взаимно просто с модулем?
2. Что даёт ускорение через КТО и от какой атаки требует защиты?
3. Почему учебный RSA не является IND-CPA-стойким?
4. Как малый показатель e позволяет восстановить короткое сообщение без ключа?
5. При каком условии работает широковещательная атака Хастада?
6. Как из двух ключей с общим модулем получить закрытый ключ одного из них?
7. Почему дополнение PKCS#1 v1.5 даёт оракул и как это использует атака Блейхенбахера?
8. Что структурно отличается в OAEP и почему частичная проверка в нём невозможна?
9. Зачем подписывать хеш, а не сообщение?
10. Чем PSS отличается от PKCS#1 v1.5 для подписи и что даёт соль?
11. Почему общие простые множители у двух ключей означают компрометацию обоих?
12. Чем KEM/DEM отличается от прямого шифрования данных асимметричным ключом?