Regjistri i zhvendosjes së reagimit linear. Regjistri linear i përsëritur

Regjistri i ndryshimit të komenteve ( FSR ) përbëhet nga dy pjesë: regjistri i ndërrimit Dhe funksionet e reagimit .

Regjistri i zhvendosjes (Gabim: Burimi i referencës nuk u gjet) është një sekuencë bitësh. Kur një bit duhet të nxirret, të gjithë bitët e regjistrit të zhvendosjes zhvendosen djathtas me 1 pozicion. Biti i ri më i majtë është vlera e funksionit të reagimit nga bitet e mbetura në regjistër. Periudha Regjistri i zhvendosjes është gjatësia e sekuencës që rezulton përpara se të fillojë të përsëritet.

Lloji më i thjeshtë i regjistrit të zhvendosjes së reagimeve është regjistri i zhvendosjes lineare me reagime (LFSR – Majtas Feedback Ndërrimi Regjistrohu) (Gabim: Burimi i referencës nuk u gjet). Reagimi është thjesht XOR i disa biteve p. regjistri, thirret lista e këtyre biteve sekuenca e anashkalimit.

n-bit LFSR mund të jetë në një nga 2 n -1 gjendjet e brendshme. Kjo do të thotë se, teorikisht, një regjistër i tillë mund të gjenerojë një sekuencë pseudo të rastësishme me një pikë 2 n -1 copa. Numri i gjendjeve të brendshme dhe periudha janë të barabarta, sepse plotësimi i regjistrit me zero do të bëjë që ai të prodhojë një sekuencë të pafundme zerosh, gjë që është absolutisht e padobishme. Vetëm me sekuenca të caktuara trokitjesh, LFSR do të qarkullojë nëpër të gjitha 2 n -1 gjendjet e brendshme. LFSR të tilla quhen LFSRme një periudhë maksimale.

Që një LFSR e veçantë të ketë një periudhë maksimale, polinomi i formuar nga sekuenca e trokitjes dhe konstanta 1 duhet të jetë modul primitiv 2 .

Llogaritja e primitivitetit të një polinomi është një problem matematikor mjaft kompleks. Prandaj, ekzistojnë tabela të gatshme që listojnë numrat e sekuencave të trokitjerave që ofrojnë periudhën maksimale të gjeneratorit. Për shembull, për një regjistër të zhvendosjes 32-bit, mund të gjeni hyrjen e mëposhtme: (32,7,5,3,2,1,0) . Kjo do të thotë që për të gjeneruar një bit të ri, duhet të përmblidhni bitet e tridhjetë e dytë, të shtatë, të pestë, të tretë, të dytë dhe të parë duke përdorur funksionin XOR.

Kodi për një LFSR të tillë në C++ do të ishte:

// Çdo vlerë tjetër përveç zeros

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegjistrohu)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

kthe ShiftRegister & 0x00000001;

Implementimet e softuerit të LFSR-ve janë mjaft të ngadalta dhe funksionojnë më shpejt nëse ato shkruhen në assembler dhe jo në C. Një zgjidhje është përdorimi i 16 LFSR-ve paralelisht (ose 32 në varësi të gjatësisë së fjalës në arkitekturën e një kompjuteri të caktuar). Në këtë skemë, përdoret një grup fjalësh, madhësia e të cilit është e barabartë me gjatësinë e LFSR, dhe secila njësi e një fjale në grup i referohet LFSR-së së vet. Me kusht që të përdoren të njëjtët numra të sekuencës së prekjes, kjo mund të japë një fitim të dukshëm të performancës.

ME qarku i reagimit gjithashtu mund të modifikohet. Në këtë rast, gjeneratori nuk do të ketë forcë më të madhe kriptografike, por do të jetë më e lehtë për ta zbatuar atë në mënyrë programore. Në vend që të përdorni bitin më të majtë të biteve të sekuencës së prekjes për të gjeneruar një bit të ri, XOR çdo bit të sekuencës së prekjes me daljen e gjeneratorit dhe zëvendësoni atë me rezultatin e këtij veprimi, atëherë rezultati i gjeneratorit bëhet biti i ri më i majtë ( Gabim: Burimi i referencës nuk u gjet).

Ky modifikim quhet Konfigurimi Galois. Në gjuhën C duket kështu:

ShiftRegister i gjatë statik i panënshkruar = 1;

void seed_LFSR (farë e gjatë e panënshkruar)

ShiftRegister = farë;

int Galua_LFSR (i pavlefshëm)

nëse (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000;

ShiftRegister >>= 1;

Shpërblimi është se të gjitha XOR-të kryhen në një operacion. Ky qark gjithashtu mund të paralelizohet.

Në vetvete, LFSR-të janë gjeneratorë të mirë të sekuencave pseudo të rastësishme, por ato kanë disa veti të padëshirueshme jo të rastësishme. Bitët sekuencialë janë linearë, duke i bërë të padobishëm për enkriptim. Për gjatësinë LFSR n gjendja e brendshme përfaqëson të mëparshmen n bitet e daljes së gjeneratorit. Edhe nëse skema e reagimit mbahet e fshehtë, ajo mund të përcaktohet nga 2 n bitet e prodhimit të gjeneratorit duke përdorur algoritme speciale. Për më tepër, numrat e mëdhenj të rastësishëm të gjeneruar duke përdorur pjesë të njëpasnjëshme të kësaj sekuence janë shumë të ndërlidhura dhe, për disa lloje aplikacionesh, nuk janë të rastësishëm. Përkundër kësaj, LFSR-të shpesh përdoren për të krijuar algoritme kriptimi. Për këtë, përdoren disa LFSR, zakonisht me gjatësi dhe numra të sekuencës së prekjes. Çelësi është gjendja fillestare e regjistrave. Sa herë që nevojitet një bit i ri, të gjithë regjistrat zhvendosen. Ky operacion quhet duke rrahur. Biti i daljes është një funksion, mundësisht jolinear, i disa biteve të LFSR. Ky funksion quhet duke kombinuar, dhe gjeneratori në tërësi - gjenerator i kombinuar. Shumë nga këta gjeneratorë janë ende të sigurt sot.

Regjistri i zhvendosjes së reagimeve lineare(RSLOS, eng. regjistri i ndërrimit të feedback-ut linear, LFSR ) është një regjistër ndërrimi i fjalëve bit, në të cilin vlera e bitit hyrës (rrëshqitës) është e barabartë me një funksion linear Boolean nga vlerat e biteve të mbetura të regjistrit përpara zhvendosjes. Mund të organizohet si nga softueri ashtu edhe nga hardueri. Përdoret për të gjeneruar bit-sekuenca pseudo të rastësishme, e cila përdoret, në veçanti, në kriptografi.

Përshkrim

Kontrolli i regjistrit në implementimet e harduerit kryhet duke aplikuar një impuls ndërrimi (i quajtur ndryshe me orë ose sinkronizimi i pulsit) për të gjitha qelizat. Menaxhimi i regjistrit në implementimet e softuerit kryhet duke ekzekutuar një lak. Në çdo përsëritje të ciklit, funksioni i reagimit llogaritet dhe bitet në fjalë zhvendosen.

Parimi i funksionimit

Kompleksiteti linear

Korrelacioni Pavarësia

Në një përpjekje për të marrë një kompleksitet të lartë linear të sekuencës së gjeneruar, kriptografët kombinojnë në mënyrë jolineare rezultatet e disa regjistrave të zhvendosjes. Në këtë rast, një ose më shumë sekuenca dalëse (ose edhe dalje të LFSR-ve individuale) mund të lidhen nga një rrymë e përbashkët dhe të hapen nga një kriptanalist. Hakerimi i bazuar në një dobësi të tillë quhet hapja e korrelacionit. Ideja kryesore e një hakimi të tillë është të gjesh një lidhje midis prodhimit të gjeneratorit dhe daljeve të pjesëve përbërëse të tij. Më pas, duke vëzhguar sekuencën e daljes, mund të merret informacion rreth këtyre daljeve të ndërmjetme, dhe kështu të hakohet gjeneratori. Thomas Siegenthaler tregoi se është e mundur të përkufizohet saktësisht pavarësia e korrelacionit dhe se ekziston një shkëmbim ndërmjet pavarësisë së korrelacionit dhe kompleksitetit linear.

Implementimi i softuerit

Implementimet e softuerit të RSLOS janë mjaft të ngadalta dhe funksionojnë më shpejt nëse shkruhen në asembler. Një nga zgjidhjet është përdorimi paralel i 16 RLLS (ose 32, në varësi të gjatësisë së fjalës në arkitekturën e kompjuterit). Në një skemë të tillë, përdoret një grup fjalësh, madhësia e të cilave është e barabartë me gjatësinë e regjistrit të zhvendosjes, dhe çdo bit i fjalës i referohet LFSR-së së vet. Meqenëse përdoren të njëjtin numër të sekuencave të trokitjerave, kjo mund të japë një përfitim të dukshëm në performancën e gjeneratorit.

Konfigurimi Fibonacci

Konsideroni një regjistër të zhvendosjes 32-bit. Ka një sekuencë ikjeje (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \majtas(32,\;31,\;30,\;28,\;26,\;1\djathtas)). Kjo do të thotë që për të gjeneruar një bit të ri, është e nevojshme të përmblidhen bitet e 31-të, 30-të, 29-të, 27-të, 25-të dhe 0-të duke përdorur operacionin XOR. LFSR që rezulton ka një periudhë maksimale 2 32 − 1 (\displaystyle 2^(32)-1). Kodi për një regjistër të tillë në C është si më poshtë:

int LFSR_Fibonacci (i pavlefshëm) (S i gjatë statik i panënshkruar = 0x00000001; S = ((((S >> 31) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25) ^ S) & 0x00000001)<< 31 ) | (S >> 1); kthimi S & 0x00000001 ; )

