Асимметричная криптография и электронная подпись

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

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

Таким образом, для симметричных алгоритмов характерна проблема обмена ключами. Кроме того, возникает проблема управления большим количеством ключей, поскольку отдельный ключ необходим для каждой пары «отправитель-получатель». Если группа из n человек желает обмениваться конфиденциальными сообщениями, понадобится O(n²) ключей (n-1 ключ каждому). Если же группа будет использовать один общий ключ, то его компрометация (утечка) у одного члена скомпрометирует переписку всей группы.

Эти проблемы и привели к появлению во второй половине XX века принципиально нового класса алгоритмов шифрования.

7.1. Алгоритмы шифрования с открытым ключом

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

Рис. 7.1. Открытый и закрытый ключи

Если пользователь A хочет отправить зашифрованное послание пользователю B, он шифрует его с помощью открытого ключа B. Теперь текст не сможет прочесть никто, кроме B (даже сам A), поскольку для дешифрования нужен закрытый ключ (рис. 7.2).

Рис. 7.2. Шифрование и дешифрование с открытым ключом

Схему шифрования можно записать в следующем виде:

M′ = E(M, K_откр)
M = D(M′, K_закр),

где E – функция шифрования, D – функция дешифрования, а K_откри K_закр – соответственно открытый и закрытый ключи получателя сообщения.

Метод шифрования с открытым ключом впервые был публично предложен в 1976 году Диффи и Хеллманом. Они не смогли придумать конкретного алгоритма, но сформулировали условия, которым такие алгоритмы должны удовлетворять:

1. Процесс генерации пары ключей (открытый и закрытый) не должен представлять вычислительных трудностей.

2. Процесс шифрования текста, т.е. вычисления E(M, K_откр), а также процесс дешифрования, т.е. вычисления D(M′, K_закр) также не должны представлять вычислительных трудностей.

3. Для противника должно быть невозможно (с точки зрения вычислительных возможностей) вычисление закрытого ключа K_закр по имеющемуся открытому ключу K_откр.

4. Для противника должно быть невозможно (с точки зрения вычислительных возможностей) вычисление открытого текста M по имеющемуся зашифрованному тексту M′ и открытому ключу K_откр.

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

Алгоритм RSA

RSA – один из первых алгоритмов шифрования с открытым ключом – разработан в 1977 году, название составлено из первых букв имен его авторов (Ривест, Шамир и Адлеман). На протяжении двадцати лет он был самым популярным и практически единственным широко используемым алгоритмом с открытым ключом.

Логика алгоритма следующая. Для генерации ключей выбираются два больших случайных простых числа p и q и вычисляется их произведение n = pq. Затем вычисляется функция Эйлера для числа n (количество таких чисел в отрезке [1; n], наибольший общий делитель которых с n равен единице):

φ(n) = (p-1)(q-1)

Далее выбирается целое число e, такое что 1 < e < φ(n)и e взаимно просто с φ(n). Находится число d такое, что ed = 1 mod φ(n). Это может быть сделано, например, при помощи расширенного алгоритма Евклида.

Открытым ключом является пара чисел (n, e), а закрытым ключом – пара (n, d).

Как видно, для того, чтобы по открытому ключу определить закрытый, необходимо вычислить φ(n), а для этого большое (сегодня для новых систем рекомендуется не менее 3072 бит) число n необходимо разложить на простые множители. Но эффективного алгоритма разложения числа на простые множители не известно.

RSA предназначен для шифрования двоичных текстов. Открытый текст разбивается на блоки и каждый блок рассматривается как двоичное число M (чтобы снять те же недостатки, что у режима электронной кодовой книги, используют случайное дополнение). При этом должно соблюдаться ограничение M < n, исходя из этого условия выбираются длина блока и минимально возможные значения p и q.

Для того чтобы зашифровать сообщение, вычисляется

M′ = Mᵉ mod n

Для дешифрования необходимо вычислить

M = M′ᵈ mod n

Убедимся в корректности алгоритма.

M′ ᵈ mod n = (Mᵉ mod n)ᵈ mod n = Mᵉᵈ mod n

Т.к. (ed) mod φ(n) = 1, то ed=kφ(n) + 1 для некоторого целого k. Отсюда:

M^ed mod n = M^{kφ(n) + 1} mod n

По теореме Эйлера M^φ⁽ⁿ⁾mod n = 1 для взаимно простых M и n. Т.о.:

M^{kφ(n) + 1} mod n = 1^k ⋅ M¹ mod n = M

Получили M′ᵈ mod n = M, что и требовалось доказать.

Очевидно, что открытый и закрытый ключ в алгоритме RSA взаимозаменяемы: то, что зашифровано одним из них, расшифровывается другим. В общем случае это не обязательно.

