WikiSort.ru - Не сортированное

Введение

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