4 Метод статистичних випробувань Метод статистичних випробувань

Скачати 2.04 Mb.

Назва	4 Метод статистичних випробувань Метод статистичних випробувань
Сторінка	14/31
Дата	08.04.2013
Розмір	2.04 Mb.
Тип	Лекция

bibl.com.ua > Інформатика > Лекция

1 ... 10 11 12 13 14 15 16 17 ... 31

Практические приложения

Генераторы случайных и псевдослучайных чисел являются связующим звеном в обеспечении информационной безопасности. В некотором смысле это жизненно важные строительные блоки криптографических алгоритмов и протоколов. Поскольку такие генераторы применяются во многих криптографических задачах, например формирование случайных параметров и ключей систем шифрования, то требования, предъявляемые к ним, оказываются достаточно высокими. В частности, одним из критериев абсолютно произвольной двоичной последовательности, получаемой на выходе генератора, является невозможность её предсказания в отсутствие какой-либо информации о данных, подаваемых на вход генератора. Поэтому на практике статистические тесты проводят для проверки случайного характера бинарной последовательности, формируемой генератором случайных или псевдослучайных чисел. Что в свою очередь позволяет выявить генераторы, заранее удовлетворяющие требованиям конкретной криптографической задачи.

Конкурс AES

Основная статья: AES (конкурс)

С целью утверждения нового стандарта шифрования Advanced Encryption Standard Национальный институт стандартов и технологий при поддержке правительства США провёл конкурс, в ходе которого были протестированы 15 претендовавших алгоритмов. Один из критериев, используемых при оценке алгоритмов, заключался в их пригодности в качестве генераторов случайных чисел. Проверка таких генераторов на предмет формирования случайных двоичных последовательностей с хорошими статистическими свойствами осуществлялась с помощью набора статистических тестов NIST.

В течение первого раунда AES тестирование проводилось с 128-битными ключами. Лишь 9 алгоритмов из 15 алгоритмов смогли пройти статистические тесты.^[10]

По результатам первого раунда 5 алгоритмов шифрования были выбраны в качестве финалистов AES: MARS, RC6, Rijndael, Serpent и Twofish. Во втором раунде конкурса AES оценка пригодности этих 5 алгоритмов в качестве генераторов случайных чисел проводилось на основе 192-битных и 256-битных ключей. Продолжительность статистических тестов NIST составило несколько месяцев, причем вычисления производились на многочисленных рабочих станциях Sun Ultra. Все данные формировались и обрабатывались в режиме онлайн. В результате второго раунда было показано, что каждый из пяти финалистов формирует случайную бинарную последовательность с хорошими статистическими свойствами, и поэтому может быть использован в качестве генератора псевдослучайных чисел, причем имеется возможность использования ключей размерами: 128, 192 и 256 бит.^[11]

Генератор Макларена-Марсальи (MacLaren-Marsaglia) - генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был предложен в 1965 году.

Данный генератор псевдослучайных чисел оперирует с тремя объектами: двумя конгруэнтными генераторами, которые порождают последовательности $<x_{n}>$ , $<y_{n}>$ , и матрицей

, состоящей из

элементов, обычно

. На выходе последовательность $<z_{n}>$ .

Генератор состоит из четырёх основных стадий:

Инициализация и с помощью заполнения первыми элементами последовательности $<x_{n}>$ - выполняется один раз;
Выборка из $<x_{n}>, <Y_{n}>$ , то есть очередные члены последовательностей $<x_{n}>$ , $<y_{n}>$ ;
Вычисление $\lfloor k * y/m \rfloor$ , где - модуль, использующийся в $<y_{n}>$ . Поэтому $j \in [0,k)$ - случайное число, определяемое ;
Присвоение $z_{i} = v_{j}$ и замена $v_{j} = x$ ;

Последние три стадии могут повторяться необходимое число раз.

Данный метод генерации позволяет получать большие периоды, если последовательности $<x_{n}>$ и $<y_{n}>$ имеют взаимно простые периоды. И даже если длина периода несущественна, соседние элементы последовательности почти не коррелируют друг с другом.

