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

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

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

Теперь Алиса хочет подписать сообщение. Для начала она хеширует сообщение и получает 256-битный хеш. Затем, для каждого бита в этом хеше, она берёт соответствующее число из секретного ключа. Если, например, первый бит в хеше сообщения равен нулю, она берёт первое число из первой пары секретного ключа. Если же первый бит равен единице, она использует второе число из первой пары. И так далее. В итоге получается 256 случайных чисел, размер которых составляет 256×256 бит = 8 КиБ. Эти числа и составляют подпись, которую Алиса отправляет вместе с сообщением.

Стоит обратить внимание, что после того как Алиса использовала свой секретный ключ, он никогда не должен быть использован снова. Остальные 256 чисел, которые она не использовала в подписи, Алиса никогда не должна публиковать или использовать. Предпочтительно, чтобы она их удалила, так как иначе кто-то может получить к ним доступ и сгенерировать с их помощью поддельную подпись.

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

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

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

Используя генератор случайных чисел, Алиса получает восемь пар случайных чисел. Эти 16 чисел являются закрытым ключом Алисы.

Закрытый ключ: ${\displaystyle (13,}$ ${\displaystyle 134)}$ ${\displaystyle (128,}$ ${\displaystyle 67)}$ ${\displaystyle (25,}$ ${\displaystyle 90)(78,}$ ${\displaystyle 156)}$ ${\displaystyle (89,}$ ${\displaystyle 37)}$ ${\displaystyle (234,}$ ${\displaystyle 29)}$ ${\displaystyle (199,}$ ${\displaystyle 74)}$ ${\displaystyle (12,}$ ${\displaystyle 3)}$

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

Открытый ключ:

${\displaystyle (00101010,}$ ${\displaystyle 10010101)}$

${\displaystyle (01100111,}$ ${\displaystyle 11010101)}$

${\displaystyle (00101110,}$ ${\displaystyle 11110111)}$

${\displaystyle (00100101,}$ ${\displaystyle 11011101)}$

${\displaystyle (11100001,}$ ${\displaystyle 00011000)}$

${\displaystyle (11000110,}$ ${\displaystyle 11001110)}$

${\displaystyle (11001101,}$ ${\displaystyle 11001001)}$

${\displaystyle (11100011,}$ ${\displaystyle 11111101)}$

Получившийся открытый ключ Алиса публикует в общий доступ.

Алиса хочет подписать сообщение M = «Lamport». Для этого она вычисляет значение хеш-функции от этого сообщения ${\displaystyle H(M)=01011010}$ и ставит в соответствие каждому биту хеша одно из значений в парах закрытого ключа, тем самым формируя подпись.

Подпись сообщения «Lamport»: ${\displaystyle (13,}$ ${\displaystyle 67,}$ ${\displaystyle 25,}$ ${\displaystyle 156,}$ ${\displaystyle 37,}$ ${\displaystyle 234,}$ ${\displaystyle 74,}$ ${\displaystyle 12)}$

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

Набор чисел, полученный из открытого ключа:

${\displaystyle 00101010,}$

${\displaystyle 11010101,}$

${\displaystyle 00101110,}$

${\displaystyle 11011101,}$

${\displaystyle 00011000,}$

${\displaystyle 11000110,}$

${\displaystyle 11001001,}$

${\displaystyle 11100011}$

Хеш подписи:

${\displaystyle 00101010,}$

${\displaystyle 11010101,}$

${\displaystyle 00101110,}$

${\displaystyle 11011101,}$

${\displaystyle 00011000,}$

${\displaystyle 11000110,}$

${\displaystyle 11001001,}$

${\displaystyle 11100011}$

Так как данные наборы равны — подпись настоящая.

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

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

Секретный ключ ${\displaystyle K}$ состоит из ${\displaystyle 2k}$ значений ${\displaystyle y_{i,j}}$. Открытый ключ состоит из ${\displaystyle 2k}$ значений ${\displaystyle z_{i,j}}$.[3]

Пусть ${\displaystyle m=m_{1}\ldots m_{k}\in \{0,1\}^{k}}$ — сообщение.

Подпись сообщения — это ${\displaystyle sign(m_{1}\ldots m_{k})=(y_{1,m_{1}},\ldots ,y_{k,m_{k}})=(s_{1},\ldots ,s_{k})}$.

Сторона, валидирующая подпись, проверяет ${\displaystyle f(s_{i})=z_{i,m_{i}}}$ для всех ${\displaystyle 1\leq i\leq k}$.

