Где RSA ломают на самом деле: четыре ошибки применения

Если ты объяснишь, почему нельзя шифровать формулой mᵉ mod n без дополнения, чем опасен показатель 3, как общий множитель двух модулей раскрывает оба ключа и почему p и q не должны стоять рядом, - листай до «Теперь сам».

Как думаешь, сколько стоит ключ, у которого с чужим общее простое

Два роутера одной модели включили впервые, и каждый создал себе ключ RSA в 2048 бит. Случайности сразу после включения в устройстве почти нет, и первым простым у обоих вышло одно и то же число p. Вторые простые разные, и модули разные: n₁ = p · q₁, n₂ = p · q₂. Оба открытых ключа видит каждый, кто подключится к роутеру.

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

На что это похоже

Представь бронированную дверь с замком, который не вскрыть за сто лет. Дверь стоит в стене из гипсокартона, а запасной ключ лежит под ковриком. Вор замок не трогает: он проверяет коврик и стену.

Стойкость RSA - утверждение про замок: произведение двух больших случайных простых трудно разложить. Каждая ошибка ниже либо нарушает одно из слов этого утверждения, либо обходит разложение стороной.

Механизм: четыре ошибки и алгоритм на каждую

что сделали                  что получает посторонний  алгоритм
число зашифровано как есть,  сообщение                 перебор догадок
вариантов сообщения мало                               открытым ключом
e = 3, сообщение короткое    сообщение                 кубический корень,
или ушло трём получателям                              китайская теорема
у двух ключей общее простое  оба секретных ключа       алгоритм Евклида
p и q стоят рядом            секретный ключ            метод Ферма

Число зашифровано как есть. В формуле c = mᵉ mod n нет ничего случайного: одно сообщение всегда даёт один шифртекст. Открытый ключ есть у всех, значит любой может зашифровать свою догадку и сравнить. Пусть по каналу прошёл зашифрованный четырёхзначный код, а ключ - из урока про RSA:

n = 7800001490000011
e = 65537
c = 4885659480074017

for pin in range(10000):
    if pow(pin, e, n) == c:
        print(pin)
        break

Программа печатает 4821 за 91 623 шага. Ключ при этом цел, и длина модуля роли не играет: перебирается не ключ, а сообщение. То же с ответом «да» или «нет», суммой перевода, датой рождения.

Защищает дополнение: перед возведением в степень сообщение по стандартной схеме смешивают со случайными байтами до длины модуля. Схема для шифрования называется OAEP. Одно сообщение каждый раз даёт новый шифртекст, и догадку сравнивать не с чем. У подписи схема своя, PSS: она дополняет хеш до длины модуля, тоже со случайными байтами.

Маленький показатель. С e = 3 шифрование стоит два умножения, и раньше его брали ради скорости. Но остаток по модулю меняет число, только когда оно не меньше модуля. Тот же модуль, показатель 3, сообщение m = 123 456:

n            = 7 800 001 490 000 011
m³           = 1 881 640 295 202 816     меньше n
c = m³ mod n = 1 881 640 295 202 816     остаток ничего не изменил

Шифртекст - просто куб, а целый кубический корень находит двоичный поиск:

def koren3(c):
    lo = 0
    hi = 208063
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * mid * mid <= c:
            lo = mid
        else:
            hi = mid - 1
    return lo

print(koren3(1881640295202816))

123456 за 77 шагов, без единого обращения к ключу. Граница 208 063 - наибольшее число, куб которого помещается в точные целые тренажёра. В настоящих размерах картина та же: ключ сеанса в 256 бит, возведённый в куб, занимает 768 бит при модуле в 2048.

У той же ошибки есть второй вид. Одно сообщение отправили трём получателям, у каждого свой модуль и e = 3. Теперь куб больше каждого модуля, и каждый шифртекст - честный остаток. Но три остатка одного числа по трём попарно взаимно простым модулям - это вход китайской теоремы об остатках. (Будь у двух модулей общий делитель, он раскрыл бы оба ключа ещё проще - это первый разбор.) Она восстанавливает число по модулю произведения n₁ · n₂ · n₃, а m³ меньше этого произведения, потому что m меньше каждого модуля. Функция kto - из урока о китайской теореме:

