Rejestry zmianowe z informacją zwrotną. Teoretyczne podstawy działania Liniowe sprzężenie zwrotne

Liniowy rejestr przesuwny c sprzężenie zwrotne(Linear Feedback Shift Register - LFSR) - mechanizm tworzenia pseudolosowej sekwencji bitów binarnych. Rejestr (rys. 1) składa się z wielu komórek, które są ustawione przez wektor inicjujący (najczęściej tajny klucz). Działanie rejestru jest określone przez obecność lub brak połączenia każdego bitu ze sprzężeniem zwrotnym. Krany rejestru sprzężenia zwrotnego nie są stałe, ale są częścią klucza. W kolejnym kroku zawartość komórek rejestrów zostaje przesunięta o jedną pozycję w prawo, a w wyniku operacji XOR o jeden bit wolny w lewo umieszczany jest w komórce skrajnej lewej.

Ryż. jeden. Rejestr liniowy zmiana sprzężenia zwrotnego

Aby osiągnąć maksymalny okres gamma szyfru, liczba cyfr m rejestr przesuwny jest wybrany jako jedna z liczb pierwszych Mersenne'a (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), a łącza wewnętrzne rejestru musi być wybrany zgodnie z nierozkładalnymi wielomianami pierwotnymi o najwyższym stopniu m. W tym przypadku okres gamma szyfru może osiągnąć (2 m-1).

LFSR jest szybki i łatwy do wdrożenia zarówno w oprogramowaniu, jak i sprzęcie. Przy odpowiednim doborze bitów sprzężenia zwrotnego generowane sekwencje mają dobre właściwości statystyczne. LFSR jest używany jako element bazowy do budowy wysoce bezpiecznych systemów.

Kaskada rejestrów to zestaw LFSR połączonych w taki sposób, że zachowanie jednego LFSR zależy od zachowania poprzedniego LFSR w kaskadzie. To „zależne” zachowanie jest zwykle skonfigurowane do kontrolowania licznika zmiany następnego LFSR przez pierwszy LFSR.

Np. rejestr jest przesuwany o jeden krok, jeśli wartość poprzedniego rejestru wynosi 1, a jeśli wartość wynosi 0, to rejestr jest przesuwany o dwa kroki lub inaczej. Duża liczba Takie kombinacje zapewniają bardzo wysokie bezpieczeństwo.

Najbezpieczniejsze sekwencje są tworzone przez generator kurczący się w oparciu o prostą interakcję między wynikami dwóch rejestrów LFSR. Bity jednego wyniku określają, czy odpowiednie bity drugiego wyniku zostaną użyte jako część pełnego „klucza strumienia”. Generator kompresji jest prosty, skalowalny i ma dobre właściwości bezpieczeństwa. Jego wadą jest to, że szybkość generowania „klucza przesyłania strumieniowego” nie będzie stała, o ile nie zostaną podjęte pewne środki ostrożności.

Metoda Fibonacciego z opóźnieniami Jeden z powszechnie stosowanych generatorów Fibonacciego oparty jest na następującej iteracyjnej formule:

gdzie Y k - liczby rzeczywiste poza zakresem

Ryż. 2. Szyfrowanie round-robin

Tryb sprzężenia zwrotnego DES może być używany do generowania liczb pseudolosowych, podobnie jak jest używany do szyfrowanie strumienia. Dane wyjściowe każdego etapu szyfrowania to wartość 64-bitowa, z której tylko górne j bitów jest przesyłanych z powrotem do szyfrowania. Wyjścia 64-bitowe stanowią ciąg liczb pseudolosowych o dobrych właściwościach statystycznych.

Generator liczb pseudolosowych, opisany w standardzie ANSI X9.17, jest jednym z najbezpieczniejszych kryptograficznie generatorów liczb pseudolosowych. Aplikacje wykorzystujące tę technologię obejmują zabezpieczenia finansowe i aplikacje PGP.

Generator ANSI X9.17 składa się z następujących części (rysunek 3):

