Теоретические основы работы. Введение в основы современных шифров с симметричным ключом Линейный регистр сдвига пример

Рис. 7.21.

Шифры потока быстрее, чем блочные шифры . Аппаратная реализация шифра потока также более проста. Когда мы должны зашифровать двоичные потоки и передать их на постоянной скорости, лучший выбор - использовать шифр потока. Шифры потока обладают большей защитой против искажения битов в течение передачи.

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

Одноразовый блокнот - идеальный шифр. Он совершенен. Нет метода, который дал бы противнику возможность распознать ключ или статистику зашифрованного текста и исходного текста. Нет никаких соотношений между исходным и зашифрованным текстами. Другими словами, зашифрованный текст – настоящий случайный поток битов, даже если получить некоторые образцы исходного текста. Ева не может нарушить шифр, если она не попробует все возможные случайные ключевые потоки, которые были бы 2 n , если размер исходного текста - n -битовый. Однако при этом есть проблема. Передатчик и приемник для того, чтобы совместно использовать одноразовый блокнот ключей, должны установить соединение каждый раз, когда они хотят обменяться информацией. Они должны, так или иначе, договориться о случайном ключе. Так что этот совершенный и идеальный шифр очень трудно реализовать.

Пример 7.17

Какой вид имеет зашифрованный текст при использовании шифра одноразового блокнота в каждом из следующих случаев?

а. Исходный текст состоит из n нулей.

б. Исходный текст состоит из n единиц.

в. Исходный текст состоит из чередующихся нулей и единиц.

г. Исходный текст - случайная строчка бит.

Решение

a. Поскольку , то поток зашифрованного текста совпадет с ключевым потоком. Если ключ случайный, зашифрованный текст также случайный. Отрывки исходного текста в зашифрованном тексте не сохраняются.

b. Поскольку , где является дополнением, поток зашифрованного текста - дополнение ключевого потока. Если ключевой поток случайный, то зашифрованный текст также случайный, отрывки исходного текста не сохраняются в зашифрованном тексте.

c. В этом случае каждый бит в потоке зашифрованного текста является или тем же самым, что и в ключевом потоке, или его дополнением. Поэтому результат - также случайный, если ключевой поток случайный.

d. В данном случае зашифрованный текст явно случайный, потому что проведение операции ИСКЛЮЧАЮЩЕЕ ИЛИ двух случайных битов в результате дает случайный поток бит.

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

Одно усовершенствование к одноразовому блокноту - ( FSR - Feedback Shift Register ). FSR может быть реализован или в программном обеспечении, или в аппаратных средствах, но для простоты мы рассмотрим аппаратную реализацию. Регистр сдвига с обратной связью состоит из регистра сдвига и функции обратной связи , как показано на рис. 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.19

Построим линейный регистр сдвига с обратной связью с 4 -мя ячейками, в которых . Покажите значение регистра после 20 операций (сдвигов ), если исходное значение - (0001) 2 .

Решение

Рисунок 7.25 показывает схему и использование линейного регистра сдвига с обратной связью для шифрования.

Таблица 7.6. показывает значение потока ключей. Для каждого перехода первое значение b 4 вычисляется, а затем каждый бит сдвигается на одну ячейку вправо.

Заметим, что поток ключей - 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 .

Кроме того, большие случайные числа, генерируемые с использованием идущих подряд битов этой последовательности, сильно коррелированны и для некоторых типов приложений вовсе не являются случайными. Несмотря на это РгСсЛОС часто используются для создания алгоритмов шифрования в качестве составных частей систем и алгоритмов шифрования.

- «Tetromino tennis»). Он создал и решил бесчисленное количество математических головоломок и каламбуров. Лет 20 назад я узнал, что он был очень близок к открытию моего любимого правила 30 для клеточных автоматов еще в 1959 году, когда я только родился.

Как я встретил Сола Голомба

Семья Голомб жила в доме, расположенном в горах близ Пасадены. У них было две дочери: Астрид - немного старше меня, честолюбивая голливудская девушка, и Беатрис - примерно моего возраста и научного склада ума. Сестры Голомб часто устраивали вечеринки - как правило, у себя дома. Темы были разные: это и вечеринка в саду и крокет с фламинго и ежами ("победителем станет тот, чей костюм более всего будет соответствовать заявленной теме "), или вечеринка в стиле Стоунхендж с инструкциями, написанными рунами. На этих вечеринках пересекались молодые и не очень люди, в том числе - различные местные светила. И на них, немного в стороне, присутствовал всегда маленький человек с большой бородой, немного похожий на эльфа и носивший всегда темное пальто, - сам Соломон Голомб.

Постепенно я узнал немного о нем. То, что он был вовлечен в "теорию информации ". То, что он работал в Университете Южной Калифорнии . То, что у него были различные неопределенные, но, по-видимому, высокоуровневые правительственные и другие связи. Я слышал про регистры сдвига, но практически ничего не знал о них.

Вот что происходит через некоторое время:

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

Если регистр сдвига имеет размер n, то у него есть 2 n возможных состояний (соответствующих всем возможным последовательностям 0 и 1 при длине n ). Поскольку правила для регистра сдвига детерминированы, любое данное положение должно всегда прийти к другому такому же положению. А это означает, что максимально возможное число шагов, которое регистр сдвига может пройти, прежде чем шаги начнут повторяться, равно 2 n (на самом деле 2 n - 1, так как положение со всеми 0 не может эволюционировать во что-нибудь еще).

В приведенном выше примере, регистр сдвига имеет размер 7 и повторится ровно через 2 7 - 1 = 127 шагов. Но какие регистры сдвига - с какими расположениями ответвлений - будут производить последовательности максимальной длины? Это вопрос Соломон Голомб начал исследовать летом 1954 года. И его ответ был прост и элегантен.

Регистр сдвига приведенный выше имеет ответвления в положениях 7, 6 и 1. Сол представил это алгебраически, используя многочлен х 7 + х 6 + 1. Он показал тогда, что генерируемая последовательность будет максимальной длины, если этот многочлен "неприводим по модулю 2 "; поэтому он не может быть факторизован, что делает его аналогом простого числа среди многочленов; а наличие некоторых других свойств делает его "примитивным многочленом ". На сегодняшний день это легко проверить с помощью системы Mathematica и языка Wolfram Language :

Тогда, в 1954 году, Сол должен был делать всё это вручную; он составил довольно длинную таблицу примитивных многочленов, соответствующих регистрам сдвига, которые выдавали последовательности максимальной длины:

Предыстория регистров сдвига

Основная идея криптографии - изменение осмысленных сообщений таким образом, чтобы их нельзя было распознать; при этом, если вы знаете ключ, вы сможете воссоздать зашифрованное сообщение. Так называемые потоковые шифры работают по принципу создания длинных последовательностей как бы случайных элементов, и декодируются с помощью приемника, самостоятельно генерирующего ту же последовательность элементов.

Регистры сдвига с линейной обратной связью ценились в криптографии из-за длинных периодов повтора. Однако математический анализ, который Сол использовал, чтобы найти эти периоды, дает понять, что такие регистры сдвига не годятся для безопасной криптографии. Однако в начале они казались неплохими (особенно в сравнении с последовательными положениями ротора в Энигме); ходили упорные слухи, что на этой основе строились советские военные криптосистемы.

Еще в 2001 году, когда я работал над историческими заметками для моей книги Новый вид науки , мы с Солом долго говорили по телефону о сдвигах регистра. Сол сказал мне, что, когда он начинал, он ничего не знал о криптографической работе по регистрам сдвига. Он сказал, что сотрудники лаборатории Белла, лаборатории Линкольна и Лаборатории реактивного движения начали работать над регистрами сдвига примерно в то же время, что и он; однако ему удалось продвинуться немного дальше, что он и отметил в своем отчете от 1955 года.

В течение последующих лет Сол постепенно узнавал о различных предшественниках своих работ из литературы, посвященной чистой математике. Уже в 1202 году Фибоначчи говорил о том, что теперь называют числами Фибоначчи и которые генерируются рекуррентным соотношением (которое может рассматриваться как аналог регистра сдвига с линейной обратной связью, работающего с произвольными целыми числами, а не с нулями и единицами). Существуют также небольшие работы начала 1900-х по цикличности 0 и 1, однако первым крупномасштабным исследованием стала работа Ойстена Оре из Университета Осло. У Оре был студент по имени Маршалл Холл , который консультировал предшественника Агентства национальной безопасности в конце 1940-х гг. - вероятно, по теме регистров сдвига. Однако все, что он делал, было засекречено, и поэтому он договорился с Солом, чтобы тот опубликовал историю регистров сдвига с линейной обратной связью; Сол посвятил свою книгу Маршаллу Холлу.

Для чего нужны последовательности, генерируемые регистрами сдвига?

В большинстве случаев используются те регистры сдвига, которые дают последовательности максимальной длины (иначе известные как "М-последовательности "). Причины, по которым они используются, как правило, связаны с некоторыми их свойствами, которые обнаружил Сол. Они всегда содержат одинаковое количество 0 и 1 (хотя на самом деле всегда есть ровно одна дополнительная 1). Впоследствии Сол показал, что им также свойственно одинаковое количество последовательностей 00, 01, 10 и 11 - и для больших блоков тоже. Это свойство "баланса " это само по себе уже очень полезно, - к примеру, если тестировать все возможные комбинации битов в качестве входных данных.

Однако Сол обнаружил еще одно, даже более важное свойство. Замените каждый 0 в последовательности на 1, затем умножьте каждый элемент в сдвинутой версии последовательности на соответствующий элемент оригинала. Сол показал, что при сложении эти элементы всегда будут равны нулю (кроме случаев, когда никакого сдвига нет вообще). То есть последовательность не имеет никакой корреляции со сдвинутыми версиями самой себя.

Эти свойства будут верны для любой достаточно длинной случайной последовательности из 0 и 1. Удивительно, что для последовательностей максимальной длины эти свойства всегда верны. Последовательности имеют некоторые черты хаотичности, однако на самом деле они вовсе не хаотичны: они имеют вполне определенную, организованную структуру .

Именно эта структура, свойственная регистрам сдвига с линейной обратной связью, делает их непригодными для серьезной криптографии. Но они прекрасно подходят для базовой «перестановки элементов» и дешевой криптографии и активно используются для этих целей. Часто стоит задача просто «отбелить» сигнал (как в «белом шуме»). Иногда нужно передавать данные с длинными последовательностями 0. Но электроника в таком случае может запутаться, если «молчание» будет слишком долгим. Можно избежать этой проблемы через скремблинг исходных данных путем объединения его с последовательностью, генерируемую регистром сдвига. Именно это было сделано с Wi-Fi , Bluetooth , USB , цифровым TV , интернетом и т. д.

Побочный эффект скремблинга регистра сдвига - более сложное декодирование, что используется иногда для повышения безопасности (в технологии DVD для кодирования данных используется комбинация регистров сдвига с длиной 16 и 24 бита; многие GSM телефоны используют комбинацию из трех регистров сдвига для кодирования всех сигналов).

Сол создал математическую основу для всего этого, а также перезнакомил друг с другом ряд ключевых фигур. Еще в 1959 году он познакомился с Ирвином Джейкобсом , который недавно получил докторскую степень в Массачусетском технологическом институте. Также он был знаком с Энди Витерби , который работал в Лаборатории реактивного движения. Сол познакомил их, и в 1968 году они основали компанию под названием Linkabit , работавшую над системами кодирования (в основном для военных целей).

В 1985 году Джейкобс и Витерби основали еще одну компанию под названием Qualcomm . Сначала дела у них шли не особенно хорошо, но к началу 1990-х годов, когда они начали производить компоненты для развертывания CDMA в сотовых телефонах, компания начала стремительно расти.

Ну и где же эти регистры?

Если рассматривать мобильные телефоны, то использование в них последовательностей, генерируемых регистрами сдвига, менялось на протяжении многих лет, - то увеличиваясь, то уменьшаясь. сети основаны на TDMA, так что для кодирования своих данных не используют последовательности, генерируемые регистрами сдвига, однако до сих пор часто используют CRC (циклический избыточный код) для проверки блоков данных. сети - крупнейшие пользователи CDMA, так что последовательности, генерируемые регистрами сдвига, задействованы в передаче каждого бита. сети обычно используют сочетание времени и частоты слотов, не включающих последовательности регистров сдвига, хотя CRC еще используются: например, чтобы взаимодействовать с целостными данными, когда частотные окна перекрывают друг друга. имеет более сложную структуру - с множеством антенн, динамически адаптирующихся для использования оптимального времени и частоты слотов. Однако половина их каналов, как правило, выделяется для «пилот-сигналов», которые используются для выведения локальной радиосреды; в их основе также лежат последовательности, генерируемые регистрами сдвига.

При производстве электроники обычно стараются достичь наиболее высокой скорости передачи данных при минимальных энергозатратах, позволяющих битам преодолевать шумовой порог. И, как правило, этот путь приводит к автоматизации обнаружения ошибок, - а значит, к использованию CRC (циклического избыточного кода) и, следовательно, последовательностей, генерируемых сдвиговым регистром. Это касается практически всех видов шин внутри компьютера (PCIe , SATA и т. д.): обеспечивающих взаимодействие частей центрального процессора, или получение данных с устройств, или подключение к дисплею с HDMI . В случае с дисками или с памятью CRC и другие коды, основанные на последовательностях, генерируемых регистрами сдвига, также практически повсеместно используются для работы на максимальной скорости.

Регистры сдвига настолько вездесущи, что практически невозможно оценить, сколько бит ими генерируется. Существует примерно 10 миллиардов компьютеров, чуть меньше - телефонов, и огромное количество устройств во встроенным IoT («интернетом вещей») . Почти у каждого автомобиля в мире (а их больше миллиарда!) - около 10 встроенных микропроцессоров.

На какой частоте работают регистры сдвига? В системах связи есть базовая несущая частота в герцовом диапазоне, а также «скорость передачи элементов сигнала», которая говорит о том, как быстро осуществляется множественный доступ (речь идет о CDMA) в диапазоне МГц. С другой стороны, в шинах внутри компьютеров все данные передаются с помощью регистров сдвига - с наилучшей скоростью передачи в герцовом диапазоне.

Существует по крайней мере 10 миллиардов линий связи, работающих по крайней мере 1/10 миллиарда секунд (около 3-х лет), которые используют по меньшей мере 1 миллиард битов из сдвиговых регистров каждую секунду, что означает, что на сегодняшний день алгоритм Сола был использован по крайней мере октиллион раз.

Действительно ли этот алгоритм используется наиболее часто? Думаю, да. Я подозреваю, что конкуренцию могут составить только арифметические операции. В наши дни процессоры способны проводить триллион арифметических операций в секунду, и такие операции необходимы для почти каждого бита, генерируемого с помощью компьютера. Но как выполняется арифметика? На каком-то уровне это просто реализация цифровой электроники.

