2014-02-10
331
Генерация случайных битов
Псевдослучайные последовательности
Может быть какой угодно стойкий протокол, но если можно угадать ключ, то о безопасности не имеет смысла говорить.
Генератор случайных битов (ГСБ) – устройство или алгоритм, выдающий последовательность статистически независимых и непредсказуемых двоичных разрядов. Основное требование в том, что последовательность не может быть уверенно воспроизведена, то есть не может быть воспроизведена при запуске генератора с одним входом.
Существуют следующие типы ГСБ:
a) аппаратные – основаны на физических процессах (радиоактивный распад и т.д.);
b) программные (ввод пользователя, системные часы, содержимое буферов ввода/вывода, сетевая статистика и т.д.).
Недостатком аппаратных генераторов является то, что они являются очень медленными, также они часто выдают ненормированную последовательность.
Способы борьбы с недостатками:
1. хэширование;
2. последовательности битов заменяются следующим образом:
|
|
|
01->0,
10->1,
случаи 00, 11 отбрасываются.
1. Комбинаторный
Рассмотрим систему, в которой некоторая физическая величина характеризуется (xi,yj), пусть событие А происходит с вероятностью 
, В – с вероятностью 
, С – с вероятность 
, D – c вероятностью
.
Если величины может принимать 4 значения, то в последовательности из 1000 значение количества информации будет 41000. Недостатком является то, что величины имеют разные вероятности, поэтому в 41000 они также будут иметь разные вероятности.
2. Вероятностный (по Шенону)
Суть подхода заключается в том, что самое вероятное значение несет меньше информации, а наименее вероятное – больше.
Учитывая этот факт, для величин А (PA=), В (PB=), С (PC=), D (PD=) значения количества информации будут иметь вид:
A 0
B 10
C 110
D 111
3. Алгоритмический (по Колмогорову)
Количество информации определяется как длина минимального алгоритма, описывающего последовательность
, где h – хэш-функция. Есть 1024 бита.
Последователньости, которые проходят тест по Колмогорову, проходят статистичесеие тесты.