1. Wejście: Generator jest kontrolowany przez dwa pseudolosowe wejścia. Pierwsze dane wejściowe to 64-bitowa reprezentacja bieżącej daty i godziny ( ID i), które zmieniają się za każdym razem, gdy tworzony jest numer. Drugie dane wejściowe to 64-bitowa wartość początkowa, która jest inicjowana do pewnej wartości arbitralnej i zmieniana podczas generowania ciągu liczb pseudolosowych ( Vi).

2. Klucze: Generator wykorzystuje trzy potrójne moduły DES z dwoma kluczami K 1 , K 2 . Wszystkie trzy używają tej samej pary kluczy 56-bitowych, która musi być utrzymywana w tajemnicy i używana tylko do generowania liczby pseudolosowej.

Ryż. 3. Generator liczb pseudolosowych ANSI X9.17

Rejestr przesuwny sprzężenia zwrotnego składa się z dwóch części: rejestru przesuwnego i funkcje sprzężenia zwrotnego.

Rysunek 19. Rejestr przesuwny sprzężenia zwrotnego.

Ogólnie rzecz biorąc, rejestr przesuwny to sekwencja niektórych elementów pierścienia lub pola. Najczęściej używane fragment rejestry przesuwne. Długość takiego rejestru wyrażona jest liczbą bitów. Za każdym razem, gdy pobierany jest bit, wszystkie bity w rejestrze są przesuwane w prawo o jedną pozycję. Nowy najbardziej znaczący bit jest obliczany jako funkcja wszystkich pozostałych bitów w rejestrze. Wyjście jest zwykle najmniej znaczącym bitem. Okres rejestru przesuwnego to długość sekwencji wyjściowej, zanim zacznie się powtarzać.

Najprostszym typem rejestrów przesuwnych jest rejestr przesuwny z liniowym sprzężeniem zwrotnym (LFSR lub LRS). Sprzężenie zwrotne to prosta operacja XOR na niektórych bitach rejestru. Lista tych bitów jest zdefiniowana wielomian charakterystyczny i zadzwoniłem sekwencja kranu. Czasami ten schemat nazywa się Konfiguracja Fibonacciego.

Ryc.20. LFOS w konfiguracji Fibonacciego.

Na wdrażanie oprogramowania LFSR używają zmodyfikowanego schematu: aby wygenerować nowy znaczący bit, zamiast używać bitów sekwencji zaczepów, każdy bit sekwencji zaczepów jest XORowany z wyjściem generatora, zastępując stary bit sekwencji zaczepów. Ta modyfikacja jest czasami nazywana Konfiguracja Galois.

Rys.21. RLOS konfiguracji Galois.

n-bit LFSR może być w jednym z 2 n– 1 stany wewnętrzne. Oznacza to, że teoretycznie taki rejestr może generować ciąg pseudolosowy o okresie 2 n– 1 bit (dopełnianie zerami jest całkowicie bezużyteczne). Przejście wszystkich 2 n– 1 stany wewnętrzne możliwe tylko przy określonych sekwencjach zaczepów. Takie rejestry nazywane są LFSR z maksymalnym okresem. Aby zapewnić maksymalny okres LFSR, konieczne jest, aby jego wielomian charakterystyczny był prymitywny modulo 2. Stopień wielomianu to długość rejestru przesuwnego. Wielomian stopnia pierwotnego n- to jest takie nieskracalny wielomian, który jest dzielnikiem, ale nie jest dzielnikiem x d+ 1 za wszystkich D, które są dzielnikami 2 n– 1. (Omawiając wielomiany, termin Liczba pierwsza zastąpiony terminem wielomian nierozkładalny). Wielomian charakterystyczny LFSR pokazany na rysunkach:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

jest prymitywnym modulo 2. Okres takiego rejestru będzie maksymalny, przechodząc przez wszystkie 2 32 - 1 wartości, aż się powtórzą. Najczęściej stosowane są wielomiany pocienione, czyli które mają tylko niektóre współczynniki. najbardziej popularne trójmiany.

