Учбово-методичний посібник для виконання лабораторних робіт з дисципліни „Основи теорії криптографії і криптоаналізу”, страница 23

Вихідною послідовністю буде рядок молодших значущих бітів: 111101011001000....

n-бітовий РЗЛЗЗ може знаходитися в одному з 2ⁿ-1 внутрішніх станів. Це означає, що теоретично такий регістр може генерувати псевдовипадкову послідовність з періодом 2ⁿ-1 бітів. (Число внутрішніх станів і період рівні 2ⁿ-1, тому що заповнення РЗЛЗЗ нулями, приведе до того, що регістр зрушення буде видавати нескінченну послідовність нулів, що абсолютно даремно.) Тільки при визначених відвідних послідовностях РЗЛЗЗ циклічно пройде через усі 2ⁿ-1 внутрішніх станів, такі РЗЛЗЗ є РЗЛЗЗ із максимальним періодом. Результат, що вийшов, називається m-послідовністю. [6]

Для того, щоб конкретний РЗЛЗЗ мав максимальний період, поліном, утворений з відвідної послідовності і константи 1, повинний бути примітивним по модулю 2. Ступіньполінома є довжиною регістра зрушення. Примітивний поліном ступеня п – поліном, що неприводиться, якщо є дільником , але не є дільником x^d+1 для всіх d, що є дільниками 2^n-1 (див. розділ 4).

У загальному випадку не існує простого способу генерувати примітивні поліноми даного ступеня по модулю 2. Найпростіше вибирати поліном випадковим чином і перевіряти, чи не є він примітивним. Це чимось схоже на перевірку, чи не є простим випадково обране число.

Деякі, але, звичайно ж не всі, поліноми різних ступенів, примітивні по модулю 2, приведені в таблиці 5.2.

Приклад 5.3.1. Запис (32, 7, 5, 3, 2, 1, 0) означає, що наступний поліном примітивний по модулю 2:

х³²+х⁷+х⁵+х³+х²+х+1

Це можна легко узагальнити для РЗЛЗЗ із максимальним періодом. Першим числом є довжина РЗЛЗЗ. Останнє число завжди дорівнює 0, і його можна опустити. Усі числа, за винятком 0, задають відвідну послідовність, відлічувану від лівого краю регістра зрушення. Тобто, члени полінома з меншим ступенем відповідають позиціям ближче до правого краю регістра. [1]

Продовжуючи приклад, запис (32, 7, 5, 3, 2, 1, 0) означає, що для узятого 32-бітового регістра зрушення новий біт новий біт генерується за допомогою XOR тридцять першого, сьомого, п'ятого, третього, другого, першого і нульового бітів (див. мал. 5.4), що виходить РЗЛЗЗ і буде мати максимальну довжину, циклічно проходячи до повторення через 2³² – 1 значень.

Код для цього РЗЛЗЗ мовою C++ виглядає так:

int LFSR ()

{

static unsigned long ShiftRegister = 1;

ShiftRegister=((((ShiftRegister >> 31)

^(ShiftRegister>>7)^(ShiftRegister>>5)

^(ShiftRegister>>3)^(ShiftRegister>>2)

^ShiftRegister>>1)^ShiftRegister))&0x00000001)<<31)

|(ShiftRegister>>1);

return ShiftRegister&0x00000001;

}

Якщо РЗЛЗЗ довше комп'ютерного слова, код ускладнюється, але не набагато.

Табл. 5.2. Деякі примітивні поліноми по модулю 2