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].