vi1 im 2

Значения для i можно найти в [47_N),ключи).ВIST_STS]. Затем вычисляется значение P-тест,value

	igamc K		,		2	obs
P-тест,value =
							.
		2				2

Тест серий

Цель теста серий (the serial test) – определить является ли число появлений 2m m-битовых пересекающихся образцов приблизительно таким же, как в случайной последовательности. Случайные последовательности однородны, т.е. каждый m-битовый образец имеет такой же шанс появления, как и любой другой m-битовый образец. Для случая m = 1 тест серий равносилен частотному тесту из п.????.

Тестируемая двоичная последовательность длиной n бит расширяется путем добавления к ней в конце (m–1) первых бит этой же последовательности.

Определяется частота появления всех возможных пересекающихся m-битовых блоков (серий), всех возможных пересекающихся (m–1)-битовых блоков и всех возможных пересекающихся (m–2)-битовых блоков:

vi1 im – частота появления m-битового блока i1…im,

vi1 im 1 – частота появления m-битового блока i1…im–1,

– частота появления m-битового блока i1…im–2. Вычисляются следующие значения

2

2m

n

2m

2

m

n

vi1 im

n

vi1 im

n ,

2

m

i1 im

i1 im

2

2m 1

n

2m 1

2

m 1

n

vi1 im 1

n

vi1 im 1

n ,

2

m 1

i1 im 1

i1 im 1

2

2m 2

n

2m 2

2

m 2

n

vi1 im 2

n

vi1 im 2

n .

2

m 2

i1 im 2

i1 im 2

Вычисляется тестовая статистика

m2 m2 m2 1 ,

2 m2 m2 2 m2 1 m2 2 .

Затем вычисляются значения P-тест,value1 и P-тест,value2

P-тест,value1 = igamc 2m 2 , m2 , P-тест,value2 = igamc 2m 3 , 2 m2 .

236

Энтропийный тест

Цель энтропийного теста (the approximate entropy test) – сравнить частоты пересекающихся блоков двух смежных длин (m и m+1) с аналогичными результатами для случайной последовательности.

Тестируемая двоичная последовательность длиной n бит расширяется путем добавления к ней в конце (m–1) первых бит этой же последовательности.

Подсчитываются частоты #i появления различных m-битовых блоков. Для каждого значения i вычисляется

Cim #ni ,

2m 1

m i log i ,

i 0

где i C 3j , j = log2i.

Аналогичным образом проводятся вычисления для (m+1)-битовых блоков. Вычисляется тестовая статистика

2 = 2n (ln 2 – ( (m) – (m+1))). Затем вычисляется значение P-тест,value

			m 1		2
P-тест,value =	igamc	2		,
					2	.

Тест совокупных сумм

Цель теста совокупных сумм (the cumulative sums (cusums) test) – определить является ли совокупная сумма частичных последовательностей, встречающихся в тестируемой последовательности, слишком большой или слишком маленькой относительно аналогичных совокупных сумм для случайной последовательности. Эту совокупную сумму можно рассматривать как случайный маршрут. Для случайной последовательности отклонение случайного маршрута должно быть около 0. Для определенных типов неслучайных последовательностей отклонения этого случайного маршрута от 0 будут большими.

Из тестируемой двоичной последовательности длиной n бит формируется последовательность X = x1, x2, …, xn, где xi = +1, если i-й элемент исходной последовательности равен 1 и xi = –1, если i-й элемент равен 0.

Последовательно вычисляются частичные суммы Si увеличивающихся подпоследовательностей, каждая из которых начинается с x1, если mode = 0, или xn если mode = 1. То есть для mode = 0: S1 = x1, S2 = x1 + x2, …, а для mode = 1: S1 = xn, S2 = xn + xn–1, ….

Вычисляется тестовая статистика

237

z max Sk .

1 k n

Затем вычисляется значение P-тест,value

P-тест,value =

где z

n 1

n

1

z

4k 1 z

4k 1 z

z

4k 3 z

4k 1 z

4

4

1

,

n

n

n

n

n

1

n

3

k

z

k

z

4

4

1

z

u2

e

2

du – нормальная функция распределения [53_Корн].

2