В данном исходном коде на языке программирования Паскаль реализованы основные части генератора Макларена-Марсальи.

Const

k = 128; {размер матрицы V}

N = 100; {размер выходной последовательности}

Var

i: word;

V: array[1..k] of extended; {вспомогательная матрица}

Z: array[1..N] of extended; {выходная последовательность}

out: extended;

Function GMM: extended;

Var

Result, x, y: extended;

j: word;

Begin

x := Random; {случайное число первой последовательности}

y := Random; {случайное число второй последовательности}

j := Trunc( y * k );

If j < 1 then

j := 1;

Result := V[j];

V[j] := x; {случайное заполнение новым числом}

GMM := Result;

End;

Begin

Randomize;

For i:=1 to k do

V[i] := Random; {Инициализация матрицы V}

For i:=1 to N do

Z[i] := GMM;

End.

В данном исходном коде учтён второй дефект генератора, поэтому

превышает число элементов выходной последовательности.

Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.

Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

$x_{k+1} = (a x_k + c)~~\bmod~~m,$

где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа $x_{0}$ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа.

Последовательность чисел, порождаемая линейным конгруэнтным методом, периодична с периодом, не превышающим m. При этом длина периода в точности равна m тогда и только тогда, когда:

НОД(c,m) = 1 (то есть, c и m взаимно просты);
a-1 кратно p для всех простых делителей p числа m;
a-1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c. Для этих констант выписаны условия, гарантирующие удовлетворительное качество получаемых случайных чисел.

При реализации выгодно выбирать

, где e — число битов в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на $m^{1/d}$ гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.

В таблице ниже приведены наиболее часто используемые параметры линейных конгруэнтных генераторов, в частности, в стандартных библиотеках различных компиляторов (функция rand()).

Source	m	a	c	выдаваемые биты результата в rand() / Random(L)
Numerical Recipes	2³²	1664525	1013904223
MMIX by Donald Knuth	2⁶⁴	6364136223846793005	1442695040888963407
Borland C/C++	2³²	22695477	1	биты 30..16 в rand(), 30..0 в lrand()
GNU Compiler Collection	2³²	69069	5	биты 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++	2³²	1103515245	12345	биты 30..16
Borland Delphi, Virtual Pascal	2³²	134775813	1	биты 63..32 числа (seed * L)
Microsoft Visual/Quick C/C++	2³²	214013	2531011	биты 30..16
Apple CarbonLib	2³¹ - 1	16807	0

Особенностью линейного конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X₀, a, c, m.

Регистр сдвига с линейной обратной связью (РСЛОС, Linear feedback shift register, LFSR) — регистр сдвига битовых слов, у которого входной (вдвигаемый) бит является линейной функцией состояния остальных битов регистра до сдвига. Может быть организован как программными, так и аппаратными средствами и применяется для генерации псевдослучайных последовательностей битов, что находит применение, в частности, в криптографии.

В регистре сдвига с линейной обратной связью выделяют две части (модуля): собственно регистра сдвига и схемы (или подпрограммы) вычисляющих значение вдвигаемого бита. Регистр состоит из функциональных ячеек (или битов машинного слова или нескольких слов), в каждой из которой хранится текущее состояние одного бита. Количество ячеек

, называют длиной регистра. Биты (ячейки) обычно нумеруются числами $~0, 1, 2, \dots, l-1$ , каждая из которых способна хранить

бит, причём в ячейку

происходит вдвижение вычисленного бита, а из ячейки

извлекается выдвигаемый очередной сгенерированный бит. Вычисление вдвигаемого бита обычно производится до сдвига регистра, и только после сдвига значение вычисленного бита помещается в ячейку

.

Периодом регистра сдвига называют минимальную длину получаемой последовательности до начала её повторения. Так как регистр из

битовых ячеек имеет только $2^{l}-1$ разных ненулевых состояний, то, принципиально, период регистра не может превышать это число. Если период регистра равен этому числу, то такой регистр называют регистром максимального периода.

Для РСЛОС функция обратной связи является линейной булевой функцией от состояний всех или некоторых битов регистра. Например, сумма по модулю два или её логическая инверсия является линейной булевой функцией (операция XOR, в формулах обозначают как $\oplus$ ) и наиболее часто применяется в таких регистрах.