Ważny parametr generator oparty na RLSS, jest złożoność liniowa. Jest definiowany jako długość n najkrótszy LFSR, który może symulować moc generatora. Złożoność liniowa jest ważna, ponieważ z prostym Algorytm Berlenkampa-Masseya możliwe jest odtworzenie takiego LFSR poprzez zaznaczenie tylko 2 n bity gamma. Z definicją pożądanego LFSR szyfr strumieniowy jest faktycznie złamany.

Rejestr przesuwny sprzężenia zwrotnego ( FSR ) składa się z dwóch części: rejestr przesuwny oraz funkcje sprzężenia zwrotnego .

Rejestr przesuwny (błąd: źródło odniesienia) nie znaleziono) to ciąg bitów. Kiedy trzeba wyodrębnić bit, wszystkie bity rejestru przesuwnego są przesuwane w prawo o 1 pozycję. Nowy lewy bit to wartość funkcji sprzężenia zwrotnego z pozostałych bitów w rejestrze. Okres Rejestr przesuwny to długość wynikowej sekwencji, zanim zacznie się powtarzać.

Najprostszym rodzajem rejestru przesuwnego ze sprzężeniem zwrotnym jest liniowy rejestr przesuwny ze sprzężeniem zwrotnym (LFSR – Lewo Sprzężenie zwrotne Zmiana Zarejestrować) (Błąd: nie znaleziono źródła odniesienia). Sprzężenie zwrotne to po prostu XOR niektórych p bitów. rejestru, lista tych bitów nazywa się sekwencja obejścia.

n-bit LFSR może być w jednym z 2 n -1 stany wewnętrzne. Oznacza to, że teoretycznie taki rejestr może generować ciąg pseudolosowy z kropką 2 n -1 bity. Liczba stanów wewnętrznych i okres są sobie równe, ponieważ wypełnienie rejestru zerami spowoduje powstanie nieskończonego ciągu zer, co jest absolutnie bezużyteczne. Tylko w przypadku niektórych sekwencji kranu LFSR przejdzie przez wszystkie 2 n -1 stany wewnętrzne. Takie LFSR są nazywane LFSRz maksymalnym okresem.

Aby konkretny LFSR miał maksymalny okres, wielomian utworzony z sekwencji zaczepienia i stałej 1 musi być prymitywnym modulo 2 .

Obliczanie prymitywizmu wielomianu jest dość złożonym problemem matematycznym. Dlatego istnieją gotowe tabele, które zawierają numery sekwencji zaczepów, które zapewniają maksymalny okres generatora. Na przykład dla 32-bitowego rejestru przesuwnego można znaleźć następujący wpis: (32,7,5,3,2,1,0) . Oznacza to, że aby wygenerować nowy bit, musisz zsumować trzydziesty drugi, siódmy, piąty, trzeci, drugi i pierwszy za pomocą funkcji XOR.

Kod dla takiego LFSR w C++ byłby następujący:

// Dowolna wartość inna niż zero

ShiftRejestr = ((((ShiftRejestr >> 31)

^(ShiftRejestr>>6)

^(ShiftRejestr>>4)

^(ShiftRejestr>>2)

^(ShiftRejestr>>1)

^Zmiana rejestru)

& 0x000000001)<<31)

| (ShiftRejestr >> 1);

return ShiftRejestr & 0x0000001;

Implementacje programowe LFSRs są dość wolne i działają szybciej, jeśli są napisane w asemblerze, a nie w C. Jednym z rozwiązań jest użycie 16 LFSRs równolegle (lub 32 w zależności od długości słowa w architekturze konkretnego komputera). W tym schemacie używana jest tablica słów, której rozmiar jest równy długości LFSR, a każda jednostka słowa w tablicy odnosi się do własnego LFSR. Zakładając, że używane są te same numery sekwencji kranu, może to dać zauważalny wzrost wydajności.

