RSA шифрование: как работает алгоритм

Шифрование RSA построено на паре ключей: открытым ключом (n, e) данные шифруют, закрытым ключом (n, d) расшифровывают. Число n равно произведению двух больших простых чисел p и q. Надёжность алгоритма во многом держится на сложности факторизации: разложить n обратно на p и q очень трудно, а без них не вычислить d.

Примеры прогнаны на Python 3.14.3 и библиотеке cryptography 50.0.2 (pip install cryptography), каждый блок запускается сам по себе, вывод скопирован из консоли.

Что такое RSA

Алгоритм RSA назван по фамилиям авторов: Рон Ривест, Ади Шамир и Леонард Адлеман (Rivest, Shamir, Adleman). Заявку на патент подали 14 декабря 1977 года, статья с описанием метода вышла в феврале 1978 года. В ней же предложена и цифровая подпись.

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

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

Алгоритм генерации ключей RSA состоит из пяти шагов:

1. Выбрать два разных больших простых числа p и q. Их берут случайными: у ключа 2048 бит каждое длиной 1024 бита.
2. Вычислить модуль n = p · q. Его размер в битах и называют размером ключа.
3. Вычислить φ(n) = (p − 1)(q − 1), это значение функции Эйлера, или λ(n) = НОК(p − 1, q − 1), функцию Кармайкла. В исходной статье авторов стоит φ(n), действующий стандарт PKCS #1 использует λ(n). Годятся обе.
4. Выбрать открытую экспоненту e: число от 3 до n − 1, взаимно простое с λ(n). В рабочих ключах берите e = 65537.
5. Найти закрытую экспоненту d: число, для которого e · d mod λ(n) = 1. Это обратное к e по модулю, его считают расширенным алгоритмом Евклида.

Открытый ключ: пара (n, e). Закрытый ключ: пара (n, d). Кто знает p и q, тот повторит шаги 3-5 и получит d, поэтому p и q держат в таком же секрете, как сам закрытый ключ.

Возьмём p = 41 и q = 73. Тогда n = 2993, φ(n) = 40 · 72 = 2880, λ(n) = НОК(40, 72) = 360. Открытая экспонента e = 17: у 17 и 360 нет общих делителей. Закрытую экспоненту найдём руками, делением с остатком:

• 360 = 21 · 17 + 3
• 17 = 5 · 3 + 2
• 3 = 1 · 2 + 1

Идём обратно: 1 = 3 − 2 = 3 − (17 − 5 · 3) = 6 · 3 − 17 = 6 · (360 − 21 · 17) − 17 = 6 · 360 − 127 · 17. Значит, 17 · (−127) даёт остаток 1 по модулю 360, а −127 + 360 = 233. Проверка: 17 · 233 = 3961 = 11 · 360 + 1, d = 233.

В Python обратное число по модулю находят с помощью встроенной функции pow(e, -1, m), она умеет это с версии 3.8:

from math import gcd, lcm

# Учебный RSA на маленьких числах: только чтобы увидеть арифметику
p, q = 41, 73
n = p * q
phi = (p - 1) * (q - 1)       # функция Эйлера
lam = lcm(p - 1, q - 1)       # функция Кармайкла, её берёт стандарт PKCS #1
e = 17
if gcd(e, lam) != 1:
    raise ValueError("e должно быть взаимно простым с λ(n)")

d = pow(e, -1, lam)           # обратное к e по модулю λ(n)
d_phi = pow(e, -1, phi)       # тот же расчёт по φ(n), как в учебниках

print("n =", n, " φ(n) =", phi, " λ(n) =", lam)
print("открытый ключ (n, e):", (n, e), " закрытый ключ (n, d):", (n, d))
print("d по φ(n):", d_phi, " проверка e*d mod λ(n):", e * d % lam)

message = 1234                # сообщение: число меньше n
cipher = pow(message, e, n)   # шифрование открытым ключом
print("шифротекст:", cipher, " расшифровка:", pow(cipher, d, n), "и", pow(cipher, d_phi, n))

