(4) sk= OT+ rx mod q rs=gOTyr mod p

(5) OTk= s+ rx mod q rOT=gsyr mod p

(6) OTk= r+sx mod q rOT=grys mod p

Это шесть различных схем цифровых подписей. Добавление минуса увеличивает их количество до 24. При использовании всех возможных значения a, b и c число схем доходит 120.

EIGamal [518, 519] и DSA [1154] по существу основаны на уравнении (4). Другие схемы - на уравнении (2) [24, 1629]. Schnorr [1396, 1397], как и другая схема [1183], тесно связан с уравнением (5). А уравнение (1) можно изменить так, чтобы получить схему, предложенную в [1630]. Оставшиеся уравнения - новые.

Далее. Любую из этих схем можно сделать более DSA-подобной, определив r как

r = (gk mod p) mod q

Используйте то же уравнение подписи и сделайте уравнением проверки

u1 = a-1 b mod q

u2 = a-1 c mod q

v = ((gu1 *7u2) mod,p) mod q

(r mod q)a = gbyc mod p

Существуют и две другие возможности подобных преобразований [740, 741]. Такие операции можно проделать с каждой из 120 схем, доведя общее число схем цифровой подписи, использующих дискретные логарифмы,

до 480.

Но и это еще не все. Дополнительные обобщения и изменения приводят более, чем к 13000 вариантам (не все из них достаточно эффективны) [740, 741].

Одной из приятных сторон использования RSA для цифровой подписи является свойство, называемое восстановлением сообщения. Когда вы проверяете подпись RSA, вы вычисляете от. Затем вычисленное от сравнивается с сообщением и проверяется, правильна ли подпись сообщения . В предыдущих схемах восстановить от при вычислении подписи невозможно, вам потребуется вероятное от, которое и используется в уравнении проверки. Но, оказывается, можно построить вариант с восстановлением сообщения для всех вышеприведенных схем. Для подписи сначала вычислим

r = OTgk mod p

и заменим от единицей в уравнении подписи. Затем можно восстановит уравнение проверки так, чтобы от могло быть вычислено непосредственно. То же самое можно предпринять для DSA-подобных схем:

r = (OTgk mod p) mod q

Безопасность всех вариантов одинакова, поэтому имеет смысл выбирать схему по сложности вычисления . Большинство схем замедляет необходимость вычислять обратные значения . Как оказывается, одна из этих схем позволяет вычислять и уравнение подписи, и уравнение проверки без использования обратных значений, при этом еще и восстанавливая сообщение. Она называется схемой p-NEW [1184].

r = OTg-k mod p

s = k - rx mod q

от восстанавливается (и проверяется подпись) с помощью вычисления

от = gsyrr mod p

В ряде вариантов одновременно подписывается по два-три блока сообщения [740], другие варианты можно использовать для слепых подписей [741].

Это значительная область для изучения. Все различные схемы цифровой подписи с использованием ди с-кретных логарифмов были объединены логическим каркасом. Лично я считаю, что это окончательно положит конец спорам между Schnorr [1398] и DSA [897]: DSA не является ни производной Schnorr, равно как и EIGa-mal. Все три алгоритма являются частными случаями описанной общей схемы, и эта общая схема незапатент о-вана.

20.5 ONG-SCHNORR-SHAMIR

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

h = -k-2 mod n = -(k-1)2 mod n

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

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

51 = 1/2 (M/r +r) mod n

52 = 1/2 (M/r -r) mod n

Пара чисел S1 и S2 йредставляет собой подпись. Проверяя подпись, убеждаются, что S12 + h*S22= M (mod n)

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

20.6 ESIGN

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

n = p2*q

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

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

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

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

(H(m) - *k mod n)/pq

