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 и М - целые, найти х, для которого выполняется gx=M{moup).
3. Разложение на множители: Если N - произведение двух простых чисел, то лиьо
(a) разложить N на множители,
(b) для заданных целых чисел Ми С найти d, для которого М* = С (mod N),
(c) для заданных целых чисел е и С найти М, для которого Af = С (mod N),
(d) для заданного целого числа х определить, существует ли целое число у, для которого х = у2 (mod N).
Согласно Диффи [492, 494], проблема дискретных логарифмов была предложена Дж. Гиллом (J. Gill), проблема разложения на множители - Кнутом, а проблема рюкзака - самим Диффи.
Эта узость математических основ криптографии с открытыми ключами немного беспокоит . Прорыв в решении либо проблемы дискретных логарифмов, либо проблемы разложения на множители сделает небезопасными целые классы алгоритмов с открытыми ключами. Диффи показал [492, 494], что подобный риск смягчается двумя факторами:
1. Все операции, на которые сейчас опирается криптография с открытыми ключами - умножение, возведение в степень и разложение на множители - представляют собой фундаментальные арифметические явления . Веками они были предметом интенсивного математического изучения, и рост внимания к ним, вызванный применением в криптосистемах с открытыми ключами, увеличил, а не уменьшил наше доверие.
2. Наша возможность выполнять большие арифметические вычисления растет равномерно и сейчас позволяет нам реал и-зовывать системы с числами такого размера, чтобы эти системы были чувствительны только к действительно радикальным прорывам в разложении на множители, дискретных логарифмах или извлечении корней .
Как мы уже видели, не все алгоритмы с открытыми ключами, основанные на этих проблемах, безопасны . Сила любого алгоритма с открытым ключом зависит не только от вычислительной сложности проблемы, леж а-щей в основе алгоритма. Трудная проблема необязательно реализуется в сильном алгоритме . Ади Шамир объясняет это тремя причинами [1415]:
1. Теория сложности обычно связана с отдельными частными случаями проблемы. Криптоаналитик же часто получает большой набор статистически связанных проблем - различные шифротексты, заши ф-рованные одним и тем же ключом.
2. Вычислительная сложность проблемы обычно измеряется для худшего или среднего случаев . Чтобы быть эффективной в качестве способа шифрования, проблема должна быть трудной для решения по ч-ти во всех случаях.
3. Произвольную сложную проблему необязательно можно преобразовать в криптосистему, к тому же проблема должна позволить встроить в нее лазейку, знание которой и только оно делает возможным простое решение проблемы.