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

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

static long si = 1 ; /* "long" должно быть 32-битовым целым. */ 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 <= с < m. */

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

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

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

double combinedLCG ( void ) {

long q ;

long z ;

MODMULT ( 53668, 40014, 12211, 2147483563L, si )

MODMULT ( 52774, 40692, 3791, 2147483399L, s2 )

z = si - s2 ;

if ( z < 1 )

z += 2147483562 ;

return z * 4.656613e-10 ; }

/* В общем случае перед использованием combinedLCG вызывается initLCG. */

void initLCG( long InitSl, long InitS2 )

{

si = InitSl;

s2 = InitS2;

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


и 2147483562, для переменной ,2 - между 1 и 2147483398. Период генератора близок к 1018.

На 16-битовом компьютере используйте другой генератор :

static int si = 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, si ) MODMULT ( 217, 146, 45, 31727, s2 ) MODMULT ( 222, 142, 133, 31657, s3 ) z = si - s2 ; if ( z < 1 )

z -= 32362 ; z += s3 ; if ( z < 1 )

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

}

/* В общем случае перед использованием combinedLCG вызывается initLCG. */

void initLCG( long InitSl, long InitS2, long InitS3)

{

si = InitSl;

s2 = InitS2;

s3 = InitS3; }

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

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

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