Однако есть «алгоритмические идеи», которые остаются непонятными для всех, кроме дизайнеров микропроцессоров. Когда Бэббидж делал свою разностную машину (см. статью на Хабре "Распутывая историю Ады Лавлейс (первого программиста в истории) "), переносы стали большой помехой в выполнении арифметических операций (на самом деле, о регистре сдвига с линейной обратной связью можно думать как о системе, которая делает что-то вроде арифметических вычислений, но не осуществляет перенос). Существуют «деревья распространения сигнала переноса», оптимизирующие перенос. Есть также маленькие хитрости (вроде "алгоритма Бута ", " деревьев Уоллеса " и т. д.), которые уменьшают количество битовых операций, необходимых для создания «внутренностей» арифметики. Но, в отличие от регистров сдвига с линейной обратной связью, единой алгоритмической идеи, которая использовалась бы практически где угодно, просто не существует; поэтому я думаю, что максимально длинные последовательности, генерируемые регистрами сдвига с линейной обратной связью, все-таки побеждают среди наиболее используемых последовательностей.

Клеточные автоматы и регистры сдвига с нелинейной обратной связью

Чтобы увидеть, как они связаны между собой, нужно запустить регистр сдвига с обратной связью размера n , и при этом отображать его состояние только каждые n шагов; другими словами, дать всем битам перезаписаться до повторного их появления. Если отображается каждый шаг регистра сдвига с линейной обратной связью (здесь - с двумя ответвлениями), то на каждом из шагов все сместится влево - и все. Но если сделать сжатую картинку, показывая только каждые n шагов, станет видна закономерность.

Это вложенный паттерн; и эта картина очень похожа на ту, которую можно получить в случае, если клеточный автомат возьмет клетку и соседнюю с ней и сложит их по модулю 2 (XOR). Вот что происходит с клеточным автоматом, если он располагает свои клетки так, что они находятся в окружности того же размера, что и регистр сдвига выше:

Вначале клеточные автоматы и паттерны сдвигового регистра оказываются точно такими же. Если посмотреть на эти картинки, становится менее удивительно, что математика регистров сдвига должна иметь отношение к клеточным автоматам. И, учитывая повторяемость вложенных паттернов, становится ясно, почему должна существовать элегантная математическая теория регистров сдвига.

Для типичных регистров сдвига, используемых на практике, не свойственны такие явно повторяющиеся паттерны. Вот несколько примеров регистров сдвига, которые генерируют последовательности максимальной длины. Факт в том, что ответвления находятся далеко друг от друга, что затрудняет нахождение визуальных следов вложенности.

Насколько же широко соответствие между регистрами сдвига и клеточными автоматами? Для клеточных автоматов правила генерации новых значений ячеек могут быть какими угодно. В регистрах сдвига с линейной обратной связью они всегда должны быть основаны на сложении по модулю 2 (или XOR). Это то, что означает «линейная» часть «регистра сдвига с линейной обратной связью». Также возможно использование любого правила для объединения значений для регистров сдвига с нелинейной обратной связью (NFSR).

И в самом деле: когда Сол разработал свою теорию для регистров сдвига с линейной обратной связью, он начал с нелинейного случая. Когда он прибыл в JPL в 1956 году, он получил лабораторию, укомплектованную стойками для маленьких электронных модулей. Сол рассказывал, что модули (каждый из которых был размером с сигаретную пачку) были построены для проекта Bell Labs для выполнения определенной логической операции (AND, OR, NOT, ...). Модули могут быть использованы вместе для реализации любых желаемых регистров сдвига с нелинейной обратной связью, обеспечивая около миллиона бит в секунду (Сол сказал мне, что кто-то пытался сделать то же самое с помощью универсального компьютера, и то, что заняло 1 секунду при использовании аппаратных модулей, потребовало 6 недель работы на универсальном компьютере).

Когда Сол стал изучать регистры сдвига с линейной обратной связью, первым его серьезным открытием стали периоды их повторения. И в случае с нелинейными он большую часть своих усилий направил на попытки понять то же самое. Он собрал все виды экспериментальных данных. Он рассказал мне, что он проверял даже последовательности длиной 2 45 , что потребовало год. Он сделал резюме, как на картинке ниже (обратите внимание на визуализацию последовательностей, показанных на линии осциллограммы). Но ему так и не удалось придумать какой-то общей теории, какая была у него для регистров сдвига с линейной обратной связью.

Неудивительно, что он не смог этого сделать. Уже в 1950-е годы появились теоретические результаты (в большинстве случаев основанные на идеях универсальных вычислений Тьюринга), того, какие программы в принципе могли бы сделать это. Я не думаю, что Сол или кто-либо еще когда-нибудь думал, что в регистрах сдвига с нелинейной обратной связью будут применяться очень простые (нелинейные) функции.

И только позже стало ясно, насколько сложным может быть поведение даже очень простых программ. Мой любимый пример - правило 30 для клеточного автомата, в котором значения соседних ячеек объединяются с помощью функции, которая может быть представлена в виде р + q + r + q*r mod 2 (или р XOR (q OR r )). Невероятно, но Сол рассматривал регистры сдвига с нелинейной обратной связью, основанные на аналогичные функциях: р + г + s + q*r + q*s + r*s mod 2 . Вот здесь, ниже, - иллюстрации того, как функция Сола (которую можно рассматривать как "правило 29070 "), правило 30 и несколько других подобных правил выглядят в регистре сдвига:

А здесь они, не ограниченные регистром фиксированного размера, похожи на клеточные автоматы:

Конечно, Сол никогда не делал картинок вроде этой (да и это было почти нереально сделать в 1950-е годы). Вместо этого он сосредоточился на периоде повторения как своего рода совокупной характеристике.

Сол задавался вопросом о том, могут ли регистры сдвига с нелинейной обратной связью быть источниками хаотичности. Из того, что на сегодняшний день известно о клеточных автоматах, ясно, что могут. К примеру, для создания хаотичности для системы Mathematica мы в течение 25 лет использовали правило 30 клеточных автоматов (хотя недавно мы отказались от него в пользу более эффективного правила, которое мы нашли, изучив триллионы возможностей).

О шифровании Сол говорил немного; хотя я думаю, что он недолго работал на правительство. Он сказал мне, что, хотя в 1959 году он и обнаружил "многомерные корреляционные атаки на нелинейные последовательности ", в то же время он "тщательно избегал утверждений, что программа была для криптоанализа ". Дело в том, что правило 30 для клеточных автоматов (и, возможно, также регистры сдвига с нелинейной обратной связью) могут быть хорошими криптосистемами - хотя из-за того, что они как будто эквивалентны регистрам сдвига с линейной обратной связью (а это не так), они никогда не использовались настолько, насколько можно.

Будучи энтузиастом, в течение последних нескольких десятилетий я пытался изучить всех предшественников моей работы над одномерными клеточными автоматами. Двумерные клеточные автоматы были немного изучены, а вот в случае с одномерными нашлась только одна чисто теоретическая работа. Я думаю, что из всего, что я видел, регистры сдвига с нелинейной обратной связью Соломона Голомба оказались ближе всего к тому, чем я в конечном итоге занялся четверть века спустя.

Полиомино

