Сдвиговый регистр с обратной связью ( FSR ) состоит из двух частей: сдвигового регистра и функции обратной связи .
Сдвиговый регистр (Error: Reference source not found) представляет собой последовательность битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является значением функции обратной связи от остальных битов регистра. Периодом сдвигового регистра называется длина получаемой последовательности до начала её повторения.
Простейшим
видом сдвигового регистра с обратной
связью является линейный сдвиговый
регистр с обратной связью (LFSR
–
Left
Feedback
Shift
Register
)
(Error: Reference source not found).
Обратная связь представляет собой
простоXORнекоторых битов
р
егистра,
перечень этих битов называетсяотводной
последовательностью
.
n -битовыйLFSRможет находиться в одном из2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом2 n -1 битов. Число внутренних состояний и период равны, потому что заполнение регистра нулями приведет к тому, что он будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно. Только при определенных отводных последовательностяхLFSRциклически пройдет через все2 n -1 внутренних состояний. ТакиеLFSRназываютсяLFSR с максимальным периодом .
Для того чтобы конкретный LFSRимел максимальный период, многочлен, образованный из отводной последовательности и константы1 должен быть примитивным по модулю2 .
Вычисление примитивности многочлена – достаточно сложная математическая задача. Поэтому существуют готовые таблицы, в которых приведены номера отводных последовательностей, обеспечивающих максимальный период генератора. Например, для 32-х битового сдвигового регистра можно найти такую запись: (32,7,5,3,2,1,0) . Это означает, что для генерации нового бита необходимо с помощью функцииXORпросуммировать тридцать второй, седьмой, пятый, третий, второй, и первый биты.
Код для такого LFSRна языке С++ будет таким:
// Любое значение кроме нуля
ShiftRegister = ((((ShiftRegister >> 31)
^ (ShiftRegister >> 6)
^ (ShiftRegister >> 4)
^ (ShiftRegister >> 2)
^ (ShiftRegister >> 1)
^ ShiftRegister)
& 0x00000001) <<31)
| (ShiftRegister >> 1);
return ShiftRegister & 0x00000001;
Программные реализации LFSRдостаточно медленны и быстрее работают, если они написаны на ассемблере, а не на С. Одним из решений является использование параллельно 16-тиLFSR(или 32 в зависимости от длины слова в архитектуре конкретного компьютера). В такой схеме используется массив слов, размер которого равен длинеLFSR, а каждый юит слова массива относится к своемуLFSR. При условии, что используются одинаковые номера отводных последовательностей, то это может дать заметный выигрыш в производительности.
С
хему
обратной связи также можно модифицировать.
При этом генератор не будет обладать
большей криптостойкостью, но его будет
легче реализовать программно. Вместо
использования для генерации нового
крайнего левого бита битов отводной
последовательности выполняетсяXORкаждого бита отводной последовательности
с выходом генератора и замена его
результатом этого действия, затем
результат генератора становится новым
левым крайним битом (Error: Reference source not found).
Эту модификацию называют конфигурацией Галуа . На языке С это выглядит следующим образом:
static unsigned long ShiftRegister = 1;
void seed_LFSR (unsigned long seed)
ShiftRegister = seed;
int Galua_LFSR (void)
if (ShiftRegister & 0x00000001) {
ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000;
ShiftRegister >>= 1;
Выигрыш состоит том, что все XORвыполняются за одну операцию. Эта схема также может быть распараллелена.
Сами по себе LFSRявляются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. ДляLFSRдлиныn внутреннее состояние представляет собой предыдущиеn выходных битов генератора. Даже если схема обратной связи хранится в секрете, то она может быть определена по2 n выходным битам генератора при помощи специальных алгоритмов. Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой последовательности, сильно коррелированны и для некоторых типов приложений не являются случайными. Несмотря на это,LFSRчасто используются для создания алгоритмов шифрования. Для этого используются несколькоLFSR, обычно с различными длинами и номерами отводных последовательностей. Ключ является начальным состоянием регистров. Каждый раз, когда необходим новый бит, все регистры сдвигаются. Эта операция называетсятактированием . Бит выхода представляет собой функцию, желательно нелинейную, некоторых битовLFSR. Эта функция называетсякомбинирующей , а генератор в целом –комбинирующим генератором . Многие из таких генераторов безопасны до сих пор.
дешифрование - p i = D (k i , c i) , как показывает рис. 7.21 .
Рис.
7.21.
Шифры потока быстрее, чем блочные шифры . Аппаратная реализация шифра потока также более проста. Когда мы должны зашифровать двоичные потоки и передать их на постоянной скорости, лучший выбор - использовать шифр потока. Шифры потока обладают большей защитой против искажения битов в течение передачи.
В современном шифре потока каждое r -битовое слово в потоке исходного текста зашифровано, используя r -битовое слово в ключевом потоке, чтобы создать соответствующее r -битовое слово в потоке зашифрованного текста .
Рис. 7.22.
Одноразовый блокнот - идеальный шифр. Он совершенен. Нет метода, который дал бы противнику возможность распознать ключ или статистику зашифрованного текста и исходного текста. Нет никаких соотношений между исходным и зашифрованным текстами. Другими словами, зашифрованный текст – настоящий случайный поток битов, даже если получить некоторые образцы исходного текста. Ева не может нарушить шифр, если она не попробует все возможные случайные ключевые потоки, которые были бы 2 n , если размер исходного текста - n -битовый. Однако при этом есть проблема. Передатчик и приемник для того, чтобы совместно использовать одноразовый блокнот ключей, должны установить соединение каждый раз, когда они хотят обменяться информацией. Они должны, так или иначе, договориться о случайном ключе. Так что этот совершенный и идеальный шифр очень трудно реализовать.
Пример 7.17
Какой вид имеет зашифрованный текст при использовании шифра одноразового блокнота в каждом из следующих случаев?
а. Исходный текст состоит из n нулей.
б. Исходный текст состоит из n единиц.
в. Исходный текст состоит из чередующихся нулей и единиц.
г. Исходный текст - случайная строчка бит.
Решение
a. Поскольку 
, то поток зашифрованного текста совпадет с ключевым потоком. Если ключ случайный, зашифрованный текст также случайный. Отрывки исходного текста в зашифрованном тексте не сохраняются.
b. Поскольку 
, где является дополнением, поток зашифрованного текста - дополнение ключевого потока. Если ключевой поток случайный, то зашифрованный текст также случайный, отрывки исходного текста не сохраняются в зашифрованном тексте.
c. В этом случае каждый бит в потоке зашифрованного текста является или тем же самым, что и в ключевом потоке, или его дополнением. Поэтому результат - также случайный, если ключевой поток случайный.
d. В данном случае зашифрованный текст явно случайный, потому что проведение операции ИСКЛЮЧАЮЩЕЕ ИЛИ двух случайных битов в результате дает случайный поток бит.
Регистр сдвига с обратной связью
Одно усовершенствование к одноразовому блокноту - ( FSR - Feedback Shift Register ). FSR может быть реализован или в программном обеспечении, или в аппаратных средствах, но для простоты мы рассмотрим аппаратную реализацию. Регистр сдвига с обратной связью состоит из регистра сдвига и функции обратной связи , как показано на рис. 7.23 .
Рис. 7.23.
Регистр сдвига – последовательность из m ячеек от b 0 до b m-1 , где каждая ячейка предназначена для сохранения единственного бита. Ячейки рассматриваются как n -битовое слово, называемое в начале "начальное значение" или источник . Всякий раз, когда необходимо получить бит на выходе (например, по сигналу в определенное время), каждый бит сдвигается на одну ячейку вправо. Это означает, что значение каждой ячейки присваивается правой соседней ячейке и принимает значение левой ячейки. Самая правая ячейка b 0 считается выходом и дает выходное значение (k i ). Крайняя левая ячейка, b m-1 , получает свое значение согласно значению информации функции обратной связи. Обозначаем выход функции с информацией обратной связи b m . Функция информации обратной связи определяет, какие значения имеют ячейки, чтобы вычислить b m . Регистр сдвига информации обратной связи может быть линейный или нелинейный.
Линейный регистр сдвига с обратной связью (LFSR) . Примем, что b m - это линейная функция b 0 , b 1 ,…..., b m-1 , для которой
Линейный регистр сдвига с обратной связью работает с двоичными цифрами, поэтому умножение и сложение находятся в поле GF(2) , так что значение C i является или 1 , или 0 , но C 0 должно быть 1 , чтобы получить информацию обратной связи на выходе. Операция сложения – это операция ИСКЛЮЧАЮЩЕЕ ИЛИ. Другими словами,
Пример 7.18
Построим линейный регистр сдвига с обратной связью с 5 -ю ячейками, в которых .
Решение
Если С i = 0, b i не играет роли в вычислении b m , то это означает, что b i не связан с функцией информации обратной связи. Если c i = 1 , b i включается в вычисление b m . В этом примере c 1 и c 3 - нули, это означает, что, мы имеем только три подключения. Рисунок 7.24 показывает схему линейного регистра сдвига с обратной связью.
Рис. 7.24.
Пример 7.19
Построим линейный регистр сдвига
с обратной связью с 4
-мя ячейками, в которых 
. Покажите значение регистра после 20
операций (сдвигов
), если исходное значение - (0001) 2
.
Решение
Рисунок 7.25 показывает схему и использование линейного регистра сдвига с обратной связью для шифрования.
Рис. 7.25.
Таблица 7.6. показывает значение потока ключей. Для каждого перехода первое значение b 4 вычисляется, а затем каждый бит сдвигается на одну ячейку вправо.
| Текущее значение | b 4 | b 3 | b 2 | b 1 | b 0 | k i |
|---|---|---|---|---|---|---|
| Начальное значение | 1 | 0 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 |
| 2 | 0 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 | 1 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 0 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 0 | 1 | 1 | 0 |
| 8 | 1 | 0 | 1 | 0 | 1 | 1 |
| 9 | 1 | 1 | 0 | 1 | 0 | 1 |
| 10 | 1 | 1 | 1 | 0 | 1 | 0 |
| 11 | 1 | 1 | 1 | 1 | 0 | 1 |
| 12 | 0 | 1 | 1 | 1 | 1 | 0 |
| 13 | 0 | 0 | 1 | 1 | 1 | 1 |
| 14 | 0 | 0 | 0 | 1 | 1 | 1 |
| 15 | 1 | 0 | 0 | 0 | 1 | 1 |
| 16 | 0 | 1 | 0 | 0 | 0 | 1 |
| 17 | 0 | 0 | 1 | 0 | 0 | 0 |
| 18 | 1 | 0 | 0 | 1 | 0 | 0 |
| 19 | 1 | 1 | 0 | 0 | 1 | 0 |
| 20 | 1 | 1 | 1 | 0 | 0 | 1 |
Заметим, что поток ключей - 1000100110101111 1001…… . Он выглядит, на первый взгляд, как случайная последовательность, но если просмотреть большое число транзакций (сдвигов), мы можем увидеть, что последовательности периодичны. Это повторение по 15 бит показано ниже.
Ключ потока генерирует с помощью линейного регистра сдвига с обратной связью псевдослучайную последовательность , в которой повторяются последовательности длиною N . Поток периодичен. Он зависит от схемы генератора и начальной информации и может быть не свыше 2 m – 1 . Каждая схема порождает m -битовые последовательности от содержащих все нули до содержащих все единицы. Однако если начальная последовательность состоит только из нулей, результат бесполезен - исходный текст был бы потоком из одних нулей. Поэтому такая начальная последовательность исключена.
Последовательности регистров сдвига используются как в криптографии, так и в теории кодирования. Их теория прекрасно проработана, потоковые шифры на базе регистров сдвига являлись рабочей лошадкой военной криптографии задолго до появления электроники.
Регистр сдвига с обратной связью (далее РгСсОС) состоит из двух частей: регистра сдвига и функции обратной связи. Регистр сдвига представляет собой последовательность битов. Количество битов определяется длиной сдвигового регистра , если длина равна n битам, то регистр называется n-битовым сдвиговым регистром . Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.
Рисунок 1. Регистр сдвига с обратной связью
Регистры сдвига очень быстро нашли применение в потоковых шифрах, так как они легко реализовывались с помощью цифровой аппаратуры. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности регистров сдвига . Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера . Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (linear feedback shift register, далее LFSR или РгСсЛОС). Обратная связь таких регистров представляет собой просто XOR (сложение по модулю два) некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа РгСсЛОС можно использовать довольно развитую математическую теорию. Проанализировав получаемые выходные последовательности, можно убедиться в том, что эти последовательности достаточно случайны, чтобы быть безопасными. РгСсЛОС чаще других сдвиговых регистров используются в криптографии.
Рисунок 2. РгСсЛОС Фиббоначи
В общем случае n-битовый РгСсЛОС может находиться в одном из N=2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом Т=2 n -1 битов. (Число внутренних состояний и период равны N=T max =2 n -1, потому что заполнение РгСсЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно). Только при определенных отводных последовательностях РгСсЛОС циклически пройдет через все 2 n -1 внутренних состояний, такие РгСсЛОС являются РгСсЛОС с максимальным периодом . Получившийся результат называется М-последовательностью .
Пример . На рисунке ниже показан 4-битовый РгСсЛОС с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:
 Номер такта сдвига (внутреннего состояния) |
Состояние регистров |
Выходной бит |
|||
|
Инициальное значение |
|||||
|
15 (возврат в инициальное состояние) |
|||||
|
16 (повтор состояний) |
Выходной последовательностью будет строка младших значащих битов: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 с периодом Т=15, общее число возможных внутренних состояний (кроме нулевого), N=2 4 -1=16-1=15=T max , следовательно, выходная последовательность - M-последовательность.
Для того чтобы конкретный РгСсЛОС имел максимальный период, многочлен, образованный из отводной последовательности и константы 1, должен быть примитивным по модулю 2. Многочлен представляется в виде суммы степеней, например многочлен степени n представляется так:
a n x n +a n-1 x n-1 + … +a 1 x 1 +a 0 x 0 =a n x n +a n-1 x n-1 + … +a 1 x+a 0 , где а i ={0,1} для i=1…n, a x i - указывает разряд.
Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x 2n?1 +1, но не является делителем x d +1 для всех d, являющихся делителями 2 n -1. Соответствующую математическую теорию можно найти в .
В общем случае не существует простого способа генерировать примитивные многочлены данной степени по модулю 2. Проще всего выбирать многочлен случайным образом и проверять, не является ли он примитивным. Это нелегко и чем-то похоже на проверку, не является ли простым случайно выбранное число - но многие математические пакеты программ умеют решать такую задачу.
Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2, приведены далее. Например, запись
(32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2: x 32 + x 7 +x 5 + x 3 + x 2 + x + 1.
Это можно легко обобщить для РгСсЛОС с максимальным периодом. Первым числом является длина РгСсЛОС. Последнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последовательность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.
Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов, получающийся РгСсЛОС будет иметь максимальную длину, циклически проходя до повторения через 2 32 -1 значений.
Рисунок 4. 32-битовый РгСсЛОС с максимальной длиной
Рассмотрим программный код РгСсЛОС, у которого отводная последовательность характеризуется многочленом (32, 7, 5, 3, 2, 1, 0). На языке C выглядит следующим образом :
static unsigned long ShiftRegister = 1;
/* Все, кроме 0. */
ShiftRegister = ((((ShiftRegister >> 31)
^(ShiftRegister >> 6)
^(ShiftRegister >> 4)
^(ShiftRegister >> 2)
^(ShiftRegister >> 1)
^ShiftRegister))
| (ShiftRegister >> 1);
return ShiftRegister & 0x00000001;}
Если сдвиговый регистр длиннее компьютерного слова, код усложняется, но не намного. В приложении B приведена таблица некоторых примитивных многочленов по модулю 2 , будем использовать ее в дальнейшем для выявления некоторых свойств этих многочленов, а также в программной реализации для задания отводной последовательности.
Следует обратить внимание, что у всех элементов таблицы нечетное число коэффициентов. Такая длинная таблица приведена для дальнейшей работы с РгСсЛОС, так как РгСсЛОС часто используются для криптографии с потоковыми шифрами и в генераторах псевдослучайных чисел. В нашем случае можно использовать многочлены со старшей степенью не более семи.
Если p(x) примитивен, то примитивен и x n p (1/x), поэтому каждый элемент таблицы на самом деле определяет два примитивных многочлена. Например, если (a, b, 0) примитивен, то примитивен и (a, a-b, 0). Если примитивен (a, b, c, d, 0), то примитивен и (a, a-d, a-c, a-b, 0). Математически:
если примитивен x a +x b +1, то примитивен и x a +x a-b +1,
если примитивен x a +x b +x c +x d +1, то примитивен и x a +x a-d +x a-c +x a-b +1. Быстрее всего программно реализуются примитивные трехчлены, так как для генерации нового бита нужно выполнять XOR только двух битов сдвигового регистра (нулевой член не учитывается, т.е. х 0 =1, см. пример выше). Действительно, все многочлены обратной связи, приведенные в таблице, являются разреженными, то есть, у них немного коэффициентов. Разреженность всегда представляет собой источник слабости, которой иногда достаточно для вскрытия алгоритма. Для криптографических алгоритмов гораздо лучше использовать плотные примитивные многочлены, те, у которых много коэффициентов. Применяя плотные многочлены, особенно в качестве части ключа, можно использовать значительно более короткие РгСсЛОС.
Генерировать плотные примитивные многочлены по модулю 2 нелегко. В общем случае для генерации примитивных многочленов степени k нужно знать разложение на множители числа 2 k -1.
Сами по себе РгСсЛОС являются хорошими генераторами псевдослучайных последовательностей, но они обладают некоторыми нежелательными неслучайными (детерминированными) свойствами. Последовательные биты линейны, что делает их бесполезными для шифрования. Для РгСсЛОС длины n внутреннее состояние представляет собой предыдущие n выходных битов генератора. Даже если схема обратной связи хранится в секрете, она может быть определена по 2n выходным битам генератора с помощью высоко эффективного алгоритма Berlekamp-Massey .
Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой последовательности, сильно коррелированны и для некоторых типов приложений вовсе не являются случайными. Несмотря на это РгСсЛОС часто используются для создания алгоритмов шифрования в качестве составных частей систем и алгоритмов шифрования.
Последовательности сдвиговых регистров используются как в криптографии, так и в теории кодирования. Их теория прекрасно проработана, потоковые шифры на базе сдвиговых регистров являлись рабочей лошадкой военной криптографии задолго до появления электроники.
Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи (рисунок 1.2.1). Сдвиговый регистр представляет собой последовательность битов. (Количество битов определяется длиной сдвигового регистра. Если длина равна n битам, то регистр называется n-битовым сдвиговым регистром.) Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.
Рис. 1.2.1.
Криптографам нравились потоковые шифры на базе сдвиговых регистров: они легко реализовывались с помощью цифровой аппаратуры. Я лишь слегка затрону математическую теорию. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности сдвиговых регистров. Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера.
Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linear feedback shift register, или LFSR) (рисунок 1.2.2). Обратная связь представляет собой просто XOR некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа LFSR можно использовать довольно развитую математическую теорию. Криптографы любят анализировать последовательности, убеждая себя, что эти последовательности достаточно случайны, чтобы быть безопасными. LFSR чаще других сдвиговых регистров используются в криптографии.
Рис. 1.2.2.
На Рис. 1.2.3 показан 4-битовый LFSR с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:
Рис. 1.2.3. 4
Выходной последовательностью будет строка младших значащих битов:
1 1 1 1 0 1 0 1 1 0 0 1 0 0 0....
n-битовый LFSR может находиться в одном из 2n-1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2n-1 битов. (Число внутренних состояний и период равны 2n-1, потому что заполнение LFSR нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях LFSR циклически пройдет через все 2n-1 внутренних состояний, такие LFSR являются LFSR с максимальным периодом. Получившийся результат называется М-последовательностью.
Для того, чтобы конкретный LFSR имел максимальный период, многочлен, образованный из отводной последовательности и константы 1, должен быть примитивным по модулю 2. Степень многочлена является длиной сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем, но не является делителем xd+1 для всех d, являющихся делителями 2n-1.
В общем случае не существует простого способа генерировать примитивные многочлены данной степени по модулю 2. Проще всего выбирать многочлен случайным образом и проверять, не является ли он примитивным. Это нелегко - и чем-то похоже на проверку, не является ли простым случайно выбранное число - но многие математические пакеты программ умеют решать такую задачу.
Некоторые, но, конечно же, не все, многочлены различных степеней, примитивные по модулю 2. Например, запись (32, 7, 5, 3, 2, 1, 0) означает, что следующий многочлен примитивен по модулю 2:
x32 + x7 +x5 + x3 + x2 + x + 1
Это можно легко обобщить для LFSR с максимальным периодом. Первым числом является длина LFSR. Последнее число всегда равно 0, и его можно опустить. Все числа, за исключением 0, задают отводную последовательность, отсчитываемую от левого края сдвигового регистра. То есть, члены многочлена с меньшей степенью соответствуют позициям ближе к правому краю регистра.
Продолжая пример, запись (32, 7, 5, 3, 2, 1, 0) означает, что для взятого 32-битового сдвигового регистра новый бит новый бит генерируется с помощью XOR тридцать второго, седьмого, пятого, третьего, второго и первого битов получающийся LFSR будет иметь максимальную длину, циклически проходя до повторения через 232-1 значений.
Регистр линейного сдвига 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
- вещественные числа из диапазона
Рис. 2. Циклическое шифрование
Режим обратной связи по выходу DES может применяться для генерации псевдослучайных чисел, аналогично тому, как он используется для поточного шифрования. Выходом каждой стадии шифрования является 64-битное значение, из которого только старшие j битов подаются обратно для шифрования. 64-битные выходы составляют последовательность псевдослучайных чисел с хорошими статистическими свойствами.
Генератор псевдослучайных чисел, описанный в стандарте ANSI X9.17, является одним из наиболее криптостойких генераторов псевдослучайных чисел. В число приложений, использующих эту технологию, входят приложения финансовой безопасности и PGP.
Генератор ANSI X9.17 состоит из следующих частей (рис. 3):
1. Вход: генератором управляют два псевдослучайных входа. Первый вход является 64-битным представлением текущих даты и времени (DT i ), которые изменяются каждый раз при создании числа. Второй вход является 64-битным начальным значением, которое инициализируется некоторым произвольным значением и изменяется в ходе генерации последовательности псевдослучайных чисел (V i ).
2. Ключи: генератор использует три модуля тройного DES с двумя ключами K 1 , K 2 . Все три используют одну и ту же пару 56-битных ключей, которая должна держаться в секрете и применяться только для генерации псевдослучайного числа.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K 1 , K 2 |
| DT i |
| V i |
| R i |
| V i+1 |
3. Выход: выход состоит из 64-битного псевдослучайного числа R i и 64-битного значения, которое будет использоваться в качестве начального значения при создании следующего числа (V i +1 ) .
Рис. 3. Генератор псевдослучайных чисел ANSI X9.17
