Конгруэнтные датчики ПСЧ для гаммирования

Одним из хороших конгруэнтных генераторов является линейный конгруэнтный датчик ПСЧ. Он вырабатывает последовательности псевдослучайных чисел T(i), описываемые соотношением

T(i+1) = (A*T(i)+C)mod m,

где А и С - константы, Т(0) - исходная величина, выбранная в качестве порождающего числа. Очевидно, что эти три величины и образуют ключ.

Такой датчик ПСЧ генерирует псевдослучайные числа с определенным периодом повторения, зависящим от выбранных значений А и С. Значение m обычно устанавливается равным 2n , где n - длина машинного слова в битах. Датчик имеет максимальный период М до того, как генерируемая последовательность начнет повторяться. По причине, отмеченной ранее, необходимо выбирать числа А и С такие, чтобы период М был максимальным. Как показано Д. Кнутом, линейный конгруэнтный датчик ПСЧ имеет максимальную длину М тогда и только тогда, когда С - нечетное, и Аmod 4 = 1.

Целочисленные последовательности

Интересный класс генераторов случайных чисел неоднократно предлагался многими специалистами целочисленной арифметике, в частности Джорджем Марсалиа и Арифом Зейманом. Генераторы этого типа основаны на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34...}. За исключением первых двух ее членов, каждый последующий член равен сумме двух предшествующих. Если брать только последнюю цифру каждого числа в последовательности, то получится последовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5, 9, 4...} Если эта последовательность применяется для начального заполнения массива большой длины, то, используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа. Марсалиа и Зейман предложили ввести в схему Фибоначчи "бит переноса", который может иметь начальное значение 0 или 1. Построенный на этой основе генератор "сложения с переносом" приобретает интересные свойства, на их основании можно создавать последовательности, период которых значительно больше, чем у применяемых в настоящее время конгруэнтных генераторов.

Датчики М-последовательностей

М-последовательности также популярны, благодаря относительной легкости их реализации.

М-последовательности представляют собой линейные рекуррентные последовательности максимального периода, формируемые k-разрядными генераторами на основе регистров сдвига. На каждом такте поступивший бит сдвигает k предыдущих и к нему добавляется их сумма по модулю 2. Вытесняемый бит добавляется к гамме.

Строго это можно представить в виде следующих отношений:

r₁:=r₀ r₂:=r₁ ... r_k-1:=r_k-2

r₀:=a₀ r₁ Å a₁ r₂ Å ... Å a_k-2 r_k-1

Г_i:= r_k-

Здесь r₀ r₁ ... r_k-1 - k однобитных регистров, a₀ a₁ ... a_k-1 - коэффициенты неприводимого двоичного полинома степени k-1. Г_i - i-е значение выходной гаммы.

Период М-последовательности исходя из ее свойств равен 2^k-1.

Другим важным свойством М-последовательности является объем ансамбля, т.е. количество различных М-последовательностей для заданного k. Эта характеристика приведена в таблице:

Метод псевдослучайного гаммирования

Этот метод похож на метод гаммирования, но к нему добавляется еще модификация ключа. В данном случае ключ модифицируется по случайному закону по формуле

где С mod 4 = 1,

N+1 - максимальное псевдослучайное число этого ряда,

 - ключ для предыдущей итерации;

Ki- ключ для новой итерации.

Метод цепочечного гаммирования

Метод аналогичен методу гаммирования, но ключ изменяется по-другому. Суть метода: имеется последовательность ключей (например, 16). Каждый ключ содержит в себе 12 разрядов ключевого числа для кодирования и 4 разряда для указания следующего ключа в цепочке. После использования ключа берем новый по адресу, указанному в текущем ключе.

Список литературы

1. Гатчин Ю.А., Коробейников А.Г. Основы криптографических алгоритмов. Учебное пособие. - СПб.: СПбГИТМО(ТУ), 2002. - 29 с.

2. Главная редакция физико-математической литературы, 1974. 324с.

3. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. – М.: КУДИЦ-ОБРАЗ, 2001, - 368 с.

4. Кон П. Универсальная алгебра. - М.: Мир. - 1968. 351 с

5. Коробейников А. Г. Математические основы криптографии. Учебное пособие. СПб: СПб ГИТМО (ТУ), 2002. 41 с

6. Левин Максим. Криптография. Руководство пользователя. - М.: Познавательная книга плюс, 2001, - 320 с.

7. Левин М. Криптография. Руководство пользователя. - М.: Познавательная книга плюс, 2001, - 320 с.

8. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. – СПб.: Издательство "Лань", 2001, - 224 с.

9. Панасенко С.П. Алгоритмы шифрования. Специальный справочник BHV-Санкт-Петербург, 2009. – 576с.

10. Смирнов В.И. Курс высшей математики, том III, часть I – М:. Наука,

11. Чмора А.Л. Современная прикладная криптография. 2-е изд. – М.: Гелиос, АРВ, 2002. – 256 с. ил.