Главный вопрос, в ответе на который Сол был заинтересован, это как наборы полиомино могут быть организованы, покрыв некоторую область. Иногда это довольно очевидно, а иногда - довольно сложно. Свою первую статью о полиомино Сол опубликовал в 1954 году, однако действительно популярным сделал полиомино Мартин Гарднер в 1957 году (он вел колонку о математических играх в журнале Scientific American ). Как пояснил Сол в предисловии к своей книге от 1964 года, в результате он получил "постоянный поток корреспондентов со всего мира и из всех слоев общества: председателей совета директоров ведущих университетов, жителей неизвестных монастырей, заключенных из известных тюрем... ".

Игровые компании также обратили внимание на новые головоломки, и в течение нескольких месяцев появились заголовки вроде "новые сенсационные головоломки ", а за ними последовали десятилетия других головоломок и игр на основе полиомино (нет, зловещий лысый парень не похож на Сола):

Сол печатал статьи о полиомино на протяжении еще 50 лет после первой публикации. В 1961 году он представил варианты деления на мелкие части "rep-tiles ", с помощью которых можно создавать фрактальные («Infin-tile») узоры. Но почти все, что Сол делал с полиомино, включало в себя решение конкретных проблем.

Меня мало интересует специфика полиомино; меня интересуют связанные с ними феномены более общего характера . Кажется, что решить, можно ли с помощью нескольких простых форм «замостить» всю плоскость, легко. Но в случае с полиомино (а также со всеми играми и головоломками, основанными на них) становится ясно, что все не так-то просто. И действительно - в 1960-е годы было доказано, что эта задача теоретически неразрешима .

Если нас интересует только ограниченная область, то, в принципе, можно просто перечислить все мыслимые расположения фигур, а затем посмотреть, располагаются ли они так, как надо. Однако если нас интересует бесконечность, то этого можно не делать. Может быть, кто-то и найдет вариант удачного размещения миллиона фигур, но нет никакой гарантии, что этот результат может быть распространен дальше.

Оказывается, это может выглядеть как работающая машина Тьюринга - или клеточный автомат. Вы начинаете с линии плиточек. Тогда вопрос о том, возможно ли бесконечное замощение, эквивалентен вопросу о том, возможна ли установка для машины Тьюринга, которая даст ей возможность не останавливаться. Дело в том, что, если машина Тьюринга универсальна (то есть ее можно запрограммировать для выполнения любых возможных вычислений), то проблема остановки для нее может быть неразрешимой, что означает, что проблема замощения также будет неразрешимой.

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

Известно, что сложные и тщательно разработанные наборы полимино фактически поддерживают универсальные вычисления. Но что насчет простого набора? Действительно ли он достаточно простой для того, чтобы случайно наткнуться на него? Если посмотреть на все те системы, которые я изучал, то самый простой набор действительно оказывается простым. Однако найти его сложно.

Значительно более простая задача заключается в нахождении полиомино, которые успешно заполняют плоскости, хотя и только непериодически. Роджер Пенроуз в 1994 году нашел подходящий пример. В моей книге Новый вид науки я привел немного более простой пример с 3 полиомино:

Остальная часть истории

Регистры сдвига и полиомино - объемные темы (они даже выведены в отдельные категории в AMS классификации). В последние десятилетия они обе получили новый виток развития, когда на их основе стали проводить компьютерные эксперименты; Сол также принимал в них активное участие. Однако многие вопросы остаются без ответов. И если для регистров сдвига с линейной обратной связью можно найти большие матрицы Адамара , то даже сейчас о регистрах сдвига с нелинейной обратной связью мало что известно, не говоря уже обо всех непериодических и иных экзотических полиомино.

Сол всегда интересовался головоломками, - как математическими, так и со словами. Некоторое время он вел колонку головоломок для Los Angeles Times , и в течение 32 лет писал "гамбиты Голомба " в журнал для выпускников Джона Хопкинса. Он принимал участие в тестировании MegaIQ и выиграл поездку в Белый дом, когда он сам и его начальник вошли в пятерку лучших в стране.

Он вкладывал огромные усилия в свою работу в университете: не только обучал студентов и руководил аспирантами и восходил по административной лестнице (президент университетского совета, вице-проректор по исследованиям и др.), но и высказывал свое мнение об управлении университетом в целом (например, написал статью, озаглавленную «Консалтинг на факультете: убрать или оставить?» ; Ответ: нет, это хорошо для университета!). В университете Южной Калифорнии он занимался хедхантингом, и за время своей работы там он помог университету подняться из неизвестности на вершину рейтинга образовательных программ.

А потом был консалтинг. Сол был дотошным и не раскрывал того, что делал для правительственных организаций. В конце 60-х гг., разочарованный тем, что все, кроме него занялись продажей игр на основе полиомино, Сол основал компанию, которую назвал Recreational Technology, Inc. Дела шли не слишком хорошо, однако Сол познакомился с Элвином Берлекэмпом - профессором из Беркли, который увлекался теориями кодирования и головоломками. Впоследствии они основали компанию Cyclotomics (в честь циклотомических многочленов вида x n – 1), которая в итоге была продана компании Kodak за круглую сумму (Берлекэмп создал также алгоритмическую торговую систему, которую он затем продал Джиму Симонсу и которая стала отправной точкой для Renaissance Technologies - одного из крупнейших на сегодняшний день хедж-фондов).

Более 10000 патентов так или иначе связаны с работами Сола, а вот сам Сол получил только один патент на криптосистемы на основе квазигрупп - и я думаю, что он мало что сделал для коммерциализации своей работы.

На протяжении многих лет Сол работал с Технионом - израильским технологическим институтом. Он говорил о себе как о "нерелигиозном ортодоксальном еврее ", но при этом иногда вел для новичков семинары по Книге Бытия, а также работал над расшифровкой частей свитков Мертвого моря (Кумранских рукописей).

Сол и его жена много путешествовали, однако «центром мира» для Сола определенно были его офис в Лос-Анджелесе в Университете Южной Калифорнии, и дом, в котором он и его жена жили в течение почти 60-ти лет. Он всегда был окружен друзьями и студентами. И у него была семья. Его дочь Астрид сыграла роль студентки в пьесе о Ричарде Фейнмане (она позировала ему), и в романе моего друга в качестве одного из персонажей. Беатрис посвятила свою карьеру применению математического уровня точности к различным видам медицинского показаний и диагностики (болезни, связанные с войной в Персидском заливе, эффекты статинов, приступы икоты и т. д.). Я даже внес свой небольшой вклад в жизнь Беатрис, познакомив ее с человеком, который стал затем ее мужем - с Терри Сейновски , одним из основателей современной вычислительной нейронауки.

