Регистър за смяна на линейна обратна връзка. Линеен повтарящ се регистър

Регистър за смяна на обратната връзка ( FSR ) се състои от две части: смяна регистърИ функции за обратна връзка .

Преместващият регистър (Грешка: Референтен източник не е намерен) е поредица от битове. Когато трябва да се извлече бит, всички битове на преместващия регистър се изместват надясно с 1 позиция. Новият най-ляв бит е стойността на функцията за обратна връзка от останалите битове в регистъра. Период Регистърът за преместване е дължината на получената последователност, преди да започне да се повтаря.

Най-простият тип преместващ регистър с обратна връзка е линеен преместващ регистър с обратна връзка (LFSR – Наляво Обратна връзка Shift Регистрирам) (Грешка: Референтният източник не е намерен). Обратната връзка е просто XOR на някои p бита. регистър, списъкът с тези битове се извиква байпасна последователност.

н-bit LFSR може да бъде в един от 2 н -1 вътрешни състояния. Това означава, че теоретично такъв регистър може да генерира псевдослучайна последователност с период 2 н -1 битове. Броят на вътрешните състояния и периодът са равни, тъй като попълването на регистъра с нули ще доведе до генерирането на безкрайна последователност от нули, което е абсолютно безполезно. Само с определени последователности от докосвания, LFSR ще премине през всички 2 н -1 вътрешни състояния. Такива LFSR се наричат LFSRс максимален период.

За да има конкретен LFSR максимален период, полиномът, образуван от последователността на крана и константата 1 трябва да бъде примитивен по модул 2 .

Изчисляването на примитивността на полином е доста сложен математически проблем. Следователно има готови таблици, в които са изброени номерата на последователностите на кранове, които осигуряват максималния период на генератора. Например, за 32-битов преместващ регистър можете да намерите следния запис: (32,7,5,3,2,1,0) . Това означава, че за да генерирате нов бит, трябва да сумирате тридесет и втория, седмия, петия, третия, втория и първия бит с помощта на функцията XOR.

Кодът за такъв LFSR в C++ би бил:

// Всяка стойност, различна от нула

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

връщане ShiftRegister & 0x00000001;

Софтуерните реализации на LFSR са доста бавни и работят по-бързо, ако са написани на асемблер, а не на C. Едно решение е да се използват 16 LFSR паралелно (или 32 в зависимост от дължината на думата в архитектурата на даден компютър). В тази схема се използва масив от думи, чийто размер е равен на дължината на LFSR, като всяка единица от дума в масива се отнася до своя LFSR. При условие, че се използват едни и същи последователни номера на натискане, това може да доведе до забележимо увеличение на производителността.

СЪС веригата за обратна връзка също може да бъде модифицирана. В този случай генераторът няма да има по-голяма криптографска сила, но ще бъде по-лесно да се реализира програмно. Вместо да използвате най-левия бит от битовете на последователността на натискане, за да генерирате нов бит, XOR всеки бит на последователността на натискане с изхода на генератора и го замествайте с резултата от това действие, след което резултатът на генератора става новият най-ляв бит ( Грешка: Референтният източник не е намерен).

Тази модификация се нарича Конфигурация на Галоа. На език C изглежда така:

статичен неподписан дълъг ShiftRegister = 1;

void seed_LFSR (неподписано дълго начално число)

ShiftRegister = семена;

int Galua_LFSR(празно)

if (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ маска >> 1) | 0x8000000;

ShiftRegister >>= 1;

Изгодата е, че всички XOR се изпълняват в една операция. Тази верига може също да бъде паралелизирана.

Сами по себе си LFSR са добри генератори на псевдослучайни последователности, но имат някои нежелани неслучайни свойства. Последователните битове са линейни, което ги прави безполезни за криптиране. За дължина на LFSR нвътрешното състояние представлява предишното низходни битове на генератора. Дори ако схемата за обратна връзка се пази в тайна, тя може да бъде определена от 2 низходни битове на генератора, използващи специални алгоритми. В допълнение, големите произволни числа, генерирани с помощта на последователни битове от тази последователност, са силно корелирани и за някои видове приложения не са случайни. Въпреки това, LFSR често се използват за създаване на алгоритми за криптиране. За това се използват няколко LFSR, обикновено с различни дължини и последователни номера на крановете. Ключът е първоначалното състояние на регистрите. Всеки път, когато е необходим нов бит, всички регистри се изместват. Тази операция се нарича тактоване. Изходният бит е функция, за предпочитане нелинейна, на някои битове на LFSR. Тази функция се нарича комбиниране, и генератора като цяло - комбиниращ генератор. Много от тези генератори са безопасни и днес.

