Патенты. ESICN запатентован в Соединенных Штатах [1208], Канаде, Англии, Франции, Германии и Италии

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

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

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

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

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

Алгоритм Yagisawa объединяет возведение в степень то&р с арифметикой то&рЛ [1623], он был взломан в [256]. Другой алгоритм с открытым ключом, Tsujii-Kurosawa-Itoh-Fujioka-Matsumoto [1548], также оказался небезопасным [948]. Небезопасной [717] была и третья система, Luccio-Mazzone [993]. Схема подписи на базе birational перестановок [1425] была взломана на следующий день после ее представления [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. Дискретный логарифм: Если р - простое число, a g и М - целые, найти х, для которого выполняется g^x=M{moup).

3. Разложение на множители: Если N - произведение двух простых чисел, то лиьо

(a) разложить N на множители,

(b) для заданных целых чисел Ми С найти d, для которого М* = С (mod N),

(c) для заданных целых чисел е и С найти М, для которого Af = С (mod N),

(d) для заданного целого числа х определить, существует ли целое число у, для которого х = у² (mod N).

Согласно Диффи [492, 494], проблема дискретных логарифмов была предложена Дж. Гиллом (J. Gill), про­блема разложения на множители - Кнутом, а проблема рюкзака - самим Диффи.

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

1. Все операции, на которые сейчас опирается криптография с открытыми ключами - умножение, возведение в степень и разложение на множители - представляют собой фундаментальные арифметические явления. Веками они были предметом интенсивного математического изучения, и рост внимания к ним, вызванный применением в криптосистемах с открытыми ключами, увеличил, а не уменьшил наше доверие.

2. Наша возможность выполнять большие арифметические вычисления растет равномерно и сейчас позволяет нам реал и-зовывать системы с числами такого размера, чтобы эти системы были чувствительны только к действительно радикальным прорывам в разложении на множители, дискретных логарифмах или извлечении корней.

Как мы уже видели, не все алгоритмы с открытыми ключами, основанные на этих проблемах, безопасны. Сила любого алгоритма с открытым ключом зависит не только от вычислительной сложности проблемы, леж а-щей в основе алгоритма. Трудная проблема необязательно реализуется в сильном алгоритме. Ади Шамир объ­ясняет это тремя причинами [1415]:

1. Теория сложности обычно связана с отдельными частными случаями проблемы. Криптоаналитик же часто получает большой набор статистически связанных проблем - различные шифротексты, заши ф-рованные одним и тем же ключом.

2. Вычислительная сложность проблемы обычно измеряется для худшего или среднего случаев. Чтобы быть эффективной в качестве способа шифрования, проблема должна быть трудной для решения по ч-ти во всех случаях.

3. Произвольную сложную проблему необязательно можно преобразовать в криптосистему, к тому же проблема должна позволить встроить в нее лазейку, знание которой и только оно делает возможным простое решение проблемы.