Rejestr przesuwny z liniowym sprzężeniem zwrotnym (LFSR) jest mechanizmem tworzenia pseudolosowej sekwencji bitów binarnych. Rejestr (ryc. 1) składa się z szeregu komórek, które są ustawiane przez wektor inicjalizacyjny (najczęściej jest to klucz tajny). Działanie rejestru jest określane przez obecność lub brak komunikacji między każdym bitem a sprzężeniem zwrotnym. Stuknięcia rejestru sprzężenia zwrotnego nie są ustalone, ale stanowią część klucza. W następnym kroku zawartość komórek rejestru jest przesuwana o jedną pozycję w prawo, a jeden bit pozostający wolny w wyniku operacji XOR jest umieszczany w skrajnej lewej komórce.
Figa. 1. Rejestr przesuwny z liniowym sprzężeniem zwrotnym
Aby osiągnąć maksymalny okres gamma szyfrowania, liczba cyfr mrejestru przesuwnego jest wybierana tak, aby była równa jednej z liczb pierwszych Mersenne'a (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), a połączenia wewnętrzne rejestru muszą być wybrane zgodnie z z nieredukowalnymi prymitywnymi wielomianami 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 wygenerowane sekwencje mają dobre właściwości statystyczne. LFSR jest używany jako podstawowy element składowy wysoce bezpiecznych systemów.
Kaskada rejestrów to zestaw LFSR połączonych w taki sposób, że zachowanie jednego LFSR jest zależne od zachowania poprzedniego LFSR w kaskadzie. To „zależne” zachowanie jest zwykle konfigurowane do sterowania licznikiem przesunięcia następnego LFSR przez pierwszy LFSR.
Na przykład 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 w inny sposób. Duża liczba takich kombinacji zapewnia bardzo wysokie bezpieczeństwo.
Najsilniejsze kryptograficznie sekwencje są dostarczane przez generator kurczący się oparty na prostej interakcji między wynikami dwóch 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 ekranujące. Jego wadą jest to, że tempo generowania „klucza strumieniowego” nie będzie stałe, chyba że podejmiesz pewne środki ostrożności.
Metoda Fibonacciego z opóźnieniamiJeden z rozpowszechnionych generatorów Fibonacciego oparty jest na następującej iteracyjnej formule:
gdzie Y k - liczby rzeczywiste z zakresu
Figa. 2. Cykliczne szyfrowanie
Tryb pętli zwrotnej wyjścia DES może być używany do generowania liczb pseudolosowych, podobnie jak jest używany do szyfrowania strumieniowego. Dane wyjściowe każdego etapu szyfrowania to 64-bitowa wartość, z której tylko najbardziej znaczące bity j są zwracane do szyfrowania. 64-bitowe wyjścia stanowią ciąg liczb pseudolosowych o dobrych właściwościach statystycznych.
Generator liczb pseudolosowych ANSI X9.17 jest jednym z najsilniejszych kryptograficznie generatorów liczb pseudolosowych. Aplikacje korzystające z tej technologii 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 sterowany dwoma pseudolosowymi wejściami. Pierwsze wejście to 64-bitowa reprezentacja bieżącej daty i godziny ( DT i), które zmieniają się za każdym razem, gdy tworzysz numer. Drugie wejście to 64-bitowa wartość początkowa, która jest inicjalizowana na jakąś dowolną wartość i zmieniana podczas generowania sekwencji liczb pseudolosowych ( V i).
2. Klucze: Generator wykorzystuje trzy potrójne moduły DES z dwoma kluczami K 1, K 2. Wszystkie trzy używają tej samej pary 56-bitowych kluczy, które muszą być utrzymywane w tajemnicy i używane tylko do generowania liczby pseudolosowej.
| EDE |
| EDE |
| EDE |
| + |
| + |
| K 1, K 2 |
| DT i |
| V i |
| R i |
| V i + 1 |
3. Dane wyjściowe: dane wyjściowe składają się z 64-bitowej pseudolosowej liczby R i oraz 64-bitowej wartości, która zostanie użyta jako wartość początkowa podczas tworzenia następnej liczby ( V i +1) .
Figa. 3. Generator liczb pseudolosowych ANSI X9.17
W rejestrze przesuwnym z liniowym sprzężeniem zwrotnym rozróżnia się dwie części (moduły): sam rejestr przesuwny i obwody (lub podprogramy), które obliczają wartość wstawionego bitu. Rejestr składa się z komórek funkcjonalnych (lub bitów słowa maszynowego lub kilku słów), z których każda przechowuje aktualny stan jednego bitu. Liczba komórek nazywana jest długością rejestru. Bity (komórki) są zwykle numerowane liczbami, z których każda może przechowywać bit, a wyliczony bit jest wstawiany do komórki, a następny wygenerowany bit jest usuwany z komórki. Obliczenie wstawianego bitu jest zwykle wykonywane przed przesunięciem rejestru i dopiero po przesunięciu jest wartość wyliczanego bitu umieszczanego w komórce.
Okres rejestru przesuwnego to minimalna długość odebranej sekwencji przed rozpoczęciem jej powtarzania. Ponieważ rejestr komórek bitowych ma tylko różne stany niezerowe, to w zasadzie okres rejestru nie może przekroczyć tej liczby. Jeżeli okres rejestru jest równy tej liczbie, wówczas taki rejestr nazywany jest rejestrem maksymalnego okresu.
W przypadku RSLOS, funkcja sprzężenia zwrotnego jest liniową funkcją boolowską stanów wszystkich lub niektórych bitów rejestru. Na przykład suma modulo dwa lub jej odwrotność logiczna jest liniową funkcją boolowską (operacja XOR, oznaczana jak we wzorach) i jest najczęściej używana w takich rejestrach.
W tym przypadku te bity, które są zmiennymi funkcji sprzężenia zwrotnego, są zwykle wywoływane opukanie.
Rejestr jest kontrolowany w implementacjach sprzętowych przez zastosowanie impulsu przesuwającego (inaczej nazywanego zegar lub synchronizacja impulsu) do wszystkich komórek, w komórkach programu - przez wykonanie cyklu programu, który obejmuje obliczenie funkcji sprzężenia zwrotnego i przesunięcia bitów w słowie.
Na każdym kroku czasowym wykonywane są następujące operacje:
Rejestr przesunięcia liniowego sprzężenia zwrotnego
Zatem operacja logiczna XOR (wyłączne OR) jest przyjmowana jako funkcja sprzężenia zwrotnego, to znaczy:
Własności wielomianów pierwotnych
Nieruchomości
Właściwości sekwencji wydanej przez RSLOS są ściśle powiązane z właściwościami skojarzonego wielomianu. Jego niezerowe współczynniki są nazywane opukaniea także odpowiadające im komórki rejestru podające wartości argumentów funkcji sprzężenia zwrotnego.
Złożoność liniowa
Liniowa złożoność sekwencji binarnej jest jedną z najważniejszych cech działania RSLOS. Wprowadźmy następujący zapis:
DefinicjaLiniowa złożoność nieskończonej sekwencji binarnej nazywa się numerem, który jest zdefiniowany w następujący sposób:
Liniowa złożoność skończonej sekwencji binarnej nazywana jest liczbą równą długości najkrótszej RLOS, która generuje sekwencję, która ma jako pierwsze składowe.
Liniowe właściwości złożoności
Niech i będą sekwencjami binarnymi. Następnie:
Niezależność od korelacji
Aby uzyskać wysoką złożoność liniową, kryptolodzy próbują łączyć wyniki wielu sekwencji wyjściowych w sposób nieliniowy. W takim przypadku istnieje niebezpieczeństwo, że jedną lub kilka sekwencji wyjściowych (często nawet wyjść poszczególnych RFLOS) można połączyć wspólnym strumieniem kluczy i otworzyć za pomocą algebry liniowej. Nazywa się hakowanie w oparciu o taką lukę autopsja korelacyjna... Thomas Sigenthaler wykazał, że niezależność korelacji można dokładnie określić i że istnieje kompromis między niezależnością korelacji a złożonością liniową.
Główną ideą tego hacka jest znalezienie korelacji między mocą wyjściową generatora a mocą jednej z jego części składowych. Następnie, obserwując sekwencję wyjściową, możesz uzyskać informacje o tym pinie pośrednim. Korzystając z tych informacji i innych korelacji, możliwe jest zbieranie danych o innych pośrednich wnioskach, dopóki generator nie zostanie zhakowany.
Ataki korelacyjne lub wariacje, takie jak ataki szybkiej korelacji, zostały z powodzeniem zastosowane w wielu generatorach strumienia kluczy opartych na rejestrach przesuwnych z liniowym sprzężeniem zwrotnym, takich jak ataki szybkiej korelacji, które wymagają kompromisu między złożonością obliczeniową a wydajnością.
Przykład
W przypadku RSLOS ze skojarzonym wielomianem wygenerowana sekwencja ma postać. Załóżmy, że sekwencja jest zapisywana w rejestrze przed rozpoczęciem procesu, wówczas okres generowanego strumienia bitów będzie wynosił 7 z następującą sekwencją:
| Numer kroku | stan: schorzenie | Wygenerowany bit |
| 0 | - | |
| 1 | 1 | |
| 2 | 1 | |
| 3 | 0 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 | |
| 7 | 0 |
Ponieważ stan wewnętrzny w siódmym kroku powrócił do swojego pierwotnego stanu, to począwszy od następnego kroku nastąpi powtórzenie. Innymi słowy, okres ciągu okazał się równy 7, co wynikało z prymitywności wielomianu.
Algorytmy generowania pierwotnych wielomianów
Gotowe stoły
Obliczenie prymitywizmu wielomianu jest dość trudnym problemem matematycznym. Dlatego istnieją gotowe tabele, które pokazują numery sekwencji zaczepów, które zapewniają maksymalny okres generatora. Na przykład istnieje sekwencja dla 32-bitowego rejestru przesuwnego. Oznacza to, że aby wygenerować nowy bit, musisz XOR 31., 30., 29., 27., 25. i zerowym. Kod takiego RSLOS w C jest następujący:
Int LFSR (void) (static unsigned long S \u003d 1; S \u003d ((((S \u003e\u003e 31) ^ (S \u003e\u003e 30) ^ (S \u003e\u003e 29) ^ (S \u003e\u003e 27) ^ (S \u003e\u003e 25) ^ S) i 1)<< 31 ) | (S>\u003e 1); powrót S & 1; )
Implementacje programowe generatorów RSLOS są raczej powolne i działają szybciej, jeśli są napisane w asemblerze, a nie w C. Jednym z rozwiązań jest użycie 16 RSLOS równolegle (lub 32, w zależności od długości słowa w architekturze danego komputera). Ten schemat używa tablicy słów, których rozmiar jest równy długości RSLOS, a każdy bit słowa w tablicy odnosi się do własnego RSLOS. Pod warunkiem, że używane są te same numery sekwencji palców, może to zapewnić znaczny wzrost wydajności. [potrzebny przykład kodu] (Zobacz: bitslice).
Konfiguracja Galois
Konfiguracja Galois rejestru przesuwnego z liniowym sprzężeniem zwrotnym
Można również zmodyfikować pętlę sprzężenia zwrotnego. W takim przypadku generator nie będzie miał większej siły kryptograficznej, ale łatwiej będzie go zaimplementować w oprogramowaniu. Zamiast używać bitów sekwencji palca do generowania nowego bitu najbardziej po lewej stronie, każdy bit sekwencji F jest poddawany XOR i zastępowany wyjściem generatora, a wynik generatora staje się nowym bitem najbardziej po lewej stronie. W języku C wygląda to tak:
Int LFSR (void) (static unsigned long Q \u003d 1; Q \u003d (Q \u003e\u003e 1) ^ (Q & 1? 0x80000057: 0); return Q & 1;)
Efektem jest to, że wszystkie operacje XOR są wykonywane w jednej operacji.
- można udowodnić, że konfiguracja Fibonacciego podana w pierwszej i podana tutaj konfiguracja Galois dają te same sekwencje (długość 2 32-1), ale poza fazą jedna od drugiej
- pętla ustalonej liczby wywołań LFSR w konfiguracji Galois jest około dwa razy szybsza niż w konfiguracji Fibonacciego (kompilator MS VS 2010 na Intel Core i5)
- zauważ, że w konfiguracji Galois kolejność bitów w słowie sprzężenia zwrotnego jest odwrócona od konfiguracji Fibonacciego
Przykłady generatorów
Generatory zatrzymujące się
Generator naprzemienny typu Stop-and-Go
Ten generator wykorzystuje wyjście jednego RSLOS do sterowania częstotliwością zegara drugiego RSLOS. Wyjście zegarowe RSLOS-2 jest sterowane przez wyjście RSLOS-1, tak że RSLOS-2 może zmienić swój stan w czasie t tylko wtedy, gdy wyjście RSDOS-1 w czasie t-1 było równe jeden. Ale ten schemat nie oparł się rozgrywce korelacji.
Dlatego zaproponowano ulepszony generator oparty na tym samym pomyśle. Nazywa się to generatorem przemiennym typu stop-and-go. Używa trzech RFLO o różnych długościach. RSLOS-2 jest taktowany, gdy wyjście RSLOS-1 jest równe jeden, a RSLOS-3, gdy wyjście RSLOS-1 jest równe zero. Wyjście generatora to suma modulo 2 RSLOS-2 i RSLOS-3. Ten generator ma długi okres i dużą złożoność liniową. Jego autorzy pokazali również sposób otwierania korelacji RSLOS-1, ale nie osłabia to znacznie generatora.
Kaskada Gollmanna
Kaskada Gollmanna
Stopień Gollmanna to wzmocniona wersja generatora stop-and-go. Składa się z sekwencji RSLOS, których taktowanie jest kontrolowane przez poprzedni RSLOS. Jeśli wyjście RSLOS-1 w czasie t wynosi 1, to RSLOS-2 jest taktowany. Jeśli wyjście RSLOS-2 w czasie t wynosi 1, to RSLOS-3 jest taktowany i tak dalej. Ostatnie wyjście RFLOS to wyjście generatora. Jeżeli długość wszystkich RFLOS jest taka sama i jest równa n, to liniowa złożoność układu k LLS jest równa.
Pomysł ten jest prosty i można go wykorzystać do generowania sekwencji o dużych okresach, dużej złożoności liniowej i dobrych właściwościach statystycznych. Niestety są jednak wrażliwe na atak zwany „lock-in”. Dla większej trwałości zaleca się użycie k co najmniej 15. Ponadto lepiej jest stosować więcej krótkich RFLOS niż mniej długich RFLO.
Generator progów
Generator progów
Ten generator próbuje obejść problemy związane z bezpieczeństwem poprzednich generatorów za pomocą zmiennej liczby rejestrów przesuwnych. W teorii przy zastosowaniu większej liczby rejestrów przesuwnych zwiększa się złożoność szyfru, co zostało zrobione w tym generatorze.
Generator ten składa się z dużej liczby rejestrów przesuwnych, których dane wyjściowe przechodzą do funkcji majoryzacji. Jeśli liczba jedynek na wyjściach rejestrów jest większa niż połowa, generator generuje jeden. Jeśli liczba zer na wyjściach jest większa niż połowa, generator generuje zero. Aby porównanie liczby zer i jedynek było możliwe, liczba rejestrów przesuwnych musi być nieparzysta. Długości wszystkich rejestrów muszą być stosunkowo proste, a wielomiany sprzężenia zwrotnego muszą być prymitywne, aby okres generowanej sekwencji był maksymalny.
W przypadku trzech rejestrów przesuwnych generator można przedstawić jako:
Ten generator jest podobny do generatora Geffa, z tą różnicą, że generator progów ma bardziej liniową złożoność. Jego złożoność liniowa to:
gdzie ,, są długościami pierwszego, drugiego i trzeciego rejestru przesuwnego.
Jego wadą jest to, że każdy bit wyjściowy dostarcza pewnych informacji o stanie rejestru przesuwnego. Dokładniej 0,189 bitu. Dlatego ten generator może nie oprzeć się atakowi korelacji.
Inne rodzaje
Samo-przerzedzenie
Generatory samozachowawcze to te, które kontrolują swoją własną częstotliwość. Zaproponowano dwa typy takich generatorów. Pierwsza składa się z rejestru przesuwnego z liniowym sprzężeniem zwrotnym i niektórych obwodów, które synchronizują ten rejestr w zależności od wartości wyjściowych rejestru przesuwnego. Jeśli wyjście RSLOS jest równe jeden, to rejestr jest taktowany d razy. Jeśli wyjście ma wartość zero, to rejestr jest taktowany k razy. Drugi ma prawie taką samą konstrukcję, ale nieco zmodyfikowaną: w obwodzie zegara wejście, jako sprawdzanie dla 0 lub 1, nie odbiera samego sygnału wyjściowego, ale XOR pewnych bitów rejestru przesuwnego z liniowym sprzężeniem zwrotnym. Niestety ten rodzaj generatora nie jest bezpieczny.
Generator wielobiegowy z produktem wewnętrznym
Ten generator wykorzystuje dwa rejestry przesuwne z liniowym sprzężeniem zwrotnym o różnych częstotliwościach zegara: RSLOS-1 i RSLOS-2. Częstotliwość taktowania RSLOS-2 jest d razy większa niż RSLOS-1. Poszczególne bity tych rejestrów są połączone operatorem AND. Następnie dane wyjściowe operacji AND są XORowane. Sekwencja wyjściowa jest usuwana z tego bloku XOR. Ponownie, ten generator nie jest bezbłędny (nie wytrzymał otwarcia liniowej spójności. Jeśli jest długością RSLOS-1, jest długością RSLOS-2, ad jest współczynnikiem częstotliwości taktowania, to stan wewnętrzny generatora można uzyskać z wyjściowej sekwencji długości), ale ma wysoką złożoność liniową i doskonałą wydajność statystyczną.
Najprostszym rodzajem funkcji sprzężenia zwrotnego jest funkcja liniowa, na przykład suma modulo 2 zawartości pewnych bitów. Taki rejestr nazywany jest liniowym rejestrem zwrotnym (LFSR). Ogólnie liniowa funkcja sprzężenia zwrotnego jest określona wzorem. Tutaj c k\u003d 1 jeśli kcyfra jest używana w funkcji sprzężenia zwrotnego, a c k\u003d 0 w przeciwnym razie. Symbol Å oznacza dodatek modulo 2 (wyłączny OR).
Na przykład rozważmy LFSR z funkcją sprzężenia zwrotnego (patrz rysunek).
Jeżeli stan początkowy rejestru to 1111, to w kolejnych cyklach zegara przyjmie następującą serię stanów: 1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 1000, 1100, 1110, 1111, ...
Sekwencja wyjściowa jest tworzona z najmniej znaczącego (najbardziej po prawej) bitu rejestru. Będzie to wyglądać następująco: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Można zauważyć, że generowana sekwencja bitów jest całkowicie zdeterminowana przez stan początkowy rejestru i funkcję sprzężenia zwrotnego. Ponieważ liczba wszystkich możliwych stanów rejestrów jest skończona (jest równa 2 L), to wcześniej czy później sekwencja klawiszy zacznie się powtarzać. Maksymalna długość niepowtarzalnej części sekwencji klawiszy nazywana jest jej okresem. T... Okres zależy od funkcji sprzężenia zwrotnego. Maksymalny możliwy okres to T max \u003d 2 L-1 (rejestr akceptuje wszystkie możliwe stany oprócz 0000 ... 0). Wywoływana jest sekwencja wyjściowa LFSR z maksymalnym okresem Sekwencja M..
Aby dowiedzieć się, w jakich warunkach LFSR będzie miał maksymalny okres, funkcje sprzężenia zwrotnego pasują do charakterystycznego wielomianu. Tak więc rejestr podany powyżej jako przykład odpowiada wielomianowi. Analiza teoretyczna pokazuje, że LFSR będzie miał maksymalny okres wtedy i tylko wtedy, gdy wielomian P.(x) jest prymitywny... Poniżej znajduje się kilka prymitywnych wielomianów zalecanych do praktycznego zastosowania. Tabela pokazuje stopnie zmiennej xw notacji wielomianu. Na przykład rekord (31, 3) odpowiada wielomianowi.
| № | P.(x) | № | P.(x) | № | P.(x) |
| (39, 16, 23, 35) | (38, 5, 6, 27) | (32, 2, 7, 16) | |||
| (30, 6, 4, 1) | (31, 6) | (31, 7) | |||
| (31, 13) | (31, 25, 23, 8) | (33, 13) | |||
| (35, 2) | (47, 5) | (48, 9, 7, 4) | |||
| (47, 11, 24, 32) | (46, 18, 31, 40) | (53, 6, 2, 1) | |||
| (55, 24) | (57, 7) | (58, 19) | |||
| (59, 7, 4, 2) | (41, 27, 31, 32) | (61, 5, 2, 1) | |||
| (42, 30, 31, 34) | (51, 15, 24, 46) | (50, 17, 31, 34) |
LFSR zostały pierwotnie zaprojektowane do implementacji sprzętowej jako zestaw obwodów cyfrowych. Implementacje oprogramowania LFSR zwykle przewyższają implementacje sprzętowe. Aby zwiększyć prędkość, warto zapisać stan rejestru jako liczbę całkowitą L-numer bitu, którego poszczególne bity odpowiadają cyfrom binarnym rejestru. Następnie operacje bitowe (przesunięcie, maskowanie itp.) Są używane w celu uzyskania dostępu do poszczególnych bitów.
Rejestr przesuwny opinii ( FSR ) składa się z dwóch części: rejestr przesuwny i funkcje sprzężenia zwrotnego .
Rejestr przesuwny (błąd: nie znaleziono źródła odniesienia) to sekwencja bitów. Kiedy ma być pobrany bit, wszystkie bity rejestru przesuwnego są przesuwane w prawo o 1 pozycję. Nowy skrajnie lewy bit jest wartością funkcji sprzężenia zwrotnego z pozostałych bitów rejestru. Kropka rejestr przesuwny to długość otrzymanej sekwencji przed rozpoczęciem jej powtarzania.
Najprostszą formą rejestru przesuwnego sprzężenia zwrotnego jest liniowy rejestr przesuwny sprzężenia zwrotnego (LFSR
–
Lewo
Sprzężenie zwrotne
Zmiana
Zarejestrować)
(Błąd: nie znaleziono źródła odniesienia). Sprzężenie zwrotne to po prostu XOR niektórych bitów p 
register, lista tych bitów jest nazywana sekwencja przekierowania.
n-bit LFSR może znajdować się w jednym z 2 n -1 stany wewnętrzne. Oznacza to, że teoretycznie taki rejestr może generować pseudolosową sekwencję z okresem 2 n -1 bity. Liczba stanów wewnętrznych i okres są równe, ponieważ wypełnienie rejestru zerami spowoduje powstanie nieskończonej sekwencji zer, co jest absolutnie bezużyteczne. Tylko dla niektórych sekwencji zaczepów LFSR przechodzi przez wszystkie 2 n -1 stany wewnętrzne. Takie LFSR są nazywane LFSR z maksymalnym okresem.
Aby określony LFSR miał maksymalny okres, wielomian utworzony z sekwencji wyprowadzenia i stałej 1 musi być prymitywnym modulo 2 .
Obliczenie prymitywizmu wielomianu jest dość trudnym problemem matematycznym. Dlatego istnieją gotowe tabele, które pokazują 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ć bity trzydziesty drugi, siódmy, piąty, trzeci, drugi i pierwszy za pomocą funkcji XOR.
Kod takiego LFSR w C ++ wyglądałby tak:
// Dowolna wartość inna niż zero
ShiftRegister \u003d ((((ShiftRegister \u003e\u003e 31)
^ (ShiftRegister \u003e\u003e 6)
^ (ShiftRegister \u003e\u003e 4)
^ (ShiftRegister \u003e\u003e 2)
^ (ShiftRegister \u003e\u003e 1)
^ ShiftRegister)
& 0x00000001)<<31)
| (ShiftRegister \u003e\u003e 1);
powrót ShiftRegister & 0x00000001;
Implementacje oprogramowania LFSR są dość powolne i działają szybciej, jeśli są napisane w asemblerze, a nie w C. Jednym z rozwiązań jest użycie 16 LFSR równolegle (lub 32 w zależności od długości słowa w architekturze danego komputera). W takim 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. Pod warunkiem, że używane są te same numery sekwencji palców, może to zapewnić znaczny wzrost wydajności.
Z 
chemię sprzężenia zwrotnego można również zmodyfikować. W takim przypadku generator nie będzie miał większej siły kryptograficznej, ale łatwiej będzie go zaimplementować w oprogramowaniu. Zamiast używać bitów sekwencji palca do generowania nowego bitu znajdującego się najbardziej po lewej stronie, XOR każdy bit sekwencji F z wyjściem generatora i zastąp go wynikiem tej czynności, a wynik generatora stanie się nowym bitem najbardziej po lewej stronie (błąd: nie znaleziono źródła odniesienia).
Ta modyfikacja nosi nazwę konfiguracja Galois... W języku C wygląda to tak:
statyczny długi bez znaku ShiftRegister \u003d 1;
void seed_LFSR (unsigned long seed)
ShiftRegister \u003d ziarno;
int Galua_LFSR (nieważne)
if (ShiftRegister & 0x00000001) (
ShiftRegister \u003d (ShiftRegister ^ maska \u200b\u200b\u003e\u003e 1) | 0x8000000;
ShiftRegister \u003e\u003e \u003d 1;
Efektem jest to, że wszystkie operacje 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 właściwości nielosowe. Kolejne bity są liniowe, przez co są bezużyteczne do szyfrowania. Do długości LFSR nstan wewnętrzny reprezentuje poprzedni nbity wyjściowe generatora. Nawet jeśli schemat informacji zwrotnej jest utrzymywany w tajemnicy, można go określić za pomocą 2 nbity wyjściowe generatora za pomocą specjalnych algorytmów. Ponadto duże liczby losowe generowane przy użyciu ciągłych bitów tej sekwencji są silnie skorelowane i dla niektórych typów zastosowań 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 gałęzi. Kluczem jest początkowy stan rejestrów. Za każdym razem, gdy potrzebny jest nowy bit, przesuwane są wszystkie rejestry. Ta operacja nazywa się wyczucie czasu... Bit wyjściowy jest funkcją, korzystnie nieliniową, niektórych bitów LFSR. Ta funkcja nazywa się łączeniei generator jako całość łączący generator... Wiele z tych generatorów jest nadal bezpiecznych.
Rejestr przesuwny informacji zwrotnych składa się z dwóch części: rejestru przesuwnego i funkcje sprzężenia zwrotnego.
Rys 19. Rejestr przesuwny ze sprzężeniem zwrotnym.
Ogólnie rejestr przesuwny to sekwencja niektórych elementów pierścienia lub pola. Najczęściej używane kawałek rejestry przesuwne. Długość takiego rejestru jest wyrażona liczbą bitów. Za każdym razem, gdy pobierany jest bit, wszystkie bity rejestru są przesuwane w prawo o jedną pozycję. Nowy najbardziej znaczący bit jest obliczany jako funkcja wszystkich innych bitów rejestru. Wyjście jest zwykle najmniej znaczącym bitem. Okres rejestru przesuwnego to długość sekwencji wyjściowej, zanim zacznie się ona powtarzać.
Najprostszym typem rejestrów przesuwnych jest rejestr przesuwny ze sprzężeniem liniowym (RSLOS lub LRS). Sprzężenie zwrotne to prosta operacja XOR na niektórych bitach rejestrów. Lista tych bitów jest zdefiniowana charakterystyczny wielomian i zadzwonił kolejność gięć... To się czasem nazywa konfiguracja Fibonacciego.
Ryc.20. Konfiguracja RLOS Fibonacciego.
W implementacji oprogramowania RSLOS jest stosowany zmodyfikowany schemat: w celu wygenerowania nowego znaczącego bitu zamiast używania bitów sekwencji zaczepów wykonywana jest operacja XOR z wyjściem generatora na każdym z nich, zastępując stary bit sekwencji zaczepów. Ta modyfikacja jest czasami nazywana konfiguracja Galois.
Ryc.21. Konfiguracja RSLOS Galois.
n-bitowy RSLOS może być jednym z 2 n - 1 stany wewnętrzne. Oznacza to, że teoretycznie taki rejestr może generować pseudolosową sekwencję z okresem 2 n - 1 bity (wypełnianie zerami jest całkowicie bezużyteczne). Zdaj wszystkie 2 n - 1 stany wewnętrzne możliwe tylko przy określonych sekwencjach zaczepów. Takie rejestry nazywane są RSLOS z maksymalnym okresem. Aby zapewnić maksymalny okres RSLOS, konieczne jest, aby jego charakterystyczny wielomian był prymitywny modulo 2. Stopień wielomianu to długość rejestru przesuwnego. Prymitywny wielomian stopnia n - to jest takie nieskracalny wielomian, który jest dzielnikiem, ale nie jest dzielnikiem x d +1 dla wszystkich rektóre są dzielnikami liczby 2 n - 1. (Omawiając wielomiany, pojęcie liczba pierwsza zastępuje się terminem nieredukowalny wielomian). Charakterystyczny wielomian podany na rysunkach RLOS:
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ż do ich powtórzenia. Najczęściej używane są wielomiany rozrzedzone, tj. które mają tylko pewne współczynniki. najbardziej popularne są trójomiany.
Ważnym parametrem generatora opartego na RSLOS jest liniowa złożoność... Jest definiowana jako długość n najkrótszy RLOS, który może symulować wyjście generatora. Liniowa złożoność jest ważna, ponieważ jest prosta algorytm Berlenkampa-Masseya możesz odtworzyć taki RSLOS, zaznaczając tylko 2 n bity gamma. Przy definicji pożądanego RSLOS, szyfr strumieniowy jest faktycznie zepsuty.
