ESIGN

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

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

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

• Предварительно, ${\displaystyle A}$ генерирует ключи: открытый, известный всем, и закрытый, известный только субъекту ${\displaystyle A}$.
• Субъект ${\displaystyle A}$ генерирует цифровую подпись ${\displaystyle s}$ для сообщения ${\displaystyle m}$ на основе закрытого ключа.
• ${\displaystyle A}$ отправляет сообщение ${\displaystyle m}$ вместе с подписью ${\displaystyle s}$ субъекту ${\displaystyle b}$.
• Субъект ${\displaystyle B}$ проверяет достоверность подписи на основе открытого ключа.

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

1. Случайным образом выбираются два простых числа ${\displaystyle p}$ и ${\displaystyle q}$ одинаковой битовой длины.
2. Вычисляется число ${\displaystyle n=p^{2}q}$.
3. Выбирается целое положительное число ${\displaystyle k\geqslant 4}$.
4. Пара чисел ${\displaystyle (n,k)}$ является открытым ключом.
5. Пара чисел ${\displaystyle (p,q)}$ — закрытый ключ.

Чтобы подписать сообщение ${\displaystyle m}$, где ${\displaystyle m}$ — двоичное число произвольной длины, предпринимаются следующие шаги^[6].

1. Вычисляется ${\displaystyle \mu =h(m)}$, где ${\displaystyle h}$ — заранее выбранная хеш-функция, принимающая значения от ${\displaystyle 0}$ до ${\displaystyle n-1}$.
2. Выбирается случайное число ${\displaystyle x}$ из интервала ${\displaystyle [0,pq)}$.
3. Вычисляется ${\displaystyle \chi =\left\lceil {\frac {\mu -(x^{k}{\bmod {n}})}{pq}}\right\rceil }$ и ${\displaystyle \varkappa =\left({\frac {\chi }{k*x^{k-1}}}\right){\bmod {p}}}$, где ${\displaystyle \lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z} }$ — функция округления до наименьшего целого, большего аргумента.
4. Вычисляется подпись ${\displaystyle s=x+\varkappa pq}$.

Чтобы проверить, что подпись ${\displaystyle s}$ действительно подписывает сообщение ${\displaystyle m}$, предпринимаются следующие шаги^[6].

1. Вычисляется ${\displaystyle \mu =h(m)}$, где ${\displaystyle h}$ — та же самая хеш-функция, которая использовалась для генерации подписи.
2. Вычисляется ${\displaystyle \xi =\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil }$.
3. Выполняется проверка неравенства ${\displaystyle \mu \leqslant s^{k}{\bmod {n}}\leqslant \mu +2^{\xi }}$.
4. Подпись считается достоверной, если неравенство выполнено.

В изначально предложенном варианте ESIGN параметр ${\displaystyle k}$ был равен двум.^[5] Однако после успешной атаки Эрни Брикелла и Джона ДеЛаурентиса, которая распространялась также на вариант схемы с ${\displaystyle k=3}$, авторы изменили требование к этому параметру на существующее ${\displaystyle k\geqslant 4}$.^[7]

Атаки на хеш-функцию ${\displaystyle h}$ с целью подделки подписи основаны на ее несовершенности, то есть на несоответствии хеш-функции одному или нескольким критериям криптографической стойкости c той оговоркой, что в случае ESIGN равенства в критериях стоит понимать с точностью до ${\displaystyle (\log _{2}{n})/3}$ старших бит. Это послабление связано с условием проверки подписи, которое выполняется не только для исходного значения хеш-функции, но и для прочих, совпадающих в первых ${\displaystyle (\log _{2}{n})/3}$ старших битах.

