Открытый ключ: Диффи — Хеллман и RSA

Холодная война. По коридору аэропорта идёт человек с портфелем, прикованным цепочкой к запястью. В портфеле — ничего секретного по содержанию: страницы случайных цифр, ключи для шифровальных машин посольства на следующий месяц. Но без этого портфеля посольство замолчит. Курьеров с ключами возили по всему миру тысячами.

Все шифры, которые мы разбирали до сих пор, — от Цезаря до одноразового блокнота и AES — устроены одинаково: у отправителя и получателя должен быть один и тот же ключ. Его называют симметричным. И у всех них одна беда: прежде чем шифровать, ключ нужно как-то передать. Тайно. А чтобы передать тайно, нужен… шифр с ключом.

Замкнутый круг

Это называется проблемой распределения ключей. Для двух людей она решается одной встречей. Но представьте сеть, где каждый должен говорить с каждым по секрету. Для десяти человек нужно 45 разных ключей, для тысячи — 499 500, для миллиарда пользователей интернета — около полуквинтиллиона. И каждый ключ кто-то должен доставить лично.

А теперь представьте, что вы впервые заходите на сайт банка. Вы никогда не встречались с банком, курьер к вам не приезжал, а весь ваш разговор с первого байта идёт через чужие провода — вай-фай в кафе, провайдера, десяток узлов интернета. Как договориться о секретном ключе, если каждое слово слышат посторонние?

Вот мысленный эксперимент, который подсказывает, что это не безнадёжно. Алиса кладёт письмо в ящик, вешает свой замок и отправляет Бобу. Боб не может открыть, но вешает рядом свой замок и отправляет обратно. Алиса снимает свой замок и снова отправляет. Теперь на ящике только замок Боба — он открывает и читает. Ящик трижды прошёл через руки почтальона, и ни разу не был открыт. Ключами никто не обменивался!

Диффи — Хеллман: смешиваем краски

В 1976 году Уитфилд Диффи и Мартин Хеллман из Стэнфорда опубликовали статью «Новые направления в криптографии». В ней был способ, которым двое могут договориться об общем секрете, разговаривая только при свидетелях. Важную часть идей придумал их коллега Ральф Меркл.

Проще всего понять его на красках. У смешивания красок есть нужное свойство: смешать легко, а разделить смесь обратно на исходные краски — практически невозможно.

1. Алиса и Боб открыто договариваются об общей краске, скажем жёлтой. Её видят все.
2. Каждый выбирает свою секретную краску и никому её не показывает.
3. Каждый смешивает общую краску со своей секретной и отправляет смесь другому — открыто.
4. Каждый добавляет к полученной смеси свою секретную краску.

Теперь у обоих одинаковый цвет: общая + секрет Алисы + секрет Боба, просто смешанные в разном порядке. А подслушивающая Ева видела жёлтую краску и две смеси. Смешать их между собой — получится не то: в её банке две порции жёлтой. А отделить из смеси секрет она не может.

На самом деле Диффи и Хеллман смешивали не краски, а числа. Общая «краска» — это два открытых числа: большое простое p и число g. Секрет Алисы — число a. «Смешать» — значит вычислить A = g^a mod p: возвести g в степень a и взять остаток от деления на p. Остаток мы уже встречали в шифре Цезаря: это тот же счёт «по кругу», как на циферблате.

Боб получает A и возводит его в свою степень b: A^b = g^ab. Алиса делает то же с B = g^b: B^a = g^ba. Это одно и то же число — общий секрет. А Еве, чтобы его получить, нужно по A = g^a mod p найти a. Эту задачу называют дискретным логарифмом, и для простых чисел из сотен цифр никто не знает, как решить её быстрее, чем за астрономическое время.

Почтовый ящик с прорезью: RSA

Диффи и Хеллман описали ещё одну идею, но не нашли, как её устроить. Пусть у каждого будет два ключа: один открытый, другой закрытый. Открытым шифруют, закрытым расшифровывают. Как почтовый ящик с прорезью: бросить письмо может любой прохожий, а достать — только хозяин ключа. Открытый ключ можно печатать в газете: всё равно им ничего не прочитать.