Konfigurimi Galois

Ky gjenerator nuk ka forcë më të madhe kriptografike, por jep një fitim të performancës: të gjitha operacionet XOR përmes paralelizimit mund të kryhen në një operacion, dhe jo në mënyrë sekuenciale njëri pas tjetrit, si në konfigurimin Fibonacci. Kjo skemë do të japë gjithashtu një përfitim në zbatimin e harduerit.

Kodi për një regjistër të zhvendosjes 32-bit në C është si më poshtë:

int LFSR_Galois (i pavlefshëm) (S i gjatë statik i panënshkruar = 0x00000001 ; nëse (S & 000000001 ) (S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; tjetër) 1 kthim) >> 1 kthim

Vlen të përmendet se cikli i një numri fiks thirrjesh në funksionin LFSR_Galois në konfigurimin Galois është afërsisht 2 herë më i shpejtë se funksioni LFSR_Fibonacci në konfigurimin Fibonacci (përpiluesi MS VS 2010 në Intel Core i5).

Shembull i sekuencës së gjeneruar

Konfigurimi Fibonacci

Le të jepet LFSR nga polinomi karakteristik x 3 + x + 1 (\style ekrani x^(3)+x+1). Kjo do të thotë që bit-at e trokitjes do të jenë të 2-të dhe të 0-të, dhe njësia në formulën polinomiale do të thotë që biti i 0-të është hyrja. Funksioni i reagimit ka formën S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\plus S_(j-3)). Supozoni se gjendja fillestare e regjistrit të zhvendosjes ishte sekuenca . Gjendjet e mëtejshme të regjistrit janë paraqitur në tabelën e mëposhtme:

Meqenëse gjendja e brendshme në hapin e shtatë u kthye në gjendjen e saj origjinale, atëherë, duke filluar nga hapi tjetër, bitet do të përsëriten. Pra, sekuenca e krijuar është: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle\majtas)(rendi i biteve në sekuencë korrespondon me rendin në të cilin janë gjeneruar nga LFSR). Kështu, periudha e sekuencës është 7, domethënë vlera maksimale e mundshme, e cila ndodhi për shkak të primitivitetit të polinomit të dhënë.

Konfigurimi Galois

Le të marrim të njëjtin polinom karakteristik, d.m.th. c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Vetëm biti i parë i shtohet bitit të daljes. Gjendja fillestare është e njëjtë. Gjendjet e tjera të regjistrit:

Gjendja e brendshme e regjistrit në hapin e shtatë u kthye në gjendjen e tij origjinale, prandaj, periudha e tij është gjithashtu e barabartë me 7. Ndryshe nga konfigurimi Fibonacci, gjendjet e brendshme të regjistrit rezultuan të jenë të ndryshme, por sekuenca e krijuar është e njëjtë , zhvendosur vetëm me 4 cikle: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle\majtas)(rendi i biteve në sekuencë korrespondon me rendin në të cilin janë gjeneruar nga LFSR).