При mode = 0 большие значения статистики указывают на то, что в начальной части последовательности либо слишком много единиц, либо слишком много нулей. При mode = 1 большие значения статистики указывают на то, что в конечной части последовательности либо слишком много единиц, либо слишком много нулей. Маленькие значения статистики будут указывать на то, что единицы и нули перемешаны слишком равномерно.

Тест случайных отклонений

Цель теста случайных отклонений (the random excursions test) – определить отклоняется ли число визитов в случайном маршруте отдельного состояния от аналогичного числа в случайной последовательности.

Из тестируемой двоичной последовательности длиной n бит формируется последовательность X = x1, x2, …, xn, где xi = +1, если i-й элемент исходной последовательности равен 1 и xi = –1, если i-й элемент равен 0.

Последовательно вычисляются частичные суммы Si увеличивающихся подпоследовательностей, каждая из которых начинается с x1,т.е. S1 = x1, S2 = x1 + x2, …. Таким образом формируется набор S = {Si}. К полученному набору S добавляется ноль в начало и конец для формирования нового набора S’: S = 0, S1, S2, …, Sn, 0. Этот набор S’ и будет являться случайным маршрутом.

Определяется число нулевых узлов J – количество нулевых значений в наборе S’, за исключением первого нуля. Определяется число циклов в наборе S’. Цикл – это подпоследовательность в наборе S’, начинающаяся в одном нулевом узле и заканчивающаяся в следующем нулевом узле, включая первый нуль. Количество циклов в наборе S’ равно количеству нулевых узлов J.

Полагая, что набор S’ содержит значения x: –4, –3, –2, –1 и +1, +2, +3, +4, определяется частота каждого x в каждом цикле. Затем вычисляется vk(x) – количество циклов, в которых состояние x встретилось k раз, k = 0, …, 5. Для случая k = 5, считаются циклы, в которых состояние x встретилось 5 и более раз. При этом получается, что

238

5

vk x J .

k 0

Для каждого из восьми состояний x вычисляется тестовая статистика

2 obs	vk x J k x	,
5		2
i 0	J k x

где k(x) – вероятность того, что в случайном распределении состояние x встретится k раз. Значения для i можно найти в [47_N),ключи).ВIST_STS].

В результате будет вычислено 8 значений тестовой статистики.

Затем для каждого из восьми состояний x вычисляется значение P-тест,value

	igamc 5		,		2	obs
P-тест,value =
							.
		2				2

В результате будет получено 8 значений P-тест,value.

Вариант теста случайных отклонений

Цель варианта теста случайных отклонений (The Random Excursions Variant Test) – определить отклоняется ли общее число визитов в случайном маршруте отдельного состояния от аналогичного числа в случайной последовательности.

Из тестируемой двоичной последовательности длиной n бит формируется последовательность X = x1, x2, …, xn, где xi = +1, если i-й элемент исходной последовательности равен 1 и xi = –1, если i-й элемент равен 0.

Последовательно вычисляются частичные суммы Si увеличивающихся подпоследовательностей, каждая из которых начинается с x1,т.е. S1 = x1, S2 = x1 + x2, …. Таким образом формируется набор S = {Si}. К полученному набору S добавляется ноль в начало и конец для формирования нового набора S’: S = 0, S1, S2, …, Sn, 0. Этот набор S’ и будет являться случайным маршрутом.

Определяется число нулевых узлов J – количество нулевых значений в наборе S’, за исключением первого нуля. Определяется число циклов в наборе S’. Цикл – это подпоследовательность в наборе S’, начинающаяся в одном нулевом узле и заканчивающаяся в следующем нулевом узле, включая первый нуль. Количество циклов в наборе S’ равно количеству нулевых узлов J.

Для каждого из 18 ненулевых состояний x: – 9, – 8, …, – 1 и +1, +2, …, +9, вычисляются значения (x). (x) равно общему числу появлений состояния x во всех J циклах.

Затем для каждого из восьми состояний x вычисляется значение P-тест,value

			x J
P-тест,value = erfc											.
		2J 4			x				2

239

В результате будет получено 18 значений P-тест,value.

240

Исследование алгоритмов поточного шифрования Криптоанализ шифров Статистический анализ гаммы шифров

Для анализа прохождения псевдослучайными последовательностями статистического теста используются различные подходы. Пусть дана двоичная последовательность s. Необходимо установить проходит данная последовательность статистический тест или нет. Возможны следующие подходы:

1. Пороговый уровень.

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

2. Доверительный интервал.

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

3. Значение вероятности.

Этот подход заключается в вычислении для последовательности s тестовой статистики c(s) и соответствующего ей значения вероятности (P-тест,value). Здесь тестовая статистика рассматривается как реализация случайной величины, которая подчиняется известному закону распределения. Обычно статистические тесты строятся таким образом, чтобы большие значения тестовой статистики указывали на неслучайность тестируемой последовательности. Следовательно, маленькие значения P-тест,value рассматриваются как доказательство того, что тестируемая последовательность неслучайна. Правило принятия решения в данном случае формулируется следующим образом: для фиксированного уровня значимости двоичная последовательность s не проходит статистический тест, если P-тест,value < .

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

241

надежным по сравнению с первым. Однако, необходимо помнить о том, что различным уровням значимости соответствуют различные доверительные интервалы. Третий подход, основанный на использовании значения вероятности P-тест,value, имеет дополнительное преимущество по сравнению с предыдущим – не требуется конкретизации уровня значимости . То есть однажды вычисленное значение вероятности P-тест,value может сравниваться с любым уровнем значимости без дополнительных расчетов.

Большинство наборов статистического тестирования генераторов ПСП, например, такие как Diehard, Crypt-X и набор статистических тестов НИСТ, используют третий подход.

На практике существует много различных стратегий, используемых для статистического анализа генераторов случайных последовательностей. В [47_N),ключи).ВIST_STS] предлагается стратегия, состоящая из нескольких этапов:

1.Выбор генератора.

Выберите для тестирования программный или аппаратный генератор. Генератор должен производить двоичную последовательность нулей и единиц длиной n.

2.Генерация двоичной последовательности.

Для фиксированной последовательности длиной n и выбранного ранее генератора сконструируйте набор из m двоичных последовательностей.

3.Выполнение набора статистических тестов.

Примените статистические тесты к сконструированному на втором этапе набору последовательностей.

4.Проверка значений P-тест,value.

Врезультате выполнения статистических тестов будут получены соответствующие промежуточные значения (тестовая статистика и P-тест,value). На основе этих P-тест,value может быть сделано заключение, касающееся качества последовательности.

5.Оценка.

Для каждого статистического теста вычисляется набор значений P-тест,value, соответствующий набору последовательностей. Для фиксированного уровня значимости ожидается конечный процент P-тест,value, указывающий на провал. Например, если выбран уровень значимости равный 0,01, т.е. = 0,01, то ожидается, что около 1% последовательностей тестирование провалит.

Последовательности проходят статистические тесты всякий раз, когда P-тест,value , и не проходят во всех остальных случаях. Для каждого статистического теста вычисляется и анализируется пропорция последовательностей, успешно прошедших тестирование.

В результате тестирования может произойти три типичных исхода:

242

1.Анализ P-тест,value не указывает на отклонение от случайности.

2.Анализ ясно указывает на отклонение от случайности.

3.Анализ является недостаточным.

Впредлагается два способа интерпретации результатов:

1.Исследование доли последовательностей, прошедших статистические

тесты.

2.Исследование распределения значений P-тест,value, чтобы проверить равномерность их распределения.

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

Рассмотрим первый способ интерпретации результатов – анализ доли последовательностей, проходящих тест.

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

Например, если была протестирована 1000 двоичных последовательностей, т.е. m = 1000,

= 0,01 (уровень значимости) и при этом для 996 последовательностей P-тест,value 0,01, то доля последовательностей, которые проходят этот тест, равна 996/1000 = 0,996. Диапазон приемлемых значений этой доли определяется с использованием доверительного интервала, определенного как:

p 3	p	1 p	,
		m

где p’=1 – , m – размер образца.

Если доля выходит за пределы этого интервала, то это свидетельствует, что данные неслучайны.

Для примера, приведенного выше, доверительный интервал равен:

0,99 3 0,99 1 0,99 0,99 0,0094392,

1000

т.е. доля должна лежать выше 0,9805607.

Рассмотрим второй способ интерпретации результатов – анализ равномерности распределения значений P-тест,value.

Интервал [0; 1] делится на 10 подинтервалов. Подсчитывается количество значения P-тест, value, лежащие в каждом из подинтервалов. Затем применяется тест 2 (хи-квадрат) и

243