Регистр линейного сдвига с обратной связью

Регистр линейного сдвига c обратной связью (Linear Feedback Shift Register - LFSR) – механизм создания псевдослучайной последовательности двоичных битов. Регистр (рис. 1) состоит из ряда ячеек, которые устанавливаются вектором инициализации (чаще всего секретным ключом). Работа регистра определяется наличием или отсутствием связи от каждого разряда к обратной связи. Отводы регистра с обратной связью не фиксированы, а являются частью ключа. На очередном шаге содержимое ячеек регистра сдвигается на одну позицию вправо, а один бит, оставшийся в результате операции XOR свободным, помещается в крайнюю левую ячейку.

Рис. 1. Линейный регистр сдвига с обратной связью

Для достижения максимального периода гаммы шифра число разрядов m сдвигового регистра выбирается равным одному из простых чисел Мерсенна (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 …), а внутренние связи регистра должны выбираться в соответствии с неприводимыми примитивными многочленами со старшей степенью m. В этом случае период гаммы шифра может достигать (2^m-1).

LFSR быстро работает и легко реализуется как программно, так и аппаратно. При грамотном выборе битов обратной связи генерируемые последовательности имеют хорошие статистические свойства. LFSR используется как базовый элемент для построения высоко защищенных систем.

Каскад регистров – набор LFSR, связанных таким образом, что поведение одного регистра LFSR зависит от поведения предыдущего регистра LFSR в каскаде. Такое «зависимое» поведение обычно организуется для управления с помощью первого LFSR счетчиком сдвигов следующего за ним LFSR.

Например, регистр сдвигается на один шаг, если значение предшествующего регистра – 1, а если значение 0, то регистр сдвигается на два шага или как-то иначе. Большое количество подобных сочетаний позволяет обеспечить весьма высокую безопасность.

Наиболее криптостойкие последовательности дает сжимающий генератор (shrinking generator), основанный на простом взаимодействии между результатами двух регистров LFSR. Биты одного результата определяют, будут ли соответствующие биты второго результата использоваться как часть полного «потокового ключа». Сжимающий генератор прост, масштабируем и имеет хорошие защитные свойства. Его недостаток состоит в том, что скорость генерации «потокового ключа» не будет постоянной, если не принять некоторых предосторожностей.

Метод Фибоначчи с запаздываниямиОдин из широко распространённых фибоначчиевых генераторов основан на следующей итеративной формуле:

где Y_k - вещественные числа из диапазона [0, 1); a, b - целые положительные числа, называемые лагами. Для работы фибоначчиеву генератору требуется знать max(a, b) предыдущих сгенерированных случайных чисел. При программной реализации для хранения сгенерированных случайных чисел используется конечная циклическая очередь на базе массива. Для старта фибоначчиевому данному алгоритму требуется max(a, b) случайных чисел, которые могут быть сгенерированы простым конгруэнтным генератором.

Лаги a и b не следует выбирать произвольно. Рекомендуются следующие пары значений лагов: a=17, b=5; a=55, b=24; a=97, b=33. Качество получаемых случайных чисел зависит от значения константы a, чем оно больше, тем выше размерность пространства, в котором сохраняется равномерность случайных векторов, образованных из полученных случайных чисел. В то же время, с увеличением величины константы a увеличивается объём используемой алгоритмом памяти.Значения a = 17, b = 5 можно рекомендовать для простых приложений. Значения a = 55, b = 24 позволяют получать числа, удовлетворительные для большинства алгоритмов, требовательных к качеству случайных чисел. Значения a = 97, b = 33 позволяют получать очень качественные случайные числа и используются в алгоритмах, работающих со случайными векторами высокой размерности.Получаемые случайные числа обладают хорошими статистическими свойствами, причём все биты случайного числа равнозначны по статистическим свойствам. Период фибоначчиева датчика может быть оценен по следующей формуле: где n - число битов в мантиссе вещественного числа.

Алгоритм Блюма, Блюма и ШубаГенератор BBS основан на следующей итеративной формуле: где m=pq является произведением двух больших простых p и q. На каждом шаге алгоритма выходные данные получаются из Y_n путём взятия либо бита чётности, либо одного или больше наименее значимых бит Y_n .Два простых числа, p и q, должны быть сравнимы с числом 3 по модулю 4, т.е. (p – 3) ≡ 0 (mod 4) и (q – 3) ≡ 0 (mod 4). Данный генератор имеет необычно высокую стойкость, которая обеспечивается качеством генератора исходя из вычислительной сложности задачи факторизации чисел.

Криптографически созданные случайные числа В криптографических приложениях целесообразно шифровать получающиеся случайные числа. Чаще всего используется три способа: 1) циклическое шифрование; 2) режим обратной связи по выходу одного из симметричных блочных алгоритмов;3) генератор псевдослучайных чисел ANSI X9.17.В случае циклического шифрования в качестве входа в шифрующее устройство используется счетчик с периодом N (рис. 2). Например, в случае использования 56-битного ключа DES может применяться счетчик с периодом 2⁵⁶. После каждого созданного ключа значение счетчика увеличивается на 1. Таким образом, каждое выходное значение Х₀, Х₁,...Х_N-1 основано на различных значениях счетчика и, следовательно, получаемые числа не равны между собой.

Рис. 2. Циклическое шифрование

Режим обратной связи по выходу DES может применяться для генерации псевдослучайных чисел, аналогично тому, как он используется для поточного шифрования. Выходом каждой стадии шифрования является 64-битное значение, из которого только старшие j битов подаются обратно для шифрования. 64-битные выходы составляют последовательность псевдослучайных чисел с хорошими статистическими свойствами.

Генератор псевдослучайных чисел, описанный в стандарте ANSI X9.17, является одним из наиболее криптостойких генераторов псевдослучайных чисел. В число приложений, использующих эту технологию, входят приложения финансовой безопасности и PGP.

Генератор ANSI X9.17 состоит из следующих частей (рис. 3):

1. Вход: генератором управляют два псевдослучайных входа. Первый вход является 64-битным представлением текущих даты и времени (DT_i), которые изменяются каждый раз при создании числа. Второй вход является 64-битным начальным значением, которое инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел (V_i).

2. Ключи: генератор использует три модуля тройного DES с двумя ключами K₁, K₂. Все три используют одну и ту же пару 56-битных ключей, которая должна держаться в секрете и применяться только для генерации псевдослучайного числа.

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