Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 20
Текст из файла (страница 20)
ВыводыВ этой главе были рассмотрены два разработанных автором генератора псевдослучайных последовательностей на основе клеточных автоматов:базовый и комбинированный. В составе генераторов могут использоватьсякак классические, так и неоднородные клеточные автоматы. Параметрыавтоматов выбираются с учетом их свойств, исследованных в главе 2. Заданный период выходной последовательности обеспечивается при помощирегистра сдвига, выход которого «подмешивается» к состоянию клеточныхавтоматов.К основным достоинствам базового генератора относятся высокоебыстродействие (выработка 256 бит выхода за один такт работы), контролируемый период выходной последовательности и эффективность аппаратной реализации.
Тем не менее, выходные последовательности базовыхгенераторов являются легко предсказуемыми и, как будет показано в главе 4, обладают недостаточно хорошими статистическими свойствами, чтоограничивает их применение.Комбинированные генераторы позволяют устранить названные недостатки. Они построены на основе двух базовых генераторов и обеспечивают как непредсказуемость выходной последовательности, так и хорошиестатистические свойства.
Ценой улучшений является вдвое более низкоебыстродействие программной и повышенные требования к ресурсам аппаратной реализации.-131-ГЛАВА 4ИССЛЕДОВАНИЕ СТАТИСТИЧЕСКИХ СВОЙСТВВЫХОДНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙГЕНЕРАТОРОВОдним из критериев качества генераторов псевдослучайных чисел является схожесть выходной последовательности такого генератора с равномерно распределенной истинно случайной последовательностью.
Для оценки степени схожести используются специализированные тесты, каждый изкоторых направлен на выявление определенных шаблонов или отклоненийот ожидаемых для истинно случайных последовательностей результатов.Заметим, что ни один статистический тест не способен однозначно классифицировать последовательность как полностью соответствующую истиннослучайной; в то же время, отрицательные результаты говорят о ее явнонеслучайном характере.В этой главе мы исследуем статистические свойства выходных последовательностей разработанных генераторов на основе клеточных автоматов. В качестве инструмента исследования используется набор статистических тестов [63], разработанный и реализованный американским Национальным институтом стандартов и технологии США (National Institute ofStandards and Technology, NIST).-1324.1.О Б Щ И Е СВЕДЕНИЯЦелью любого статистического тестирования является проверка т.
н.нулевой гипотезы Щ — определенного предположения о распределении вероятностей, лежащем в основе наблюдаемой выборки данных. При тестировании генераторов псевдослучайных последовательностей в качестве выборки выступает выходная последовательность, а в качестве нулевой гипотезы—предположение о том, что последовательность получена случайным образом, т.
е. что ее члены являются независимыми случайными величинами с равновероятным распределением. Нулевой гипотезе .Но противопоставляется альтернативная гипотеза На, согласно которой последовательность не является случайной. По результатам теста принимается либонулевая гипотеза, либо альтернативная (противоположная гипотеза, соответственно, отвергается).Для каждого теста выбирается соответствующая ему статистика —числовая функция от выборки данных. Значение статистики рассматривается как случайная величина, причем ее распределение, соответствующееистинности гипотезы Щ, известно a priori и может быть получено аналитическими методами или эмпирически.На основании значения статистики рассчитывается достигаемый уровень значимости, также называемый р-значением (p-value) или простор,—вероятность, с которой при условии истинности нулевой гипотезы могла быреализоваться наблюдаемая выборка.
Случайная величина р имеет равномерное распределение. Фактически вычисление достигаемого уровня значимости позволяет привести значение статистики к шкале вероятности.Маловероятным значениям статистики в этом случае соответствуют значения р, близкие к нулю.Для принятия решения об истинности нулевой гипотезы Яо (или альтернативной На) заранее (до проведения тестирования) выбирается уровень значимости а — достаточно малое значение вероятности события, прикотором оно уже может считаться неслучайным.
Обычно это значение выбирается из диапазона [0,001; 0,05]. Гипотеза Щ принимается, если р-значение равно или превосходит а; в противном случае принимается На.-133Поскольку статистическое тестирование носит вероятностный характер, в результате теста может приниматься ложная гипотеза (см. табл. 5).Таблица 5.Возможные варианты принятия решений по результатам тестированияПоследовательностьявляется случайнойПоследовательностьне является случайнойПринята ЛоПринята НаНет ошибкиОшибка 1-го родаОшибка 2-го родаНет ошибкиЕсли нулевая гипотеза Щ истинна, но по результатам теста она былаотвергнута (т.е.
принята альтернативная г и п о т е з а ^ ) , то такое решениеназывается ошибкой 1-го рода. Если же гипотеза Щ принимается в то время, как она является ложной, то говорят об ошибке 2-го рода.Вероятность ошибки 1-го рода численно равна уровню значимости теста а. В случае тестирования псевдослучайных последовательностей этоозначает, что при а = 0,01 следует ожидать, что в одном случае из ста «хорошая» последовательность, обладающая соответствующими истинно случайной равномерно распределенной последовательности свойствами, будетпризнана неслучайной.Чрезмерное уменьшение уровня значимости (вероятности ошибки 1-города) а может привести к увеличению вероятности ошибки второго рода/3,т. е.
вероятности принять нулевую гипотезу, когда на самом деле она не верна. Таким образом, выбор уровня значимости определяется компромиссоммежду вероятностями ошибок 1-го и 2-го рода. На практике фиксируютзначение а, а затем подбирают параметры тестов, позволяющие минимизировать р.-1344.1.1. Ф О Р М А Л Ь Н О Е ОПИСАНИЕ ПРОЦЕССА С Т А Т И С Т И Ч Е С К О Г О Т Е СТИРОВАНИЯПри статистическом тестировании последовательность длины п надконечным дискретным множеством П.ё = е ь е 2 , • • • , £п,£г € Q, 1 < г < прассматривается как простая (т.
е. однородная, независимая и случайная)пвыборка объема п из генеральной совокупности О (ё G О ; в случае двоичных последовательностей JQ = Z2 = {0,1}).Формально процесс статистического тестирования псевдослучайныхпоследовательностей может быть описан следующим образом:1) формулируется нулевая гипотеза Щ — последовательность ё являетсяистинно случайной равномерно распределенной на О. — и противоположная ей альтернативная гипотеза На;2) фиксируется уровень значимости а;3) задается статистика Г : С1п —> Ж;4) вычисляется значение Т(ё) статистики Т для последовательности ё;5) вычисляется достигаемый уровень значимости р = р(Т(ё)) для полученного значения статистики;6) если р ^ а, принимается нулевая гипотеза Щ и последовательностьпризнается случайной; в противном случае принимается альтернативная гипотеза На и последовательность признается неслучайной.4.2.
Н А Б О Р С Т А Т И С Т И Ч Е С К И Х Т Е С Т О В NISTНабор статистических тестов NIST [63] разработан американским Национальным институтом стандартов и технологии и предназначен дляоценки статистических свойств двоичных последовательностей. Посколькунабор рассчитан на применение в области криптографии, в нем предъявляются наиболее жесткие требования.В состав набора входят 15 разновидностей тестов, каждая из которыхнаправлена выявление отклонений определенных характеристик от ожидаемых для истинно случайной и равномерно распределенной последова--135тельности. Выбор статистик основывается на следующих предположениях:- равновероятность: каждый символ последовательности принимаетзначение «единица» или «ноль» независимо от других символов с вероятностью 1/2; математическое ожидание количества нулей или единицв последовательности длины п равно тг/2;- масштабируемость: любой тест, применимый к последовательности,также применим и к произвольной ее подпоследовательности (этосвойство основывается на воспроизводимости случайных последовательностей при прореживании);- полнота: свойства выходных последовательностей генератора (как истинно случайного — физического, так и псевдослучайного — детерминированного) не зависят от выбора начальных значений и определяются только параметрами генератора; тем не менее, отметим, что делатьвывод о качестве генератора на основании тестирования единственной последовательности или небольшого их числа некорректно в силувероятностного характера тестов.4.2.1.
К Р А Т К О Е О П И С А Н И Е С Т А Т И С Т И Ч Е С К И Х Т Е С Т О ВМы приводим краткое описание каждой разновидности тестов, входящих в набор NIST. Более подробно тесты рассматриваются в приложении П.1, а исчерпывающее описание на английском языке приведено в [63].Под термином «случайная последовательность» в описании тестов понимается любая двоичная последовательность, обладающую характернымидля истинно случайной равномерно распределенной на множестве {0,1}последовательности свойствами.Тест считается пройденным (т. е. по результатам теста принимаетсягипотеза Щ о том, что исследуемая последовательность является случайной), если достигаемый уровень значимости р превосходит или равен уровню значимости а, который в тестах NIST имеет фиксированное значениеа = 0,01.Frequency (Monobit) Test.Объектом исследования является соотношение количества единиц инулей в исследуемой последовательности ё.
Для случайной последователь--136ности ожидается, что число единиц и нулей будет приблизительно одинаковым.Для получения достоверных результатов необходимо, чтобы длина исследуемой последовательности была не менее 100 бит.Frequency Test within a Block.Объектом исследования является соотношение количества единиц инулей в подпоследовательностях длины М исследуемой последовательности е.
Для истинно случайной последовательности ожидается, что числоединиц блоке будет близко к величине М/2.Рекомендуется использовать последовательности ё длиной не менее100 бит. Длина подпоследовательности должна выбираться таким образом, чтобы выполнялись соотношения М ^ 20, М > 0,01п и N < 100, гдеп —длина исследуемой последовательности, М —длина подпоследовательности, N = \п/М\ — количество подпоследовательностей.Runs Test.Объектом исследования является число непрерывных серий в ё.
Подсерией длины к понимается последовательность из к одинаковых (нулевыхили единичных) членов, ограниченная слева и справа членами с противоположными значениями. Целью теста является определение отклоненийколичества серий различной длины от ожидаемой для случайной последовательности величины. В частности, тест позволяет выявить слишкомчастую или слишком редкую смену значений в последовательности.Длина исследуемой последовательности ё должна быть не менее 100бит (п > 100).Test for the Longest Run of Ones in a Block.Объектом исследования являются единичные серии наибольшей длины в подпоследовательностях длины М последовательности ё.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
