Алгоритмы генерации ключевого материала и оказии
Генератор Лемера
Самым популярным алгоритмом для генерирования псевдослучайных чисел является алгоритм, предложенный Лемером (Lehmer) и называемый методом линейного сравнения. Этот алгоритм имеет четыре следующих параметра.
т |
модуль сравнения |
т > 0 |
а |
множитель |
0 < а < т |
с |
приращение |
0 < с < т |
Х0 |
начальное или порождающее число |
0 < Х0 < т |
Последовательность случайных чисел {Х0} получается с помощью итераций следующего соотношения:
.
При
этом если т,
а, с и
Х0
являются
целыми, то будет получена последовательность
целых чисел из диапазона
.
Выбор
значений для а,
с и
т
оказывается
очень важным с точки зрения разработки
хорошего генератора случайных чисел.
Рассмотрим, например, случай
.
Порождаемая при этом последовательность
очевидно не будет удовлетворительной.
Теперь рассмотрим значения
.
В
этом
случае генерируется последовательность
{7, 17, 23, 1, 7, ...}, которая также очевидно
не будет удовлетворительной. Из 32
возможных значений здесь оказывается
задействованными только 4 (в данном
случае говорят, что последовательность
имеет период 4). Если же, оставив другие
значения прежними, изменить значение
а
и
положить а=5,
то результирующей последовательностью
будет {1, 5, 25, 29, 17, 21, 9, 13, 1, ...} и ее период
будет уже равен 8.
Генератор BBS
Один
из популярных подходов к генерированию
псевдослучайных последовательностей
заключается в использовании генератора
Блюма-Блюма-Шуба (Blum-Blum-Shub,
BBS),
названный так в честь его разработчиков.
Доказательство его криптографической
надежности является, пожалуй, наиболее
строгим из опубликованных. Заложенная
в его алгоритм процедура выглядит
следующим образом. Сначала выбирается
два больших простых числа,
и
,
дающих при делении на 4 в остатке 3, т.е.
.
Это
просто означает, что
.
Например, для простых чисел 7 и 11 мы как
раз имеем 7=11=3(mod
4).
Пусть теперь
.
Выберем случайное число
,
взаимно простое с
—
в данном случае это означает, что ни
,
ни
не
являются делителями
.
Тогда
генератор BBS
порождает последовательность битов
,
в соответствии со следующим алгоритмом.
for
to
Таким образом, на каждой итерации выбирается младший бит. В табл. 1 показан пример последовательности, полученной в результате использования алгоритма BBS. Здесь, =192649=383×503 и начальное значение =101355.
Таблица 1.
Пример генерации псевдослучайных значений согласно с алгоритмом ВВS
i |
Xi |
Bi |
i |
Xi |
Bi |
0 |
20749 |
1 |
11 |
137922 |
0 |
1 |
143135 |
1 |
12 |
123175 |
1 |
2 |
177671 |
1 |
13 |
8630 |
0 |
3 |
97048 |
0 |
14 |
114386 |
0 |
4 |
89992 |
0 |
15 |
14863 |
1 |
5 |
174051 |
1 |
16 |
133015 |
1 |
6 |
80649 |
1 |
17 |
106065 |
1 |
7 |
45663 |
1 |
18 |
45870 |
0 |
8 |
69442 |
0 |
19 |
137171 |
1 |
9 |
186894 |
0 |
20 |
48060 |
0 |
10 |
177046 |
0 |
|
||
Варианты индивидуальных заданий
Номер варианта |
Схема системы |
Алгоритм шифрования |
Алгоритм хэширования |
1 |
1 |
1 |
1 |
2 |
2 |
2 |
1 |
3 |
3 |
3 |
1 |
4 |
1 |
4 |
1 |
5 |
2 |
1 |
1 |
6 |
3 |
2 |
1 |
7 |
1 |
3 |
1 |
8 |
2 |
4 |
1 |
9 |
3 |
1 |
1 |
10 |
1 |
2 |
1 |
11 |
2 |
3 |
2 |
12 |
3 |
4 |
2 |
13 |
1 |
1 |
2 |
14 |
2 |
2 |
2 |
15 |
3 |
3 |
2 |
16 |
1 |
4 |
2 |
17 |
2 |
1 |
2 |
18 |
3 |
2 |
2 |
19 |
1 |
3 |
2 |
20 |
2 |
4 |
2 |
21 |
3 |
1 |
3 |
22 |
1 |
2 |
3 |
23 |
2 |
3 |
3 |
24 |
3 |
4 |
3 |
25 |
1 |
1 |
3 |
26 |
2 |
2 |
3 |
27 |
3 |
3 |
3 |
28 |
1 |
4 |
3 |
29 |
2 |
1 |
3 |
30 |
3 |
2 |
3 |