s = * + ((w/kxk-1 mod p) pq

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

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

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

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

" = xk mod n

v = l/(kxk-1) mod p

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

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

(H(m) - ")/pq

s = * + ((wv mod p) pq

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

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

Когда этот алгоритм был впервые предложен, k было выбрано равным 2 [1215]. Такая схема быстро была взломана Эрни Брикеллом (Ernie Brickell) и Джоном ДеЛаурентисом [261], которые распространили свое вскрытие и на случай k = 3. Модифицированная версия этого алгоритма [1203] была взломана Шамиром [1204]. Вариант, предложенный в [1204], был взломан в [1553]. ESIGN - это сегодняшняя реинкарнация алгоритмов из этого семейства. Попытка вскрыть ESIGN [963] оказалась безрезультатной.

В настоящее время авторы рекомендуют использовать следующие значения k: 8, 16, 32, 64, 128, 256, 512 и 1024. Они также рекомендуют, чтобы p и q были не меньше 192 битов каждое, образуя n не менее, чем 576 битов в длину. (Я думаю, что n должно быть еще в два раза больше.) Авторы считают, что с такими значениями параметров, безопасность ESIGN равна безопасности RSA или Rabin. И выполненный ими анализ показывает, что скорость ESIGN намного выше, чем у RSA, EIGamal и DSA [582].

Патенты

ESICN запатентован в Соединенных Штатах [1208], Канаде, Англии, Франции, Германии и Италии. Любой, кто хочет получить лицензию на алгоритм, должен обратиться в Отдел интеллектуальной собственности NTT (Intellectual Property Department, NTT, 1-6Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan).

20.7 Клеточные автоматы

Совершенно новая идея, изученная Папуа Гуамом ( Papua Guam) [665], состоит в использовании в криптосистемах с открытыми ключами клеточных автоматов. Эта система все еще слишком нова и не прошла через тщательное изучение, но предварительное исследование показало, что у нее может быть такое же криптографически слабое место, как и у других систем [562]. Тем не менее, это многообещающая область исследований. Свойством клеточных автоматов является то, что даже если они инвертируемы, невозможно вычислить предка прои з-вольного состояния, инвертировав правило нахождения потомка . Это выглядит очень похоже на однонаправленную хэш-функцию с лазейкой.

20.8 Другие алгоритмы с открытым ключом

За эти годы было предложено и вскрыто множество других алгоритмов с открытыми ключами. Алгоритм Matsumoto-lmai [1021] б1л вскрыт в [450]. Алгоритм Cade был впервые предложен в 1985 году, взломан в 1986 [774], и затем доработан в том же году [286]. Помимо этих вскрытий, существуют общие вскрытия, раскладывающие многочлены над конечными полями [605]. К любому алгоритму, безопасность которого определяется композицией многочленов над конечными полями, нужно относиться со скептицизмом, если не с откровенным подозрением.

Алгоритм Yagisawa объединяет возведение в степень mod p с арифметикой mod p-1 [1623], он был взломан в [256]. Другой алгоритм с открытым ключом, Tsujii-Kurosawa-Itoh-Fujioka-Matsumoto [1548], также оказался небезопасным [948]. Небезопасной [717] была и третья система, Luccio-Mazzone [993]. Схема подписи на базе birational перестановок [1425] б1ла взломана на следующий день после ее представления [381]. Несколько схем подписей предложил Тацуаки Окамото ( Tatsuaki Okamoto): было доказано, что одна из них так же безопасна, как проблема дискретного логарифма, а другая - как проблема дискретного логарифма и проблема разложения на множители [1206]. Аналогичные схемы представлены в [709].

Густавус Симмонс (Gustavus Simmons) предложил использовать в качестве основы алгоритмов с открытыми ключами J-алгебру [1455, 145]. От этой идеи пришлось отказаться после изобретения эффективных методов разложения многочленов на множители [951]. Также были изучены и специальные полугруппы многочленов [1619, 962], но и это ничего не дало. Харальд Нидеррейтер (Harald Niederreiter) предложил алгоритм с открытым ключом на базе последовательностей сдвиговых регистров [1166]. Другой алгоритм использовал слова Линдона (Lyndon) [1476], а третий - prepositional исчисление [817]. Безопасность одного из недавних алгоритмов с открытыми ключами основывалась на проблеме matrix cover [82]. Тацуаки Окамото и Казуо Ота (Kazuo Ohta) провели сравнение ряда схем цифровой подписи в [1212].

Перспективы создания радикально новых и различных алгоритмов с открытыми ключами неясны . В 1988 году Уитфилд Диффи отметил, что большинство алгоритмов с открытыми ключами основаны на одной из трех трудных проблем [492, 494]:

1. Рюкзак: Дано множество уникальных чисел, найти подмножество, сумма которого равна N.

2. Дискретный логарифм: Еслиp - простое число, а g и M - целые, найти x, для которого выполняется gx=M (mod ,p).