Ключи
Как находится d: расширенный алгоритм Евклида
Каждая строка получается делением двух строк над ней. В строке с остатком 1 последний столбец — это d (если он отрицателен, прибавьте φ(n)).
| Частное | Остаток | Коэффициент при e |
|---|
Сообщение
Передаётся по сети
| Бит | В квадрат | Умножить на m |
|---|
Взлом ключа
Демонстрация шифрования RSA
RSA позволяет любому запереть сообщение вашим открытым ключом, а открыть его можете только вы — своим закрытым ключом. За этим стоят несколько строк школьной арифметики: два простых числа, умножение, остаток и хитроумное обратное число. Постройте пару ключей из выбранных вами простых чисел, зашифруйте и расшифруйте сообщение символ за символом, подпишите его, чтобы любой мог проверить, что оно от вас, а затем сыграйте роль атакующего и разложите n на множители, чтобы увидеть, почему настоящим ключам нужны сотни цифр. Выберите два простых числа p и q или нажмите «Новые простые». Приложение строит открытый ключ (e, n) и закрытый ключ d и показывает, как расширенный алгоритм Евклида находит d. Введите сообщение: каждый символ шифруется открытым ключом и расшифровывается закрытым. Нажмите на строку, чтобы увидеть степень, вычисленную повторным возведением в квадрат. Переключитесь на «Подписать», чтобы вместо этого подписывать закрытым ключом, и нажмите «Разложить n», чтобы увидеть, как быстро ломаются маленькие ключи.
Как это работает
- Введите два простых числа p и q или выберите размер и нажмите «Новые простые»; приложение вычислит n, φ(n), e и d и покажет, как находится d.
- Введите сообщение и выберите «Зашифровать» или «Подписать». Каждый символ превращается в число и возводится в степень по модулю n; нажмите на строку, чтобы увидеть повторное возведение в квадрат.
- Нажмите «Разложить n», чтобы Ева разложила n на два простых множителя и восстановила закрытый ключ.
Как работают ключи
Перемножьте два простых числа: n = p × q. При p = 61 и q = 53 получаем n = 3233. Число φ(n) = (p − 1)(q − 1) = 3120 показывает, сколько чисел меньше n не имеют с ним общих делителей, и вычислить его может только тот, кто знает p и q. Выберите e = 17, не имеющее общих делителей с 3120, и найдите d, при котором e × d на 1 больше числа, кратного φ(n): здесь d = 2753, потому что 17 × 2753 = 46801 = 15 × 3120 + 1. Опубликуйте (e, n) и оставьте d себе. Сообщение m превращается в c = mᵉ mod n, а теорема Эйлера гарантирует, что cᵈ mod n снова даёт m.
Почему его трудно взломать
Всё, что нужно атакующему, спрятано в множителях n. При n = 3233 это не защита: перебор нечётных делителей находит 53 примерно за два десятка попыток. Но работа растёт как квадратный корень из n. Модуль длиной 2048 бит содержит около 617 цифр, и ни один известный метод ни на одном существующем сегодня компьютере не может разложить его на множители за разумное время. Подпись — это RSA в обратную сторону: s = mᵈ mod n можно получить только закрытым ключом, а любой может проверить, что sᵉ mod n снова даёт m.
Часто задаваемые вопросы
Почему никто не может вычислить d по открытому ключу?
Чтобы найти d, нужно φ(n) = (p − 1)(q − 1), а чтобы получить φ(n), нужны p и q. Восстановить их по n значит разложить n на множители, а для чисел из сотен цифр быстрый метод неизвестен. Демонстрация позволяет разложить игрушечные ключи за долю секунды, и это как раз показывает, почему настоящие ключи такие большие.
Почему сообщение шифруется по одному символу?
Потому что игрушечные ключи маленькие: RSA может зашифровать только число меньше n. При n = 3233 код любого символа помещается, а целое предложение — нет. Настоящий RSA использует модуль длиной 2048 бит или больше, дополняет сообщение случайными байтами, чтобы одно и то же сообщение никогда не шифровалось дважды одинаково, и на практике шифрует только короткий ключ для более быстрого шифра, например AES.
Что делает повторное возведение в квадрат?
Оно вычисляет огромные степени вроде m²⁷⁵³ mod n, ни разу не выписывая огромное число. Запишите показатель в двоичном виде и пройдите по его битам: для каждого бита возводите текущий результат в квадрат, а для каждой единицы умножайте на m, каждый раз беря остаток по модулю n. Показателю длиной 2048 бит нужно всего около 2048 возведений в квадрат.
Чем шифрование отличается от подписи?
Шифрование использует открытый ключ получателя, чтобы отменить его мог только закрытый ключ получателя. Подпись использует закрытый ключ отправителя, чтобы любой мог проверить её открытым ключом отправителя и знать, что сообщение пришло от владельца этого ключа и не было изменено.
Отправляется ли куда-нибудь моё сообщение?
Нет. Всё вычисляется в вашем браузере, а ваши простые числа и сообщение остаются в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор