Линейный Рекуррентный Регистр (ЛРР)

[Марк]

Помогите с информацией, не получается найти чего-то толкового.
А также о генерации Псевдо Случайной Двоичной Последовательности (ПСДП) на основе ЛРР.

[Alik]

Возможно речь идет о регистре к выходам которого подключен мажоритарный элемент (исключающее ИЛИ)? Если да, то это стандартная схема генерации псевдо-случайных чисел, только вот книжку подсказать не могу. Вернее так - книжек со схемами много, книжек посвященных распределению чисел на выходе регистра - не встречал.

[Yuri Gendelman]

Здесь упоминается linear recurrent register:

1) Frangis Hisamov. On the Application of Pseudo-Accidental Sequences in the Information Protection Systems:
http://csdl2.computer.org/comp/proceedi ... 330433.pdf
2) P.M. Tutunnick. Line cipher demonstration for educational purposes: http://wwwmayr.informatik.tu-muenchen.d ... %20Pur.ppt
Оба автора - из России (у них российские е-мейлы)

Похоже, что речь идет не об универсальных генераторах ПСЧ, а о специальных генераторах ПСЧ для криптографических приложений.

P.S. Только сейчас заметил: "Pseudo-Accidental" вместо "Pseudo Random" - это верный признак того, что английский - не родной.

[Марк]

Линейный рекуррентный регистр
Строится на основе линейных рекуррентных соотношений. Линейный рекуррентный регистр (ЛРР) является наиболее простым и распространенным генератором ПСДП. Это малогабаритное, легкое, недорогое устройство, способное предоставить богатый выбор порождаемых последовательностей и обеспечить такие требования как:

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

ЛРР представляет собой сдвиговый регистр с линейными обратными связями (его структурная схема представлена на рисунке 1), в котором входной сигнал образуется в результате сложения по модулю 2 нескольких фиксированных разрядов. В результате образуется выходной сигнал в виде ПСП «0» и «1».Этот «шум» обладает интересным свойством: по происшествии некоторого времени, определяемого длиной регистра, он в точности повторяется (регистр максимальной длины n перед повторением проходит через 2n-1 состояний). Т.е. образуются циклические или кольцевые ПСДП.

Очередное значение, формируемое на выходе ЛРР, вычисляется по формуле

$$a_{n+1} = \bigoplus\limits_{j-0}^n a_j h_j$$

где $\oplus$ - операция вычисления суммы по модулю 2
$a_j$ - состояние j -го бита ЛРР
$h_j$ - коэффициент обратной связи.
При этом для двоичного ЛРР $a_j, h_j \in \{0,1\}$.
Каждому линейному рекуррентному регистру длиной n разрядов можно сопоставить полином обратных связей h(x) с двоичными коэффициентами вида:

$$h(x) = h_n x^n + h_{n-1} x^{n-1} + ... + h_1x + h_0 ,$$

причем обязательно $h_n = h_0 = 1$.

Если полином h(x) - примитивный, то длина последовательности, генерируемой ЛРР, максимальна и равна:
$$\mathbb{L} = 2^n - 1$.
Такая последовательность называется последовательностью максимальной длины для сдвигового регистра (Maximal Length Shift Register Sequence - MLSRS). Питерсон и Уэлдон показали, что при любом целом $n$ существует n-битовая последовательность MLSRS с периодом $2^n - 1$. В частности, при $n = 100$последовательность будет иметь период $2^100 - 1$ и не повторится $10^16$ лет при передаче ее по линии связи со скоростью 1Мбит/с.
Следует отметить, что для MLSRS, во-первых, распределение «1» и «0» близко к равномерному, насколько это возможно при прохождении полного цикла (количество «0» отличается от «1» на 1) . Во-вторых, если рассмотреть в одном цикле серии последовательных битов, то половина серий из «1» длину 1, ¼ серий - длину 2,1/8 – длину 3 и т.д. Это свойство распространяется на серии из «0»,с учетом пропущенного. Это говорит о том, что вероятности появления «1» и «0» не зависят от исхода предыдущего опыта. И, в-третьих, если последовательность полного цикла сравнить с этой же последовательностью, но циклически сдвинутой на любое число битов (не равное нулю или длине К), то число несовпадений будет на единицу больше, чем число совпадений. Все эти свойства последовательности максимальной длины свидетельствуют о равномерности распределения случайных чисел в этих последовательностях.
Благодаря этому MLSRS часто используются в качестве ПСП в криптографических системах, которые имитируют работу криптостойкой системы одноразового шифрования. Однако сама она не отличается криптосойкостью и может быть взломана за несколько секунд работы компьютера при наличии известного открытого текста.
Для нахождения начального состояния регистра с зафиксированными отводами обратной связи достаточно знать n битов открытого текста. Сложением по модулю 2 этих битов с n битами шифртекста находят n битов ключа, которые дают состояние сдвигового регистра с обратной связью в обратном направлении на некоторый момент времени. После этого можно определить исходное состояние регистра, моделируя его работу назад.
Если отводы регистра с обратной связью не фиксированы, а являются частью ключа, то достаточно 2n битов известного открытого текста, чтобы сравнительно быстро определить расположение отводов регистра и его начальное состояние.
Необходимо иметь в виду, что линейные рекуррентные последовательности не используются в чистом виде из-за низкой структурной скрытности. Для повышения структурной скрытности используют:

