Основы асимметричной криптографии: теория

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

Суть

До 1976 года перед человечеством, уже имевшем сильные шифры типа Люцифера, стояла серьёзная проблема распространения ключей к таким алгоритмам. Чтобы начать шифроваться, двум сторонам было необходимо договориться об используемом ключе по другому защищённому от прослушивания каналу, например, при личной встрече. Это, в принципе, логично, но обходные пути всё же были найдены.

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

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

Получение общего ключа

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

Головоломка Меркла

До изобретения первого в мире асимметричного алгоритма, уже были попытки собрать что-то подобное на основе симметричных схем. Так, американский штудент - Ральф Меркл (который стал крутым криптографом и изобрёл много всякого, например, дерево Меркла, используемое в Биткоине) в своём курсаче описал очень простую схему:

Я создаю 240 крупных случайных чисел и зашифровываю их все слабыми 40-битными ключами, добавив немного избыточности, например, приписав к числам несколько нулей справа перед зашифровыванием. В результате получается несколько терабайт отборного шума, которые я отсылаю тебе по электронной почте.
Ты совершенно случайным образом выбираешь оттуда любое зашифрованное число и брутфорсишь его целый день на своём Радеоне. Это даётся довольно легко, потому что ключ-то слабый.
Всё - теперь ты расшифровал это число и будешь использовать его как ключ для общения со мной, главное, не забудь намекнуть мне, какое число ты выбрал, например, прислав его хеш.

Суть в том, что я могу понять, какое число ты выбрал, потому что у меня все они есть и я знаю их хеши. И ты тоже по очевидным причинам знаешь, какое число выбрал. Но вот злоумышленник не знает, и чтобы узнать, ему придётся в худшем случае расшифровать все числа и сверить их хеши. Одно число рашифровать несложно - это потребует 240 операций, но чисел самих 240 штук, поэтому хакер влетел перебирать 280 ключей. Для сравнения, лучший результат, полученный Bitcoin, составляет 79 бит.

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

Первый чистокровный асимметричный алгоритм был изобретён двумя американскими умничками в 1976 году. Честолюбивое АНБ потом заявило, что знало о такой возможности ещё в 1966 году, но им никто не поверил.

В основе алгоритма лежит коммутативная необратимая операция. В качестве этой операции может выступать либо возведение в степень по модулю простого числа, или умножение числа на точку на эллиптической кривой в конечном поле. Это очень сложная математика, но самый простой случай - со степенями - понять легко.

Как известно, число можно возводить в несколько степеней в разном порядке, и результат от этого не изменится: (ab)c = (ac)b. Возведение в степень легко обращается - зная A = ax, я могу вычислить x = logaA. Но оно становится необратимым, если выполнять его по модулю простого числа, то есть после возведения в степень делить результат на это число и брать остаток от деления. Например: 1517 = 98526125335693359375, остаток от деления этого числа на 29 есть 18. Это записывается как 18 = 1517 mod 29. Если представить, что на месте этих 15, 17 и 29 стоят огромные числа, то зная 18 = 15x mod 29, ты никак не сможешь вычислить x.

Примечательно, что свойства степеней сохраняются и при оперировании по модулю, то есть если сначала вычислить ab mod p, а потом возвести в степень c по тому же модулю, то результат будет тот же, как если вычислять это в другом порядке (ac)b mod p. Ну а дальше не надо быть супергением, чтобы сложить из этого криптоалгоритм (mod опущен для чистоты, но он подразумевается):

Выбираем основание степени a - это несекретное число, его можно опубликовать или даже вшить в программу.
Я генерирую своё огромное число b и считаю B = ab. Большую B я публикую, тогда как малая b - мой секретный ключ.
Ты генерируешь своё огромное число c и считаещь C = ac. Большую С ты публикуешь, тогда как малая c - твой секретный ключ.
Я беру твоё C и получаю из него наш общий секретный ключ K = Cb.
Ты берёшь моё B и получаешь из него наш общий секретный ключ K = Bc.

Теперь у нас есть общий ключ K, о котором никто, кроме нас, не знает. Мой K = твоему, потому что я сделал K = (ac)b, а ты сделал K = (ab)c. И мы сделали это, не зная секретных чисел друг друга, подставив в эти выражения полученные от другой стороны ab = B и ac = C. Всекаешь? То-то же. А злоумышленник - нет, поскольку для получения K необходимо знать хотя бы одно из секретных чисел, но вычислить их из B или C нельзя, ведь после каждой операции берётся остаток от деления.

Защищённость

Стоит заметить, что обращение возведения в степень по модулю или скалярного умножения числа на точку на эллиптической кривой в конечном поле - дискретное логарифмирование - потенциально необратимая операция. Многие асимметричные алгоритмы опираются на веру в неравенство классов сложности NP и P, которая пока не доказана. Это означает, что в один прекрасный день кто-нибудь может взломать такие алгоритмы, причём все разом, решив любую NP-полную задачу, которая сводится ко всем задачам из этого класса. И этот прекрасный день обязательно настанет, когда появятся мощные квантовые компьютеры.