Недостаток алгоритмов с открытым ключом – низкая скорость. Так, в алгоритме RSA шифрование и дешифрование заключаются в возведении очень большого числа в очень большую степень, а это достаточно ресурсоемкая операция.

Поэтому на практике чаще всего используется комбинация двух алгоритмов. Сообщение шифруется с помощью симметричного алгоритма шифрования (например, AES). При этом каждый раз генерируется новый случайный ключ, называемый сеансовым ключом. Этот ключ зашифровывается открытым ключом получателя (например, с помощью RSA) и отправляется вместе с сообщением. Такая гибридная схема обеспечивает как скорость операций шифрования/дешифрования, так и надежность.

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

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

Для целей конфиденциальности текст шифруется открытым ключом получателя.

Рассмотрим ситуацию, когда сообщение шифруется закрытым ключом отправителя. В этом случае дешифровать его сможет кто угодно, поскольку открытый ключ общедоступен. Однако получатель сообщения может быть уверен в том, что подлинный автор сообщения – владелец закрытого ключа, поскольку никто другой не имеет возможности его создать (при условии, что закрытый ключ не скомпрометирован, т.е. не украден). Таким образом, достигается аутентичность (подлинность) сообщения. С юридической точки зрения это означает, что автор сообщения не сможет от него отказаться (апеллируемость).

Эта идея нашла свое воплощение в концепции электронной подписи.

Электронная подпись – тег, вычисленный на основе сообщения и закрытого ключа подписывающего и проверяемый с помощью парного открытого ключа. Предназначается для одновременной проверки неизменности и авторства сообщения.

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

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

Для сообщения M вычисляется хэш h = H(M).
Хэш шифруется с помощью закрытого ключа отправителя, т.е. вычисляется E(h, K_закр), где E – функция шифрования асимметричного алгоритма.
Полученное значение s берется в качестве электронной подписи для сообщения M. Сообщение пересылается получателю вместе с подписью (при этом подпись обычно пересылается отдельным файлом, хотя может и приписываться к сообщению). Если необходимо обеспечить как аутентичность, так и конфиденциальность, сообщение M зашифровывается открытым ключом получателя уже после вычисления подписи.

Чтобы убедиться в подлинности полученного сообщения, необходимо проделать шаги алгоритма в обратном порядке:

Полученная электронная подпись s расшифровывается открытым ключом предполагаемого отправителя сообщения, т.е. вычисляется D(s, K_откр).
Вычисляется хэш полученного сообщения H(M).
Если D(s, K_откр) = H(M), то сообщение подлинно. В противном случае оно признается неаутентичным (возможно, оно было изменено при пересылке, либо создано другим лицом).

Рис. 7.3. Формирование и проверка электронной подписи

Свойства криптографически стойкой хэш-функции обеспечивают надежность электронной подписи. Действительно, если изменить в оригинальном сообщении хотя бы один символ, его хэш (следовательно, и подпись) изменится, а подобрать другое сообщение с таким же хэшем невозможно. Сообщения с таким же хэшем, разумеется, существуют, и их бесконечно много: длина хэша фиксирована, а сообщений неограниченное число. Но вероятность случайно наткнуться на такое сообщение обратно пропорциональна числу всевозможных хэшей и при длине 512 бит равна 1/2⁵¹², то есть практически ничтожна.

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

Описание «подпись есть хэш, зашифрованный закрытым ключом» верно не всегда, а лишь для схем вроде RSA, где операции с двумя ключами взаимно обратны. В большинстве современных схем (в частности, основанных на эллиптических кривых) шифрования не происходит: подпись вычисляется отдельным алгоритмом и представляет собой пару чисел, которую дешифровать нельзя в принципе. Поэтому в общем случае электронную подпись определяют как пару алгоритмов: алгоритм формирования, получающий на вход сообщение и закрытый ключ, и алгоритм проверки, получающий сообщение, подпись и открытый ключ и выдающий ответ «да» или «нет».

Электронная подпись замыкает систему тегов, применяемых для защиты сообщения:

Контрольная сумма – тег на основе сообщения, который с высокой вероятностью изменится при изменении самого сообщения. Используется для обнаружения случайных технических искажений (помех) и не применяется в криптографии, поскольку сообщение легко изменить так, что контрольная сумма останется прежней;
Хэш – тег на основе сообщения, может быть вычислен кем угодно, имеет одностороннюю криптографическую связь с сообщением (подобрать сообщение с тем же хэшем практически неосуществимо);
MAC – тег на основе сообщения и общего секретного ключа, может быть сформирован и проверен любым, кто знает ключ, предназначен для обеспечения целостности;
Электронная подпись – тег на основе сообщения и закрытого ключа, может быть сформирован только владельцем закрытого ключа, проверен кем угодно, кто располагает открытым, обеспечивает целостность, аутентичность и апеллируемость.

