Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей (1025663), страница 22
Текст из файла (страница 22)
Пример выдержки изтакого файла приведен на рис. 4.1.Столбец STATISTICAL TEST содержит наименование статистическоготеста. В столбце P-VALUE указывается достигаемый уровень значимости,отражающий равномерность распределения р-значений, полученных в результате тестирования, а в столбце PROPORTION —относительное количество последовательностей, прошедших тест. В случае, если эти значениявыходят за пределы ожидаемых для случайных последовательностей, справа от значения указывается символ «*».
Остальные столбцы содержат количество р-значений, попавших в интервалы С1-С10, и могут использоваться при дальнейшем исследовании их распределения.4.3..МЕТОДИКАЧЕСКОГОПРОВЕДЕНИЯ И РЕЗУЛЬТАТЫСТАТИСТИТЕСТИРОВАНИЯСтатистическое тестирование выходных последовательностей разработанных генераторов направлено на поиск параметров (локальной функциисвязи и-, для генераторов на основе неоднородных клеточных автоматов,,выбора окрестности), обеспечивающих хорошие статистические свойства.Процесс тестирования является достаточно требовательным к вычислительным, ресурсам: выполнение полного набора тестов NIST для 1000'выходных последовательностей длины 1024 000 бит каждая (что соответствует исследованию одного генератора) на персональном компьютере спроцессором AMD Athlon 64 Х2 3800+ и 3 Гб оперативной памяти занимаетоколо 8 часов.
Для уменьшения общего времени, необходимого на тестирование, мы используем итеративную организацию процесса, включающуюдве фазы: предварительную и основную, различающиеся наборами тестови длиной исследуемых последовательностей (см. табл. 6).В предварительной фазе проводится сокращенный набор тестов длявыходных последовательностей небольшой длины (1024 бита каждая). Этопозволяет на ранней стадии исключить из рассмотрения генераторы, обладающие существенными статистическими недостатками.RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCESgenerator i s <data.bin>CIC2C3C4C5C6C7C8C9 CIOP-VALUEPROPORTION STATISTICAL TEST7124839721213471017586231096367791461120892812121581617768108712581571047148748118111512141724218171001313139911511973942131110128801011751393Frequency12 14 11 0.574903 1.00006 4 4 0.000883 0.9900BlockFrequency •13 9 19 0.013569 1.0000CumulativeSums14 13 11 0.6786861.0000CumulativeSums13 8 18 0.0351741.0000Runs1.00007 14 9 0.249284LongestRun29 8 9 0.000000 * 0.9800Rank20 5 10 0.0027581.0000FFT9 3 5 0.000043 * 0.9800NonOverlappingTemplate0.97008 8 3 0.001757NonOverlappingTemplate1 1 0 0.000000 * 0.8700 * NonOverlappingTemplate0.9700NonOverlappingTemplate9 4 18 0.02054814 8 12 0.1916870.9400 * NonOverlappingTemplate2 1 0 0.000000 * 0.8500 * NonOverlappingTemplateРис.
4.1. Пример выдержки из файла отчета о тестировании генератора псевдослучайных последовательностей, полученного при помощи набора тестов NIST-144-Таблица 6.Параметры предварительной и основной фаз статистическоготестирования генераторов псевдослучайных последовательностей,-тПараметрПредварит.,фазаОбъект тестированияКоличество генераторов каждого типа10 000Количество последовательностей для1000каждого генератораДлина каждой последовательности, бит1024Основная1фаза100 / 10 / X110 / 100 / 100011024000Набор тестовFrequency (Monobit) TestFrequency Test within a BlockRuns TestTest for the Longest Run of Ones in a BlockBinary Matrix Rank TestDiscrete Fourier Transform (Spectral) TestNon-overlapping Template Matching TestOverlapping Template Matching TestMaurer's Universal Statistical TestLinear Complexity TestSerial TestApproximate Entropy TestCumulative Sums (Cusum) TestRandom Excursions TestRandom Excursions Variant TestПараметры тестовFrequency Test within a Block: длинаподпоследовательности MNon-overlapping Template Matching Test:длина шаблона mOverlapping Template Matching Test:длина шаблона mLinear Complexity Test: размер блока MSerial Test: длина шаблона mApproximate Entropy Test: длинашаблона m////////////////444•I2010 240н/д9н/дн/дн/дн/д9Указаны значения для первой / второй / третьей итерации основной фазы10001610-145В основной фазе выполняется полный набор тестов.
Длина последовательностей в этом случае определяется рекомендациями [63] по применению статистических тестов и составляет 1024 000 бит. Основная фазасостоит из трех итераций. На каждой итерации осуществляется исследование генераторов, показавших наилучшие характеристики (т. е. успешнопрошедших наибольшее количество тестов) на предыдущей итерации. Последняя—третья—итерация основной фазы выполняется до тех пор, покане будет обнаружен генератор, успешно проходящий все тесты.Тестированию подвергаются следующие типы генераторов:1) базовый генератор на основе классических двумерных клеточных автоматов (см.
раздел 3.2.1);2) базовый генератор на основе неоднородных клеточных автоматов (см.раздел 3.2.2);3) комбинированный генератор на основе классических двумерных клеточных автоматов (см. раздел 3.3);4) комбинированный генератор на основе неоднородных клеточных автоматов (см. раздел 3.3).Выбор параметров подлежащих тестированию генераторов описан вприложении П.5. Начальное состояние генератора для каждой последовательности определяется заполнением ячеек памяти регистра сдвига и формируется в соответствии приложением П.3.2. Выходные последовательности вырабатываются по алгоритмам, приведенным в разделах 3.2.4 (длябазовых генераторов) и 3.3.2 (для комбинированных генераторов).Для автоматизации изложенной в данном разделе методики былразработан программный комплекс, функционирующий совместно с программным комплексом Assess. Краткое описание разработанного программного комплекса приведено в приложении П.2.Результаты статистического тестирования приведены в табл.
7. Отсутствие генераторов, успешно прошедших первую итерацию основной фазытестирования, объясняется слишком малым объемом выборки (10 последовательностей) для каждого генератора: при выявлении любых статистических отклонений относительное количество последовательностей, проходящих тест, выходит за пределы доверительного интервала.-146-Таблица 7.Результаты статистического тестирования генераторов псевдослучайныхпоследовательностейВсегоПредварительная фазаБазовый генератор на основе ККлАБазовый генератор на основе НКлАКомбинированный генератор на основе ККлАКомбинированный генератор на основе НКлА10 00010 00010 00010 000Прошли тесты145915416 6666 250(14,6%)(15,4%)(66,7%)(62,5%)Основная фаза, итерация 1Базовый генератор на основе ККлА100Базовый генератор на основе НКлА100Комбинированный генератор на основе ККлА100Комбинированный генератор на основе НКлА1000000Основная фаза, итерация 2Базовый генератор на основе ККлАБазовый генератор на основе НКлАКомбинированный генератор на основе ККлАКомбинированный генератор на основе НКлА0 (0,0%)1 (10,0%)4 (40,0%)2 (20,0%)10101010Основная фаза, итерация 3Базовый генератор на основе ККлАН/ДБазовый генератор на основе НКлА4Комбинированный генератор на основе ККлА4Комбинированный генератор на основе НКлА4(0,0%)(0,0%)(0,0%)(0,0%)Н/Д0 (0,0%)2 (50,0%)1 (25,0%)-147Как видно из таблицы, наилучшими статистическими свойствами обладают выходные последовательности комбинированных генераторов наоснове классических двумерных клеточных автоматов..
Для комбинированных генераторов на основе неоднородных клеточных автоматов, также были найдены параметры, обеспечивающие высокое качество выходных последовательностей. Примеры таких параметров для комбинированных генераторов на основе классических и неоднородных клеточных автоматовtприведены в приложении И.61•'••.•'.Статистические свойства базовых генераторов являются неудовлетво-•рительными. Отметим,"что третья итерация основной1 фазы,тестированиядля базовых генераторов на. основе классических клеточных автоматов.'непроводилась ввиду плохих результатов, полученных: на: второй итерации-.44-ВЫВОДЫ:.,Статистические свойства, выходных последовательностей и; их «схо- .жесть» с истинно случайными последовательностями являются одним из;основных показателей качества генераторов.
Для*, исследования: статистических свойств был использованшабор специализированных тестов, разработанный и-реализованный-:Национальным,институтом стандартов:и;тех-нологии СЫШ. Набор включает в себя: 15 разновидностей проверок:и пред-:назначен для исследования выходных последовательностей^ криптографических генераторов, что соответствует наиболее жестким требованиям.Тестирование • было организовано в несколько этапов, что позволилосократить, временные затраты за счет, исключения на ранних стадиях израссмотрения генераторов, обладающих заведомо, неудовлетворительнымихарактеристиками.
Для автоматизации предложенного подхода был разработан; специализированныйшрограммный комплекс, функционирующийсовместно с реализацией статистических: тестов. NIST.Исследование показало^ что выходные последовательности базовых генераторов обладают недостаточно хорошими статистическими свойствамии потому не могут быть рекомендованы к применению.Тем не менее, для комбинированных генераторов на основе как классических двумерных, так и неоднородных клеточных автоматов в результате-148тестирования были получены параметры, при которых их выходные последовательности успешно проходят все статистические тесты, т. е.
при которых генераторы полностью удовлетворяют требованиям к статистическимсвойствам выходных последовательностей.-149-ГЛАВА 5ВЫСОКОСКОРОСТНАЯ АППАРАТНАЯРЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ5.1.ГЕНЕРАТОРОВОБЩИЕ СВЕДЕНИЯПерспективным подходом к построению аппаратной реализации сложных цифровых систем (каковыми, в том числе, являются генераторы псевдослучайных последовательностей на основе клеточных автоматов), является использование программируемых логических интегральных схем(ПЛИС, programmable logic device, PLD).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