Z obwód sprzężenia zwrotnego można również zmodyfikować. W tym przypadku generator nie będzie miał większej siły kryptograficznej, ale łatwiej będzie go zaimplementować programowo. Zamiast używać skrajnego lewego bitu sekwencji zaczepów do generowania nowego bitu, XOR każdy bit sekwencji zaczepów z wyjściem generatora i zastąp go wynikiem tej akcji, wtedy wynik generatora staje się nowym skrajnym lewym bit (Błąd: nie znaleziono źródła odniesienia).

Ta modyfikacja nazywa się Konfiguracja Galois. W języku C wygląda to tak:

static unsigned long ShiftRegister = 1;

void seed_LFSR (długi materiał siewny bez znaku)

ShiftRejestr = nasiona;

int Galua_LFSR(nieważny)

jeśli (ShiftRejestr i 0x000000001) (

ShiftRejestr = (ShiftRejestr ^ maska ​​>> 1) | 0x8000000;

ShiftRejestr >>= 1;

Korzyścią jest to, że wszystkie XOR są wykonywane w jednej operacji. Ten obwód może być również zrównoleglony.

Same LFSR są dobrymi generatorami sekwencji pseudolosowych, ale mają pewne niepożądane nielosowe właściwości. Bity sekwencyjne są liniowe, co czyni je bezużytecznymi do szyfrowania. Dla długości LFSR n stan wewnętrzny reprezentuje poprzedni n bity wyjściowe generatora. Nawet jeśli schemat informacji zwrotnych jest utrzymywany w tajemnicy, można go określić przez: 2 n bity wyjściowe generatora przy użyciu specjalnych algorytmów. Ponadto duże losowe liczby, generowane przy użyciu kolejnych bitów tej sekwencji, są silnie skorelowane i dla niektórych typów aplikacji nie są losowe. Mimo to LFSR są często używane do tworzenia algorytmów szyfrowania. W tym celu stosuje się kilka LFSR, zwykle o różnych długościach i numerach sekwencji gwintowania. Kluczem jest stan początkowy rejestrów. Za każdym razem, gdy potrzebny jest nowy bit, wszystkie rejestry są przesuwane. Ta operacja nazywa się taktowanie. Bit wyjściowy jest funkcją, najlepiej nieliniową, niektórych bitów LFSR. Ta funkcja nazywa się łączenie, a generator jako całość - łączenie generatora. Wiele z tych generatorów jest nadal bezpiecznych.

Rejestr zmiany liniowego sprzężenia zwrotnego(RSLOS, inż. liniowy rejestr przesuwny ze sprzężeniem zwrotnym, LFSR ) to rejestr przesuwny słów bitowych, w którym wartość bitu wejściowego (przesuwnego) jest równa liniowej funkcji logicznej z wartości pozostałych bitów rejestru przed przesunięciem. Może być zorganizowany zarówno przez oprogramowanie, jak i sprzęt. Służy do generowania bitów pseudolosowych sekwencji, co jest wykorzystywane w szczególności w kryptografii.

Opis

Sterowanie rejestrami w implementacjach sprzętowych odbywa się poprzez zastosowanie impulsu przesuwającego (inaczej zwanego taktowany lub impuls synchronizacji) dla wszystkich komórek. Zarządzanie rejestrami we wdrożeniach oprogramowania odbywa się poprzez wykonanie pętli. W każdej iteracji pętli obliczana jest funkcja sprzężenia zwrotnego, a bity w słowie są przesuwane.

Zasada działania

Złożoność liniowa

Niezależność korelacji

Próbując uzyskać wysoką liniową złożoność generowanej sekwencji, kryptografowie nieliniowo łączą wyjścia kilku rejestrów przesuwnych. W takim przypadku co najmniej jedna sekwencja wyjściowa (lub nawet wyjścia poszczególnych LFSR) może być połączona wspólnym strumieniem i otwarta przez kryptoanalityka. Hacking oparty na takiej podatności nazywa się otwarcie  korelacji. Główną ideą takiego hacka jest znalezienie pewnej korelacji między mocą wyjściową generatora a jego mocą wyjściową. części składowe. Następnie, obserwując sekwencję wyjść, można uzyskać informacje o tych wyjściach pośrednich, a tym samym zhakować generator. Thomas Siegenthaler wykazał, że możliwe jest dokładne zdefiniowanie niezależności korelacji i że istnieje kompromis między niezależnością korelacji a złożonością liniową.

Wdrażanie oprogramowania

Implementacje programowe RSLOS są dość wolne i działają szybciej, jeśli są napisane w asemblerze. Jednym z rozwiązań jest równoległe użycie 16 RLLS (lub 32, w zależności od długości słowa w architekturze komputera). W takim schemacie używana jest tablica słów, których rozmiar jest równy długości rejestru przesuwnego, a każdy bit słowa odnosi się do własnego LFSR. Ponieważ używana jest ta sama liczba sekwencji zaczepów, może to dać zauważalny wzrost wydajności generatora.

Konfiguracja Fibonacciego

Rozważmy 32-bitowy rejestr przesuwny. Ma sekwencję ucieczki (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). Oznacza to, że aby wygenerować nowy bit, konieczne jest zsumowanie bitów 31, 30, 29, 27, 25 i 0 za pomocą operacji XOR. Wynikowy LFSR ma maksymalny okres 2 32 − 1 (\displaystyle 2^(32)-1). Kod takiego rejestru w C jest następujący:

int LFSR_Fibonacci (void ) ( static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25) ^ S) i 0x00000001)<< 31 ) | (S >> 1); zwróć S & 0x0000001 ; )