• комбинирование нескольких ЛРР;
• нелинейные функции в обратной связи регистра;
• нелинейную логику и фильтрацию содержимого регистра.

Поэтому последовательности максимальной длины MLSRS можно сделать более пригодными для криптографии, используя нелинейную логику. Например, нелинейно «фильтрующий» сдвиговый регистр выдает ключевой набор, а линейная обратная связь создает последовательность максимальной длины (рис.2)

Здесь функция $f$ должна выбираться так, чтобы обеспечить хороший баланс между «0» и «1», а фильтрованная последовательность имела распределение, близкое к равномерному. Также необходимым условием является большой период этой последовательности. Если $2^n - 1$ является простым числом, то фильтрованная последовательность может иметь период $(2^n - 1)$ (при выборе структуры сдвигового регистра в соответствии с примитивным неприводимым многочленом h(x) степени n).
Преимущества цифровой генерации с помощью ЛРР:

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

Однако существует целый ряд недостатков из-за цикличности ПСП:

• Генераторы на основе регистров образуют только циклические последовательности чисел. Для нециклических ПСДП надо использовать дополнительный комбинационный преобразователь кодов, включаемый на выходе генератора. Но при этом основные параметры генератора - быстродействие, мощность, площадь кристалла - ухудшаются;
• На основе трех свойств, которыми обладают регистры максимальной длины, можно усомниться в случайности выходного шума в том смысле, что он имеет точно заданное число проходов определенной длины и т.п. Иными словами, если «0» и «1», поступающие от регистра, использовать для управления случайным блужданием, перемещаясь на шаг вперед при «1» и на шаг назад при «0», то после завершения полного цикла регистра окажетесь смещенными на 1 только шаг по отношению к начальной точке, что, казалось бы, не свидетельствует о случайном характере процесса. Но если брать часть этой последовательности 2n-1, то она фактически будет иметь такие же статистические свойства, какими обладает процесс бросания монеты. Рассматривались несколько тысяч случайных блужданий, вызванных ПСДП, каждое из которых имело длину несколько тысяч шагов, и установили, что случайность, измеренная в соответствии с простым критерием (среднее смещение X=r1/2, где r –количеств испытаний), является практически идеальной. Однако нет гарантий удовлетворения и другим, более сложным критериям случайности, например, при измерении корреляции более высокого порядка. Эти корреляционные зависимости также оказывают влияние на характеристики аналогового шума, полученного из такой последовательности путем фильтрации. Хотя амплитуда такого шума имеет гауссово распределение, здесь могут возникнуть корреляции амплитуды высоких порядков, не свойственные действительно случайным шумам.

(c) Из конспекта.


Вообщем, ключом ко всему является:

Цитата:

ЛРР представляет собой сдвиговый регистр с линейными обратными связями

О нем можно почитать:
Д. Э. Кнут, "Искусство программирования", т. 2 "Получисленные алгоритмы", глава 3 "Случайные числа".

Брюс Шнайер, "Прикладная криптография", глава 16 "Генератор псевдослучайных почледовательностей и потоковые шифры"