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

С помощью 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}$ действительно обладает секретом.