Konfiguracja Galois

Ten generator nie ma większej siły kryptograficznej, ale daje wzrost wydajności: wszystkie operacje XOR można wykonać w jednej operacji poprzez zrównoleglenie, a nie sekwencyjnie jedna po drugiej, jak w konfiguracji Fibonacciego. Ten schemat przyniesie również korzyści w implementacji sprzętu.

Kod 32-bitowego rejestru przesuwnego w C jest następujący:

int LFSR_Galois (void ) ( static unsigned long S = 0x00000001 ; if ( S & 0x00000001 ) ( S = ( S ^ 0x80000057 >> 1 ) | 0x80000000 ; zwróć 1 ;) else ( S >>= 1 ; zwróć 0 ;)) )

Należy zauważyć, że pętla o stałej liczbie wywołań funkcji LFSR_Galois w konfiguracji Galois jest wykonywana około 2 razy szybciej niż funkcja LFSR_Fibonacci w konfiguracji Fibonacciego (kompilator MS VS 2010 na Intel Core i5).

Przykład wygenerowanej sekwencji

Konfiguracja Fibonacciego

Niech LFSR będzie dana przez wielomian charakterystyczny x 3 + x + 1 (\displaystyle x^(3)+x+1). Oznacza to, że bity zaczepu będą 2 i 0, a jednostka we wzorze wielomianu oznacza, że ​​0 bit jest wejściem. Funkcja sprzężenia zwrotnego ma postać S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Załóżmy, że początkowy stan rejestru przesuwnego to sekwencja. Dalsze stany rejestru przedstawia poniższa tabela:

Ponieważ stan wewnętrzny w kroku siódmym powrócił do stanu pierwotnego, to począwszy od kroku następnego bity będą się powtarzać. Tak więc wygenerowana sekwencja to: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1. . . ] (\styl wyświetlania\po lewej)(kolejność bitów w sekwencji odpowiada kolejności, w jakiej zostały wygenerowane przez LFSR). Zatem okres ciągu wynosi 7, czyli maksymalna możliwa wartość, jaka nastąpiła z powodu prymitywizmu danego wielomianu.

Konfiguracja Galois

Weźmy ten sam wielomian charakterystyczny, czyli c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Tylko pierwszy bit jest dodawany do bitu wyjściowego. Stan początkowy jest taki sam. Dalsze stany rejestru:

Stan wewnętrzny rejestru w kroku siódmym powrócił do stanu pierwotnego, zatem jego okres jest również równy 7. W przeciwieństwie do konfiguracji Fibonacciego stany wewnętrzne rejestru okazały się inne, ale wygenerowana sekwencja jest taka sama , przesunięte tylko o 4 cykle: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\styl wyświetlania\po lewej)(kolejność bitów w sekwencji odpowiada kolejności, w jakiej zostały wygenerowane przez LFSR).

Generowanie prymitywnych wielomianów

Zalety i wady

Zalety

• wysoka wydajność algorytmów kryptograficznych tworzonych w oparciu o LFSR (np. szyfry strumieniowe);
• użycie tylko najprostszych operacji bitowych dodawania i mnożenia, zaimplementowanych sprzętowo w prawie wszystkich urządzeniach obliczeniowych;
• dobre właściwości kryptograficzne (LFSR mogą generować sekwencje długookresowe o dobrych właściwościach statystycznych);
• ze względu na swoją strukturę, LFSR można łatwo analizować metodami algebraicznymi.

Wady

Sposoby poprawy siły kryptograficznej generowanych sekwencji

Generatory z wieloma rejestrami przesuwnymi

Ten typ generatora składa się z kilku rejestrów przesuwnych z liniowym sprzężeniem zwrotnym, które generują bity x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\kropki ,\;x_(M,i)) odpowiednio. Co więcej, wygenerowane bity są przekształcane przez jakąś funkcję logiczną f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\kropki ,\;x_(M ,i))). Należy zauważyć, że generatory tego typu mają długości rejestrów L ja (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\kropki ,\;M), są względem siebie pierwszorzędne.

Okres tego generatora to T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 LM − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), gdzie L = ∑ i = 1 M L ja (\displaystyle L=\suma\limity _(i=1)^(M)L_(i))- całkowita liczba komórek. Dlatego użycie kilku LFSR-ów wydłuża okres generowanej sekwencji w porównaniu z pojedynczym rejestrem, co zwiększa siłę kryptograficzną generatora. Zwiększa również złożoność liniową lub długość najkrótszego rejestru odpowiadającego danemu generatorowi. Rejestr taki znajdujemy za pomocą algorytmu Berlekampa-Masseya z wykorzystaniem wygenerowanej sekwencji. V najlepszy przypadek jego długość jest proporcjonalna do okresu generowanego ciągu.

Generatory z przekształceniami nieliniowymi

Schemat blokowy takiego generatora nie różni się od schematu poprzedniego generatora. Główną różnicą jest to, że urządzenie transformujące jest podane przez nieliniową funkcję Boole'a f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\kropki,x_(M))). Na przykład wielomian Zhegalkina jest traktowany jako taka funkcja (zgodnie z twierdzeniem Zhegalkina każda funkcja logiczna może być jednoznacznie reprezentowany przez wielomian Zhegalkina).

Generator nieliniowy można również zaimplementować na rejestr przesuwny z nieliniowym sprzężeniem zwrotnym. On może dać 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L)) warianty sekwencji maksymalny okres , który jest większy niż LFSR .

Siła kryptograficzna tego generatora jest zwiększona ze względu na nieliniowość użytej funkcji. Wyznaczenie stanu rejestrów z wygenerowanego ciągu bitów jest złożonym problemem matematycznym, ponieważ nie jest znany żaden algorytm odtwarzający stany pierwotne.

Ta metoda jest używana na przykład w generator (Geff) i uogólniony generator Geff, jednak takie generatory mogą zostać złamane przez atak korelacji.

Generatory z różnymi czasami rejestru przesuwnego

generator stop-go

generator stop-go(angielski Stop-and-Go , Both-Piper ) wykorzystuje wyjście LFOS-1 do sterowania częstotliwością zegara LFOS-2, tak że LFSR-2 zmienia swój stan w pewnym momencie tylko wtedy, gdy wyjście LFOS-1 w tym czasie była równa jednostce. Schemat ten nie oparł się otwarciu korelacji.

