Схема одноразовой подписи Лэмпорта
Одноразовая подпись Лампорта - это метод построения цифровой подписи, обычно включающий использование криптографической хеш-функции. Поскольку это схема одноразовой подписи, ее можно использовать только для безопасной подписи одного сообщения.
Предположим, Алиса хочет подписать свое сообщение Бобу цифровой подписью, процесс можно объяснить в 3 этапа:
- Генерация ключей
- Генерация подписи
- Проверка подписи.
1. Генерация ключей:
- Алисе сначала нужно создать пару ключей Лампорта, закрытый ключ и соответствующий открытый ключ.
- Для создания закрытого ключа используется безопасный генератор случайных чисел для генерации 256 пар случайных чисел. Каждое число состоит из 256 бит. Алиса будет надежно хранить этот закрытый ключ. Помните, что закрытый ключ не предназначен для передачи кому-либо.
- Чтобы создать открытый ключ, Алиса хеширует каждое из 512 номеров своего закрытого ключа. Это даст еще 512 чисел, каждое из которых состоит из 256 бит. Это открытый ключ, который будет доступен всем.
В математическом представлении:
- позволять
быть положительным целым числом, 
быть набором подписываемых сообщений и 
быть односторонней хеш-функцией. - Для
а также 
, Алиса случайным образом выбирает 
и применяет одностороннюю хеш-функцию для вычисления 
. - И закрытый, и открытый ключи состоят из
ценности, 
а также 
соответственно.
2. Генерация подписи:
- Алиса хэширует свое сообщение, используя 256-битную криптографическую хеш-функцию, например SHA 256, чтобы получить 256-битный дайджест.
- Для каждого бита, в зависимости от того, является ли значение бита 1 или 0, Алиса выберет соответствующее число из пары чисел своего закрытого ключа, т.е. если бит равен 0, выбирается первое число, и если бит равен 1, выбирается второй номер. В результате получается последовательность из 256 чисел, которая является ее подписью.
- Алиса отправляет Бобу сообщение со своей подписью.
В математическом представлении
- позволять
быть тем сообщением, которое Алиса хочет подписать. - Подпись создается как
знак равно 
знак равно 
. - Эта подпись отправляется Бобу вместе с сообщением.
3. Проверка подписи:
- Боб хеширует сообщение, используя ту же 256-битную криптографическую хеш-функцию, чтобы получить 256-битный дайджест.
- Для каждого бита, в зависимости от того, является ли значение бита 1 или 0, Боб выберет соответствующее число из открытого ключа Алисы, т.е. если первый бит хэша сообщения равен 0, он выберет первый хэш в первой паре и т. Д. . Это делается так же, как показано на схеме выше. В результате получается последовательность из 256 чисел.
- Боб хеширует каждое из чисел в подписи Алисы, чтобы получить 256-битный дайджест. Если это соответствует последовательности из 256 чисел, которые ранее выбрал Боб, подпись действительна.
В математическом представлении Боб проверяет, что 
для всех
Примечание. Важно понимать, что, поскольку Алиса публично опубликовала половину закрытого ключа в качестве своей подписи, ее оставшийся закрытый ключ не может быть использован снова и должен быть уничтожен.
Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к работе в отрасли.