Глава 16

Генераторы псевдослучайных последовательностей шифры

и потоковые

16.1 Линейные конгруэнтные генераторы

Линейными конгруэнтными генераторами являются генераторы следующей формы Xn = (aXn-1 + b) mod m

в которых Xn - это n-ый член последовательности, а Xn-1 - предыдущий член последовательности. Переменные a, b и m - постоянные: a - множитель, b - инкремент, и m - модуль. Ключом, или затравкой, служит значение X0.

Период такого генератора не больше, чем m. Если a, b и m выбраны правильно, то генератор будет генератором с максимальным периодом (иногда называемым максимальной длиной), и его период будет равен m. (Например, b должно быть взаимно простым с m.) Подробное описание выбора констант для получения макс и-мального периода можно найти в [863, 942]. Еще одной хорошей статьей по линейным конгруэнтным генераторам и их теории является [1446].

В 15-й, взятой из [1272,], перечисляются хорошие константы линейных конгруэнтных генераторов . Все они обеспечивают генераторы с максимальным периодом и, что даже более важно, удовлетворяют спектральному тесту на случайность для размерностей 2, 3, 4, 5 и 6 [385, 863]. Таблица организована по максимальному произведению, которое не вызывает переполнения в слове указанной длины .

Преимуществом линейных конгруэнтных генераторов является их быстрота за счет малого количества оп е-раций на бит.

К несчастью линейные конгруэнтные генераторы нельзя использовать в криптографии, так как они предск а-зуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом (Jim Reeds) [1294, 1295, 1296], а затем Джоан Бояр (Joan Boyar) [1251]. Ей удалось также вскрыть квадратичные генераторы :

Xn = (aXn-12 + bXn-1 + c) mod m

и кубические генераторы:

Xn = (aXn-13 + bXn-12 + c Xn-1+ d) mod m

Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального ген е-ратора [923, 899, 900]. Б1ли взломаны и усеченные линейные конгруэнтные генераторы [581, 705, 580], и усеченные линейные конгруэнтные генераторы с неизвестными параметрами [1500, 212]. Таким образом была доказана бесполезность конгруэнтных генераторов для криптографии.

Табл. 16-1.

Константы для линейных конгруэнтных генераторов

Переполняется при

a b m

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

Объединение линейных конгруэнтных генераторов

Был предпринят ряд попыток объединения линейных конгруэнтных генераторов [1595, 941]. Криптографическая безопасность полученных результатов не повышается, но они обладают более длинными периодами и лучшими характеристиками в некоторых статистических тестах . Для з2-битовых компьютеров можно использовать следующий генератор [941]:

static long sl = 1 ; /* "long" должно быть 32-битов1м цел1м. */ static long s2 = 1 ; #define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ;

/* MODMIJLT(a,b,c,nl,s) рассчитывает s*b mod m при условии, что m=a*b+c и 0 <= c < m. */

/* combinedLCG возвращает действительное псевдослучайное значение в диапазоне

* (0,1). Она объединяет линейные конгруэнтные генераторы с периодами

* 231-85 и 231-249, и ее период равен произведению этих двух простых чисел. */

double combinedLCG ( void ) {

long q ; long z ;

MODMULT ( 53668, 40014, 12211, 2147483563L, s1 ) MODMULT ( 52774, 40692, 3791, 2147483399L, s2 ) z = s1 - s2 ;

if ( z < 1 )

z += 2147483562 ; return z * 4.656613e-10 ;

/* В общем случае перед использованием combinedLCG вызывается initLCG. */ void initLCG( long InitS1, long InitS2 )

sl = InitS1;

s2 = InitS2;

Этот генератор работает при условии, что компьютер может представить все целые числа между -231+85 и 231-249. Переменные s1 и s2 глобальны и содержат текущее состояние генератора. Перед первым вызовом их необходимо проинициализировать. Для переменной s1 начальное значение должно лежать в диапазоне между 1

и 2147483562, для переменной s2 - между 1 и 2147483398. Период генератора близок к 1018. На 16-битовом компьютере используйте другой генератор :

static int sl = 1 ; /* "int" должно быть 16-битовым целхм. */ static int s2 = 1 ; static int s3 = 1 ;

#define MODMULT(a,b,c,m,s) q = s/a; s = b*(s-a*q) - c*q; if (s<0) s+=m ;

/* combinedLCG возвращает действительное псевдослучайное значение в диапазоне

* (0,1). Она объединяет линейные конгруэнтные генераторы с периодами 215-405,

* 215-1041 и 215-1111, и ее период равен произведению этих трех простых чисел. */

double combinedLCG ( void ) {

long q ; long z ;

MODMULT ( 206, 157, 21, 32363, sl ) MODMULT ( 217, 146, 45, 31727, s2 )

MODMULT ( 222, 142, 133, 31657, s3 )

z = s1 - s2 ;

if ( z < 1 )

z -= 32362 ;

z += s3 ;

if ( z < 1 )

z += 32362 ; return z * 3.0899e-5 ;

/* В общем случае перед использованием combinedLCG вызывается initLCG. */ void initLCG( long InitS1, long InitS2, long InitS3)

sl = InitS1;

s2 = InitS2; s3 = InitS3;

Этот генератор работает при условии, что компьютер может представить все целые числа между -32363 и 32363. Переменные s1, s2 и s3 глобальны и содержат текущее состояние генератора. Перед первым вызовом их необходимо проинициализировать. Для переменной s1 начальное значение должно лежать в диапазоне между 1 и 32362, для переменной s2 - между 1 и 31726, для переменной s3 - между 1 и 31656. Период генератора равен 1.6*1013. Для обоих генераторов константа b равна 0.

16.2 Сдвиговые регистры с линейной обратной связью

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

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи (см. 15th). Сдвиговый регистр представляет собой последовательность битов . (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 поз и-цию. Новый крайний левый бит является функцией всех остальных битов регистра . На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина п о-лучаемой последовательности до начала ее повторения .

функция обратной связи

Рис. 16-1. Сдвиговый регистр с обратной связью

Криптографам нравились потоковые шифры на базе сдвиговых регистров : они легко реализовывались с помощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров [1411]. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие ене-которые свои резальтаты и результаты Селмера [643]. См. также [970, 971, 1647].