Гайд по криптографии: что такое электронная цифровая подпись и как она работает

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

Roadmap

Это пятый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

  • Урок 1. Исторические шифры. Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины
  • Урок 2. Распределение ключей. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
  • Урок 3. Современные отечественные шифры. Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик»
  • Урок 4. Современные зарубежные шифры. В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают
  • Урок 5. Электронная подпись. Виды электронных подписей, как они работают и как их использовать (ты здесь)
  • Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

Как работает цифровая подпись

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

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

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

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

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

Факторизация больших чисел

Рассмотрим на практике электронную подпись на основе знаменитого алгоритма RSA. Шифрование RSA мы рассматривать не стали — это мейнстрим, и в той же «Википедии» есть его подробное описание.

1. Генерация ключей

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

Когда ключи сгенерированы, можно приступить к вычислению электронной подписи.

2. Вычисление электронной подписи

3. Проверка электронной подписи

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

В общем, не стоит полагаться на стойкость этой схемы подписи RSA, особенно с такими «криптостойкими» ключами, как в нашем примере.

Дискретное логарифмирование

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

Предположим, дано уравнение 4x = 13 (mod 15). Задача нахождения x и есть задача дискретного логарифмирования. Почему же она так сложна для вычисления? Попробуй решить это уравнение перебором! Компьютер, ясное дело, будет более успешен, но и задачи дискретного логарифмирования обычно далеко не так просты. Возьмем для примера схему Эль-Гамаля.

1. Генерация подписи

2. Проверка подписи

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

ЭЦП на практике

В России, как и во многих развитых странах, электронная подпись имеет официальный юридический статус. У нас этот факт регламентирует закон № 63-ФЗ «Об электронной подписи». Однако он утверждает, что юридической силой обладает далеко не любая электронная подпись, а только соответствующая определенным критериям:

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

Подпись также должна быть вычислена средствами, соответствующими требованиям закона. Этим требованиям удовлетворяет отечественный алгоритм шифрования ГОСТ 34.10—2012. Он использует математический аппарат эллиптических кривых, является достаточно стойким и официально используется для разработки криптографических средств, реализующих электронную подпись. Для того чтобы попробовать неквалифицированную подпись — без сертификата удостоверяющего центра, можно воспользоваться известной PGP. Потестировать подпись можно, к примеру, на сайте ReadVerify.

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

За рубежом электронный документооборот процветает еще дольше. Официальный стандарт электронной подписи в США DSS (Digital Signature Standard) также использует эллиптические кривые и основан на описанной выше схеме Эль-Гамаля.

Цифровая подпись в Bitcoin

Помимо прочего, электронная подпись используется в криптовалютах, в частности — в Bitcoin. У каждого пользователя Bitcoin есть пара из секретного и открытого ключа. Хеш-значение открытого ключа служит основным адресом для передачи монет. Это значение не секретно, и сообщать его можно кому угодно. Но по значению хеша вычислить значение открытого ключа невозможно.

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

  • PUB1 — публичный ключ;
  • PRIV1 — секретный ключ;
  • HASH1 или HASH(PUB1) — хеш-значение открытого ключа (биткойн-адрес);
  • HASH2 или HASH(PUB2) — хеш открытого ключа следующего владельца.

Вот как устроен сам процесс передачи прав собственности на биткойны.

  1. Владелец монеты открыто сообщает хеш своего публичного ключа HASH(PUB1), это и будет идентифицировать биткойн.
  2. До момента продажи оба ключа PUB1, PRIV1 продавца остаются в секрете. Известен только HASH(PUB1) и соответствующий ему биткойн.
  3. Как только появляется покупатель, владелец формирует открытое письмо, в котором указывает адрес биткойна HASH(PUB1) и хеш-значение публичного ключа нового владельца HASH(PUB2). И конечно же, подписывает письмо своим секретным ключом PRIV1, прилагая публичный ключ PUB1.
  4. После этого пара ключей владельца PUB1 и PRIV1 теряют свою актуальность. Публичным ключом можно проверить само письмо, узнать новый адрес монеты.

О втором собственнике ничего не известно, кроме HASH(PUB2), до тех пор пока он не передаст права третьему владельцу. И эта цепочка может быть бесконечной.

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

Благодаря HASH(PUB) получается двойная защита. Первая загадка — узнать публичный ключ по его хешу. Вторая загадка — подписаться чужим секретным ключом.

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

Выводы

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

