 |
Примеры из Nist Test Suite.
|
|
|
|
Статистические тесты
В криптографии под понятием " случайного числа " понимают число, которое нельзя предсказать до момента его генерации. Однако существует и такое требование – такое число нельзя угадать, зная последующие (так называемая "атака из будущего"). Тут надо немного пояснить. В криптографии оперируют не одиночными числами, а последовательностью, серией. Генератор случайных чисел непрерывно работает, выдавая постоянную последовательность битов, а они уже программно или аппаратно далее интерпретируются в зависимости от контекста. Допустим, у нас есть последовательность случайных чисел 2, 5, x, 7 (для простоты – это десятичные числа). Криптоаналитик хочет узнать случайное число x. Говоря о стойкости серии случайных чисел, подразумевают, что:
· нет аналитической зависимости между последовательно сгенерированными числами;
· зная предыдущие числа (в нашем случае – 2 и 5), криптоаналитик не может найти следующие число x (атака из прошлого);
· зная последующие числа (в нашем случае – 7), нельзя установить предшествующие (атака из будущего);
· вероятность появления любого числа в последовательности одинаковая.
Поскольку на практике используют генерации двоичной последовательности, то вероятность появления каждого бита - 1/2 в степени n, где n - разрядность чисел. Пример: имеется последовательность 32-разрядных чисел m, вероятность того, что
число
m +1
будет таким, как предсказал криптоаналитик, равняется 1/(2^32).
Если перебирать в секунду 1000 чисел, то это равнозначно одному совпадению за 268 дней круглосуточной работы.
Но не всякую последовательность можно назвать случайной. Для исследования алгоритмов реализации генераторов есть несколько тестов, которые определяют, случайна или нет данная последовательность. Поскольку мы имеем дело с вероятностными процессами, то суждение о случайности или нет такой последовательности также будет верным (неверным) с некоторой вероятностью. На практике для каждого теста есть свое распределение вероятности (своя статистика) и берется какое-то значение, обычно на краях диапазона, например 0,01% (так называемое критическое значение). Далее делают тест и рассчитывают вероятность – если она превышает критическое значение, тестовая последовательность признается неслучайной. Пример: в результате теста вероятность того, что числа случайные, равна 0,40%, значит, числа неслучайные, вероятность превышает критическое значение. При вероятности <0,01% числа признаются случайными, а тест пройденным.
|
|
|
В таком подходе возможны две ошибки, называемые ошибками первого и второго рода.
Ошибка первого рода (она обозначается как "a") возникает, когда тестовая последовательность чисел является истинно случайной, но тест признает ее неслучайной. Это ложное срабатывание. Ошибка второго рода случается, когда тест признает случайными данные, которые на самом деле неслучайные.
Ошибки первого рода называются еще уровнем достоверности теста, который может быть вычислен заранее. Обычно принимают уровень достоверности 0,01 – из ста истинно случайных последовательностей одна признается неслучайной.
Ошибки второго рода записывают как "β", и они означают, что исследуемые числа обладают скрытой закономерностью, а значит, порождающий их генератор выдает "плохую" последовательность. Вычислить этот коэффициент гораздо труднее, а его влияние очень большое – если ошибки первого рода приводят всего лишь к отсеиванию некоторой части чисел, то ошибки второго рода могут повлиять на стойкость шифра.
|
|
|
И последнее. Для оценки тестов применяют отдельный коэффициент, так называемый P (P -value). P -value – это вероятность того, что некий абстрактный идеальный генератор случайных чисел сгенерировал бы последовательность менее случайную,
чем исследуемая. Когда
P = 0, это значит, что последовательность чисел неслучайна, а
когда
P = 1, то последовательность близка к совершенно случайной. На практике
значение Р должно быть больше, чем уровень достоверности теста. Например, при
P >0,01
проверяемая последовательность случайна в 99% случаев (если
достоверность теста а=0,01, то одна из ста последовательностей будет неслучайной). Для двоичных последовательностей мы делаем еще некоторые предположения:
· Монотонность. Вероятность появления 1 или 0 каждый раз одинаковая – 1/2.
· Масштабируемость. Если вся последовательность случайна (проходит тест на случайность), то должна быть случайной и любая случайно выбранная подстрока. Если серия из 1000 чисел случайна, то серия чисел от 500-го до 531- го числа также должна быть случайной и проходить тест.
Национальным институтом стандартов и технологий (NIST) разработаны 16 специальных тестов для определения случайных чисел. Имеется программная реализация в виде NIST Statistical Test Suite для платформы Unix. Она распространяется в виде исходного кода и содержит как инструменты командной строки, так и графические утилиты. Загрузить код можно отсюда: http://www.csrc.nist.gov/rng/sts-1.5.tar(объем 8,7 Мб). Также есть набор дополнительных данных и утилит, в частности генератор псевдослучайных чисел Blum- Blum-Shub. Загрузить можно отсюда: http://www.csrc.nist.gov/rng/sts.data.tar(объем 43,8 Мб). Кстати, обратите внимание на размер – образцы случайных последовательностей плохо или вообще не сжимаются (один из тестов так и называется
– тест на сжимаемость). Последовательность случайных чисел вообще нельзя сжать, так как при попытке построения словаря на таких данных его размер совпадает с размером самих данных – ведь там нет повторяющихся чисел.
Рассмотрим тесты подробнее. Замечу, что непрохождение хоть одного автоматически отменяет все последующие тесты – числа неслучайны, и продолжать проверку нет смысла.
· Частотный тест (монобитный тест на частоту, Frequency (Monobits) Test). В этом тесте исследуется доля 0 и 1 в последовательности и насколько она близка к идеальному варианту – равновероятной последовательности. Для теста надо иметь не менее 100 бит данных.
|
|
|
· Блочный тест на частоту (Test for Frequency within a Block). Последовательность разбивается на блоки длиной М бит, и для каждого рассчитывается частота появления единиц и насколько она близка к эталонному значению – М/2. Когда М=1, длина блока 1 бит и тест равнозначен предыдущему. Длина тестовой последовательности не менее 100 бит, длина блока больше 20 бит.
· Тест на серийность (Runs Test). В тесте находятся все серии битов –
непрерывные последовательности одинаковых битов – и их распределение
сравнивается с ожидаемым распределением таких серий для случайной последовательности. Длина последовательности 100 и более бит.
· Тест на максимальный размер серии единиц. Исследуется длина наибольшей непрерывной последовательности единиц и сравнивается с длиной такой цепочки для случайной последовательности.
· Матрично-ранговый тест (Random Binary Matrix Rank Test). Цель теста – проверка линейной зависимости между подстроками фиксированного размера – матрицами 32х32 бита. Длина последовательности – не менее 38 912 бит, или 38 матриц.
· Спектральный тест (тест дискретным преобразованием Фурье). Цель теста –
обнаружить повторяющиеся блоки или последовательности.
· Тест с неперекрывающимися непериодическими шаблонами (Non- overlapping (Aperiodic) Template Matching Test). Показывает число заранее заданных битовых строк (шаблонов) в последовательности.
· Тест на перекрывающиеся периодические шаблоны (Overlapping (Periodic) Template Matching Test). Показывает количество заранее определенных шаблонов (периодичных битовых последовательностей) в тестовой последовательности.
· Универсальный статистический тест (Maurer's Universal Statistical Test). Показывает число бит между двумя шаблонами и служит для определения сжимаемости последовательности.
· Комплексный тест Lempel-Ziv (Lempel-Ziv Complexity Test). Цель теста – определить число четных слов в последовательности и таким образом определить сжимаемость последовательности.
|
|
|
Кроме этих тестов есть еще несколько, но мы просто перечислим их без описания:
· линейный тест (Linear Complexity Test);
· серийный тест (Serial Test);
· приближенный тест на энтропию (Approximate Entropy Test);
· суммирующий тест (Cumulative Sum (Cusum) Test);
· тест на случайные отклонения (Random Excursions Test и Random Excursions Variant Test).
Как видите, получение случайных чисел совершенно нетривиальная задача, и тут есть место не только изящным инженерным решениям (для аппаратных генераторов), но и для кропотливого труда математиков и аналитиков. Плохой генератор, который дает неслучайные числа, может сильно ослабить защищенность криптосистемы, поэтому разработчики тестов предпочитают перестраховаться – лучше назвать неслучайным истинно случайное число, чем наоборот.
Рассмотрим еще один набор тестов для анализа свойств псевдослучайных последовательностей Diehard.
Тесты Diehard — это набор статистических тестов для измерения качества набора случайных чисел. Они были разработаны Джорджем Марсальей (George Marsaglia) в течение нескольких лет и впервые опубликованы на CD-ROM, посвящённом случайным числам. Вместе они рассматриваются как один из наиболее строгих известных наборов тестов.
· Дни рождения (Birthday Spacings) — выбираются случайные точки на большом интервале. Расстояния между точками должны быть асимптотически распределены по Пуассону. Название этот тест получил на основе парадокса дней рождения.
· Пересекающиеся перестановки (Overlapping Permutations) — анализируются последовательности пяти последовательных случайных чисел. 120 возможных перестановок должны получаться со статистически эквивалентной вероятностью.
· Ранги матриц (Ranks of matrices) — выбираются некоторое количество бит из некоторого количества случайных чисел для формирования матрицы над {0,1}, затем определяется ранг матрицы. Считаются ранги.
· Обезьяньи тесты (Monkey Tests) — последовательности некоторого количества бит интерпретируются как слова. Считаются пересекающиеся слова в потоке.
Количество «слов», которые не появляются, должны удовлетворять известному распределению. Название этот тест получил на основе теоремы о бесконечном количестве обезьян.
· Подсчёт единичек (Count the 1’s) — считаются единичные биты в каждом из последующих или выбранных байт. Эти счётчики преобразуется в «буквы», и считаются случаи пятибуквенных «слов».
· Тест на парковку (Parking Lot Test) — случайно размещаются единичные окружности в квадрате 100×100. Если окружность пересекает уже существующую, попытаться ещё. После 12 000 попыток, количество успешно
«припаркованных» окружностей должно быть нормально распределено.
|
|
|
· Тест на минимальное расстояние (Minimum Distance Test) — 8000 точек случайно размещаются в квадрате 10 000×10 000, затем находится минимальное расстояние между любыми парами. Квадрат этого расстояния должен быть экспоненциально распределён с некоторой медианой.
· Тест случайных сфер (Random Spheres Test) — случайно выбираются 4000 точек в кубе с ребром 1000. В каждой точке помещается сфера, чей радиус является минимальным расстоянием до другой точки. Минимальный объём сферы должен быть экспоненциально распределён с некоторой медианой.
· Тест сжатия (The Squeeze Test) — 231 умножается на случайные вещественные числа в диапазоне [0,1) до тех пор, пока не получится 1. Повторяется 100 000 раз. Количество вещественных чисел необходимых для достижения 1 должно быть распределено определённым образом.
· Тест пересекающихся сумм (Overlapping Sums Test) — генерируется длинная последовательность на [0,1). Добавляются последовательности из 100 последовательных вещественных чисел. Суммы должны быть нормально распределены с характерной медианой и сигмой.
· Тест последовательностей (Runs Test) — генерируется длинная последовательность на [0,1). Подсчитываются восходящие и нисходящие последовательности. Числа должны удовлетворять некоторому распределению.
· Тест игры в кости (The Craps Test) — играется 200 000 игр в кости, подсчитываются победы и количество бросков в каждой игре. Каждое число должно удовлетворять некоторому распределению.
Примеры из Nist Test Suite.
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is <Linear-Congruential>
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
7 4 7 9 11 14 8 16 11 13 0.202268 98/100 Frequency
5 11 8 9 11 11 16 7 14 8 0.366918 100/100 BlockFrequency
6 6 7 9 7 7 15 18 14 11 0.055361 99/100 CumulativeSums
5 8 6 8 11 15 9 9 10 19 0.071177 99/100 CumulativeSums
11 10 5 15 5 10 6 15 15 8 0.102526 99/100 Runs
13 8 13 6 7 11 9 6 16 11 0.334538 100/100 LongestRun
6 5 7 15 11 0 22 17 7 10 0.000019 * 100/100 Serial
5 14 10 8 24 6 6 8 10 9 0.001030 99/100 Serial
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 96 for a
sample size = 100 binary sequences.
The minimum pass rate for the random excursion (variant) test is undefined.
For further guidelines construct a probability table using the MAPLE program
provided in the addendum section of the documentation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
5. ЗАКЛЮЧЕНИЕ И ПЕРСПЕКТИВЫ
Обобщенная система Лоренца используется для проектирования генераторов псевдослучайного числа. Два новых алгоритма разработаны, чтобы сгенерировать двоичную последовательность. Один из них основан на сумме трех координат хаотической орбиты GLS, другой основан на комбинации трех координат хаотической орбиты GLS. Оба из алгоритмов использовали полное число орбит, по сравнению с большинством других исследований, которые использовали только одну хаотическую орбиту (координату) высоко-размерной хаотической системы. Анализы безопасности ключевого и статистического анализа двоичных последовательностей показывают, что у PRNG было хорошее сопротивление грубым атакам и хорошие псевдослучайные характеристики.
Предложенный PRNG может использоваться в качестве источника псевдослучайных чисел, которые широко используются в криптографии, лотерее, казино (онлайн и офлайн), имитации реальных условий в многочисленных приложениях и многих других областях. Дальнейшее исследование будет посвящено приложению основанного PRNG на GLS к надежному шифрованию. Безопасность способа связи будет проанализирована подробно. Другая цель будущего исследования состоит в том, чтобы сравнить безопасность основанного PRNG на хаотических системах с PRNG, основанным на классических методах.
Литература
1. Криптографическая защита информации в АСУ СН. Курс лекций. В.И. Долгов. ХВУ. 1998.
2. Криптографическая защита информации в информационных системах. Курс лекций. И.Д. Горбенко. ХНУРЭ. 2002.
3. Теория информации. Курс лекций. В.И. Долгов. ХВУ. 1998.
4. Брюс Шнайер. Прикладная криптография. 2-ое издание. Протоколы, алгоритмы и исходные тексты на языке С. Доступно: http://nrjetix.com/r-and-d/lectures
5. Национальный институт стандартов и технологий. Web-сайт: National Institute of Standards and Technology
6. Средство для проверки генераторов случайных чисел пригодных для криптографических целей. Доступно: NIST STS Software
7. Руководство по работе со средством для статистического анализа случайных последовательностей. Доступно: Guide to the Statistical Tests.
8. Д. Кнут. Искусство программирования. Т.2
|
|
|
