Fibonacci metode med forsinkelser

Lagged Fibonacci-generatorer er pseudo - tilfældige tal-generatorer , også kaldet additiv-generatorer .

I modsætning til generatorer, der bruger en lineær kongruentiel algoritme , kan Fibonacci-generatorer bruges i statistiske algoritmer, der kræver høj opløsning.

I denne henseende mistede den lineære kongruentielle algoritme gradvist sin popularitet, og dens plads blev overtaget af familien af Fibonacci-algoritmer, som kan anbefales til brug i algoritmer, der er kritiske for kvaliteten af tilfældige tal .

Historie

En sekvens, der afhænger af mere end én af de foregående værdier og er defineret af følgende formel: $X_{{n+1}}$

X_{{n+1}}=(X_{n}+X_{{n-1}})\mod (2^{m}),

kaldes Fibonacci-sekvensen .

I begyndelsen af 50'erne blev denne algoritme undersøgt, men undersøgelser viste, at denne generator, som en kilde til tilfældige tal, var ineffektiv. Green (Grøn), Smith (Smith) og Klem (Klem) foreslog en modificeret formel for Fibonacci-sekvensen i form:

X_{{n+1}}=(X_{n}+X_{{nk}})\mod (2^{m}).

Et positivt resultat blev dog først opnået kl . $k\geq 16$

I 1958 udledte Mitchell G.J. og Moore D.F. (Moore DP) sekvensen [1] :

X_{{n}}=(X_{{n-24}}+X_{{n-55}})\mod (2^{m}),

(en)

hvor , er et lige tal, er vilkårlige heltal, ikke alle lige tal. Tallene 24 og 55 er valgt således, at der bestemmes en sekvens, hvis mindst signifikante bit har en periodelængde . $n\geq 55$ $m$ $X_{0},X_{1},...,X_{{54}}$ $(X_{n}\mod(2))$ $2^{{55}}-1$

De åbenlyse fordele ved denne algoritme er dens hastighed, da den ikke kræver multiplikation af tal, og også længden af perioden, men tilfældigheden af de tal, der opnås ved hjælp af den, er kun lidt undersøgt.

Tallene 24 og 55 kaldes normalt forsinkelsen, og tallene defineret i (1) er Fibonacci-sekvensen med forsinkelse [2] . $X_n$

Efterfølgende blev der på baggrund af disse værker valgt et sæt forsinkelser , som fører til lange perioder modulo 2.

Formel

Additive generatorer genererer tilfældige ord i stedet for tilfældige bits .

For at fungere kræver additivgeneratoren en eller anden starttilstand, som er en nøgle - et sæt n-bit ord: 16-bit, 32-bit, 64-bit ord osv. - . $X_{1},X_{2},...,X_{k}$

Ved at kende starttilstanden er det muligt at beregne det i-te ord i generatoren ved hjælp af formlen [3] :

X_{{i}}=(X_{{ia}}+X_{{ib}}+...+X_{{ik}})\mod (2^{m}),

og generatorens periode skal være større end eller lig med . $2^{m}-1$

Eksempler på algoritmer baseret på additiv generatorer

1) En af de meget anvendte fibonacci-generatorer er baseret på følgende iterative formel:

X_{k}={\begin{cases}X_{{ka}}-X_{{kb}},&{\text{if }}X_{{ka}}\geq X_{{kb}});\ \ X_{{ka}}-X_{{kb}}+1,&{\text{if }}X_{{ka}}<X_{{kb}};\end{cases}}

hvor er reelle tal fra området , er positive heltal kaldet lags. Når den implementeres gennem heltal, er en formel nok (i dette tilfælde vil der forekomme aritmetiske overløb). For at fungere skal Fibonacci-generatoren kende de tidligere genererede tilfældige tal. Når de er implementeret i software, lagres de genererede tilfældige tal i en endelig cirkulær kø baseret på et array. Fibonacci-generatoren har brug for tilfældige tal for at starte, som kan genereres ved en simpel kongruent metode. $X_{k}$ $[0,1)$ $a,b$ $X_{k}=X_{{ka}}-X_{{kb}}$ $\max\{a,b\}$ $\max\{a,b\}$

De resulterende tilfældige tal har gode statistiske egenskaber, og alle bits af det tilfældige tal er statistisk ækvivalente. Perioden for Fibonacci-generatoren kan estimeres ved hjælp af følgende formel:

T=(2^{{\max\{a,b\))}-1)\cdot 2^{{\ell )),

hvor er antallet af bits i mantissen af et reelt tal. $\ell$

Valg af muligheder

Log a og b er "magiske" og bør ikke vælges vilkårligt. Følgende forsinkelsesværdier anbefales: , eller . Kvaliteten af de resulterende tilfældige tal afhænger af værdien af konstanten, og jo større den er, jo højere er dimensionen af det rum, hvor ensartetheden af tilfældige vektorer dannet ud fra de opnåede tilfældige tal bevares. Samtidig, når værdien af konstanten a stiger, øges mængden af hukommelse, der bruges af algoritmen. $(a,b)=(55,24)$ $(17,5)$ $(97,33)$

Værdierne kan anbefales til simple applikationer, der ikke bruger højdimensionelle vektorer med tilfældige komponenter. Værdierne giver dig mulighed for at få tal, der er tilfredsstillende for de fleste algoritmer, der stiller krav til kvaliteten af tilfældige tal. Værdier giver dig mulighed for at få tilfældige tal af meget høj kvalitet og bruges i algoritmer, der arbejder med højdimensionelle tilfældige vektorer. Den beskrevne Fibonacci tilfældige talgenerator (med forsinkelser 20 og 5) bruges i det almindeligt kendte Matlab -system (forfatteren til den første version af dette system var D. Kahaner). $(a,b)=(17,5)$ $(a,b)=(55,24)$ $(a,b)=(97,33)$

