Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[92]

и 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 поз и-цию. Новый крайний левый бит является функцией всех остальных битов регистра . На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина п о-лучаемой последовательности до начала ее повторения .

± ± ± t

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

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

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


Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register, или LFSR) (см. 14th). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи Из-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию. Криптографы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случа й-ны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии.

Выходной бит

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

На 13-й показан 4-битовый LFSR с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния :

1 1 1 1

10 1 0 1 1 0 1

0 1 1 0

0 1 0 0 0 0 1 0

10 0 0 1 1 0 0

1 1 1 0

-►

Выходной бит

Рис. 16-3. 4-битовый LFSR.

Выходной последовательностью будет строка младших значащих битов : 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0. . . .

n-битовый LFSR может находиться в одном из 2 n-1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n-1 битов. (Число внутренних состояний и период равны 2 n-1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно .) Только при определенных отводных последовательностях LFSR циклически пройдет через все 2 n-1 внутренних состояний, такие


LFSR являются LFSR с максимальным периодом. Получившийся результат называется М-последовательностью.

Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной п о-следовательности и константы 1, должен быть примитивным по модулю 2. Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x2" +1, но не является делителем xd+1 для всех d, являющихся делителями 2n-1 (см. раздел 11.3). Соответствующую математическую теорию можно найти в [643, 1649, 1648].

В общем случае не существует простого способа генерировать примитивные многочлены данной степени по модулю 2. Проще всего выбирать многочлен случайным образом и проверять, не является ли он примитивным . Это нелегко - и чем-то похоже на проверку, не является ли простым случайно выбранное число - но многие м а-тематические пакеты программ умеют решать такую задачу. Ряд методов приведен в [970, 971].

Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2, приведены в 14-й [1583, 643, 1649, 1648, 1272, 691]. Например, запись (32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2:

x32 + x7 +x5 + x3 + x2 + x + 1

Это можно легко обобщить для LFSR с максимальным периодом. Первым числом является длина LFSR. Последнее число всегда равно 0, и его можно опустить . Все числа, за исключением 0, задают отводную последов а-тельность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.

Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и пе р-вого битов (см. 12th), получающийся LFSR будет иметь максимальную длину, циклически проходя до повтор е-ния через 232-1 значений.

Код для этого LFSR на языке C выглядит следующим образом:

int LFSR ( ) {

static unsigned long ShiftRegister = 1; /* Все, кроме 0. */

ShiftRegister = ((((ShiftRegister >> 31) A(ShiftRegister >> 6) A(ShiftRegister >> 4) A(ShiftRegister >> 2) A(ShiftRegister >> 1) AShiftRegister)) & 0x00000001) <<31)

(ShiftRegister >> 1) ; return ShiftRegister & 0x00000001;

Если сдвиговый регистр длиннее компьютерного слова, код усложняется, но не намного .

Выходной бит

Рис. 16-4. 32-битовый LFSR с максимальной длиной. Табл. 16-2.

Некоторые примитивные многочлены по модулю 2

(1, 0) (2, 1, 0) (3, 1, 0) (4, 1, 0)

(5, 2, 0)

(6, 1, 0) (7, 1, 0)

(7, 3, 0) (8, 4, 3, 2, 0) (9, 4, 0)

(10, 3, 0) (11, 2, 0) (12, 6, 4, 1, 0) (13, 4, 3, 1, 0)

(14, 5, 3, 1, 0) (15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0) (17, 5, 0) (17, 6, 0) (18, 7, 0)

(18, 5, 2, 1, 0) (19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0) (22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203]