ЛЕКЦИЯ 16. Методы генерации случайных чисел 16.1. Требования к случайным

Физические источники случайных чисел.

16.2. Генераторы псевдослучайных последовательностей.

16.3. Криптографически генерируемые псевдослучайные

числа.

в лекции 6. Сценарии распределения ключей в процессе установления соединения

используют оказии для того, чтобы исключить возможность атаки на основе воспроизведения сообщений. Использование случайных чисел для оказий не дает шанса оппоненту определить или угадать значение оказии.
Генерирование сеансовых ключей, выполняемое либо центром распределения ключей, либо одним из участников соединения.
Генерирование ключей для алгоритма RSA − шифрования с открытым ключом.

Требования к используемой последовательности случайных чисел:
случайность и непредсказуемость.

Критерии для проверки последовательности на случайность:
однородность распределения: распределение чисел в последовательности должно быть однородным, т.е. частота появления в последовательности конкретного значения должна быть примерно одинаковой для всех значений;
независимость: ни одно из значений последовательности не должно логически выводиться из других значений.

Физические источники случайных чисел:
импульсные детекторы ионизирующего излучения,
газоразрядные лампы,
конденсаторы с утечкой тока и пр.

гаммы):
1. Период гаммы должен быть достаточно большим для шифрования сообщений

различной длины.
2. Гамма должна быть трудно предсказуемой.
3. Генерирование гаммы не должно быть связано с большими техническими и организационными трудностями.
Формирование значений дробной части многочлена первой степени:
Y(n) = Ent (a n+b), a, b = const.

Способ Джона фон Неймана –
каждое последующее случайное число образуется возведением предыдущего в квадрат с последующим отбрасыванием цифр с обоих концов.
Генератор последовательности Фибоначчи
Последовательность Фибоначчи – в данной последовательности, за исключением первых двух ее членов, каждый последующий член равен сумме двух предыдущих:
{0,1,1,2,3,5,8,13,21,34 …}.

Генератор последовательности Фибоначчи.
Квадратами обозначены разряды генератора,
треугольниками обозначено умножение на коэффициенты (на практике в зависимости от коэффициента там либо есть соединение с последующей логикой, либо его нет).
Плюсы в кружках − операция XOR: 0+0=0, 0+1=1, 1+1=0

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

сумматоров (0, 2, .., N);
0 и N всегда равны 1 (поэтому на схеме их можно не указывать);
из всех i , i{1,2,..,N-1}, хотя бы одно должно иметь значение ‘1’.

Фильтр Хаффмана

Циклические свойства генератора последовательности определяется т.н.
характеристическим полиномом:

где 0=N=1, j{0,1}, j=1,2,..N-1.

Период последовательности будет максимальным в том случае, когда многочлен (x) удовлетворяет условиям примитивности и неприводимости.

а а = 1+4 j, то период можно увеличить до

числа

Используются значения а = 69069 и а = 71365.

Значение m выбирается равным или почти равным значению 231 - максимально допустимому для компьютера неотрицательному целому числу.

При реализации псевдослучайных последовательностей в компьютере предлагаются
три критерия качества генератора двоичных псевдослучайных чисел:
Генерирующая функция должна быть функцией полного периода, т.е. функция должна порождать все числа от 0 до m прежде, чем числа начнут повторяться.
Генерируемая последовательность должна вести себя как случайная.
Генерирующая функция должна эффективно реализовываться в рамках 32-битовой арифметики.

Алгоритм имеет четыре параметра:
т модуль сравнения m > 0,
а множитель 0≤ ac приращение 0≤ cX0 начальное или порождающее число 0≤ X0
Последовательность случайных чисел {Х} получается с помощью итераций:
Xn+1= (aXn + c) mod m.

1. Если т, а, с и X0 являются целыми, то будет получена последовательность целых чисел из
диапазона 0≤ Xn2. При c = 0, наибольший период составит m/4 при а = 3+8j или а = 5+8j и нечетном
начальном числе.

-1.
В этом случае генерирующая функция принимает вид
Xn+1 = (aXn)

mod (231 – 1).

Знания небольшой части последовательности уже достаточно для того, чтобы определить все параметры алгоритма.

Например, противник сможет определить значения Х0, Х1, Х2, и Х3.
Тогда

X1 = (aX0 + c) mod m,
X2 = (aX1 + c) mod m,
X3 = (aX2 + c) mod m.

Эти уравнения могут быть решены относительно а, с и m.

сделать алгоритм еще более защищенным, вместо значений простого счетчика в

качестве вводимых значений можно использовать выходные значения некоторого полнопериодического генератора псевдослучайных чисел.

подается два псевдослучайных значения. Одно из них является 64-битовым представлением

текущих даты и времени и меняется для каждого нового генерируемого числа. Другое представляет собой 64-битовое начальное произвольное значение, которое обновляется в процессе вычислений.
Ключи. Генератор использует три модуля шифрования «тройного» DES. Каждый из этих трёх модулей использует одну и ту же пару 56-битовых ключей, которые должны сохраняться в секрете и использоваться только для генерирования псевдослучайных чисел.
Вывод. Выводимыми значениями являются 64-битовое псевдослучайное число и 64-битовое начальное значение.

Генератор псевдослучайных чисел ANSI X9.17.

генерирования;
Vi : начальное значение для i -

го шага генерирования;
Ri : псевдослучайное число, получаемое в результате i - го шага генерирования;
K1, K2 : ключи DES, используемые на каждом шаге генерирования.
Тогда
Ri = EDEK1,K2 [Vi EDEK1,K2 [DTi]],

Vi+1 = EDEK1,K2 [Ri EDEK1,K2 [DTi]],

где EDEK1,K2 означает последовательность «шифрования-дешифрования-шифрования» с использованием алгоритма «тройного» DES с двумя ключами.

Криптографическая надежность метода определяется факторами:

используются 112-битовый ключ и три блока шифрования EDE, в сумме дающие девятикратное шифрование DES.

Схема управляется двумя вводимыми псевдослучайными значениями: значением даты и времени и начальным значением, производимым генератором, но отличным от производимого генератором псевдослучайного значения.

два больших простых числа р и q, дающих при делении

на 4 в остатке 3,
т.е.
р ≡ q ≡ 3 (mod 4).

Это означает, что (р mod 4) ≡ (q mod 4) ≡ 3.
Например, для простых чисел 7 и 11 как раз имеем 7 ≡ 11 ≡ 3 (mod 4).

2. Пусть n = p q .

Выбирается случайное число s, взаимно простое с n —
ни р, ни q не являются делителями s.

3. Генератор BBS порождает последовательность битов Вi в соответствии с алгоритмом:
Х0 = s2 (mod n)
for i = 1 to ∞
Хi = (Хi-1)2 (mod n)
Bi = Хi (mod 2)

На каждой итерации выбирается младший бит.

503 и начального значения s = 101355.
Генератор BBS называют криптографически

защищенным генератором псевдослучайных битов.
Этот генератор удовлетворяет критерию следующего бита (next-bit test):
«Генератор псевдослучайных битов удовлетворяет критерию следующего бита, если не существует алгоритма с полиномиальной оценкой времени его выполнения, который по первым k битам выходной последовательности может предсказать ее (k+1)-й бит с вероятностью, существенно большей, чем ½».