Боб печатает ключ для писем к нему прямо в газете. Как сделать, чтобы этим ключом можно было запереть письмо, но нельзя открыть?
Боб хочет, чтобы ему могли писать тайно — кто угодно, даже люди, которых он никогда не видел. Он печатает в газете ключ: «шифруйте письма мне вот этим». Газету читает и Ева. Может ли быть так, что Ева держит в руках тот же ключ и всё равно не прочтёт ни одного письма Бобу?
Звучит как бессмыслица. В любом привычном шифре, от Цезаря до AES, один и тот же ключ и запирает, и отпирает. Кто знает, как зашифровать, знает и как расшифровать: достаточно проделать всё в обратном порядке. Опубликовать такой ключ — значит опубликовать сам секрет.
В 1976 году Диффи и Хеллман показали, как двоим договориться об общем ключе при всех. Но договариваться приходится с каждым собеседником заново, и оба должны быть на связи одновременно. В той же статье они описали мечту получше: шифр с двумя разными ключами — открытым, чтобы запирать, и закрытым, чтобы отпирать. Как такой шифр построить, они не знали.
RSA — шифр с открытым ключом: ключей у Боба два, и они разные. Открытый ключ Боб раздаёт всем, закрытый не показывает никому. Тот же принцип есть в быту — навесной замок.
Боб раздаёт всем открытые навесные замки, а ключ от них держит у себя. Алиса кладёт письмо в ящик и защёлкивает на нём замок Боба: для этого ключ не нужен. Ящик едет к Бобу обычной почтой. У Евы тоже есть замок Боба, но замок умеет только защёлкиваться.
Упрощение: настоящий замок можно вскрыть отмычкой. У числового замка RSA отмычка тоже есть — разложить n на множители, но на огромных числах она не срабатывает.
Запирают в RSA той же операцией, что в Диффи — Хеллмане: возводят число в степень и берут остаток от деления. Новое в другом: модуль n Боб собирает сам из двух тайных простых чисел, и именно они позволяют ему вычислить ключ. Все примеры ниже — на числах игры, где n = 33.
Боб выбирает два случайных простых числа p и q — таких, что делятся только на 1 и на себя. В настоящих ключах каждое длиной 1024 бита и больше, это около 309 десятичных цифр. Их произведение n = p × q Боб раздаёт, а сами p и q держит в тайне. Перемножить два числа легко. Найти по произведению, из каких простых оно сложено, трудно, если числа огромные.
Пример: p = 3, q = 11, n = 3 × 11 = 33.
Боб вычисляет φ = (p − 1)(q − 1) и выбирает степень замка e — число, у которого нет общих делителей с φ. В настоящих ключах почти всегда e = 65537. По e и φ Боб находит степень ключа d: такую, что e · d при делении на φ даёт остаток 1. Открытый ключ — пара (n, e), закрытый — d. Чтобы найти d, нужно знать φ, а чтобы найти φ, нужны p и q.
Пример: φ = 2 × 10 = 20, e = 3, d = 7, ведь 3 · 7 = 21 = 1 · 20 + 1.
Письмо — это число m меньше n: текст сначала переводят в числа. Алиса берёт открытый ключ Боба и вычисляет c = me mod n. Это и есть «защёлкнуть замок». Степень считают по этапам: умножили — взяли остаток, умножили — взяли остаток. Ответ тот же, что если возвести в степень целиком, но числа не растут. Иначе со степенью 65537 и числами из сотен цифр не справился бы ни один компьютер. Число c отправляют открыто: без d оно бесполезно.
Пример: m = 4. 4 × 4 = 16; 16 × 4 = 64 = 1 · 33 + 31. Значит, c = 31.
Боб возводит c в свою тайную степень d по тому же модулю и получает исходное m. Никакой новой операции нет: способ тот же, другая только степень.
Пример: 317 mod 33 по этапам: 31 · 31 = 961 → 4; 4 · 31 = 124 → 25; 25 · 31 = 775 → 16; 16 · 31 = 496 → 1; 1 · 31 = 31; 31 · 31 = 961 → 4. Боб получил m = 4.
Алиса возвела m в степень e, Боб возвёл результат в степень d. Вместе это me·d. А e · d Боб подобрал так, чтобы оно было на 1 больше, чем φ, взятое сколько-то раз. У остатков по модулю n есть свойство (это теорема Эйлера): такая степень возвращает любое число на своё место. Поэтому cd = me·d = m mod n. Можно представить это так: замок переставляет числа от 0 до n − 1, как карты в колоде, и у каждого числа своё место. Ключ ведёт по тем же линиям обратно.
Пример: 3 · 7 = 21 = 1 · 20 + 1, и 421 mod 33 = 4.
Рональд Ривест, Ади Шамир и Леонард Адлеман из MIT год искали функцию, о которой мечтали Диффи и Хеллман. Ривест и Шамир предлагали схемы, Адлеман их ломал. Рабочая схема на двух простых числах появилась в апреле 1977 года, буквы RSA — первые буквы их фамилий. В августе Мартин Гарднер рассказал о шифре в Scientific American и опубликовал задачу: число из 129 цифр и зашифрованную им фразу, приз — 100 долларов. Её решили только в 1994 году: около 600 добровольцев восемь месяцев раскладывали число по интернету. Фраза оказалась «The Magic Words are Squeamish Ossifrage».
Британская GCHQ опередила MIT и здесь. Молодой математик Клиффорд Кокс в 1973 году прочитал записку коллеги Джеймса Эллиса о «несекретном шифровании» и за один вечер нашёл ту же схему на двух простых числах — почти за четыре года до Ривеста, Шамира и Адлемана. Патент MIT на RSA действовал в США до сентября 2000 года, после этого алгоритм стал свободным.
RSA и сегодня работает рядом с вами, хотя теперь он чаще подписывает, чем шифрует:
Сертификаты большинства сайтов подписаны по RSA, и браузер этой подписью проверяет, что ключ принадлежит именно этому сайту. А передавать ключ соединения через RSA в TLS 1.3 запретили: теперь это работа обмена Диффи — Хеллмана.
При первом подключении сервер или маршрутизатор показывает отпечаток своего открытого ключа, и часто это ключ RSA. Им устройство доказывает, что вы говорите именно с ним, а не с подменой.
Письма с PGP, подписи программ и обновлений, банковские карты с чипом — везде, где нужно проверить автора, ни разу с ним не встречаясь.
Оба алгоритма — из криптографии с открытым ключом, и оба считают степени по модулю, поэтому их часто путают. Разница в том, что они делают. В обмене Диффи — Хеллмана Алиса и Боб вдвоём обмениваются открытыми числами и каждый у себя вычисляет общий ключ. Там ничего не шифруется, и оба должны участвовать одновременно. В RSA у Боба уже есть замок, розданный всем заранее: Алиса берёт его и запирает письмо сама, даже если Боб сейчас не в сети.
| Вопрос | RSA | Диффи — Хеллман |
|---|---|---|
| Зачем нужен | Запереть письмо для одного адресата или подписать своё | Вдвоём получить общий ключ, которым потом шифруют переписку |
| Нужен ли собеседник в сети | Нет: замок Боба уже у Алисы | Да: каждый должен внести своё тайное число |
| Что отправляют | Само письмо, запертое замком | Только открытые числа; ни письма, ни ключа в канале нет |
| Ключи | Замок и ключ Боба служат годами | Тайные числа выбирают заново для каждого разговора |
| Трудная задача для Евы | Разложить n на два простых числа | Найти тайное число по открытому (дискретный логарифм) |
| Аналогия | Открытый навесной замок | Краски, которые смешивают вдвоём |
В российских стандартах RSA нет совсем. Подпись делают по ГОСТ Р 34.10-2012 на эллиптических кривых, а общий ключ вырабатывают по VKO (о нём — в статье про Диффи — Хеллмана). Открытый ключ здесь — точка на кривой, а не произведение двух простых чисел, поэтому раскладывать на множители нечего. Стойкость держится на другой трудной задаче — дискретном логарифме.
Запирать письмо прямо открытым ключом в ГОСТ не принято: открытым ключом только подписывают и вырабатывают общий ключ, а письмо шифруют уже симметричным шифром. Впрочем, и в мире RSA делают почти так же: им обычно запирают не само письмо, а случайный ключ для AES.
При этом RSA в России встречается каждый день. Обычные браузеры не понимают ГОСТ, поэтому даже сертификаты для сайтов, которые с 2022 года выпускает национальный удостоверяющий центр Минцифры, подписаны по RSA. Для ГОСТ-соединений у этого центра есть отдельная цепочка сертификатов, но такие сайты открываются только в браузерах с поддержкой ГОСТ, например в Яндекс Браузере.
В игре вы сами соберёте ключ, запрёте и откроете письмо, а потом попробуете взломать его за Еву. Что стоит сделать:
У обеих схем пара ключей — открытый и закрытый, но трудные задачи под ними разные, и умеют они разное:
| Параметр | RSA | ГОСТ Р 34.10-2012 |
|---|---|---|
| Из чего ключ | Два больших простых числа и их произведение | Тайное число и точка на эллиптической кривой |
| Трудная задача | Разложение на множители | Дискретный логарифм на кривой |
| Размер ключа для стойкости ≈ 128 бит | 3072 бита | 256 бит |
| Что умеет | Шифрование (с OAEP) и подпись | Подпись; общий ключ — по VKO |
| Год | 1977 | 2012 (до него — ГОСТ Р 34.10-2001) |
| Стандарт | PKCS #1 (RFC 8017) | ГОСТ Р 34.10-2012 (RFC 7091), ТК 26 |
Числа RSA раскладывают тем же решетом числового поля, которое грозит Диффи — Хеллману, поэтому и стойкость та же: 2048 бит примерно равны 112-битному симметричному ключу, а для 128 бит нужно 3072. Как росли рекорды: RSA-129 (426 бит) разложили в 1994 году, RSA-768 — в 2009-м, RSA-250 (829 бит) — в 2020-м. До 2048 бит ещё очень далеко, но ключи короче 2048 бит сегодня считаются небезопасными.
Число 65537 = 216 + 1 простое, а в двоичной записи у него всего две единицы, поэтому запереть письмо можно за 17 умножений. Брать совсем маленькое e, например 3, опасно, если не добавлять случайность: когда m3 меньше n, деление ничего не меняет, и Ева просто извлекает кубический корень из c. В игре это видно на m = 2 и 3: 23 = 8 меньше 33, и c = 8.
В 2012 году две группы исследователей собрали миллионы открытых ключей RSA из интернета и сравнили их попарно. У десятков тысяч ключей нашлись общие простые множители, в основном у маршрутизаторов, сетевых камер и другой техники, которая создавала ключ сразу после первого включения, когда хорошей случайности в ней ещё не было. Если у двух n общее p, его находят за доли секунды алгоритмом Евклида, и оба ключа раскрыты. Простые числа должны быть не только огромными, но и по-настоящему случайными.
Алгоритм Шора на квантовом компьютере разложил бы n так же быстро, как решил бы задачу Диффи — Хеллмана. Для RSA важнее всего подписи, и им уже готовят замену: постквантовые стандарты подписи ML-DSA (FIPS 204) и SLH-DSA (FIPS 205). Второй интересен тем, что держится только на хэш-функциях, без всякой теории чисел.
Теперь вы знаете, как запереть письмо ключом, который есть у всех, и почему одной трудности разложения для этого мало
В игре вы выберете свои простые числа, построите ленту замка и увидите, как Ева читает письмо без всякого разложения