Подробный аналитический разбор физического датчика calif.bit в сравнении с неисправным датчиком germany.bit по критериям американского стандарта Draft SP 800-90b

Основные критерии американского стандарта Draft SP 800–90b.

Были рассмотрены следующие критерии:

·             ApproximateEntropy

·             ChiSquare

·             Collision

·             Frequency

·             Markov

Рассмотрим основные критерии прохождения/не прохождения тестов датчиками.

·                 ApproximateEntropy

Данный тест оценивает энтропию на выходе генератора равномерно распределенной величины, базирующийся на подсчете среднестатистического выходного значения, полученного в результате нескольких наблюдений [1]. Оценка энтропии генератора равномерно распределенной величины — простой процесс. Она используется для обеспечения верхней границы вероятности в 99 %, pmax, что наиболее распространенные значения в выборке будут лежать в этих пределах. Также эта величина используется и для оценки минимального значения энтропии на выходе генератора [1].

·                 ChiSquare

Для нашего случая проверка по критерию «хи-квадрат» позволит узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ, то есть удовлетворяет ли он требованию равномерного распределения или нет.

Частотная диаграмма эталонного ГСЧ представлена на рисунке ниже [1]. Так как закон распределения эталонного ГСЧ равномерный, то (теоретическая) вероятность p_i попадания чисел в i-ый интервал (всего этих интервалов k) равна p_i = 1/k. И, таким образом, в каждый из k интервалов попадет ровно по p_i · N чисел (N — общее количество сгенерированных чисел).

Реальный ГСЧ будет выдавать числа, распределенные (причем, не обязательно равномерно!) по k интервалам и в каждый интервал попадет по n_i чисел (в сумме n₁ + n₂ + … + n_k = N). Как же нам определить, насколько испытываемый ГСЧ хорош и близок к эталонному? Вполне логично рассмотреть квадраты разностей между полученным количеством чисел n_i и «эталонным» p_i · N.

·                 Collision

Тест на коллизии измеряет оцениваемое время до первой коллизии в выборке. Цель статистики коллизий — оценка вероятности наступления наиболее желаемого состояния, основываясь на времени коллизий [1]. Данный тест будет оценивать минимальную энтропию для источников шума, которые являются весьма предвзятыми (т. е. это означает, что время между коллизиями относительно мало), в то время как увеличение времени между коллизиями предполагает повышение общего уровня энтропии в целом. Нижняя граница энтропии в данном тесте может быть оценена с известным уровнем доверия только в случае, когда элементы в последовательности независимы. Какие либо зависимости между элементами могут вызвать переоценку энтропии [8]. На практике, незначительная переоценка решается выбором минимальной оценки энтропии от всех тестов как ожидаемой от данного генератора шума.

·             Frequency

Суть теста — определение доли единиц внутри блока длиной m бит. Цель — выяснить действительно ли частота повторения единиц в блоке длиной m бит приблизительно равна m/2, как можно было бы предположить в случае абсолютно случайной последовательности [1]. Вычисленное в ходе теста значение вероятности p должно быть не меньше 0,01. В противном случае (p < 0,01), двоичная последовательность не носит истинно случайный характер.

·             Markov

В процессе Маркова первого порядка состояние на выходе зависит только от текущего состояния; а в процессе Маркова n-го порядка состояние на выходе зависит от текущего состояния и предыдущих n-1 состояний [1]. По этой причине, модель Маркова может использоваться в качестве шаблона для тестирования источников с зависимостями. Данный тест обеспечивает оценку минимума энтропии путем измерения зависимостей между последовательными выходами от источника шума. Оценка минимума энтропии основывается на энтропии какой либо выходной цепочки, вместо оценки минимума энтропии для каждого выхода.

Ключевая компонента в оценке энтропии процесса Маркова — возможность точно оценить матрицу вероятностей переходов. Главная трудность в оценке — требование к большому количеству оцениваемых данных для исключения каких либо возможных зависимостей [1]. В целом, переходы с низкой вероятностью могут не случиться при тестировании на небольшом количестве данных. Чем больше размер выборки — тем легче становится произвести точную оценку вероятности переходов.

Аналитический разбор датчиков.

По результатам теста на оценку энтропии для равномерно распределенных последовательностей, теста получены данные:

сalif.bit, хуже — germany.bit.