Gjenerimi i polinomeve primitive

Avantazhet dhe disavantazhet

Përparësitë

• performancë e lartë e algoritmeve kriptografike të krijuara në bazë të LFSR (për shembull, shifrat e transmetimit);
• përdorimi i vetëm operacioneve më të thjeshta të biteve të mbledhjes dhe shumëzimit, të zbatuara në harduer pothuajse në të gjitha pajisjet kompjuterike;
• veti të mira kriptografike (LFSR-të mund të gjenerojnë sekuenca me periudha të gjata me veti të mira statistikore);
• për shkak të strukturës së tyre, LFSR-të analizohen lehtësisht duke përdorur metoda algjebrike.

Të metat

Mënyrat për të përmirësuar forcën kriptografike të sekuencave të krijuara

Gjeneratorë me regjistra me ndërrime të shumëfishta

Ky lloj gjeneratori përbëhet nga disa regjistra linearë të zhvendosjes së reagimit që gjenerojnë bit x 1 , i , x 2 , i , … , x M , i (\shfaqja e stilit x_(1,i),\;x_(2,i),\;\pikat ,\;x_(M,i)) përkatësisht. Më tej, bitet e krijuara transformohen nga disa funksione boolean f (x 1 , i , x 2 , i , … , x M , i) (\stil ekrani f(x_(1,i),\;x_(2,i),\;\pika ,\;x_(M ,i))). Duhet të theksohet se gjeneratorët e këtij lloji kanë gjatësi regjistrash L i (\displaystyle L_(i)), i = 1 , 2 , ... , M (\style display i=1,\;2,\;\pika ,\;M), jane coprime me njeri tjetrin.

Periudha e këtij gjeneratori është T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2)-1)\cpika (2^(L_(M))-1)\lesssim 2^(L)), Ku L = ∑ i = 1 M L i (\displaystyle L=\shuma \ limitet _(i=1)^(M)L_(i))- numri i përgjithshëm i qelizave. Prandaj, përdorimi i disa LFSR-ve rrit periudhën e sekuencës së gjeneruar në krahasim me një regjistër të vetëm, gjë që rrit fuqinë kriptografike të gjeneratorit. Ai gjithashtu rrit kompleksitetin linear ose gjatësinë e regjistrit më të shkurtër që korrespondon me një gjenerator të caktuar. Një regjistër i tillë gjendet duke përdorur algoritmin Berlekamp-Massey duke përdorur sekuencën e gjeneruar. Në rastin më të mirë, gjatësia e saj është në përpjesëtim me periudhën e sekuencës së krijuar.

Gjeneratorë me transformime jolineare

Diagrami bllok i një gjeneratori të tillë nuk është i ndryshëm nga diagrami i gjeneratorit të mëparshëm. Dallimi kryesor është se pajisja e transformimit jepet nga një funksion jolinear Boolean f (x 1 , x 2 , … , x M) (\style ekrani f(x_(1),x_(2),\pika ,x_(M))). Për shembull, polinomi Zhegalkin merret si funksion i tillë (sipas teoremës Zhegalkin, çdo funksion Boolean mund të përfaqësohet në mënyrë unike nga polinomi Zhegalkin).

Një gjenerator jolinear gjithashtu mund të zbatohet në regjistri i zhvendosjes jolineare të reagimit. Ai mund të japë 2 2 L − 1 − L (\style ekrani 2^(2^(L-1)-L)) variante të sekuencave periudha maksimale , që është më shumë se ajo e LFSR .

Fuqia kriptografike e këtij gjeneratori është rritur për shkak të jolinearitetit të funksionit të përdorur. Përcaktimi i gjendjes së regjistrave nga sekuenca e biteve të gjeneruara është një problem kompleks matematikor, sepse nuk dihet asnjë algoritëm që rikthen gjendjet origjinale.

Kjo metodë përdoret, për shembull, në gjenerator Geff dhe gjeneratori i përgjithësuar Geff, megjithatë, gjeneratorë të tillë mund të prishen nga një sulm korrelacioni.

Gjeneratorë me kohë të ndryshme regjistrash ndërrimi

