rijndael (1085220), страница 6
Текст из файла (страница 6)
Выберем a равным 0.01, которое говорит о том, что из 100 случайных последовательностей не прошла бы тест лишь одна. При P-value > 0.01 последовательность рассматривается как случайная с доверительностью 99%. При P-value < 0.01 последовательность рассматривается как неслучайная с доверительностью 99%.
Итак, оценка статистических испытаний основана на проверке гипотезы о случайности исследуемой последовательности нулей единиц. Ниже приведен алгоритм, позволяющий оценить конкретную двоичную последовательность.
Постановка гипотезы. Предполагаем, что последовательность является случайной.
Вычисление тестовой статистики. Проводим непосредственное тестирование последовательности на битном уровне.
Вычисление P-value. P-value Î[0;1].
Сравнение P-value с a. Задаем a, где a= 0.01. Если P-value > a, то тесты пройдены.
Далее приведен список и общие характеристики (определяемы дефект) каждого статистического теста НИСТ.
1. Частотный тест. Слишком много нулей или единиц.
2. Частотный тест в подпоследовательностях. Слишком много нулей или единиц в подпоследовательностях.
3. Проверка “дырок”. Большое (малое) число подпоследовательностей нулей и единиц свидетельствует, что колебание потока бит слишком быстрое (медленное).
4. Проверка “дырок” в подпоследовательностях. Отклонения в распределении подпоследовательностей единиц.
5. Проверка рангов матриц. Отклонение распределения рангов матриц от соответствующего распределения для истинно случайной последовательности, связанное с периодичностью подпоследовательностей.
6. Спектральный тест. Периодические свойства последовательности.
7. Проверка непересекающихся шаблонов. Непериодические шаблоны встречаются слишком часто.
8. Проверка пересекающихся шаблонов. Слишком часто встречаются m-битные последовательности единиц.
9. Универсальный статистический тест Маурера. Сжимаемость (регулярность) последовательности.
10. Сжатие при помощи алгоритма Лемпела-Зива. Большая сжимаемость, чем истинно случайная последовательность.
11. Линейная сложность. Отклонение от распределения линейной сложности для конечной длины (под)строки.
12. Проверка серий. Неравномерность распределения m-битных слов.
13. Проверка аппроксимированной энтропии. Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость.
14. Проверка кумулятивных сумм. Слишком много нулей или единиц в начале последовательности.
15. Проверка случайных отклонений. Отклонение от распределения числа появлений подпоследовательностей определенного вида.
16. Разновидность проверки случайных отклонений. Отклонение от распределения числа появлений подпоследовательностей определенного вида.
4.3 Описание каждого теста и их параметры.
Длина тестируемой последовательности во всех тестах равна бит. Число экспериментов равно 1000 для каждого теста.
4.3.1 Частотный (Монобитный) тест (Frequency).
Цель этого теста состоит в том, чтобы определить, является ли число появлений 0 и 1 в последовательности приблизительно тем же самым, как ожидалось бы для верно случайной последовательности. Тест оценивает близость частоты появления 1 к 1/2, то есть и количество 0 в последовательности должно быть тем же самым. Все последующие тесты зависят от прохождения этого теста; нет другого наглядного теста, чтобы показать, что тестируемая последовательность неслучайна.
4.3.2 Частотный тест в подпоследовательностях
(Block-Frequency).
Цель этого испытания состоит в том, чтобы определить, приближается ли число появлений 1 в M-битной подпоследовательности к величине M/2, как ожидалось бы согласно предположению о ее случайности. Для размера блока M=1, этот тест вырождается в Частотный (Монобитный) тест.
В нашем тесте значение длины подпоследовательности равно M=10500.
4.3.3 Тест “дырок” (Runs).
Внимание этого теста сосредоточено на общем количестве отрезков в последовательности, где отрезок — непрерывная последовательность идентичных бит (0 или 1). Отрезок длины k состоит ровно из k идентичных бит и ограничен до и после противоположным битом. Цель теста состоит в том, чтобы определить, какое число отрезков из 0 или 1 различных длин ожидается для случайной последовательности. В частности этот тест определяет, является ли колебание между такими 0 или 1 слишком быстрым или медленным. “Дыркой” называется отрезок из 0.
4.3.4 Тест “блоков” в подпоследовательностях (Long-Run).
Внимание этого теста сосредоточено на самым длинном отрезке, состоящего из 1 (“блок”), в M-битной подпоследовательности. Цель этого теста состоит в том, чтобы определить, согласуется ли длина самого длинного отрезка в тестируемой последовательности с длиной самого длинного “блока”, ожидаемой в случайной последовательности. Обратим внимание, что неравномерность в ожидаемой длине самого длинного “блока” подразумевает, что есть также неравномерность в ожидаемой длине самой длинной “дырке”. Поэтому, можно тестировать только “блоки”.
4.3.5 Проверка рангов матриц (Rank).
Внимание этого теста сосредоточено на появлении матриц различных рангов. Матрица интерпретируется как часть последовательности. Цель этого теста состоит в том, чтобы проверить линейную зависимость среди фиксированных подстрок исходной последовательности.
4.3.6 Спектральный тест (FFT).
Внимание этого теста сосредоточено на высоте выброса дискретного пробразования Фурье последовательности. Цель этого теста состоит в том, чтобы обнаружить периодические особенности (то есть, повторные образцы, находящиеся друг около друга) в тестируемой последовательности, которая показала бы отклонение от предположения о ее случайности. Смысл состоит в том, чтобы обнаружить, превышает ли число высот выбросов, превышающих порог на 95%, более чем на 5%.
4.3.7 Проверка непересекающихся шаблонов
(Aperiodic-Template).
Внимание этого теста сосредоточено на количестве возникновений заранее определенных шаблонов. Цель этого теста состоит в том, чтобы обнаружить генераторы, которые вырабатывают слишком много заданных шаблонов. Для этого теста и для теста Пересекающихся шаблонов (описание ниже), m-битное окно используется для поиска определенных m-битных образцов. Если образец не найден, то окно сдвигается на одну позицию. Если образец найден, окно сдвигается на m позиций. И так до конца последовательности.
В нашем тесте значение длины шаблона равно m=9.
4.3.8 Проверка пересекающихся шаблонов
(Periodic-Template).
Этот тест очень похож на тест Непересекающихся шаблонов. Различие между этим тестами в том, что в этом тесте, когда образец найден, окно сдвигается только на одну позицию.
В данном тесте значение длины шаблона так же равно m=9.
4.3.9 Универсальный тест Маурера (Universal).
Внимание этого теста сосредоточено на числе бит между соответствующими образцам (мера, которая связана с длиной сжатой последовательности). Цель теста состоит в том, чтобы обнаружить, действительно ли последовательность может быть значительно сжата без потери информации. Значительно сжимаемая последовательность, как считается, является неслучайной.
Тестируемая последовательность разбивается на два сегмента: инициализирующий и тестовый. Первый состоит из Q блоков по L бит каждый, второй из K=ën/Lû-Q блоков по L бит.
В данном тесте значение параметров равны L=7 и Q=1280.
4.3.10 Проверка сжатия при помощи алгоритма Лемпела-Зива
(Lempel-Ziv).
Внимание этого теста сосредоточено на числе кумулятивно отличных образцов (слов) в последовательности. Цель теста состоит в том, чтобы определить, как сильно тестируемая последовательность может быть сжата. Считается, что последовательность является неслучайной, если она может быть значительно сжата. Случайная последовательность будет иметь характерное число отличных образцов.
4.3.11 Проверка линейной сложности (Linear-Complexity).
Внимание этого теста сосредоточено на длине линейного регистра сдвига с обратной связью (LFSR). Цель этого теста состоит в том, чтобы определить, действительно ли последовательность достаточно сложна, чтобы быть случайной. Случайные последовательности характеризуются более длинным регистром сдвига. Регистр сдвига, который является слишком коротким, считается неслучайным.
Тестируемая последовательность разбивается на подпоследовательности длины M, для которой и вычисляется длина регистра сдвига.
В данном тесте значение параметра равно M=500.
4.3.12 Проверка серий (Serial).
Внимание этого теста сосредоточено на частоте всех возможных пересекающихся m-битных образцов сквозь полную последовательность. Цель этого теста состоит в том, чтобы определить, является ли число возникновений m-битных пересекающихся образцов приблизительно тем же самым, какое ожидается для случайной последовательности. Случайные последовательности имеют однородность; то есть каждый m-битный образец имеет ту же самую возможность появления как и любой другой. Обратим внимание, что для m=1, этот тест эквивалентен Частотному (Монобитному) тесту.
В данном тесте значение параметра равно m=5.
4.3.13 Проверка аппроксимированной энтропии (Apen).
Внимание этого теста сосредоточено на тех же объектах, что и в тесте Проверки серий. Цель теста состоит в том, чтобы сравнить частоту пересекающихся блоков двух смежных длин (m и m+1) по отношению к ожидаемому результату для случайной последовательности.
В данном тесте значение параметра равно m=5.
4.3.14 Проверка кумулятивных сумм (Cusum).
Внимание этого теста сосредоточено на максимальном отклонении суммы элементов нормированной последовательности от нуля. Цель теста состоит в том, чтобы определить, является ли совокупная сумма частичных последовательностей, встречающихся в тестируемой последовательности слишком большой или слишком маленькой относительно ожидаемого поведения совокупной суммы для случайных последовательностей. Эта совокупная сумма может рассматриваться как случайное хождение (на шаг вперед или назад). Для случайной последовательности, отклонение случайного хождения должны быть около нуля. Для некоторых типов неслучайных последовательностей, отклонение этого случайного хождения от нуля будет большим числом.
4.3.15 Проверка случайных отклонений (Random-Excursion).
Внимание этого теста сосредоточено на числе циклов, имеющих точно K посещений в совокупной сумме случайного хождения. Совокупная сумма случайного хождения получена из частичных сумм после замены 0 и 1 в исходной последовательности на -1 и +1. Цикл случайного хождения состоит из последовательности шагов длины единицы, которая начинается и заканчивается в одном и том же состоянии. Цель этого теста состоит в том, чтобы определить, отклоняется ли число посещений отдельного состояния в пределах цикла, от того, которого можно было бы ожидать для случайной последовательности.
4.3.16 Проверка случайных отклонений (вариант)
(Random-Excursion-V).
Внимание этого теста сосредоточено на общем количестве посещений отдельных состояния в совокупной сумме случайного хождения. Цель этого теста состоит в том, чтобы обнаружить отклонения от ожидаемого числа посещений различных состояний в случайном хождении. Данный тест является расширением предыдущего.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
