Подпись Лэмпорта

В криптографии подпись Лампорта или схема одноразовой подписи Лампорта — это метод построения цифровой подписи . Подписи Лампорта могут быть созданы из любой криптографически безопасной односторонней функции ; обычно криптографическая хэш-функция используется .

Хотя потенциальное развитие квантовых компьютеров угрожает безопасности многих распространенных форм криптографии, таких как RSA , считается, что подписи Лэмпорта с большими хеш-функциями в этом случае все равно будут безопасными. Каждый ключ Лампорта можно использовать только для подписи одного сообщения. Однако многие подписи Лампорта могут обрабатываться одним хеш-деревом Меркла , поэтому для многих сообщений можно использовать один ключ хэш-дерева, что делает эту схему цифровой подписи довольно эффективной.

Криптосистема подписи Лэмпорта была изобретена в 1979 году и названа в честь ее изобретателя Лесли Лэмпорта .

Пример

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

Создание пары ключей

Для создания закрытого ключа Алиса использует генератор случайных чисел для создания 256 пар случайных чисел (всего 2×256 чисел), каждое число имеет размер 256 бит, то есть всего 2×256×256 бит = 128 кибит. всего. Это ее личный ключ, и она сохранит его в надежном месте для дальнейшего использования.

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

Подписание сообщения

Позже Алиса хочет подписать сообщение. Сначала она хеширует сообщение до 256-битной хеш-суммы. Затем для каждого бита хеша на основе значения бита она выбирает одно число из соответствующих пар чисел, составляющих ее закрытый ключ (т. е., если бит равен 0, выбирается первое число, а если бит равен 1, выбирается второй). В результате получается последовательность из 256 чисел. Поскольку каждое число само по себе имеет длину 256 бит, общий размер ее подписи составит 256×256 бит = 65536 бит = 64 кибита. Эти (первоначально случайно выбранные) числа являются ее подписью, и она публикует их вместе с сообщением.

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

Проверка подписи

Затем Боб хочет проверить подпись сообщения Алисы. Он также хэширует сообщение, чтобы получить 256-битную хэш-сумму. Затем он использует биты хеш-суммы, чтобы выбрать 256 хэшей открытого ключа Алисы. Он выбирает хэши таким же образом, как Алиса выбирает случайные числа для подписи. То есть, если первый бит хеша сообщения равен 0, он выбирает первый хеш из первой пары и так далее.

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

Обратите внимание, что до того, как Алиса опубликовала подпись сообщения, никто больше не знал случайных чисел 2×256 в закрытом ключе. Таким образом, никто другой не сможет создать для подписи правильный список из 256 случайных чисел. И после того, как Алиса опубликовала подпись, другие все еще не знают остальных 256 случайных чисел и, следовательно, не могут создавать подписи, соответствующие другим хешам сообщений.

Формальное описание

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

Ключи

Позволять $k$ целое положительное число и пусть $P=\{0,1\}^{k}$ быть набором сообщений. Позволять $f:\,Y\rightarrow Z$ быть односторонней функцией .

Для $1\leq i\leq k$ и $j\in \{0,1\}$ подписывающая сторона выбирает $y_{i,j}\in Y$ случайным образом и вычисляет $z_{i,j}=f(y_{i,j})$.

Закрытый ключ, $K$, состоит из $2k$ ценности $y_{i,j}$. Открытый ключ состоит из $2k$ ценности $z_{i,j}$.

Подписание сообщения

Позволять $m=m_{1}\ldots m_{k}\in \{0,1\}^{k}$ быть сообщением.

Подпись сообщения есть

$\operatorname {sig} (m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})$.

Проверка подписи

Верификатор проверяет подпись, проверяя что $f(s_{i})=z_{i,m_{i}}$ для всех $1\leq i\leq k$.

Чтобы подделать сообщение, Еве придется инвертировать одностороннюю функцию. $f$. Предполагается, что это неразрешимо для входов и выходов подходящего размера.

Параметры безопасности

Безопасность подписей Лампорта основана на безопасности односторонней хеш-функции и длине ее вывода.

Для хеш-функции, которая генерирует n-битный дайджест сообщения, идеальное сопротивление прообразу и второму прообразу при одном вызове хеш-функции подразумевает порядок 2. ^н операции по поиску коллизий в рамках классической вычислительной модели. Согласно алгоритму Гровера , обнаружение коллизии прообразов при одном вызове идеальной хеш-функции является верхней границей O(2 ^{н /2} ) операции в рамках модели квантовых вычислений. В подписях Лэмпорта каждый бит открытого ключа и подписи основан на коротких сообщениях, требующих только одного вызова хэш-функции.

Для каждого закрытого ключа y _i,j и соответствующей ему пары открытых ключей z _i,j длина закрытого ключа должна быть выбрана так, чтобы атака по прообразу на длину входных данных была не быстрее, чем атака по прообразу на длину входных данных. выход. Например, в вырожденном случае, если каждый элемент закрытого ключа y _i,j имел длину всего 16 бит, тривиально выполнить исчерпывающий поиск по всем 2 элементам. ¹⁶ возможные комбинации секретных ключей в 2 ¹⁶ операции для поиска совпадения с выходными данными независимо от длины дайджеста сообщения. Таким образом, сбалансированная конструкция системы гарантирует, что обе длины примерно равны.

