Wikipedia

Rejestr przesuwający z liniowym sprzężeniem zwrotnym: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
GDR! (dyskusja | edycje)
166 edycji
m Literówka
Znaczniki: Z urządzenia mobilnego Z wersji mobilnej (przeglądarkowej)
Linia 3:
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 [[Generator liczb pseudolosowych|generowanie liczb pseudolosowych]] i pseudoszumu.
 
Każdy LFSR jest związany z określonym wielomianem z [[pierścień wielomianów|pierścienia wielomianów]] <math>R[t],</math>, gdzie '''<math>R'''</math> jest [[ciało skończone|ciałem skończonym]] <math>\mathbb{Z}_2.</math>.
 
Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie <math>2^d - 1,</math>, gdzie ''<math>d''</math> jest stopniem wielomianu (ciało <math>\mathbb{Z}_2</math> 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 ''<math>d''</math> jest wyznaczona przez [[funkcja φ|funkcję Eulera]] i wynosi <math>\varphi(2^d - 1)/d.</math>.
Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie <math>\varphi(2^7 - 1)/7 = \varphi(127)/7 = 126/7 = 18</math> rejestrów maksymalnej długości.
 
Jeżeli znany jest stopień wielomianu wystarczy zaledwie 2''d''<math>2d</math> bitów wyjścia rejestru, by znaleźć ów wielomian. (Gdyż należy rozwiązać ''<math>d''</math> równań, każde z ''<math>d''</math> niewiadomymi, ale żeby otrzymać ''<math>d''</math> równań wystarczy zaledwie 2''d''<math>2d</math> bitów wyjścia)
 
W celu stosowania rejestrów w kryptografii., Npnp. w [[szyfr strumieniowy|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 (n.pnp. generator redukujący)<ref name="ShrinkingGenerator" />,
* regulacja większościowa częstotliwości taktowania rejestru (n.pnp. taka jak w szyfrze strumieniowym [[A5 (kryptografia)|A5/1]]).
 
== Zobacz też ==
* [[Szyfr strumieniowy]]▼
* [[A5 (kryptografia)]]
▲* [[Szyfrszyfr strumieniowy]]
 
== Przypisy ==
{{Przypisy|
<ref name="ShrinkingGenerator">{{cytuj książkę |nazwisko = Coppersmith |imię = Don |nazwisko2 = Krawczyk |imię2 = Hugo |nazwisko3 = Mansour |imię3 = Yishay |tytuł = Advances in Cryptology – CRYPTO ’93 |doi = 10.1007/3-540-48329-2 |strony = 22–39 |rozdział = The Shrinking Generator |język = en}}</ref>
<ref name="ShrinkingGenerator">{{cytuj książkę
| nazwisko = Coppersmith
| imię = Don
| nazwisko2 = Krawczyk
| imię2 = Hugo
| nazwisko3 = Mansour
| imię3 = Yishay
| tytuł = Advances in Cryptology - CRYPTO '93
| doi = 10.1007/3-540-48329-2
| strony = 22-39
| rozdział = The Shrinking Generator
| język = en
}}</ref>
}}
 
== Bibliografia ==
* {{Cytuj książkę |nazwisko = Menezes |imię = Alfred J. |nazwisko2 = van Oorschot |imię2 = Paul C. |nazwisko3 = Vanstone |imię3 = Scott A. |tytuł = Handbook of applied cryptography |rozdział = 6. Stream Ciphers |data = 1997 |wydawca = CRC Press |miejsce = Boca Raton |isbn = 0-8493-8523-7 |strony =}}
* {{Cytuj książkę
* {{cytuj stronę |url = http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html |tytuł = Berlekamp-Massey Algorithm |opublikowany = [[PlanetMath]] |data = 2005-04-14 |język = en |archiwum = http://web.archive.org/web/20120716181541/http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html |zarchiwizowano= 2012-07-16 |data dostępu = 2010-06-03}}
| nazwisko = Menezes
| imię = Alfred J.
| nazwisko2 = van Oorschot
| imię2 = Paul C.
| nazwisko3 = Vanstone
| imię3 = Scott A.
| tytuł = Handbook of applied cryptography
| rozdział = 6. Stream Ciphers
| data = 1997
| wydawca = CRC Press
| miejsce = Boca Raton
| isbn = 0-8493-8523-7
| strony =
}}
* {{cytuj stronę
| url = http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html
| tytuł = Berlekamp-Massey Algorithm
| opublikowany = [[PlanetMath]]
| data dostępu = 2010-06-03
| data = 2005-04-14
| język = en
| archiwum = http://web.archive.org/web/20120716181541/http://planetmath.org/encyclopedia/BerlekampMasseyAlgorithm.html
| zarchiwizowano= 2012-07-16
}}
 
[[Kategoria:Elektronika cyfrowa]]
Źródło: „https://pl.wikipedia.org/wiki/Rejestr_przesuwający_z_liniowym_sprzężeniem_zwrotnym”