gjenerator stop-go

gjenerator stop-go(Anglisht Stop-and-Go , Both-Piper ) përdor daljen e LFOS-1 për të kontrolluar frekuencën e orës së LFOS-2, në mënyrë që LFSR-2 të ndryshojë gjendjen e tij në një moment në kohë vetëm nëse dalja e LFOS-1 në atë kohë ishte e barabartë me njësinë. Kjo skemë nuk i rezistoi hapjes së korrelacionit.

Për të rritur fuqinë kriptografike, u propozua alternator ndal-dhe-shko. Ai përdor tre regjistra ndërrimi me gjatësi të ndryshme. Këtu, LFOS-1 kontrollon frekuencën e orës së regjistrave të 2-të dhe të 3-të, domethënë, LFSR-2 ndryshon gjendjen e tij kur dalja LFSR-1 është e barabartë me një, dhe LFSR-3 - kur dalja LFSR-1 është e barabartë me zero. Dalja e gjeneratorit është operacioni i shtimit të  modulo dy daljeve të RLOS-2 dhe RLOS-3. Ky gjenerator ka një periudhë të madhe dhe një kompleksitet të madh linear. Ekziston një metodë e hapjes së korrelacionit të RLOS-1, por kjo nuk i dobëson shumë vetitë kriptografike të gjeneratorit.

Përdoret një skemë e sofistikuar e orës gjenerator me dy drejtime ndale-dhe-shko, i cili përdor 2 regjistra ndërrimi me të njëjtën gjatësi. Nëse prodhimi i RLOS-1 në një moment në kohë t i − 1 (\displaystyle t_(i-1))- një, atëherë RLOS-2 nuk është akorduar në atë kohë t i (\displaystyle t_(i)). Nëse dalja e RLOS-2 në momentin e kohës t i − 1 (\displaystyle t_(i-1)) barazohet me zero, dhe në kohë t i − 2 (\displaystyle t_(i-2))- një, dhe nëse ky regjistër është i akorduar në atë kohë t i (\displaystyle t_(i)), atëherë në të njëjtin moment RLOS-1 nuk është i akorduar. Kompleksiteti linear i këtij qarku është afërsisht i barabartë me periudhën e sekuencës së krijuar.

Gjenerator që vetëshkatërrohet

Oscilator me shumë norma me produkt të brendshëm

Ky gjenerator përdor dy regjistra ndërrimi RSLOS-1 dhe RSLOS-2. Frekuenca e orës prej RSLOS-2 in d (\displaystyle d) herë më shumë se ai i RSLOS-1. Disa pjesë të këtyre regjistrave shumëzohen me njëri-tjetrin duke përdorur operacionin AND. Rezultatet e shumëzimeve shtohen nga operacioni XOR dhe merret sekuenca e daljes. Ky gjenerator ka një kompleksitet të lartë linear dhe ka veti të mira statistikore. Megjithatë, gjendja e tij mund të përcaktohet nga një sekuencë dalëse e gjatësisë L 1 + L 2 + log 2 ⁡ d (\shfaqja e stilit L_(1)+L_(2)+\log _(2)(d)), Ku L 1 (\displaystyle L_(1)) Dhe L 2 (\displaystyle L_(2)) janë gjatësitë e LFOS-1 dhe LFOS-2, përkatësisht, dhe d (\displaystyle d)- raporti i frekuencave të tyre të orës.

Kaskada e Gollmanit

Ky qark është një version i përmirësuar i gjeneratorit stop-go. Ai përbëhet nga një sekuencë LFSR-sh, koha e secilës prej të cilave kontrollohet nga LFSR-ja e mëparshme. Nëse prodhimi i RLOS-1 në atë kohë t i (\displaystyle t_(i))është 1, atëherë RLOS-2 është i akorduar. Nëse dalja e RLOS-2 në momentin e kohës t i (\displaystyle t_(i))është 1, pastaj RLOS-3 është i akorduar, e kështu me radhë. Prodhimi i LFSR-së së fundit është dalja e gjeneratorit. Nëse gjatësia e të gjitha LFSR-ve është e njëjtë dhe e barabartë me L (\displaystyle L), pastaj periudha e sistemit nga M (\displaystyle M) LFSR është e barabartë me (2 L − 1) M (\style ekrani (2^(L)-1)^(M)), dhe kompleksiteti linear është L (S) = L (2 L − 1) M − 1 (\shtili i ekranit L(S)=L(2^(L)-1)^(M-1)) .

