Симметричная схема цифровой подписи Диффи — Лампорта

Рассмотренные системы цифровой подписи, основанные на сложности задач разложения целых чисел на множители или логарифмирования в конечных полях, имеют один потенциальный недостаток. Он состоит в возможности построения новых эффективных алгоритмов для решения этих математических задач. Поэтому в реальных схемах длину ключа выбирают с определённым превышением необходимой величины для обеспечения достаточного запаса стойкости. Это, в свою очередь, значительно усложняет алгоритмы вычисления и проверки подписи. Поэтому представляется весьма привлекательной задача построения схем цифровой подписи на основе симметричных систем шифрования, свободных от подобных недостатков.

Пусть требуется подписать сообщение М = m₁ m_2… m_n m_i Є {0, 1} i = 1,.n

Согласно схеме Диффи Лампорта подписывающий сначала выбирает 2n случайных секретных ключей K = [(k_10, k_11),…, (k_n0, k_n1)] для используемой им симметричной шифросистемы, затем n пар случайных чисел S: S = [(S_10, S_11),…, (S_n0, S_n1)], где S_ij Є {0, 1} i = 1,.n; j = 0, 1

и вычисляет значения.

Rij = Ekij (Sij), i = 1,.n; j = 0, 1.

Наборы S и R являются открытыми и помещаются в общедоступном месте так, чтобы каждый мог прочитать их, но записать туда мог бы только автор подписи. Подпись для сообщения М имеет вид (k_1,m1,…, k_n,mn).

Чтобы убедиться в её правильности, следует проверить равенства.

Rij = Ekij (Sij), j= mi, i = 1,.n.

Недостатком этой схемы является слишком большой размер подписи, который может превышать размер самого подписываемого сообщения. Имеется несколько способов избавиться от этого недостатка. Во — первых, хранить не 2n значений секретных ключей, а лишь один секретный ключ k. Для этого можно воспользоваться, например, одной из следующих схем формирования последовательности K: k_{ij =} E_k (i, j), j = 0, 1, i = 1,.n; Во — вторых можно аналогичным образом свернуть набор открытых значений S. В — третьих можно подписывать не само сообщение, а его хэш. Вместе с тем подобные модификации не устраняют главного недостатка рассматриваемых подписей, состоящего в том что после проверки подписи либо весь секретный ключ, либо его часть становятся известными проверяющему. Поэтому рассмотренная схема цифровой подписи является по существу одноразовой.