Идея RSA простыми словами

RSA — самый известный асимметричный алгоритм. Его надёжность держится на одной школьной операции: умножении.

Откуда название

RSA назван по фамилиям трёх создателей — Ривеста, Шамира и Адлемана, опубликовавших алгоритм в 1977 году. Он до сих пор используется в HTTPS, цифровых подписях и многом другом.

Главный секрет RSA: лёгкое умножение, трудное разложение

Идея простая. Возьмём два больших простых числа и перемножим — получится одно большое число n. Перемножить просто. А вот обратная задача — по числу n найти те самые два простых множителя — невероятно сложна, если n большое. Эта задача называется факторизацией.

import time

def factorize(n):
    for i in range(2, n):
        if n % i == 0:
            return i, n // i
    return None

# два простых числа
n = 1009 * 1013
print("Опубликованное n =", n)

start = time.time()
p, q = factorize(n)
print("Разложилось на:", p, "и", q)
print("Заняло (мс):", round((time.time() - start) * 1000, 2))

Вывод:

Опубликованное n = 1022117
Разложилось на: 1009 и 1013
Заняло (мс): около 0.3

Здесь числа маленькие, и компьютер разложил n мгновенно. Но в реальном RSA простые числа имеют по 300 и более цифр. Тогда даже все компьютеры мира не разложат n за миллиарды лет.

Как из этого получается шифрование

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

p, q = 61, 53
n = p * q                 # 3233
e = 17                    # открытая экспонента
d = 2753                  # закрытая экспонента (вычислена заранее)

message = 65              # "буква" как число

cipher = pow(message, e, n)     # шифруем открытым ключом (e, n)
decrypted = pow(cipher, d, n)   # расшифровываем закрытым (d, n)

print("Сообщение:", message)
print("Шифр-текст:", cipher)
print("Расшифровано:", decrypted)

Вывод:

Сообщение: 65
Шифр-текст: 2790
Расшифровано: 65

Сообщение 65 зашифровалось в 2790 с помощью открытого ключа (e=17, n=3233), а закрытый ключ (d=2753, n=3233) вернул его обратно. Магия в том, что e можно публиковать, а d вычислить из него без знания p и q невозможно.

Почему нельзя считать RSA вручную для реальной защиты

Игрушечный RSA на маленьких числах — отличная учёба, но НЕ защита. Для реальных задач всегда используют проверенные библиотеки с числами нужного размера и правильным дополнением (padding).