7.3. Криптография на эллиптических кривых

Стойкость RSA опирается на трудность разложения числа на множители. У этой задачи есть неприятное свойство: хотя эффективного решения не найдено, известны алгоритмы, работающие существенно быстрее полного перебора. Практическое следствие состоит в том, что стойкость растет недостаточно быстро с увеличением длины ключа. Отсюда и наблюдаемая история рекомендаций (512 бит, 1024, 2048, 3072), в которой числа растут быстро, а запас прочности прибавляется скромно, при этом чем длиннее ключ, тем медленнее работает алгоритм.

Выход был найден в переносе тех же схем в другую математическую структуру, где известны лишь методы, близкие к полному перебору. Такой структурой оказалась группа точек эллиптической кривой – множество решений уравнения определенного вида (y² = x³ + ax + b) с заданной на нем операцией, формальные свойства которой совпадают со свойствами умножения чисел по модулю. Это совпадение и позволяет перенести схемы без изменений: там, где раньше возводили число в степень, теперь выполняют аналогичную операцию над точками кривой, а обращение этой операции столь же трудно.

Стойкости, которую в RSA обеспечивает ключ длиной около 3072 бит, здесь соответствует ключ в 256 бит. Поэтому криптография на эллиптических кривых вытеснила RSA в защищенных протоколах, мессенджерах, смарт-картах, банковских картах и системах распределенных реестров. На ней построено целое семейство алгоритмов, в частности, схемы электронной подписи ECDSA и EdDSA. Замена основания не потребовала переделки самих схем: сменилась лишь группа, в которой они реализованы.

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

Российский стандарт электронной подписи ГОСТ Р 34.10–2012 построен на эллиптических кривых. Он замыкает перечень основных отечественных криптографических стандартов, в который входят также ГОСТ Р 34.11–2012 (хэширование), ГОСТ Р 34.12–2015 (блочные шифры «Магма» и «Кузнечик») и ГОСТ Р 34.13–2015 (режимы их использования). Для государственных информационных систем, для защиты сведений, составляющих государственную тайну, для значимых объектов критической информационной инфраструктуры и в ряде других случаев применение сертифицированных средств, реализующих национальные стандарты, обязательно; разработка и распространение таких средств лицензируются. За пределами этого круга выбор алгоритмов свободен, однако документооборот с государственными органами и квалифицированная электронная подпись в любом случае выводят разработчика на отечественные стандарты.

7.4. Сертификат ключа и удостоверяющий центр

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

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

Можно связать открытый ключ с именем владельца с помощью внешней конструкции. Например, обеспечить доступность и целостность утверждения «открытый ключ K принадлежит субъекту S». Парадокс в том, что лучшее средство обеспечения целостности – сама электронная подпись. Получается, можно оформить утверждение как документ, подписать его – и мы получим сертификат открытого ключа. Сертификат содержит открытый ключ, сведения о владельце, срок действия, допустимое назначение ключа, идентификаторы алгоритмов, ссылки на сведения об отзыве и т.д., а подписывается он третьим лицом, которое называют удостоверяющим центром (УЦ) или издателем (сведения о нем также содержатся в сертификате).

Проблема при этом переносится уровнем выше: чтобы проверить сертификат, нужен открытый ключ удостоверяющего центра. Чтобы разорвать замкнутый круг, можно получить ключ УЦ при личном контакте (все равно необходимо встретиться, чтобы передать ему свой открытый ключ для выпуска сертификата). Тогда все клиенты этого центра смогут проверять сертификаты друг друга. Можно утверждать, что на основе доверия клиентов к УЦ возникает косвенное доверие между ними (рис. 7.4).

Рис. 7.4. Косвенное доверие

Маловероятно, что один человек или организация обслужит всех, с кем необходимо общаться. Но группа удостоверяющих центров может объединиться схожим образом и предоставить свои ключи для подтверждения УЦ более высокого уровня и так далее. Возникает древовидная структура делегированного доверия. Сертификат удостоверяющего центра подписывается вышестоящим центром, тот – еще одним; получается цепочка сертификатов, проверка которой состоит в последовательном подтверждении каждого звена. Проблема в том, что цепочка не может быть бесконечной и последний ключ некому подписать. Сертификат, завершающий цепочку, подписывается своим же ключом и называется корневым сертификатом. Его подлинность не может быть установлена математически, поэтому он представляет собой элемент доверия внутри криптографической схемы. Способы обеспечения доверия могут быть разными, например, корневой сертификат может быть заранее «зашит» в коде операционной системы, браузера или другой программы.