Казалось, что Сол вовлечен во множество событий, даже если он не слишком распространялся о деталях. Время от времени мне хотелось поговорить с ним о науке и математике, но ему интереснее было рассказывать истории (часто очень увлекательные) как об отдельных личностях, так и об организациях ("Можете ли вы поверить, что [в 1985 году], после многолетнего отсутствия на конференциях, Клод Шеннон просто появился без предупреждения в баре на ежегодной конференции по теории информации? "; "вы знаете, сколько они должны были заплатить главе Калифорнийского технологического института, чтобы заставить его поехать в Саудовскую Аравию ? », и т. д.).

Оглядываясь назад, я понимаю, что хотел бы заинтересовать Сола в решении некоторых математических вопросов, поднятых в моей работе. Думаю, что я так и не понял, до какой степени он любил решать проблемы, предложенные другими людьми. Несмотря на значительный вклад в развитие инфраструктуры вычислительного мира, сам Сол никогда всерьез не использовал компьютеры. Он очень гордился тем, что может с легкостью проводить вычисления в уме. До 70-ти лет он не пользовался электронной почтой и никогда не пользовался компьютером дома, хотя вот мобильный телефон у него был (обычной электронной почты от него почти не приходило. Я упомянул как-то, что около года назад я изучал историю Ады Лавлейс ; он ответил: "История Ады Лавлейс как программиста Бэббиджа настолько широко распространена, что все, кажется, принимают ее как факт, однако я никогда не видел источников по этому вопросу. ").

Дочери Сола несколько лет назад организовали вечеринку по поводу его 80-летия и создали такие интересные приглашения:

У Сола были определенные проблемы со здоровьем, хотя, казалось, это не очень отражается на его ритме жизни. Здоровье его жены ухудшалось, и в последние несколько недель довольно резко. В пятницу Сол, как обычно, пошел в свой кабинет, а в субботу ночью умер во сне. Его жена Бо пережила его всего на две недели и умерла всего за два дня до 60-й годовщины их свадьбы.

Хотя Сол и ушел, его работа живет в октиллионах бит в цифровом мире.

Прощай, Сол. И от всех нас - спасибо.

Министерство образования и науки

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ СОЦИАЛЬНЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА ЗАЩИТЫ ИНФОРМАЦИИ

Криптографические методы и средства обеспечения информационной безопасности

Курсовая работа

«Р егистры сдвига с линейной обратной связью как генераторы псевдослучайных чисел»

Выполнил:

студент 3-го курса

группа КЗОИ-Д-3

Ларионов И.П.

Проверила:

доц. Баранова Е.К.

Москва 2011
СОДЕРЖАНИЕ

Введение ……………………………..…………………………………….3

1. Теоретические основы работы …………………………………………4
   1. Общие сведения о регистрах сдвига с обратной связью……...…..4
      1. О потоковых шифрах на базе РгСсЛОС………………….………10
      2. О линейной сложности генерируемой псевдослучайной последовательности РгСсЛОС………………………………….……12
      3. О корреляционной независимости генерируемой последовательности псевдослучайных чисел РгСсЛОС………..….13
      4. О других способах вскрытия генерируемой последовательности псевдослучайных чисел РгСсЛОС…………………………………..14
2. Программная реализация РгСсЛОС как генератора псевдослучайной последовательности ….…………………………….15
   1. Обобщенная схема алгоритма…………………………………...15
   2. Описание программных модулей и интерфейса.……………….16
   3. Инструкция пользователя………………………………………...20

Заключение ………………………………………………………………22

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

Приложение А ….………………………………………………………..24

ВВЕДЕНИЕ

Целью данной работы является разработка программного приложения, реализующего работу генератора псевдослучайных чисел на регистрах сдвига с обратной связью. Разработка данного приложения с графическим интерфейсом осуществляется на языке C ++ для ОС Windows .

С развитием криптографии в ХХ веке перед криптографами встала задача создания шифровальных устройств и машин, которые могли бы быстро и надежно зашифровывать и расшифровывать сообщения. Этому требованию отвечали уже открытые в то время симметричные системы шифрования, однако их слабым местом была сильная зависимость от ключа и его секретность. Наиболее удобным классом шифров, которые можно было использовать для этой цели это шифры гаммирования. Возникла задача генерации гаммы, которую нельзя было бы обнаружить при дешифровании сообщения. Теоретически это было возможно, если каждый раз гамма была случайной и изменялась во времени. Однако при использовании абсолютно случайной изменяющейся гаммы было бы трудно обеспечить достоверную шифровку-дешифровку сообщения. Криптографы занялись решением этой задачи, целью которой было нахождения алгоритма реализующего генерацию случайной гаммы по определенному правилу, такая последовательность должна содержать в себе нули и единицы на «якобы» случайных позициях, причем число единиц и нулей должно быть примерно одинаково. Такая случайная последовательность была названа псевдослучайной, так как генерировалась она по определенному правилу, а не случайным образом.

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

1.Теоретические основы работы

1.1.Общие сведения о регистрах сдвига с линейной обратной связью

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

Регистр сдвига с обратной связью (далее РгСсОС) состоит из двух частей: регистра сдвига и функции обратной связи. Регистр сдвига представляет собой последовательность битов. Количество битов определяется длиной сдвигового регистра , если длина равна n битам, то регистр называется n-битовым сдвиговым регистром . Всякий раз, когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на 1 позицию. Новый крайний левый бит является функцией всех остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Периодом сдвигового регистра называется длина получаемой последовательности до начала ее повторения.

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

Регистры сдвига очень быстро нашли применение в потоковых шифрах, так как они легко реализовывались с помощью цифровой аппаратуры. В 1965 году Эрнст Селмер (Ernst Selmer), главный криптограф норвежского правительства, разработал теорию последовательности регистров сдвига . Соломон Голомб (Solomon Golomb), математик NSA, написал книгу, излагающие некоторые свои результаты и результаты Селмера . Простейшим видом регистра сдвига с обратной связью является регистр сдвига с линейной обратной связью (linear feedback shift register , далее LFSR или РгСсЛОС) . Обратная связь таких регистров представляет собой просто XOR (сложение по модулю два) некоторых битов регистра, перечень этих битов называется отводной последовательностью (tap sequence). Иногда такой регистр называется конфигурацией Фиббоначи. Из-за простоты последовательности обратной связи для анализа РгСсЛОС можно использовать довольно развитую математическую теорию. Проанализировав получаемые выходные последовательности, можно убедиться в том, что эти последовательности достаточно случайны, чтобы быть безопасными. РгСсЛОС чаще других сдвиговых регистров используются в криптографии.

Рисунок РгСсЛОС Фиббоначи

В общем случае n -битовый РгСсЛОС может находиться в одном из N =2 n -1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом Т=2 n -1 битов. (Число внутренних состояний и период равны N = T max =2 n -1, потому что заполнение РгСсЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно). Только при определенных отводных последовательностях РгСсЛОС циклически пройдет через все 2 n -1 внутренних состояний, такие РгСсЛОС являются РгСсЛОС с максимальным периодом . Получившийся результат называется М-последовательностью .

Пример . На рисунке ниже показан 4-битовый РгСсЛОС с отводом от первого и четвертого битов. Если его проинициализировать значением 1111, то до повторения регистр будет принимать следующие внутренние состояния:

Выходной последовательностью будет строка младших значащих битов: 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 выглядит следующим образом :

int LFSR () {

static unsigned long ShiftRegister = 1;

/* Все , кроме 0. */

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister >> 6)

^(ShiftRegister >> 4)

^(ShiftRegister >> 2)

^(ShiftRegister >> 1)

^ShiftRegister))

& 0x00000001)

<<31)

| (ShiftRegister >> 1) ;

return ShiftRegister & 0 x 00000001;}

Если сдвиговый регистр длиннее компьютерного слова, код усложняется, но не намного. В приложении 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.О потоковых шифрах на базе РгСсЛОС