Комментарии (14)

      • Кому нужно, тот поймет:) крипто тема специфичная и для избранного круга читателей)

  • Уважаемая автор статьи, перед написанием стоило почитать ФЗ-63 "Об электронной подписи", согласно которому понятие электронная цифровая подпись (ЭЦП) более не существует (с 2011 года)! Теперь используется понятие электронная подпись (ЭП). Понятия открытый/закрытый ключи тоже устарели и более не актуальны. Используйте понятия ключ электронной подписи и ключ проверки электронной подписи.

    • Уважаемый автор, в словаре криптографических терминов есть понятие цифровой подписи, электронной подписи, и электронной цифровой подписи. Ключи соответственно открытые/секретные. Уважаемая автор статьи, я уверен, в качестве основного источника использовала именно этот словарь, пользующийся авторитетом в отечественных криптографических кругах.

      • Федеральный закон имеет большую юридическую силу. Я понимаю, что статья написана для тех, кто не знаком с ЭП и то, что ОК и ЗК более понятны. Но тем не менее, ФЗ-63 для справки лучше почитать.

    • Да суть не в терминах, законы постоянно меняются, сегодня один термин используется завтра уже другой, главное, что концепция остается не именной, автор про нее и пишет.
      С персональными данными тоже кучу правок навносили в ФЗ, даже в тот же ФЗ-149 об информации постоянно правят..

  • У ГОСТ 28147—89 и "Кузнечика" один и тот же недостаток, который выглядит как намеренно заложенное ослабление криптостойкости. В конкретной реализации S-блоки могут оказаться слабыми (т.е. не быть пседослучайными числами), так как нет никаких проверок их качества. Пример атаки на «Кузнечик» описан здесь: https://eprint.iacr.org/2015/096.pdf

    • Немного истории... (Посмотрел комментарии выше, заранее извиняюсь, что не все термины будут даваться согласно словарю криптографических терминов, но надеюсь, что народ поймет). Давайте по порядку. Начать хочется с того, что S боксы это не псевдослучайные числа, а все таки многомерные функции, причем мерность аргумента не всегда равна мерности функции. Во-вторых, "намеренно заложенное ослабление криптостойкости" у старого ГОСТа, который, к слову, до сих пор не является вскрытым, ни что иное, как потуги одних "нехороших людей" сделать себе имя, а других "нехороших людей" -- всего лишь предлог, чтобы не выдвигать ГОСТ в мировые стандарты: OpenSSL добавил поддержку ГОСТ только в версии 1.0.0. Более подробно: "самостоятельный" выбор слоя S боксов использовался в качестве дополнительного долговременного ключа, до тех пор пока не вышла "сокрушительная" статья Куртуа -- не мечта, а "кошмар" AESа, который, используя произвольность выбора S боксов, провел атаку на усеченную версию алгоритма, с временной сложностью в районе 2^220 (за точные числа не ручаюсь, интересующиеся могут почитать вот тут: http://eprint.iacr.org/2011/626.pdf). Ну ладно, подумали отечественные криптографы и сделали фиксированный! набор S боксов, который даже в вики можно посмотреть: давайте ломайте... В КУЗНЕЧИКе эту ошибку уже учли, и сразу сделали фиксированный набор S боксов. В третьих, о каком "намеренно заложенном ослаблении криптостойкости" может идти речь, если в статье, которую вы привели, рассматривается атака на 5!!! раундов из 10 с какой-то невообразимой временной сложность 2^140 с дополнительными требованиями памяти 2^150 и 2^113 пар открытых-шифрованных текстов. Статья из разряда: я провел атаку на усеченную версию AES: 1 пара О-Ш текст, сложность O(1), памяти не нужно, вот только раунд всего 1. В заключение хотелось бы отметить, (ИМХО) что такие статьи используются только для того, чтобы "опустить" неугодные алгоритмы, никакой практически полезной информации они не несут.

      • Спасибо, прочту подробнее. В работах Николя Куртуа действительно есть ничем не подкреплённые утверждения. К сожалению, факты и домыслы очень часто путают друг с другом. Главное, пореже делать это самому.

  • Об этом подробнее можно где-нибудь почитать?

  • И к статье небольшой комментарий. Очень глаза режет фраза "RSA собирается уходить на пенсию" и про квантовую криптографию (я так понял имелся ввиду алгоритм Шора).
    1) Про ключи длины 1024: может тот день и недалек, но тут нужны не вычислительные мощности, а теоретический скачок вперед (в современных реалиях я бы даже назвал это революцией). К тому же, что нам мешает взять ключи длины 2048 бит, вы посмотрите хотя бы сертификаты Windows, там даже модули длины 4096 можно найти. Тут я могу ошибаться, но скорее всего имелось ввиду, что на пенсию уходит протокол передачи секретного ключа с помощью RSA, и на смену ему приходит протокол выработки общего секрета ECDH. По крайней мере таков приоритет во всеми любимом OpenSSL.
    2) По поводу квантовой криптографии и факторизации числа 15))) Один криптограф (где-то читал фразу, но автора вспомнить не могу, может народ подскажет) сказал: " И собаку можно научить факторизации. К примеру, чтобы факторизовать число 15, достаточно научить ее пролаять 3 раза".

  • Спасибо, а есть подобная серия статей у Хакера про серитификаты/PKI ?

Похожие материалы