Ong-schnorr-shamir

Эта схема подписи использует многочлены по модулю п [1219, 1220]. Выбирается большое целое число (знать разложение п на множители не обязательно). Затем выбирается случайное число к, взаимно простое с и, и вычисляется h, равное

h = -к'² mod n = -(k^Af mod n

Открытым ключом служат h и и; а закрытым - к.

Чтобы подписать сообщение М, сначала генерируется случайное число г, взаимно простое с п. Затем вычис­ляется:

S_x = 1/2 (Mir +r) mod n

S₂ = 1/2 (M/r -r) mod n

Пара чисел & и S₂ представляет собой подпись. Проверяя подпись, убеждаются, что

SS + h*S2²=M (mod п)

Описанный здесь вариант схемы основан на квадратичных многочленах. При его опубликовании в [1217] за успешный криптоанализ было предложено вознаграждение в $100. Небезопасность схемы была доказана [1255, 18], но это не остановило ее авторов. Они предложили модификацию алгоритма, основанную на кубических многочленах, также оказавшуюся небезопасной [1255]. Авторы предложили версию на базе многочленов чет­вертой степени, но была взломана и она [524, 1255]. Вариант, решающий эти проблемы, описан в [1134].

ESIGN

ESICN -это схема цифровой подписи, разработанная NTT Japan [1205, 583]. Утверждалось, что она не менее безопасна, чем RSA или DSA, и намного быстрее при тех же размерах ключа и подписи. Закрытым ключом служит пара больших простых чисел ряд. Открытым ключом является п, для которого

п = p²*q

Я- это хэш-функция, применяемая к сообщению т, причем значение Щт) находится в пределах от 0 до й-1. Используется также параметр безопасности к, который будет вкратце рассмотрен.

(1) Алиса выбирает случайное число х, меньшее pq.

(2) Алиса вычисляет:

w, наименьшее целое, которое больше или равно

(Щт) -х^к mod n)lpq

s = x + ((wlkx^k-¹ mod p) pq

(3) Алиса посылает s Бобу.

(4) Для проверки подписи Боб вычисляет s mod п. Кроме этого, он вычисляет а, наименьшее целое, которое больше или равно удвоенному числу битов п, деленному на 3. Если Щт) меньше или равна / mod n, и ес­ли / mod n меньше Щт)+2^а, то подпись считается правильной.

Выполнив ряд предварительных вычислений, этот алгоритм можно ускорить. Эти вычисления могут быть выполнены в произвольный момент времени и никак не связаны с подписываемым сообщением. Выбрав х, Алиса может разбить этап (2) на два подэтапа. Сначала.

(2а) Алиса вычисляет:

u = x^k mod n

v-l/ikx^mod p

(2b) Алиса вычисляет:

w= наименьшее целое, которое больше или равно

(Щт) - u)lpq

s = x + ((wv mod p) pq

Для обычно используемых размеров чисел предварительные вычисления ускоряют процесс подписи на п о-рядок. Почти вся трудная работа выполняется именно на стадии предварительных вычислений. Обсуждение действий модульной арифметики, выполняемых при ускорении ESIGN, можно найти в [1625, 1624]. Этот алго-

ритм можно расширить для работы с эллиптическими кривыми [1206].