n = 2993  φ(n) = 2880  λ(n) = 360
открытый ключ (n, e): (2993, 17)  закрытый ключ (n, d): (2993, 233)
d по φ(n): 2033  проверка e*d mod λ(n): 1
шифротекст: 2280  расшифровка: 1234 и 1234

По λ(n) вышло d = 233, по φ(n) d = 2033, и оба значения возвращают исходное сообщение 1234. Если e выбрано неудачно, например e = 3 при λ(n) = 360, обратного числа нет и pow(3, -1, 360) падает с ValueError: base is not invertible for the given modulus. На такой случай в коде стоит проверка gcd(e, lam) != 1: она остановит программу с понятным текстом раньше.

Шифрование и расшифровка: расчёт по шагам

Сообщение m должно быть числом от 0 до n − 1:

• шифрование: c = m^e mod n;
• расшифровка: m = c^d mod n.

Степень 1234^17 ещё можно посчитать целиком, это число из 53 цифр. В рабочем ключе показатель d занимает около 2048 бит, и такая степень целиком не поместится ни в какую память. Остаток по модулю n берут на каждом шаге: показатель записывают в двоичном виде, число раз за разом возводят в квадрат по модулю n и перемножают те квадраты, где в показателе стоит единица. Функция ниже печатает каждый шаг:

def power_steps(base, exponent, modulus):
    """Возведение в степень по модулю с печатью каждого шага."""
    print(f"{base}^{exponent} mod {modulus}, показатель в двоичном виде {exponent:b}")
    result = 1
    square = base % modulus             # base^1, затем base^2, base^4, ...
    power = 1
    for digit in reversed(f"{exponent:b}"):
        if digit == "1":
            result = result * square % modulus
            print(f"  умножаем на {base}^{power} = {square} -> {result}")
        power *= 2
        if power <= exponent:
            square = square * square % modulus
            print(f"  {base}^{power} mod {modulus} = {square}")
    return result

n, e, d = 2993, 17, 233
cipher = power_steps(1234, e, n)
print("шифротекст:", cipher)
print()
message = power_steps(cipher, d, n)
print("расшифровка:", message, " pow() даёт:", pow(1234, e, n), pow(cipher, d, n))

1234^17 mod 2993, показатель в двоичном виде 10001
  умножаем на 1234^1 = 1234 -> 1234
  1234^2 mod 2993 = 2312
  1234^4 mod 2993 = 2839
  1234^8 mod 2993 = 2765
  1234^16 mod 2993 = 1103
  умножаем на 1234^16 = 1103 -> 2280
шифротекст: 2280

2280^233 mod 2993, показатель в двоичном виде 11101001
  умножаем на 2280^1 = 2280 -> 2280
  2280^2 mod 2993 = 2552
  2280^4 mod 2993 = 2929
  2280^8 mod 2993 = 1103
  умножаем на 2280^8 = 1103 -> 720
  2280^16 mod 2993 = 1451
  2280^32 mod 2993 = 1322
  умножаем на 2280^32 = 1322 -> 66
  2280^64 mod 2993 = 2765
  умножаем на 2280^64 = 2765 -> 2910
  2280^128 mod 2993 = 1103
  умножаем на 2280^128 = 1103 -> 1234
расшифровка: 1234  pow() даёт: 2280 1234

Строки «умножаем на 1234^1 = 1234 -> 1234» и «умножаем на 2280^1 = 2280 -> 2280» только записывают исходное число в результат, в счёт умножений их не берём. Для e = 17 (двоичное 10001) хватило четырёх возведений в квадрат и одного умножения: 1234 · 1103 mod 2993 = 2280. Для d = 233 (11101001) понадобилось семь квадратов и четыре умножения, и последнее, 2910 · 1103 mod 2993, вернуло 1234.

