Основной алгоритм.
Данный тест оценивает энтропию на выходе генератора равномерно распределенной величины, базирующийся на подсчете среднестатистического выходного значения, полученного в результате нескольких наблюдений [1]. Оценка энтропии генератора равномерно распределенной величины — простой процесс. Она используется для обеспечения верхней границы вероятности в 99 %, pmax, что наиболее распространенные значения в выборке будут лежать в этих пределах. Также эта величина используется и для оценки минимального значения энтропии на выходе генератора [1].
Алгоритм выполнения теста следующий:
Получаем выборку из N элементов.
а) Находим наиболее часто встречающееся значение в выборке;
б) Считаем количество совпадений с этим значением, пусть это будет Cmax;
в) Pmax = Cmax/N;
г) Считаем Сbound=CMAX+2.3
;
д) H=-log2(Cbound/N);
е) Пусть W будет количество бит в каждом элементе выборки (т. е. размер элемента);
ж) min(W,H) — это нижняя граница оценки энтропии.
Например, если набор данных {0, 1, 1, 2, 0, 1, 2, 2, 0, 1, 0, 1, 1, 0, 2, 2, 1, 0, 2, 1}, наиболее часто встречающееся значение — 1, CMAX=8 и pmax = 0.4.
CBOUND = 8 + 2.3
= 13.04.
H = –log2(0.652) = 0.186.
W = 3.
Рис. 1. Абстрактный автомат алгоритма теста на оценку энтропии для равномерно распределенных последовательностей
Абстрактный автомат получим, если укажем алфавит A, B, C, I, R и программу P, как совокупность команд вида: ii,aj ®bx,cy.
В нашем случае:
A = {a1,a2,a3, a4… aN}, B={b1}, C={ c1,c2, c3}, I={i1,i2,…,in}, R={r1}
δ: IxA ®BxC ={a1i1 ® b1c1, a2i2 ® b1c1, anin ® b1c1, a1i1 ® b1c2, a2i2 ® b1c2, anin ® b1c2, a1i1 ® b1c3, a2i2 ® b1c3, где w1c3®r1}
Имеем следующий абстрактный автомат, как математическую модель схемы оценки минимальной энтропии в равномерно распределенной последовательности.
Программная реализация.
Литература:
1. http://csrc.nist.gov/publications/PubsSPs.html «DRAFT — SP800–90b».
