• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Rejestr przesuwny z liniowym sprzężeniem zwrotnym

    Przeczytaj także...
    Generator liczb pseudolosowych (Pseudo-Random Number Generator, lub PRNG) to program lub podprogram, który na podstawie niewielkiej ilości informacji (ziarno, zarodek, ang. seed) generuje deterministycznie ciąg bitów, który pod pewnymi względami jest nieodróżnialny od ciągu uzyskanego z prawdziwie losowego źródła.Szyfr strumieniowy – nazywany także algorytmem strumieniowym, algorytmem potokowym lub szyfrem strumieniowym; jest to algorytm symetryczny, który szyfruje oddzielnie każdy bit wiadomości. Algorytm ten składa się z generatora strumienia bitowego, będącego kluczem szyfrującym oraz elementu dodającego (na przykład operacji XOR).
    Rejestr – układ służący do przechowywania i odtwarzania informacji w postaci bitów. Na każdej pozycji rejestru przechowywany jest jeden bit informacji.

    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.

    Rejestr przesuwający – zwany też rejestrem przesuwnym, to rejestr zbudowany z przerzutników połączonych ze sobą w taki sposób, iż w takt impulsów zegarowych przechowywana informacja bitowa przemieszcza się (przesuwa) do kolejnych przerzutników.PlanetMath - wolna encyklopedia matematyczna typu Wiki, rozwijana online, hostowana przez Digital Library Research Lab w Virginia Tech.

    Każdy LFSR jest związany z określonym wielomianem z pierścienia wielomianów , gdzie R jest ciałem skończonym .

    A5 – rodzina algorytmów kryptograficznych stosowanych do zapewniania poufności transmisji głosu i danych w sieciach GSM.Funkcja φ (Eulera) lub tocjent – funkcja nosząca nazwisko Eulera przypisująca każdej liczbie naturalnej liczbę liczb względnie z nią pierwszych nie większych od niej samej.

    Okres rejestru jest ograniczony przez stopień stowarzyszonego z nim wielomianu i wynosi maksymalnie , gdzie d jest stopniem wielomianu (ciało 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 . Tak więc, dla przykładu dla rejestrów długości 7 istnieje dokładnie 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 nie-liniowej,
  • 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)
  • Przypisy

    1. The Shrinking Generator. W: Coppersmith, Krawczyk, Mansour: Advances in Cryptology - CRYPTO '93. s. 22-39. DOI: 10.1007/3-540-48329-2. (ang.)

    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)].



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.03 sek.