Стандарт PKCS #1 разрешает хранить закрытый ключ и в другом виде: p, q, dP = d mod (p − 1), dQ = d mod (q − 1) и qInv. Тогда расшифровка идёт двумя степенями с меньшими показателями по модулям p и q, а результаты склеивают по китайской теореме об остатках. Для нашего ключа dP = 33, dQ = 17.

Почему учебный RSA нельзя использовать

Формула c = m^e mod n в чистом виде называется «учебным» RSA (textbook RSA). Это только примитив, математическая операция: безопасность дают схемы, в которые её встраивают. У голой формулы две проблемы, обе видны в коде на настоящем ключе. Первая: шифрование детерминированное, одинаковые данные всегда дают одинаковое зашифрованное сообщение. Вторая: результат можно подправить, не зная ключа, потому что (m^e) · (3^e) = (3m)^e.

from cryptography.hazmat.primitives.asymmetric import rsa

private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
numbers = private_key.private_numbers()
n, e, d = numbers.public_numbers.n, numbers.public_numbers.e, numbers.d

def to_int(text):
    return int.from_bytes(text.encode("utf-8"), "big")

# 1. Одно и то же сообщение всегда даёт один и тот же шифротекст
intercepted = pow(to_int("отказать"), e, n)       # перехватили по сети
for guess in ["одобрить", "отказать", "на доработку"]:
    if pow(to_int(guess), e, n) == intercepted:    # хватает открытого ключа
        print("угадали ответ:", guess)

# 2. Шифротекст можно подправить, не зная ключа
amount = 5000
cipher = pow(amount, e, n)
forged = cipher * pow(3, e, n) % n                 # умножаем на шифр тройки
print("получатель расшифровал:", pow(forged, d, n))

угадали ответ: отказать
получатель расшифровал: 15000

В первой части злоумышленник знает, что ответ один из трёх, шифрует каждый вариант открытым ключом и сравнивает с перехваченным. Длина ключа здесь не помогает: перебирать надо всего три варианта, раскладывать n на множители не нужно. Во второй части он умножил перехваченное число на 3^e mod n, и получатель честно расшифровал 15000 вместо 5000.

Против таких атак нужно дополнение (padding): перед возведением в степень сообщение смешивают со случайными байтами по строгой схеме. Для шифрования берите OAEP, для подписи PSS. Старая схема PKCS #1 v1.5 осталась в стандарте только для совместимости. OAEP и PSS уже есть в криптографических библиотеках, свою схему дополнения не пишите. Учебные формулы с рабочими ключами не используйте.

Шифрование RSA с OAEP на Python

В библиотеке cryptography ключ создаёт rsa.generate_private_key(), открытый ключ берут из закрытого методом public_key(). Если Python отвечает ModuleNotFoundError: No module named 'cryptography', пакет стоит не в том окружении: разбор этой ошибки No module named есть отдельно.

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

oaep = padding.OAEP(
    mgf=padding.MGF1(algorithm=hashes.SHA256()),
    algorithm=hashes.SHA256(),
    label=None,
)
private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key = private_key.public_key()

message = "Встреча перенесена на четверг".encode("utf-8")
first = public_key.encrypt(message, oaep)
second = public_key.encrypt(message, oaep)
print("длина шифротекста:", len(first), "байт")
print("два шифротекста одинаковые:", first == second)
print("расшифровка:", private_key.decrypt(second, oaep).decode("utf-8"))

# Предел длины по стандарту: k - 2*hLen - 2, где k = 256 байт, hLen = 32 для SHA-256
limit = public_key.key_size // 8 - 2 * hashes.SHA256.digest_size - 2
public_key.encrypt(b"x" * limit, oaep)
print("предел", limit, "байт: такое сообщение зашифровалось")
try:
    public_key.encrypt(b"x" * (limit + 1), oaep)
except ValueError as error:
    print(limit + 1, "байт:", error)

