Linjär feedback skiftregister. Återkopplingsskiftregister

I ett skiftregister med en linjär respons det finns två delar (moduler): själva skiftregistret och kretsen (eller subrutinen) som beräknar värdet på den infogade biten. Registret består av funktionella celler (eller bitar av ett maskinord eller flera ord), som var och en lagrar Nuvarande tillstånd en bit. Antalet celler kallas registrets längd. Bitar (celler) numreras vanligtvis med siffror, som var och en kan lagra en bit, och den beräknade biten skjuts in i cellen och nästa genererade bit dras ut från cellen. Beräkningen av den infogade biten utförs vanligtvis före skiftningen av registret, och först efter skiftet placeras värdet på den beräknade biten i cellen.

Perioden för skiftregistret är den minsta längden av den resulterande sekvensen innan den börjar upprepas. Eftersom registret av bitceller endast har olika icke-noll-tillstånd, kan i princip registrets period inte överstiga detta antal. Om registrets period är lika med detta antal, kallas ett sådant register registret över den maximala perioden.

För LFSR är återkopplingsfunktionen linjär boolesk funktion från tillstånden för alla eller vissa delar av registret. Till exempel är summan modulo två eller dess logiska invers en linjär boolesk funktion (XOR-operation, betecknad som i formler) och används oftast i sådana register.

Samtidigt, de där bitarna som är funktionsvariabler feedback, vanligtvis kallad böjer sig.

Registerkontroll i hårdvaruimplementationer utförs genom att applicera en skiftpuls (kallas annars klocka eller synkpuls) till alla celler, i mjukvara - genom att exekvera en programcykel, inklusive beräkning av återkopplingsfunktionen och bitförskjutning i ordet.

Under varje klocktick utförs följande operationer:

Linjärt återkopplingsskiftregister

Som en återkopplingsfunktion tar vi alltså logisk operation XOR (exklusiv OR), det vill säga:

Egenskaper för primitiva polynom

Egenskaper

Egenskaperna för sekvensen som produceras av LFSR är nära besläktade med egenskaperna hos det associerade polynomet. Dess icke-nollkoefficienter kallas böjer sig, såväl som motsvarande celler i registret, som tillhandahåller värdena för argumenten för återkopplingsfunktionen.

Linjär komplexitet

Den linjära komplexiteten hos en binär sekvens är en av de mest viktiga egenskaper RSLOS fungerar. Låt oss presentera följande notation:

Definition

Den linjära komplexiteten hos en oändlig binär sekvens kallas ett tal, vilket definieras enligt följande:

Den linjära komplexiteten för en finit binär sekvens kallas talet , som är lika med längden på den kortaste LFSR, som genererar en sekvens som har som första termer .

Linjär komplexitetsegenskaper

Låta och vara binära sekvenser. Sedan:

Korrelation Oberoende

För att få hög linjär komplexitet försöker kryptografer att icke-linjärt kombinera resultaten av flera utdatasekvenser. I det här fallet är faran att en eller flera utgångssekvenser (ofta till och med utgångarna från individuella LFSR) kan kopplas samman med en gemensam nyckelström och avslöjas med linjär algebra. Hacking baserat på en sådan sårbarhet kallas korrelationsobduktion. Thomas Siegenthaler har visat att korrelationsoberoende kan definieras exakt, och att det finns en avvägning mellan korrelationsoberoende och linjär komplexitet.

Huvudidén med ett sådant hack är att hitta en viss korrelation mellan utsignalen från en generator och utsignalen från en av dess beståndsdelar. Sedan, genom att observera utmatningssekvensen, kan information om denna mellanutgång erhållas. Med hjälp av denna information och andra korrelationer är det möjligt att samla in data på andra mellanutgångar tills generatorn hackas.

Korrelationsattacker eller variationer såsom snabba korrelationsattacker har framgångsrikt använts mot många linjära åtnyckelströmsgeneratorer, som involverar en avvägning mellan beräkningskomplexitet och effektivitet.