Shift регистър с линейна обратна връзка(RSLOS, англ. регистър за смяна на линейна обратна връзка, LFSR ) е регистър за смяна на битови думи, в който стойността на входния (плъзгащ) бит е равна на линейна булева функция от стойностите на останалите битове на регистъра преди смяната. Може да се организира както софтуерно, така и хардуерно. Използва се за генериране на псевдослучайни последователности битове, което се използва по-специално в криптографията.

Описание

Контролът на регистъра в хардуерните реализации се извършва чрез прилагане на импулс за изместване (наричан по друг начин с часовникили синхронизиращ импулс) за всички клетки. Управлението на регистъра в софтуерните реализации се извършва чрез изпълнение на цикъл. При всяка итерация на цикъла функцията за обратна връзка се изчислява и битовете в думата се изместват.

Принцип на действие

Линейна сложност

Корелационна независимост

В опит да получат висока линейна сложност на генерираната последователност, криптографите нелинейно комбинират изходите на няколко регистъра за изместване. В този случай една или повече изходни последователности (или дори изходи на отделни LFSR) могат да бъдат свързани с общ поток и отворени от криптоаналитик. Хакване, базирано на такава уязвимост, се нарича корелация отваряне. Основната идея на такъв хак е да се намери някаква корелация между изхода на генератора и изходите на неговите съставни части. След това, чрез наблюдение на изходната последователност, човек може да получи информация за тези междинни изходи и по този начин да хакне генератора. Томас Зигенталер показа, че е възможно да се дефинира точно корелационната независимост и че има компромис между корелационната независимост и линейната сложност.

Софтуерно внедряване

Софтуерните реализации на RSLOS са доста бавни и работят по-бързо, ако са написани на асемблер. Едно от решенията е паралелното използване на 16 RLLS (или 32, в зависимост от дължината на думата в компютърната архитектура). В такава схема се използва масив от думи, чийто размер е равен на дължината на регистъра за изместване и всеки бит от думата се отнася до собствен LFSR. Тъй като се използват еднакви последователности от натискания, това може да даде забележима печалба в производителността на генератора.

Конфигурация на Фибоначи

Помислете за 32-битов преместващ регистър. Има последователност за бягство (32, 31, 30, 28, 26, 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). Това означава, че за да се генерира нов бит, е необходимо да се сумират 31-ви, 30-ти, 29-ти, 27-ми, 25-ти и 0-ти битове, като се използва операцията XOR. Полученият LFSR има максимален период 2 32 − 1 (\displaystyle 2^(32)-1). Кодът за такъв регистър в C е както следва:

int LFSR_Fibonacci (void ) ( static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25) ^ S) & 0x00000001)<< 31 ) | (S >> 1); връща S & 0x00000001; )

Конфигурация на Галоа

Този генератор няма по-голяма криптографска сила, но дава печалба в производителността: всички XOR операции чрез паралелизиране могат да се извършват в една операция, а не последователно една след друга, както е в конфигурацията на Фибоначи. Тази схема също ще даде печалба в хардуерното внедряване.

Кодът за 32-битов преместващ регистър в C е както следва:

int LFSR_Galois (void) (static unsigned long S = 0x00000001; if (S & 0x00000001) (S = (S ^ 0x80000057 >> 1) | 0x80000000; return 1;) else (S >>= 1; return 0;) )

Струва си да се отбележи, че цикълът на фиксиран брой извиквания на функцията LFSR_Galois в конфигурацията на Galois е приблизително 2 пъти по-бърз от функцията LFSR_Fibonacci в конфигурацията на Fibonacci (MS VS 2010 компилатор на Intel Core i5).

Пример за генерирана последователност

Конфигурация на Фибоначи