длина шифротекста: 256 байт
два шифротекста одинаковые: False
расшифровка: Встреча перенесена на четверг
предел 190 байт: такое сообщение зашифровалось
191 байт: Encryption failed

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

Размер сообщения ограничивает формула стандарта: не больше k − 2·hLen − 2 байт, где k означает размер модуля, а hLen размер хеша. Про длину в тексте ошибки ни слова, а Encryption failed бывает и из-за слишком длинного сообщения. Сверьте его размер с таблицей, мы прогнали предел для трёх размеров ключа:

Кириллица в UTF-8 занимает два байта на букву, так что в ключ 2048 бит с SHA-256 влезет меньше сотни русских букв. Хеш при расшифровке должен быть тем же, что при шифровании: шифротекст с SHA-256, который расшифровывают с SHA-1, даёт ValueError: Decryption failed. Поэтому в примере один объект oaep передаётся и в encrypt(), и в decrypt().

Цифровая подпись RSA

Подпись RSA устроена так: от документа считают хеш, оформляют его по схеме PSS и возводят в степень d закрытым ключом. Проверяющий возводит подпись в степень e открытым ключом и сверяет результат с хешем документа. Что такое хеш и какие у него свойства, разобрано в статье о хеш-функциях.

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

pss = padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH)
private_key = rsa.generate_private_key(public_exponent=65537, key_size=3072)
public_key = private_key.public_key()

document = "Платёж 5000 руб. на счёт 40817".encode("utf-8")
signature = private_key.sign(document, pss, hashes.SHA256())
print("длина подписи:", len(signature), "байт")
print("вторая подпись того же текста совпала:",
      signature == private_key.sign(document, pss, hashes.SHA256()))

def check(data):
    try:
        public_key.verify(signature, data, pss, hashes.SHA256())
        return "подпись верна"
    except InvalidSignature:
        return "InvalidSignature: подпись не подходит"

print("исходный документ:", check(document))
print("сумма изменена:", check("Платёж 9000 руб. на счёт 40817".encode("utf-8")))

длина подписи: 384 байт
вторая подпись того же текста совпала: False
исходный документ: подпись верна
сумма изменена: InvalidSignature: подпись не подходит

Метод verify() ничего не возвращает: если подпись верна, он молча завершается, если нет, бросает InvalidSignature. Поэтому проверку оборачивают в try, сравнивать результат с True бессмысленно. Подписи одного текста разные, потому что PSS добавляет случайную соль.

Подпись по схеме PKCS #1 v1.5 тоже в ходу: на ней, например, алгоритм RS256 в JWT токенах. Атак на эту схему подписи не известно, но в новом коде берите PSS.

Безопасен ли RSA: атаки и защита

Разложение модуля на множители

Кто разложит n на p и q, тот посчитает d по формуле из первого примера. От этой атаки защищает размер ключа.

Слабый генератор случайных чисел

Если p и q получены плохим генератором, у двух разных ключей может совпасть один из множителей. Тогда наибольший общий делитель двух открытых модулей сразу выдаёт общее простое число: на двух модулях по 2048 бит math.gcd() нашёл его за 13 мкс. Такие ключи находили на роутерах и других сетевых устройствах, которые часто создают ключ сами при первом включении. Модуль random для ключей не годится, он не предназначен для задач безопасности. Ключи RSA создавайте библиотекой или ssh-keygen.

Атаки по сторонним каналам

Время ответа сервера может подсказать злоумышленнику, удалась ли расшифровка данных. Для схемы PKCS #1 v1.5 это открывает атаку с подобранным шифротекстом. В cryptography от неё защищает OpenSSL 3.2.0 и новее: вместо исключения он возвращает случайное значение. Онлайн-протоколы на расшифровке PKCS #1 v1.5 не стройте при любой версии OpenSSL.

Подмена открытого ключа: человек посередине

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

Какой длины ключ RSA выбрать

