Este fezabil să construim o întreagă ramură a criptografiei pe o familie de surse pseudo-aleatoare?
În teorie, da. Dacă a existat un generator de numere pseudoaleatoare, eficient și sigur din punct de vedere criptografic, construit dintr-un sistem haotic, care ar putea servi ca fundament pentru o criptografie simetrică rezonabil de practică și chiar pentru semnătură.
Problema este că nu știm așa ceva. PRNG-urile construite dintr-un sistem haotic și care au un argument de securitate chiar ușor convingător¹, palid în eficiență în comparație cu un CSPRNG modern² (cu excepția cazului în care extindem definiția „sistemului haotic” cu mult dincolo de funcțiile continue obișnuite iterate peste $\mathbb R$, sau aproximări discrete ale acestora).
Un generator de numere pseudoaleatoare (securizat din punct de vedere criptografic), în el definiție modernă, este un instrument suficient de puternic pentru a construi toate celelalte funcționalități de criptare simetrică: CPA și CCA(2)-cifr securizat, cifru bloc, Cod de autentificare a mesajului, criptare autentificată, hash⦠Câteva exemple:
- Un cifr poate fi construit dintr-un (CS)PRNG folosind cheia și un IV aleatoriu cu adevărat pentru a genera PRNG și construind textul cifrat prin XOR al ieșirii PRNG cu textul simplu.Securitatea decurge direct din cea a PRNG și aceasta este o modalitate atât de bună și comună de a construi un cifr, încât are un nume: stream cipher.
- Un cifru bloc poate fi construit dintr-un PRNG ca a Cifrul Feistel, folosind PRNG pentru a construi funcțiile rotunde. Cheia, numărul rotund și jumătatea dreaptă a blocului generează PRNG, a cărui ieșire este valoarea XOR cu jumătatea stângă.
Aceste construcții sunt în mod demonstrabil criptografic sigur dacă PRNG este. Dar, cu excepția cifrurilor de flux, acestea nu sunt utilizate în practică, în primul rând din motive de eficiență. CSPRNG obișnuite sunt construite din cifruri bloc sau/și hash-uri, mai degrabă decât invers.
Este fezabil să construiești primitive criptografice cu cheie publică din PRNG?
Da pentru semnătură. Putem construi hash securizat din PRNG securizat, apoi semnătură securizată din hash, prin diverse abordări, inclusiv SPHINCS. Pe această cale, orice PRNG eficient duce la o schemă de semnătură plauzibilă.
Pentru criptare și schimb de chei, mă îndoiesc că este cunoscută o metodă cu o dovadă de securitate sau chiar un argument convingător. Nu sunt convins de încercările de a construi criptare asimetrică din sisteme haotice continue pe căi mai directe...
¹ Nu putem cere o dovadă în sens matematic, deoarece nu avem o astfel de dovadă de securitate pentru niciun CPRNG. Dar nu vrem să acceptăm ca argument de securitate faptul de a trece un test de aleatorietate predefinit, cum ar fi NIST SP800-22rev1a sau mai tare. Un test experimental ar trebui să fie cel puțin: imposibilitate pentru criptografi umani pricepuți cunoscând proiectarea PRNG-ului, asistat de calculatoare clasice, pentru a distinge de aleatorietatea reală rezultatul PRNG însămânțat cu aleatorie adevărată. Și am dori să extindem asta la o astfel de imposibilitate începând cu o valoare minimă a anumitor parametri ai PRNG, cum ar fi dimensiunea stării sau/și numărul de runde, cu parametrii utilizați efectiv setați confortabil mai mari.
² Cum ar fi cel derivat din ChaCha considerând cheia și IV-ul ca fiind sămânța și textul simplu nu.
³ Decriptarea este similară cu schimbul de text simplu și ciphertext, cu excepția faptului că criptarea atrage IV-ul și îl face un preambul al textului cifrat, în timp ce decriptarea extrage IV-ul din preambul.
â´ Unul astfel atentat, încercare utilizări (paywalled). Polinoamele Cebyshev $T_r$ de mare grad $r$. O cheie privată este $r$, cheia publică corespunzătoare este $T_r(x)$ pentru unele fixe publice alese aleatoriu real $x\în[-1,1]$. Pentru orice număr întreg $s>0$ tine $T_r(T_s(x))=T_s(T_r(x))$ și (ignorând problemele legate de modul în care este calculat) care permite un analog al Schimb de chei Diffie-Hellman, și din asta Criptare ElGamal. Când l-am citit prima dată, am rămas neconvins de afirmația fără argumentare a securității, precum și de unele aspecte ale fezabilității (de exemplu, că, cu 2048 de biți de precizie pentru valori reale, numerele întregi $r$ și $s$ pot fi alese ca numere întregi aleatoare de 910 de biți, mai degrabă decât ca produs de numere prime de cel mult 133 ca în articol).
Actualizare: sa constatat că criptosistemul este nesigur, vezi asta articol (paywalled). Este încă prezentat în asta capitolul Criptografia cu cheie publică (paywalled) într-un timp mult mai târziu carte despre criptografia bazată pe haos (paywalled), cu recunoașterea nesiguranței. Mi se pare grăitor despre starea acelui domeniu academic. Și asta este cel mai bun: majoritatea pretențiilor de securitate, făcute cu argumente relativ slabe, nu sunt niciodată investigate serios și dovedite că sunt greșite.
