Математические основы криптологии. Галуев Г.А. - 51 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

101
можно толковать и как сложность закона генерации псевдослу-
чайной последовательности чисел. Если по достаточно длинно-
му отрезку этой последовательности нельзя ни статистически,
ни аналитически определить этот закон генерации, то в принци-
пе этим можно удовлетвориться.
И, наконец, третье требование должно гарантировать воз-
можность практической реализации генераторов псевдослучай-
ных последовательностей с
учетом требуемого быстродействия
и удобства практичного использования.
Рассмотрим теперь некоторые практические методы полу-
чения псевдослучайных чисел. Одним из первых таких методов
был метод, предложенный в 1946 году Д. фон Нейманом. Этот
метод базировался на том, что каждое последующее число в
псевдослучайной последовательности формировалось возведе-
нием предыдущего числа в квадрат и отбрасыванием
цифр с
обоих концов. Однако этот метод оказался ненадежным, и от не-
го быстро отказались. Другим методом является так называемый
конгруэнтный способ. Его математическое выражение имеет
вид:
).(mod
1
mckgg
nn
+=
+
Здесь каждое последующее случайное число
1+n
g получа-
ется умножением предыдущего числа
n
g на k сложением с c и
взятием остатка от деления на
m. Главной проблемой здесь было
подобрать хорошие значения коэффициентов
k, c, m. Выбор в
качестве
k, c, m иррациональных чисел, требующих для своего
представления бесконечного числа знаков, практически не реа-
лизуем. Выбор почти иррациональных чисел представленных,
например, 4 байтами в формате с плавающей запятой, дает псев-
дослучайные последовательности с периодами всего лишь 1225
и 147 в зависимости от начального заполнения. Исследования
показали, что более эффективно вести вычисления в целых чис-
лах.
Для них, в частности, было показано, что при c = 0,
n
m 2= наибольшей период составит m/4 при k = 3+8j или k =
5+8j
и нечетном начальном числе. При этом при достаточно
больших
к последовательность производит впечатление случай-
102
ной. Дальнейшие исследования показали, что если
c нечетно, а k
= 1+4, то период можно увеличить до числа
n
m 2= . После дол-
гих поисков числа
k исследователи остановились на значениях k
= 69069 и k = 71365.
Интересный класс генераторов псевдослучайных последо-
вательностей основан на использовании
последовательностей
Фибоначчи. Классический пример такой последовательности
{0,1,1,2,3,5,8,13,21,34 …} - за исключением первых двух ее
членов, каждый последующий член равен сумме двух предыду-
щих.
Если брать только последнюю получающуюся в результате
суммирования цифру, то получим
{0,1,1,2,3,5,8,3,1,4 …} Если
ввести в схему Фибоначчи «бит переноса», который может
иметь начальные значения
0 или 1, то можно построить генера-
тор сложения с переносом, который по своим свойствам превос-
ходит конгруэнтные генераторы.
И, наконец, построение псевдослучайных последователь-
ностей с гарантированно хорошими для криптографии свойст-
вами (максимальная длина периода, равномерный спектр) воз-
можно путем использования аппарата и результатов теории ли-
нейных рекуррентных последовательностей над конечными по-
лями,
о которых мы подробно говорили на прошлых лекциях.
Получаемые при помощи рассмотренных методов псевдо-
случайные последовательности, используются в поточных крип-
тосистемах для игнорирования сообщений путем использования
различных типов шифров замены. Например, для шифрования
сообщений может быть использована та или иная модификация
известной уже вам системы Вернама:
k
mc
γ
⊕
=
, где
k
γ
- псев-
дослучайная последовательность чисел, определяемая секрет-
ным ключом
k.
Примерами стандартизованных алгоритмов блочных крип-
тосистем являются американский стандарт
DES (режим элек-
тронной кодовой книги
ЕСВ) и российский стандарт ГОСТ
28147-89 (режим простой замены). Поскольку описание этих ал-
горитмов носит закрытый характер, проиллюстрируем работу
блочных алгоритмов на примере описания работы криптосистем

Страницы