Головоломка Меркла и несколько других не таких как все асимметричных алгоритмов такой проблеме не подвержены, но их никто не использует либо ввиду непрактичности, либо из-за малой изученности.

Электронная подпись

Кроме алгоритмов получения общего секрета, есть специализированные алгоритмы, предназначенные для подписи или шифрования, а то и для обеих целей сразу.

Электронная подпись - это такой набор байтов, который связан с каким-то сообщением и может быть сгенерирован только владельцем закрытого ключа, а проверен - любым, у кого есть ключ открытый. Подписанный документ нельзя модифицировать, не повредив электронную подпись, поэтому она используется для авторизации. В то же время, однажды подписав документ, не получится отречься от подписи в будущем - можно подписывать контракты.

Как правило, подписывают не само сообщение, а его хеш, потому что длина хеша достаточно мала и всегда фиксирована, в отличие от длины сообщения.

Схема Лэмпорта

Схема Лэмпорта - самый естественный алгоритм ЭЦП, но у него есть недостаток - им можно подписать только одно сообщение.

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

Логичное продолжение затеи - публиковать больше одной пары строк, чтобы можно было подписать много бит сразу. Ральф Меркл произвёл ещё кучу улучшений этой идеи, доведя её до очень даже практичной конфетки, в частности придумал дерево Меркла, позволяющее сделать больше одной подписи одним ключом.

Шифрование

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

Схема Рабина

Широко известный в узких кругах Майкл Рабин (тот самый, который придумал тест на простоту, используемый для генерации больших простых чисел) создал простую схему асимметричного шифрования: c = m2 mod n. Шифруемый текст превращается в число, возводится в квадрат, и итоговый результат есть остаток от деления квадрата на открытый ключ n.

Чрезвычайно важным свойством такой схемы является её доказанность - достоверно известно, что нахождение корня по модулю не менее сложно, чем разложение закрытого ключа на множители. Тот же RSA (подобный алгоритм) может быть быть взломан даже без решения NP-полной задачи, которой является разложение на множители (и такой взлом был продемонстирован для малых значений шифрующих показателей степени).

Для расшифровывания необходимо знать простые множители (p и q) открытого ключа n, они и являются закрытым ключом и должны быть тоже достаточно большими. Ради упрощения расшифровывания с помощью китайской теоремы об остатках рекомендуется выбирать p и q так, чтобы им не хватало 1 до делимости на 4. Сама процедура выглядит несколько мозгоёбски, поэтому описывать здесь её нет смысла, надо только заметить, что в результате получится 4 разных сообщения, одно из которых верно. Поэтому необходимо добавлять в сообщение перед зашифровыванием немного избыточности, чтоб получатель мог определить, какая версия правильная.

Ещё

В статье описаны самые простые алгоритмы для общего понимания, благо такие существуют. Смысла описывать здесь все алгоритмы и их технические подробности нет - для этого есть книги и документация.

Асимметричных шифров существует великое множество, и периодически появляются новые с разными интересными свойствами, но в основном применяются RSA, Диффи-Хеллман (в HTTPS) и производные Эль-Гамаля и их эллиптические версии (DSA, ECDSA, патриотичный велосипед ГОСТ Р 34.10-94. Их легко осилить, поняв Диффи-Хеллмана). Есть чисто академические варианты типа схем Рабина, Шнора, GHR - более полный список в английской Википедии.

Человек посередине

Все без единого исключения асимметричные алгоритмы подвержены атаке "человек посередине", и с этим ничего нельзя сделать.

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

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

Стоит заметить, что с этической точки зрения проблема отсутствует вовсе. Если два человека начинают общение как анонимы, то можно полноправно считать, что каждый из них общается со вмешавшимся посередине мудаком, а то, откуда он берёт ответы, роли не играет - он ведь тоже анонимен. Это как играть в шахматы по интернету, передавая все ходы компьютерной игре.

Если же одна из сторон не является анонимной, то проблема связи реальной личности с ключами совершенно естественна, и без помощи из невиртуальной реальности тут не обойтись. Поэтому для установления доверенного HTTPS-соединения необходимы удостоверяющие центры, которые, будучи обязанными юридически, своим авторитетным словом скажут, что такой-то ключ и правда принадлежит такому-то банку.

Если требуется установить связь между ключом и какой-то человекочитаемой строкой (например, доменным именем), то тут тоже нельзя обойтись без вмешательства извне, поскольку требуется понятие частной собственности на эту строку. Но самые современные передовые технологии позволяют решить это без централизованного удостоверяющего агента - с помощью децентрализованного.

Chipollino Onion Club