Нека LFSR е даден от характеристичния полином x 3 + x + 1 (\displaystyle x^(3)+x+1). Това означава, че битовете за отклоняване ще бъдат 2-ри и 0-ти, а единицата във формулата на полинома означава, че 0-ият бит е входът. Функцията за обратна връзка има формата S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Да предположим, че първоначалното състояние на регистъра за смяна е последователността. Допълнителни състояния на регистъра са показани в таблицата по-долу:

Тъй като вътрешното състояние на седмата стъпка се върна в първоначалното си състояние, тогава, започвайки от следващата стъпка, битовете ще бъдат повторени. Така че генерираната последователност е: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle\left)(редът на битовете в последователността съответства на реда, в който са били генерирани от LFSR). Така периодът на редицата е 7, т.е. максималната възможна стойност, която се получава поради примитивността на дадения полином.

Конфигурация на Галоа

Нека вземем същия характерен полином, т.е. c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Само 1-вият бит се добавя към изходния бит. Първоначалното състояние е същото. Допълнителни състояния на регистъра:

Вътрешното състояние на регистъра на седмата стъпка се върна в първоначалното си състояние, следователно периодът му също е равен на 7. За разлика от конфигурацията на Фибоначи, вътрешните състояния на регистъра се оказаха различни, но генерираната последователност е същата , изместен само с 4 цикъла: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle\left)(редът на битовете в последователността съответства на реда, в който са били генерирани от LFSR).

Генериране на примитивни полиноми

Предимства и недостатъци

Предимства

• висока производителност на криптографски алгоритми, създадени на базата на LFSR (например поточни шифри);
• използването само на най-простите битови операции на събиране и умножение, реализирани хардуерно в почти всички изчислителни устройства;
• добри криптографски свойства (LFSR могат да генерират дълги периодични последователности с добри статистически свойства);
• поради тяхната структура, LFSR лесно се анализират с помощта на алгебрични методи.

недостатъци

Начини за подобряване на криптографската сила на генерираните последователности

Генератори с множество преместващи регистри

Този тип генератор се състои от няколко регистри за изместване с линейна обратна връзка, които генерират битове x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\dots ,\;x_(M,i))съответно. Освен това, генерираните битове се трансформират от някаква булева функция f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\dots ,\;x_(M , аз))). Трябва да се отбележи, че генераторите от този тип имат дължини на регистрите L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\dots ,\;M), са взаимно прости помежду си.

Периодът на този генератор е T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), Където L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- общ брой клетки. Следователно използването на няколко LFSR увеличава периода на генерираната последователност в сравнение с един регистър, което увеличава криптографската сила на генератора. Той също така увеличава линейната сложност или дължината на най-късия регистър, съответстващ на даден генератор. Такъв регистър се намира с помощта на алгоритъма Berlekamp-Massey, използвайки генерираната последователност. В най-добрия случай неговата дължина е съизмерима с периода на генерираната последователност.

Генератори с нелинейни трансформации

Блоковата схема на такъв генератор не се различава от схемата на предишния генератор. Основната разлика е, че трансформиращото устройство се дава от нелинейна булева функция f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\dots ,x_(M))). Например полиномът на Жегалкин се приема като такава функция (според теоремата на Жегалкин всяка булева функция може да бъде уникално представена от полинома на Жегалкин).

Може да се реализира и нелинеен генератор регистър за смяна на нелинейна обратна връзка. Той може да даде 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L))варианти на последователности максимален период, който е повече от този на LFSR.

Криптографската сила на този генератор се увеличава поради нелинейността на използваната функция. Определянето на състоянието на регистрите от генерираната битова последователност е сложен математически проблем, тъй като не е известен алгоритъм, който да възстановява първоначалните състояния.

Този метод се използва например в генератор Geffи обобщения генератор на Geff, но такива генератори могат да бъдат разбити чрез корелационна атака.

Генератори с различно синхронизиране на преместващия регистър

стоп-старт генератор

стоп-старт генератор(Английски Stop-and-Go, Both-Piper) използва изхода на LFOS-1, за да контролира тактовата честота на LFOS-2, така че LFSR-2 променя състоянието си в даден момент от времето само ако изходът на LFOS-1 по това време е равно на единица. Тази схема не устоя на отварянето на корелацията.

