§3.5. Асимметричное шифрование

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

Алгоритм Диффи–Хеллмана

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

В математике всё немного сложнее: обычно мы не можем снять шифр из-под другого, поэтому у Алисы не получится просто так снять свой замок, оставив при этом замок Боба. Однако, Диффи, Хеллман и Меркл в 1976 году разработали алгоритм, который позволяет аналогичным способом двум сторонам получить общий ключ шифрования. Он называется алгоритмом Диффи–Хеллмана и основан на возведении в степень по модулю.

У алгоритма Диффи–Хеллмана есть серьёзный недостаток. Предположим, почтальон Мэллори всё же хочет получить доступ к коробке. Получив коробку Алисы, она сама повесит свой замок и отправит её обратно, указав Боба в качестве отправителя. Алиса снимет свой замок и вернёт посылку лишь с ключом Мэллори. Тогда Мэллори сможет открыть коробку. Более того, она может повесить свой замок снова и отправить коробку уже Бобу. Ни Алиса, ни Боб не смогут понять, что коробку кто-то открыл, и даже возможно изменил её содержимое. Такая атака называется MITM (англ. man in the middle — человек посередине).

На этом проблемы симметричного шифрования не заканчиваются. Рассмотрим мессенджер, в котором тысяча пользователей обмениваются сообщениями между собой. Чтобы защитить сообщения от прочтения владельцем серверов, все пользователи их шифруют. Таким образом, каждая пара пользователей хранит по ключу для переписки, и всего в сети порядка полумиллиона ключей. Более того, если одна из сторон потеряет ключ, его нужно будет сгенерировать заново.

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

В таких алгоритмах широко применяется подход односторонней функции: для любого x легко вычислить f(x), но сложно по значению f(x) получить исходный x. Эти алгоритмы используют два ключа — открытый и закрытый. Открытый ключ используется для шифрования, а закрытый — для расшифровывания. Таким образом, отправить сообщение может кто угодно, а прочитать — только владелец ключа.

RSA

Далее мы будем работать с целыми неотрицательными числами — 0, 1, 2… Вспомним базовые вещи из математики, которые нам понадобятся.

Понятия

  • Частное, остаток — результаты операции деления. Например, при делении 13 на 3 частное — 4, остаток — 1, так как 13 = 3 × 4 + 1.

  • Одно число делится на другое нацело, если остаток от деления равен нулю.

  • Взятие остатка от деления — операция, обозначаемая словом mod: 13 mod 4 = 1

  • Равные по модулю числа (также: сравнимые) — числа, у которых остатки от деления равны. Такое равенство обозначают знаком ≡:

    • 13 ≡ 7 (mod 3)

  • Наибольший общий делитель (НОД) двух натуральных чисел a и b — максимальное c такое, что a ÷ c и b ÷ c — целые числа.

  • Простое число — число, у которого ровно два множителя: оно само и единица. Например, простыми являются числа 2, 5, 11, 149.

  • Составное число — число, у которого больше двух множителей. Ноль и единицу мы не считаем ни простыми, ни составными.

  • Взаимно простые числа — числа, НОД которых равен единице. 8 и 15 взаимно простые, а 108 и 76 — нет.

  • Обратное число к a по модулю m — число x такое, что ax ≡ 1 (mod m). Например, обратное к 7 по модулю 31 — 9.

Рассмотрим RSA — один из самых известных алгоритмов асимметричного шифрования, использующийся и в наши дни. Его придумали американские учёные Р. Ривест, А. Шамир и Л. Адлеман (алгоритм назван первыми буквами фамилий авторов). В его основе лежит то, что большое число очень долго раскладывать на простые множители.

Чтобы получить ключи RSA, возьмём два простых числа p и q. Перемножим их, получим число n — модуль RSA. Рассмотрим магическое число φ = (p – 1) × (q – 1) — функция Эйлера для n. После этого придумаем e — оно должно быть взаимно простым с φ. Это число называется публичной экспонентой. Наконец, посчитаем число d — это обратное к e по модулю φ — приватную экспоненту. Пара чисел (n, e) будет открытым ключом, а (n, d) — закрытым.

