RSA: математика и реализация

Зачем это нужно в блокчейне

RSA — первый практичный алгоритм с открытым ключом. Хотя блокчейны используют ECC (следующий урок), RSA проще для понимания концепции: два ключа — один открытый, один секретный.

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

RSA назван в честь Ривеста, Шамира и Адлемана, которые опубликовали алгоритм в 1977 году. Это первая практическая реализация идеи асимметричного шифрования Диффи и Хеллмана.

Интуитивное объяснение

Представьте почтовый ящик с замком. Любой может бросить письмо в щель (зашифровать открытым ключом), но только владелец ключа может открыть ящик и прочитать письмо (расшифровать секретным ключом).

Математическая основа: умножить два больших простых числа легко, а разложить произведение обратно на множители — вычислительно сложно.

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

Пройдем генерацию ключей пошагово на маленьких числах:

Алгоритм по шагам

1. Выбираем два простых числа p и q (в реальности — по 1024+ бит каждое)
2. Вычисляем модуль n = p * q (это часть открытого и секретного ключей)
3. Вычисляем функцию Эйлера phi(n) = (p-1)(q-1)
4. Выбираем открытую экспоненту e, взаимно простую с phi(n)
5. Вычисляем секретную экспоненту d = e^(-1) mod phi(n)

Открытый ключ: (e, n) — можно публиковать Секретный ключ: (d, n) — хранить в тайне

Шифрование и дешифрование

Формулы просты:

• Шифрование: c = m^e mod n
• Дешифрование: m = c^d mod n

Почему это работает? Благодаря теореме Эйлера:

m^(e*d) mod n = m^(1 + k*phi(n)) mod n = m * (m^phi(n))^k mod n = m * 1^k mod n = m

Произведение e * d дает 1 по модулю phi(n), поэтому шифрование и дешифрование — обратные операции.

Код на Python

Учебная реализация (маленькие простые числа)

def generate_rsa_keypair(p: int, q: int, e: int = 17):
    """Генерация RSA ключей (учебная версия с маленькими числами)."""
    n = p * q
    phi = (p - 1) * (q - 1)

    # Проверяем, что e взаимно просто с phi
    from math import gcd
    assert gcd(e, phi) == 1, f"e={e} не взаимно просто с phi={phi}"

    # Вычисляем d = e^(-1) mod phi
    d = pow(e, -1, phi)

    public_key = (e, n)
    private_key = (d, n)
    return public_key, private_key

def rsa_encrypt(m: int, public_key: tuple) -> int:
    """c = m^e mod n"""
    e, n = public_key
    return pow(m, e, n)

def rsa_decrypt(c: int, private_key: tuple) -> int:
    """m = c^d mod n"""
    d, n = private_key
    return pow(c, d, n)

# Пример
pub, priv = generate_rsa_keypair(p=61, q=53, e=17)
print(f"Открытый ключ:  {pub}")
print(f"Секретный ключ: {priv}")

message = 42
ciphertext = rsa_encrypt(message, pub)
decrypted = rsa_decrypt(ciphertext, priv)
print(f"{message} -> шифрование -> {ciphertext} -> дешифрование -> {decrypted}")
assert decrypted == message

Продакшен реализация (pycryptodome + OAEP)

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# Генерация ключей RSA-2048
key = RSA.generate(2048)
private_key = key
public_key = key.publickey()

# Шифрование с OAEP (безопасный паддинг)
cipher = PKCS1_OAEP.new(public_key)
message = "Приватный ключ кошелька".encode('utf-8')
ciphertext = cipher.encrypt(message)

# Дешифрование
decipher = PKCS1_OAEP.new(private_key)
decrypted = decipher.decrypt(ciphertext)
print(f"Расшифровано: {decrypted.decode('utf-8')}")

Почему OAEP? «Учебный» RSA (m^e mod n) уязвим к нескольким атакам: если m маленькое, шифротекст предсказуем; одинаковые сообщения дают одинаковый шифротекст. OAEP добавляет случайный паддинг, делая каждое шифрование уникальным.

Безопасность RSA

Безопасность RSA основана на задаче факторизации: зная n, вычислительно сложно найти p и q.

Почему факторизация сложна

• Умножение: O(n^2) битовых операций — легко
• Факторизация: лучший известный алгоритм (Number Field Sieve) работает за субэкспоненциальное время — сложно

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

Математический уровень

Почему e = 65537?

Число 65537 = 2^16 + 1 — простое число Ферма. У него только два бита установлены в единицу (10000000000000001 в двоичной), что делает возведение в степень m^e быстрым (всего 17 умножений по алгоритму square-and-multiply).

CRT оптимизация

В продакшене дешифрование ускоряется в ~4 раза с помощью Китайской теоремы об остатках (CRT). Вместо одного возведения в степень по модулю n выполняются два по модулю p и q (меньшие числа):

mp = c^(d mod (p-1)) mod p
mq = c^(d mod (q-1)) mod q
m = CRT(mp, mq)  # объединяем результаты

Атаки на RSA

RSA vs ECC

Блокчейны выбрали ECC из-за компактности: каждая транзакция содержит подпись, и экономия 200 байт на транзакцию критична при миллионах транзакций.

Практика

Откройте Jupyter notebook 05-rsa.ipynb для практических упражнений:

• Реализация RSA от нуля с маленькими простыми числами
• Шифрование и подпись с pycryptodome
• Сравнение размеров ключей RSA vs ECC
• Челлендж: атака Винера на маленький секретный показатель

Что дальше

RSA показал, как работает асимметричная криптография. Но блокчейны используют эллиптические кривые — они обеспечивают такую же безопасность с ключами в 8 раз короче. В следующем уроке разберем математику эллиптических кривых и поймем, как работают подписи Bitcoin и Ethereum.