Проверка по критерию «хи-квадрат» позволила узнать, насколько созданный нами реальный ГСЧ близок к эталону ГСЧ, т. е. удовлетворяет ли он требованию равномерного распределения или нет [7]. В таблице 1 приведены теоретические значения «хи-квадрат» (χ2теор.), где ν = N — 1 — это число степеней свободы, p — это доверительная вероятность, задаваемая пользователем, который указывает, насколько ГСЧ должен удовлетворять требованиям равномерного распределения, или p — это вероятность того, что экспериментальное значение χ2эксп. будет меньше табулированного (теоретического) χ2теор. или равно ему.

Из проведенного исследования следует, что этому критерию по степени доверительной вероятности не соответствуют последовательности сalif.bit, хуже — germany.bit.

При длине блока равной длине всей последовательности частотный блочный тест переходит в частотный побитовый тест.

Кроме этого, оценка P-значения, если ~1, то тест пройден, если 0 — не пройден.

P-value можно считать удовлетворительным, у calif.bit и germany.bit — нет, так что хотя результаты по энтропии они показывают очень хорошие, проверку на p-value они не прошли. Чем меньше длина блока — тем больше разброс, неравномерность распределения 0 и 1 в битовой последовательности, очевидно что они будут разными [1]. Поскольку размер блока был взят большой (в первую очередь для оценки P-value), то результаты частотного и блочно-частотного тестов не сильно отличаются.По тесту Маркова идеально прошел тестирование calif.bit. Хуже всех germany.bit.

Анализируем лог-файлы, полученные в ходе тестирования этих двух датчиков

·             Лог датчика calif.bit

Approximate:

Общее количество единиц 39984889, и общее количество нолей 40015111

Общее количество символов в отобранном файле 80000000

Вероятность ноля 0.4998111125

Вероятность единства 0.5001888875

Энтропия = 0.9999998971 бита за бит.

p-val в приблизительном тесте энтропии 0.17916603510836965000

Критерий хи-квадрат:

Ценность кси квадрата для распределения 80000000 образцов 11.417116

и вероятность взвешенной ценности кси квадрата составляет 0.0727706672 процента

Тест столкновения:

Средняя длина интервала столкновения 18.89

среднеквадратичное отклонение 18.89223

нижний предел доверительного интервала 18.86502

оценка минимальной энтропии в тесте столкновения 0.99752

p-val в тесте столкновения 1.00000000000000000000

Тест частоты:

Энтропия = 0.9991950219 бита за бит.

В стендовых испытаниях двигателя энтропия составляет 0.9953290195 бита за бит.

p-val в тесте частоты 1.00000000000000000000

Тест Маркова:

среднеквадратичное отклонение элементов в матрице вероятностей перехода 0.00106

Оценка энтропии в тесте Маркова 0.99941

p-val в тесте markov 0.92972973801143322000

·             Лог-файл датчика germany.bit

Approximate:

Общее количество единиц 38809162 и общее число нулей 41190838 / / 38809162 Общее количество единиц и общее число нулей 41190838

Общее число символов в выбранный файл является 80000000 / / Общее число символов в выбранном файле

Вероятность нуля 0,4851145250 / / Вероятность нуля

Вероятность единство 0,5148854750 / / Вероятность единства

Энтропия = 0,9993605684 бит в бит.

P-Val в приблизительном тест энтропия +0,00000000000000000000

Хи-квадрат:

Хи-квадрат значение для распространения образцов 70904.757112 80000000 / / Хи-квадрат значения для распределения 80000000 образцов 70904.757112

Измеренные и вероятность значения хи-квадрат 0,0000000000 процента / / и вероятности хи-квадрат измеренное значение 0,0000000000 процента

Столкновение тест:

Средней длины интервала столкновение 16.66 / / Средней длины интервала столкновение

Стандартное отклонение составляет 16,65622 / / Стандартное отклонение составляет 16,65622

Нижняя граница доверительного интервала 16,63286 / / Нижняя граница доверительного интервала 16,63286

мин-энтропии оценка в столкновении тест 0,91791 / / мин-энтропии оценка в столкновении тест 0,91791

P-Val в столкновении тест +0,00000000000000000000

Частота тест:

Энтропия = 0,9574238785 бит в бит.

В тест-блока энтропия 0,9544848325 бит на бит. / / В энтропии Испытательный блок 0,9544848325 бит в бит.

P-Val в тесте частота +0,00000000000000000000 / / P-Val в частоте тест 0,00000000000000000000

Маркова тест:

стандартное отклонение элементов в матрице переходных вероятностей является 0,00239 / / стандартное отклонение элементов в матрице переходных вероятностей 0,00239

Энтропия оценку в тесте Маркова 0,93350

P-Val в марковской тест +0,02562168050851533500

Литература:

1.                 http://csrc.nist.gov/publications/PubsSPs.html «DRAFT — SP800–90b».