Практические реализации

Для последовательности из шести элементов нетрудно решить задачу рюкзака, даже если последовательность не является сверхвозрастающей. Реальные рюкзаки должны содержать не менее 250 элементов. Длина каждого члена сверхвозрастающей последовательности должна быть где-то между 200 и 400 битами, а длина модуля должна быть от 100 до 200 битов. Для получения этих значений практические реализации используют генераторы случайной последовательности.

Вскрывать подобные рюкзаки при помощи грубой силы бесполезно. Если компьютер может проверять миллион вариантов в секунду, проверка всех возможных вариантов рюкзака потребует свыше 10⁴⁶ лет. Даже миллион машин, работающих параллельно, не успеет решить эту задачу до превращения солнца в сверхновую звезду.

Безопасность метода рюкзака

Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов. Сначала был раскрыт единственный бит открытого текста [725]. Затем Шамир показал, что в определенных обстоятельствах рюкзак может быть взломан [1415, 1416]. Были и другие достижения - [1428, 38, 754, 516, 488] - но никто не мог взломать систему Мартина-Хеллмана в общем случае. Наконец Шамир и Циппел (Zippel) [1418, 1419, 1421] обнаружили слабые места в преобразовании, что позволило им восстановить сверхвозрастающую последовательность рюкзака по нормальной. Точные доказательства выходят за рамки этой книги, но их хороший обзор можно найти в [1233, 1244]. На конференции, где докладывались эти результаты, вскрытие было продемонстрировано по стадиям на компьютере Apple II [492, 494].

Варианты рюкзака

После вскрытия оригинальной схемы Меркла-Хеллмана было предложено множество других систем на принципе рюкзака: несколько последовательных рюкзаков, рюкзаки Грэм-Шамира (Graham-Shamir), и другие. Все они были проанализированы и взломаны, как правило, с использованием одних и тех же криптографических методов, и их обломки были сметены со скоростного шоссе криптографии [260, 253, 269, 921, 15, 919, 920, 922, 366, 254, 263, 255]. Хороший обзор этих систем и их криптоанализ можно найти в [267, 479, 257, 268].

Были предложены и другие алгоритмы, использующие похожие идеи, но все они тоже были взломаны. Криптосистема Lu-Lee [990, 13] была взломана в [20, 614, 873], ее модификация [507] также оказалась небезопасной [1620]. Вскрытия криптосистемы Goodman-McAuley приведены в [646, 647, 267, 268]. Криптосистема Pieprzyk [1246] была взломана аналогичным образом. Криптосистема Niemi [1169], основанная на модульных рюкзаках, взломана в [345, 788]. Новый, многостадийный рюкзак [747] пока еще не был взломан, но я не оптимистичен. Другим вариантом является [294].

Хотя вариант алгоритма рюкзака в настоящее время безопасен - алгоритм рюкзака Char-Rivest [356], несмотря на "специализированное вскрытие" [743] - количество необходимых вычислений делает его намного менее полезным, чем другие рассмотренные здесь алгоритмы. Вариант, названный Powerline System (система электропитания) небезопасен [958]. Более того, учитывая легкость с которой пали все остальные варианты, доверять устоявшим пока вариантом, по видимому, неосторожно.

Патенты

Оригинальный алгоритм Меркла-Хеллмана запатентован в Соединенных Штатах [720] и в остальном мире (см. Табл. 19-1). Public Key Partners (PKP) получила лицензию на патент вместе с другими патентами криптографии с открытыми ключами (см. раздел 25.5). Время действия патента США истечет 19 августа 1997 года.

Табл. 19-1.
Иностранные патенты на алгоритм рюкзака Меркла-Хеллмана

RSA

Вскоре после алгоритма рюкзака Меркла появился первый полноценный алгоритм с открытым ключом, который можно использовать для шифрования и цифровых подписей: RSA [1328, 1329]. Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. (Мартин Гарднер (Martin Gardner) опубликовал раннее описание алгоритма в своей колонке "Математические игры" в Scientific American[599].) Он также является самым популярным. Названный в честь трех изобретателей - Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Эдлмана (Leonard Adleman) - этот алгоритм многие годы противостоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму.

Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100 - 200 разрядов или даже больше) простых чисел. Предполагается, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел.

Для генерации двух ключей используются два больших случайных простых числа, pи q. Для максимальной безопасности выбирайте pи q равной длины. Рассчитывается произведение:

n= p q

Затем случайным образом выбирается ключ шифрования e, такой что eи (p-1)(q-1) являются взаимно простыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифрирования d, такого что

ed = 1 (mod (p-1)(q-1))

Другими словами

d= e^-1mod ((p-1)(q-1))

Заметим, что dи nтакже взаимно простые числа. Числа e и n - это открытый ключ, а число d- закрытый. Два простых числа pи q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты.

Для шифрования сообщения m оно сначала разбивается на цифровые блоки, меньшие n(для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть, если pи q - 100-разрядные простые числа, то nбудет содержать около 200 разрядов, и каждый блок сообщения m_i должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение c будет состоять из блоков c_i той же самой длины. Формула шифрования выглядит так

c_i = m_i^e mod n

Для расшифровки сообщения возьмите каждый зашифрованный блок c_i и вычислите

m_i = c_i^d mod n

Так как

c_i^d = (m_i^e)^d = m_i^ed = m_i^{k(p-1)(q-1)+1} = m_im_i^k(p-1)(q-1) = m_i*1 = m_i; все (mod n)

формула восстанавливает сообщение. Это сведено в Табл. 19-2.

Табл. 19-2.
Шифрование RSA

Открытый ключ:

n произведение двух простых чисел pи q (pи q должны храниться в секрете)

e число, взаимно простое с (p-1)(q-1)

Закрытый ключ:

de^-1mod ((p-1)(q-1))

Шифрование:

c = m^e mod n

Дешифрирование:

m = c^d mod n

Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью e, возможен любой выбор. Я уберегу вас от теории чисел, доказывающей, почему этот алгоритм работает. В большинстве книг по криптографии этот вопрос подробно рассмотрен.

Короткий пример возможно поможет пояснить работу алгоритма. Если p= 47 и q= 71, то

n= pq= 3337

Ключ eне должен иметь общих множителей

(p-1)(q-1)= 46*70 =3220

Выберем (случайно) e равным 79. В этом случае d= 79^-1 mod 3220 = 1019

При вычислении этого числа использован расширенный алгоритм Эвклида (см. раздел 11.3). Опубликуем e и n, сохранив в секрете d. Отбросим p и q.Для шифрования сообщения

m = 6882326879666683

сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков m_i:

m_l = 688

m₂= 232

m₃ = 687

m₄= 966

m₅ = 668

m₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = c_l

Выполняя те же операции для последующих блоков, создает шифротекст сообщения:

c = 1570 2756 2091 2276 2423 158

Для дешифрирование нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019:

1570¹⁰¹⁹ mod 3337 = 688 = m_l

Аналогично восстанавливается оставшаяся часть сообщения.