Algoritmii criptografici post-cuantici

Aceștia sunt algoritmi criptografici a căror securitate se bazează pe probleme dificile din teoria codurilor corectoare de erori, în special probleme precum syndrom decoding problem. Aceste probleme sunt considerate greu de rezolvat atât pentru calculatoarele clasice, cât și pentru cele cuantice. Algoritmii criptografici post-cuantici (PQC) sunt concepuți să reziste atacurilor conduse de computerele cuantice.

1. Introducere în Criptografia Post-Cuantică

Criptografia post-cuantică se referă la algoritmi criptografici care sunt considerați siguri împotriva atacurilor efectuate de computere cuantice, în special cele bazate pe algoritmul lui Shor (care poate sparge RSA, ECC și DSA) și algoritmul lui Grover (care reduce complexitatea forței brute).

2. Categorii Principale de Algoritmi Post-Cuantici

A. Criptografie Bazată pe Rețele (Lattice-based Cryptography)

Aceasta este una dintre cele mai promițătoare direcții în PQC, bazată pe probleme matematice legate de rețelele lattices (structuri geometrice în spații multidimensionale).

Algoritmi notabili:

• Kyber: Un algoritm de criptare hibridă (KEM – Key Encapsulation Mechanism) selectat de NIST în 2022 pentru standardizare.
• Dilithium: Folosit pentru semnături digitale, alt finalist NIST.
• NTRU: Un algoritm mai vechi, dar rezistent la atacuri cuantice.

Problema greu de rezolvat pe care se bazează:

• Learning With Errors (LWE) și variantele sale (Ring-LWE, Module-LWE).

B. Criptografie Bazată pe Coduri (Code-based Cryptography)

Acești algoritmi utilizează teoria codurilor corectoare de erori pentru a asigura securitatea.

Algoritmi notabili:

• McEliece: Un sistem de criptare bazat pe coduri Goppa, rezistent la atacuri cuantice de decenii.
• Classic McEliece: O variantă modernizată, finalist NIST.

Problemă greu de rezolvat:

• Decodificarea unor cuvinte aleatoare într-un cod liniar (NP-hard).

C. Criptografie Bazată pe Multivariate Quadratic Equations (MQ-based)

Acești algoritmi se bazează pe dificultatea rezolvării sistemelor de ecuații polinomiale multivariabile.

Algoritmi notabili:

• Rainbow: Un algoritm de semnătură digitală, finalist NIST.
• GeMSS: Alt candidat pentru semnături digitale.

Problema greu de rezolvat:

• Rezolvarea sistemelor de ecuații peste câmpuri finite (MQ-problem).

D. Criptografie Bazată pe Izogenii (Isogeny-based Cryptography)

Folosește proprietăți ale curbelor eliptice și ale hărților între ele (izogenii) pentru a crea chei securizate.

Algoritmi notabili:

• SIKE (Supersingular Isogeny Key Encapsulation): A fost un candidat important, dar a fost spart în 2022, demonstrând riscurile acestei abordări.

Problemă greu de rezolvat:

• Găsirea unei izogenii între două curbe supersingulare (Problemă a izogeniei supersingulare).

E. Criptografie Bazată pe Hash (Hash-based Cryptography)

Folosește funcții hash criptografice pentru a construi scheme de semnături digitale.

Algoritmi notabili:

• SPHINCS+: Un algoritm de semnătură digitală fără stare (stateless), standardizat de NIST.
• XMSS: Un alt algoritm bazat pe hash-uri, dar necesită gestionarea stării.

Problemă greu de rezolvat:

• Rezistența la coliziuni și preimagine a funcțiilor hash.

3. Standardizarea NIST (2022-2024)

NIST a selectat următorii algoritmi pentru standardizare:

4. Avantaje și Dezavantaje

Criptografia post-cuantică reprezintă viitorul securității informatice, iar algoritmii bazati pe rețele (lattice) și coduri par să fie cei mai promițători. NIST continuă să evalueze noi scheme, iar în următorii ani vom vedea o migrare treptată de la RSA/ECC către aceste soluții rezistente la atacuri cuantice.

