Я просматриваю одноразовую подпись Лэмпорта Диффи.
В качестве примечания; эта работа является ранней попыткой, кульминацией которой стало то, что известно как «Методы подписи на основе хэша с отслеживанием состояния»; современные конструкции включают XMSS и СУО, и удивительно близки к тому, что в статье Меркла. Вы можете найти ссылку на Wiki более доступной...
В любом случае, для решения ваших вопросов:
- Как длинные сообщения (более 100 бит) могут быть преобразованы в короткие сообщения (100 бит) с помощью односторонней функции и подписано только короткое сообщение?
Чтобы не казаться слишком упрощенным:
Мы берем длинное сообщение для подписи
Мы используем это в качестве входных данных для «односторонней функции» (современная терминология: хэш-функция), которая генерирует выходные данные фиксированного размера (в этом примере 100 бит).
Мы берем этот 100-битный вывод и применяем к нему алгоритм подписи.
Это не относится к подписям на основе хэшей; практически все алгоритмы подписи (по крайней мере, те, о которых я слышал) используют этот вариант в качестве первого шага. Единственная разница в том, что 100 бит не будут считаться достаточно длинными; обычно мы настаиваем на гораздо более длинных выходных хэшах (поскольку возможности злоумышленника значительно выросли с 1979 года, поэтому нам нужно сделать наши системы сильнее).
Неочевидный вопрос: «Почему это безопасно»? Хорошо, если мы предположим, что злоумышленник не может найти другое сообщение, которое односторонняя функция отображает на те же 100 бит, и злоумышленник не может сгенерировать подпись для того другого набора 100 битов, на который сопоставляется сообщение злоумышленника, тогда это безопасно. .
На самом деле, на практике мы беспокоимся о коллизионных атаках, когда злоумышленник имеет контроль над подписываемым действительным сообщением (но ему все равно нужно произвести подделку, то есть действительную подпись для сообщения, которое не было подписано); Меркл действительно считает это, однако давайте пока не будем усложнять ситуацию.
- "сообщение может быть зашифровано вновь сгенерированным случайным ключом..." Кто-нибудь может мне это объяснить?
Что ж, эту часть, вероятно, можно пропустить — это один из разделов документа, которому современные криптографы не следуют.
Меркл пытается определить «сертифицированную функцию шифрования» и использует для этого определенные предположения, включая рандомизированный ввод; подписываемое сообщение не рандомизировано, поэтому он вставляет функцию шифрования (со случайным ключом), чтобы оно соответствовало его предположениям.
В современной криптографии мы этого не делаем — мы обычно используем готовую хеш-функцию (такую как SHA-2 или SHAKE) и используем ее — они были разработаны (и криптоанализированы) для удовлетворения различных предположений для криптографических хеш-функции; следовательно, нам (как дизайнеру сигнатур) не нужно об этом беспокоиться.
Чтобы быть справедливым к Меркле, это может быть самый первый раз, когда кто-либо пытался понять, как будет выглядеть «устойчивая к коллизиям хэш-функция», и он сделал довольно приличную попытку — просто это не то направление, в котором пошли более поздние криптографы.
- «Метод, описанный до сих пор, страдает недостатком, заключающимся в том, что B может изменить m, заменив биты, равные 1, на 0 ...» Может кто-нибудь объяснить, как это решает проблему.
Что ж, давайте рассмотрим простейший случай; подписывая один бит. В «методе, описанном до сих пор», для создания закрытого ключа мы выбираем случайное значение $х$, и применить случайную функцию $F$ к нему, создавая общественную ценность $Ф(х)$. Затем, чтобы подписать бит «1», мы должны создать в качестве подписи $х$ (что верификатор сможет подтвердить, что $F$ сопоставляет это с открытым ключом). Однако, чтобы подписать бит «0», мы бы ничего не раскрывали. Очевидно, что тот, кто увидит действительную подпись «1», может преобразовать ее в подпись «0» (или, если уж на то пошло, сгенерировать подпись «0», ничего не видя).
В схеме Лэмпорта для подписи одного бита мы генерируем два случайных значения $х$ и $х'$, и опубликовать в качестве открытого ключа значения $Ф(х)$ и $F(х')$. Чтобы подписать 0, мы производим $х$; чтобы подписать 1, мы производим $х'$; кто-то с подписью 1 не может сгенерировать подпись 0 (потому что им пришлось бы создавать $х$, а они этого не знают).
Теперь это работает, однако это довольно дорого (в конечном итоге вам понадобится открытый ключ, который имеет в два раза больше хэш-выходов, чем битов, которые производит ваша хеш-функция - например, если ваша хэш-функция выводит 100 бит, у нее есть открытый ключ, который состоит из из 200 хэшей). Далее в документе показаны способы его уменьшения, как указано в разделах 4 и 5 документа (что и используется на практике).
