Rejestr przesuwający z liniowym sprzężeniem zwrotnym

LFSR (Linear Feedback Shift Register, rejestr przesuwający z liniowym sprzężeniem zwrotnym^{[potrzebne źródło]}) – rejestr przesuwający, którego bit wejściowy jest funkcją liniową jego poprzedniego stanu.

Jedynymi funkcjami liniowymi w dziedzinie pojedynczych bitów są EX-OR oraz EX-NOR. Z tego powodu LFSR można zdefiniować jako rejestr przesuwający, którego wejście jest wysterowane funkcją XOR stanów kilku z komórek tworzących rejestr.

Najczęstsze zastosowania LFSR to generowanie liczb pseudolosowych i pseudoszumu.

Każdy LFSR jest związany z określonym wielomianem z pierścienia wielomianów $R[t]$, gdzie R jest ciałem skończonym $\mathbb{Z}_2$.

Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie $2^d - 1$, gdzie d jest stopniem wielomianu (ciało $\mathbb{Z}_2$ ma charakterystykę równą 2).

Okres danego LFSR jest maksymalny jeżeli stowarzyszony z nim wielomian jest wielomianem pierwotnym. Rejestr taki, nazywamy rejestrem maksymalnej długości.

Liczba wielomianów pierwotnych stopnia d jest wyznaczona przez funkcję Eulera i wynosi $\varphi(2^d - 1)/d$. Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie $\varphi(2^7 - 1)/7 = \varphi(127)/7 = 126/7 = 18$ rejestrów maksymalnej długości.

Jeżeli znany jest stopień wielomianu wystarczy zaledwie 2d bitów wyjścia rejestru, by znaleźć ów wielomian. (Gdyż należy rozwiązać d równań, każde z d niewiadomymi, ale żeby otrzymać d równań wystarczy zaledwie 2d bitów wyjścia)

W celu stosowanie rejestrów w kryptografii. Np. w szyfrach strumieniowych wykorzystuje się różne metody przełamywania liniowości:

• nielinowa kombinacja kilku bitów z aktualnego stanu rejestru,
• kombinacja bitów z kilku różnych rejestrów za pomocą funkcji nieliniowej,
• nieliniowa kombinacja bitów z kilku różnych rejestrów (n.p. generator redukujący),
• regulacja większościowa częstotliwości taktowania rejestru (n.p. taka jak w szyfrze strumieniowym A5/1).

Zobacz też

• Szyfr strumieniowy
• A5 (kryptografia)

Bibliografia

• 6. Stream Ciphers. W: Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of applied cryptography. Boca Raton: CRC Press, 1997. ISBN 0-8493-8523-7.
• Berlekamp-Massey Algorithm (ang.). 2005-04-14. [dostęp 2010-06-03].