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

 

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, особенно с такими «криптостойкими» ключами, как в нашем примере.

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов. Подробнее о подписке

Вариант 2. Купи один материал

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.


14 комментария

  1. derek78

    15.12.2016 at 12:56

    Круто хотя я ничего не поняла

  2. maximalmax90

    16.12.2016 at 02:21

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

    • wanderer5800

      18.12.2016 at 20:21

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

      • maximalmax90

        19.12.2016 at 05:11

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

    • RobotNed

      24.12.2016 at 21:39

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

  3. 84ckf1r3

    17.12.2016 at 23:09

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

    • wanderer5800

      18.12.2016 at 19:45

      Немного истории… (Посмотрел комментарии выше, заранее извиняюсь, что не все термины будут даваться согласно словарю криптографических терминов, но надеюсь, что народ поймет). Давайте по порядку. Начать хочется с того, что 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. В заключение хотелось бы отметить, (ИМХО) что такие статьи используются только для того, чтобы «опустить» неугодные алгоритмы, никакой практически полезной информации они не несут.

      • 84ckf1r3

        18.12.2016 at 21:26

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

  4. Veneficus

    18.12.2016 at 15:22

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

  5. wanderer5800

    18.12.2016 at 20:04

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

  6. Kanar

    19.12.2016 at 14:03

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

Оставить мнение

Check Also

Украинская киберполиция задержала четырех создателей фиктивных криптовалютных обменников

Правоохранительные органы Украины сообщили о задержании четырех членов преступной группы, …