Exempel

För LFSR med ett associerat polynom har den genererade sekvensen formen . Antag att sekvensen skrivs i registret före processens start, då kommer perioden för den genererade bitströmmen att vara lika med 7 med följande sekvens:

Stegnummer	stat	Bit genererad
0		-
1		1
2		1
3		0
4		1
5		1
6		1
7		0

Eftersom det interna tillståndet i det sjunde steget återgick till sitt ursprungliga tillstånd, kommer det, från och med nästa steg, att bli en upprepning. Med andra ord visade sig perioden för sekvensen vara lika med 7, vilket hände på grund av polynomets primitivitet.

Algoritmer för att generera primitiva polynom

Färdiga bord

Att beräkna primitiviteten hos ett polynom är ganska komplicerat matematiskt problem. Därför finns det färdiga tabeller som listar antalet uttagssekvenser som ger den maximala perioden för generatorn. Till exempel, för ett 32-bitars skiftregister finns det en sekvens . Detta betyder att för att generera en ny bit är det nödvändigt att summera de 31:a, 30:e, 29:e, 27:e, 25:e och 0:e bitarna med hjälp av XOR-funktionen. Koden för sådan LFSR på C-språket är följande:

Int LFSR (void ) ( statisk osignerad lång S = 1 ; S = ((((S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); returnera S & 1 ; )

Mjukvaruimplementationer av RSLOS-generatorer är ganska långsamma och fungerar snabbare om de är skrivna i assembler snarare än i C. En lösning är att använda 16 RLLS parallellt (eller 32, beroende på ordlängden i en viss dators arkitektur). I ett sådant schema används en array av ord, vars storlek är lika med längden på LFSR, och varje bit i arrayordet hänvisar till dess LFSR. Förutsatt att samma tappsekvensnummer används kan detta ge en märkbar prestandavinst. [behöver exempelkod] (Se: bitslice).

Galois-konfiguration

Galois-konfiguration av ett linjärt återkopplingsskiftregister

Återkopplingsschemat kan också modifieras. I det här fallet kommer generatorn inte att ha större kryptografisk styrka, men det blir lättare att implementera det programmatiskt. Istället för att använda bitarna i tappsekvensen för att generera en ny bit längst till vänster, XELLER varje bit i tappsekvensen med utgången från generatorn och ersätt den med resultatet av denna åtgärd, då blir resultatet av generatorn den nya biten längst till vänster . I C-språket ser det ut så här:

Int LFSR (void ) ( statisk unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Fördelen är att alla XOR utförs i en operation.

det kan bevisas att Fibonacci-konfigurationen som ges först och Galois-konfigurationen som ges här ger samma sekvenser (med längden 2 32 −1), men skiftade i fas från varandra
en slinga av ett fast antal anrop till LFSR-funktionen i Galois-konfigurationen är ungefär dubbelt så snabb som i Fibonacci-konfigurationen (MS VS 2010 kompilator på Intel Core i5)
Observera att i Galois-konfigurationen är bitarnas ordningsföljd i återkopplingsordet omvänd jämfört med Fibonacci-konfigurationen

Exempel på generatorer

stoppgeneratorer

Stop-and-Go alternerande generator

Denna oscillator använder utsignalen från en LFSR för att styra klockfrekvensen för en annan LFSR. Klockutgången från RSLOS-2 styrs av utgången från RSLOS-1, så att RSLOS-2 kan ändra sitt tillstånd vid tidpunkten t endast om utsignalen från RSLOS-1 vid tidpunkten t-1 var lika med ett. Men detta schema motstod inte korrelationsöppningen.

Därför har en förbättrad generator baserad på samma idé föreslagits. Det kallas den stopp-och-gå interfolierade generatorn. Den använder tre LFSR:er av olika längd. LFSR-2 klockas när utsignalen från LFSR-1 är lika med ett och LFSR-3 när utsignalen från LFSR-1 är lika med noll. Generatorns utgång är modulo 2-summan av RSLOS-2 och RSLOS-3. Denna generator har en stor period och en stor linjär komplexitet. Dess författare visade också en metod för korrelationsöppning av RLOS-1, men detta försvagar inte generatorn avsevärt.

Gollmann Cascade

Gollmann Cascade är en förbättrad version av stop-go-generatorn. Den består av en sekvens av LFSR, vars timing styrs av föregående LFSR. Om utsignalen från LFSR-1 vid tidpunkten t är 1, klockas LFSR-2. Om utsignalen från LFSR-2 vid tidpunkten t är 1, så klockas LFSR-3, och så vidare. Utsignalen från den sista LFSR är utsignalen från generatorn. Om längden på alla LFSRs är samma och lika med n, då är den linjära komplexiteten för systemet av k LFSRs .

Denna idé är enkel och kan användas för att generera sekvenser med stora perioder, stora linjära komplexiteter och goda statistiska egenskaper. Men tyvärr är de mottagliga för en öppning som kallas "låsning" (låsning). För större stabilitet rekommenderas att använda k minst 15. Dessutom är det bättre att använda mer kort LFSR än mindre lång LFSR.

tröskelgenerator

Denna generator försöker kringgå säkerhetsproblemen hos tidigare generatorer genom att använda ett variabelt antal skiftregister. I teorin, när man använder ett större antal skiftregister, ökar chifferens komplexitet, vilket gjordes i denna generator.

Denna generator består av ett stort antal skiftregister, vars utgångar matas till majoriseringsfunktionen. Om antalet enheter vid registrens utgång är mer än hälften, producerar generatorn en enhet. Om antalet nollor på utgångarna är mer än hälften, producerar generatorn en nolla. För att jämförelsen av antalet nollor och ettor ska vara möjlig måste antalet skiftregister vara udda. Längden på alla register måste vara relativt prime, och återkopplingspolynomen måste vara primitiva så att perioden för den genererade sekvensen är maximal.

För fallet med tre skiftregister kan generatorn representeras som:

Denna generator liknar Geff-generatorn, förutom att tröskelgeneratorn har mer linjär komplexitet. Dess linjära komplexitet är:

där , , är längden på de första, andra och tredje skiftregistren.

Dess nackdel är att varje utgångsbit ger viss information om skiftregistrets tillstånd. För att vara exakt 0,189 bitar. Därför kanske denna generator inte motstår korrelationsöppningen.

Andra typer

Självförtunning

Självsänkande generatorer kallas generatorer som styr sin egen frekvens. Två typer av sådana generatorer har föreslagits. Den första består av ett omvänt skiftregister. linjär anslutning och någon krets som klockar detta register, beroende på vad skiftregistrets utvärden är. Om LFSR-utgången är lika med ett, klockas registret d gånger. Om utgången är noll, klockas registret k gånger. Den andra har nästan samma design, men något modifierad: i klockkretsen, som en kontroll för 0 eller 1, tas inte själva utsignalen, utan XOR för vissa bitar av skiftregistret med linjär återkoppling, emot vid ingången . Tyvärr är denna typ av generator inte säker.

Multirate oscillator med inre produkt

Denna generator använder två skiftregister med linjär återkoppling med olika klockfrekvenser: LFSR-1 och LFSR-2. Klockfrekvensen för RLOS-2 är d gånger högre än den för RLLS-1. De individuella bitarna i dessa register kombineras med en OCH-operation. Utgångarna från OCH-operationen XORed. Utmatningssekvensen tas från detta XOR-block. Återigen, denna generator är inte perfekt (den överlevde inte öppningen av linjär konsistens. Om - längden på LFSR-1, - längden på LFSR-2 och d är förhållandet mellan klockfrekvenser, då är det interna tillståndet för generator kan erhållas från utdatasekvensen av längd ), men den har hög linjär komplexitet och utmärkt statistisk prestanda.

För att bygga strömchiffer används mycket ofta sekvenser på skiftregister. Ett återkopplingsskiftregister består av två delar: ett skiftregister och en återkopplingsfunktion, som visas i fig. 87. Själva skiftregistret är en sekvens av bitar, vars antal bestämmer längden på registret. Så, om n bitar är involverade i registret, så säger de att n-bitars skiftregistret. Varje gång en bit hämtas skiftas alla bitar i skiftregistret åt höger med en position, vanligtvis mot de minst signifikanta bitarna. Perioden för skiftregistret är längden på den resulterande sekvensen innan den börjar upprepas.

Ris. 87.

Vilken matematisk funktion som helst som utför en operation på bitar kan fungera som återkoppling. Den enklaste typen av återkopplingsskiftregister är det linjära återkopplingsskiftregistret (LFSR). I LFSR är återkoppling helt enkelt en modulo 2 additionsoperation (XOR) på vissa bitar i ett register; listan över dessa bitar kallas en sekvens av tappningar, eller pickup-punkter, som visas i fig. 88. Ibland kallas ett sådant mönster för en Fibonacci-konfiguration. På grund av återkopplingssekvensens enkelhet kan en ganska utvecklad matematisk teori användas för att analysera LFSR. I vilket fall som helst utvärderas kvaliteten på den producerade SRP genom en speciell uppsättning tester.

Ris. 88.

LFSR skrivs i form av polynom. I detta fall indikerar graden av det första elementet i polynomet antalet bitar i skiftregistret, och exponentialexponenterna för de återstående medlemmarna av polynomet indikerar vilka upptagningspunkter som kommer att användas. Så, till exempel, att skriva x 4 + x + 1 innebär att ett register med fyra element kommer att användas, för vilka bitarna bi och b 0 kommer att delta i bildandet av återkoppling (fig. 89).

Ris. 89,4

Tänk på driften av registret som visas i fig. 89. Initiera den, till exempel, med värdet 0101 (den initiala initieringen kan utföras av vilken bitsekvens som helst, förutom en sekvens av endast nollor, eftersom återkopplingen i detta fall alltid kommer att bilda ett värde på noll och registret kommer att inte producerar den förväntade PSP). Så i registret sker en förskjutning åt höger med en position. Den minst signifikanta biten, lika med 1, tvingas ut ur registret och bildar den första biten i PRS. De bitar som var i positionerna b och b 0 före skiftet läggs till modulo 2 och bildar en ny

hög bit av registret. Ett illustrativt exempel på funktionen av den övervägda LFSR visas i fig. 90.

Ris. 90.

Som framgår av fig. 90 kommer registerfyllningen att gå igenom en vikt av 15 av 16 möjliga tillstånd (vi har tidigare fastställt att det sextonde tillståndet, när LFSR är 0000, inte kan beaktas). Därefter kommer fyllningen av registret återigen att vara lika med det initiala värdet på 0101, och genereringen av bitsekvensen kommer att börja upprepas. Utmatningssekvensen från registret kommer att vara strängen med minst signifikanta bitar (upp till den horisontella linjen i fig. 90): 101011110001001. Storleken på bitsekvensen innan den upprepas kallas perioden. För att säkerställa den maximala perioden för en viss LFSR (dvs. för att registret ska gå igenom alla möjliga interna tillstånd), måste polynomet som bestämmer registrets funktion vara primitiv modulo 2. Som med stora primtal, finns det inget sätt att generera sådana polynom. Man kan bara ta ett polynom och kontrollera om det är irreducible modulo 2 eller inte. I det allmänna fallet är ett primitivt polynom av grad n ett sådant irreducerbart polynom som är en divisor av x 2 "+1, men är inte en divisor av x d +1 för alla d som är divisorer av 2 "-1. En tabell av vissa polynom ges i B. Schneiers arbete, vilka är irreducible modulo 2.

Genom att sammanfatta kunskapen som erhållits som ett resultat av att betrakta exemplet på driften av LFSR (fig. 90), kan vi säga att n-bitars LFSR kan vara i ett av de 2”-1 interna tillstånden. Teoretiskt kan ett sådant register generera en pseudo-slumpmässig sekvens med en period av 2n-1 bitar. Sådana register kallas LFSR-register med en maximal period. Den resulterande utsignalen kallas en t-sekvens.

Definition

Skiftregistret för linjär återkoppling består av två delar: skift register och återkopplingsfunktioner. Registret består av bitar, dess längd är antalet av dessa bitar. När en bit ska hämtas förskjuts alla bitar i registret en position åt höger. Den nya biten längst till vänster bestäms av funktionen hos de återstående bitarna. Utdata från registret är en, vanligtvis den minst signifikanta biten. Skiftregisterperioden är längden av den resulterande sekvensen innan den börjar upprepas.

För LFSR är återkopplingsfunktionen summa modulo 2(xor) några bitar av registret, anropade böjer sig.

Ett återkopplingsregister med linjär längd består av celler numrerade , som var och en kan lagra en bit och har en ingång och en utgång, såväl som en klocksignal som styr dataoffset. Under varje tidsenhet utförs följande operationer:

Linjärt återkopplingsskiftregister

Således tas den logiska operationen XOR (exklusiv ELLER) som en återkopplingsfunktion, det vill säga:

Egenskaper

Egenskaperna för sekvensen som produceras av LFSR är nära besläktade med egenskaperna associerat polynom över fältet. Dess icke-nollkoefficienter kallas böjer sig, såväl som motsvarande celler i registret, som tillhandahåller värdena för argumenten för återkopplingsfunktionen.

Periodicitet

Eftersom det finns olika registertillstånd som inte är noll, alltså period sekvens som genereras av LFSR för något initialtillstånd som inte är noll överstiger inte . I det här fallet beror perioden på det associerade polynomet:

Egenskaper för primitiva polynom

Linjär komplexitet

Den linjära komplexiteten hos en binär sekvens är en av de viktigaste egenskaperna hos LFSR-drift. Låt oss presentera följande notation:

Definition

Linjär komplexitet En oändlig binär sekvens kallas ett tal, som definieras enligt följande:

Linjär komplexitet den sista binära sekvensen kallas talet , vilket är lika med längden på den kortaste LFSR, som genererar en sekvens som har som första medlemmar .

Linjär komplexitetsegenskaper

Låta och vara binära sekvenser. Sedan:

Korrelation Oberoende

För att få hög linjär komplexitet försöker kryptografer att icke-linjärt kombinera resultaten av flera utdatasekvenser. I det här fallet är faran att en eller flera utgångssekvenser (ofta till och med utgångarna från individuella LFSR) kan kopplas samman med en gemensam nyckelström och avslöjas med linjär algebra. Hacking baserat på en sådan sårbarhet kallas korrelationsobduktion. Thomas Siegenthaler visade att det är möjligt att exakt bestämma korrelation oberoende, och att det finns en avvägning mellan korrelationsoberoende och linjär komplexitet.

Notera

Huvudidén bakom detta hack är att hitta en viss korrelation mellan utsignalen från en generator och utsignalen från en av dess komponentdelar. Sedan, genom att observera utmatningssekvensen, kan information om denna mellanutgång erhållas. Med hjälp av denna information och andra korrelationer är det möjligt att samla in data på andra mellanutgångar tills generatorn hackas.

Exempel

Stegnummer	stat	Bit genererad
0		-
1		1
2		0
3		0
4		1
5		1
6		1
7		0

Algoritmer för att generera primitiva polynom

Färdiga bord

Att beräkna primitiviteten hos ett polynom är ett ganska komplext matematiskt problem. Därför finns det färdiga tabeller som listar antalet uttagssekvenser som ger den maximala perioden för generatorn. Till exempel, för ett 32-bitars skiftregister finns det en sekvens . Detta betyder att för att generera en ny bit är det nödvändigt att summera de 31:a, 30:e, 29:e, 27:e, 25:e och 0:e bitarna med hjälp av XOR-funktionen. Koden för sådan LFSR i språket Xi Nästa:

Int LFSR (void ) ( statisk osignerad lång S = 1 ; S = ((((S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); returnera S & 1 ; )

Konfiguration Galois

Galois-konfiguration av ett linjärt återkopplingsskiftregister

Int LFSR (void ) ( statisk unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

Fördelen är att alla XOR utförs i en operation.

Anmärkningar:

det kan bevisas att Fibonacci-konfigurationen som ges först och Galois-konfigurationen som ges här ger samma sekvenser (med längden 2³²-1), men skiftade i fas från varandra
en slinga av ett fast antal anrop till LFSR-funktionen i Galois-konfigurationen är ungefär dubbelt så snabb som i Fibonacci-konfigurationen (MS VS 2010 kompilator på Intel core i5)
Observera att i Galois-konfigurationen är bitarnas ordningsföljd i återkopplingsordet omvänd jämfört med Fibonacci-konfigurationen

Exempel på generatorer på LFSR

stoppgeneratorer

Stopp-och-gå alternerande generator

Gollmann Cascade

Gollmann Cascade är en förbättrad version av stop-go-generatorn. Den består av en sekvens av LFSR, vars timing styrs av föregående LFSR. Om utsignalen från LFSR-1 vid tidpunkten t är 1, klockas LFSR-2. Om utsignalen från LFSR-2 vid tidpunkten t är 1, så klockas LFSR-2, och så vidare. Utsignalen från den sista LFSR är utsignalen från generatorn. Om längden på alla LFSR är lika och lika med n, är den linjära komplexiteten för ett system av k LFSR lika med

tröskelgenerator

Denna generator består av ett stort antal skiftregister, vars utgångar matas till majoriseringsfunktionen. Om antalet enheter vid registrens utgång är mer än hälften, producerar generatorn en enhet. Om antalet nollor på utgångarna är mer än hälften, producerar generatorn en nolla. För att jämförelsen av antalet nollor och ettor ska vara möjlig måste antalet skiftregister vara udda. Längden på alla register måste vara relativt primtal, och återkopplingspolynomen måste vara det primitiv så att perioden för den genererade sekvensen är maximal.

För fallet med tre skiftregister kan generatorn representeras som:

Denna generator är som Geff generator förutom att tröskelgeneratorn har mer linjär komplexitet. Dess linjära komplexitet är:

Där , , är längden på de första, andra och tredje skiftregistren.

Dess nackdel är att varje utgångsbit ger viss information om skiftregistrets tillstånd. För att vara exakt 0,189 bitar. Därför kanske denna generator inte motstår korrelationsöppningen.

Andra typer av generatorer

Låt oss kort beskriva dem

Självdecimerande generatorer

Självsänkande generatorer kallas generatorer som styr sin egen frekvens. Två typer av sådana generatorer har föreslagits. Den första består av ett linjärt återkopplingsskiftregister och någon krets som klockar detta register, beroende på vad skiftregistrets utvärden är. Om LFSR-utgången är lika med ett, klockas registret d gånger. Om utgången är noll, klockas registret k gånger. Den andra har nästan samma design, men är något modifierad: i klockkretsen, som en kontroll för 0 eller 1, tar inte ingången emot själva utsignalen, utan XOR för vissa bitar i skiftregistret med linjär återkoppling . Tyvärr är denna typ av generator inte säker.

Spelande. Gamma-chiffer. Metoder för att generera chiffer gamma. Linjärt skiftregister.

Kapitel 3. Förfarandet för registrering av enskilda handlingar av civilstånd

Statlig registrering av en emission (tilläggsemission) av värdepapper.

Linear Feedback Shift Register (LFSR) är en mekanism för att skapa en pseudo-slumpmässig sekvens av binära bitar. Registret (fig. 1) består av ett antal celler som sätts av en initieringsvektor (oftast en hemlig nyckel). Registrets funktion bestäms av närvaron eller frånvaron av en anslutning från varje bit till återkopplingen. Återkopplingsregistrets kranar är inte fasta, utan är en del av nyckeln. Vid nästa steg skiftas innehållet i registercellerna en position åt höger och en bit som lämnas ledig som ett resultat av XOR-operationen placeras i cellen längst till vänster.

Ris. 1. Linjärt skiftregister med återkoppling

För att uppnå maximal chiffer gammaperiod, antalet siffror m skiftregistret är valt att vara ett av Mersenne-primtal (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), och de interna länkarna av registret måste väljas enligt med irreducerbara primitiva polynom med högsta grad m. I det här fallet kan chiffer gammaperioden nå (2 m-1).

LFSR är snabbt och enkelt att implementera i både mjukvara och hårdvara. Med rätt val av återkopplingsbitar har de genererade sekvenserna goda statistiska egenskaper. LFSR används som grundelement för att bygga mycket säkra system.

En kaskad av register är en uppsättning LFSR:er länkade på ett sådant sätt att beteendet hos en LFSR beror på beteendet hos den tidigare LFSR i kaskaden. Detta "beroende" beteende sätts vanligtvis in för att styra skifträknaren för nästa LFSR av den första LFSR.

Till exempel skiftas registret med ett steg om värdet för det föregående registret är 1, och om värdet är 0, så skiftas registret med två steg eller på annat sätt. Ett stort antal sådana kombinationer möjliggör mycket hög säkerhet.

De säkraste sekvenserna produceras av en krympande generator baserad på en enkel interaktion mellan resultaten från två LFSR-register. Bitarna i ett resultat avgör om motsvarande bitar i det andra resultatet kommer att användas som en del av den fullständiga "strömnyckeln". Kompressionsgeneratorn är enkel, skalbar och har goda säkerhetsegenskaper. Dess nackdel är att hastigheten med vilken "strömningsnyckeln" genereras inte kommer att vara konstant om inte vissa försiktighetsåtgärder vidtas.

Fibonacci-metoden med förseningar En av de mycket använda Fibonacci-generatorerna är baserad på följande iterativa formel:

var Y k- reella tal från intervallet

Ris. 2. Round-robin-kryptering

DES-utgångsåterkopplingsläget kan användas för att generera pseudoslumptal, liknande hur det används för strömkryptering. Utdata från varje krypteringssteg är ett 64-bitars värde, varav endast de övre j-bitarna återkopplas för kryptering. 64-bitars utgångarna utgör en sekvens av pseudoslumptal med goda statistiska egenskaper.

Generatorn av pseudoslumptal, beskriven i ANSI X9.17-standarden, är en av de kryptografiskt säkraste pseudoslumptalsgeneratorerna. Tillämpningar som använder denna teknik inkluderar ekonomisk säkerhet och PGP-applikationer.

ANSI X9.17-generatorn består av följande delar (Figur 3):

1. Ingång: Generatorn styrs av två pseudo-slumpmässiga ingångar. Den första ingången är en 64-bitars representation av aktuellt datum och tid ( DT i) som ändras varje gång numret skapas. Den andra ingången är ett 64-bitars initialvärde, som initieras till något godtyckligt värde och ändras under genereringen av en sekvens av pseudoslumptal ( Vi).

2. Nycklar: Generatorn använder tre trippel DES-moduler med två nycklar K 1 , K 2 . Alla tre använder samma 56-bitars nyckelpar, som måste hållas hemligt och endast användas för att generera ett pseudoslumptal.

EDE

K1, K2

DT i

R i

Vi+1

3. Utdata: Utdatan består av ett 64-bitars pseudoslumptal R i och ett 64-bitars värde som kommer att användas som startvärde när nästa tal genereras ( Vi +1) .

Ris. 3. ANSI X9.17 pseudo-slumptalsgenerator