Рис. 7.5. Инфраструктура открытых ключей

Такой подход называют созданием инфраструктуры открытых ключей (рис. 7.5). Он не единственный, в зависимости от модели угроз и стартовых ограничений системы может быть предпочтительной одна из более простых моделей:

Сеть доверия (web of trust) обходится без выделенных центров: каждый участник подписывает ключи тех, чью личность проверил лично, доверие распространяется по цепочкам знакомств, и пользователь сам решает, скольким промежуточным звеньям верить. Модель безопасности, требующая компетентного решения от каждого пользователя, не масштабируется, поэтому массовой она не стала.
Доверие при первом соединении (trust on first use, TOFU) применяется в SSH и ряде мессенджеров: при первом подключении ключ собеседника принимается без проверки и запоминается, при последующих расхождение вызывает предупреждение. Противника, присутствовавшего в момент первой встречи, модель не остановит, зато сделает заметным появление любого следующего. Цена – предупреждения при законной смене ключа, которые пользователь привыкает игнорировать, после чего модель перестает работать вовсе.
Привязка ключа (pinning) означает, что программа заранее содержит ожидаемый открытый ключ и отвергает любой другой, даже подписанный доверенным центром. Например, антивирус или клиент онлайн-игры периодически загружает с сервера файл обновления. Чтобы злоумышленник не подменил это обновление (например, убедив программу, что сервером обновлений является его компьютер), оно подписывается электронной подписью, которую программа проверяет перед установкой. Открытый ключ для проверки хранится в самой программе, закрытый есть только у производителя (для надежности обновления подписывают на компьютере без доступа в интернет). Подделать подпись злоумышленник не сможет, а без успешной проверки программа не обновится. Никакие удостоверяющие центры здесь не нужны, потому что программа и ее разработчик хорошо «знают» друг друга. Цена – жесткость: смена ключа требует обновления всех клиентов, а ошибка оборачивается недоступностью сервиса.

Таблица 7.1. Модели доверия к открытому ключу

Модель	Кто удостоверяет ключ	Основной риск	Цена
Инфраструктура открытых ключей	Удостоверяющий центр из списка доверенных	Компрометация любого из корней	Зависимость от внешних организаций
Сеть доверия	Другие пользователи, лично знающие владельца	Отсутствие пути до незнакомого адресата	Требует решений от каждого пользователя
Доверие при первом соединении	Никто; ключ запоминается при первой встрече	Противник, присутствовавший при первой встрече	Ложные тревоги при законной смене ключа
Привязка ключа	Разработчик программы, заранее	Ошибка разработчика при смене ключа	Обновление клиента при каждой смене

Ни одна модель не устраняет корень доверия, все они лишь по-разному его размещают: у внешнего авторитета, у самого пользователя, у разработчика программы. Инфраструктура открытых ключей также не является панацеей. В хранилище программы лежит не один корневой сертификат, а многие десятки – по числу независимых удостоверяющих центров, и все они доверены одинаково. Компрометация любого из них компрометирует не только его клиентов: взломанный центр, как правило, ничем не ограничен по именам и выпишет сертификат на любое чужое имя. В 2011 году был взломан нидерландский удостоверяющий центр DigiNotar: злоумышленник выпустил сертификаты на имена крупных почтовых и поисковых сервисов, и они некоторое время использовались для перехвата переписки. Правило «система надежна настолько, насколько надежно ее слабейшее звено» приобретает здесь буквальный смысл.

Таким образом, вся криптографическая схема, построенная вокруг электронной подписи – примитива, который должен обеспечивать доверие к подлинности сообщения, просто переносит это доверие на другой уровень. Вопрос «кому мы доверяем и почему» криптографического ответа не имеет.

Криптография не создает доверие, а только переносит его

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

7.5. Три уровня мер на примере электронной подписи

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

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

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

В российском праве действует Федеральный закон «Об электронной подписи». Он различает три вида подписи.

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

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

Закон, действовавший до 2013 года, назывался «Об электронной цифровой подписи» и признавал по существу только третий вариант. Требование сильной криптографии с инфраструктурой сертифицированных удостоверяющих центров оказалось слишком дорогим для многих задач. Именно поэтому появилась простая подпись, которая может представлять собой просто имя в конце электронного письма. Подделать такое письмо несложно, однако при согласовании служебных записок или ознакомлении с внутренними приказами в закрытой корпоративной сети эта угроза к высоким рискам не относится. В то же время для определенных правоотношений (например, сделки с недвижимостью) закон прямо устанавливает необходимость применения именно усиленной квалифицированной подписи.