rijndael (Курсовая - Построение и исследование криптосистемы на основе Rijndael), страница 6

Проверка серий. Неравномерность распределения m-битных слов.13. Проверка аппроксимированной энтропии. Неравномерность распределения m-битных слов. Малые значения означают высокую повторяемость.14. Проверка кумулятивных сумм. Слишком много нулей или единиц вначале последовательности.15. Проверка случайных отклонений. Отклонение от распределения числапоявлений подпоследовательностей определенного вида.16. Разновидность проверки случайных отклонений.

Отклонение от распределения числа появлений подпоследовательностей определенного вида.264.3Описание каждого теста и их параметры.Длина тестируемой последовательности во всех тестах равна n = 220 бит.Число экспериментов равно 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).Внимание этого теста сосредоточено на появлении матриц различных рангов.Матрица интерпретируется как часть последовательности. Цель этого теста27состоит в том, чтобы проверить линейную зависимость среди фиксированныхподстрок исходной последовательности.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).Внимание этого теста сосредоточено на числе кумулятивно отличных образцов (слов) в последовательности. Цель теста состоит в том, чтобы опреде-28лить, как сильно тестируемая последовательность может быть сжата.

Считается, что последовательность является неслучайной, если она может бытьзначительно сжата. Случайная последовательность будет иметь характерноечисло отличных образцов.4.3.11 Проверка линейной сложности (Linear-Complexity).Внимание этого теста сосредоточено на длине линейного регистра сдвигас обратной связью (LFSR). Цель этого теста состоит в том, чтобы определить, действительно ли последовательность достаточно сложна, чтобы бытьслучайной.

Случайные последовательности характеризуются более длиннымрегистром сдвига. Регистр сдвига, который является слишком коротким, считается неслучайным.Тестируемая последовательность разбивается на подпоследовательностидлины M , для которой и вычисляется длина регистра сдвига.В данном тесте значение параметра равно M = 500.4.3.12 Проверка серий (Serial).Внимание этого теста сосредоточено на частоте всех возможных пересекающихся m-битных образцов сквозь полную последовательность.

Цель этоготеста состоит в том, чтобы определить, является ли число возникновений 2mm-битных пересекающихся образцов приблизительно тем же самым, какоеожидается для случайной последовательности. Случайные последовательности имеют однородность; то есть каждый m-битный образец имеет ту жесамую возможность появления как и любой другой. Обратим внимание, чтодля m = 1, этот тест эквивалентен Частотному (Монобитному) тесту.В данном тесте значение параметра равно m = 5.4.3.13 Проверка аппроксимированной энтропии (Apen).Внимание этого теста сосредоточено на тех же объектах, что и в тесте Проверки серий.

Цель теста состоит в том, чтобы сравнить частоту пересекающихся блоков двух смежных длин (m и m + 1) по отношению к ожидаемомурезультату для случайной последовательности.В данном тесте значение параметра равно m = 5.4.3.14 Проверка кумулятивных сумм (Cusum).Внимание этого теста сосредоточено на максимальном отклонении суммыэлементов нормированной последовательности от нуля. Цель теста состоитв том, чтобы определить, является ли совокупная сумма частичных последовательностей, встречающихся в тестируемой последовательности слишкомбольшой или слишком маленькой относительно ожидаемого поведения совокупной суммы для случайных последовательностей.

Эта совокупная суммаможет рассматриваться как случайное хождение (на шаг вперед или назад).Для случайной последовательности, отклонение случайного хождения должны быть около нуля. Для некоторых типов неслучайных последовательностей, отклонение этого случайного хождения от нуля будет большим числом.294.3.15 Проверка случайных отклонений (Random-Excursion).Внимание этого теста сосредоточено на числе циклов, имеющих точно Kпосещений в совокупной сумме случайного хождения. Совокупная суммаслучайного хождения получена из частичных сумм после замены 0 и 1 висходной последовательности на −1 и +1.

Цикл случайного хождения состоит из последовательности шагов длины единицы, которая начинается изаканчивается в одном и том же состоянии. Цель этого теста состоит в том,чтобы определить, отклоняется ли число посещений отдельного состояния впределах цикла, от того, которого можно было бы ожидать для случайнойпоследовательности.4.3.16 Проверка случайных отклонений (вариант)(Random-Excursion-V).Внимание этого теста сосредоточено на общем количестве посещений отдельных состояния в совокупной сумме случайного хождения.