Шифрование производится очень просто: допустим, мы хотим зашифровать сообщение m (m < n). Посчитаем me mod n — это будет зашифрованным сообщением. Обратная операция не сложнее: если c — зашифрованное сообщение, то m = cd mod n.

Рассмотрим на примере:

  • p = 13, q = 23, n = 299, φ = 264

  • e = 17, d = 233 (17 × 233 = 264 × 15 + 1)

  • m = 25 → c = 25¹⁷ mod 299 = 64

  • c = 64 → m = 64²³³ mod 299 = 25

Мы уже знаем, что любые данные представимы в шестнадцатеричном виде, то есть в виде числа. Значит, мы можем делить текст на маленькие блоки, чтобы числа получались меньше n, и таким образом их шифровать.

Ключевая вещь, которая делает RSA безопасным — невозможность быстро разложить число n на множители. Если бы мы смогли это сделать, то нашли бы p, q и φ, а затем, зная публичную экспоненту e, посчитали бы d. Кажется, что число 299 несложно разложить на множители и вручную. Однако, в RSA применяются достаточно большие простые числа — длиной 1024 бита и более. Авторы RSA проводили конкурс по разложению чисел на простые множители. На данный момент опубликованы решения для чисел длиной до 829 бит.

Одно из самых известных применений RSA — в криптографических протоколах, используемых в интернете. Эти протоколы называются SSL (англ. Secure Sockets Layer — уровень защищённных сокетов) и TLS (англ. Transport Layer Security — транспортный протокол защиты). SSL использовался до 2014 года — тогда в нём нашли критическую уязвимость POODLE (CVE-2014-3566), и он был вытеснен TLS.

Подписи и доверенные лица

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

Однако остаётся проблема man-in-the-middle: мы всё ещё не можем убедиться, что к нам попал публичный ключ именно нужного сервера. Для этого созданы центры сертификации (англ. certificate authority) — специальные доверенные лица, проверяющие сертификаты. Они подписывают своей подписью сертификат, если он реально предоставлен владельцем домена или представителем какой-либо компании. Публичные ключи центров сертификации устанавливаются на все компьютеры и телефоны ещё на заводе, и при каждом входе на сайт браузер может проверить, действительно ли этот сертификат выдан доверенным центром сертификации.

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

Что ещё бывает в криптографии

Кажется, что асимметричное шифрование имеет много плюсов перед симметричным. Но у него есть и существенный минус: как правило, алгоритмы асимметричного шифрования основаны на сложных математических преобразованиях. Тот же RSA возводит большие числа в огромные степени. Следовательно, симметричные шифры в сотни, а то и тысячи раз выигрывают в скорости.

Поэтому сейчас чаще всего используются комбинации симметричных и асимметричных криптосистем. Один из таких примеров — протокол TLS. В нём в начале соединения клиент и сервер генерируют общий секретный ключ с помощью протокола Диффи-Хеллмана. Для защиты от атаки man-in-the-middle публичные части ключей подписываются RSA-ключом сервера, а дальше все данные шифруются выбранным алгоритмом симметричного шифрования.

В данный момент исследователи работают над созданием квантовых компьютеров. Уже известно, что такие компьютеры смогут быстро раскладывать числа на простые множители. Для решения возникшей проблемы были придуманы алгоритмы шифрования на эллиптических кривых, которые заменят RSA после появления таких компьютеров. Более того, некоторые из них уже применяются на практике.

Выводы

  1. Для работы симметричного шифрования нужен безопасный обмен ключами. Для этого применяется алгоритм Диффи–Хеллмана.

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

  3. Алгоритм RSA использует то, что никто не умеет быстро раскладывать числа на простые множители.

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

  5. На практике симметричное шифрование сильно быстрее, поэтому на практике симметричные и асимметричные алгоритмы комбинируют. Сейчас криптография активно развивается в направлении создания постквантовых алгоритмов шифрования.

Задача А. Не Цезарь ⟶