Rejestr przesuwający z liniowym sprzężeniem zwrotnym

Rejestr przesuwający z liniowym sprzężeniem zwrotnym (Szablon:Ang., 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 $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 $\phi (2^d-1)/d.$ Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie $\phi (2^7-1)/7=\phi (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 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),
• regulacja większościowa częstotliwości taktowania rejestru (np. taka jak w szyfrze strumieniowym A5/1).

Zobacz też

• A5 (kryptografia)
• szyfr strumieniowy

Bibliografia

• Szablon:Cytuj książkę
• Szablon:Cytuj stronę