Через год, в 1977-м, такой ящик построили трое учёных из MIT — Рон Ривест, Ади Шамир и Леонард Адлеман. Шифр назвали по первым буквам фамилий: RSA. Вот рецепт:

1. Выберите два больших простых числа p и q. Это главный секрет.
2. Перемножьте: n = p · q. Это число открытое.
3. Посчитайте φ(n) = (p − 1)(q − 1) — функцию Эйлера. Это снова секрет: без p и q её не узнать.
4. Выберите e — число без общих делителей с φ(n). Пара (n, e) — открытый ключ.
5. Найдите d такое, что e · d при делении на φ(n) даёт остаток 1. Это закрытый ключ.

Шифровать: сообщение — число m (меньше n), шифр c = m^e mod n. Расшифровывать: m = c^d mod n. Возведение в e и в d — два поворота ключа, которые гасят друг друга.

Где здесь защита? Чтобы найти d, нужно знать φ(n), а для этого — p и q. Ева знает n. Значит, ей нужно разложить n на множители. Для n = 143 это минута: 143 = 11 · 13. Для n из 600 цифр — неизвестно, как это сделать за время жизни Вселенной.

Умножить легко, разложить трудно

Перемножить два числа по сто цифр — работа на несколько минут с карандашом и на микросекунду для компьютера. Обратная задача — по произведению найти множители — совсем другое дело. Можно перебирать делители, можно применять хитрые методы, но для больших чисел все известные способы работают невообразимо долго. Такую задачу, лёгкую в одну сторону и трудную в обратную, называют односторонней функцией; у RSA есть ещё и «лазейка» — знание p и q, которое делает обратный путь лёгким.

С тех пор и компьютеры, и алгоритмы стали сильнее. В 2020 году разложили RSA-250 — число из 250 цифр; это заняло около 2700 лет процессорного времени. Поэтому сегодня в ключах RSA берут n из 2048 битов (617 цифр) и больше. Единственная известная угроза такой длине — большой квантовый компьютер: в 1994 году Питер Шор придумал для него быстрый алгоритм разложения. Таких машин пока нет, но к ним уже готовятся: в 2024 году в США утвердили первые стандарты постквантовой криптографии.

Подпись

У пары ключей есть второе применение, не менее важное. Если «зашифровать» сообщение закрытым ключом, s = m^d mod n, то «расшифровать» его открытым, s^e mod n, сможет любой. Секретности это не даёт, зато доказывает авторство: получить такое s мог только владелец d. Это и есть цифровая подпись. На практике подписывают не само сообщение, а его хеш из прошлого урока — поэтому так важно, чтобы хеш был без коллизий.

В жизни оба изобретения работают вместе. Когда браузер открывает сайт по HTTPS, он с помощью обмена Диффи — Хеллмана (обычно в варианте на эллиптических кривых) договаривается с сервером о секретном ключе, а подпись сервера доказывает, что это действительно банк, а не самозванец. Дальше данные шифруются быстрым симметричным шифром вроде AES. Всё это — за долю секунды, при свидетелях и без единого курьера.

Что взять с собой

• Симметричным шифрам нужен общий ключ, и его надо как-то тайно доставить. Это проблема распределения ключей.
• Диффи — Хеллман (1976): двое договариваются о секрете открыто. Смешивать (возводить в степень по модулю) легко, разделять (дискретный логарифм) — трудно.
• RSA (1977): n = p · q, φ = (p − 1)(q − 1), e открыт, d — такое, что e · d даёт остаток 1 по модулю φ. Шифр c = m^e mod n, расшифровка m = c^d mod n.
• RSA стоит, пока n нельзя разложить на множители. Для 617 цифр это не под силу ни одному существующему компьютеру.
• Подпись — то же самое наоборот: подписывают закрытым ключом, проверяют открытым.

Теперь у вас есть все инструменты дешифровщика: от счёта букв до разложения на множители. Осталось посмотреть, как ими пользовались в настоящих делах — от заговора против королевы до шифровок серийного убийцы. Дальше: знаменитые шифры →