Kjo ide është e thjeshtë dhe mund të përdoret për të gjeneruar sekuenca me periudha të mëdha, kompleksitete të mëdha lineare dhe veti të mira statistikore. Por, për fat të keq, ata janë të ndjeshëm ndaj një autopsie të thirrur mbyllje(ang. lock-in) kur

Regjistri Linear Feedback Shift (LFSR) është një mekanizëm për krijimin e një sekuence pseudo të rastësishme të biteve binare. Regjistri (Fig. 1) përbëhet nga një numër qelizash që vendosen nga një vektor inicializimi (më shpesh një çelës sekret). Funksionimi i regjistrit përcaktohet nga prania ose mungesa e një lidhjeje nga çdo bit me reagimin. Trokitjet e regjistrit të reagimeve nuk janë fikse, por janë pjesë e çelësit. Në hapin tjetër, përmbajtja e qelizave të regjistrit zhvendoset një pozicion në të djathtë dhe një bit lihet i lirë si rezultat i operacionit XOR vendoset në qelizën më të majtë.

Oriz. 1. Regjistri i zhvendosjes lineare me reagime

Për të arritur periudhën maksimale të gama të shifrimit, numrin e shifrave m regjistri i ndërrimit është zgjedhur të jetë një nga numrat kryesorë të Mersenne (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), dhe lidhjet e brendshme i regjistrit duhet të zgjidhet sipas me polinome primitive të pareduktueshme me shkallë më të lartë m. Në këtë rast, periudha e gamës së shifrimit mund të arrijë (2 m-1).

LFSR është i shpejtë dhe i lehtë për t'u zbatuar si në softuer ashtu edhe në harduer. Me zgjedhjen e duhur të biteve të reagimit, sekuencat e gjeneruara kanë veti të mira statistikore. LFSR përdoret si një element bazë për ndërtimin e sistemeve shumë të sigurta.

Një kaskadë regjistrash është një grup LFSR-sh të lidhur në atë mënyrë që sjellja e një LFSR varet nga sjellja e LFSR-së së mëparshme në kaskadë. Kjo sjellje "e varur" zakonisht vendoset për të kontrolluar numëruesin e ndërrimit të LFSR-së së ardhshme nga LFSR-ja e parë.

Për shembull, regjistri zhvendoset me një hap nëse vlera e regjistrit të mëparshëm është 1, dhe nëse vlera është 0, atëherë regjistri zhvendoset me dy hapa ose ndryshe. Një numër i madh i kombinimeve të tilla mundëson siguri shumë të lartë.

Sekuencat më të sigurta prodhohen nga një gjenerator që zvogëlohet bazuar në një ndërveprim të thjeshtë midis rezultateve të dy regjistrave LFSR. Bitet e një rezultati përcaktojnë nëse bitet përkatëse të rezultatit të dytë do të përdoren si pjesë e "çelësit të transmetimit" të plotë. Gjeneratori i kompresimit është i thjeshtë, i shkallëzuar dhe ka veti të mira sigurie. Disavantazhi i tij është se shpejtësia me të cilën gjenerohet "çelësi i transmetimit" nuk do të jetë konstante nëse nuk merren disa masa paraprake.

Metoda Fibonacci me vonesa Një nga gjeneratorët e përdorur gjerësisht Fibonacci bazohet në formulën e mëposhtme përsëritëse:

Ku Y k- numra realë nga diapazoni

Oriz. 2. Round-robin encryption

Modaliteti i reagimit të daljes DES mund të përdoret për të gjeneruar numra pseudo të rastësishëm, të ngjashëm me mënyrën se si përdoret për enkriptimin e transmetimit. Dalja e çdo faze të enkriptimit është një vlerë 64-bitësh, nga e cila vetëm bitet e sipërme j kthehen për kriptim. Daljet 64-bit përbëjnë një sekuencë numrash pseudo të rastësishëm me veti të mira statistikore.