Algoritmul lui Shor

Algoritmul lui Shor este un algoritm cuantic care poate factoriza numere întregi în timp polinomial, reprezentând o amenințare majoră pentru sistemele criptografice clasice precum RSA și ECDSA. Iată o explicație detaliată a funcționării sale:

1. Context și Importanță

• Scop: Factorizarea eficientă a unui număr compus NN în produs de numere prime (e.g., N=p×qN=p×q).
• Impact: Sparge RSA, deoarece securitatea lui RSA se bazează pe dificultatea factorizării numerelor mari.

2. Pașii Algoritmului lui Shor

Algoritmul are două părți principale:

1. Partea clasică: Reduce problema factorizării la găsirea perioadei unei funcții.
2. Partea cuantică: Folosește Transformata Fourier Cuantică (QFT) pentru a găsi perioada eficient.

A. Partea Clasică

1. Alegerea unui număr aleator:
   • Alege un întreg a (unde 1<a<N) care este coprim cu N (adică cmmdc(a,N)=1).
   • Dacă cmmdc(a,N)≠1cmmdc(a,N)=1, am găsit deja un factor al lui NN.
2. Definirea funcției periodice:
   • Consideră funcția f(x)=axmod  Nf(x)=axmodN.
   • Această funcție este periodică (există un r astfel încât f(x+r)=f(x)).
3. Găsirea perioadei r:
   • Dacă r este par și ar/2≠−1mod  N, atunci:
     • cmmdc(ar/2+1,N) și cmmdc(ar/2−1,N) sunt factori non-triviali ai lui NN.
   • Exemplu: Pentru N=15 și a=7:
     • r=4 (deoarece 74mod15=1).
     • cmmdc(72+1,15)=cmmdc(50,15)=5.

B. Partea Cuantică (Găsirea lui rr cu QFT)

Aici intervine calculul cuantic pentru a găsi perioada rr rapid:

1. Crearea unei superpoziții:
   • Un registru cuantic este inițializat într-o superpoziție egală a tuturor valorilor posibile xx.
2. Calculul f(x)=axmodN:
   • Se aplică o transformare cuantică care mapează ∣x⟩∣0⟩∣x⟩∣0⟩ la ∣x⟩∣f(x)⟩∣x⟩∣f(x)⟩.
3. Măsurarea celui de-al doilea registru:
   • Colapsează starea cuantică într-o superpoziție a tuturor x cu aceeași f(x).
4. Aplicarea Transformatei Fourier Cuantice (QFT):
   • QFT transformă superpoziția periodică într-o stare unde rr (perioada) poate fi măsurată direct.
5. Extragerea lui r:
   • Măsurarea registrului cuantic oferă o valoare din care rr poate fi dedusă clasic (folosind algoritmul lui Euclid).

3. De ce este eficient?

• Clasic: Cel mai bun algoritm cunoscut (General Number Field Sieve) rulează în timp sub-exponențial.
• Cuantic: Algoritmul lui Shor rulează în timp polinomial (O((log⁡N)3)O((logN)3)), datorită QFT și paralelismului cuantic.

4. Limitări și Provocări

• Erori cuantice: Calculatoarele cuantice actuale (NISQ) sunt prea zgomotoase pentru a rula Shor la scară mare.
• Dimensiunea numărului: Pentru NN-uri foarte mari (e.g., 2048 biți), sunt necesare qubiți de înaltă calitate.

5. Exemplu Simplu

Factorizarea lui N=15N=15:

1. Alegem a=7 (coprim cu 15).
2. Găsim r=4 (deoarece74mod15=1).
3. Calculăm cmmdc(72±1,15):
   • cmmdc(49−1,15)=cmmdc(48,15)=3.
   • cmmdc(49+1,15)=cmmdc(50,15)=5.
4. Obținem factorii 33 și 55.

6. Concluzie

