Вводная часть

Привет! Работая в DeFi, мы часто сталкиваемся с тем, что в мире криптовалют активно используются инструменты, принцип работы которых понимают единицы пользователей. Все остальные либо понимают очень смутно, либо просто не знают, что такие инструменты есть. Для того, чтобы изменить сложившееся положение вещей, мы командой Symbiosis будем популярно объяснять, как и на чём работает наш протокол и почему мы считаем, что он такой классный!

Начнём мы с одного из основных механизмов, который используется в нашем протоколе — MPC (multi-party computation). Этот механизм делает возможным создание цифровой подписи группой участников таким образом, что:

1. Ни один из участников не имеет доступа к секрету, который позволяет подпись создать.

2. Для создания подписи необходимы не все участники, а только часть группы участников — кворум.

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

MPC — очень молодой механизм по меркам криптографии. Однако он основан на криптографических инструментах, которые проверены десятилетиями. 

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

В первой статье мы начнём с самого простого — разберемся из чего состоит цифровая подпись и зачем она нужна.

Стандартная схема цифровой подписи

Для каких задач используются цифровые подписи? Исторически это 2 задачи:

1. Обеспечить аутентичность — гарантировать, что сообщение подписано именно тем, кто представилися как автор.

2. Обеспечить целостность — гарантировать, что сообщение не изменилось с момента создания подписи.

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

Таким образом, обычная подпись решает поставленные задачи не идеально. 

Цифровая подпись — это способ решения поставленных задач с помощью современных вычислительных технологий.

В случае цифровых подписей используется другой подход. Подписываемое сообщение*, подпись и публичный идентификатор — это числа**, связанные математической формулой***, которая позволяет однозначно установить, что для данного сообщения,  данная подпись была создана только тем, кто обладает данным публичным идентификатором. И никак иначе. То есть, подпись меняется в зависимости от сообщения для которого она создается.

-------------------------------
Числа**, формула*** — эти понятия мы раскроем дальше в наших публикациях
-------------------------------

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

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

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

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

Таким образом работа цифровой подписи состоит из трёх частей:

1. Алгоритм KeyGen используется для создания пары чисел: публичного и секретного ключей,

2. Алгоритм Sig используется для создания подписи, с использованием сообщения и секретного ключа,

3. Алгоритм Ver используется для проверки подписи, с использованием подписи, подписанного сообщения и публичного ключа.

Далее мы детально рассмотрим все 3 части.   

Алгоритм создания ключей KeyGen

Каждый раз алгоритм создания ключей выдает новую пару чисел sk, pk=KeyGen( ), где sk — секретный ключ, а pk — публичный. 

Число sk выбирается случайным образом, а ключ pk получается применением к sk некоторого заранее установленного одностороннего преобразования. Одностороннее преобразование — это математическая операция, которая не позволяет восстановить входные параметры по результатам.   В результате, по полученному числу pk нельзя определить исходное sk, так что никакой опасности в том, чтобы делать pk публичным значением, нет.

Классический пример одностороннего преобразования — возведение в степень по модулю. Обычное возведение в степень pk=ask, где a — какое-то фиксированное число, является взаимно однозначным: зная pk, можно единственным образом восстановить sk. Например, если a=2, pk=16, то sk=4, так как 16=24. Эта взаимная однозначность видна на графике: каждому значению sk соответствует единственное значение pk и наоборот (рис. 1).

Добиться одностороннего преобразования из операции возведения в степень, можно дополнительной операций, взятием модуля: pk=ask  mod  q, где q — еще одно целое положительное число. Эта операция возвращает остаток от деления на число q. Например, 25  mod  10=5. Взятие “mod” сразу убивает взаимную однозначность, потому что зная остаток, делимое восстановить невозможно. 

Если, например, взять pk=4, a=2, q=7, то из соотношения 4=2sk  mod  7 число sk не получится однозначно восстановить. Оно может быть равно 2, ведь 

22=4, 4  mod  7=4. 

А может быть равно 5, так как

25=32, 

32  mod  7=(28+4)  mod  7=(47+4)  mod  7=4 (рис. 2). 

Можно рассмотреть это на примере часов. Мы измеряем часы по модулю числа 12, минуты и секунда — по модулю 60. Представьте, что кто-то сказал вам: “В первый раз я посмотрел на часы, когда на них было 1:00, а во второй раз, когда на них было 3:00. Сколько времени прошло между?” Вы не сможете дать гарантированно правильный ответ, поскольку могло пройти 2 часа, 2+12=14 часов, 14+12=26 или еще больше. Операция “mod  12” стирает эту информацию.

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

Алгоритм создания подписи Sig

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

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

Например криптографическ стойкая хеш функция sha256 выдаёт числа  в диапазоне от 0 до 2256-1.  На строке “I promise to give you $5,000” выдается число 

be657fcad7933b87869835c571b60ff1444f68179326e7754c3d99babf919995.  А если теперь поменять $5,000 на $50,000, добавив всего один дополнительный 0: “I promise to give you $50,000”, — то хэш изменится на 90222db12a4a59f8d083e3cf88bf22dab15385c9946f4526a67855e6a5ff0737.

Таким образом, на вход алгоритм создания подписи получает секретный ключ sk и число m — хэш подписываемого сообщения.

На выходе алгоритм создания подписи выдает число подпись s=Sigsk, m.  Более детальный разбор алгоритма подписи ECDSA, который используется в криптовалютах, будет описан в соответствующем разделе. 

Алгоритм проверки подписи Ver

Алгоритмы KeyGen и Sig предназначены для тех, кто хочет создать свою цифровую подпись. Алгоритм Ver используется теми, кому необходимо проверить подлинность чьей-то чужой подписи. 

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

На выходе алгоритм выдает значение 1 (TRUE), если подпись прошла проверку, и значение 0 (FALSE), если нет.

Успешно пройденная проверка означает:

1. Публичный ключ pk и тот секретный ключ sk, что использовался при создании подписи, соответствуют друг другу. То есть тот, кто оставил подпись обладает секретным ключом sk. 

2. Само подписанное сообщение (хеш) не менялось с момента создания подписи.

Соответственно, подпись не пройдет проверку, если имеет место хотя бы одно из следующих обстоятельств:

1. Секретный ключ sk, использованный при создании подписи, не соответствует публичному ключу pk. То есть тот, кто выдает себя за автора, на самом деле им не является, и подпись оставил кто-то другой.

2. После того, как подпись была поставлена, сообщение было изменено.

Какое именно из этих условий повлияло на недействительность подписи, алгоритм не определяет.

В следующей статье мы расскажем об алгоритме ECDSA и о эллиптических кривых.

Авторы:

Алексей Трошичев Вдохновитель
Артём Фомичев Математик
Инга Пашенцева Редактор
Александр Половьян Проверка фактов