Рейтинг:2

Однократная подпись Лэмпорта Диффи

флаг no

я прохожу через Лэмпорт Диффи Одноразовая подпись. мне трудно понять

  1. Как длинные сообщения (более 100 бит) могут быть преобразованы в короткие сообщения (100 бит) с помощью односторонней функции и подписано только короткое сообщение? Может ли кто-нибудь объяснить это на примере? (См. стр. 13 в прикрепленном документе.)

  2. «сообщение может быть зашифровано подписывающей стороной с помощью вновь сгенерированного случайного ключа до того, как оно будет подписано, и случайный ключ будет добавлен к сообщению. Таким образом, подписанное сообщение будет случайным (при условии, что шифрование случайным ключом эффективно рандомизирует сообщение, факт, который обычно признается современным шифрованием функции [11]). Эти шаги будут удовлетворять условиям для свойства 2. Поэтому мы можем предположить без ограничения общности, что все сообщения имеют фиксированную длину, например, 100 бит». Кто-нибудь может мне это объяснить? в прикрепленном документе.)

  3. «Описанный до сих пор метод страдает тем недостатком, что В может изменить m, заменив биты, которые являются единицами, на биты D. В просто отрицает, что он когда-либо получал xj ' (несмотря на тот факт, что он это сделал). Однако биты D нельзя изменить на 1. Лэмпорт и Диффи преодолели эту проблему, подписав новое сообщение m', которое ровно в два раза длиннее m и вычисляется путем конкатенации m с побитовым дополнением m. То есть каждый бит m в J исходном сообщении равен представлен двумя битами, mj и дополнением m в новом сообщении m'.Ясно, что один или другой бит J должен быть равен O. Чтобы изменить сообщение, B должен превратить 0 в 1, чего он не может сделать». Кто-нибудь может объяснить, как это решает проблему. (Пожалуйста, обратитесь к стр. 14)

Я пытаюсь читать о технологиях в криптопространстве прямо сейчас. Я начал с прикрепленного документа, потому что он упоминался в здесь. Если вы считаете, что есть ресурсы, которые подробно объясняют прилагаемый документ, но так, чтобы его понял новичок, я был бы вам очень признателен.

Рейтинг:3
флаг my

Я просматриваю одноразовую подпись Лэмпорта Диффи.

В качестве примечания; эта работа является ранней попыткой, кульминацией которой стало то, что известно как «Методы подписи на основе хэша с отслеживанием состояния»; современные конструкции включают XMSS и СУО, и удивительно близки к тому, что в статье Меркла. Вы можете найти ссылку на Wiki более доступной...

В любом случае, для решения ваших вопросов:

  1. Как длинные сообщения (более 100 бит) могут быть преобразованы в короткие сообщения (100 бит) с помощью односторонней функции и подписано только короткое сообщение?

Чтобы не казаться слишком упрощенным:

  • Мы берем длинное сообщение для подписи

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

  • Мы берем этот 100-битный вывод и применяем к нему алгоритм подписи.

Это не относится к подписям на основе хэшей; практически все алгоритмы подписи (по крайней мере, те, о которых я слышал) используют этот вариант в качестве первого шага. Единственная разница в том, что 100 бит не будут считаться достаточно длинными; обычно мы настаиваем на гораздо более длинных выходных хэшах (поскольку возможности злоумышленника значительно выросли с 1979 года, поэтому нам нужно сделать наши системы сильнее).

Неочевидный вопрос: «Почему это безопасно»? Хорошо, если мы предположим, что злоумышленник не может найти другое сообщение, которое односторонняя функция отображает на те же 100 бит, и злоумышленник не может сгенерировать подпись для того другого набора 100 битов, на который сопоставляется сообщение злоумышленника, тогда это безопасно. .

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

  1. "сообщение может быть зашифровано вновь сгенерированным случайным ключом..." Кто-нибудь может мне это объяснить?

Что ж, эту часть, вероятно, можно пропустить — это один из разделов документа, которому современные криптографы не следуют.

Меркл пытается определить «сертифицированную функцию шифрования» и использует для этого определенные предположения, включая рандомизированный ввод; подписываемое сообщение не рандомизировано, поэтому он вставляет функцию шифрования (со случайным ключом), чтобы оно соответствовало его предположениям.

