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

Ставер Е. В. Анализ процедур генерации ключей криптографических алгоритмов. Программная реализация теста на оценку энтропии для равномерно распределенных последовательностей 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».

Основные термины (генерируются автоматически): Программная реализация, генерации ключей криптографических, ключей криптографических алгоритмов, процедур генерации ключей, Анализ процедур генерации, оценку энтропии, Программная реализация теста, Draft SP, выходе генератора, Абстрактный автомат, минимального значения энтропии, Оценка энтропии генератора, Программная реализация критерия, распределенных последовательностей, распределенных последовательностей draft, оценки минимальной энтропии, Абстрактный автомат алгоритма, Draft SP 800–90b, выполнения теста следующий, среднестатистического выходного значения.

Обсуждение

Социальные комментарии Cackle
Задать вопрос