На основе алгоритма Гровера, квантовобезопасной системы, длина элементов открытого ключа z _i,j , элементов закрытого ключа y _i,j и элементов подписи s _i,j должна быть не менее чем в 2 раза больше рейтинга безопасности. системы. То есть:

• 80-битная безопасная система использует длину элементов не менее 160 бит;
• 128-битная безопасная система использует длину элементов не менее 256 бит;

Однако следует проявлять осторожность, поскольку приведенные выше идеалистические оценки работы предполагают идеальную (идеальную) хеш-функцию и ограничиваются атаками, нацеленными только на один прообраз за раз. В рамках традиционной вычислительной модели известно, что если 2 ^{3 н /5} осуществляется поиск прообразов, полная стоимость прообраза снижается с 2 ^{н /2} до 2 ^{2 н /5} . Выбор оптимального размера элемента с учетом сбора нескольких дайджестов сообщений является открытой проблемой. Выбор элементов большего размера и более сильных хэш-функций, таких как 512-битные элементы и SHA-512, обеспечивает больший запас безопасности для управления этими неизвестными.

Оптимизации и варианты

Короткий закрытый ключ

Вместо создания и хранения всех случайных чисел закрытого ключа можно сохранить один ключ достаточного размера. (Обычно того же размера, что и одно из случайных чисел в секретном ключе.) Затем одиночный ключ можно использовать в качестве начального числа для криптографически безопасного генератора псевдослучайных чисел (CSPRNG) для создания всех случайных чисел в секретном ключе, когда это необходимо. Обратите внимание, что криптографически безопасный хеш (или, по крайней мере, вывод которого не подвергается XOR с начальным числом) не может использоваться вместо CSPRNG, поскольку подписание сообщения раскроет дополнительные случайные значения из закрытого ключа. Если злоумышленник сможет получить доступ к подписи раньше, чем предполагаемые получатели, то он сможет подделать подпись с понижением уровня безопасности вдвое для каждого удвоения выявленных случайных значений из закрытого ключа.

Таким же образом один ключ можно использовать вместе с CSPRNG для создания множества ключей Лампорта. какой-то постквантовый безопасный CSPRNG с произвольным доступом Предпочтительно тогда использовать . Примечательно, что классический CSPRNG, такой как BBS, использовать не следует.

Короткий открытый ключ

Подпись Лампорта можно комбинировать со списком хешей , что позволяет публиковать только один верхний хеш вместо всех хэшей открытого ключа. То есть вместо $2k$ ценности $z_{ij}$. Для проверки по единственному верхнему хешу подпись должна включать случайные числа и неиспользуемые хеши из списка хэшей открытого ключа, в результате чего размер подписей увеличивается примерно в два раза. То есть значения $(z_{ij})$ для всех $j\neq m_{i}$ необходимо включить.

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

Короткие клавиши и подпись

Сжатие подписи Winternitz уменьшает размер закрытого и открытого ключей чуть менее чем в два раза. $2\langle {\text{chunk size in bits}}\rangle$и половина этого коэффициента для подписи. Объем вычислений увеличивается чуть более чем в 1 раз. $2^{\langle {\text{chunk size in bits}}\rangle }/\langle {\text{chunk size in bits}}\rangle$. Вместо требования CSPRNG достаточно криптографически безопасного хеша.

Хэш-список также можно использовать для сокращения открытого ключа до одного значения за счет удвоения размера подписи, как описано в предыдущем разделе.

Открытый ключ для нескольких сообщений

Основная статья: Схема подписи Меркла

Каждый открытый ключ Лампорта можно использовать только для подписи одного сообщения, а это означает, что для подписания многих сообщений необходимо опубликовать множество ключей. Но для этих открытых ключей можно использовать хэш-дерево , публикуя вместо этого верхний хэш дерева хэшей. Это увеличивает размер результирующей подписи, поскольку в подпись должна быть включена ветвь хеш-дерева, но позволяет публиковать один хэш, который затем можно использовать для проверки большого количества будущих подписей.

См. также

• S/КЛЮЧ

Дальнейшее чтение

• Л. Лэмпорт , Построение цифровых подписей на основе односторонней функции , Технический отчет SRI-CSL-98, Международная лаборатория компьютерных наук SRI, октябрь 1979 г.
• Эффективное использование деревьев Меркла - объяснение в лабораториях RSA первоначального назначения деревьев Меркла + подписей Лэмпорта как эффективной схемы одноразовой подписи.
• Введение в подписи на основе хеша и подписи Меркла Адама Лэнгли.
• Эталонная реализация схемы Лэмпорта поверх BLAKE2b (C++)
• Эталонная реализация подписей Лампорта поверх SHA256, SHA512 или Blake2b (Rust)