В современной криптографии мы этого не делаем — мы обычно используем готовую хеш-функцию (такую ​​как SHA-2 или SHAKE) и используем ее — они были разработаны (и криптоанализированы) для удовлетворения различных предположений для криптографических хеш-функции; следовательно, нам (как дизайнеру сигнатур) не нужно об этом беспокоиться.

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

  1. «Метод, описанный до сих пор, страдает недостатком, заключающимся в том, что B может изменить m, заменив биты, равные 1, на 0 ...» Может кто-нибудь объяснить, как это решает проблему.

Что ж, давайте рассмотрим простейший случай; подписывая один бит. В «методе, описанном до сих пор», для создания закрытого ключа мы выбираем случайное значение $х$, и применить случайную функцию $F$ к нему, создавая общественную ценность $Ф(х)$. Затем, чтобы подписать бит «1», мы должны создать в качестве подписи $х$ (что верификатор сможет подтвердить, что $F$ сопоставляет это с открытым ключом). Однако, чтобы подписать бит «0», мы бы ничего не раскрывали. Очевидно, что тот, кто увидит действительную подпись «1», может преобразовать ее в подпись «0» (или, если уж на то пошло, сгенерировать подпись «0», ничего не видя).

В схеме Лэмпорта для подписи одного бита мы генерируем два случайных значения $х$ и $х'$, и опубликовать в качестве открытого ключа значения $Ф(х)$ и $F(х')$. Чтобы подписать 0, мы производим $х$; чтобы подписать 1, мы производим $х'$; кто-то с подписью 1 не может сгенерировать подпись 0 (потому что им пришлось бы создавать $х$, а они этого не знают).

Теперь это работает, однако это довольно дорого (в конечном итоге вам понадобится открытый ключ, который имеет в два раза больше хэш-выходов, чем битов, которые производит ваша хеш-функция - например, если ваша хэш-функция выводит 100 бит, у нее есть открытый ключ, который состоит из из 200 хэшей). Далее в документе показаны способы его уменьшения, как указано в разделах 4 и 5 документа (что и используется на практике).

redd avatar
флаг no
Прежде всего, большое спасибо за ответ и за ваши усилия. Я был расстроен из-за того, что не смог понять содержание статьи, и ваш ответ сделал мой день и дал мне надежду!
redd avatar
флаг no
В ответ на ваш первый ответ. Мое понимание алгоритма подписи состоит в том, что для каждого бита в передаваемом сообщении существует секретный ключ и связанный с ним открытый ключ. Что я имею в виду под каждым битом, так это то, что (используя пример, упомянутый в прикрепленном документе), скажем, я буду продавать акции, каждый бит в сообщении будет указывать стороне B, какие акции продавать. Если мы сопоставим сообщение с новым 100-битным хешем (ссылаясь на ваш пример), как сторона B узнает, какие акции продавать? Потому что исходное сообщение преобразуется в этот новый 100-битный хэш.
redd avatar
флаг no
Вы ссылаетесь на «устойчивую к коллизиям хеш-функцию», когда говорите, что вы говорите о хеш-функциях, которые не производят одинаковый результат для разных входных данных? Насколько это проблематично на практике?
redd avatar
флаг no
В отношении ответа 3 в вашем посте. Ну разве это не уязвимость, когда, скажем, сторона A отправляет стороне B действительное подписанное сообщение, не может ли сторона B просто сказать, что он не получил никакого сообщения, которое было подписано? Как они обходят эту проблему?
poncho avatar
флаг my
@redd: пункт 1: подпись предназначена для того, чтобы люди могли проверить сообщение, а не для его передачи. Предполагается, что B отправил копию сообщения вместе с подписью.
poncho avatar
флаг my
@redd: «устойчивая к коллизиям хеш-функция» - это не та функция, в которой буквально нет двух входных данных, которые хешируют одно и то же значение (легко показать, что для любой такой функции выход как минимум равен входу) . Наоборот, это тот случай, когда слишком сложно (мы не знаем, как это сделать с имеющимися у нас ресурсами) найти два разных значения, которые хэшируют одинаково.
poncho avatar
флаг my
@redd: пункт 3: смысл подписи заключается в том, чтобы разрешить, что сообщение было отправлено точно так, как есть, А. Оно не для того, чтобы помешать Б заявить, что он его не получил; это делается для того, чтобы B не утверждал, что A отправляет другое сообщение (и кто-то, кроме A, не отправляет B другое сообщение)

Ответить или комментировать

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