W celu zwiększenia siły kryptograficznej zaproponowano alternator typu stop-and-go. Wykorzystuje trzy rejestry przesuwne o różnych długościach. Tutaj LFOS-1 kontroluje częstotliwość zegara drugiego i trzeciego rejestru, to znaczy LFSR-2 zmienia swój stan, gdy wyjście LFSR-1 jest równe jeden, a LFSR-3 - gdy wyjście LFSR-1 jest równe zero. Wyjściem generatora jest operacja dodania modulo dwóch wyjść RSLOS-2 i RSLOS-3. Ten generator ma duży okres i dużą liniową złożoność. Istnieje metoda otwierania korelacji RLOS-1, ale nie osłabia to znacząco właściwości kryptograficznych generatora.

Wyrafinowany schemat taktowania jest używany w dwukierunkowy generator typu stop-and-go, który wykorzystuje 2 rejestry przesuwne o tej samej długości. Jeśli wyjście RLOS-1 w pewnym momencie? t ja − 1 (\displaystyle t_(i-1))- jeden, to RLOS-2 nie jest taktowany w tym czasie t ja (\displaystyle t_(i)). Jeśli wyjście RLOS-2 w chwili czasu t ja − 1 (\displaystyle t_(i-1)) równa się zero, a w czasie t ja − 2 (\displaystyle t_(i-2))- jeden, a jeśli ten rejestr jest taktowany w tym czasie t ja (\displaystyle t_(i)), to w tym samym momencie RLOS-1 nie jest taktowany. Liniowa złożoność tego obwodu jest w przybliżeniu równa okresowi wygenerowanej sekwencji.

Generator samodziesiątkujący

Oscylator wieloczęstotliwościowy z produktem wewnętrznym

Ten generator wykorzystuje dwa rejestry przesuwne RSLOS-1 i RSLOS-2. Częstotliwość zegara RSLOS-2 w d (\displaystyle d) razy więcej niż RSLOS-1. Niektóre bity tych rejestrów są mnożone przez siebie za pomocą operacji AND. Wyniki mnożenia są dodawane przez operację XOR i uzyskiwana jest sekwencja wyjściowa. Ten generator ma dużą złożoność liniową i dobre właściwości statystyczne. Jednak jego stan można określić na podstawie sekwencji wyjściowej o długości L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), gdzie L 1 (\ Displaystyle L_(1)) oraz L 2 (\ Displaystyle L_(2)) są długościami odpowiednio LFOS-1 i LFOS-2, oraz d (\displaystyle d)- stosunek ich częstotliwości taktowania.

Kaskada Gollmanna

Ten obwód jest ulepszoną wersją generatora stop-go. Składa się z sekwencji LFSR, z których synchronizacja każdego z nich jest kontrolowana przez poprzedni LFSR. Jeśli wyjście RLOS-1 w tym czasie t ja (\displaystyle t_(i)) wynosi 1, to RLOS-2 jest taktowany. Jeśli wyjście RLOS-2 w chwili czasu t ja (\displaystyle t_(i)) wynosi 1, to RLOS-3 jest taktowany i tak dalej. Wyjście ostatniego LFSR jest wyjściem generatora. Jeśli długość wszystkich LFSR jest taka sama i równa L (\ Displaystyle L), to okres systemu od M (\styl wyświetlania M) LFSR jest równy (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), a złożoność liniowa to L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

Pomysł ten jest prosty i można go wykorzystać do generowania ciągów z dużymi okresami, dużą złożonością liniową i dobrymi właściwościami statystycznymi. Ale niestety są wrażliwe na autopsję zwaną zamykający(ang. lock-in) kiedy

Rejestr przesuwny sprzężenia zwrotnego składa się z dwóch części: rejestru przesuwnego i funkcje sprzężenia zwrotnego.

Rysunek 19. Rejestr przesuwny sprzężenia zwrotnego.

