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

За эти годы было предложено и вскрыто множество других алгоритмов с открытыми ключами. Алгоритм Matsumoto-lmai [1021] был вскрыт в [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] была взломана на следующий день после ее представления [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, для которого выполняется g^xºM (mod p).

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

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

(b) для заданных целых чисел Mи C найти d, для которого M^dº C(mod N),

(c) для заданных целых чисел eи C найти M, для которого M^eº C(mod N),

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

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

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

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

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

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

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

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

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