Bär feedback skiftregister

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 13 mars 2013; kontroller kräver 23 redigeringar .

Skiftregister med överföringsskiftregister ( FCSR ) är ett skiftregister av , en aritmetisk analog till ett  linjärt återkopplingsskiftregister , som skiljer sig från det genom närvaron av ett överföringsregister. Den används för att generera pseudo-slumpmässiga bitsekvenser och användes också för att skapa F-FCSR- strömchifferet .

Historik

1994 uppfanns skiftregistret med bärfeedback av Goresky och Ecuyer L'och)Coutureengelsk(Couture,ZamanochMarsagliaavoberoendeKlapper, samt engelska L'Ecuyer ). Dessutom ville Clapper och Goresky använda den för kryptoanalys av summeringsgeneratorn. Å andra sidan siktade Marsaglia, Zaman, Couture, L'Ecuer på att hitta en bra slumptalsgenerator för att lösa problem som att använda quasi-Monte Carlo-metoden . [ett]      

Beskrivning

FCSR har ett skiftregister, en återkopplingsfunktion och ett överföringsregister . Längden på skiftregistret är antalet bitar. När en bit behöver extraheras skiftas alla bitar i skiftregistret åt höger med en position. [2]

Istället för att XORera alla bitar i tappsekvensen, adderas dessa bitar till varandra och till innehållet i bärregistret. Resultatet blir ett nytt beat. Resultatet dividerat med blir det nya innehållet i bärregistret. [3]

 — Värdet på transportregistret

 — ny tillstånd i registret

 — Nytt värde på överföringsregistret

Exempel

Betrakta ett exempel på ett 3-bitars register med uttag i första och andra positionen. Låt dess initiala värde vara och det initiala innehållet i bärregistret vara lika med . Utsignalen kommer att vara biten längst till höger i skiftregistret . Ytterligare tillstånd i registret visas i tabellen nedan:

Stegnummer skift register Bär register
0 0
ett 0
2 0
3 0
fyra 0
5 0
6 ett
7 ett
åtta ett
9 ett
tio ett
elva 0

Det slutliga interna tillståndet (inklusive innehållet i överföringsregistret) är detsamma som det andra interna tillståndet. Från och med detta ögonblick upprepas sekvensen cykliskt med en period lika med . Det är också värt att nämna att bärregistret inte är en bit , utan ett nummer. Dess storlek måste vara minst , där  är antalet grenar. I exemplet finns det bara tre grenar, så bärregistret är enbit. Om det fanns fyra grenar skulle bärregistret bestå av två bitar och skulle kunna ta på sig värdena eller . [3]

Egenskaper

Till skillnad från LFSR finns det en fördröjning för FCSR innan den går in i den cykliska moden, det vill säga den börjar generera en cyklisk upprepad sekvens. Beroende på det valda initiala tillståndet är 4 olika fall möjliga: [3]

Empiriskt kan du kontrollera hur ett visst initialtillstånd slutar. Måste köra FCSR ett tag. (Om  är den initiala mängden minne och  är antalet grenar, då är cykler tillräckliga.) Om utgångsströmmen urartar till en oändlig sekvens av nollor och ettor per bit, var  är längden på FCSR, bör detta initiala tillstånd inte användas. [3]

Det är också värt att notera att en uppsättning FCSR-baserade generatornycklar kommer att vara svaga, eftersom det initiala tillståndet för FCSR motsvarar nyckeln för strömchifferet. [3]

Den maximala FCSR-perioden är, där är ett heltal för anslutningen. Detta nummer definierar grenar och definieras som:

 - måste vara ett primtal där 2 är en primitiv rot . [3] [1]

Anslutning till LFSR

Precis som LFSR-analys är baserad på tillägg av primitiva mod 2-polynom, baseras FCSR-analys på tillägg av tal, kallade 2-adic . I en värld av 2-adiska nummer finns det analoger för allt. På samma sätt som linjär komplexitet definieras, kan 2-adisk komplexitet också definieras. Det finns också en 2-adisk analog för Berlekamp-Massey-algoritmen . Det betyder att antalet möjliga strömchiffer åtminstone har fördubblats. Allt som kan göras med LFSR kan göras med FCSR. [3]

Implementeringsalternativ

Galois-konfiguration

Galois-konfigurationen består av:

Vid tidpunkten t ändras tillståndet enligt följande:

1. , för alla , med och och där representerar återkopplingsbiten.

2. Status uppdateras: , för alla och , för alla . [4] [5]

Fibonacci-konfiguration

Fibonacci-konfigurationen består av:

Staten ändras enligt följande:

1  .;

2. uppdateringstillstånd: , . [4] [5]

Möjliga användningsfall i generatorer

Interfolierade stop-and-go-generatorer

Huvudartikel: Stop-go-generator

Den använder tre skiftregister av olika längd. Här styr Register-1 klockfrekvensen för det andra och 3:e registret, det vill säga Register-2 ändrar sitt tillstånd när utsignalen från Register-1 är lika med ett, och Register-3 - när utsignalen från Register-1 är lika med noll. [3]

Dessa register använder FCSRs istället för vissa LFSRs, och XOR-operationen kan ersättas med en carry add.

Kaskadgeneratorer

Huvudartikel: Gollmann Cascade

Denna krets är en förbättrad version av stop-go-generatorn. Den består av en sekvens av register, vars klockning styrs av det föregående registret. Om utsignalen från Register-1 vid tidpunkten är 1, klockas Register-2. Om utsignalen från Register-2 vid tidpunkten är 1, klockas Register-3, och så vidare. Utsignalen från det sista registret är utsignalen från generatorn. [3]

Det finns två sätt att använda FCSR i kaskadkopplade oscillatorer:

Kombinerade generatorer

Dessa generatorer använder ett variabelt antal FCSR:er och/eller LFSR:er och en mängd olika funktioner som kombinerar register. XOR-operationen förstör de algebraiska egenskaperna hos FCSR, så det är vettigt att använda den här operationen för att kombinera dem. [3]

Applikation

Skiftregister med bärfeedback kan tjäna som bas för att skapa olika generatorer (av vilka några beskrivs ovan), såväl som olika strömchiffer.

F-FCSR

Huvudartikel: F-FCSR .

F-FCSR är en familj av strömchiffer baserad på användningen av ett överföringsåterkopplingsskiftregister (FCSR) med ett linjärt utgångsfilter. Idén till chiffret föreslogs av Terry Berger, François Arnault och Cédric Larade. F-FCSR skickades till eSTREAM- tävlingen , ingick i listan över vinnare av tävlingen i april 2008, men senare avslöjades en kryptografisk svaghet och i september 2008 avnoterades F-FCSR från eSTREAM.

Se även

Anteckningar

  1. 1 2 A. Klapper En undersökning av feedback med bärskiftregister  (nedlänk)
  2. A. Klapper och M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, i Journal of Cryptology vol. 10, sid. 111-147 , 1997, [1]  (otillgänglig länk)
  3. 1 2 3 4 5 6 7 8 9 10 11 12 13 B. Schneier, 2013 .
  4. 1 2 A. Klapper och M. Goresky, Fibonacci och Galois Representations of Feedback with Carry Shift Registers , 2004, [2] Arkiverad 23 september 2015 på Wayback Machine
  5. 1 2 Francois Arnault, Thierry Berger, C´edric Lauradoux, Marine Minier och Benjamin Pousse, A new approach for FCSRs , [3] Arkiverad 2 juni 2018 på Wayback Machine

Litteratur