close

Вход

Забыли?

вход по аккаунту

?

kursovaya itog

код для вставкиСкачать
ВВЕДЕНИЕ
Важнейшими элементами любой системы защиты являются генераторы псевдослучайных последовательностей. Нахождения случайных и псевдослучайных последовательностей - одна из главных задач криптографии. Например, в любой криптосистеме используются ключи, которые должны быть сгенерированы случайным образом. Многие криптографические протоколы, такие как электронно-цифровая подпись и протокол аутентификации, также основаны на случайных и псевдослучайных числах.
В реальной жизни многие задачи не являются столь тривиальными, как, например, задача зашифровывания одного файла. Очень часто требуется не только и не столько зашифровать данные, сколько еще и сделать их хранение и передачу как можно более эффективной. В программных приложениях активно используются алгоритмы сжатия, а периферийные устройства на аппаратном уровне поддерживают работу методов обеспечения целостности хранимых и передаваемых данных.
В данном курсовом проекте будут рассмотрены статистические тесты для определения псевдослучайной последовательности. Будет проведён анализ работы тестов и оценена эффективность.
1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
1.1 Наборы статистических тестов для тестирования псевдослучайных последовательностей
При реализации криптографических преобразований, используют различные случайные первичные состояния либо целые последовательности. Отсюда следует, что стойкость криптопреобразования напрямую зависит от алгоритма формирования случайных чисел и последовательностей, точнее от их степени случайности.
Современные компиляторы обладают собственной реализацией генератора псевдослучайных последовательностей, однако, с криптографической точки зрения они являются непригодными. Основная сложность генерации последовательности псевдослучайных чисел на компьютере в том, что компьютеры детерминистичны по своей сути. Компьютер может находиться только в конечном количестве состояний (количество состояний огромно, но все-таки конечно). Следовательно, любой датчик случайных чисел по определению периодичен. Все периодическое - предсказуемо, т.е. не случайно. Лучшее, что может произвести компьютер - это псевдослучайная последовательность. Период такой последовательности должен быть таким, чтобы конечная последовательность разумной длины не была периодической. Относительно короткие непериодические подпоследовательности должны быть как можно более неотличимы от случайных последовательностей, в частности, соответствовать различным критериям случайности.
Генератор последовательности псевдослучаен, если он выглядит случайным, т.е. проходит все статистические тесты случайности. Для криптографических приложений статистической случайности недостаточно, хотя это и необходимое свойство.
Последовательность называется криптографически надежной псевдослучайной последовательностью, если она непредсказуема, т.е. вычислительно неосуществимо предсказать следующий бит, имея полное знание алгоритма (или аппаратуры) и всех предшествующих битов потока.
Во многих протоколах и шифрах случайные слова и числа используются как секретные ключи. Более того, с развитием криптографии выяснилось, что многие фундаментальные проблемы этой науки тесно связаны с генерированием и тестированием случайных чисел. Методы, используемые для проверки этого условия, рассматриваются в рамках математической статистики. Таким образом, необходимо проверить гипотезу о том, что источник порождает символы алфавита равновероятно и независимо, против альтернативной гипотезы, говорящей, что последовательность создана стационарным источником и не выполняется. 0 H1 H0 H
Рисунок 1 - Группы тестов для исследования ПСП
Для исследования ПСП применяются две группы тестов (рис. 1): 1. Графические тесты. Статистические свойства последовательностей отображаются в виде графических зависимостей, по виду которых делают выводы о свойствах исследуемой последовательности. 2. Оценочные тесты. Статистические свойства последовательностей определяются числовыми характеристиками. На основе оценочных критериев делаются заключения о степени близости свойств анализируемой и истинно случайной последовательностей. В отличие от графических тестов, где результаты интерпретируются пользователями, вследствие чего возможны различия в трактовке результатов, оценочные тесты характеризуются тем, что они выдают численную характеристику, которая позволяет однозначно сказать, пройден тест или нет. Тесты Diehard - это набор статистических тестов для измерения качества набора случайных чисел. Они были разработаны Джордже Марсалья в течение нескольких лет и впервые опубликованы в 1995 г. на CD-ROM, посвященном случайным числам. Вместе они рассматриваются как один из наиболее строгих существующих наборов тестов.
Тесты Д. Кнута
Тесты Кнута основаны на статистическом критерии. Вычисляемое значение статистики сравнивается с табличными результатами, и в зависимости от вероятности появления такой статистики делается вывод о ее качестве. Среди достоинств этих тестов - небольшое их количество и существование быстрых алгоритмов выполнения. Недостаток - неопределенность в трактовке результатов. Вот краткое описание этих тестов:
- проверка несцепленных серий. Последовательность разбивается на m непересекающихся серий и строится распределение для частот появления каждой возможной серии.
- проверка интервалов. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя длины подпоследовательностей, все элементы которых принадлежат определённому числовому интервалу.
- проверка комбинаций. Последовательность разбивается на подпоследовательности определённой длины, и исследуются серии, состоящие из различных комбинаций чисел.
- тест собирателя купонов. Пусть существует последовательность длины n и размерности m. Исследуются подпоследовательности определённой длины, содержащие каждое m-разрядное число.
- проверка перестановок. Данный тест проверяет равномерность распределения символов в исследуемой последовательности, анализируя взаимное расположение чисел в подпоследовательностях.
- проверка на монотонность. Служит для определения равномерности исходя из анализа невозрастающих и неубывающих подпоследовательностей.
- проверка корреляции. Данный тест проверяет взаимонезависимость элементов последовательности.
TEST-U01 Автор - P.L'Ecuyer и др. Организация - Universit´e de Montr´eal
TestU01 - это программная библиотека, реализованная на языке ANSI C, которая предлагает набор утилит для эмпирической проверки статистических равномерного генератора случайных чисел.
Библиотека реализует несколько типов генераторов случайных чисел в общей форме, а также многие конкретные генераторы, предложенные в литературе или найденные в широко используемом программном обеспечении. Она обеспечивает общее реализации классических статистических тестов для генераторов случайных чисел, а также ряд других предложенных в литературе, и некоторые оригинальные. Эти тесты могут быть применены к генераторам предопределенных в библиотеку и пользовательских генераторов. Конкретные люкс тесты для любой последовательности равномерных случайных чисел в [0,1] или последовательности бит, также доступны. Основные инструменты для построения векторов точек производства генераторов также предоставляются.
Дополнительное программное обеспечение позволяет выполнять систематические исследования взаимодействия специальных тестов и структуры заданных точек производства данного семейства генераторов случайных чисел. То есть, для данного вида испытаний и данного класса генераторов случайных чисел, определяется, насколько большой должна быть выборка из теста, в зависимости от длины периода генератора, прежде чем генератор начнёт проваливать тест систематически.
Таблица 1 - Основные тесты для определения случайности последовательности
№НазваниеАвторОрганизация разработки1Тесты NISTHandbook of Applied CryptographyNIST ITL2TEST-U01P.L'Ecuyer и дрUniversit´e de Montr´eal3CRYPT-XHelen Gustafson и дрQueensland University of Technology4The pLab ProjectPeter HellekalekUniversity of Salzburg5DIEHARDGeorge MarsagliaFlorida State University6DieharderRobert G. BrownDuke University7ENTJohn WalkerAutodesk, Inc8The Art Of Computer Programming Vol. 2 Seminumerical AlgorithmsДональд КнутStanford University9Handbook of Applied CryptographyAlfred Menezes и дрCRC Press, Inc
Различные усилия, основанные на принципе анализа, показывают, что есть избыточности в статистических тестах (то есть, не все тесты являются независимыми). Результаты также предполагают, что статический набор тестов NIST содержит достаточное количество практически независимых статистических испытаний, которые обнаруживают любое отклонение от случайности. Следовательно, для анализа случайности мы используем самые строгие тесты на случайность: NIST набор тестов. Рассмотрим данный набор более подробно.
1.2. Пакет статических тестов NIST
Статистические тесты NIST - это пакет статистических тестов, разработанный Лабораторией информационных технологий (англ. Information Technology Laboratory), являющейся главной исследовательской организацией Национального института стандартов и технологий (NIST). Отличие этих тестов от других современных - открытость алгоритмов. Также среди достоинств - однозначная интерпретация результатов тестирования. В состав пакета входит 15 статистических тестов, целью которых является определение меры случайности двоичных последовательностей, порождённых либо аппаратными, либо программными генераторами случайных чисел. Эти тесты основаны на различных статистических свойствах, присущих только случайным последовательностям. Итак, в таблице 2, представленной ниже, рассмотрим тесты NIST подробнее. Стоит отметить, что не прохождение хоть одного из тестов автоматически отменяет все последующие тесты - числа неслучайны, и продолжать проверку нет смысла.
Все тесты делятся на две группы: параметризованные и непараметризованные.
Таблица 2 - Виды тестов NIST
НазваниеСуть тестаОбнаруживаемый дефектНепараметризованные тесты1.Побитный тест (Frequency (monobit) test)Определение соотношения между нулями и единицами во всей двоичной последовательности. Цель - выяснить действительно ли число нулей и единиц в последовательности приблизительно одинаковы, как это можно было бы предположить в случае истинно случайной бинарной последовательности. Тест оценивает насколько близка доля единиц к 0,5 длины всей последовательности. Таким образом число нулей и единиц должно быть примерно одинаковым. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, последовательность носит случайный характер. Все последующие тесты проводятся при условии, что пройден данный тест.Слишком много нулей или единиц2.Тест на последовательность одинаковых битов (Runs test)Подсчёт полного числа рядов в исходной последовательности, где под словом "ряд" подразумевается непрерывная подпоследовательность одинаковых битов.
Ряд длиной k бит состоит из k абсолютно идентичных битов, начинается и заканчивается с бита, содержащего противоположное значение. Цель данного теста - сделать вывод о том действительно ли число рядов, состоящих из единиц и нулей, и различными длинами соответствует их числу в случайной последовательности. В частности, определяется быстро либо медленно чередуются единицы и нули в исходной последовательности. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является истинно случайной. В противном случае, она носит случайный характер.Большое (маленькое) общее количество рядов указывает, что колебание (изменения между рядами нолей и рядами единиц), слишком быстрое (слишком медленное)3.Тест на самую длинную последовательность единиц в блоке (Test for longest run of ones in a block)Определяется самый длинный ряд единиц внутри блока длиной m бит. Цель - выяснить действительно ли длина такого ряда соответствует ожиданиям длины самого протяжённого ряда единиц в случае абсолютно случайной последовательности. Если высчитанное в ходе теста значение вероятности p < 0,01 полагается, что исходная последовательность не является случайной. В противном случае, делается вывод о ее случайности. Следует заметить, что из предположения о примерно одинаковой частоте появления единиц и нулей (тест № 1) следует, что точно такие же результаты данного теста будут получены при рассмотрении самого длинного ряда нулей. Поэтому измерения можно проводить только с единицами.Отклонение распределения длинных рядов4.Тест сжатия Лемпеля - Зива (Lempel-Ziv compression test)Этот тест сосредотачивает свое внимание на сжатии тестируемой последовательности. При сжатии алгоритмом Лемпеля-Зива нехаотическая последовательность поддается хорошему сжатию, а хаотическая сжатию не поддается.Более сжатая, чем действительно случайная последовательность5.Тест рангов бинарных матриц (Binary matrix rank test)
Производится расчёт рангов непересекающихся подматриц, построенных из исходной двоичной последовательности. Целью этого теста является проверка на линейную зависимость подстрок фиксированной длины, составляющих первоначальную последовательность. В случае, если вычисленное в ходе теста значение вероятности p < 0,01, делается вывод о неслучайном характере входной последовательности бит. В противном случае, считаем ее абсолютно случайной.Проверка на линейную зависимость среди подстрок исходной последовательности6.Тест кумулятивных сумм (Cumulative sums test)
Тест заключается в максимальном отклонении (от нуля) при произвольном обходе, определяемым кумулятивной суммой заданных (-1, +1) цифр в последовательности. Цель данного теста - определить является ли кумулятивная сумма частичных последовательностей, возникающих во входной последовательности, слишком большой или слишком маленькой по сравнению с ожидаемым поведением такой суммы для абсолютно случайной входной последовательности. Таким образом, кумулятивная сумма может рассматриваться как произвольный обход. Для случайной последовательности отклонения от произвольного обхода должны быть вблизи нуля. Для некоторых типов последовательностей, не являющихся в полной мере случайными подобные отклонения от нуля при произвольном обходе будут достаточно существенными. Если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит случайный характер.Слишком много нолей или единиц в начале последовательности.7.Спектральный тест на основе ДФП (Discrete Fourier transform (spectral) test)
Оценка высоты пиков дискретного преобразования Фурье исходной последовательности. Цель - выявление периодических свойств входной последовательности, например, близко расположенных друг к другу повторяющихся участков. Тем самым это явно демонстрирует отклонения от случайного характера исследуемой последовательности. Идея состоит в том, чтобы число пиков, превышающих пороговое значение в 95 % по амплитуде, было значительно больше 5 %. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является абсолютно случайной. В противном случае, она носит случайный характер.Периодические особенности в битовом потоке8.Тест на произвольные (случайные) отклонения (Random excursions test)
Подсчёт числа циклов, имеющих строго k посещений при произвольном обходе кумулятивной суммы. Произвольный обход кумулятивной суммы начинается с частичных сумм после последовательности (0,1), переведённой в соответствующую последовательность (-1, +1). Цикл произвольного обхода состоит из серии шагов единичной длины, совершаемых в случайном порядке. Кроме того такой обход начинается и заканчивается на одном и том же элементе. Цель данного теста - определить отличается ли число посещений определенного состояния внутри цикла от аналогичного числа в случае абсолютно случайной входной последовательности. Фактически данный тест есть набор, состоящий из восьми тестов, проводимых для каждого из восьми состояний цикла: −4, −3, −2, −1 и +1, +2, +3, +4. В каждом таком тесте принимается решение о степени случайности исходной последовательности в соответствии со следующим правилом: если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит случайный характер.Слишком много посещений случайных блужданий в одно из состяний9.Вариант теста на произвольные отклонения (Random excursions variant test)Подсчитывается общее число посещений определенного состояния при произвольном обходе кумулятивной суммы. Целью является определение отклонений от ожидаемого числа посещений различных состояний при произвольном обходе. В действительности этот тест состоит из 18 тестов, проводимых для каждого состояния: −9, −8, ..., −1 и +1, +2, ..., +9. На каждом этапе делается вывод о случайности входной последовательности. Если вычисленное в ходе теста значение вероятности p < 0,01, то входная двоичная последовательность не является абсолютно случайной. В противном случае, она носит случайный характер.Слишком много посещений (посредством числа случайных блужданий) в одно из состянийПараметризованные тесты1.Частотный блочный тест (Frequency test within a block)Определение доли единиц внутри блока длиной m бит. Цель - выяснить действительно ли частота повторения единиц в блоке длиной m бит приблизительно равна m/2, как можно было бы предположить в случае абсолютно случайной последовательности. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не носит истинно случайный характер. Если принять m = 1, данный тест переходит в тест № 1 (частотный побитовый тест).Слишком много единиц в пределах M-битного блока2.Тест аппроксимационный энтропии (Approximate entropy test)
Акцент делается на подсчёте частоты всех возможных перекрываний шаблонов длины m бит на протяжении исходной последовательности битов. Цель теста - сравнить частоты перекрывания двух последовательных блоков исходной последовательности с длинами m и m+1 с частотами перекрывания аналогичных блоков в абсолютно случайной последовательности. Вычисляемое в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно случайной.Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость3.Тест на линейную сложность (Linear complexity test)В основе теста лежит принцип работы линейного регистр сдвига с обратной связью (англ. Linear Feedback Shift Register, LFSR). Цель - выяснить является ли входная последовательность достаточно сложной для того, чтобы считаться абсолютно случайной. Абсолютно случайные последовательности характеризуются длинными линейными регистрами сдвига с обратной связью. Если же такой регистр слишком короткий, то предполагается, что последовательность не является в полной мере случайной. В ходе теста вычисляется значение вероятности p. Если p < 0,01, то полагается, что исходная последовательность не является случайной. В противном случае, делается вывод о её случайности.Отклонение от распределения линейной сложности для последовательности конечной длины4.Универсальный статистический тест Маурера (Maurer's universal statistical test) Определяется число бит между одинаковыми шаблонами в исходной последовательности (мера, имеющая непосредственное отношение к длине сжатой последовательности). Цель теста - выяснить может ли данная последовательность быть значительно сжата без потерь информации. В случае, если это возможно сделать, то она не является истинно случайной. В ходе теста вычисляется значение вероятности p. Если p < 0,01, то полагается, что исходная последовательность не является случайной. В противном случае, делается вывод о её случайности.Сжимаемость (регулярность) (подпоследовательность представляет всю последовательность)5.Тест на периодичность (Serial test)
Подсчет частоты всех возможных перекрываний шаблонов длины m бит на протяжении исходной последовательности битов. Целью является определение действительно ли количество появлений 2m перекрывающихся шаблонов длиной m бит, приблизительно такое же как в случае абсолютно случайной входной последовательности бит. Последняя, как известно, обладает однообразностью, то есть каждый шаблон длиной m бит появляется в последовательности с одинаковой вероятностью. Если вычисленное в ходе теста значение вероятности p < 0,01, то данная двоичная последовательность не является абсолютно случайной. В противном случае, она носит случайный характер. Стоит отметить, что при m=1 тест на периодичность переходит в частотный побитовый тест (№ 1).Неравномерное распределение слов длиной m. Схоже с Приблизительной Энтропией6.Тест на совпадение неперекрывающихся шаблонов (Non-overlapping template matching test)
Подсчитывается количество заранее определенных шаблонов, найденных в исходной последовательности. Цель - выявить генераторы случайных или псевдослучайных чисел, формирующие слишком часто заданные непериодические шаблоны. Как и в тесте на совпадение перекрывающихся шаблонов для поиска конкретных шаблонов длиной m бит используется окно также длиной m бит. Если шаблон не обнаружен, окно смещается на один бит. Если же шаблон найден, окно перемещается на бит, следующий за найденным шаблоном, и поиск продолжается дальше. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно случайной.Слишком много возникновений непериодических шаблонов7.Тест на совпадение перекрывающихся шаблонов (Overlapping template matching test)
Подсчет количества заранее определенных шаблонов, найденных в исходной последовательности. Как и в тесте №6 на совпадение неперекрывающихся шаблонов для поиска конкретных шаблонов длиной m бит используется окно также длиной m бит. Сам поиск производится аналогичным образом. Если шаблон не обнаружен, окно смещается на один бит. Разница между этим тестом и тестом № 3.6 заключается лишь в том, что если шаблон найден, окно перемещается только на бит вперед, после чего поиск продолжается дальше. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не является абсолютно случайной.Слишком много возникновений M-битных рядов единиц
1.3 Определение ошибки I и II рода
Статистический тест формулируется для проверки определенной нулевой гипотезы H0 о том, что проверяемая последовательность является случайной. С этой нулевой гипотезой связана альтернативная гипотеза Hα о том, что последовательность неслучайна. Для каждого применяемого теста получают заключение о принятии или отклонении нулевой гипотезы, основываясь на сформированной исследуемым генератором последовательности. Для каждого теста должна быть выбрана подходящая статистика случайности для принятия или отклонения нулевой гипотезы. Согласно предположению о случайности, такая статистика имеет распределение возможных значений. Теоретическое эталонное распределение этой статистики для нулевой гипотезы определяется математическими методами. Из этого эталонного распределения определяется критическое значение. Во время проведения теста вычисляется значение тестовой статистики. Это значение сравнивается с критическим значением. Если значение тестовой статистики превышает критическое значение, нулевая гипотеза для случайности отклоняется. В противном случае нулевая гипотеза принимается.
Проверка статистических гипотез работает, потому что эталонное распределение и критическое значение зависят и генерируются согласно предварительному предположению о случайности. Если предположение о случайности последовательности истинно, то результирующее значение тестовой статистики для нее будет иметь очень низкую вероятность превышения критического значения (например, 0.01). С другой стороны, если расчетное значение тестовой статистики превышает критическое значение (т. е. происходит событие с низкой вероятностью), то с точки зрения проверки статистической гипотезы событие с низкой вероятностью не может встретиться естественно. Поэтому, когда расчетное значение тестовой статистики превышает критическое значение, делается заключение, что первоначальное предположение о случайности является подозрительным или ошибочным. В этом случае делается заключение об отклонении H0 (случайность) и принятии Hα (не случайность).
Проверка статистической гипотезы - процедура генерации заключения, которая имеет два возможных результата - или принять H0 (данные случайны), или принять Hα (данные не случайны). Таблица 3 связывает истинное (неизвестное) состояние данных с заключением, полученным процедурой проверки.
Таблица 3 - Принятие заключений по результатам проведения статистических испытаний
СитуацияЗаключениеПринять H0Принять HαДанные случайны (H0 истина)Нет ошибкиОшибка I родаДанные неслучайны (Hα истина)Ошибка II родаНет ошибки
Если данные на самом деле случайны, то заключение об отклонении нулевой гипотезы (т.е. что данные не случайны) будет приниматься крайне редко. Это заключение называется ошибкой первого рода. Если данные не случайны, то заключение о принятии нулевой гипотезы (т. е. что данные случайны) называется ошибкой второго рода. Заключения о принятии H0, когда данные действительно случайны, и отклонении H0, когда данные не случайны, являются правильными.
Вероятность ошибки 1-го рода называется уровнем значимости теста. Эта вероятность может быть установлена до испытания и обозначается как α. Для теста α суть вероятность того, что тест укажет на не случайность последовательности, тогда как на самом деле она является случайной. То есть на то, что последовательность имеет неслучайные свойства, даже если ее произвел хороший генератор.
Вероятность ошибки 2-го рода обозначается как β. Для теста β есть вероятность того, что тест укажет на случайность последовательности, тогда как это не так; т. е. плохой генератор произвел последовательность, которая, как кажется, имеет случайные свойства. В отличие от α, β не является фиксированным значением; β могут принимать множество различных значений, потому что существует бесконечное число ситуаций, когда поток данных может быть неслучаен, и каждая из них выдает различные β. Вычисление ошибки 2-го рода является более сложным из-за множества возможных типов неслучайности.
Одной из основных целей нижеописанных тестов является минимизация вероятности ошибки 2-го рода, иначе говоря, минимизация вероятности принятия последовательности, произведенной плохим генератором, за последовательность, произведенную хорошим генератором. Вероятности α и β связаны друг с другом длиной n проверяемой последовательности: если два этих значений определены, третье определяется автоматически. На практике обычно выбирают размер n и значение для α (вероятности ошибки 1-го рода). Тогда критическая точка для данной статистики выбирается так, чтобы получить наименьшее значение β (вероятность ошибки 2-го рода).
Каждый тест основан на вычислении значения тестовой статистики, которое является функцией данных. Если значение тестовой статистики есть S, а t - критическое значение, то вероятность ошибки 1-го рода и 2-го рода есть соответственно P(S > t || H0 истина) = P(отклонить H0 | H0 истина),
P(S ≤ t || H0 ложка) = P(принять H0 | H0 ложна).
1.4 Пошаговый процесс тестирования
Изначально определим, что такое P-value. P-value - вероятность того, что наблюдаемый результат (или более экстремальные результаты), произошел бы случайно, если на самом деле нет никакого результата. Однако это не говорит ничего о масштабе истинного результата и, кроме того, поскольку проверки гипотез являются разветвлёнными (мы заинтересованы в различиях в любом направлении), она даже не говорит нам направление этого результата. Таким образом, например, P-value = 0.006 указывает, что положительный результат произошел бы только в 6 из 1000 испытаний, если в действительности нет никакого эффекта. P-value отвечает на вопрос: "Есть ли между этими двумя режимами статистически значимые различия?"
Тестовая статистика использует вычисление значения P-value, которое констатирует силу доказательства против нулевой гипотезы, иначе говоря, P-value есть вероятность того, что совершенный генератор случайных чисел произвел бы последовательность менее случайную, чем исследуемая, для типа неслучайности, проверяемого тестом. Если P-value для теста равно 1, то последовательность абсолютно случайна. P-value, равное 0, указывает, что последовательность абсолютно неслучайна. Для теста следует выбрать уровень значимости . Если значение P-value больше или равно α, то принимается нулевая гипотеза, т. е. последовательность кажется случайной. Если значение P-value меньше α, то нулевая гипотеза отклоняется, т. е. последовательность кажется неслучайной. Параметр α обозначает вероятность ошибки 1-го рода. Как правило, α выбирается в интервале [0.001, 0.01].
Значение, равное 0.001. говорит о том, что из 1000 случайных последовательностей не прошла бы тест лишь одна. При P-value ≥ 0.001 последовательность рассматривается как случайная с доверительностью 99.9%. При P-value < 0.001 последовательность рассматривается как неслучайная с доверительностью 99.9%.
Значение α равное 0.01, говорит о том, что из 100 случайных последовательностей не прошла бы тест лишь одна. При P-value ≥ 0.01 последовательность, рассматривается как случайная с доверительностью 99%. При P-value < 0.01 последовательность рассматривается как неслучайная с доверительностью 99%.
По отношению к исследуемым последовательностям можно сделать следующие предположения. 1. Равномерность. В любой точке при генерации последовательности случайных или псевдослучайных битов 0 и 1 равновероятны и вероятности их появления равны 1/2. Ожидаемое число нулей (или единиц) равно n/2, где n - длина последовательности. 2. Масштабируемость. Любой тест, применимый к последовательности, может также применяться к произвольной подпоследовательности. Если последовательность случайна, то любая ее подпоследовательность должна также быть случайна. Следовательно, любая подпоследовательность должна пройти все тесты на случайность. 3. Полнота. Поведение генератора ПСП связано с начальным заполнением, поэтому неверно делать заключение о качестве генератора, основываясь на результатах анализа последовательности при каком-то одном начальном заполнении. Аналогично неверно делать заключение о генераторе случайных чисел, основываясь только на результатах анализа одного произведенного им фрагмента последовательности. Итак, оценка статистических испытаний основана на проверке гипотезы о случайности исследуемой последовательности нулей и единиц. Пошаговый процесс, позволяющий оценить конкретную двоичную последовательность (рис. 2): Рисунок 2 - Процесс оценки последовательности
2. ПОШАГОВОЕ ОПИСАНИЕ АЛГОРИТМОВ 2.1.Универсальный статический тест Маурера на сжимаемость двоичной последовательности.
1 шаг. Инициализация начальных параметров.
1.1 Исходная двоичная последовательность , (1)
где - длина битовой последовательности
Пример: ε = 01011010011101010111, n = 20.
1.2 Выбор блоков исходной последовательности
L- длина каждого блока.
L = 2
1.3 Выбор блоков инициализирующей последовательности Q-число блоков инициализирующей последовательности.
Q = 4
2 шаг. Разбиение исходной последовательности на блоки.
Разобьём двоичную последовательность на 2 сегмента: инициализирующий и тестовый. , (2)
где - инициализирующий сегмент; - тестовый сегмент.
Первый состоит из Q блоков по L бит, второй- из K = n/L - Q = 20/2 - 4 = 6 блоков по L бит. Лишние биты отбрасываем.
Инициализирующий сегмент Тестовый сегмент Лишние биты
Q по L бит K по L бит |L-бит| L-бит|L-бит|...|L-бит|L-бит| L-бит|L-бит|L-бит|...| L-бит|
n бит
Q блоков K блоков Рисунок 3 - Представление исходной последовательности
Пример: Инициализирующий сегмент 01011010, тестовый сегмент 011101010111.
Все L- битные блоки занесены в таблицу:
Таблица 4 - Результаты разбиения исходной последовательности БлокТипСодержание1
Инициализирующий
сегмент012013104105
Тестовый сегмент016117018019011011
3 шаг. Создание таблицы значений Т.
Инициализирующий сегмент используется для создания таблицы Т. , (3)
где ;-номер состояния двухбитного блока
- десятичное представление i-го L-го блока. Пример: Так как в инициализирующем сегменте 4 блока, то составим таблицу значений Т:
Таблица 5 - Таблица значений Т
Возможные L- битовые значения00(заносится в T0)01(заносится в T1)10(заносится в T2)11(заносится в T3)Инициализация 0 2 4 0 4 шаг. Вычисление тестового блока. Вычисление сумм логарифмов от длин промежутков между повторными появлениями мулътиграмм заданной длины.
Проверяем каждый из K блоков и определяем расстояние в блоках от последнего появления данного i-го блока, т.е. , одновременно обновляя таблицу: . Добавляем расчетное расстояние между перевозникновениями к накоплению log2 суммы всех различий, обнаруженных в K блоках (т.е. sum = sum + log2(i - Tj)).
Пример: Блоку 5 (первый тестовый блок) соответствует содержимое "01" согласно таблицы (т.e. T1), и sum=log2(5-2) = 1.584962501. Для блока 6: Блоку 6 соответствует содержимое "11" согласно таблицы (т.e., T3), и sum = 1.584962501 + log2(6-0) = 1.584962501 + 2.584962501 = 4.169925002. Для блока 7: Блоку 7 соответствует содержимое "01" согласно таблицы (т.e., T1), и sum = 4.169925002 + log2(7-5) = 4.169925002 + 1 = 5.169925002. Для блока 8: Блоку 8 соответствует содержимое "01" согласно таблицы (т.e., T1), и sum = 5.169925002 + log2(8-7) = 5.169925002 + 0 = 5.169925002. Для блока 9: Блоку 9 соответствует содержимое "01" согласно таблицы (т.e., T1), и sum = 5.169925002 + log2(9-8) = 5.169925002 + 0 = 5.169925002. Для блока 10: Блоку 10 соответствует содержимое "11" согласно таблицы (т.e., T3), и sum = 5.169925002 + log2(10-6) = 5.169925002 + 2 = 7.169925002. Конечным результатом данного шага является .
5 шаг. Вычисление статистики для тестового блока
Тестовая статистика определяется с помощью соотношения: , (4)
где - десятичное представление i-го L-го блока.
Т.е. - сумма log2 расстояний между соответствием L-bit шаблонов.
Пример: .
6 шаг. Вычисление P-value.
Тестовая статистика использует вычисление P-value, которое констатирует силу доказательства против нулевой гипотезы. Для теста следует выбрать уровень значимости α. Если значение P-value больше или равно α, то принимается нулевая гипотеза, т.е. последовательность является случайной. Если значение P-value меньше α, то нулевая гипотеза отклоняется, т.е. последовательность не является случайной. Для нашего примера α =0.01.
,(5)
где - математическое ожидание (теоритически ожидаемое значение вычисленной статистики для данной L-битовой последовательности);
- среднеквадратическое отклонение (показатель рассеивания значений случайной величины относительно её математического ожидания), где - дисперсия (отклонение от математического ожидания). Функция erfc(x)- дополнительная функция ошибок:
, (6)
где erf(x)- функция ошибок:
(7)
Рисунок 4- График функции ошибок
Рисунок 5- График дополнительной функции ошибок
;
Значения и берутся из таблицы предварительно вычисленных значений: Таблица 6 -Предварительно вычисленные значения
L10.73264950.69021.53743831.33832.40160681.90143.31122472.35854.25342662.70565.21770522.95476.19625073.12587.18366563.23898.17642483.311109.17232433.3561110.1700323.3841211.1687653.4011312.1680703.4101413.1676933.4161514.1674883.4191615.1673793.421
Пример: .
7 шаг. Конечный результат работы алгоритма.
Если вычисленное значение P-value <0.01, то последовательность является неслучайной. Иначе последовательность - случайна.
Полученное нами значение P-value= 0.767189, делаем вывод о том, что последовательность случайна.
Т.к. наша последовательность случайна, можно сделать вывод о том, что её нельзя значительно сжать без потерь.
Рекомендации по начальным параметрам.
Тест Маурера требует, чтобы длина битовой последовательности была равна . Она разделяется на 2 сегмента, состоящих из L-битных блоков, где L должно находиться в пределах 6 ≤ L ≤ 16. Первый сегмент состоит из Q инициализирующих блоков, где Q должно удовлетворять условию . Второй сегмент состоит из K тестовых блоков, где . Значения L, Q и n должны быть следующими:
Таблица 7 -Рекомендации по входным параметрам.
nLQ≥ 387,840 6640≥ 904,96071280≥ 2,068,480 82560≥ 4,654,080 95120≥ 1,342,4001010240≥ 22,753,280 1120480≥ 49,643,520 1240960≥ 107,560,960 1381920≥ 231,669,760 14163840≥ 496,435,200 15327680≥1,059,061,76016655360
2.2 Частотный тест (Frequency Test). Цель теста - проверить равномерность появления 0 и 1 в исходной последовательности.
1 шаг. Инициализация начальных параметров.
Исходная двоичная последовательность , (1)
где - длина битовой последовательности
Пример: ε = 1011010101, n = 10.
2 шаг. Нахождение суммы .
Нули и единицы входной последовательности преобразовываем в значения -1 и +1 и находим их сумму.
, (2)
где Пример: 3 шаг. Вычисление тестовой статистики.
- абсолютное значение суммы Xi в исходной последовательности разделенное на корень из длины этой последовательности.
(3)
Пример: 4 шаг. Вычисление P-value.
, (4)
Где - дополнительная функция ошибок
Пример: 5 шаг. Конечный результат работы алгоритма.
Если вычисленное значение P-value <0.01, то последовательность является неслучайной. Иначе последовательность - случайна.
Полученное нами значение P-value= 0.527089, делаем вывод о том, что последовательность случайна.
Рекомендации по входным параметрам.
Рекомендуется, чтобы каждая последовательность, которая будет протестирована, состояла минимум из1000 битов (то есть, n ≥ 1000).
2.3 Частотный тест в подпоследовательностях (Frequency Test within a Block). Цель теста - проверить равномерность появления 0 и 1 в последовательностях.
1 шаг. Инициализация начальных параметров.
1.1 Исходная двоичная последовательность , (1)
где - длина битовой последовательности
Пример: ε = 1011010101, n = 10.
1.2 Выбор блока исходной последовательности
M- длина каждого блока.
M = 3
2 шаг. Разбиение исходной последовательности
Разобьём входную последовательность на неперекрывающихся блоков. Ненужные биты отбрасываем.
Пример: , т.е. будут получены 3 блока, состоящие из 011,001 и 101.
3 шаг. Определение доли единиц.
Определим долю единиц в каждом M- битном блоке исходной последовательности:
, (2)
где Пример: , ,.
4 шаг. Вычисляем статистику - мера того, насколько хорошо наблюдается доля единиц в рамках данного М-го блока.
Формула для статистики: (3)
Пример: 5 шаг. Вычисление P-value
, (4)
где ,где , - гамма-функция.
Пример: 6 шаг. Конечный результат работы алгоритма.
Если вычисленное значение P-value <0.01, то последовательность является неслучайной. Иначе последовательность - случайна.
Полученное нами значение P-value= 0.801252, делаем вывод о том, что последовательность случайна.
Отметим, что малые значения P-value (<0,01) указывают на большое отклонение от равного количества единиц и нулей, по крайней мере в одном из блоков.
Рекомендации по входным параметрам.
Рекомендуется, чтобы каждая последовательность, которая будет протестирована, состояла минимум из1000 битов (то есть, n ≥ 1000).Заметим, . Блок размера M должен быть и .
2.4 Тест "дырок" (Runs Test)
Цель теста - проверить равномерность распределения 0 и 1 в исследуемой подпоследовательности на основе анализа количества появления "блоков"- подпоследовательностей, состоящих из одних единиц, и "дырок"- подпоследовательностей, состоящих из одних нулей.
1 шаг. Инициализация начальных параметров.
1.1 Исходная двоичная последовательность , (1)
где - длина битовой последовательности
Пример: ε = 1001101011, n = 10.
2 шаг. Вычисление предтестовой статистики.
Предтестовая статистика π - доля единиц в рассматриваемой последовательности.
(2)
Если ,то тест считается непройденным.
Пример: ; , значит тест пройден, переходим к следующему пункту.
3 шаг. Вычисление статистики Vn(obs).
Vn(obs) - количество блоков и дырок.
, (3)
где r(k)=0 ,если εk=εk+1 и r(k)=1 ,если εk≠εk+1.
Пример: V10(obs)=(1+0+1+0+1+1+1+1+0)+1=7.
4 шаг. Вычисление P-value.
(4)
Пример: 5 шаг. Конечный результат работы алгоритма.
Если вычисленное значение P-value <0.01, то последовательность является неслучайной. Иначе последовательность - случайна.
Полученное нами значение P-value= 0. 147232, делаем вывод о том, что последовательность случайна.
Отметим, что большие значения Vn(obs) указывают на большое отклонение от равного количества единиц и нулей.
Рекомендации по входным параметрам.
Рекомендуется, чтобы каждая последовательность, которая будет протестирована, состояла минимум из1000 битов (то есть, n ≥ 1000).
2.5 Тест "блоков" в подпоследовательностях (Test for the Longest Run of Ones in a Block)
Цель теста - проверить равномерность распределения 0 и 1 в исследуемой подпоследовательности на основе анализа количества появления "блоков" подпоследовательностей.
1 шаг. Инициализация начальных параметров.
1.1 Исходная двоичная последовательность , (1)
где - длина битовой последовательности
1.2 Выбор блока исходной последовательности
M- длина каждого блока. Таблица 8 -Таблица соотношений между длиной блока и количеством блоков
Minimum nM12886272128750,00010000
1.3 Выбор числа блоков
N -число блоков, выбранное в соответствии с значением M.
2 шаг. Определение значения νi
Разделяем последовательность на M- битные блоки. Значения частот νi приведены в таблице, где каждая ячейка содержит число серий из единиц заданной длины:
Таблица 9 -Таблица значений частот
νiM=8M=128M=10000ν0ν12511ν23612ν3713ν4814ν515ν63 шаг. Вычисление статистики - мера того, насколько хорошо наблюдается доля единиц в рамках данного М-го блока.
Формула для статистики: , (2)
Где значения K,N и πi выбираются из таблиц: Таблица 10 - Таблица соотношений между M ,N и K
MKN831612854910000675
Таблица 11 -Значения πi для раздичных M и νi
νiM=8M=128M=10000ν00.21480.11740.0882ν10.36720.24300.2092ν20.23050.24930.2483ν30.18750.17520.1933ν40.10270.1208ν50.11240.0675ν60.07274 шаг. Вычисление P-value.
(3)
5 шаг. Если вычисленное значение P-value <0.01, то последовательность является неслучайной. Иначе последовательность - случайна.
Рекомендации по входным параметрам.
Рекомендуется, чтобы каждая последовательность, которая будет проходить тест, состояла из минимума бит.
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ТЕСТОВ НИСТ
Программная реализация тестов осуществлена на языке C++. После компелляции и запуска программы на экране появляется диалоговое окно "Nist Statistical Test Suite", где предлагается выбрать тип тестируемого генератора или выбрать файл, в котором находится исходная последовательность. Затем необходимо определиться с режимом: "Regenerate" или "Reuse". При выборе первого режима последовательности будут генерироваться каждый раз заново, при выборе второго ̶ несколько раз будет тестироваться одна и та же последовательность. Также имеется возможность сохранения результатов теста в отдельный файл. Для этого необходимо выбрать режим "Save Source Data". После выполнения всех данных операций нужно нажать на кнопку "Далее". На рисунке 6 приведен вид диалогового окна инициализации начальных параметров.
Рисунок 6-Диалоговое окно инициализации начальных параметров
После нажатия кнопки "Далее" появится еще одно диалоговое окно, где будет предложено выбрать исполняемые тесты, а также ввести количество тестируемых последовательностей и их длину. На рисунке 7 представлен вид данного диалогового окна.
Рисунок 7 - Диалоговое окно выбора теста
Для выполнения всех тестов необходимо нажать на кнопку "Click here". По окончании ввода параметров необходимо нажать на кнопку "Далее".
На рисунке 8 приведен вид диалогового окна, в котором проверяются выбранные ранее начальные параметры, а именно тестируемый генератор, количество последовательностей, длина каждой из них, вид теста и их количество в случае, если было выбрано более одного.
Рисунок 8 - Диалоговое окно проверки инициализации начальных параметров
Рисунок 9 - Диалоговое окно процесса тестирования
На рисунках 10 и 11 приведен вид диалогового окна, в котором отображаются результаты тестирования Рисунок 10 - Диалоговое окно отображающее результаты частотно-блочного теста (Block Frequency)
Рисунок 11 - Диалоговое окно отображающее результаты теста кумулятивных сумм (Cumulative sums test)
ЗАКЛЮЧЕНИЕ
В ходе выполнения курсовой работы были разработаны алгоритмы статических тестов на определение случайности (неслучайности) исходной последовательности. В каждом из приведённых алгоритмов было вычислено значение P-value, которое является критерием для принятия решения о случайности (неслучайности) последовательности. Разработанные алгоритмы обладают понятностью, лёгкостью и простотой реализации, универсальностью, несложностью объяснения и т.д.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Andrew Rukhin, Juan Soto, James Nechvatal, Miles Smid -A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.2008г.-131с.
2.Иванов М.А., Чугунков И.В. -Теория, применение и оценка качества генераторов псевдослучайных последовательностей.2003г.
3. Wiki-books. Режим доступа: http://ru.wikipedia.org/wiki/NIST_STS.
3
Документ
Категория
Рефераты
Просмотров
403
Размер файла
462 Кб
Теги
kursovaya, itog
1/--страниц
Пожаловаться на содержимое документа