Чтобы подделать подпись сообщения криптоаналитику придется инвертировать одностороннюю функцию ${\displaystyle f}$, а это предполагается вычислительно невозможным.

Дерево Меркла с восемью листовыми элементами

Для начала необходимо сгенерировать ${\displaystyle 2^{n}}$ закрытых одноразовых ключей Лэмпорта ${\displaystyle X_{i}}$ и открытых одноразовых ключей Лэмпорта ${\displaystyle Y_{i}}$. Далее для каждого открытого ключа ${\displaystyle Y_{i}}$, где ${\displaystyle 1\leq i\leq 2^{n}}$, вычисляется его хеш ${\displaystyle h_{i}=H(Y_{i})}$. И на основе этих значений ${\displaystyle h_{i}}$ строится дерево Меркла.

Пронумеруем узлы дерева ${\displaystyle a_{i,j}}$ таким образом, что индекс ${\displaystyle i}$ обозначает расстояние от этого узла до листового элемента, а индекс ${\displaystyle j}$ обозначает порядковый номер узла слева направо на одном уровне ${\displaystyle i}$.

В нашем дереве хеш значения ${\displaystyle h_{i}}$ являются листовыми элементами, то есть ${\displaystyle h_{i}=a_{0,i}}$. Каждый нелистовой узел дерева представляет из себя хеш-значение от соединения вместе двух детей, то есть ${\displaystyle a_{1,0}=H(a_{0,0}||a_{0,1})}$, ${\displaystyle a_{2,0}=H(a_{1,0}||a_{1,1})}$ и так далее.

Таким образом, мы имеем дерево, корневой элемент которого и является нашим открытым ключом ${\displaystyle pub}$.

Вычисление пути до вершины в дереве Меркла

Чтобы подписать сообщение по нашей схеме, сначала нужно подписать его одноразовой подписью Лэмпорта ${\displaystyle sig'}$. Это делается, используя одну из пар открытых/закрытых ключей ${\displaystyle (X_{i},Y_{i},)}$.

${\displaystyle a_{0,i}=H(X_{i})}$ — соответствующий открытому ключу ${\displaystyle X_{i}}$ листовой элемент дерева. Путь от листового элемента ${\displaystyle a_{0,i}}$ дерева к его вершине состоит из элементов ${\displaystyle A_{0},...A_{n}}$, где ${\displaystyle A_{0}=a_{0,i}}$ — листовой элемент, а ${\displaystyle A_{n}=a_{n,0}=pub}$ — вершина дерева. Чтобы вычислить этот путь, нам необходимы все дети узлов ${\displaystyle A_{1},...,A_{n}}$. Мы знаем, что узел ${\displaystyle A_{i}}$ — дочерний элемент узла ${\displaystyle A_{i+1}}$. Чтобы вычислить следующий узел на пути к вершине нам нужны оба дочерних элемента узла ${\displaystyle A_{i+1}}$. Поэтому нам нужно знать «брата» узла ${\displaystyle A_{i}}$. Назовём его ${\displaystyle auth_{i}}$. Итак, ${\displaystyle A_{i+1}=H(A_{i}||auth_{i})}$. Следовательно, нам нужны ${\displaystyle n}$ узлов ${\displaystyle auth_{0},...,auth_{n-1}}$, чтобы вычислить вершину дерева. Мы вычисляем их и сохраняем.

Эти узлы в совокупности с одноразовой подписью ${\displaystyle sig'}$ сообщения ${\displaystyle M}$ составляют итоговую подпись ${\displaystyle sig=(sig'||X_{i}||auth_{0}||auth_{1}||...||auth_{n-1})}$.

Получатель сообщения имеет в распоряжении открытый ключ ${\displaystyle pub}$, сообщение ${\displaystyle M}$ и подпись ${\displaystyle sig=(sig'||X_{i}||auth_{0}||auth_{1}||...||auth_{n-1})}$. Сначала он проверяет одноразовую подпись ${\displaystyle sig'}$ сообщения ${\displaystyle M}$. Если она подлинна, получатель вычисляет ${\displaystyle A_{0}=H(X_{i})}$. И далее для ${\displaystyle j=1,..,n-1}$ вычисляет ${\displaystyle A_{j}=H(A_{j-1}||auth_{j-1})}$. Если ${\displaystyle A_{n}}$ оказывается равна ${\displaystyle pub}$, то подпись считается подлинной.

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

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

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

Схема цифровой подписи Лэмпорта не требует, чтобы сообщение m было захешировано перед тем, как оно будет подписано. Хеширование может быть использовано, например, для подписания длинных сообщений, где подписываться будет хеш сообщения, а не оно само[6].