moduli = [139147, 137317, 137497]
shifry = [101997, 79450, 31135]
x = kto(shifry, moduli)[0]
print(x, koren3(x))

1881640295202816 123456

Ни один из трёх ключей не взломан, а сообщение прочитано. Защита - e = 65 537 и то же дополнение: с ним у каждого получателя под степенью оказывается своё число.

Две оставшиеся ошибки касаются не шифрования, а выбора простых. Им отданы разборы.

Правило

Формулу mᵉ mod n не применяют к сообщению напрямую: шифруют с дополнением OAEP, подписывают с дополнением PSS, и оба делает библиотека. Открытый показатель - 65 537. Простые p и q берут из криптографического генератора случайных чисел, каждое независимо от другого и от чужих ключей: тогда совпадение с чужим простым и соседство двух своих невероятны. Нарушение любого из условий открывает дорогу алгоритму, которому длина модуля не мешает.

Разбор: общее простое и алгоритм Евклида

Первый ключ - из урока про RSA: n₁ = 7 800 001 490 000 011. У второго то же первое простое и другое второе: n₂ = 6 600 002 230 000 187. Открытый показатель у обоих - 65 537. Постороннему известны только открытые ключи.

def nod(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

n1 = 7800001490000011
n2 = 6600002230000187
p = nod(n1, n2)
print(p, n1 // p, n2 // p)

60000011 130000001 110000017

Оба модуля разложены. Почему это работает: p делит и n₁, и n₂, а других общих делителей у них нет, потому что q₁ и q₂ - разные простые. Наибольший общий делитель равен p, и алгоритму Евклида не нужно знать множители, чтобы его найти: он только берёт остатки.

действие                                               шагов
НОД двух модулей, вся программа выше                      46
ро-метод из прошлой главы на одном модуле n₁       1 011 535

Дальше посторонний делает то же, что хозяин ключа: считает φ(n₂) = (p − 1)(q₂ − 1) и d₂ = e⁻¹ mod φ(n₂) = 2 596 918 582 193 633.

Ответ на вопрос из начала: один НОД. Для модулей в 2048 бит это несколько тысяч делений длинных чисел - число кругов алгоритма Евклида растёт как число битов. Работа занимает доли секунды, и длина ключа её почти не меняет.

Почему совпадает одно простое, а не оба. В момент выбора p у двух одинаковых устройств одинаковое состояние генератора. К выбору q в него успевает попасть немного случайности: показание часов, первый сетевой пакет. В 2012 году исследователи собрали открытые ключи со всех доступных адресов интернета и посчитали общие делители. Секретные ключи нашлись у 0,5% серверов TLS (это протокол, который защищает HTTPS); почти все - роутеры и другие устройства, создававшие ключ при первом включении. Миллионы ключей попарно не сравнивают: каждый модуль сверяют с произведением всех остальных.

Разбор: длинный ключ с соседними простыми

Наивное правило - «длинный модуль трудно разложить». Оно верно, только если множители выбраны независимо. Пусть p и q стоят рядом. Обозначим середину между ними a = (p + q) / 2, а половину расстояния b = (q − p) / 2. Тогда p = a − b, q = a + b и

n = (a − b)(a + b) = a² − b²

Метод Ферма ищет такое a перебором. При близких множителях b мало, и a лишь чуть больше корня из n. Поэтому перебор начинают от корня и идут вверх, пока a² − n не окажется точным квадратом.

def ferma(n):
    a = int(n ** 0.5)
    while a * a < n:
        a = a + 1
    krugov = 1
    while True:
        b = int((a * a - n) ** 0.5)
        if b * b == a * a - n:
            return [a - b, a + b, krugov]
        a = a + 1
        krugov = krugov + 1

print(ferma(7744002464000171))

Степень 0.5 - квадратный корень дробным числом, int отбрасывает дробную часть. Для настоящих длин вместо неё берут целочисленный корень math.isqrt: в дробное число модуль в 2048 бит не поместится. Программа печатает [88000009, 88000019, 1]: множители найдены с первого круга. Три модуля одной длины, 53 бита:

                                          метод Ферма        ро-метод
p            q            q − p         кругов       шагов      шагов
88 000 009   88 000 019          10          1          10    897 383
87 000 037   89 000 027   1 999 990      5 682      28 415    815 827
70 000 027  110 000 017  39 999 990  2 250 355  11 251 780  2 756 371

Ро-метод разницы между строками почти не замечает: его цена зависит от размера множителя. При одной длине модуля цену метода Ферма определяет расстояние между множителями. Кругов столько, сколько целых чисел от корня из n до середины (p + q) / 2. Во второй строке середина равна 88 000 032, корень - 87 994 350,06, между ними 5 682 числа. Расстояние между множителями выросло в двадцать раз - кругов стало больше в 396 раз, почти в 20².

В первой строке q - следующее простое после p. В 2022 году такие ключи нашли в принтерах двух производителей: библиотека выбирала простые рядом друг с другом, и модуль в 2048 бит раскладывался с первого круга. У независимых случайных простых по 1024 бита расстояние порядка 2¹⁰²², и число кругов записывается тремя сотнями цифр. Стандарт генерации ключей требует, чтобы p и q различались уже в первых ста битах; у независимых случайных чисел это выполняется само.

Что ломается без этого

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

Второе: сервер, который по-разному отвечает на верное и неверное дополнение. Старая схема дополнения для шифрования, PKCS#1 версии 1.5, проверяется при расшифровке. Если по тексту ошибки или по времени ответа можно отличить «дополнение сошлось» от «не сошлось», посторонний шлёт подобранные шифртексты. Каждый ответ «сошлось» означает, что расшифрованное число начинается с известных служебных байтов, то есть лежит в узком промежутке; тысячи таких ответов сужают промежуток до одного числа. Способ описан в 1998 году, а в июле 2026 года такую утечку по времени закрывали в библиотеке Mbed TLS. В TLS версии 1.3 пересылки ключа под шифрованием RSA нет вовсе.

Третье: генератор с изъяном у производителя. В 2017 году выяснилось, что чипы одного производителя строят простые особого вида; Эстонии пришлось заменить сертификаты на 750 тысячах удостоверений личности. В июне 2026 года в ключах, собранных по интернету, нашли модули с ровными блоками нулей - их создавала одна программа передачи файлов в версиях 2016-2019 годов.

Четвёртое: один ключ на всех. Образ диска с уже созданным ключом SSH размножили на сотню серверов. Секретный ключ у них общий, и украсть его достаточно с одного.

Зачем это в работе

Формулу RSA ты в работе не напишешь, а четыре решения примешь. В библиотеке выбираешь режим: в модуле cryptography для Python это padding.OAEP для шифрования и padding.PSS для подписи, а не PKCS1v15. В чужом коде строка pow(m, e, n) рядом со словом «шифрование» - находка для ревью.

Ключи для виртуальных машин и устройств создаются при первом запуске, а не лежат в образе, и создаются после того, как система набрала случайность. Готовые открытые ключи проверяет на известные слабости утилита badkeys: общие множители с ключами из её базы, близкие простые, изъяны конкретных библиотек.

Для новых ключей SSH сегодня берут не RSA, а ssh-keygen -t ed25519: в этой схеме нет ни дополнения, ни выбора простых.

Теперь сам

1. Два модуля: 187 и 253. Найди их общий множитель алгоритмом Евклида и разложи оба.
2. n = 8633. С какого a начнёт метод Ферма и сколько кругов ему понадобится?
3. Открытый ключ (n, e) = (187, 3), шифртекст 125. Найди сообщение без секретного ключа и объясни, почему это удалось.
4. Ключ (187, 7), перехвачен шифртекст 15. Известно, что сообщение - 41, 42 или 43. Как узнать, какое именно, и что помешало бы это сделать?