În criptografie. (. Engl construcție burete sau funcție burete) burete funcția se referă la o clasă de algoritmi cu o stare internă finită, intrarea care primește un șir binar de lungime arbitrară, și care returnează, de asemenea, un șir binar de lungime arbitrară f: ^ n → ^ *. Burete este o generalizare a ambelor funcții hash. și fluxul și blocarea cipurilor, generatoare de numere pseudo-aleatoare având lungimea arbitrară a datelor de intrare.
Un burete este o construcție iterativă pentru a crea o funcție cu o lungime arbitrară la intrare și o lungime de ieșire arbitrară bazată pe transformările f. Buretele are o stare internă S - cu date de dimensiune fixă b (bit). În acest caz, datele sunt împărțite în două părți - primul S1 al dimensiunii r, iar cel de-al doilea S2 - al dimensiunii c. Valoarea r este numită rata de biți, iar valoarea lui c este puterea => b = r + c.
În faza de inițializare, blocul de date cu mărimea b este umplut cu zerouri, iar datele de intrare ale lui M sunt împărțite în blocuri de mărime r. Lucrarea ulterioară a buretelui se desfășoară în două etape:
- In faza de „fitil» (absorbant), o operațiune a XOR blocul următor mesajului original de marimea partea S1 r primul stat (bit), porțiunea rămasă S2 starea rămâne capacitate neafectat c. Rezultatul este plasat in S1, iar apoi procesat de stat S f - keyless pseudoaleatoare permutare multi-rotunde, și așa mai departe se repetă până când toate blocurile de mesaje originale.
- În faza de "stoarcere", starea S este alimentată la funcția f, după care partea S1 este trimisă la ieșire. Aceste acțiuni sunt repetate până când se obține o secvență de lungime dorită (de exemplu, lungimea hash-ului).
Ultimii biți c depind în mod indirect de blocurile de intrare și nu sunt emise în timpul fazei de "stoarcere".
5. Generator de numere pseudo-aleatoare bazat pe funcția de burete 5.1. Modelarea GPRS cu date de intrare variabile
Definiți un GPRCH cu date sursă variabile ca obiect cu o stare care acceptă două tipuri de interogări, în orice ordine:
- Cerere de depunere. feed (σ) - dă valoarea inițială, constând dintr-un șir neempted σ ε Z 2 + ^>. în starea GPRS;
- Solicitați acceptarea, preluați (l) - instruiește RANDOM să returneze l biți.
Apoi materialul de însămânțare alimentat la intrarea generatorului este concatenarea σ obținută în toate cererile de alimentare.
În mod informal, cerințele pentru un GPRS cu date sursă variabile pot fi definite după cum urmează:
În primul rând, producția sa (adică răspunsurile la cererile de depunere) ar trebui să depindă de toate materialele sursă. În al doilea rând, pentru un atacator care nu cunoaște materialul sursă, dar observă o parte a producției, ar trebui să fie imposibil să se deducă partea rămasă din producție.
Definiți idealul GPRS ca un design folosind un oracle aleator.
Răspunsul unui GPRS ideal cu intrare variabilă la cererea de acceptare
Construcția pe care am definit-o poate fi descrisă după cum urmează. Se salvează ca stare succesiunea tuturor cererilor de depunere și de acceptare pe care le-a primit, făcând povestea h. Când se primește o solicitare de alimentare (σ), aceasta actualizează istoricul prin conectarea acestei solicitări. La primirea acceptarea cerere fetch (l), este nevoie de linia Oracle aleatoare, care, la rândul său, criptează și returnează biții de istorie șir de la Z la Z + L-1 a răspunsului său, în care z - numărul de biți solicitat în cererea de depunere. Prin urmare, concatenarea răspunsurilor la cererile de feed este doar un răspuns oracle aleatoriu la o singură interogare. Acest lucru este demonstrat în figură. Noi numim această construcție un mod care păstrează istoria, cu funcția de criptare e (h). Definiția unui mod cu păstrarea istoriei, prin urmare, converge la definiția acestei funcții de criptare.
pentru că ieșirea PGNCH trebuie să depindă de întregul material sursă rezultat, funcția de criptare e (h) trebuie să fie injectabilă cu materialul sursă. Cu alte cuvinte, pentru oricare două secvențe de interogări cu material sursă diferit, cele două hărți e (h) trebuie să fie diferite. Noi numim aceasta completitudinea materialului original (seminte-completitudine). În funcția de criptare cu material sursă completă, la cererea de acceptare vor fi oferite răspunsuri diferite la diferite linii de intrare. Rezultă că GPRS returnează biți independenți.
Astfel, se propune următoarea definiție a unui GPRCH ideal cu date de intrare variabile.
PSTN-ul ideal cu date de intrare variabile este un mod care păstrează istoricul, numit un oracol aleatoriu, cu funcția de criptare e (h) cu materialul sursă integrală.
5.2. Crearea GPRS utilizând funcția unui burete
Pare natural să includeți o cerere de alimentare în faza de "înmuiere" și o cerere de acceptare în faza "stoarcere". Cu toate acestea, funcția buretele de execuție are doar o singură fază de absorbție (o intrare), care este urmată de o fază de „stoarcere“ (adică, o ieșire de lungime arbitrară), și nu poate fi folosit pentru a produce mai multe etape.
Evident, această dificultate este ușor de ocolită. Este suficient să presupunem că de fiecare dată când sunt primite biți pseudo-aleatori, este necesară o altă execuție a funcției burete cu o intrare diferită.
La construirea funcției burete, mesajul de intrare m e Z 2 * ^> ar trebui împărțit în blocuri de biți r și umplut. Fie ca p (m) funcția care face acest lucru și presupunem că această funcție adaugă numai biții după m. Să presupunem că vrem să reutilizăm starea buretelui, pentru care linia de intrare a fost mesajul m1 și pentru care biții de ieșire au fost "stoarși" pentru l> 0. Starea funcției burete în acest punct este ca și cum mesajul parțial m'1 = p (m1) || 0 r (⌈l / rûnd-1) a fost "absorbit". Rețineți că blocurile zero reprezintă iterații suplimentare datorate fazei de compresie. Repornirea buretei din acest punct înseamnă că mesajul de intrare este m2, pentru care m'1 este prefix.
Pentru a defini în mod formal un GOSM, trebuie să specificăm funcția de criptare e (h) cu materialul sursă integrală, care afișează secvența de cereri de depunere și acceptare. Ieșirea e (h) este utilizată ca intrare pentru funcția buretelui.
În practică, ideea nu este de a numi funcția burete cu toate e (h) de fiecare dată când primim cererea de primire. În schimb, designul folosește funcția burete într-o manieră cascadă, reutilizând starea, așa cum este descris în secțiunea 3.2. Pentru a permite reutilizarea stării funcției burete e (h), trebuie să existe astfel încât, dacă h '= h || aduceți (l) || furajul (σ), apoi p (e (h)) || 0 r (⌈l / r dint-1) este prefixul e (h ').
Pentru a raporta construcția la implementarea practică, vom descrie construcția cu două constrângeri pentru a începe. Prima restricție privind lungimea cererilor pentru valoarea inițială. Pentru un număr întreg fix k, este necesar ca lungimea materialului inițial σ în orice cerere de alimentare (σ) să fie de așa natură încât | p (σ) | = kr. Cu alte cuvinte, după umplere, materialul sursă acoperă exact k blocurile de biți r. A doua limitare este că prima cerere trebuie să fie o cerere de alimentare.
Construcția este o stare statală dacă starea ei constă în m biți N primiți de la ultima cerere de alimentare. Să începem cu noua execuție a funcției burete, setați m = 0. Să desemnăm e ca un șir, afișând e (h) de interogări adăugate la istoria h.
-Dacă interogarea este preluată (l):
Executarea produce biți de ieșire, "stoarcându-i" din funcția de burete. Formal, va fi adaptat în timpul următoarei solicitări de alimentare.
Valoarea lui m se modifică: m = m + l.
-Dacă feedul de solicitare (σ):
Apoi "se absoarbe" σ. Formal, acest lucru este exprimat prin adăugarea lui σ la e.
În cele din urmă, execuția comută funcția burete în faza "stoarcere". Aceasta înseamnă că datele "înmuiate" trebuie umplete, iar permutarea f este aplicată statului. (Formal, acest lucru nu se schimba e, deoarece umplerea prin definiție este efectuată la trecerea la faza de rotație).
Limitarea dimensiunii fixe a cererilor de depunere nu este obligatorie și poate fi eliminată. Pentru a asigura o lungime variabilă a materialului sursă și pentru a păstra integralitatea materialului sursă, trebuie introduse anumite forme de umplere în cadrul funcției de criptare pentru a se asigura că limitele materialului sursă pot fi identificate. În plus, va trebui să adăugați o modalitate de a distinge blocurile cu materialul sursă zero de blocurile zero. Aceasta se poate face, de exemplu, prin setarea 1 în fiecare bloc care conține materialul de pornire.
Limitarea primei cereri, care este o cerere de feed, poate fi ștearsă, deoarece Nu are sens să se genereze biți pseudo-aleatorii fără a se furniza mai întâi materialul sursă. Dacă prima cerere este acceptabilă, execuția umple imediat intrarea (linia goală), comută funcțiile de burete în faza "squeeze" și produce biți de ieșire utilizând "stoarcere". Formal în următoarea cerere de depunere, acest lucru trebuie luat în considerare în cesiunea e a valorii p (șir gol) || 0 r ([m = r] -1).
Articole similare
Trimiteți-le prietenilor: