ESIGN

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

ESIGN (англ. Efficient digital SIGNature — эффективная цифровая подпись) — схема цифровой подписи с открытым ключом, основанная на проблеме факторизации чисел. Отличительной чертой данной схемы является возможность быстрой генерации подписи.[1]

Цифровая подпись была разработана в японской компании NTT в 1985 году.[2] Схема оказалась эффективна в плане скорости генерации цифровой подписи. Однако первые версии были взломаны Эрни Брикеллом (англ. Ernie Btickel) и Джоном ДеЛаурентисом (англ. John DeLaurentis), после чего рекомендованные параметры алгоритма были модифицированы.[3] Последующие попытки взлома оказались безуспешными. Авторы уверяют, что сложность взлома последней версии ESIGN сравнима со сложностью задачи факторизации числа вида , где и простые числа.[4]

Описание протокола

[править | править код]

В протоколе участвуют два субъекта: субъект , цель которого — доказать то, что является автором сообщения , и субъект , целью которого является проверка авторства. В ESIGN для осуществления поставленных целей и должны совершить следующие действия[5].

  • Предварительно, генерирует ключи: открытый, известный всем, и закрытый, известный только субъекту .
  • Субъект генерирует цифровую подпись для сообщения на основе закрытого ключа.
  • отправляет сообщение вместе с подписью субъекту .
  • Субъект проверяет достоверность подписи на основе открытого ключа.

Генерация открытого и закрытого ключей

[править | править код]

Ключи ESIGN генерируются следующим образом[6].

  1. Случайным образом выбираются два простых числа и одинаковой битовой длины.
  2. Вычисляется число .
  3. Выбирается целое положительное число .
  4. Пара чисел является открытым ключом.
  5. Пара чисел — закрытый ключ.

Генерация подписи

[править | править код]

Чтобы подписать сообщение , где двоичное число произвольной длины, предпринимаются следующие шаги[6].

  1. Вычисляется , где — заранее выбранная хеш-функция, принимающая значения от до .
  2. Выбирается случайное число из интервала .
  3. Вычисляется и , где — функция округления до наименьшего целого, большего аргумента.
  4. Вычисляется подпись .

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

[править | править код]

Чтобы проверить, что подпись действительно подписывает сообщение , предпринимаются следующие шаги[6].

  1. Вычисляется , где — та же самая хеш-функция, которая использовалась для генерации подписи.
  2. Вычисляется .
  3. Выполняется проверка неравенства .
  4. Подпись считается достоверной, если неравенство выполнено.

Предыдущие версии

[править | править код]

В изначально предложенном варианте ESIGN параметр был равен двум.[5] Однако после успешной атаки Эрни Брикелла и Джона ДеЛаурентиса, которая распространялась также на вариант схемы с , авторы изменили требование к этому параметру на существующее .[7]

Криптоанализ

[править | править код]

Атака на хеш-функцию

[править | править код]

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

Допустим, что функция неустойчива к поиску коллизий, то есть можно найти такие различные и , что и совпадают в первых старших битах. Тогда, подписывая сообщение , автор , ничего не подозревая, автоматически подписывает сообщение , так как выполняется неравенство

Если выбранная хеш-функция криптографически стойкая, то атака с использованием коллизий займет операций вычисления хеш-функции, атака с использованием второго прообраза операций, что считается неосуществимым, при больших .[8][9]

Атака на открытый ключ

[править | править код]

Атака на открытый ключ заключается в попытке получить на его основе закрытый ключ . Сделать это можно, решив уравнение , то есть факторизовав число . Можно заметить, что в RSA число генерируется похожим образом, там , но на сегодняшний день вопрос о том, в каком из случаев факторизация становится проще или сложнее, остается открытым, так как эффективных алгоритмов факторизации до сих пор нет. На данный момент самым быстрым способом факторизовать число , что для ESIGN, что для RSA, является метод решета числового поля, который делает это со скоростью, зависящей от битовой длины . Однако, при большой битовой длине числа задача факторизации становится невыполнимой.[10][9]

Рекомендуемые параметры

[править | править код]

Помимо уже введенных ограничений в описании ESIGN, для большей безопасности рекомендуется выбирать размер и равным или большим бит, размер равным или большим соответственно, а параметр большим или равным 8[11]:

  • ;
  • ;

Уровень безопасности относительно других схем цифровой подписи