Цель этоготеста состоит в том, чтобы обнаружить отклонения от ожидаемого числа посещений различных состояний в случайном хождении. Данный тест являетсярасширением предыдущего.4.4Результат тестирования генератора.Ниже приведено содержимое файла результата тестирования генератора.-------------------------------------------------------------------------------C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST-------------------------------------------------------------------------------103 87 84 98 100 102 117 103 113 93 0.3855430.9920Frequency101 95 89 115 93 95 107 102 109 94 0.7238040.9900Block-Frequency91 99 91 94 96 104 105 95 116 109 0.7217770.9910Cusum102 90 78 102 102 94 99 120 114 99 0.1969200.9900Cusum82 99 91 86 112 122 106 112 95 95 0.1025260.9930Runs94 101 97 101 101 92 100 104 108 102 0.9920840.9980Long-Run85 103 116 116 112 83 84 108 107 86 0.0422550.9960Rank97 124 101 116 102 104 94 88 80 94 0.0971590.9970FFT98 107 103 92 94 82 98 106 101 119 0.4484240.9870Aperiodic-Template95 89 108 94 106 100 96 104 84 124 0.2454900.9890Aperiodic-Template110 84 94 96 102 104 93 84 120 113 0.1617030.9890Aperiodic-Template112 80 99 92 110 108 94 97 101 107 0.4673220.9880Aperiodic-Template93 125 93 106 107 104 82 105 84 101 0.1120470.9920Aperiodic-Template101 104 106 100 102 103 78 92 108 106 0.6225460.9870Aperiodic-Template102 95 113 106 85 102 99 110 100 88 0.6287900.9880Aperiodic-Template112 91 98 97 85 99 111 99 98 110 0.6475300.9860Aperiodic-Template108 108 102 89 119 97 80 91 104 102 0.2596160.9850Aperiodic-Template119 114 85 96 86 123 89 103 94 91 0.0388180.9880Aperiodic-Template91 96 93 105 113 125 92 93 90 102 0.2236480.9880Aperiodic-Template106 92 92 94 110 93 119 102 100 92 0.5564600.9920Aperiodic-Template125 80 86 107 102 87 107 110 96 100 0.0652300.9860Aperiodic-Template90 80 104 110 124 104 102 82 104 100 0.0776070.9880Aperiodic-Template118 94 103 90 122 107 89 92 101 84 0.1075120.9840Aperiodic-Template107 103 86 98 106 110 98 98 114 80 0.3521070.9890Aperiodic-Template89 113 98 100 108 106 87 95 107 97 0.6931420.9950Aperiodic-Template102 99 91 95 111 99 94 102 104 103 0.9650830.9910Aperiodic-Template102 117 89 112 94 102 95 91 102 96 0.6121470.9870Aperiodic-Template83 117 87 93 124 97 100 87 112 100 0.0496640.9910Aperiodic-Template100 97 116 94 93 98 90 104 113 95 0.6745430.9880Aperiodic-Template110 114 101 112 96 86 96 109 91 85 0.3070770.9850Aperiodic-Template96 97 91 98 108 106 91 95 111 107 0.8463380.9940Aperiodic-Template104 105 106 92 104 89 96 92 109 103 0.8770830.9890Aperiodic-Template107 121 98 84 98 104 89 96 96 107 0.3736250.9940Aperiodic-Template98 110 102 81 121 99 122 92 89 86 0.0380620.9920Aperiodic-Template101 101 115 102 101 97 97 96 106 84 0.7811060.9930Aperiodic-Template3011596921048610410798839710988979210496961138910110210110310088811048210510810611488123919990103102103105108102839110410097100103105898212089911009010510694101851021031159295961019898108101111941209210799104113951019311412910310587109969810297104102105861129893106108899275971001041089310810610512094989075791081021069277898710011395105121107113959089961061009510293100939510298105107106112901101051001011019399978912210511911296100102918693989610197941001059177991059410095761098910510411311412210394881091041127910993118948610583901029689968910710490971019810874112102988811489105116102103117789310297102789096961019110296961041038510410710711589104123102103899882831049196103118941001088911196101991008810995881059210710411210693909710111093969410810977899310295968811611310493114859910211597100869510510311111310810498114102981089589100968910412289991021111071028892113879299104115101120929811485118105111111938510810986114121102108111888899928893988511586968996114110901011021059310294941031058710312298861059190104108841069884989711310410996107918211199100102128961041091019397108869511511010490110931021061091051009110097116117101108951029410210399115100931238310390107113102100101103951009191909310311091109102969210611011993116998896103999411410798100103106889610795100107969010310110294114869598112981101128886104111113104116116102879510195871011069311196961131168597118868511688101961241099210410211296948910697831101031041069998989510410897921011089610810511588105106929310411410287971059798111103859479999110298115110108901178910581106871119610291124941131071181021119491112107911181051151029887101100109991011009896104117949399921048794899810911187951011209410799971011089696100981131209899899195809184102108969110010212297929612497106881128610686100108103101888810510191107102751221009794119891011041089198961021051099710491102101931011071019910699839884900.1230380.6163050.0876920.3472570.1699810.3160520.9368230.4136280.1554990.8308080.2570040.3329700.0215540.6869550.3026570.1068770.7772650.0522750.6745430.5301200.7943910.9482980.8237250.2583070.2405010.1699810.7054660.1288740.2368100.4788390.7379150.8513830.0145500.0795380.8530490.2953910.5914090.8755390.5707920.1478150.2622490.1617030.3570000.1349440.5790210.4064990.0815100.4335900.8412260.6993130.8831710.2283670.0810130.1303690.9710060.3070770.7238040.6807550.3685870.5914090.2144390.7734050.2826260.7095580.8991710.5790210.4521730.7617190.6142260.9019590.2716190.9681280.8147240.805569310.99400.99300.98900.99000.98800.98800.98500.99000.99300.99300.98800.99200.98700.99500.99300.98600.98800.99300.99000.99200.99000.99100.98700.98800.98300.99000.99200.99000.98700.99000.98900.99000.99200.99000.99100.99300.98700.99300.98800.99200.99400.98800.98800.99600.98900.98600.99300.98700.99400.99000.98400.99200.99100.98700.99000.99200.98400.98900.98300.99200.99000.99300.99300.99300.98800.98800.99200.99000.99200.99400.99400.98900.98700.9870Aperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-Template981029088989593961129011787106116105110979190102838497848285961268510510211410796107878995941231151121181071009610012810587616160625172555968605760474236424769646263636769109107789712197102859710510210811295106818810794104106105103100102939689104949610012094831149487899085111107981001157991116925748507772636272626874607055645574565765576470651041051021089110011110010710392989595988711590981041129894921089795107111939697103929510410111611310490991098610292122891101154764685869576965637055655876666863557163646462661139010995108911121069410998941189887111116998810711110510589951087610397119116971021039610785114124878991100889695118105901147671676667606259635061727855606464615071685951529276105104981061069986103961078710711610691811091139694931061061021199692921079294971139710682969610610591119101998810599105676852797358576353568268727355706970685760696655941079310792108105101911229810086819893106951009793981071191101011118510295941081031131099710291110889293869810610591104108905651696165635266586856676776616255526966798071681031079895106968510711699112104849710010199110959510511989879610810589951071019388991039410011989108107100809910311210210182996871486256537568724858596461637063656064695852701049111710092106899510789109102100113105941039610190106121861161081029311910584108949592839510411291110113941001171049510689105834361774564725553637362616070636279587752686666549510510199871009011190829110310410197100911091178887104941111029710795981111031068611210711510894969698879792849010193881126472655958606958618357586154846960595767525263658811010710710710110710010098859710897881179412210810010172132969110710291111100779910210210490111909898105108112961041019395971038759705751687063635064564964746452815359465158620.7753370.3055990.2854270.9228550.3702620.9756440.4616120.8563590.4190210.2380350.4262720.9357160.1969200.4299230.6662450.2355890.4578250.1635130.5914090.8055690.4502970.0211170.0771310.1223250.6183850.8530490.1906540.0512810.7258290.3619380.3669180.8644940.4597170.8201430.3570000.5002790.7156790.0499840.1916870.2380350.3361110.6475300.1699810.2570040.9390050.7136410.0747910.1875810.3130410.2011890.0032700.3375860.1318060.1211820.3744960.7463580.4432510.8767850.9217040.0197910.2563330.9196980.1246390.0302810.0080960.2892090.1234770.2626750.2846570.8865460.1670340.3200660.6270440.700637320.99500.98600.99000.99000.99400.99100.98800.99200.99200.99000.98500.99400.98600.99000.98800.98500.98800.99300.99400.99200.99300.98800.98700.98800.99100.99100.99600.98200.98700.98600.98900.98900.99100.99000.98600.99200.98800.99000.98900.98600.99100.98500.98800.99200.98900.98800.99300.99100.98700.99500.99040.98560.98720.98560.99040.98720.99520.98080.98720.98720.98880.98880.99200.99360.99040.99840.99200.99360.99360.99520.99520.99520.99040.9888Aperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplateAperiodic-TemplatePeriodic-TemplateUniversalApenRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-ExcursionRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-VRandom-Excursion-V65 55 60 74 66 61 51 75 66 53 0.3637000.9824Random-Excursion-V61 58 65 76 59 54 71 61 67 54 0.5835440.9856Random-Excursion-V83 91 124 94 94 105 89 101 114 105 0.1273930.9880Serial83 101 98 105 105 101 100 91 101 115 0.6869550.9940Serial000000000 1000 0.000000 * 1.0000Lempel-Ziv108 90 92 114 111 106 106 89 99 85 0.3804070.9870Linear-Complexity--------------------------------------------------------------------------------Большое количество проведенных тестов объясняется тем, что некоторые тесты были пройдены несколько раз, но с разными внутренними параметрами.