Библиографическое описание:

Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов. Программная реализация теста на оценку энтропии для равномерно распределенных последовательностей Draft SP 800-90b // Молодой ученый. — 2013. — №8. — С. 119-124.

Основной алгоритм.

Данный тест оценивает энтропию на выходе генератора равномерно распределенной величины, базирующийся на подсчете среднестатистического выходного значения, полученного в результате нескольких наблюдений [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».

Обсуждение

Социальные комментарии Cackle