(286, 69, 0) (286, 73, 0)

(294, 61, 0)

(322, 67, 0) (333, 2, 0) (350, 53, 0) (366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0) (462, 73, 0)

(521, 32, 0) (521, 48, 0) (521, 158, 0)

(521, 168, 0) (607, 105, 0) (607, 147, 0)

(607, 273, 0)

(1279, 216, 0) (1279, 418, 0) (2281, 715, 0)

(2281, 915, 0) (2281, 1029, 0) (3217, 67, 0) (3217, 576, 0) (4423, 271, 0)

(9689, 84, 0)

Обратите внимание, что у всех элементов таблицы нечетное число коэффициентов . Я привел такую длинную таблицу, так как LFSR часто используются для криптографии с потоковыми шифрами, и я хотел, чтобы разные люди могли подобрать различные примитивные многочлены. Если p(x) примитивен, то примитивен и xn/;(1/x), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена .

Например, если (a, b, 0) примитивен, то примитивен и (a, a - b, 0). Если примитивен (a, b, c, d, 0), то примитивен и (a, a - d, a - c, a - b, 0). Математически:

если примитивен xa + xb + 1, то примитивен и xa + xa - b + 1

если примитивен x + x + x + x + 1, то примитивен и x + x + x + x + 1

Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита тужно выполнять XOR только двух битов сдвигового регистра. Действительно, все многочлены обратной связи, приведенные в 14-й, являются разреженными, то есть, у них немного коэффициентов. Разреженность всегда представляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма . Для криптографических алгоритмов гораздо лучше использовать плотные примитивные многочлены, те, у которых много коэффицие н-тов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие LFSR.

Генерировать плотные примитивные многочлены по модулю 2 нелегко . В общем случае для генерации примитивных многочленов степени k нужно знать разложение на множители числа 2 k-1. Примитивные многочлены можно найти в следующих трех хороших работах: [652, 1285, 1287].

Сами по себе LFSR являются хорошими генераторами псевдослучайных последовательностей, но они обл а-дают некоторыми нежелательными неслучайными свойствами . Последовательные биты линейны, что делает их бесполезными для шифрования. Для LFSR длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey [1082,1083]: см. раздел 16.3.

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

Программная реализация LFSR

Программные реализации LFSR медленны и быстрее работают, если они написаны на ассемблере, а не на C. Одним из решений является использование параллельно 16 LFSR (или 32, в зависимости от длины слова вашего компьютера). В этой схеме используется массив слов, размер которого равен длине LFSR, а каждый бит слова массива относится к своему LFSR. При условии, что используются одинаковые многочлены обратной связи , это может дать заметный выигрыш производительности . Вообще, лучшим способом обновлять сдвиговые регистры является умножение текущего состояния на подходящие двоичные матрицы [901].

Схему обратной связи LFSRможно модифицировать. Получающийся генератор не будет криптографически более надежным, но он все еще будет обладать максимальным периодом, и его легче реализовать программно [1272]. Вместо использования для генерации нового крайнего левого бита битов отводной последовательности выполняется XOR каждого бита отводной последовательности с выходом генератора и замена его результатом этого действия, затем результат генератора становится новым крайним левым битом (см. 11th). Иногда эту модификацию называют конфигурацией Галуа. На языке C это выглядит следующим образом:

#define mask 0x80000057

static unsigned long ShiftRegister=1; void seed LFSR (unsigned long seed)

if (seed == 0) /* во избежание беды */

seed = 1 ; ShiftRegister = seed;

int modified LFSR (void)

if (ShiftRegister & 0x00000001) {

ShiftRegister = (ShiftRegister л mask >> 1) 0x8000000 ; return 1; } else {

ShiftRegister >>= 1;

return 0;

Выходной бит

Рис. 16-5. LFSR Галуа.

Выигрыш состоит в том, что все XOR можно сделать за одну операцию. Эта схема также может быт распараллелена, а полиномы различных обратных связей могут быть различны . Такая конфигурация Галуа может дать выигрыш и при аппаратной реализации, особенно в виде СБИС . Вообще, при использовании аппаратуры, которая хорошо выполняет сдвиги применяйте конфигурацию Фиббоначи, если есть возможность использовать параллелизм, применяйте конфигурацию Галуа.

16.3 Проектирование и анализ потоковых шифров

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

Проблема LFSR состоит в том, что их программная реализация очень неэффективна . Вам приходится избегать разреженных многочленов обратной связи - они облегчают корреляционные вскрытия [1051, 1090, 350] - а плотные многочлены обратной связи неэффективны . Выход любого потокового шифра является побитовым, для шифрования того, что можно выполнить за одну итерацию DES, необходимо выполнить 64 итерации потоков ого алгоритма. Действительно, программная реализация простого алгоритма LFSR, подобного описываемому ниже сжимающему генератору, не быстрее, чем DES.

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

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

Линейная сложность

Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используемым для анализа генераторов на базе LFSR, является линейная сложность (linear complexity), или линейный интервал. Она определяется как длина n самого короткого LFSR, который может имитировать выход генератора. Любая последовательность, генерированная конечным автоматом над конечным полем, имеет конечную линейную сложность [1006]. Линейная сложность важна, потому что с помощью простого алгоритма, называ е-мого алгоритмом Berlekamp-Massey, можно определить этот LFSR, проверив только 2 n битов потока ключей [1005]. Воссоздавая нужный LFSR, вы взламываете потоковый шифр.

Эта идея можно расширить с полей на кольца [1298] и на случаи, когда выходная последовательность рассматривается как числа в поле нечетной характеристики [842]. Дальнейшее расширение приводит к вводу понятия профиля линейной сложности, который определяет линейную сложность последовательности по мере ее удлинения [1357, 1168, 411, 1582]. Другой алгоритм вычисления линейной сложности прост только в очень сп е-