За да се увеличи криптографската сила, беше предложено алтернатор стоп-тръгване. Той използва три преместващи регистъра с различна дължина. Тук LFOS-1 управлява тактовата честота на 2-ри и 3-ти регистър, т.е. LFSR-2 променя състоянието си, когато изходът на LFSR-1 е равен на единица, а LFSR-3 - когато изходът на LFSR-1 е равен на нула. Изходът на генератора е операцията на добавяне модуло два изхода на RSLOS-2 и RSLOS-3. Този генератор има голям период и голяма линейна сложност. Има метод за корелационно отваряне на RLOS-1, но това не отслабва значително криптографските свойства на генератора.

Използва се сложна тактова схема двупосочен стоп-тръг генератор, който използва 2 регистъра за преместване с еднаква дължина. Ако изходът на RLOS-1 в даден момент от времето t i − 1 (\displaystyle t_(i-1))- едно, тогава RLOS-2 не е тактован по това време t i (\displaystyle t_(i)). Ако изходът на RLOS-2 в момента на време t i − 1 (\displaystyle t_(i-1))е равно на нула и в момент t i − 2 (\displaystyle t_(i-2))- един, и ако този регистър е тактован в момента t i (\displaystyle t_(i)), то в същия момент RLOS-1 не е клокнат. Линейната сложност на тази схема е приблизително равна на периода на генерираната последователност.

Саморазрушаващ се генератор

Многоскоростен осцилатор с вътрешно произведение

Този генератор използва два преместващи регистъра RSLOS-1 и RSLOS-2. Тактова честота на RSLOS-2 в d (\displaystyle d)пъти повече от това на RSLOS-1. Определени битове от тези регистри се умножават един с друг с помощта на операцията И. Резултатите от умноженията се събират чрез операцията XOR и се получава изходната последователност. Този генератор има висока линейна сложност и има добри статистически свойства. Състоянието му обаче може да се определи от изходна последователност с дължина L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), Където L 1 (\displaystyle L_(1))И L 2 (\displaystyle L_(2))са дължините на LFOS-1 и LFOS-2, съответно, и d (\displaystyle d)- съотношението на техните тактови честоти.

Каскада Голман

Тази схема е подобрена версия на генератора за спиране. Състои се от поредица от LFSR, времето на всеки от които се контролира от предишния LFSR. Ако изходът на RLOS-1 по това време t i (\displaystyle t_(i))е 1, тогава RLOS-2 се тактова. Ако изходът на RLOS-2 в момента на време t i (\displaystyle t_(i))е 1, след това RLOS-3 се тактова и т.н. Изходът на последния LFSR е изходът на генератора. Ако дължината на всички LFSR е еднаква и равна на L (\displaystyle L), след това периодът на системата от M (\displaystyle M) LFSR е равно на (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), а линейната сложност е L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

Тази идея е проста и може да се използва за генериране на последователности с огромни периоди, голяма линейна сложност и добри статистически свойства. Но, за съжаление, те са чувствителни към аутопсия, наречена заключване(англ. lock-in) когато

Регистър за преместване с линейна обратна връзка (LFSR) е механизъм за създаване на псевдослучайна последователност от двоични битове. Регистърът (фиг. 1) се състои от множество клетки, които се задават от инициализиращ вектор (най-често секретен ключ). Работата на регистъра се определя от наличието или липсата на връзка от всеки бит към обратната връзка. Крановете на регистъра за обратна връзка не са фиксирани, а са част от ключа. На следващата стъпка съдържанието на клетките на регистъра се измества с една позиция надясно и един бит, останал свободен в резултат на операцията XOR, се поставя в най-лявата клетка.

Ориз. 1. Линеен отместващ регистър с обратна връзка

За да се постигне максимален шифър гама период, броят на цифрите мрегистърът за смяна е избран да бъде едно от простите числа на Мерсен (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), и вътрешните връзки на регистъра трябва да бъде избран в съответствие с нередуцируеми примитивни полиноми с най-висока степен м. В този случай гама-периодът на шифъра може да достигне (2 м-1).

LFSR е бърз и лесен за внедряване както в софтуер, така и в хардуер. С правилен избор на битове за обратна връзка, генерираните последователности имат добри статистически свойства. LFSR се използва като основен елемент за изграждане на високо защитени системи.