При этом те биты, которые являются переменными функции обратной связи, принято называть отводами.

Управление регистром в аппаратных реализациях производится подачей сдвигающего импульса (иначе называемого тактовогоили синхроимпульса) на все ячейки, в программных — выполнением программного цикла, включающего вычисление функции обратной связи и сдвига битов в слове.

В течение каждого такта времени выполняются следующие операции:

содержимое ячейки формирует очередной бит выходной последовательности битов;
новое содержимое ячейки определяется битом обратной связи, являющегося значением функции обратной связи (обычно сложение по модулю ) с определёнными коэффициентами (принимающими значение 0 и 1) битов ячеек $~0, 1, 2, \dots, l-1$ ;
содержимое -й ячейки перемещается в ячейку для любого ;
содержимое -й ячейки принимает значение вычисленного бита.

http://upload.wikimedia.org/wikipedia/commons/thumb/c/c7/register12.png/600px-register12.png

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

Таким образом, в качестве функции обратной связи берётся логическая операция XOR (исключающее ИЛИ), то есть:

на первом шаге: $s_l = (c_1*s_{l-1}) \oplus (c_2*s_{l-2}) \oplus \dots \oplus (c_l*s_{0})$
на втором шаге: $s_{l+1} = (c_1*s_{l}) \oplus (c_2*s_{l-1}) \oplus \dots \oplus (c_l*s_{1})$
…
на -м шаге: $s_{j} = (c_1*s_{j-1}) \oplus (c_2*s_{j-2}) \oplus \dots \oplus (c_l*s_{j-l})$ , причём некоторые коэффициенты (но не все, иначе вырожденный случай) равны 0.

Свойства примитивных многочленов

если примитивный многочлен степени , то примитивен и ;
если примитивен многочлен , то примитивен и $x^a + x^{a-b} + 1$ ;
если примитивен многочлен , то примитивен и $x^a + x^{a-d} + x^{a-c} + x^{a-b} + 1$ .

1 ... 10 11 12 13 14 15 16 17 ... 31

Схожі:

Тема: Предмет, структура, завдання й методи досліджень в юридичній психології Юридична психологія, метод спостереження (інтроспекція), метод бесіди, метод експерименту (законодавчий, природний, лабораторний,...	Урок розвитку мовлення в 11 класі Підготовка до написання твору роздуму... Методи: метод випереджального навчання, метод наукового дослідження, метод дискусії, активний метод навчання — робота в малих групах,...
Список абітурієнтів, які подали ОРИГІНАЛИ ДОКУМЕНТІВ на напрям 050502 Сума балів вступних випробувань, творчих конкурсів, та вступних випробувань з фізичної підготовки	«УЗАГАЛЬНЕНИЙ МЕТОД НАЙМЕНШИХ КВАДРАТІВ (метод ЕЙТКЕНА)» Узагальнений метод найменших квадратів (метод Ейткена) оцінка параметрів лінійної економетричної моделі з гетероскедастиними заліками....
МетодичнІ матеріали до ВСТУПНИХ ВИПРОБУВАНЬ Методичні матеріали до вступних випробувань на навчання для осіб, які здобули освітньо-кваліфікаційний рівень молодшого спеціаліста...	УРОК 58 Тема уроку: Розв'язування логарифмічних рівнянь Мета уроку: формування умінь учнів розв'язувати логарифмічні рівняння різними методами: зведення логарифмічного рівняння до алгебраїчного;...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...	ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...
ЗМІСТ Вступ 3 Змістовна програма вступних випробувань 3 Критерії оцінювання 7 Література 9 Вступ Методичні матеріали до вступних випробувань з Історії України на навчання до Дніпропетровського університету імені Альфреда Нобеля...	Тема: Введення в хімію високомолекулярних сполук Опишіть методики визначення молекулярних мас полімерів (кріоскопія, ебуліоскопія, осмометрія, метод кінцевих груп, ультрацентрифугування,...

Додайте кнопку на своєму сайті:
Портал навчання