Допустим, что функция ${\displaystyle h}$ неустойчива к поиску коллизий, то есть можно найти такие различные ${\displaystyle m}$ и ${\displaystyle m'}$, что ${\displaystyle h(m)}$ и ${\displaystyle h(m')}$ совпадают в первых ${\displaystyle (\log _{2}{n})/3}$ старших битах. Тогда, подписывая сообщение ${\displaystyle m}$, автор ${\displaystyle A}$, ничего не подозревая, автоматически подписывает сообщение ${\displaystyle m'}$, так как выполняется неравенство ${\displaystyle h(m')\leqslant s^{k}{\bmod {n}}\leqslant h(m')+2^{\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil }}$

Если выбранная хеш-функция криптографически стойкая, то атака с использованием коллизий займет ${\displaystyle 2^{(\log _{2}{n})/3}}$ операций вычисления хеш-функции, атака с использованием второго прообраза — ${\displaystyle 2^{(\log _{2}{n})/6}}$ операций, что считается неосуществимым, при больших ${\displaystyle n}$.^[8][9]

Атака на открытый ключ ${\displaystyle (n,k)}$ заключается в попытке получить на его основе закрытый ключ ${\displaystyle (p,q)}$. Сделать это можно, решив уравнение ${\displaystyle n=p^{2}q}$, то есть факторизовав число ${\displaystyle n}$. Можно заметить, что в RSA число ${\displaystyle n}$ генерируется похожим образом, там ${\displaystyle n=pq}$, но на сегодняшний день вопрос о том, в каком из случаев факторизация становится проще или сложнее, остается открытым, так как эффективных алгоритмов факторизации до сих пор нет. На данный момент самым быстрым способом факторизовать число ${\displaystyle n}$, что для ESIGN, что для RSA, является метод решета числового поля, который делает это со скоростью, зависящей от битовой длины ${\displaystyle n}$. Однако, при большой битовой длине числа ${\displaystyle n}$ задача факторизации становится невыполнимой.^[10][9]

Помимо уже введенных ограничений в описании ESIGN, для большей безопасности рекомендуется выбирать размер ${\displaystyle p}$ и ${\displaystyle q}$ равным или большим ${\displaystyle 320}$ бит, размер ${\displaystyle n}$ равным или большим ${\displaystyle 960}$ соответственно, а параметр ${\displaystyle k}$ большим или равным 8^[11]:

• ${\displaystyle \log _{2}{p}\geqslant 320}$;
• ${\displaystyle k\geqslant 8}$;

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

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

Схема ESIGN позволяет быстро генерировать подпись. Так как вычислительно сложные операции, такие как возведение в степень ${\displaystyle (x^{k}{\bmod {n}})}$ и нахождение обратного элемента ${\displaystyle (k*x^{k-1})^{-1}}$, не зависят от подписываемого сообщения ${\displaystyle m}$, их можно осуществить заранее и сохранить полученные значения в памяти. Таким образом, чтобы подписать сообщение, достаточно выполнить оставшиеся операции сложения, умножения и деления, доля которых в вычислительной сложности алгоритма создания подписи мала. В случае, когда ${\displaystyle k=4}$, а битовая длина ${\displaystyle n}$ равна ${\displaystyle 768}$, скорость генерации подписи в ${\displaystyle 10\div 100}$ больше, чем для RSA при соответствующих параметрах. Что же касается проверки подписи, то её скорость сравнима со скоростью проверки подписи в алгоритме RSA, открытая экспонента которого мала.^[13][9]

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

1. ${\displaystyle P}$ генерирует открытые ${\displaystyle (n,k)}$ и секретные ${\displaystyle (p,q)}$ ESIGN ключи.
2. ${\displaystyle P}$ выбирает случайным образом числа ${\displaystyle r}$ и ${\displaystyle u}$, вычисляет ${\displaystyle x=f(r\|u)}$, где ${\displaystyle f}$ — односторонняя функция, ${\displaystyle \|}$ — операция конкатенации, и отправляет ${\displaystyle x}$ проверяющему ${\displaystyle V}$.
3. ${\displaystyle V}$ выбирает случайным образом число ${\displaystyle y}$ и отправляет доказывающему.
4. ${\displaystyle P}$ вычисляет ${\displaystyle m=r\oplus y}$, генерирует подпись ${\displaystyle s}$ для ${\displaystyle m}$ и отправляет тройку ${\displaystyle (s,r,u)}$ проверяющему.
5. ${\displaystyle V}$ проверяет выполнение равенства ${\displaystyle x=f(r\|u)}$ и достоверность подписи ${\displaystyle s}$ для сообщения ${\displaystyle m}$.

1. ${\displaystyle P}$ генерирует открытые ${\displaystyle (n,k)}$ и секретные ${\displaystyle (p,q)}$ ESIGN ключи.
2. ${\displaystyle V}$ выбирает случайным образом число ${\displaystyle r}$ и отправляет доказывающему.
3. ${\displaystyle P}$ выбирает случайным образом число ${\displaystyle u}$, вычисляет ${\displaystyle m=f(r\|u)}$, генерирует подпись ${\displaystyle s}$ для ${\displaystyle m}$ и отправляет ${\displaystyle (s,u)}$ проверяющему.
4. ${\displaystyle V}$ проверяет выполнение равенства ${\displaystyle m=f(r\|u)}$ и достоверность подписи ${\displaystyle s}$ для сообщения ${\displaystyle m}$.

В приведенных протоколах секретной информацией являются ключи ${\displaystyle (p,q)}$, знание которых и доказывает субъект ${\displaystyle P}$. Если результаты всех проверок на завершающих этапах оказываются успешными, то считается, что ${\displaystyle P}$ действительно обладает секретом.

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = 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 года.