Каскада от регистри е набор от LFSR, свързани по такъв начин, че поведението на един LFSR зависи от поведението на предишния LFSR в каскадата. Това "зависимо" поведение обикновено се настройва за управление на брояча на смяна на следващия LFSR от първия LFSR.

Например, регистърът се измества с една стъпка, ако стойността на предишния регистър е 1, а ако стойността е 0, тогава регистърът се измества с две стъпки или по друг начин. Голям брой такива комбинации позволяват много висока сигурност.

Най-сигурните последователности се произвеждат от свиващ се генератор въз основа на просто взаимодействие между резултатите от два LFSR регистъра. Битовете на един резултат определят дали съответните битове на втория резултат ще бъдат използвани като част от пълния "ключ на потока". Генераторът на компресия е прост, мащабируем и има добри характеристики за сигурност. Недостатъкът му е, че скоростта, с която се генерира "стрийминг ключът", няма да бъде постоянна, освен ако не се вземат някои предпазни мерки.

Метод на Фибоначи със закъсненияЕдин от широко използваните генератори на Фибоначи се основава на следната итеративна формула:

Където Y k- реални числа от диапазона

Ориз. 2. Кръгово криптиране

Режимът за обратна връзка на изхода DES може да се използва за генериране на псевдослучайни числа, подобно на начина, по който се използва за криптиране на поток. Резултатът от всеки етап на криптиране е 64-битова стойност, от която само горните j бита се връщат обратно за криптиране. 64-битовите изходи представляват поредица от псевдослучайни числа с добри статистически свойства.

Генераторът на псевдо-случайни числа, описан в стандарта ANSI X9.17, е един от най-криптографски защитените генератори на псевдо-случайни числа. Приложенията, използващи тази технология, включват приложения за финансова сигурност и PGP.

Генераторът ANSI X9.17 се състои от следните части (Фигура 3):

1. Вход: Генераторът се управлява от два псевдослучайни входа. Първият вход е 64-битово представяне на текущата дата и час ( DT i), които се променят при всяко създаване на числото. Вторият вход е 64-битова начална стойност, която се инициализира до някаква произволна стойност и се променя по време на генерирането на поредица от псевдослучайни числа ( Vi).

2. Ключове: Генераторът използва три тройни DES модула с два ключа K 1 , K 2 . И трите използват една и съща 56-битова двойка ключове, която трябва да се пази в тайна и да се използва само за генериране на псевдослучайно число.

Ориз. 3. ANSI X9.17 генератор на псевдослучайни числа

Регистър за смяна на обратната връзкасе състои от две части: регистър за смяна и функции за обратна връзка.

Фигура 19. Регистър за изместване на обратната връзка.

Като цяло регистърът за преместване е последователност от някои елементи на пръстен или поле. Най-често използвани малкорегистри за смяна. Дължината на такъв регистър се изразява като брой битове. Всеки път, когато се извлича бит, всички битове в регистъра се изместват надясно с една позиция. Новият най-значим бит се изчислява като функция на всички останали битове в регистъра. Резултатът обикновено е най-малкият бит. Периодът на регистъра за изместване е дължината на изходната последователност, преди да започне да се повтаря.

Най-простият тип регистри за преместване е регистърът за преместване с линейна обратна връзка (LFSR или LRS). Обратната връзка е проста операция XOR върху някои битове на регистър. Списъкът с тези битове е дефиниран характерен полиноми се обади последователност от докосвания. Понякога тази схема се нарича Конфигурация на Фибоначи.

Фиг.20. LFOS на конфигурацията на Фибоначи.

При софтуерната реализация на LFSR се използва модифицирана схема: за генериране на нов значим бит, вместо да се използват битовете на последователността на крана, се извършва операция XOR на всеки от неговите битове с изхода на генератора, замествайки стария малко от последователността на докосване. Тази модификация понякога се нарича Конфигурация на Галоа.

Фиг.21. RLOS на конфигурацията на Galois.