Algoritmul lui Shor demonstrează superioritatea cuantică în problema factorizării, motiv pentru care criptografia post-cuantică (PQC) este urgent necesară. Schemele bazate pe rețele (lattice) sau coduri corectoare de erori sunt alternative rezistente la Shor.

Documentație

Iată o listă de cărți recomandate care acoperă algoritmii criptografici post-cuantici (PQC), inclusiv fundamentele matematice, implementări și standardizări:

1. Cărți Generale despre Criptografia Post-Cuantică

(A) Post-Quantum Cryptography

• Autor: Daniel J. Bernstein, Johannes Buchmann, Erik Dahmen
• Ediție: Springer (2009)
• Conținut:
  • Introducere în PQC, atacurile cuantice, și principalele categorii de algoritmi (lattice-based, code-based, hash-based, etc.).
  • Analiză teoretică și comparații între scheme.

(B) Quantum Computing and Post-Quantum Cryptography

• Autor: Brian Chen
• Ediție: Self-published / Amazon (2022)
• Conținut:
  • Explică impactul calculatoarelor cuantice asupra criptografiei clasice.
  • Prezintă algoritmi PQC cu exemple practice.

2. Criptografie Bazată pe Rețele (Lattice-based)

(A) Lattice-Based Cryptography

• Autori: Vadim Lyubashevsky, Chris Peikert, Oded Regev
• Disponibil: Articole academice + capitole în cărți de criptografie
• Conținut:
  • Fundamentele problemei LWE (Learning With Errors) și aplicații în Kyber, Dilithium.

(B) Advances in Lattice-Based Cryptography

• Editor: Özgür Dagdelen (2023)
• Conținut:
  • Evoluții recente în algoritmii bazati pe rețele și optimizări.

3. Criptografie Bazată pe Coduri (Code-based)

(A) Code-Based Cryptography

• Autor: Raphael Overbeck, Nicolas Sendrier
• Ediție: Springer (2009)
• Conținut:
  • Detalii despre McEliece, Niederreiter, și securitatea lor.

(B) Post-Quantum Cryptography: Code-Based Signatures

• Autor: Edoardo Persichetti
• Disponibil: Articole + prelegeri universitare
• Conținut:
  • Focus pe semnături digitale bazate pe coduri (e.g., Wave, Stern).

4. Criptografie Bazată pe Hash (Hash-based)

(A) Hash-Based Digital Signature Schemes

• Autor: Andreas Hülsing
• Ediție: Springer (2013)
• Conținut:
  • Explică SPHINCS+, XMSS, și construcția arborilor Merkle.

(B) Quantum-Resistant Cryptography

• Autor: Mikhail J. Atallah
• Ediție: Wiley (2021)
• Conținut:
  • Comparație între hash-based și alte abordări PQC.

5. Cărți Avansate și Standarde NIST

(A) NIST PQC Standardization Documentation

• Disponibil: nist.gov/pqcrypto
• Conținut:
  • Specificațiile oficiale pentru Kyber, Dilithium, SPHINCS+, etc.

(B) Post-Quantum Cryptography for Developers

• Autor: Rafael Misoczki (2023)
• Conținut:
  • Implementări practice în Python/C, focus pe API-uri și librării (e.g., liboqs).

6. Cărți în Limba Română (Dacă sunt Disponibile)

• „Criptografia în Era Cuantică” (dacă există traduceri sau lucrări autohtone).
• Cursuri universitare de la Universitatea București/Cluj pot avea materiale în română.

7. Resurse Online Gratuite

1. „A Decade of Lattice Cryptography” (Chris Peikert) – Disponibil PDF gratuit.
2. Cursuri Coursera/edX:
   • „Quantum Cryptography” (University of Maryland).
   • „Post-Quantum Cryptography” (KU Leuven).

Recomandare Finală

Dacă vrei o introducere accesibilă, începe cu:

1. „Post-Quantum Cryptography” (Daniel Bernstein).
2. Documentația NIST.

Pentru implementări practice:

• „Programming Bitcoin” (Jimmy Song) – Are capitole despre PQC.