I øjeblikket er der valgt en del par af tal a og b, her er nogle af dem:

(24.55),(38.89),(37.100),(30.127),(83.258),(107.378),(273.607),(1029.2281),(576.3217),(4178.9689), ...

2) Bruce Schneier giver i sit arbejde "Applied Cryptography" eksempler på 3 algoritmer baseret på additivgeneratorer [5] :

Fiskealgoritmen _

“Fisk er en additivgenerator baseret på de teknikker, der bruges i den decimerede generator. Det producerer en strøm af 32-bit ord, der kan bruges (af XOR) med klartekststrømmen for at få chiffertekst eller med chiffertekststrømmen for at få klartekst. Navnet på algoritmen er en forkortelse for Fibonacci shrinking generator - udtyndet Fibonacci generator.

Brug først følgende to additivgeneratorer. Nøglen er starttilstandene for disse generatorer.

A_{i}=(A_{{i-55}}+A_{{i-24}})\mod (2^{{32}})

B_{i}=(B_{{i-52}}+B_{{i-19}})\mod (2^{{32}})

Disse sekvenser udtyndes i par afhængigt af den mindst signifikante bit : hvis dens værdi er 1, så bruges parret, hvis 0 ignoreres det. er rækkefølgen af brugte ord , a er rækkefølgen af brugte ord . For at generere to 32-bit resultatord, og disse ord bruges i par - . $B_{i}$ $C_{j}$ $A_{i}$ $D_{j}$ $B_{i}$ $K_{{2j}}$ $K_{{2j+1}}$ $C_{{2j}},C_{{2j+1}},D_{{2j}},D_{{2j+1}}$

E_{{2j}}=C_{{2j}}\oplus (D_{{2j}}\land D_{{2j+1}})

F_{{2j}}=D_{{2j+1}}\oplus (E_{{2j}}\land C_{{2j+1}})

K_{{2j}}=E_{{2j}}\oplus F_{{2j}}

K_{{2j+1}}=C_{{2j+1}}\oplus F_{{2j}}

Denne algoritme er hurtig; på i486/33-processoren krypterer C-implementeringen af Fish data med 15 Mbps. Desværre er det heller ikke sikkert, obduktionsordren er omkring 2 40. ”

The Pike Algorithm

Pike er en udtømt og afklædt version af Fish af Ross Anderson , personen der knækkede Fish. Den bruger tre additivgeneratorer. For eksempel:

A_{i}=(A_{{i-55}}+A_{{i-24}})\mod (2^{{32}})

B_{i}=(B_{{i-57}}+B_{{i-7}})\mod (2^{{32}})

C_{i}=(C_{{i-58}}+C_{{i-19}})\mod (2^{{32}})

For at generere et nøglestrømsord skal du desuden se på bærebittene. Hvis alle tre er ens (alle nuller eller alle enere), så klokkes alle tre generatorer. Hvis ikke, klokkes der kun to matchende oscillatorer. Gem bærestykkerne til næste gang. Den endelige udgang er XOR for udgangene fra de tre oscillatorer.

Gedde er hurtigere end Fish, da det tager 2,75 handlinger i gennemsnit for at få et resultat i stedet for 3. Det er også for nyt til at man kan stole på, men det ser ret godt ud."

Mush- algoritme

"Mush er en gensidigt udtyndende generator. Hans arbejde er let at forklare. Lad os tage to additiv generatorer: A og B. Hvis bærebit A er indstillet, klokkes B. Hvis bærebit B er indstillet, klokkes A. Vi clocker A , og ved overløb sætter vi bærebit. Vi ur B og sætter bærebitten på overløb. Det endelige output er XOR for output A og B. Den nemmeste måde er at bruge de samme generatorer som i Fish:

A_{i}=(A_{{i-55}}+A_{{i-24}})\mod (2^{{32}})

B_{i}=(B_{{i-52}}+B_{{i-19}})\mod (2^{{32}})

I gennemsnit tager det tre iterationer af generatoren at generere ét outputord. Og hvis koefficienterne for additivgeneratoren er valgt korrekt og er relativt prime, vil længden af outputsekvensen være maksimal."

Noter

↑ Knut D. Kunsten at programmere. - Bind 2. - 3. udgave. - 2001 - Kap.3.2.2.
↑ Knut D. Kunsten at programmere. - bind 2. - 3. udgave - 2001 - s.39.
↑ Schneier B. Anvendt kryptografi. Protokoller, algoritmer og kildetekster i C. - 2002 - S. 291.
↑ Bruce, Schneier. 16.9 Additive Generators // Anvendt kryptografi: protokoller, algoritmer og kildekode i C. John Wiley & Sons, Inc., New York (1996).
↑ Schneier B. Anvendt kryptografi. Protokoller, algoritmer og kildetekster i C-sprog - 2002 - kap.16.9.

Litteratur

Ferguson N., Schneier B. Praktisk kryptografi. - Dialektik, 2005. - 418 s.
Lifshits Yu nr. 9 // Moderne problemer med kryptografi. - Et kursus med forelæsninger .. - Matematiklaboratorium. Logik POMI RAN, 2005.
Zhelnikov V. Kryptografi fra papyrus til computer. - 1996. - 325 s.
William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery. Numeriske opskrifter i C: The Art of Scientific Computing. - 1992.
Ross Andersen. På Fibonacci Keystream Generatorer. - Computerrum. Pembroke Street, Cambridge CB2 3QG.