н-bit LFSR може да бъде в едно от 2 н– 1 вътрешни състояния. Това означава, че теоретично такъв регистър може да генерира псевдослучайна последователност с период от 2 н– 1 бита (подпълването с нули е напълно безполезно). Преминаване на всички 2 н– 1 вътрешни състояния са възможни само при определени последователности от докосвания. Такива регистри се наричат ​​LFSR с максимален период. За да се осигури максимален период на LFSR, е необходимо неговият характерен полином да бъде примитивенпо модул 2. Степента на полинома е дължината на регистъра за смяна. Полином на примитивна степен н- такова е нередуцируемполином, който е делител, но не е делител x d+ 1 за всички д, които са делители на 2 н– 1. (Когато се обсъждат полиноми, терминът просто числозаменен от термина нередуцируем полином). Характерният полином на LFSR, показан на фигурите:

х 32 + х 7 + х 5 + х 3 + х 2 + х + 1

е примитивен модул 2. Периодът на такъв регистър ще бъде максимален, преминавайки през всичките 2 32 - 1 стойности, докато се повторят. Най-често използваните са изтънените полиноми, т.е. които имат само някои коефициенти. най-популярните тричлени.

Важен параметър на генератора, базиран на LFSR, е линейна сложност. Определя се като дължина ннай-късият LFSR, който може да симулира изхода на генератора. Линейната сложност е важна, защото с проста Алгоритъм на Берленкамп-Масивъзможно е да се пресъздаде такъв LFSR, като се отметнат само 2 нгама битове. С дефинирането на желания LFSR, шифърът на потока всъщност е разбит.

Освен LFSR се използват и регистри за смяна с нелинейна обратна връзка, трансферна обратна връзка и др.

Редица генератори са разработени на базата на теоретико-числовия подход (генератори на Блум-Микали, RSA, BBS, компресионни, адитивни генератори и др.).

Математическата поддръжка за синтеза на поточни криптографски алгоритми е разработена по-пълно и подробно в сравнение с блоковите криптографски алгоритми. Въпреки това, за създаване на поточни шифри често се използват алгоритми за блоково шифиране в режими OFB или CFB.

Най-простият вид функция за обратна връзка е линейна функция, като сумата по модул 2 на съдържанието на определени битове. Такъв регистър се нарича регистър на преместване с линейна обратна връзка (накратко LFSR). В общия случай линейната функция на обратната връзка се дава с формулата . Тук c k= 1 ако к th бит се използва във функцията за обратна връзка и c k= 0 в противен случай. Символът Å означава събиране по модул 2 (изключващо ИЛИ).

Например, разгледайте LFSR с функция за обратна връзка (вижте фигурата).

Ако първоначалното състояние на регистъра е 1111, тогава в следващите тактове той ще приеме следните серии от състояния: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100 , 1110, 1111, 1111, 1111 …

Изходната последователност се формира от най-малката (най-дясната) цифра на регистъра. Тя ще изглежда така: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Вижда се, че генерираната битова последователност се определя изцяло от началното състояние на регистъра и функцията за обратна връзка. Тъй като броят на възможните състояния на регистъра е краен (той е равен на 2 Л), тогава рано или късно ключовата последователност ще започне да се повтаря. Максималната дължина на неповтаряща се част от ключова последователност се нарича неин период. T. Периодът зависи от функцията за обратна връзка. Максималният възможен период е Tмакс=2 Л-1 (регистърът приема всички възможни състояния с изключение на 0000...0). Извиква се изходната последователност на LFSR с максимален период М-последователност.

За да разберете условията, при които LFSR ще има максимален период, функциите за обратна връзка съответстват на характеристичния полином. И така, регистърът, даден по-горе като пример, съответства на полинома. Теоретичният анализ показва, че LFSR ще има максимален период тогава и само ако полиномът П(х) е примитивен. По-долу са някои примитивни полиноми, препоръчани за практическа употреба. Таблицата показва степените на променливата хв полинома. Например записът (31, 3) съответства на полинома.

LFSR първоначално са проектирани да бъдат внедрени в хардуера като набор от цифрови схеми. Софтуерните реализации на LFSR обикновено са по-бавни от хардуерните реализации. За да се увеличи производителността, е полезно състоянието на регистъра да се съхранява като цяло число Л- битово число, чиито отделни битове съответстват на двоичните цифри на регистъра. След това се използват битови операции (преместване, маскиране и т.н.) за достъп до отделни битове.