ДНЕВНИК СТУДЕНТКИ: Цифровая подпись

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

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

Какие у нас есть требования к подписи?

• чтобы только ты мог подписать, а все могли проверить/удостовериться, что это твоя подпись
• чтобы подпись была закреплена за определенным документом - нельзя вырезать и прицепить к другому документу
• чтобы ее нельзя было подделать

Итак, чтобы подписать своей уникальной электронной подписью какой-либо электронный документ или его часть, вам необходимо прибегнуть к такой схеме:

1. (sk, pk) := generateKeys(keysize) – это операция по генерации двух кусочков информации секретного ключа (sk) и публичного ключа (pk).
   Передавать в функцию generateKeys надо информацию о том, какой размер ключа в битах тебе нужен на выходе. При совершении этой криптографической операции, профессор советует быть очень тщательными в выборе алгоритмов для генерации ключей - качественная генерация случайностей.
   Секретный ключ sk ты копируешь себе и никому не показываешь.
   Публичный ключ pk могут видеть все. Ты, например, можешь опубликовать его у себя на сайте.

1. sig := sign(sk, message) — это операция по подписыванию, собственно. Ты берешь 2 кусочка информации (твой секретный ключ и документ/сообщение) и передаешь в функцию. На выходе получаешь криптографически преобразованный кусочек информации, в котором твоя подпись связана с документом. Этот кусочек информации ты можешь посылать/публиковать - он защищен от подделывания или внесения изменений. Этот этап также требует использования качественных алгоритмов рандомизации (генерации случайностей).

1. isValid := verify(pk, message, sig) – это операция по проверке твоей подписи. Для ее выполнения необходимо иметь 3 кусочка информации: публичный ключ pk, документ/сообщение message и подписанный документ/сообщение sig. Итог этой операции - логическое значение isValid, которое будет верно (true), если sig является корректной подписью.

verify (pk, message, sign(sk, message))=true

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

Как мы можем быть уверены, что подпись нельзя подделать?

Это свойство невозможности подделать, Unforgeability, объясняется в курсе таким примером игры (упрощенный вариант):

• Представьте, что есть некий мошенник, который заявляет о том, что он может подделать мою цифровую подпись (attacker)
• Чтобы доказать невозможность этого, я принимаю вызов от него и предоставляю разную информацию (challenger)
• Я с помощью операции generateKeys создаю 2 ключа - секретный прячу, публичный показываю всем, в том числе и мошеннику
• Далее мошенник запрашивает у меня какой-либо подписанный документ - я его генерирую с помощью операции sign(sk, message) и отправляю ему
• Мошенник теперь имеет в своем арсенале публичный ключ pk и подписанный документ sig
• Поскольку я знаю, что подпись нельзя подделать, я спокойно могу отправлять разные подписанные документы мошеннику много раз
• Когда мошенник готов, он присылает документ с "поддельной" подписью для проверки с помощью verify(pk, message, sig)
• Если verify (pk, message, sign(sk, message))=true - он выиграл
• В результате игры вот что выходит - даже в случае, если я ему отправлю миллион (но не 2^80) разных подписанных документов - он никак не может вытащить оттуда никакими алгоритмами мой секретный ключ, кроме как до бесконечности перебирать варианты
• Вероятность подделывания подписи настолько мала, что принято считать схему подписи невозможно подделать (еще раз, все это работает, если при генерации ключей и шифровании подписи используются алгоритмы с хорошим уровнем генерации случайностей)

точный текст профессора:

what we say is that the attacker's probability of winning this game is negligible, and that that's true no matter what algorithm the attacker is using. In other words, we're going to say that the signature scheme is unforgeable if, no matter what algorithm the attacker is using, the attacker has only a negligible chance of successfully forging a message.

Elliptic Curve Digital Signature Algorithm (ECDSA) - это название схемы цифровой подписи, которая используется Биткоином и является государственным стандартом в США. Алгоритмы, которые шифруют здесь информацию, основываются на проблеме дискретного логарифма в группе точек эллиптической кривой. Нам, простым смертным, понятно лишь, что эти группы точек эллиптической кривой - сильная и надежная вещь на уровне высшей математики.

Что еще надо добавить?

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

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

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

Еще раз, друзья, я создаю этот контент на основе онлайн-курса Bitcoin and Cryptocurrency Technologies - каждый может подписаться и бесплатно учиться.

Для тех, кому полезна информация о криптографических примитивах, обратите внимание на мои предыдущие посты в этом цикле:

• Криптографическая хэш-функция и ее свойства!

• Что за чудо дивное эта функция SHA-256?

• Структуры данных Блокчейн и Дерево Меркля

Следующая тема в цикле криптографических технологий - публичные ключи как личности (англ: identities), так что подписывайтесь на мой дневник!

@studentka