Gjeneruesi i numrave pseudo të rastësishëm, i përshkruar në standardin ANSI X9.17, është një nga gjeneruesit më të sigurt kriptografikisht të numrave pseudo të rastësishëm. Aplikacionet që përdorin këtë teknologji përfshijnë sigurinë financiare dhe aplikacionet PGP.

Gjeneratori ANSI X9.17 përbëhet nga pjesët e mëposhtme (Figura 3):

1. Hyrja: Gjeneratori kontrollohet nga dy hyrje pseudo të rastësishme. Hyrja e parë është një paraqitje 64-bitëshe e datës dhe kohës aktuale ( DT i) që ndryshojnë sa herë që gjenerohet numri. Hyrja e dytë është një vlerë fillestare 64-bit, e cila inicializohet në një vlerë arbitrare dhe ndryshohet gjatë gjenerimit të një sekuence numrash pseudo të rastësishëm ( Vi).

2. Çelësat: Gjeneratori përdor tre module të trefishta DES me dy çelësa K 1 , K 2 . Të tre përdorin të njëjtin çift çelësash 56-bitësh, i cili duhet të mbahet sekret dhe të përdoret vetëm për të gjeneruar një numër pseudo të rastësishëm.

Oriz. 3. ANSI X9.17 gjenerues i numrave pseudo të rastësishëm

Regjistri i ndërrimit të reagimeve përbëhet nga dy pjesë: regjistri i ndërrimit dhe funksionet e reagimit.

Figura 19. Regjistri i zhvendosjes së reagimeve.

Në përgjithësi, një regjistër zhvendosjeje është një sekuencë e disa elementeve të një unaze ose fushe. Më së shpeshti përdoret pak regjistrat e ndërrimit. Gjatësia e një regjistri të tillë shprehet si një numër bitësh. Sa herë që merret një bit, të gjithë bitet në regjistër zhvendosen djathtas me një pozicion. Biti i ri më i rëndësishëm llogaritet si funksion i të gjithë biteve të tjerë në regjistër. Prodhimi është zakonisht biti më pak i rëndësishëm. Periudha e regjistrit të zhvendosjes është gjatësia e sekuencës së daljes përpara se të fillojë të përsëritet.

Lloji më i thjeshtë i regjistrave të ndërrimit është një regjistër linear i zhvendosjes së reagimit (LFSR ose LRS). Feedback-u është një operacion i thjeshtë XOR në disa pjesë të një regjistri. Lista e këtyre biteve është përcaktuar polinom karakteristik dhe thirri sekuenca e prekjes. Ndonjëherë kjo skemë quhet Konfigurimi Fibonacci.

Fig.20. LFOS i konfigurimit Fibonacci.

Në zbatimin e softuerit të LFSR, përdoret një skemë e modifikuar: për të gjeneruar një bit të ri të rëndësishëm, në vend që të përdoren bitet e sekuencës së trokitjes, kryhet një operacion XOR në secilin prej biteve të tij me daljen e gjeneratorit, duke zëvendësuar atë të vjetër. pak nga sekuenca e trokitjes. Ky modifikim nganjëherë quhet Konfigurimi Galois.

Fig.21. RLOS e konfigurimit Galois.

n-bit LFSR mund të jetë në një nga 2 n– 1 gjendje të brendshme. Kjo do të thotë se teorikisht një regjistër i tillë mund të gjenerojë një sekuencë pseudo të rastësishme me një periudhë prej 2 n– 1 bit (mbushja me zero është krejtësisht e padobishme). Kalimi i të gjitha 2 n– 1 gjendje të brendshme të mundshme vetëm me sekuenca të caktuara trokitjesh. Regjistra të tillë quhen LFSR me një periudhë maksimale. Për të siguruar periudhën maksimale të LFSR, është e nevojshme që polinomi i tij karakteristik të jetë primitive moduli 2. Shkalla e polinomit është gjatësia e regjistrit të zhvendosjes. Polinom i shkallës primitive n- është e tillë e pareduktueshme një polinom që është pjesëtues por nuk është pjesëtues x d+ 1 për të gjithë d, të cilët janë pjesëtues të 2 n– 1. (Kur diskutohet për polinomet, termi Numri kryesor zëvendësohet me termin polinom i pareduktueshëm). Polinomi karakteristik i LFSR i paraqitur në figura:

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