Стойкость ключа RSA сравнивают с размером ключа симметричного алгоритма шифрования, который ломается так же тяжело. Ключ 1024 бит и короче сейчас считается взламываемым, новые ключи делают от 2048 бит.

Новые ключи делайте от 3072 бит, а 2048 оставьте для ключей, которые сменятся до 2031 года. Данные, зашифрованные ключом 2048 бит, после этого срока ещё можно расшифровывать, но новые шифровать уже нет. Команда ssh-keygen -t rsa без параметра -b создаёт ключ 3072 бит: так вышло и в OpenSSH 10.5p1 из Git Bash, и в OpenSSH 9.5p1 из Windows.

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

RSA и AES: гибридная схема

Алгоритм RSA шифрует за раз не больше нескольких сотен байт и по скорости сильно уступает AES. На нашей машине (Core i9-9900KF, cryptography 50.0.2) расшифровка 190 байт ключом RSA 2048 бит заняла около 460 мкс, а AES-256-GCM шифровал и расшифровывал те же 190 байт примерно за 1 мкс на операцию. Шифрование открытым ключом быстрее расшифровки, около 23 мкс, но тоже в десятки раз медленнее AES.

Поэтому RSA обычно шифрует не сами данные, а случайный секретный ключ AES. Отправитель создаёт ключ AES, шифрует им файл или сообщение, а сам ключ из 32 байт шифрует открытым ключом получателя по схеме OAEP. Получатель расшифровывает ключ AES своим закрытым ключом, затем данные. Такую гибридную схему предлагали ещё авторы RSA в статье 1978 года. Как устроен AES, какой режим брать и почему нельзя повторять nonce, читайте в статье про шифрование AES.

Где используется RSA

• В HTTPS по протоколу TLS 1.3 статический обмен ключами через RSA убрали, а подписи RSA остались: ими подписаны многие сертификаты, и сервер с ключом RSA подписывает рукопожатие, а браузер проверяет подпись открытым ключом из сертификата.
• Для входа пользователя на сервер по SSH используют ключи RSA. С OpenSSH 8.8 подпись ssh-rsa с SHA-1 по умолчанию отключена, но менять ключ не нужно: тот же ключ подписывает с SHA-256 или SHA-512.
• Токены JWT с алгоритмами RS256 и PS256 подписывают закрытым ключом RSA, проверяют открытым.
• Стандарты электронной почты S/MIME и OpenPGP поддерживают RSA и для шифрования ключа сообщения, и для подписи письма.

Частые вопросы о шифровании RSA

Можно ли зашифровать данные закрытым ключом?

В формулах можно, так устроена подпись: s = m^d mod n. Но такое сообщение откроет любой, у кого есть открытый ключ, секрета оно не даёт. В cryptography у закрытого ключа нет метода encrypt(), вызов падает с AttributeError; есть sign() для подписи и decrypt() для расшифровки.

Что за число e = 65537?

Это простое число 2^16 + 1, в двоичном виде 10000000000000001: возведение в такую степень занимает 16 возведений в квадрат и одно умножение. В cryptography 50.0.2 параметр public_exponent принимает только 65537 или 3, тройка оставлена для совместимости, если её требуют старые системы. На public_exponent=17 библиотека отвечает ValueError: public_exponent must be either 3 (for legacy compatibility) or 65537. Almost everyone should choose 65537 here! Берите 65537.

Можно ли шифровать RSA онлайн?

Онлайн-калькулятор RSA подходит, чтобы проверить учебный пример на малых числах. Рабочий закрытый ключ в чужие сервисы не вставляйте: вы не проверите, что страница не отправит его на сервер.

Чем RSA отличается от ECC?

Оба алгоритма асимметричные. RSA опирается на сложность разложения на множители, ECC на задачу дискретного логарифма на эллиптической кривой. При той же стойкости ключи ECC намного короче: 256 бит против 3072 бит у RSA. Квантовый компьютер с алгоритмом Шора опасен для обоих.