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

Взломали криптосистему, основанную на проблеме рюкзака, не миллион машин, а пара криптографов. Сна­чала был раскрыт единственный бит открытого текста [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]. Более того, учитывая легкость с которой пали все остальные варианты, д о-верять устоявшим пока вариантом, по видимому, неосторожно.