ESIGN (англ.Efficient digital SIGNature — эффективная цифровая подпись) — схема цифровой подписи с открытым ключом, основанная на проблеме факторизации чисел. Отличительной чертой данной схемы является возможность быстрой генерации подписи.[1]
Цифровая подпись была разработана в японской компании NTT в 1985 году.[2] Схема оказалась эффективна в плане скорости генерации цифровой подписи. Однако первые версии были взломаны Эрни Брикеллом (англ.Ernie Btickel) и Джоном ДеЛаурентисом (англ.John DeLaurentis), после чего рекомендованные параметры алгоритма были модифицированы.[3] Последующие попытки взлома оказались безуспешными. Авторы уверяют, что сложность взлома последней версии ESIGN сравнима со сложностью задачи факторизации числа вида , где и — простые числа.[4]
В протоколе участвуют два субъекта: субъект , цель которого — доказать то, что является автором сообщения , и субъект , целью которого является проверка авторства. В ESIGN для осуществления поставленных целей и должны совершить следующие действия[5].
Предварительно, генерирует ключи: открытый, известный всем, и закрытый, известный только субъекту .
Субъект генерирует цифровую подпись для сообщения на основе закрытого ключа.
отправляет сообщение вместе с подписью субъекту .
Субъект проверяет достоверность подписи на основе открытого ключа.
В изначально предложенном варианте ESIGN параметр был равен двум.[5] Однако после успешной атаки Эрни Брикелла и Джона ДеЛаурентиса, которая распространялась также на вариант схемы с , авторы изменили требование к этому параметру на существующее .[7]
Атаки на хеш-функцию с целью подделки подписи основаны на ее несовершенности, то есть на несоответствии хеш-функции одному или нескольким критериям криптографической стойкости c той оговоркой, что в случае ESIGN равенства в критериях стоит понимать с точностью до старших бит. Это послабление связано с условием проверки подписи, которое выполняется не только для исходного значения хеш-функции, но и для прочих, совпадающих в первых старших битах.
Допустим, что функция неустойчива к поиску коллизий, то есть можно найти такие различные и , что и совпадают в первых старших битах. Тогда, подписывая сообщение , автор , ничего не подозревая, автоматически подписывает сообщение , так как выполняется неравенство
Если выбранная хеш-функция криптографически стойкая, то атака с использованием коллизий займет операций вычисления хеш-функции, атака с использованием второго прообраза — операций, что считается неосуществимым, при больших .[8][9]
Атака на открытый ключ заключается в попытке получить на его основе закрытый ключ . Сделать это можно, решив уравнение , то есть факторизовав число . Можно заметить, что в RSA число генерируется похожим образом, там , но на сегодняшний день вопрос о том, в каком из случаев факторизация становится проще или сложнее, остается открытым, так как эффективных алгоритмов факторизации до сих пор нет. На данный момент самым быстрым способом факторизовать число , что для ESIGN, что для RSA, является метод решета числового поля, который делает это со скоростью, зависящей от битовой длины . Однако, при большой битовой длине числа задача факторизации становится невыполнимой.[10][9]
Помимо уже введенных ограничений в описании ESIGN, для большей безопасности рекомендуется выбирать размер и равным или большим бит, размер равным или большим соответственно, а параметр большим или равным 8[11]:
;
;
Уровень безопасности относительно других схем цифровой подписи
Ниже представлена таблица соответствия уровня безопасности ESIGN уровням безопасности RSA и ECDSA при различных размерах параметра в битах. Можно заметить, что при одинаковым размерах RSA и ESIGN сравнимы по уровню безопасности.[12]
Схема ESIGN позволяет быстро генерировать подпись. Так как вычислительно сложные операции, такие как возведение в степень и нахождение обратного элемента , не зависят от подписываемого сообщения , их можно осуществить заранее и сохранить полученные значения в памяти. Таким образом, чтобы подписать сообщение, достаточно выполнить оставшиеся операции сложения, умножения и деления, доля которых в вычислительной сложности алгоритма создания подписи мала. В случае, когда , а битовая длина равна , скорость генерации подписи в больше, чем для RSA при соответствующих параметрах. Что же касается проверки подписи, то её скорость сравнима со скоростью проверки подписи в алгоритме RSA, открытая экспонента которого мала.[13][9]
С помощью ESIGN можно реализовать протоколы идентификации с нулевым разглашением, которые позволяют субъекту (англ.Prover — доказывающий) доказать субъекту (англ.Verifier — проверяющий) факт наличия информации, сохранив её в тайне от . Протоколы идентификации на основе ESIGN не уступают протоколу Фейга — Фиата — Шамира в своей эффективности. Мы рассмотрим два таких протокола: трёхраундовый и двухраундовый.[14]
выбирает случайным образом число и отправляет доказывающему.
выбирает случайным образом число , вычисляет , генерирует подпись для и отправляет проверяющему.
проверяет выполнение равенства и достоверность подписи для сообщения .
В приведенных протоколах секретной информацией являются ключи , знание которых и доказывает субъект . Если результаты всех проверок на завершающих этапах оказываются успешными, то считается, что действительно обладает секретом.
Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
Atsushi Fujioka, Tatsuaki Okamoto, Shoji Miyaguchi.ESIGN: An Efficient Digital Signature Implementation for Smart Cards // Advances in Cryptology — EUROCRYPT ’91 : материалы конф. / Advances in Cryptology - EUROCRYPT '91, Брайтон, Великобритания, 8-11 апреля 1991. — Springer Berlin Heidelberg, 1991. — С. 446—457. — ISBN 978-3-540-54620-7. (недоступная ссылка)