Ce sunt reducerile de securitate ale algoritmilor cu cheie simetrică?

Citeam pagina Wikipedia de criptografie post-cuantică. Se spune că este de dorit ca algoritmii criptografici să fie reducțibili la o anumită problemă matematică, adică insolubilitatea sistemului ar trebui să decurgă în principal din duritatea unei probleme matematice.

De exemplu, criptografia bazată pe zăbrele, sistemul Diffie-Hellman, RSA, McEliece, criptografia multivariată reduce la cea mai scurtă problemă vectorială, problema logaritmului discret, factorizarea întregului, problema de decodificare a sindromului, respectiv problema de rezolvare a ecuațiilor pătratice multivariate.

Nu am putut vedea exemple de algoritmi cu cheie simetrică. De ce este asta? Presupun că nu au nevoie de această proprietate din cauza naturii criptografiei cu chei simetrice?

Este pentru că, deoarece nu este o cheie publică de criptare, nu este necesară asimetria și, prin urmare, nu este nevoie de un sistem ușor de criptat, greu de decriptat, care se traduce într-o funcție unidirecțională, care este greu de inversat din cauza matematicii din spatele lui?

multumesc pentru raspunsuri, a fost de ajutor.

Nu am putut vedea exemple de algoritmi cu cheie simetrică. dar de ce?

Există mai multe moduri posibile de a răspunde la aceasta; cel mai simplu este acel algoritm cheie simetrică sunt pe baza unor probleme matematice specifice (de obicei nu o exprimăm așa).

Pentru a lua câteva exemple de algoritmi asimetrici:

de exemplu ... diffie-hellman, rsa ... reduce la ... problema logaritmului discret, factorizarea întregului ... respectiv.

Este incorect; dacă vi se oferă un Oracle care poate sparge Diffie-Hellman, nu există nicio modalitate cunoscută de a-l folosi pentru a rezolva probleme de jurnal discret; dacă vi se oferă un Oracle care poate rupe RSA, nu există nicio modalitate cunoscută de a-l folosi pentru factor.

În schimb, ceea ce se reduce Diffie-Hellman este cunoscut sub numele de „problema Diffie-Hellman” (din punct de vedere tehnic, fie cDH, fie dDH, în funcție de ceea ce face Oracle); la ce se reduce RSA se numește „problema RSA”.

Acum, care este diferența dintre „problema Diffie-Hellman” sau „problema RSA” și „problema AES”? În afară de faptul că „problema AES” durează mai mult pentru a descrie și se simte mai arbitrară, nu văd una (și cu siguranță „problema AES” a fost destul de bine studiată). Și, dacă folosim AES într-un anumit mod, există în general o dovadă că securitatea modului se reduce la „problema AES”, prin urmare, acesta nu este doar un joc de cuvinte prostesc.

Un alt mod de abordare a întrebării (dacă insistăm asupra „probleme matematice simple” ca o modalitate de descalificare a „problemei AES”) este să observăm că știm despre primitive simetrice care se reduc la probleme simple matematice; cu toate acestea, acele primitive rulează, în general, mult mai încet (și au, de obicei, texte cifrate mult mai mari) decât ceea ce folosim în practică, și deci nu le folosim niciodată, mai ales că nu cunoaștem nicio dovadă că „problema matematică simplă” este de fapt mai dificilă. decât „problema matematică complexă” pe care o folosim în practică.

Se poate întoarce acest lucru și se poate întreba „de ce insistăm să ne bazăm algoritmii asimetrici pe probleme dificile specifice?”. Un răspuns este că algoritmii asimetrici încearcă să facă mai mult decât un algoritm simetric; nu numai că un algoritm asimetric trebuie să arate „aleatoriu”, dar trebuie să fie în continuare securizat chiar dacă atacatorului i se oferă un indiciu sub forma unei chei publice. Această cheie publică trebuie să fie legată cumva de cheia privată, dar nu într-un mod evident (și, desigur, operațiunile care sunt ușoare având în vedere cheia privată trebuie să fie imposibil de realizat având în vedere doar cheia publică). Singurul mod în care știm că avem o relație atât de obscură implică reducerea acesteia la o problemă mai simplă și grea.

În măsura în care există reduceri de securitate în criptografia simetrică, acestea tind să se aplice construcțiilor care utilizează primitive idealizate, cum ar fi un funcţie pseudo-aleatorie sau a permutare pseudo-aleatorie. Astfel, de exemplu, Luby și Rackoff au demonstrat că este posibil să se construiască o permutare pseudo-aleatoare dintr-o funcție pseudo-aleatoare folosind o construcție Feistel cu trei runde. De asemenea, criptografii simetrici ar putea încerca să demonstreze că un mod de operare cu cifrare în bloc extinde o permutare pseudo-aleatoare a dimensiunii blocului la o permutare pseudo-aleatoare pe o bucată mai mare de date.

Apoi, asigurarea vine din credința că primitivele simetrice pe care le folosim se pot distinge de omologii lor idealizați pseudo-aleatoriu. Dacă există mai multă asigurare în afirmația „ruperea acestei construcții este la fel de greu ca să distingeți SHA256 de o funcție pseduo-aleatorie” sau „ruperea acestui construct este la fel de greu pe cât problema decizională Diffie-Hellman din acest grup” depinde de consumator.