Асимметрия и RSA

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

Идея

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

Сразу оговорка, которая убережёт от популярной путаницы. Красивая симметрия «зашифруй одним ключом, расшифруй другим, и наоборот» это особенность учебного RSA, где обе операции сводятся к одному и тому же возведению в степень. Асимметрия вообще этого не обещает: подпись это не шифрование закрытым ключом, а отдельная операция со своей математикой (в ECDSA из следующих уроков никакого шифрования нет вовсе, там только точки и скаляры). Честная общая формула такая: открытым ключом шифруют и проверяют подписи, закрытым расшифровывают и подписывают. RSA просто удачно совместил обе роли в одной формуле, и за это его удобно разбирать первым.

Проблема распространения ключей растворяется. Бобу больше не нужно тайно передавать Алисе секрет: Алиса публикует свой открытый ключ, Боб шифрует им, и подслушивающий с тем же открытым ключом сделать ничего не может. Вместо N^2 симметричных секретов сети из N участников нужно N пар ключей.

Держится это на односторонней функции с лазейкой (trapdoor function). Вперёд считать легко, назад без секрета невозможно за разумное время, а с секретом снова легко. У RSA эта функция стоит на умножении: перемножить два больших простых числа просто, а разложить их произведение обратно на множители очень трудно. Лазейка это знание самих простых.

Немного модульной арифметики

RSA это арифметика остатков. Модульная арифметика работает с остатками от деления на модуль n, как часовая стрелка по кругу: 15 mod 12 = 3. Нам нужны три кирпича.

Первый, возведение в степень по модулю: m^e mod n. Считать его в лоб через огромное m^e нельзя, число не влезет ни в какой тип. Берут остаток на каждом шаге и идут методом «возведи в квадрат и умножь», за log e умножений вместо e.

Второй, функция Эйлера φ(n): сколько чисел от 1 до n взаимно просты с n. Для произведения двух разных простых n = p·q она равна (p−1)·(q−1). На ней стоит теорема Эйлера, из которой и следует, что RSA расшифровывает то же, что зашифровал.

Третий, обратный по модулю: для e найти такое d, что e·d ≡ 1 (mod φ(n)). Его ищут расширенным алгоритмом Евклида. Это и будет закрытая экспонента.

RSA по шагам

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

1. Выбери два больших простых p и q, посчитай n = p·q (это модуль) и φ(n) = (p−1)·(q−1).
2. Выбери открытую экспоненту e, взаимно простую с φ(n) (на практике почти всегда 65537).
3. Найди закрытую экспоненту d = e⁻¹ mod φ(n).
4. Открытый ключ это пара (n, e), закрытый это d (плюс p, q, которые надо забыть или беречь как секрет).

Почему e почти всегда именно 65537, а не любое подходящее число. Это 2^16 + 1, в двоичном виде 10000000000000001, всего две единицы. Возведение в такую степень это шестнадцать возведений в квадрат и одно умножение, шифрование летает. Маленькие e вроде 3 ещё быстрее, но открывают атаки на короткую экспоненту, о них ниже. 65537 это компромисс: достаточно большое, чтобы те атаки не работали, и достаточно «дырявое» по битам, чтобы шифрование оставалось дешёвым. Бонус: 65537 простое, так что gcd(e, φ(n)) = 1 выполняется почти всегда само собой.

Шифрование и расшифровка это одно и то же возведение в степень, разными экспонентами:

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

Сообщение m это число меньше n. Почему круг замыкается, гарантирует теорема Эйлера: m^(e·d) ≡ m (mod n), потому что e·d ≡ 1 (mod φ(n)). Безопасность в том, что найти d из открытого (n, e) это по сути разложить n на p и q, а это та самая трудная задача факторизации.

Соберём это на Rust с маленькими числами, чтобы всё было видно. Возведение в степень по модулю руками:

/// m^e mod n методом «возведи в квадрат и умножь».
fn modpow(mut base: u128, mut exp: u128, modulus: u128) -> u128 {
    if modulus == 1 {
        return 0;
    }
    let mut result = 1u128;
    base %= modulus;
    while exp > 0 {
        if exp & 1 == 1 {
            result = result * base % modulus; // подмешиваем текущий квадрат
        }
        exp >>= 1;
        base = base * base % modulus; // следующий квадрат
    }
    result
}

/// Обратный по модулю через расширенный алгоритм Евклида: a^(-1) mod m.
fn mod_inverse(a: u128, m: u128) -> u128 {
    let (mut old_r, mut r) = (a as i128, m as i128);
    let (mut old_s, mut s) = (1i128, 0i128);
    while r != 0 {
        let q = old_r / r;
        (old_r, r) = (r, old_r - q * r);
        (old_s, s) = (s, old_s - q * s);
    }
    // old_s это коэффициент при a; приводим в диапазон [0, m).
    let m = m as i128;
    ((old_s % m + m) % m) as u128
}

fn main() {
    // Учебные простые. В проде это два случайных простых по 1024+ бит.
    let (p, q) = (61u128, 53u128);
    let n = p * q; //  3233 это модуль
    let phi = (p - 1) * (q - 1); //  3120
    let e = 17u128; //  gcd(e, phi) == 1
    let d = mod_inverse(e, phi); //  2753

    let m = 65u128; // сообщение как число, обязательно m < n
    let c = modpow(m, e, n); //  2790 это шифротекст
    let back = modpow(c, d, n); //  снова 65

    println!("открытый ключ (n={n}, e={e}), закрытый d={d}");
    println!("m={m} -> c={c} -> {back}");
    assert_eq!(back, m);
}

Запусти: 65 уезжает в 2790 и возвращается обратно. Это вся механика RSA. С настоящими числами на 2048 бит u128 не хватит, и в Rust берут num-bigint или готовый крейт rsa, но арифметика та же, меняется только размер чисел.

Покрути это руками. Выбери два простых, смотри, как складываются n и φ, как из φ рождается закрытая экспонента d, и прогони сообщение по кругу. А потом нажми «атаковать»: при крошечном n факторизация мгновенно вернёт p, q, а вместе с ними φ и тот же самый d. Вся защита RSA держится только на том, что для боевого n этот перебор не закончится никогда.

простое p: 1111131719232931374143475361простое q: 1311131719232931374143475361сообщение m: 9

открытый ключn = 11·13 = 143e = 7

Можно публиковать. Им шифруют.

закрытый ключφ = (11−1)·(13−1) = 120d = e⁻¹ mod φ = 103

Секрет. d рождается из φ, а φ требует p и q.

m9

^7 mod 143шифруем

c48

^103 mod 143расшифровываем

m'9

Круг замкнулся: 9 уехало в 48 и вернулось обратно. Это вся механика RSA, дальше меняется только размер чисел.

атаковать ключ (факторизовать n)

Обрати внимание на одну деталь из виджета: d вычисляется из φ, а φ это (p−1)·(q−1). Значит, кто знает p и q, мгновенно получает закрытый ключ. Поэтому p и q после генерации либо стирают, либо берегут как сам секрет, а вся стойкость сводится к одному вопросу: можно ли разложить n обратно на множители.

Есть и обратная польза от знания p и q. Расшифровка c^d mod n это возведение в огромную степень по большому модулю, она в разы медленнее шифрования с маленьким e. Поэтому в проде владелец ключа держит p и q при себе и считает не сразу по модулю n, а отдельно по p и отдельно по q, через китайскую теорему об остатках (CRT). Числа вдвое короче, а время растёт почти кубически от длины, так что расшифровка ускоряется примерно вчетверо. Это ещё одна причина не выкидывать p и q, а хранить их в закрытом ключе.