Русская Википедия:ESIGN

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

ESIGN (Шаблон:Lang-en — эффективная цифровая подпись) — схема цифровой подписи с открытым ключом, основанная на проблеме факторизации чисел. Отличительной чертой данной схемы является возможность быстрой генерации подписи.Шаблон:Sfn

История

Цифровая подпись была разработана в японской компании NTT в 1985 году.Шаблон:Sfn Схема оказалась эффективна в плане скорости генерации цифровой подписи. Однако первые версии были взломаны Эрни Брикеллом (Шаблон:Lang-en) и Джоном ДеЛаурентисом (Шаблон:Lang-en), после чего рекомендованные параметры алгоритма были модифицированы.Шаблон:Sfn Последующие попытки взлома оказались безуспешными. Авторы уверяют, что сложность взлома последней версии ESIGN сравнима со сложностью задачи факторизации числа <math>n</math> вида <math>p^2q</math>, где <math>p</math> и <math>q</math> — простые числа.Шаблон:Sfn

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

Введение

В протоколе участвуют два субъекта: субъект <math>A</math>, цель которого — доказать то, что является автором сообщения <math>m</math>, и субъект <math>B</math>, целью которого является проверка авторства. В ESIGN для осуществления поставленных целей <math>A</math> и <math>B</math> должны совершить следующие действияШаблон:Sfn.

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

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

Ключи ESIGN генерируются следующим образомШаблон:Sfn.

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

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

Чтобы подписать сообщение <math>m</math>, где <math>m</math> — двоичное число произвольной длины, предпринимаются следующие шагиШаблон:Sfn.

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

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

Чтобы проверить, что подпись <math>s</math> действительно подписывает сообщение <math>m</math>, предпринимаются следующие шагиШаблон:Sfn.

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

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

В изначально предложенном варианте ESIGN параметр <math>k</math> был равен двум.Шаблон:Sfn Однако после успешной атаки Эрни Брикелла и Джона ДеЛаурентиса, которая распространялась также на вариант схемы с <math>k = 3</math>, авторы изменили требование к этому параметру на существующее <math>k \geqslant 4</math>.Шаблон:Sfn

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

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

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

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

Если выбранная хеш-функция криптографически стойкая, то атака с использованием коллизий займет <math>2^{(\log_2{n})/3}</math> операций вычисления хеш-функции, атака с использованием второго прообраза — <math>2^{{(\log_2{n})/6}}</math> операций, что считается неосуществимым, при больших <math>n</math>.Шаблон:SfnШаблон:Sfn

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

Атака на открытый ключ <math>(n,k)</math> заключается в попытке получить на его основе закрытый ключ <math>(p,q)</math>. Сделать это можно, решив уравнение <math>n = p^2q</math>, то есть факторизовав число <math>n</math>. Можно заметить, что в RSA число <math>n</math> генерируется похожим образом, там <math>n = pq</math>, но на сегодняшний день вопрос о том, в каком из случаев факторизация становится проще или сложнее, остается открытым, так как эффективных алгоритмов факторизации до сих пор нет. На данный момент самым быстрым способом факторизовать число <math>n</math>, что для ESIGN, что для RSA, является метод решета числового поля, который делает это со скоростью, зависящей от битовой длины <math>n</math>. Однако, при большой битовой длине числа <math>n</math> задача факторизации становится невыполнимой.Шаблон:SfnШаблон:Sfn

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

Помимо уже введенных ограничений в описании ESIGN, для большей безопасности рекомендуется выбирать размер <math>p</math> и <math>q</math> равным или большим <math>320</math> бит, размер <math>n</math> равным или большим <math>960</math> соответственно, а параметр <math>k</math> большим или равным 8Шаблон:Sfn:

• <math>\log_2{p} \geqslant 320</math>;
• <math>k \geqslant 8 </math>;

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

Ниже представлена таблица соответствия уровня безопасности ESIGN уровням безопасности RSA и ECDSA при различных размерах параметра <math>n</math> в битах. Можно заметить, что при одинаковым размерах <math>n</math> RSA и ESIGN сравнимы по уровню безопасности.Шаблон:Sfn

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

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

Схема ESIGN позволяет быстро генерировать подпись. Так как вычислительно сложные операции, такие как возведение в степень <math>(x^k \bmod n)</math> и нахождение обратного элемента <math>(k*x^{k-1})^{-1}</math>, не зависят от подписываемого сообщения <math>m</math>, их можно осуществить заранее и сохранить полученные значения в памяти. Таким образом, чтобы подписать сообщение, достаточно выполнить оставшиеся операции сложения, умножения и деления, доля которых в вычислительной сложности алгоритма создания подписи мала. В случае, когда <math>k = 4</math>, а битовая длина <math>n</math> равна <math>768</math>, скорость генерации подписи в <math>10\div100</math> больше, чем для RSA при соответствующих параметрах. Что же касается проверки подписи, то её скорость сравнима со скоростью проверки подписи в алгоритме RSA, открытая экспонента которого мала.Шаблон:SfnШаблон:Sfn

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

С помощью ESIGN можно реализовать протоколы идентификации с нулевым разглашением, которые позволяют субъекту <math>P</math> (Шаблон:Lang-en — доказывающий) доказать субъекту <math>V</math> (Шаблон:Lang-en — проверяющий) факт наличия информации, сохранив её в тайне от <math>V</math>. Протоколы идентификации на основе ESIGN не уступают протоколу Фейга — Фиата — Шамира в своей эффективности. Мы рассмотрим два таких протокола: трёхраундовый и двухраундовый.Шаблон:Sfn

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

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

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

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

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

Литература

• Книга:Шнайер Б.: Прикладная криптография
• Шаблон:Книга
• Шаблон:СтатьяШаблон:Недоступная ссылка
• Шаблон:Статья