është modulo primitive 2. Periudha e një regjistri të tillë do të jetë maksimale, duke kaluar nëpër të gjitha vlerat 2 32 - 1 derisa ato të përsëriten. Më të përdorurit janë polinomet e holluar, d.m.th. të cilat kanë vetëm disa koeficientë. trinomet më të njohura.

Një parametër i rëndësishëm i gjeneratorit të bazuar në LFSR është kompleksiteti linear. Përcaktohet si gjatësia n LFSR-ja më e shkurtër që mund të simulojë daljen e gjeneratorit. Kompleksiteti linear është i rëndësishëm sepse me një të thjeshtë Algoritmi Berlenkamp-Masseyështë e mundur të rikrijoni një LFSR të tillë duke kontrolluar vetëm 2 n bit gama. Me përcaktimin e LFSR-së së dëshiruar, shifra e rrjedhës në të vërtetë prishet.

Krahas LFSR-së përdoren edhe regjistrat e ndërrimit me reagime jolineare, reagime transferuese etj.

Një numër gjeneratorësh janë zhvilluar në bazë të qasjes së teorisë së numrave (gjeneratorët Blum-Micali, RSA, BBS, gjeneratorët e kompresimit, aditivëve, etj.).

Mbështetja matematikore për sintezën e algoritmeve kriptografike rrjedhëse është zhvilluar më plotësisht dhe në detaje në krahasim me algoritmet kriptografike të bllokut. Sidoqoftë, për të krijuar shifra të transmetimit, shpesh përdoren algoritmet e shifrimit të bllokut në modalitetet OFB ose CFB.

Lloji më i thjeshtë i funksionit të reagimit është një funksion linear, siç është shuma modul 2 e përmbajtjes së biteve të caktuara. Një regjistër i tillë quhet Linear Feedback Shift Register (shkurt LFSR). Në rastin e përgjithshëm, funksioni i reagimit linear jepet me formulën . Këtu c k= 1 nëse k biti i th përdoret në funksionin e reagimit dhe c k= 0 ndryshe. Simboli Å qëndron për shtimin e modulit 2 (ekskluzive OR).

Për shembull, merrni parasysh një LFSR me një funksion reagimi (shih figurën).

Nëse gjendja fillestare e regjistrit është 1111, atëherë në ciklet pasuese do të marrë seritë e mëposhtme të gjendjeve: ...

Sekuenca e daljes formohet nga shifra më pak e rëndësishme (më e djathta) e regjistrit. Do të duket kështu: 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1. Mund të shihet se sekuenca e biteve të gjeneruara përcaktohet tërësisht nga gjendja fillestare e regjistrit dhe funksioni i reagimit. Meqenëse numri i gjendjeve të mundshme të regjistrit është i kufizuar (është i barabartë me 2 L), atëherë, herët a vonë, sekuenca kryesore do të fillojë të përsëritet. Gjatësia maksimale e një pjese që nuk përsëritet i një sekuence kyçe quhet perioda e saj. T. Periudha varet nga funksioni i reagimit. Periudha maksimale e mundshme është T max=2 L-1 (regjistri merr të gjitha gjendjet e mundshme përveç 0000...0). Quhet sekuenca e daljes së LFSR me periudhën maksimale M-sekuenca.

Për të gjetur kushtet në të cilat LFSR do të ketë periudhën maksimale, funksionet e reagimit përputhen me polinomin karakteristik . Pra, regjistri i dhënë më sipër si shembull korrespondon me polinomin . Analiza teorike tregon se LFSR do të ketë një periudhë maksimale nëse dhe vetëm nëse polinomi P(x) është primitive. Më poshtë janë disa polinome primitive të rekomanduara për përdorim praktik. Tabela tregon shkallët e ndryshores x në polinom. Për shembull, hyrja (31, 3) përputhet me polinomin .

LFSR-të fillimisht u krijuan për t'u zbatuar në harduer si një grup qarqesh dixhitale. Implementimet e softuerit të LFSR janë zakonisht më të ngadalta se implementimet harduerike. Për të rritur performancën, është e dobishme të ruhet gjendja e regjistrit si një numër i plotë L- numri i bitit, bitet individuale të të cilit korrespondojnë me shifrat binare të regjistrit. Pastaj operacionet bitwise (shift, masking, etj.) përdoren për të hyrë në bit individualë.