Rejestr przesuwający z liniowym sprzężeniem zwrotnym

Rejestr przesuwający z liniowym sprzężeniem zwrotnym (ang. linear feedback shift register, LFSR) – 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 ${\displaystyle R[t],}$ gdzie ${\displaystyle R}$ jest ciałem skończonym ${\displaystyle \mathbb {Z} _{2}.}$

Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie ${\displaystyle 2^{d}-1,}$ gdzie ${\displaystyle d}$ jest stopniem wielomianu (ciało ${\displaystyle \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 ${\displaystyle d}$ jest wyznaczona przez funkcję Eulera i wynosi ${\displaystyle \varphi (2^{d}-1)/d.}$ Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie ${\displaystyle \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 ${\displaystyle 2d}$ bitów wyjścia rejestru, by znaleźć ów wielomian. (Gdyż należy rozwiązać ${\displaystyle d}$ równań, każde z ${\displaystyle d}$ niewiadomymi, ale żeby otrzymać ${\displaystyle d}$ równań wystarczy zaledwie ${\displaystyle 2d}$ bitów wyjścia)

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

• nieliniowa 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 (np. generator redukujący)^[1],
• regulacja większościowa częstotliwości taktowania rejestru (np. taka jak w szyfrze strumieniowym A5/1).

Zobacz też

• A5 (kryptografia)
• szyfr strumieniowy

Przypisy

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.). PlanetMath, 2005-04-14. [dostęp 2010-06-03]. [zarchiwizowane z tego adresu (2012-07-16)].