ESIGN

В протоколе участвуют два субъекта: субъект ${\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

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