Ogólnie rzecz biorąc, rejestr przesuwny to sekwencja niektórych elementów pierścienia lub pola. Najczęściej używane fragment rejestry przesuwne. Długość takiego rejestru wyrażona jest liczbą bitów. Za każdym razem, gdy pobierany jest bit, wszystkie bity w rejestrze są przesuwane w prawo o jedną pozycję. Nowy najbardziej znaczący bit jest obliczany jako funkcja wszystkich pozostałych bitów w rejestrze. Wyjście jest zwykle najmniej znaczącym bitem. Okres rejestru przesuwnego to długość sekwencji wyjściowej, zanim zacznie się powtarzać.

Najprostszym typem rejestrów przesuwnych jest rejestr przesuwny z liniowym sprzężeniem zwrotnym (LFSR lub LRS). Sprzężenie zwrotne to prosta operacja XOR na niektórych bitach rejestru. Lista tych bitów jest zdefiniowana wielomian charakterystyczny i zadzwoniłem sekwencja kranu. Czasami ten schemat nazywa się Konfiguracja Fibonacciego.

Ryc.20. LFOS w konfiguracji Fibonacciego.

W implementacji programowej LFSR stosowany jest zmodyfikowany schemat: w celu wygenerowania nowego znaczącego bitu, zamiast używania bitów sekwencji zaczepów, na każdym z jego bitów wykonywana jest operacja XOR z wyjściem generatora, zastępując stary bit sekwencji kranu. Ta modyfikacja jest czasami nazywana Konfiguracja Galois.

Rys.21. RLOS konfiguracji Galois.

n-bit LFSR może być w jednym z 2 n– 1 stany wewnętrzne. Oznacza to, że teoretycznie taki rejestr może generować ciąg pseudolosowy o okresie 2 n– 1 bit (dopełnianie zerami jest całkowicie bezużyteczne). Przejście wszystkich 2 n– 1 stany wewnętrzne możliwe tylko przy określonych sekwencjach zaczepów. Takie rejestry nazywane są LFSR z maksymalnym okresem. Aby zapewnić maksymalny okres LFSR, konieczne jest, aby jego wielomian charakterystyczny był prymitywny modulo 2. Stopień wielomianu to długość rejestru przesuwnego. Wielomian stopnia pierwotnego n- to jest takie nieskracalny wielomian, który jest dzielnikiem, ale nie jest dzielnikiem x d+ 1 za wszystkich D, które są dzielnikami 2 n– 1. (Omawiając wielomiany, termin Liczba pierwsza zastąpiony terminem wielomian nierozkładalny). Wielomian charakterystyczny LFSR pokazany na rysunkach:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

jest prymitywnym modulo 2. Okres takiego rejestru będzie maksymalny, przechodząc przez wszystkie 2 32 - 1 wartości, aż się powtórzą. Najczęściej stosowane są wielomiany pocienione, czyli które mają tylko niektóre współczynniki. najbardziej popularne trójmiany.

Ważnym parametrem generatora opartego na LFSR jest złożoność liniowa. Jest definiowany jako długość n najkrótszy LFSR, który może symulować moc generatora. Złożoność liniowa jest ważna, ponieważ z prostym Algorytm Berlenkampa-Masseya możliwe jest odtworzenie takiego LFSR poprzez zaznaczenie tylko 2 n bity gamma. Z definicją pożądanego LFSR szyfr strumieniowy jest faktycznie złamany.

Oprócz LFSR stosowane są również rejestry przesuwne z nieliniowym sprzężeniem zwrotnym, sprzężeniem zwrotnym transferu itp.

Szereg generatorów zostało opracowanych w oparciu o podejście teorii liczb (generatory Blum-Micali, RSA, BBS, kompresja, generatory addytywne itp.).

Matematyczne wsparcie dla syntezy strumieniowych algorytmów kryptograficznych zostało rozwinięte bardziej i bardziej szczegółowo w porównaniu z blokowymi algorytmami kryptograficznymi. Jednak do tworzenia szyfrów strumieniowych często stosuje się algorytmy szyfrowania blokowego w trybach OFB lub CFB.