Основной подход при проектировании генератора потока ключей на базе РгСсЛОС прост. Сначала берется один или несколько РгСсЛОС, обычно с различными длинами и различными многочленами обратной связи. (Если длины взаимно просты, а все многочлены обратной связи примитивны, то у образованного генератора будет максимальная длина.) Ключ является начальным состоянием регистров РгСсЛОС. Каждый раз, когда необходим новый бит, сдвиньте на бит регистры РгСсЛОС (это иногда называют тактированием (clocking)). Бит выхода представляет собой функцию, желательно нелинейную, некоторых битов регистров РгСсЛОС. Эта функция называется комбинирующей функцией, а генератор в целом - комбинационным генератором. (Если бит выхода является функцией единственного РгСсЛОС, то генератор называется фильтрующим генератором.) Большая часть теории подобного рода устройств разработана Селмером (Selmer) и Нилом Цирлером (Neal Zierler). Можно ввести ряд усложнений. В некоторых генераторах для различных РгСсЛОС используется различная тактовая частота, иногда частота одного генератора зависит от выхода другого. Все это электронные версии идей шифровальных машин, появившихся до Второй мировой войны, которые называются генераторами с управлением тактовой частотой (clock - controlled generators ). Управление тактовой частотой может быть с прямой связью, когда выход одного РгСсЛОС управляет тактовой частотой другого РгСсЛОС, или с обратной связью, когда выход одного РгСсЛОС управляет его собственной тактовой частотой. Хотя все эти генераторы чувствительны, по крайней мере теоретически, к вскрытиям вложением и вероятной корреляцией, многие из них безопасны до сих пор.

Ян Касселлс (Ian Cassells), ранее возглавлявший кафедру чистой математики в Кембридже и работавший криптоаналитиком в Блетчли Парк (Bletchly Park), сказал, что «криптография - это смесь математики и путаницы, и без путаницы математика может быть использована против вас». Он имел в виду, что в потоковых шифрах для обеспечения максимальной длины и других свойств необходимы определенные математические структуры, такие как РгСсЛОС, но, чтобы помешать кому-то получить содержание регистра и вскрыть алгоритм, необходимо внести некоторый сложный нелинейный беспорядок. Этот совет справедлив и для блочных алгоритмов.

Большинство реальных потоковых шифров основаны на РгСсЛОС. Даже в первые дни электроники построить их было несложно. Сдвиговый регистр не представляет собой ничего большего, чем массив битов, а последовательность обратной связи - набор вентилей XOR. Даже при использовании СБИС потоковый шифр на базе РгСсЛОС обеспечивает немалую безопасность с помощью нескольких логических вентилей. Проблема РгСсЛОС состоит в том, что их программная реализация очень неэффективна. Вам приходится избегать разреженных многочленов обратной связи - они облегчают корреляционные вскрытия – а плотные многочлены обратной связи неэффективны.

Эта отрасль криптографии быстро развивается и находится под зорким государственным контролем со стороны NSA . Большинство разработок засекречены - множество используемых сегодня военных систем шифрования основаны на РгСсЛОС. Действительно, у большинства компьютеров Cray (Cray 1, Cray X-MP, Cray Y-MP) есть весьма любопытная инструкция, обычно называемая как "счетчик совокупности" (population count). Она подсчитывает количество единиц в регистре и может быть использована как для эффективного вычисления расстояния Хэмминга между двумя двоичными словами и для реализации векторизированной версии РгСсЛОС. Эта инструкция считается канонической инструкцией NSA, обязательно фигурирующей почти во всех контрактах, касающихся компьютеров.

С другой стороны было взломано удивительно большое число казавшихся сложными генераторов на базе сдвиговых регистров. И, конечно же, число таких генераторов, взломанных военными криптоаналитическими учреждениями, такими как NSA, еще больше.

1.3.О линейной сложности генерируемой последовательности псевдослучайных чисел РгСсЛОС

Анализировать потоковые шифры часто проще, чем блочные. Например, важным параметром, используемым для анализа генераторов на базе РгСсЛОС, является линейная сложность (linear complexity), или линейный интервал. Она определяется как длина n самого короткого РгСсЛОС, который может имитировать выход генератора. Любая последовательность, генерированная конечным автоматом над конечным полем, имеет конечную линейную сложность . Линейная сложность важна, потому что с помощью простого алгоритма, называемого алгоритмом Berlekamp-Massey, можно определить этот РгСсЛОС, проверив только 2n битов потока ключей . Воссоздавая нужный РгСсЛОС, вы взламываете потоковый шифр.

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

1.4.О корреляционной независимости генерируемой последовательности псевдослучайных чисел РгСсЛОС

Криптографы пытаются получить высокую линейную сложность, нелинейно объединяя результаты некоторых выходных последовательностей. При этом опасность состоит в том, что одна или несколько внутренних выходных последовательностей - часто просто выходы отдельных РгСсЛОС - могут быть связаны общим ключевым потоком и вскрыты при помощи линейной алгебры. Часто такое вскрытие называют корреляционным вскрытием или вскрытием разделяй-и-властвуй. Томас Сигенталер (Thomas Siegenthaler) показал, что можно точно определить корреляционную независимость, и что существует компромисс между корреляционной независимостью и линейной сложностью .

Основной идеей корреляционного вскрытия является обнаружение некоторой корреляции между выходом генератора и выходом одной из его составных частей. Тогда, наблюдая выходную последовательность, можно получить информацию об этом промежуточном выходе. Используя эту информацию и другие корреляции, можно собирать данные о других промежуточных выходах до тех пор, пока генератор не будет взломан.

Против многих генераторов потоков ключей на базе РгСсЛОС успешно использовались корреляционные вскрытия и их вариации, такие как быстрые корреляционные вскрытия, предлагающие компромисс между вычислительной сложностью и эффективностью.

1.5.О других способах вскрытия генерируемой последовательности псевдослучайных чисел РгСсЛОС

Существуют и другие способы вскрытия генераторов потоков ключей. Тест на линейную корректность (linear consistency) пытается найти некоторое подмножество ключа шифрования с помощью матричной техники. Существует и вскрытие корректности "встречей посередине" (meet-in-the-middle consistency attack). Алгоритм линейного синдрома (linear syndrome algorithm) основан на возможности записать фрагмент выходной последовательности в виде линейного уравнения. Существует вскрытие лучшим аффинным приближением (best afflne approximation attack) и вскрытие выведенным предложением (derived sequence attack). К потоковым шифрам можно применить также методы дифференциального и линейного криптоанализа.

2. Описание программной реализации РгСсЛОС как генератора псевдослучайной последовательности

2.1.Обобщенная схема алгоритма

2.2.Описание программных модулей и интерфейса

Ниже на рисунке 3 представлено окно программы.

Рисунок Интерфейс программы

В меню есть следующие функции:

• Файл->Сохранить отчет

Эта функция осуществляет создание файла отчета, куда записывается инициальное состояние РгСсЛОС, отводная последовательность, период полученной псевдослучайной последовательности бит, сама последовательность и таблица состояний. Если файл успешно был сохранен, то выдается сообщение об успешном сохранении (рисунок 4). Рекомендуемое расширение файла отчета *. txt .

Рисунок

• Файл- > Выход

Эта функция обеспечивает закрытие приложения.

• Задать отводную последовательность

Эта функция формирует отводную последовательность, считывая значения из клеточек, которые пользователь отметил галочкой на экранной форме. После чего она уведомляет пользователя о создании отводной последовательности (рисунок 5). Отводная последовательность определяет от каких триггеров регистра сдвига будут идти обратные связи XOR для формирования бита смещения. По умолчанию обратная связь от первого триггера стоит всегда, при отсутствии других связей, будет осуществляться сдвиг влево с перестановкой младшего бита на позицию старшего.

Рисунок

• Установить инициальное значение

