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

По сути всё делается примерно так:

1) Выбираются два больших простых числа, назовём их p и q.
2) Вычисляется их произведение n = p * q. Это n является частью открытого ключа.
3) Вычисляется φ(n) = (p-1) × (q-1)
4) Выбирается некое число e (т.н. "экспонента"), которое не имеет общих делителей с φ(n) (наибольший общий делитель = 1).
e тоже является частью открытого ключа
5) вычисляется секретная экспонента d, такая, чтобы остаток от деления (e*d) на φ(n) был 1

Таким образом, мы имеем ключи:

открытый ключ - числа n и e
закрытый ключ - числа n и d

Шифрование

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

Шифрованное сообщение будет

с = m^e mod n

Расшифровка

Расшифровать с можно так:

m = c^d mod n

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

package main

import (
    "fmt"
    "math/big"
)

func main() {
    // В реальности числа должны быть намного больше
    p := big.NewInt(61)
    q := big.NewInt(53)
    
    // Вычисляем n = p * q
    n := new(big.Int).Mul(p, q)
    
    // Вычисляем φ(n) = (p-1) * (q-1)
    p1 := new(big.Int).Sub(p, big.NewInt(1))
    q1 := new(big.Int).Sub(q, big.NewInt(1))
    phi := new(big.Int).Mul(p1, q1)
    
    // Выбираем e (взаимно простое с φ(n))
    e := big.NewInt(17)
    
    // Находим d (мультипликативное обратное к e по модулю φ(n))
    d := new(big.Int)
    d.ModInverse(e, phi)
    
    fmt.Printf("Открытый ключ (n=%v, e=%v)\n", n, e)
    fmt.Printf("Закрытый ключ (n=%v, d=%v)\n", n, d)
    
    // Пример шифрования сообщения
    message := big.NewInt(129)
    
    // Проверяем, что сообщение меньше модуля
    if message.Cmp(n) >= 0 {
        fmt.Printf("\nОшибка: сообщение %v больше или равно модулю %v\n", message, n)
        fmt.Printf("В этом примере сообщение должно быть меньше %v\n", n)
        return
    }
    
    fmt.Printf("\nИсходное сообщение: %v\n", message)
    
    // Шифруем: c = m^e mod n
    encrypted := new(big.Int).Exp(message, e, n)
    fmt.Printf("Зашифрованное сообщение: %v\n", encrypted)
    
    // Расшифровываем: m = c^d mod n
    decrypted := new(big.Int).Exp(encrypted, d, n)
    fmt.Printf("Расшифрованное сообщение: %v\n", decrypted)
}

Безопасность RSA основана на сложности факторизации (разложения на множители) больших чисел. Зная только открытый ключ (n,e), практически невозможно вычислить закрытый ключ d без знания p и q.

Прикол в том, что квантовые компьютеры способны эффективно раскладывать числа на множители с помощью алгоритма Шора. Получив p и q, можно легко вычислить φ(n) и все остальные компоненты для взлома шифра.

🫥 Cross Join
⠀