О потоковых шифрах на базе РгСсЛОС

Основной подход при проектировании генератора потока ключей на базе РгСсЛОС прост. Сначала берется один или несколько РгСсЛОС, обычно с различными длинами и различными многочленами обратной связи. (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет максимальная длина.) Ключ является начальным состоянием регистров РгСсЛОС. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры РгСсЛОС (это иногда называют тактированием (clocking)). Бит выхода представляет собой функцию, желательно нелинейную, некоторых битов регистров РгСсЛОС. Эта функция называется комбинирующей функцией, а генератор в целом — комбинационным генератором. (Если бит выхода является функцией единственного РгСсЛОС, то генератор называется фильтрующим генератором.) Большая часть теории подобного рода устройств разработана Селмером (Selmer) и Нилом Цирлером (Neal Zierler). Можно ввести ряд усложнений. В некоторых генераторах для различных РгСсЛОС используется различная тактовая частота, иногда частота одного генератора зависит от выхода другого. Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управлением тактовой частотой (clock-controlled generators). Управление тактовой частотой может быть с прямой связью, когда выход одного РгСсЛОС управляет тактовой частотой другого РгСсЛОС, или с обратной связью, когда выход одного РгСсЛОС управляет его собственной тактовой частотой. Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией, многие из них безопасны до сих пор.

Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Блетчли Парк (Bletchly Park), сказал, что «криптография — это смесь математики и путаницы, и без путаницы математика может быть использована против вас». Он имел в виду, что в потоковых шифрах для обеспечения максимальной длины и других свойств необходимы определенные математические структуры, такие как РгСсЛОС, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести некоторый сложный нелинейный беспорядок. Этот совет справедлив и для блочных алгоритмов.

Большинство реальных потоковых шифров основаны на РгСсЛОС. Даже в первые дни электроники построить их было несложно. Сдвиговый регистр не представляет собой ничего большего, чем массив битов, а последовательность обратной связи — набор вентилей XOR. Даже при использовании СБИС потоковый шифр на базе РгСсЛОС обеспечивает немалую безопасность с помощью нескольких логических вентилей. Проблема РгСсЛОС состоит в том, что их программная реализация очень неэффективна. Вам приходится избегать разреженных многочленов обратной связи — они облегчают корреляционные вскрытия — а плотные многочлены обратной связи неэффективны.

Эта отрасль криптографии быстро развивается и находится под зорким государственным контролем со стороны NSA. Большинство разработок засекречены — множество используемых сегодня военных систем шифрования основаны на РгСсЛОС. Действительно, у большинства компьютеров Cray (Cray 1, Cray X-MP, Cray Y-MP) есть весьма любопытная инструкция, обычно называемая как «счетчик совокупности» (population count). Она подсчитывает количество единиц в регистре и может быть использована как для эффективного вычисления расстояния Хэмминга между двумя двоичными словами и для реализации векторизированной версии РгСсЛОС. Эта инструкция считается канонической инструкцией NSA, обязательно фигурирующей почти во всех контрактах, касающихся компьютеров.

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