Эта функция считывает введенное пользователем инициальное значение регистра из окна Edit 1 и осуществляет проверку введенного значения согласно заданным условиям: введенная строка непустая (рисунок 6), введенная строка имеет длину равную восьми (8бит=1байт, рисунок 7), введенная строка содержит только нули и/или единицы (рисунок 8), введенная строка ненулевая (рисунок 9). В противном случае выдаются сообщения об ошибке, пользователь должен их исправить и снова нажать на кнопку. В случае успешной проверки инициальное значение будет записано в таблицу состояний в строке «Инициальное» и выдано уведомление (рисунок 10).

Рисунок

Рисунок

Рисунок

Рисунок

Рисунок

• Произвести сдвиг регистра

Эта функция эмулирует работу регистра сдвига. Последовательно производя 256 сдвигов, каждый сдвиг формирует выходной бит псевдослучайной последовательности и новое состояние регистра. Как только находится состояние регистра равное инициальному, вычисляется период и выводит в поле Memo 1 полученную псевдослучайную последовательность.

• Помощь- > О программе

Эта функция выводит на экран краткое описание программы и инструкцию (рисунок 11).

Рисунок

• Помощь- > Об авторе

Эта функция выводит на экран информацию об авторе программы (рисунок 12).

Рисунок

2.3.Инструкция пользователя

1. Сначала установите инициальное состояние регистра. Оно должно содержать восемь двоичных символов. В противном случае будет выдано сообщение об ошибке и Вам придется исправить введенное значение. Нажмите пункт меню «Задать инициальное значение».
2. Затем отметьте флажками в клеточках обратные связи регистра (Отводная последовательность). Нажмите пункт меню «Задать отводную последовательность».
3. Далее нажмите пункт меню «Сдвиг регистра». Обязательно перед этим удостоверьтесь в том, что вы выполнили пункт 1 и 2, иначе произойдет программная ошибка.
4. Получив результаты вы можете их сохранить нажав пункт меню «Файл->Сохранить отчет». Обязательно перед этим удостоверьтесь в том, что вы выполнили пункты 1-3, иначе произойдет программная ошибка.
5. Для получения справки нажмите пункты меню «Файл->О программе», «Файл->Об авторе».
6. Чтобы посмотреть работу регистра при других значениях отводной последовательности и инициального состояния регистра, повторите последовательно действия в пунктах 1-3, введя другие параметры.

ЗАКЛЮЧЕНИЕ

В данной работе были рассмотрены РгСсЛОС в качестве генераторов псевдослучайных чисел. Программа может служить наглядной демонстрацией принципов работы регистров сдвига с линейной обратной связью по XOR . На ней можно изучать принцип формирования псевдослучайной последовательности битов, зависимость между инициальным значением регистра и значением псевдослучайной последовательности, отводной последовательностью и периодом. Получаемую псевдослучайную гамму можно использовать в другом программном приложении (например, программная реализация шифра гаммирования).

На сегодняшний момент данные регистры не используются как самостоятельные генераторы псевдослучайных чисел, а входят в состав более сложных устройств. Однако именно они открыли новые направления в математике (поиск примитивных многочленов в конечных полях, математические способы взлома генераторов псевдослучайных чисел). Без знания принципов работы генераторов на РгСсЛОС нельзя понять работу более сложных устройств. Благодаря своей простой аппаратной реализации они получили широкое распространение в технике. Исследование РгСсОС привело к возникновению новых шифров - блочных и потоковых - основанных на этих типах регистров (шифр скользящей перестановки, DES и т.п.; ЭЦП, хеш-функции).

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

СПИСОК ЛИТЕРАТУРЫ

1. Шнайер Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. – М.: Триумф, 2002
2. Бабаш А.В. Криптографические и теоретико-автоматные аспекты современной защиты информации. Том 1 – М.: Изд. центр ЕАОИ, 2009. – 414 с.
3. Е.С. Селмер. Монография: «Линейная рекурсия в конечном поле». Университет Бергена, Норвегия, 1966.
4. Н.Зиерлер и Дж. Бриллхарт. "О примитивных трехчленах по модулю 2", журнал Информация и Контроль, издание 13 №6 декабрь 1968, стр. 541-544.
5. К.Х. Мейер и У.Л.Тучман. "Псевдослучайные коды могут быть взломаны, " журнал Электроник Дизайн, №. 23, ноябрь 1972.
6. Дж.Л.Массей. "Обобщение регистров сдвига и дешифровка кода Бозе-Чоудхури-Хоквингема", IEEE Transactions on Information Theory , v . IT -15, n . 1, январь 1969, стр. 122-127.
7. С.У. Голомб. Последовательности регистров сдвига, Сан-Франциско, Голден-Дей, 1967 (переиздано Аигеан Парк Пресс, 1982).

Приложение А

Таблица некоторых примитивных многочленов по модулю 2

(1, 0)

(2, 1, 0)

(3, 1, 0)

(4, 1, 0)

(5, 2, 0)

(6, 1, 0)

(7, 1, 0)

(7, 3, 0)

(8, 4, 3, 2, 0)

(9, 4, 0)

(10, 3, 0)

(11, 2, 0)

(12, 6, 4, 1, 0)

(13, 4, 3, 1, 0)

(14, 5, 3, 1, 0)

(15, 1, 0)

(16, 5, 3.2, 0)

(17, 3, 0)

(17, 5, 0)

(17, 6, 0)

(18, 7, 0)

(18, 5, 2, 1, 0)

(19, 5, 2, 1, 0)

(20, 3, 0)

(21, 2, 0)

(22, 1, 0)

(23, 5, 0)

(24, 4, 3, 1, 0)
(25, 3, 0)

(26, 6, 2, 1, 0)

(27, 5, 2, 1, 0)

(28, 3, 0)

(29, 2, 0)

(30, 6, 4, 1.0)

(31, 3, 0)

(31, 6, 0)

(31, 7, 0)

(31, 13, 0)

(32, 7, 6, 2, 0)

(32, 7, 5, 3, 2, 1, 0)

(33, 13, 0)

(33, 16, 4, 1, 0)

(34, 8, 4, 3, 0)

(34, 7, 6, 5, 2, 1, 0)

(35, 2, 0)

(135, 11, 0)

(135, 16, 0)

(135, 22, 0)

(136, 8, 3, 2, 0)

(137, 21, 0)

(138, 8, 7, 1, 0)

(139, 8, 5, 3, 0)

(140, 29, 0)

(141, 13, 6, 1, 0)

(142, 21, 0)

(143, 5, 3, 2, 0)

(144, 7, 4, 2, 0)

(145, 52, 0)

(145, 69, 0)

(146, 5, 3, 2, 0)

(147, 11, 4, 2, 0)

(148, 27, 0)

(149, 10, 9, 7, 0)

(150, 53, 0)

(151, 3, 0)

(151, 9, 0)

(151, 15, 0)

(151, 31, 0)

(151, 39, 0)

(151, 43, 0)

(151, 46, 0)

(151, 51, 0)

(151, 63, 0)

(151, 66, 0)

(151, 67, 0)

(151, 70, 0)

(36, 11, 0)

(36, 6, 5, 4, 2, 1, 0)

(37, 6, 4, 1, 0)

(37, 5, 4, 3, 2, 1, 0)

(38, 6, 5, 1, 0)

(39, 4, 0)

(40, 5, 4, 3, 0)

(41, 3, 0)

(42, 7, 4, 3, 0)

(42, 5, 4, 3, 2, 1, 0)

(43, 6, 4, 3, 0)

(44, 6, 5, 2, 0)

