RSA простыми словами
Каждый раз, когда браузер показывает замочек, сообщение подписывается или программа проверяет обновление, работает криптография с открытым ключом, и RSA — самая известная её разновидность. Её идея в том, что ключ, который запирает сообщение, можно опубликовать, а ключ, который его открывает, остаётся закрытым. Удивительно, но вся система держится на арифметике из школьной программы: простых числах, умножении и остатках.
Какую задачу решает RSA
Более старые шифры, от сдвига Цезаря до современного AES, используют один и тот же ключ, чтобы запирать и отпирать, поэтому обеим сторонам сначала нужно тайно договориться о секретном ключе. Криптография с открытым ключом убирает этот шаг. У каждого есть два ключа: открытый, которым любой может зашифровать сообщение для его владельца, и закрытый, который есть только у владельца и только с помощью которого это сообщение можно расшифровать. Уитфилд Диффи и Мартин Хеллман описали эту идею в 1976 году, а год спустя Рон Ривест, Ади Шамир и Леонард Адлеман из MIT нашли способ её реализовать, названный RSA по их инициалам.
Создание ключей
Выберите два больших простых числа p и q и перемножьте их: n = p × q. Вычислите φ(n) = (p − 1)(q − 1) — функцию Эйлера, которая показывает, сколько чисел меньше n не имеют с ним общих делителей. Выберите открытую экспоненту e, не имеющую общих делителей с φ(n); обычно берут 65537. Затем найдите закрытую экспоненту d, такую что e × d при делении на φ(n) даёт остаток 1. Расширенный алгоритм Евклида делает это быстро. Открытый ключ — пара (e, n), закрытый ключ — d. При p = 61 и q = 53 получается n = 3233, φ(n) = 3120, e = 17 и d = 2753.
Шифрование и расшифровка
Сначала сообщение превращают в число m меньше n. Чтобы зашифровать его, вычислите c = mᵉ mod n — остаток от деления mᵉ на n. Чтобы расшифровать, вычислите cᵈ mod n. Теорема Эйлера гарантирует, что получится снова m, потому что e × d на единицу больше числа, кратного φ(n). С ключами выше буква A с кодом 65 превращается в 65¹⁷ mod 3233 = 2790, а 2790²⁷⁵³ mod 3233 снова равно 65. Такие большие степени никогда не выписывают целиком: повторное возведение в квадрат вычисляет их с одним возведением в квадрат на каждый бит показателя, беря остаток на каждом шаге.
Цифровые подписи
RSA работает и в обратную сторону. Возведение сообщения в закрытую экспоненту, s = mᵈ mod n, даёт подпись, которую может создать только владелец ключа. Любой может проверить её открытым ключом: если sᵉ mod n снова даёт m, сообщение пришло от владельца d и не было изменено по дороге. На практике подписывают не само сообщение, а его короткий хеш. Такие подписи защищают обновления программ, защищённые сайты и электронные документы.
Почему это надёжно
Все видят n и e. Чтобы найти d, атакующему нужно φ(n), а чтобы найти φ(n), нужны p и q, так что взлом RSA сводится к разложению n на множители. Перемножение двух простых чисел занимает у компьютера долю микросекунды; разложить произведение обратно на них, как считается, чрезвычайно трудно. Самое большое из разложенных на сегодня чисел конкурса RSA, RSA-250 в 2020 году, имеет 829 бит, и на его разложение ушло около 2700 лет компьютерного времени. Ключи, используемые сегодня, имеют не менее 2048 бит, это около 617 цифр.
Секрет, открытый дважды
В 1973 году, за четыре года до RSA, британский математик Клиффорд Кокс нашёл ту же схему во время работы в спецслужбе GCHQ, развив идею своего коллеги Джеймса Эллиса. Работа была засекречена и обнародована только в 1997 году. Сам RSA был запатентован в США в 1983 году; патент истёк в сентябре 2000 года, через две недели после того, как алгоритм был передан в общественное достояние.
RSA на практике
Настоящий RSA никогда не шифрует текст напрямую. Сообщение дополняют случайными байтами по схеме вроде OAEP, чтобы одно и то же сообщение каждый раз шифровалось по-разному и никакие закономерности не просачивались. Поскольку RSA медленный, его в основном используют для обмена или защиты короткого ключа для быстрого симметричного шифра, например AES, или для подписи. Достаточно большие квантовые компьютеры могли бы быстро разложить n на множители с помощью алгоритма Шора 1994 года, поэтому рядом с RSA сейчас внедряются новые постквантовые методы.
Исследуйте сами
Откройте демонстрацию шифрования RSA, чтобы строить ключи из своих простых чисел или из случайных длиной от 2 до 8 цифр, смотреть, как расширенный алгоритм Евклида строка за строкой находит d, шифровать или подписывать сообщение символ за символом и следить за повторным возведением в квадрат для любого символа. Затем позвольте Еве разложить n на множители и посмотрите, как нужное ей время растёт с размером простых чисел.
Часто задаваемые вопросы
Зачем RSA простые числа?
Потому что φ(n) легко вычислить, только если знать, как n раскладывается на простые множители. Для n = p × q с простыми p и q имеем φ(n) = (p − 1)(q − 1). Кроме того, простые множители делают n настолько трудным для разложения, насколько это возможно при его размере, ведь у него вообще нет маленьких делителей.
Почему e часто равно 65537?
65537 = 2¹⁶ + 1 — простое число, и в его двоичной записи всего две единицы, поэтому шифрование с ним требует лишь 16 возведений в квадрат и одного умножения. Кроме того, оно достаточно велико, чтобы избежать слабостей очень маленьких показателей, например 3.
Чем RSA отличается от протокола Диффи — Хеллмана?
Протокол Диффи — Хеллмана позволяет двум людям договориться об общем секретном ключе по открытому каналу; сам по себе он ничего не шифрует и не подписывает. RSA шифрует и подписывает напрямую с помощью пары ключей. Оба опираются на задачи, которые легко решаются в одну сторону и трудно в другую: на разложение на множители в случае RSA и на дискретное логарифмирование в случае Диффи — Хеллмана.
Можно ли использовать ключи из демонстрации для настоящего шифрования?
Нет. Её простые числа содержат не больше двенадцати цифр, поэтому любой созданный ею ключ можно разложить на множители за секунды или быстрее, а каждый символ шифруется отдельно, без дополнения. Она нужна, чтобы увидеть, как работает RSA, а не чтобы что-то защищать.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть демонстрацию шифрования RSA