[править | править код]

Ниже представлена таблица соответствия уровня безопасности ESIGN уровням безопасности RSA и ECDSA при различных размерах параметра в битах. Можно заметить, что при одинаковым размерах RSA и ESIGN сравнимы по уровню безопасности.[12]

Размер в ESIGN, биты Размер в RSA, биты Размер в ECDSA, биты
960 960 152
1024 1024 160
2048 2048 224
3072 3072 256
7680 7680 384

Преимущества

[править | править код]

Схема ESIGN позволяет быстро генерировать подпись. Так как вычислительно сложные операции, такие как возведение в степень и нахождение обратного элемента , не зависят от подписываемого сообщения , их можно осуществить заранее и сохранить полученные значения в памяти. Таким образом, чтобы подписать сообщение, достаточно выполнить оставшиеся операции сложения, умножения и деления, доля которых в вычислительной сложности алгоритма создания подписи мала. В случае, когда , а битовая длина равна , скорость генерации подписи в больше, чем для RSA при соответствующих параметрах. Что же касается проверки подписи, то её скорость сравнима со скоростью проверки подписи в алгоритме RSA, открытая экспонента которого мала.[13][9]

Протоколы идентификации на основе ESIGN

[править | править код]

С помощью ESIGN можно реализовать протоколы идентификации с нулевым разглашением, которые позволяют субъекту (англ. Prover — доказывающий) доказать субъекту (англ. Verifier — проверяющий) факт наличия информации, сохранив её в тайне от . Протоколы идентификации на основе ESIGN не уступают протоколу Фейга — Фиата — Шамира в своей эффективности. Мы рассмотрим два таких протокола: трёхраундовый и двухраундовый.[14]

Трёхраундовая схема идентификации

[править | править код]
  1. генерирует открытые и секретные ESIGN ключи.
  2. выбирает случайным образом числа и , вычисляет , где односторонняя функция, — операция конкатенации, и отправляет проверяющему .
  3. выбирает случайным образом число и отправляет доказывающему.
  4. вычисляет , генерирует подпись для и отправляет тройку проверяющему.
  5. проверяет выполнение равенства и достоверность подписи для сообщения .

Двухраундовая схема идентификации

[править | править код]
  1. генерирует открытые и секретные ESIGN ключи.
  2. выбирает случайным образом число и отправляет доказывающему.
  3. выбирает случайным образом число , вычисляет , генерирует подпись для и отправляет проверяющему.
  4. проверяет выполнение равенства и достоверность подписи для сообщения .

В приведенных протоколах секретной информацией являются ключи , знание которых и доказывает субъект . Если результаты всех проверок на завершающих этапах оказываются успешными, то считается, что действительно обладает секретом.

Примечания

[править | править код]
  1. Menezes, Oorschot, Vanstone, 1996, §11.7 п.2, pp. 473—474.
  2. Minghua, 2001, p. 1.
  3. Шнайер, 2002, глава 20, п.6.
  4. Atsushi, 1991, глава 2, п.3: «We conjective that to break our higher degree version (ESIGN) is as hard as facctoring N».
  5. 1 2 Шнайер, 2002, глава 2, п.6.
  6. 1 2 3 Menezes, Oorschot, Vanstone, 1996, §11.7 п.2, p. 473.
  7. Menezes, Oorschot, Vanstone, 1996, §11.9, pp. 486—487.
  8. Minghua, 2001, p. 3.
  9. 1 2 3 Menezes, Oorschot, Vanstone, 1996, §11.7 п.2, p. 474.
  10. Minghua, 2001, p. 4.
  11. Minghua, 2001, p. 6.
  12. Minghua, 2001, p. 7.
  13. Atsushi, 1991, глава 3.
  14. Atsushi, 1991, глава 4.

Литература

[править | править код]
  • Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
  • Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Глава 11. Digital Signatures // Handbook of Applied Cryptography. — 5-e изд. — CRC Press, 1996. — С. 473—474. — 816 с. — ISBN 0-8493-8523-7.
  • 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. (недоступная ссылка)
  • Alfred Menezes , Minghua Qu , Doug Stinson , Yongge Wang. Evaluation of security level of cryptography: ESIGN signature scheme : материалы проекта / CRYPREC Project, Япония. — 2001. — Январь. Архивировано 9 августа 2017 года.