(45, 4, 3, 1, 0)

(46, 8, 7, 6, 0)

(46, 8, 5, 3, 2, 1, 0)

(47, 5, 0)

(48, 9, 7, 4, 0)

(48, 7, 5, 4, 2, 1, 0)

(49, 9, 0)

(49, 6, 5, 4, 0)

(50, 4, 3, 2, 0)

(51, 6, 3, 1, 0)

(52, 3, 0)

(53, 6, 2, 1, 0)

(54, 8, 6, 3, 0)

(54, 6, 5, 4, 3, 2, 0)

(55, 24, 0)

(55, 6, 2, 1, 0)

(56, 7, 4, 2, 0)

(57, 7, 0)

(57, 5, 3, 2, 0)

(58, 19.0)

(58, 6, 5, 1, 0)

(59, 7, 4, 2, 0)

(59, 6, 5, 4, 3, 1, 0)

(60, 1, 0)

(61, 5, 2, 1, 0)

(62, 6, 5, 3, 0)

(63, 1, 0)

(64, 4, 3, 1, 0)

(65, 18, 0)

(65, 4, 3, 1, 0)

(66, 9, 8, 6, 0)

(66, 8, 6, 5, 3, 2, 0)

(67, 5, 2, 1, 0)

(152, 6, 3, 2, 0)

(153, 1, 0)

(153, 8, 0)

(154, 9, 5, 1, 0)

(155, 7, 5, 4, 0)

(156, 9, 5, 3, 0)

(157, 6, 5, 2, 0)

(158, 8, 6, 5, 0)

(159, 31, 0)

(159, 34, 0)

(159, 40, 0)

(160, 5, 3, 2, 0)

(161, 18, 0)

(161, 39, 0)

(161, 60, 0)

(162, 8, 7, 4, 0)

(163, 7, 6, 3, 0)

(164, 12, 6, 5, 0)

(165, 9, 8, 3, 0)

(166, 10, 3, 2, 0)

(167, 6, 0)

(170, 23, 0)

(172, 2, 0)

(174, 13, 0)

(175, 6, 0)

(175, 16, 0)

(175, 18, 0)

(175, 57, 0)

(177, 8, 0)

(177, 22, 0)

(1 77, 88, 0)

(68, 9, 0)

(68, 7, 5, 1, 0)

(69, 6, 5, 2, 0)

(70, 5, 3, 1, 0)

(71, 6, 0)

(71, 5, 3, 1, 0)

(72, 10, 9, 3, 0)

(72, 6, 4, 3, 2, 1, 0)

(73, 25, 0)

(73, 4, 3, 2, 0)

(74, 7, 4, 3, 0)

(75, 6, 3, 1, 0)

(76, 5, 4, 2, 0)

(77, 6, 5, 2, 0)

(78, 7, 2, 1, 0)

(79, 9, 0)

(79, 4, 3, 2, 0)

(80, 9, 4, 2, 0)

(80, 7, 5, 3, 2, 1, 0)

(81, 4, 0)

(82, 9, 6, 4, 0)

(82, 8, 7, 6, 1, 0)

(83, 7, 4, 2, 0)

(84, 13, 0)

(84, 8, 7, 5, 3, 1, 0)

(85, 8, 2, 1, 0)

(86, 6, 5, 2, 0)

(87, 13, 0)

(87, 7, 5, 1, 0)

(88, 11, 9, 8, 0)

(88, 8, 5, 4, 3, 1, 0)

(89, 38, 0)

(89, 51, 0)

(89, 6, 5, 3, 0)

(90, 5, 3, 2, 0)

(91, 8, 5, 1, 0)

(91, 7, 6, 5, 3, 2, 0)

(92, 6, 5, 2, 0)

(93, 2, 0)

(94, 21, 0)

(94, 6, 5, 1, 0)

(95, 11, 0)

(95, 6, 5, 4, 2, 1, 0)

(96, 10, 9, 6, 0)

(96, 7, 6, 4, 3, 2, 0)

(178, 87, 0)

(183, 56, 0)

(194, 87, 0)

(198, 65, 0)

(201, 14, 0)

(201, 17, 0)

(201, 59, 0)

(201, 79, 0)

(202, 55, 0)

(207, 43, 0)

(212, 105, 0)

(218, 11, 0)

(218, 15, 0)

(218, 71, 0)

(218.83, 0)

(225, 32, 0)

(225, 74, 0)

(225, 88, 0)

(225, 97, 0)

(225, 109, 0)

(231, 26, 0)

(231, 34, 0)

(234, 31, 0)

(234, 103, 0)

(236, 5, 0)

(250, 103, 0)

(255, 52, 0)

(255, 56, 0)

(255, 82, 0)

(258, 83, 0)

(266, 47, 0)

(97, 6, 0)

(98, 11, 0)

(98, 7, 4, 3, 1, 0)

(99, 7, 5, 4, 0)

(100, 37, 0)

(100, 8, 7, 2, 0)

(101, 7, 6, 1, 0)

(102, 6, 5, 3, 0)

(103, 9, 9)

(104, 11, 10, 1, 0)

(105, 16, 0)

(106, 15, 0)

(107, 9, 7, 4, 0)

(108, 31, 0)

(109, 5, 4, 2.0)

(110, 6, 4, 1, 0)

(111, 10, 0)

(111, 49, 0)

(113, 9, 0)

(113, 15, 0)

(113, 30, 0)

(114, 11, 2, 1, 0)

(115, 8, 7, 5, 0)

(116, 6, 5, 2, 0)

(117, 5, 2, 1, 0)

(118, 33, 0)

(119, 8, 0)

(119, 45, 0)

(120, 9, 6, 2, 0)

(121, 18, 0)

(122, 6, 2, 1, 0)

(123, 2, 0)

(124, 37, 0)

(125, 7, 6, 5, 0)

(126, 7, 4, 2, 0)

(127, 1, 0)

(127, 7, 0)

(127, 63, 0)

(128, 7, 2, 1, 0)

(129, 5, 0)

(130, 3, 0)

(131, 8, 3, 2, 0)

(132, 29, 0)

(133, 9, 8, 2, 0)

(134, 57, 0)

(270, 133, 0)

(282, 35, 0)

(282, 43, 0)
(286, 69, 0)

(286, 73, 0)

(294, 61, 0)

(322, 67, 0)

(333, 2, 0)

(350, 53, 0)

(366, 29, 0)

(378, 43, 0)

(378, 107, 0)

(390, 89, 0)

(462, 73, 0)

(521, 32, 0)

(521, 48, 0)

(521, 158, 0)

(521, 168, 0)

(607, 105, 0)

(607, 147, 0)

(607, 273, 0)

(1279, 216, 0)

(1279, 418, 0)

(2281, 715, 0)

(2281, 915, 0)

(2281, 1029, 0)

(3217, 67, 0)

(3217, 576, 0)

(4423, 271, 0)

(9689, 84, 0)

Ввод инициального состояния (ИС)

роверка на правильность ввода

Выдача сообщения об ошибке

Установка отводной последовательности

Запись ИС в таблицу состояний

Запись i -го состояния регистра и выходного бита в таблицу состояний

ИС==Текущее состояние

Сохранение результатов

Вывод псевдослучайно последовательности

Выход

Запуск

Да

Да

Нет

Сдвиговый регистр с обратной связью ( 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. Эта функция называетсякомбинирующей , а генератор в целом –комбинирующим генератором . Многие из таких генераторов безопасны до сих пор.