Criptografie cu cheie asimetrică

În această lecție vom explora criptografia cu cheie asimetrică, care stă la baza multor interacțiuni de rețea securizate din ziua de azi.

Până la sfârșitul lecției, vom fi acoperit:

• Ce este criptografia cu cheie asimetrică
• Utilizările criptografiei cu cheie asimetrică, inclusiv schimbul de chei și semnăturile digitale
• Securitatea criptografiei cu cheie asimetrică în general
• Detalii suplimentare despre algoritmii RSA, DSA și Curbe Eliptice și securitatea lor
• Câteva exemple de cod Python care arată cum funcționează algoritmii în practică
• Amenințări la adresa acestor algoritmi atât din partea calculatoarelor clasice, cât și a celor cuantice

Introducere în criptografia cu cheie asimetrică

Așa cum am aflat în lecția precedentă, criptografia cu cheie simetrică este foarte rapidă și eficientă pentru protejarea informațiilor, dar are câteva limitări:

1. Pe măsură ce numărul de părți care doresc să facă schimb de informații securizate crește, numărul de chei necesar crește combinatorial. Nu există niciun mecanism de distribuire securizată a acestor chei între expeditori și destinatari.
2. Nu există nicio prevedere pentru non-repudiere. Orice parte poate decripta sau cripta mesaje, fără nicio modalitate de a garanta că un mesaj a fost primit sau de unde a provenit.

Soluția la ambele probleme este oferită de criptografia cu cheie asimetrică (AKC), cunoscută și sub denumirea de criptografie cu cheie publică (PKC), care formează astfel o piatră de temelie a securității digitale moderne.

Criptografia cu cheie asimetrică (AKC) implică utilizarea unei perechi de chei — una publică, una privată. Cheia publică și cea privată sunt legate criptografic și sunt generate de obicei în același timp ca o pereche de chei, folosind un algoritm matematic specializat. Cheia publică, după cum sugerează și numele, este menită să fie distribuită liber, în timp ce cheia privată este păstrată secretă de către partea care a generat perechea de chei. Securitatea comunicațiilor care utilizează perechi de chei asimetrice este asigurată atâta timp cât cheia privată rămâne confidențială.

Figura 1. Criptare cu cheie asimetrică

AKC oferă mai multe funcții utile, cum ar fi:

1. Criptare și decriptare pentru a asigura confidențialitatea comunicațiilor.
2. Semnături digitale pentru a garanta autenticitatea, integritatea și non-repudierea.
3. Schimb securizat de chei pentru a facilita utilizarea ulterioară a criptosistemelor simetrice.

În aplicațiile moderne, AKC este utilizat în principal pentru semnături digitale și schimb securizat de chei. În această lecție, prezentăm aceste două funcții cheie, apoi discutăm mai multe variante de protocoale criptografice pentru aceste funcții.

Schimbul de chei cu criptografia cu cheie asimetrică

Una dintre problemele fundamentale în criptografie este schimbul securizat de chei. De exemplu, dacă două părți doresc să utilizeze criptarea simetrică, ambele au nevoie de aceeași cheie pentru a cripta și decripta mesajele. Dar cum fac schimbul securizat al cheii? Criptografia cu cheie asimetrică abordează această problemă prin mecanisme de schimb de chei interactive și non-interactive.

Schimb de chei interactiv

Un protocol de schimb de chei interactiv se referă la o metodă prin care două părți colaborează pentru a crea o cheie secretă partajată printr-un canal de comunicație nesecurizat. Această cheie secretă partajată poate fi apoi utilizată pentru sarcini de criptare și decriptare simetrică.

Cel mai cunoscut dintre astfel de protocoale este algoritmul Diffie-Hellman (DH), conceput special pentru a facilita schimbul de chei. În acest protocol, fiecare parte generează o pereche de chei (publică și privată) și transmite cheia sa publică. Apoi, fiecare parte utilizează propria cheie privată și cheia publică a celeilalte părți pentru a genera o cheie secretă partajată. DH folosește principiile aritmeticii modulare pentru a garanta că ambele părți ajung la același secret partajat, chiar dacă fiecare parte are acces doar la cheia publică a celeilalte.

Criptosistemele moderne bazate pe criptografia cu curbe eliptice (ECC) extind acest concept cu schimbul de chei Diffie-Hellman pe curbe eliptice (ECDH). ECDH funcționează similar cu DH, dar utilizează proprietățile curbelor eliptice, rezultând un sistem mai sigur și mai eficient.

Figura 2. Protocol de schimb de chei

Schimb de chei non-interactiv

Spre deosebire de protocoalele de schimb de chei precum DH și ECDH, care sunt interactive și necesită comunicare în ambele sensuri pentru a determina cheia simetrică, AKC oferă și modalități non-interactive de a stabili o cheie secretă partajată. În astfel de scheme, o parte generează o pereche de chei (publică și privată) și partajează cheia publică cu cealaltă parte. Cea de-a doua parte generează apoi o cheie simetrică aleatorie, o criptează cu cheia publică primită și o trimite înapoi primei părți. Prima parte utilizează cheia sa privată pentru a decripta mesajul primit, obținând astfel cheia simetrică partajată. Această schemă este non-interactivă în sensul că cheia simetrică este determinată de o singură parte și pur și simplu comunicată în mod securizat celeilalte părți în formă criptată.

O considerație importantă în schimbul de chei non-interactiv ține de diferența în biți dintre cheia simetrică pe care părțile doresc să o schimbe și dimensiunile de mesaj recomandate în AKC. De obicei, cheile simetrice moderne au între 128-256 biți, în timp ce criptosistemele cu cheie asimetrică precum RSA lucrează cu dimensiuni de mesaj de aproximativ 1024-4096 biți. Prin urmare, atunci când se utilizează AKC pentru a transmite o cheie simetrică, aceasta trebuie totuși codificată într-un mesaj mai lung de 1024-4096 biți. Acest lucru poate fi realizat prin două abordări:

• Schimb de chei bazat pe padding: În această abordare, cheia simetrică mai scurtă (128-256 biți) este generată mai întâi, iar apoi o schemă de padding reversibilă convenită, cum ar fi OAEP, este utilizată pentru a o încorpora într-un mesaj mai lung (1024-4096 biți). Acest mesaj mai lung este criptat folosind AKC și transmis ca text cifrat. Destinatarul decriptează mai întâi textul cifrat, apoi elimină padding-ul pentru a extrage cheia simetrică mai scurtă.

• Mecanisme de încapsulare a cheilor (KEM): Cu schimbul de chei bazat pe KEM, se generează mai întâi un mesaj în text clar aleatoriu și lung (1024-4096 biți), din care o cheie simetrică mai scurtă (128-256 biți) poate fi extrasă folosind o funcție de derivare a cheilor (KDF) convenită. Textul clar mai lung este criptat folosind AKC și transmis destinatarului ca text cifrat. Destinatarul decodifică textul cifrat folosind cheia sa privată și apoi utilizează KDF pentru a extrage cheia simetrică mai scurtă (128-256 biți). Criptosisteme populare precum RSA, cu capacitatea lor de a cripta direct date, pot fi folosite pentru a implementa KEM-uri.

Figura 3. Mecanism de încapsulare a cheilor

Semnături digitale cu criptografia cu cheie asimetrică

Semnăturile digitale reprezintă o altă aplicație puternică a criptografiei cu cheie asimetrică. Ele asigură autentificarea, integritatea și non-repudierea, posibile datorită faptului că în AKC, entitățile posedă chei private unice. Ideea de bază a protocoalelor de semnătură este că expeditorii de mesaje securizate vor semna digital mesajele folosind cheia lor privată unică. Destinatarul va verifica apoi semnătura digitală folosind cheia publică a expeditorului. În AKC, semnăturile digitale pot fi implementate folosind algoritmi special concepuți în acest scop sau prin utilizarea criptosistemelor generice.

Figura 4. Semnături digitale cu criptografia cu cheie asimetrică

Algoritmi dedicați pentru semnături digitale

În prezent, standardul US Federal Information Processing Standard (FIPS) pentru semnături digitale este o schemă dedicată denumită simplu Algoritmul de Semnătură Digitală (DSA). Similar într-o oarecare măsură cu protocolul Diffie-Hellman, DSA utilizează proprietățile algebrice ale exponențialului modular și ale inverselor multiplicative pentru generarea și verificarea semnăturilor.

Algoritmul de semnătură digitală pe curbe eliptice (ECDSA) este o variantă ECC a DSA, oferind aceeași funcționalitate dar cu chei semnificativ mai scurte. Aceasta duce la o eficiență îmbunătățită, făcându-l o alegere populară pentru sistemele cu constrângeri de resurse.

Atât DSA, cât și ECDSA vor fi ilustrate în mai mult detaliu mai târziu.

Scheme de semnătură digitală folosind criptosisteme generice

Pe lângă algoritmii dedicați, semnăturile digitale pot fi generate și folosind criptosisteme asimetrice generice, cum ar fi RSA.

RSA, care va fi discutat în detaliu într-o secțiune ulterioară, exploatează și el inversele multiplicative modulare și exponențierea modulară ca operații fundamentale, dar le combină într-o secvență diferită față de DSA. În RSA, semnatarul creează de obicei un hash al mesajului și apoi criptează hash-ul cu cheia sa privată, creând semnătura digitală. Orice parte poate verifica ulterior această semnătură decriptând-o cu cheia publică a semnatarului și comparând-o cu mesajul hash.

Aplicații ale criptografiei cu cheie asimetrică

Criptografia cu cheie asimetrică este ubiquitară în aplicațiile moderne de tehnologie digitală. Funcționalitățile de bază ale AKC descrise mai sus formează blocurile de construcție ale multor protocoale de aplicații de nivel superior, inclusiv:

1. Comunicarea pe internet: Comunicarea securizată pe internet, cum ar fi HTTPS, se bazează în mare măsură pe criptografia cu cheie asimetrică. Transport Layer Security (TLS) și predecesorul său, Secure Sockets Layer (SSL), utilizează criptografia cu cheie asimetrică în timpul procesului inițial de handshake pentru a stabili o cheie simetrică, care este apoi folosită pentru restul sesiunii de comunicare.

2. Autentificare: Criptografia cu cheie asimetrică este utilizată pentru a crea semnături digitale, permițând unei entități să autentifice un document sau un mesaj digital ca provenind de la un anumit expeditor. Aceasta este folosită în multe scenarii, de la verificarea actualizărilor de software până la contracte digitale cu forță juridică.

3. Criptarea e-mailurilor: Protocoalele de criptare a e-mailurilor precum PGP (Pretty Good Privacy) și alternativa sa open-source GPG (GNU Privacy Guard) utilizează criptografia cu cheie asimetrică pentru a se asigura că numai destinatarul vizat poate citi conținutul e-mailului.

4. Shell securizat (SSH): SSH este un protocol pentru conectare la distanță securizată și alte servicii de rețea securizate peste o rețea nesecurizată. Utilizează criptografia cu cheie asimetrică pentru a autentifica serverul față de client și, opțional, clientul față de server.

5. VPN (rețea privată virtuală): Criptarea cu cheie asimetrică este utilizată pentru a stabili conexiuni securizate în VPN-uri, asigurând comunicarea securizată prin rețele publice.

6. Blockchain și criptomonede: Tehnologiile blockchain, inclusiv Bitcoin și Ethereum, utilizează criptografia cu cheie asimetrică. De exemplu, proprietatea asupra Bitcoin este stabilită prin semnături digitale folosind criptografia cu cheie asimetrică.

7. Autorități de certificare: Criptografia cu cheie asimetrică este utilizată de autoritățile de certificare (CA) pentru a emite și semna certificate digitale, care sunt folosite în comunicarea TLS, semnarea codului, criptarea e-mailurilor și altele. Un certificat digital leagă o cheie publică de o entitate specifică (de exemplu, o persoană sau un server).

Figura 5. Emiterea și semnarea certificatelor digitale folosind criptografia cu cheie asimetrică

Securitatea criptografiei cu cheie asimetrică

Mai multe noțiuni criptografice se reunesc pentru a permite o criptografie cu cheie asimetrică securizată, inclusiv:

Secretul cheii private: Cea mai de bază cerință de securitate a AKC este că cheia privată rămâne secretă. Cu toate acestea, deoarece cheia privată trebuie să fie legată matematic de cheia publică, secretul cheii private necesită și că este imposibil din punct de vedere computațional să se derive cheia privată din cunoașterea cheii publice. Schemele de generare a cheilor în AKC se bazează pe probleme matematice dificile din punct de vedere computațional pentru a facilita această cerință.

Funcționalitate trapă: În AKC, operațiunile de criptare și decriptare implică chei complementare diferite dintr-o singură pereche de chei. Textul cifrat generat prin criptare folosind una dintre chei (de exemplu cheia publică) trebuie să fie de nedescifrat pentru terțe părți, în timp ce să fie ușor de decriptat de deținătorul cheii complementare (în acest caz cheia privată). Cu alte cuvinte, criptarea ar trebui să semene cu o funcție unidirecțională cu trapă, astfel încât terțele părți să nu poată inversa operația și recupera textul clar, dar cheia privată să ofere o trapă secretă care permite inversarea ușoară. Algoritmii AKC populari utilizează exponențierea modulară pentru a crea comportamentul de funcție unidirecțională cu trapă.

Aleatorietatea: Procesul de generare a cheilor ar trebui să exploateze și aleatorietatea pentru a se asigura că cheile sunt impredictibile, deoarece orice model sau predictibilitate în generarea cheilor ar putea fi exploatat de un atacator. Aleatorietatea este utilizată și pentru padding în timpul criptării pentru a genera texte cifrate semantic securizate și în schemele de semnătură digitală pentru a produce semnături unice chiar și atunci când același mesaj este semnat de mai multe ori. Din acest motiv, utilizarea generatoarelor de numere aleatoare puternice este o parte importantă a AKC.

Dimensiune mare a cheii: Ca și în cazul SKC, dimensiunile mari ale cheilor asigură protecție împotriva atacurilor prin forță brută. Cu toate acestea, deoarece dimensiunile mari ale cheilor cresc și costul computațional al procesului de criptare și decriptare, o soluție optimă trebuie să echilibreze considerațiile de securitate și eficiență. Tabelul următor prezintă dimensiunile tipice ale cheilor pentru diverse protocoale și aplicații de criptografie cu cheie asimetrică:

Protocol	Dimensiuni tipice ale cheilor (în biți)	Aplicație
RSA	1024 (depreciat), 2048, 3072, 4096	Criptare, semnături digitale
DSA	1024 (depreciat), 2048, 3072	Semnături digitale
DH	2048, 3072, 4096	Schimb de chei
ECDH	224, 256, 384, 521	Schimb de chei
ECDSA	224, 256, 384, 521	Semnături digitale

Infrastructura cu cheie publică: În AKC, cheile private trebuie păstrate secrete de proprietari, în timp ce cheile publice sunt partajate. Este nevoie de un mecanism securizat pentru a gestiona și distribui aceste chei publice între utilizatori. Infrastructura cu cheie publică (PKI) oferă o modalitate de a face acest lucru folosind certificate digitale. Un certificat digital oferă dovada identității proprietarului cheii publice și este emis de o autoritate de încredere, cum ar fi o autoritate de certificare (care face parte dintr-un PKI). Prin urmare, PKI joacă un rol integral în securitatea aplicațiilor moderne care utilizează AKC, permițând gestionarea cheilor la scară largă (prin crearea, gestionarea, distribuirea și revocarea certificatelor digitale).

Riscuri de securitate pentru criptografia cu cheie asimetrică

Așa cum se arată în tabelul de mai sus, algoritmii moderni cu cheie asimetrică, cum ar fi RSA, utilizează de obicei dimensiuni de cheie mult mai mari decât omologii cu cheie simetrică utilizați în mod obișnuit, cum ar fi AES-128. Chiar și protocoalele bazate pe ECC (ECDH și ECDSA) care au dimensiuni mai mici ale cheilor utilizează un minim de cel puțin 224 biți pentru chei. Aceasta implică la rândul său că un atac prin forță brută care implică o căutare exhaustivă a spațiului cheilor private pentru a identifica cheia corectă este intractabil din punct de vedere computațional în viitorul previzibil. Acest lucru rămâne valabil chiar dacă calculatoarele cuantice ar fi folosite pentru această sarcină. Prin urmare, atacurile împotriva AKC se concentrează de obicei pe exploatarea altor potențiale slăbiciuni ale criptosistemelor specifice. Unele moduri de atac bine documentate vizează:

1. Slăbiciunea algoritmică prin utilizarea mijloacelor matematice și computaționale sofisticate pentru a submina ipotezele de dificultate folosite pentru a formula algoritmii cu cheie asimetrică. De exemplu, securitatea RSA este condiționată de dificultatea factorizării numerelor prime mari, iar progresele computaționale recente au permis factorizarea cu succes a cheilor RSA de 829 de biți. Prin urmare, RSA pe 1024 biți este în prezent depreciat. Așa cum va fi discutat mai târziu, riscul principal pe care calculatoarele cuantice îl reprezintă pentru AKC se încadrează și în această categorie.

2. Aleatorietatea imperfectă, care poate duce la slăbiciuni în procesul de generare a cheilor. De exemplu, dacă generatorul de numere aleatoare utilizat pentru a crea cheile este defect și generează chei care nu sunt cu adevărat aleatoare, un atacator ar putea fi capabil să prevadă cheile.

3. Defecte de implementare, cum ar fi erori în implementarea algoritmilor criptografici care dezvăluie involuntar informații despre chei. De exemplu, padding-ul incorect poate dezvălui potențial detalii despre chei.

4. Canale laterale care se referă la scurgeri de informații din sistemul fizic care efectuează criptografia. Astfel de scurgeri ar putea fi sub formă de informații de sincronizare, consum de energie sau chiar sunet, care pot fi exploatate într-un așa-numit atac pe canal lateral. De exemplu, analizarea duratei de execuție a operațiunilor criptografice ar putea dezvălui numărul de „1"-uri dintr-o cheie binară. Această scurgere aparent inocentă restrânge semnificativ spațiul de căutare, dezvăluind soluții potențiale la probleme care inițial păreau de nerezolvat.

5. Schimbul de chei prin interceptarea cheilor în timp ce sunt schimbate, cum ar fi într-un atac de tip om-în-mijloc (MITM). Protocolul DH este susceptibil la atacuri MITM dacă nu sunt incorporate pași suplimentari de autentificare.

6. Stocarea cheilor prin vizarea furtului cheilor din spații de stocare insuficient securizate. Aceasta include atacuri fizice, cum ar fi manipularea sau furtul dispozitivelor de stocare.

Securizarea criptosistemelor cu cheie asimetrică împotriva varietății de atacuri posibile este, prin urmare, o sarcină semnificativă care implică considerații matematice, hardware, software, logistice și juridice.

RSA

Algoritmul RSA (Rivest-Shamir-Adleman) este unul dintre primele sisteme de criptografie cu cheie publică și este utilizat pe scară largă pentru transmiterea securizată a datelor. Este un sistem criptografic versatil, oferind operațiile necesare pentru a permite criptarea, decriptarea, semnăturile digitale și schimbul de chei într-un cadru comun.

În această secțiune, vom ilustra criptografia cu cheie asimetrică (AKC) folosind RSA prin exemple simple.

Vom folosi scenariul standard cu două părți, Alice și Bob, care doresc să comunice în siguranță folosind AKC.

Algoritmul RSA

Algoritmul RSA de bază implică patru operații: generarea cheilor, distribuirea cheilor, criptarea și decriptarea:

1. Generarea cheilor:

   Cheile publice și private sunt generate pe baza principiilor matematice legate de numerele prime, unde calculul acestora este ușor, dar inversul este dificil.

   Le vom numi astfel:

   • Cheie publică: $(e, n)$
   • Cheie privată: $(d, n)$

   Observă că $n$ este comun atât cheii publice, cât și cheii private, și este cunoscut sub numele de modul. Vom avea nevoie de acesta mai târziu.

Detaliu matematic

• Alege două numere prime distincte, $p$ și $q$.
  • alese aleatoriu (pentru securitate).
  • Ar trebui să fie de magnitudini similare, dar să difere ca număr de cifre, pentru a face factorizarea mai dificilă.
  • Numerele prime pot fi alese eficient folosind un test de primalitate.
• Calculează $n = p*q$.
  • $n$ este modulul atât pentru cheile publice, cât și pentru cele private.
• Calculează totientul $φ$$(n) = (p-1)*(q-1)$.
  • Totientul trebuie păstrat secret și este de obicei eliminat după generarea cheilor.
• Alege un întreg $e$ astfel încât $1 < e <$$φ$$(n)$ și $gcd$$(e,$$φ$$(n)) = 1$.
  • adică, $e$ și $φ$$(n)$ ar trebui să fie coprime.
  • Acest număr $e$ formează exponentul cheii publice și este de obicei ales ca un număr mic pentru eficiență computațională.
  • Numărul prim $65537 = 2^{16} + 1$ este folosit frecvent.
  • Calculează $d$ pentru a satisface relația de congruență $d*e ≡ 1 ($$mod$$φ$$(n))$.
    • Adică, $d$ este inversul multiplicativ al lui $e$ modulo $φ$$(n)$.
    • Acesta este calculat mai eficient folosind algoritmul euclidian extins.
    • Acest număr $d$ este exponentul cheii private.
• Cheia publică este formată din $(e, n)$, iar cheia privată este $(d, n)$.

2. Distribuirea cheilor:

   • Cheia publică $(e, n)$ este făcută publică celor care pot dori să trimită un mesaj
   • Cheia privată $(d, n)$ este păstrată secretă.

3. Criptarea:

   • Alice dorește să trimită un mesaj $M$ lui Bob. În acest caz un simplu număr întreg
   • Alice folosește cheia publică a lui Bob $(e, n)$ pentru a cripta mesajul în textul cifrat $C$

   Detaliu matematic

   • $M$ este un număr întreg $0 ≤ M < n$.
   • $C ≡ M^e (mod n)$, unde $C$ este textul cifrat.

4. Decriptarea:

   • Bob primește textul cifrat $C$
   • Bob folosește cheia sa privată $(d, n)$ pentru a decripta mesajul înapoi în mesajul $M$

   Detaliu matematic

   • $M ≡ C^d (mod n)$.

Acesta este conturul de bază al RSA. În practică, scheme de umplutură mai sofisticate sunt aplicate textului simplu $M$ înainte de criptare pentru a se asigura că texte simple egale conduc la texte cifrate diferite. Aceasta previne o serie de atacuri posibile împotriva implementărilor naive ale RSA și permite securitatea semantică.

Ilustrarea RSA în Python

În celulele de cod de mai jos, ilustrăm un exemplu simplu al algoritmului RSA folosind numere întregi mici și apoi demonstrăm distribuția practică a cheilor și aplicații de semnătură digitală folosind biblioteci Python care implementează RSA.

notă

Notă: În această secțiune vom arăta calculele matematice în detaliu ca parte a codului Python

Generarea cheilor RSA

Să parcurgem pas cu pas o instanță simplă a algoritmului RSA folosind numere prime mici.

Va trebui să putem calcula cel mai mare divizor comun a două numere întregi, deoarece va fi necesar pentru a testa dacă două numere întregi sunt coprime.

Vom explica o metodă simplă de calcul a acestuia, dar este mult mai eficient cu numere întregi mai mari să folosești funcția Python math.gcd.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

import math

# Example function to compute the gcd (greatest common divisor)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# let's calculate some examples using algorithm
n1 = gcd(50, 10)
n2 = gcd(99, 33)
n3 = gcd(59, 9)

# do the same with the python library call

m1 = math.gcd(50, 10)
m2 = math.gcd(99, 33)
m3 = math.gcd(59, 9)

# Confirm they are the same
assert n1 == m1
assert n2 == m2
assert n3 == m3

# They are - print out the values for explanation
print("gcd(50,10) =", m1)
print("gcd(99,33) =", m2)
print("gcd(59,9) =", m3)

Prima fază a fluxului de lucru RSA este generarea cheilor. Aceasta este inițiată prin alegerea a două numere prime, care trebuie păstrate secrete de entitatea care generează cheile.

# Choosing two prime numbers and keep them secret
p = 13
q = 19
print("The secret prime numbers p and q are:", p, q)

Apoi, modulul $n$, care este pur și simplu produsul celor două numere prime alese, este calculat. Acest modul va fi publicat ca parte a cheii publice.

# Calculate n which is the modulus for both the public and private keys
n = p * q
print("modulus n (p*q)=", n)

Funcția totient a lui Euler $\varphi(n)$ este calculată în continuare, deoarece este necesară pentru operația de invers multiplicativ modular folosită pentru a determina cheile în RSA. $phi$ este de asemenea păstrat secret și de obicei eliminat după generarea cheilor.

# Compute Euler's totient function, φ(n) and keep it secret
phi = (p - 1) * (q - 1)
print("The secret Euler's function (totient) [phi(n)]:", phi)

Suntem acum gata să calculăm cheile publice și private. În RSA, fiecare dintre acestea este specificată printr-un tuplu de două numere întregi. Prima intrare din fiecare tuplu este un număr întreg distinct, iar a doua intrare este modulul $n$ care este comun ambelor chei.

Prima intrare din cheia publică poate fi orice număr întreg mai mare de 1 care este coprim cu $phi$. Două numere întregi sunt coprime dacă cel mai mare divizor comun al lor este 1. Deci folosim funcția math.gcd pentru a găsi un număr întreg $e$ coprim cu $phi$.

# Choose an integer e such that e and φ(n) are coprime
e = 2
while e < phi:
    if math.gcd(e, phi) == 1:
        break
    else:
        e += 1
print("Public Key (e):", e)

Cheia privată necesită un număr întreg $d$, care este inversul multiplicativ al lui $e$ modulo $phi$; adică, satisface relația de congruență $d*e\equiv 1 \pmod{\varphi(n)}$. Pentru această ilustrare simplă în care lucrăm cu numere întregi mici, putem pur și simplu itera peste numerele întregi pozitive pentru a găsi un $d$ potrivit. În scenarii reale, algoritmul euclidian extins, eficient din punct de vedere computațional, este folosit în acest scop.

# Compute a value for d such that (d * e) % φ(n) = 1
d = 1
while True:
    if (d * e) % phi == 1:
        break
    else:
        d += 1
print("Private Key (d):", d)

Formăm acum tuplurile $(e, n), (d, n)$, care formează cheile publică și privată, respectiv. Cheia publică este apoi publicată, în timp ce cheia privată este păstrată secretă.

# Public and Private Key pair
public = (e, n)
private = (d, n)

print(f"The Public key is {public} and Private Key is {private}")

Criptarea și decriptarea în RSA folosesc operația de exponențiere modulară. Mai mult, cheile publice și private sunt complementare în sensul că oricare poate fi utilizată pentru a cripta un mesaj pe care cealaltă îl poate decripta.

Ilustrăm aici cazul în care cheia publică $(e,n)$ este utilizată pentru criptare și cheia privată $(d, n)$ este utilizată pentru decriptare, definind o funcție Python pentru fiecare operație.

Criptăm și decriptăm apoi un mesaj întreg $msg$.

# Encryption function
def encrypt(plain_text):
    return (plain_text**e) % n

# Decryption function
def decrypt(cipher_text):
    return (cipher_text**d) % n

# Simple message to encode
msg = 9

# encrypt then decrypt
enc_msg = encrypt(msg)
dec_msg = decrypt(enc_msg)

print("Original Message:", msg)
print("Encrypted Message:", enc_msg)
print("Decrypted Message:", dec_msg)

În timp ce numerele întregi mici utilizate mai sus sunt utile pentru a contura cu ușurință ideile de bază ale algoritmului RSA, în aplicații reale RSA necesită utilizarea unor numere întregi foarte mari. De exemplu, RSA pe 2048 de biți implică utilizarea unui modul $n$ de 2048 de biți, ale cărui echivalente în zecimal sunt în jur de 10$^616$. Aceste numere cu adevărat enorme sunt necesare pentru securitatea practică a RSA.

Schimbul de chei simetrice cu RSA

Așa cum am discutat anterior, AKC permite două părți care doresc să comunice să stabilească în siguranță un secret comun, care poate fi utilizat, de exemplu, ca cheie secretă pentru criptarea simetrică ulterioară a textului simplu în vrac.

Să luăm în considerare următorul scenariu. Alice și Bob vor să folosească SKC pentru a cripta și decripta mesaje. Cu toate acestea, înainte ca acest proces să poată fi inițializat, trebuie să convină asupra unei chei secrete comune. O opțiune este ca una dintre părți — să zicem, Alice — să genereze o cheie secretă și apoi să o transmită în siguranță lui Bob. Pentru a realiza acest transfer securizat, Alice decide să folosească RSA ca mecanism de încapsulare a cheilor (KEM).

Aceasta implică următorii pași:

• Mai întâi, Alice generează o cheie simetrică aleatorie, pe care intenționează să o împartă cu Bob.
• Apoi, Bob generează o pereche de chei asimetrice și face disponibilă cheia sa publică pe un canal adecvat.
• Apoi, Alice folosește cheia publică a lui Bob pentru a cripta cheia simetrică, încapsulând-o astfel într-un text cifrat.
• Apoi, Alice transmite textul cifrat pe un canal fiabil, dar nu neapărat securizat.
• În cele din urmă, Bob primește textul cifrat și îl decriptează folosind cheia sa privată. Acum are acces la cheia simetrică generată de Alice.

Figura 1. Schimbul de chei simetrice cu RSA

Exemplu de schimb de chei bazat pe umplutură în Python

Un flux de lucru practic care utilizează RSA pentru schimbul de chei non-interactiv bazat pe umplutură este ilustrat acum folosind biblioteca Python cryptography.

Importă modulele necesare din biblioteca Python cryptography. Dacă este nevoie, această bibliotecă poate fi instalată folosind comanda pip install cryptography.

Alice generează apoi o cheie secretă aleatorie, pe care intenționează să o transmită lui Bob.

# pip install cryptography
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.fernet import Fernet
from cryptography.hazmat.primitives import hashes

symmetric_key = Fernet.generate_key()
print(f"\nSymmetric key generated by Alice: {symmetric_key}")

Folosind modulul rsa din biblioteca cryptography, Bob generează o pereche de chei și apoi transmite cheia sa publică. Oricine poate intercepta cheia publică și poate citi numerele publice $(e,n)$ care formează cheia.

# Bob generates a 2048-bit RSA key pair
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()
print(f"Public key broadcast by Bob: {bob_public_key}")
print(f"\nPublic numbers in Bobs' public key: {bob_public_key.public_numbers()}")

În acest moment, presupunem că Alice a primit cheia publică transmisă de Bob. symmetric_key-ul lui Alice de mai sus poate fi acum criptat folosind cheia publică a lui Bob pentru a produce textul cifrat. Într-un scenariu realist, Alice va folosi și metode suplimentare de umplutură cum ar fi OAEP pentru a asigura securitatea semantică a comunicărilor sale cu Bob.

# Encryption
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Ciphertext:", ciphertext)

Alice transmite apoi textul cifrat pe un canal deschis, încrezătoare că numai Bob cu cheia privată corespunzătoare va putea să îl decripteze. Presupunem că Bob a primit textul cifrat și îl poate acum decripta folosind cheia sa privată confidențială.

# Bob decrypts ciphertext to access the symmetric key
decrypted_symmetric_key = bob_private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted key:", decrypted_symmetric_key)
assert decrypted_symmetric_key == symmetric_key

În acest moment, atât Alice cât și Bob au acces la cheia simetrică secretă, pe care o pot folosi pentru aplicații SKC.

Simularea unui Mecanism de Încapsulare a Cheilor cu RSA în Python

În fluxul de lucru următor, ilustrăm utilizarea RSA pentru a simula un Mecanism de Încapsulare a Cheilor (KEM) prin care un mesaj secret aleatoriu suficient de lung este schimbat în siguranță și convertit ulterior într-un secret comun de lungime adecvată folosind un KDF.

Din nou, Alice și Bob vor să stabilească un secret comun în mod non-interactiv, iar Alice este cea care decide ce secret să folosească.

Începem prin importarea unor biblioteci Python necesare.

Bob generează apoi perechea sa de chei RSA și transmite cheia sa publică.

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives import hashes
from os import urandom

# Bob's RSA key pair
private_key_Bob = rsa.generate_private_key(public_exponent=65537, key_size=2048)
public_key_Bob = private_key_Bob.public_key()

print("Bob's private and public keys created")

Alice generează mai întâi un secret aleatoriu lung din care secretul comun va fi eventual derivat. Într-un KEM pur, secretul lung va fi un element aleatoriu din structura algebrică ce stă la baza sistemului criptografic. În cazul RSA pe 2048 de biți, acesta ar fi un număr întreg aleatoriu modulo modulul RSA pe 2048 de biți. Deoarece un KEM pur nu necesită umplutură suplimentară, dar în acest exemplu simulăm doar un KEM folosind RSA și biblioteca cryptography necesită utilizarea umpluturilor la criptarea cu RSA. Deci vom folosi un secret lung oarecum mai scurt care este totuși mult mai lung decât o cheie AES standard de 256 de biți.

Alice_long_secret = urandom(160)  # A 160 byte or 1280 bit random message
print("Alice's secret created")

Alice criptează secretul lung folosind cheia publică a lui Bob și secretul criptat este comunicat lui Bob.

Alice_encrypted_secret = public_key_Bob.encrypt(
    Alice_long_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)
print("Alice's secret encrypted")

Bob decriptează secretul criptat primit de la Alice folosind cheia sa privată.

Bob_decrypted_secret = private_key_Bob.decrypt(
    Alice_encrypted_secret,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

assert Alice_long_secret == Bob_decrypted_secret, "Secrets do not match!"

# if we get here they match
print("Secrets match")

În cele din urmă, atât Alice cât și Bob aplică separat o Funcție de Derivare a Cheilor (KDF) convenită pe secretul lung pentru a deriva cheia simetrică.

Rețineți că procesul implică un protocol de hashing și utilizarea unui salt aleatoriu care asigură unicitatea și impredictibilitatea cheii simetrice comune în cazul în care secretul lung este vreodată reutilizat (nu este recomandat). Cu toate acestea, salt-ul în sine nu trebuie să fie secret și odată ce este generat aleatoriu, de exemplu de Alice în acest exemplu, poate fi transmis lui Bob alături de secretul lung criptat.

Vom presupune, prin urmare, că atât Alice cât și Bob au acces la același salt aleatoriu.

def key_derivation_function(secret, salt):
    hkdf = HKDF(
        algorithm=hashes.SHA256(),
        length=32,  # Desired key length
        salt=salt,
        info=None,
        backend=None,
    )
    return hkdf.derive(secret)

common_salt = urandom(16)  # Random salt accessible to both Alice and Bob

symmetric_key_Alice = key_derivation_function(Alice_long_secret, common_salt)
symmetric_key_Bob = key_derivation_function(Bob_decrypted_secret, common_salt)

assert symmetric_key_Alice == symmetric_key_Bob, "Derived keys do not match!"
print(
    f"A symmetric key of length {len(symmetric_key_Alice)*8} bits was successfully derived by both Alice and Bob!"
)

Semnături digitale cu RSA

Vom extinde acum scenariul de comunicare confidențială de mai sus cu Alice și Bob la unul care include și validarea cu ajutorul unei semnături digitale.

Ca înainte, Alice va trimite confidențial un mesaj care încapsulează o cheie simetrică lui Bob, dar va semna digital și mesajul astfel încât Bob, la primirea mesajului, să poată verifica că Alice l-a origina și că conținutul mesajului nu a fost alterat în timpul transmiterii.

Mai general, este de dorit să se permită validarea fără a compromite confidențialitatea, prin care orice parte interesată poate verifica integritatea, autenticitatea și poate stabili non-repudierea cu privire la o anumită comunicare, chiar dacă acea parte nu are acces la mesajul text simplu propriu-zis.

Vom considera acest cadru general care implică următorii pași:

• Mai întâi, atât Bob cât și Alice fac disponibile cheile lor publice pe un canal deschis.
• Apoi, Alice criptează textul simplu folosind cheia publică a lui Bob, creând un text cifrat.
• Apoi, Alice creează un hash al textului cifrat cu o funcție hash și criptează ulterior hash-ul textului cifrat rezultat folosind cheia sa privată. Acest hash criptat este semnătura.
• Apoi, Alice transmite atât textul cifrat cât și semnătura pe un canal deschis.
• Apoi, Bob folosește cheia publică a lui Alice pentru a decripta semnătura, dezvăluind hash-ul textului cifrat.
• Apoi, deoarece Bob are și el acces la textul cifrat în sine, folosește aceeași funcție hash folosită de Alice pentru a recrea o a doua instanță a hash-ului textului cifrat. Dacă aceasta se potrivește cu cea obținută prin decriptarea semnăturii lui Alice, atunci mesajul este validat, chiar dacă textul cifrat în sine nu a fost încă decriptat.
• În cele din urmă, Bob, după ce a validat mesajul, decriptează textul cifrat folosind propria sa cheie privată.

Figura 2. Semnături digitale cu RSA

Acest flux de lucru pentru o semnătură digitală este ilustrat în continuare.

Importăm din nou câteva module utile din biblioteca cryptography. Ca înainte, Alice intenționează să trimită în siguranță o cheie simetrică lui Bob, dar dorește și să o semneze digital. În acest caz, avem nevoie de chei publice atât pentru Alice cât și pentru Bob. Prin urmare, primul pas este ca atât Alice cât și Bob să creeze propria lor pereche de chei folosind RSA și să transmită propria lor cheie publică lumii întregi.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding, rsa
from cryptography.hazmat.primitives.asymmetric.utils import Prehashed

# Generate keys for Bob
bob_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
bob_public_key = bob_private_key.public_key()

# Generate keys for Alice
alice_private_key = rsa.generate_private_key(public_exponent=65537, key_size=2048)
alice_public_key = alice_private_key.public_key()

print("Private and Public keys generated for Bob and Alice.")

În pasul următor, ca înainte, Alice folosește cheia publică a lui Bob pentru a cripta cheia simetrică și pregătește textul cifrat.

# Alice encrypts the message using Bob's public key
ciphertext = bob_public_key.encrypt(
    symmetric_key,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("ciphertext of symmetric key: ", ciphertext)

În acest stadiu, în loc să transmită doar textul cifrat, Alice intenționează să atașeze o semnătură digitală la acesta pentru a-i putea dovedi lui Bob că ea a fost expeditoarea mesajului. Aceasta se face în două etape:

1. Creează un hash al textului cifrat folosind un algoritm de hashing.
2. Criptează hash-ul folosind cheia privată a lui Alice, ceea ce echivalează cu o semnătură.

# Alice signs the ciphertext using her private key
digest = hashes.Hash(hashes.SHA256())
digest.update(ciphertext)
hash_to_sign = digest.finalize()

signature = alice_private_key.sign(
    hash_to_sign,
    padding.PSS(mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH),
    Prehashed(hashes.SHA256()),
)

print("signature: ", signature)

Alice transmite apoi textul cifrat și semnătura pe o rețea astfel încât Bob să le poată intercepta pe amândouă.

# Bob receives the ciphertext and signature
received_ciphertext = ciphertext
received_signature = signature

# Send signature and ciphertext here
print("Sending ciphertext and signature.....")

Pe partea lui Bob, prima sarcină este să verifice integritatea și autenticitatea textului cifrat. Pentru a face acest lucru, Bob creează un hash al textului cifrat primit folosind același algoritm de hashing folosit de Alice.

# Bob creates a hash of the ciphertext using the same algorithm used by Alice
digest = hashes.Hash(hashes.SHA256())
digest.update(received_ciphertext)
hash_to_verify = digest.finalize()

print("hash to verify: ", hash_to_verify)

Apoi, Bob decriptează semnătura primită folosind cheia publică a lui Alice. Deoarece Alice a folosit cheia sa privată pentru a crea semnătura, Bob poate să o decripteze folosind cheia publică a lui Alice. Semnătura decriptată nu este altceva decât un hash al textului cifrat creat de Alice. Dacă hash-ul creat de Bob se potrivește cu semnătura decriptată, atunci Bob a verificat că textul cifrat pe care l-a primit nu a fost alterat și că Alice a semnat textul cifrat.

În codul Python de mai jos, aceste operații sunt combinate într-o funcție utilă numită verify furnizată de un obiect asociat cu cheia publică a lui Alice.

from cryptography.exceptions import InvalidSignature

def is_signature_valid(public_key, signature, data_hash):
    try:
        public_key.verify(
            signature,
            data_hash,
            padding.PSS(
                mgf=padding.MGF1(hashes.SHA256()), salt_length=padding.PSS.MAX_LENGTH
            ),
            Prehashed(hashes.SHA256()),
        )
        return True
    except InvalidSignature:
        return False

if is_signature_valid(alice_public_key, received_signature, hash_to_verify):
    print("The signature is valid.")
else:
    print("The signature is not valid.")

După ce a verificat integritatea și autenticitatea textului cifrat primit, Bob poate să îl decripteze folosind cheia sa privată, deoarece Alice a creat textul cifrat folosind cheia publică a lui Bob.

# Bob decrypts the message using his private key
decrypted_message = bob_private_key.decrypt(
    received_ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None,
    ),
)

print("Decrypted message:", decrypted_message.decode())

În scenariul de semnătură digitală de mai sus, orice parte — nu doar Bob — poate verifica că Alice este expeditoarea textului cifrat deoarece toată lumea poate accesa cheia publică a lui Alice, textul cifrat și semnătura digitală. Mai mult, după trimiterea textului cifrat și a semnăturii, Alice nu poate nega ulterior că a făcut-o deoarece semnătura poate fi decriptată la un hash semnificativ folosind doar cheia sa publică. Aceasta stabilește non-repudierea.

Prin permiterea distribuirii securizate a cheilor și susținerea non-repudierii, criptografia cu cheie publică stabilește o bază solidă pentru comunicarea digitală securizată.

Spargerea RSA

Utilitatea și securitatea algoritmului RSA descris mai sus se bazează pe două ipoteze matematice:

1. Găsirea inversului multiplicativ modular $d$ cunoscând doar $(e, n)$ este imposibilă din punct de vedere computațional.

2. În contextul RSA, operația de exponențiere modulară se comportă ca o funcție unidirecțională cu trapă. Când este folosită pentru criptare, produce un text cifrat de neînțeles, iar fără acces la cheia privată, inversarea operației pentru a recupera textul clar din textul cifrat nu este fezabilă. Totuși, cu acces la cheia privată, care acționează ca o trapă, textul cifrat poate fi decriptat cu ușurință.

Cel mai proeminent atac asupra algoritmului RSA urmărește să submineze ipoteza 1, recuperând eficient numărul cheii private $d$ prin factorizarea modulului $n$. Așa cum va fi ilustrat mai jos, este ușor să recuperezi $d$ dacă ai acces la factorii primi $p$ și $q$ ai lui $n$ sau la totientul $φ$$(n)$. Reamintește-ți că $p$, $q$ și $φ$$(n)$ sunt ținute secrete în timpul generării cheii și eliminate după aceea. O terță parte care recuperează aceste informații folosind un calculator clasic sau cuantic descoperă practic cheia privată, spărgând RSA. Astfel, factorizarea în numere prime este operația computațională esențială necesară pentru spargerea RSA.

Calculul clasic și RSA

Factorizarea în numere prime a numerelor întregi mari prezintă o scalare superpolinomială sau subexponențială pe calculatoarele clasice. Cel mai cunoscut algoritm clasic pentru factorizarea numerelor întregi mai mari de $10^{100}$ este sita generală a câmpului de numere (GNFS)

Detalii matematice

$L_n[\frac{1}{3}, (\frac{64}{9})^{(\frac{1}{3})}] = e^{[((\frac{64}{9})^{(\frac{1}{3})} + o(1)) (log(n))^{\frac{1}{3}}(log(log(n))^{\frac{2}{3}})]}$

ca funcție a numărului întreg $n$ de factorizat.

Această scalare este superpolinomială în numărul de biți necesari pentru a reprezenta $n$.

Prin urmare, factorizarea în numere prime este considerată ineficientă pe calculatoarele clasice.

În prezent, cele mai mari numere întregi factorizate pe hardware clasic sunt în jur de 829 de biți sau 250 de cifre zecimale. Având în vedere creșterea exponențială a puterii de calcul clasice observată în ultimele câteva decenii, RSA pe 1024 de biți nu mai este considerat sigur pe termen scurt și este acum depreciat. Cu toate acestea, în viitorul previzibil, factorizarea numerelor întregi de 2048 de biți cu magnitudinea în jur de $10^{617}$ este considerată în prezent nefezabilă pe sistemele clasice, sugerând o viabilitate continuă. Apariția calculatoarelor cuantice, totuși, anulează această evaluare.

Algoritmul cuantic al lui Shor și RSA

Probabil cel mai cunoscut algoritm cuantic de astăzi este algoritmul lui Shor pentru găsirea factorilor primi ai numerelor întregi. Când a fost introdus de Peter Shor în 1994, a fost recunoscut ca primul algoritm cuantic care oferea o accelerare superpolinomială față de algoritmii clasici pe o problemă de mare importanță practică, și anume factorizarea în numere prime.

Algoritmul lui Shor poate factoriza numere prime cu $O(n^2)$ unde $n$ este numărul de biți.

Explicație matematică a algoritmului lui Shor

În contextul RSA, algoritmul lui Shor funcționează exploatând periodicitatea funcției exponențiale modulare $f(x) = a^x (mod~n)$ și oferă o primitivă cuantică de găsire a perioadei care permite factorizarea eficientă în numere prime a modulului $n$.

O schiță simplificată la nivel înalt a schemei generale a lui Shor pentru spargerea RSA este următoarea:

1. Dat modulul $n$, care este publicat ca parte a cheii publice, alege un număr $a$ coprim cu $n$, adică $gcd(a,n) = 1$. Deoarece știm că $n = p*q$ are exact doi factori primi $(p, q)$, aproape orice număr mai mic decât $n$ pe care îl alegem aleatoriu este probabil coprim cu $n$.

2. Având ales $a$, găsește exponentul $r$ astfel încât $a^r \equiv 1 (mod~n)$. Aceasta implică $a^r - 1 \equiv 0 (mod~n)$. Existența unui exponent $r$ astfel încât congruența de mai sus să fie satisfăcută este garantată de proprietatea de periodicitate a exponențierii modulare.

3. Dacă $r$ este par, $a^r - 1 \equiv 0 (mod~n) \implies (a^{r/2} - 1) (a^{r/2} + 1) = \gamma*n$ pentru un număr întreg $\gamma$. Membrul stâng al acestei ultime egalități trebuie să conțină $p$ și $q$ ca doi dintre factorii săi primi, deoarece membrul drept îi conține. Dacă $r$ este impar, revino la pasul 1 și încearcă o altă alegere pentru $a$.

4. Folosește algoritmul extins al lui Euclid pentru a găsi $gcd((a^{r/2} - 1), n)$ sau $gcd((a^{r/2} + 1), n)$. CMMDC calculat este foarte probabil să identifice unul dintre factorii primi $p$ sau $q$. Împarte $n$ cu acest factor prim pentru a-l recupera pe celălalt.

5. Odată cunoscuți $p, q$, folosește pașii din algoritmul RSA original pentru a reconstrui totientul $\phi(n)$ și a genera numărul cheii private $d$ ca invers modular al numărului cunoscut al cheii publice $e$.

În august 2023, Oded Regev a publicat o îmbunătățire față de originalul lui Shor folosind o abordare multidimensională, rezultând $O(n^{1.5})$. Continuă să existe cercetări suplimentare, inclusiv de către Ragavan și Vaikuntanathan în acest domeniu, care ar putea îmbunătăți timpul, costul sau numărul de qubiți necesari. Deși nu putem spune când rularea unor astfel de algoritmi împotriva criptării RSA reale devine cu adevărat viabilă, aceasta se apropie tot mai mult.

Exemplu Python care demonstrează spargerea criptării RSA

În următoarele celule de cod, ilustrăm un exemplu de găsire a cheii private cunoscând doar cheia publică. Aceasta va folosi calculul clasic prin forță brută, dar arată cum ar putea fi folosit algoritmul lui Shor — inclusiv pentru chei mari.

notă

În această secțiune vom arăta calculele matematice în detaliu ca parte a codului Python

În exemplu, avem o cheie publică $(5, 247)$ și vom recupera cheia privată.

Pasul 1: Primul pas este să alegem un număr coprim cu 247. Aproape orice număr pe care îl ghicim va face treaba. Hai să alegem 6.

n = 247  # the modulus
e = 5  # public key number
a = 6  # an integer coprime to n
assert gcd(a, n) == 1
print(f"Checked {n} and {a} are coprime")

Pasul 2: Trebuie să găsim perioada $r$ astfel încât $6^r \equiv 1 (mod~247)$. În acest exemplu, calculăm $r$ clasic prin forță brută, dar am putea folosi și algoritmul lui Shor pe un calculator cuantic folosind Qiskit.

r = 0
rem = 100
while rem != 1:
    r += 1
    rem = (a**r) % n

print(f"period r is: {r}")
assert a**r % n == 1

print(f"Checked {a}^{r} mod {n} is 1")

Pasul 3: Deoarece perioada $r = 36$ este pară, putem calcula $f1 = (a^{r/2}-1), f2=(a^{r/2}+1)$.

# explicitly use as integer
f1 = int(a ** (r / 2) - 1)
f2 = int(a ** (r / 2) + 1)

print(f"f1 = {f1}")
print(f"f2 = {f2}")

Pasul 4: Găsim CMMDC al oricăruia dintre acei factori cu $n$. Împărțim pur și simplu $n$ cu factorul prim deja găsit pentru a obține al doilea factor prim.

q_found = gcd(f1, n)
print(f"One possible prime factor of n ({n}) is: {q_found}")

# explicit int (to avoid floating point)
p_found = int(n / q_found)
print(f"The second prime factor of n ({n}) is: {p_found}")

assert n == p_found * q_found

Pasul 5: După ce am recuperat factorii primi ai lui $n = 247$ ca $p_{found}=13$ și $q_{found}=19$, calculăm totientul $\phi_{found} = (p_{found}-1)*(q_{found}-1)$.

Cheia privată este inversul modular al numărului cheii publice $e=5$.

# Compute the totient
phi_found = (p_found - 1) * (q_found - 1)
print(f"The totient is: {phi_found}")

# Recover the private key number d_found by satisfying (d_found * e) % phi_found = 1
d_found = 1
while True:
    if (d_found * e) % phi_found == 1:
        break
    else:
        d_found += 1
print("Private Key number:", d_found)

În schema de mai sus, pasul 2 este operația crucială de găsire a perioadei pentru care algoritmul lui Shor folosește două primitive cuantice fundamentale, și anume transformata Fourier cuantică și estimarea de fază cuantică. Pentru o explicație detaliată a aspectelor cuantice ale algoritmului lui Shor, consultă lecția despre Estimarea fazei și factorizare din cursul Fundamentals of Quantum Algorithms. Pașii 1 și 3 până la 5 implică operații relativ ieftine care pot fi efectuate cu ușurință pe calculatoare clasice.

Opțional, iată un ghid vizual detaliat pentru implementarea algoritmului lui Shor.

Pe calculatoarele cuantice, algoritmul lui Shor poate prezenta o scalare polologaritmică la fel de favorabilă ca $O((log~n)^2 (log~log~n))$ în termeni ai modulului $n$, sau o scalare polinomială în termeni ai numărului de biți necesari pentru a reprezenta $n$. Aceasta este o accelerare superpolinomială față de algoritmul clasic GNFS.

Estimările recente ale resurselor indică faptul că, pe baza unor ipoteze cu privire la configurația hardware, vor fi necesari câteva zeci de mii până la câteva milioane de qubiți pentru a sparge RSA pe 2048 de biți folosind algoritmul lui Shor. Nu este de neconceput ca în câțiva ani să devină disponibile calculatoare cuantice cu câteva zeci de mii de qubiți, făcând accesibilă limita inferioară a estimării resurselor.

Schimbul de chei Diffie-Hellman și Algoritmul de Semnătură Digitală

În secțiunea anterioară, am discutat despre sistemul criptografic RSA, a cărui securitate se bazează pe dificultatea computațională a factorizării în numere prime. Aici, vom discuta două protocoale criptografice cu cheie asimetrică populare, schimbul de chei Diffie-Hellman (DH) și Algoritmul de Semnătură Digitală (DSA), ambele bazate pe o problemă matematică diferită, și anume problema logaritmului discret (DLP).

Problema logaritmului discret

În ecuația următoare trebuie să găsim $a$ cunoscând doar $e$, $M$, $c$

$a^e$ $mod$ $M = c$

Se crede că aceasta este dificilă cu calculatoarele clasice datorită utilizării aritmeticii modulo și, prin urmare, reprezintă o bază matematică bună pentru un algoritm de criptare.

Aceasta este cunoscută sub numele de problema logaritmului discret (DLP).

Detalii matematice ale problemei logaritmului discret

DLP este de obicei formulată în contextul grupurilor ciclice și este enunțată după cum urmează.

Consideră un grup ciclic $G$ generat de un element de grup $g \in G$ și dat un element arbitrar $h \in G$, găsește un număr întreg $k$ astfel încât $h = g^{k}$.

Aici numărul întreg $k \equiv log_{g}h$ este logaritmul discret. Proprietatea ciclică a lui $G$ garantează că pentru orice $h$, există un număr întreg valid $k$.

Pentru criptografie, DLP pe grupul multiplicativ al numerelor întregi modulo un număr prim $p$, notat $(\mathbb{Z}_p)^{\times}$, se dovedește a fi util. Elementele lui $(\mathbb{Z}_p)^{\times}$ sunt clase de congruență etichetate cu numere întregi modulo $p$ care sunt coprime cu $p$.

De exemplu:

$(\mathbb{Z}_5)^{\times} = \{[1],[2],[3],[4]\}~\mathrm{și}~(\mathbb{Z}_7)^{\times} = \{[1],[2],[3],[4],[5],[6]\}$

Operația de înmulțire $(\times)$ pe aceste grupuri este pur și simplu înmulțirea obișnuită a numerelor întregi urmată de reducerea modulo $p$, iar exponențierea cu un număr întreg $k$ este doar înmulțirea repetată de $k$ ori și reducerea modulo $p$.

Hai să ilustrăm o instanță a DLP pe $(\mathbb{Z}_7)^{\times}$.

Acest grup multiplicativ are doi generatori $\{[3],[5]\}$, cunoscuți și sub numele de rădăcini primitive. Vom folosi $[5]$ ca generator; adică vom genera fiecare element al lui $(\mathbb{Z}_7)^{\times}$ folosind puteri întregi succesive ale lui 5.

#Generate elements of (Z_7)^{x} using generator [5].
g = 5
p = 7
print(f"Using generator {g}")
for k in range(3*p):
    print(f"{g}**{k} mod {p} ≡ {(g**k)%7}")

Vedem că în aritmetica modulo 7, ridicarea lui 5 la puteri întregi succesive produce fiecare element al lui $(\mathbb{Z}_7)^{\times}$ exact o dată înainte ca ciclul să se repete la nesfârșit cu o perioadă $p-1 =6$.

Astfel, DLP pe $(\mathbb{Z}_7)^{\times}$ cu generatorul [5] este:

$\mathrm{Dat}~h \in (\mathbb{Z}_7)^{\times} \mathrm{, găsește~} k \mathrm{~astfel~încât~} 5^{k} \equiv h~(mod~7)$.

Din rezultatul celulei Python de mai sus vedem că:

$h = 2 \implies k=4 \mathrm{~sau~} 4 = log_5(2) (mod~7)$

$h = 6 \implies k=3 \mathrm{~sau~} 3 = log_5(6) (mod~7)$

În aritmetica numerelor reale obișnuite, exponențierea este o funcție monotonă, iar găsirea logaritmului oricărui număr față de orice bază este ușoară din punct de vedere computațional. În contrast, după cum reiese din exemplul simplu al lui $(\mathbb{Z}_7)^{\times}$ de mai sus, exponențierea modulară este nemonotonă și, deși este periodică cu perioada $p-1$, este altfel extrem de netrivială. Astfel, calcularea inversului său, logaritmul discret, se dovedește a fi ineficientă pentru $p$ mare pe calculatoarele clasice.

Această observație stă la baza atât a schimbului de chei Diffie-Hellman (DH), cât și a Algoritmului de Semnătură Digitală (DSA), care sunt discutate în secțiunea următoare.

DLP poate fi extinsă la subgrupuri ciclice după cum urmează:

• Consideră $(\mathbb{Z}_p)^{\times}$ definit mai sus și un element $g \in (\mathbb{Z}_p)^{\times}$ de ordin prim $r$, adică $g^r \equiv 1 (~mod~p)$.
• Mulțimea puterilor întregi ale lui $g$: $\{g^k~(mod~p) | 1 \le k \le r\} = \langle g \rangle$ este un subgrup ciclic al lui $(\mathbb{Z}_p)^{\times}$ cu ordinul grupului $r$.
• O DLP poate fi specificată pe $\langle g \rangle$ alegând un $h \in \\langle g \rangle$ și cerând $1 \le a \le r$ astfel încât $g^a~(mod~p) = h$

Schimbul de chei Diffie-Hellman

În 1976, Whitfield Diffie și Martin Hellman au propus un protocol de schimb de chei pentru a permite crearea unei chei secrete partajate prin canale de comunicare nesecurizate. Cheia secretă putea fi folosită ulterior de către părțile care o dețin pentru criptarea simetrică. Algoritmul se bazează pe DLP.

Figura 1. Schimbul de chei Diffie-Hellman

Detalii matematice ale schimbului de chei Diffie-Hellman

Cu Alice și Bob ca cele două părți care comunică, protocolul funcționează astfel:

• Mai întâi, Alice și Bob convin asupra unui număr prim mare $p$ și a unei rădăcini primitive sau generator $a$.
• Apoi, Alice alege un exponent secret $k_A$ aleatoriu cu $1 \le k_A \le p-2$ și calculează $h_A = a^{k_A}~(mod~p)$. $k_A, h_A$ sunt respectiv cheia privată și cheia publică ale lui Alice.
• Apoi, Bob alege un exponent secret $k_B$ aleatoriu cu $1 \le k_B \le p-2$ și calculează $h_B = a^{k_B}~(mod~p)$. $k_B, h_B$ sunt respectiv cheia privată și cheia publică ale lui Bob.
• Apoi, Alice îi trimite lui Bob $h_A$, iar Bob îi trimite lui Alice $h_B$ printr-un canal de comunicare fiabil, dar nu neapărat securizat.
• Apoi, Alice folosește $h_B$ primită pentru a calcula cheia secretă partajată $\kappa = h_B^{k_A}~(mod~p)$.
• În final, Bob folosește $h_A$ primită pentru a calcula cheia secretă partajată $\kappa = h_A^{k_B}~(mod~p)$.

Cu acest protocol,

• Alice și Bob sunt garantați că vor ajunge la aceeași cheie secretă $\kappa$ deoarece $h_B^{k_A}~(mod~p) = (a^{k_B})^{k_A}~(mod~p) = a^{k_A k_B}~(mod~p) = (a^{k_A})^{k_B}~(mod~p) = h_A^{k_B}~(mod~p)$.
• O terță parte care interceptează $h_A$ sau $h_B$ nu poate construi cheia secretă $\kappa$ deoarece nu are acces la $k_B$ sau $k_A$ respectiv.
• Extragerea lui $k_A$ sau $k_B$ folosind informațiile publice $a$, $p$, $h_A$ și $h_B$ este dificilă din punct de vedere computațional, deoarece este echivalentă cu rezolvarea DLP pe $(\mathbb{Z}_p)^{\times}$.

Ilustrarea protocolului Diffie-Hellman în Python

Hai să analizăm un exemplu simplu al protocolului DH în Python folosind numere prime mici:

notă

În această secțiune vom arăta calculele matematice în detaliu ca parte a codului Python

Pasul 1: Alice și Bob convin asupra unui număr prim $p$ și a unei rădăcini primitive $a$. Hai să alegem $p=11, a=7$.

# Step 1: Choose a prime `p` and a primitive root `a`
p = 11
a = 7

print(f"prime: {p}")
print(f"primitive root: {a}")

Pașii 2, 3: Alice alege un exponent secret $k_A$ și calculează $h_A = a^{k_A}~(mod~p)$. Similar, Bob alege un exponent secret $k_B$ și calculează $h_B = a^{k_B}~(mod~p)$.

k_A = 4  # Alice's private key
h_A = (a ** (k_A)) % p  # Alice's public key

print(f"Alice's private key is {k_A} and public key is {h_A}")

k_B = 8  # Bob's private key
h_B = (a ** (k_B)) % p  # Bob's public key

print(f"Bob's private key is {k_B} and public key is {h_B}")

Pasul 4: Cele două părți transmit public cheile lor publice $h_A$ și $h_B$.

Pașii 5, 6: Fiecare parte combină cheia sa privată cu cheia publică a celeilalte părți pentru a crea cheia secretă partajată.

secret_key_alice = h_B**k_A % p
secret_key_bob = h_A**k_B % p
assert secret_key_alice == secret_key_bob
print(f"The shared secret key is: {secret_key_bob}")

Alice și Bob pot folosi acum cheia secretă partajată pentru criptarea simetrică.

Securitatea schimbului de chei Diffie-Hellman

Așa cum s-a menționat mai sus, securitatea DH este condiționată de dificultatea computațională a rezolvării DLP cu numere prime mari $p$. În aplicațiile tipice, NIST recomandă numere prime întregi de 2048 sau 3072 de biți pentru schimbul de chei DH, considerat suficient de sigur împotriva tentativelor de rezolvare a DLP folosind calculatoare clasice.

Atacuri tip om-la-mijloc (MITM): Faptul că DH este o schemă interactivă în care secretul partajat depinde de combinarea cheii private a unei părți cu cheia publică a celeilalte îl face vulnerabil la un atac numit Man-in-the-middle (MITM).

Detalii matematice despre securitatea DH și atacurile MITM

În acest scenariu, o terță parte — să zicem, Eva — interceptează cheile publice $h_A, h_B$ în timpul transmisiei și substituie propria cheie publică $h_E$ pentru fiecare dintre $h_A$ și $h_B$ înainte de a le transmite mai departe lui Bob și respectiv lui Alice.

Apoi, în loc să folosească $h_B$ pentru a-și crea secretul partajat, Alice va folosi $h_E$ crezând că folosește cheia publică a lui Bob. Similar, în loc să folosească $h_A$ pentru a-și crea secretul partajat, Bob va folosi $h_E$ crezând că folosește cheia publică a lui Alice.

Deoarece $h_E$ a fost folosită pentru a crea secretul partajat al lui Alice (Bob), textul clar criptat de Alice (Bob) poate fi decriptat de Eva.

Prin urmare, schimbul de chei DH este de obicei folosit împreună cu un algoritm de semnătură digitală pentru a garanta că fiecare parte folosește o cheie publică autentificată pentru a-și crea secretul partajat.

Algoritmul de Semnătură Digitală (DSA)

Chiar dacă sistemele criptografice generice precum RSA oferă funcționalitate de semnătură digitală, în 1994 NIST a adoptat o schemă specializată de semnătură bazată pe exponențierea modulară și problema logaritmului discret ca standard federal pentru semnăturile digitale. Această schemă, care a ajuns să fie cunoscută pur și simplu ca Algoritmul de Semnătură Digitală (DSA), implică patru faze distincte:

1. Generarea cheilor:

   Cheile DSA sunt generate din:

   • 2 numere prime care îndeplinesc anumite reguli
     • $p$ - de obicei 256 de biți (vom numi această lungime $N$)
     • $q$ - de obicei 3072 de biți (vom numi această lungime $L$)
   • O funcție hash criptografică care va converti din șiruri de lungime $L$ la $N$
   • Un parametru suplimentar $g$ (vezi detaliile de mai jos)

   Din aceasta alegem un număr aleatoriu $x$ ca cheie privată și putem calcula o cheie publică $y$

   Detalii matematice ale generării cheilor

   • Generarea parametrilor: Din punct de vedere matematic, DSA implică un subgrup ciclic al lui $(\mathbb{Z}_p)^{\times}$ generat de un element $g$ de ordin prim q < p. Primul pas în DSA este prin urmare selectarea a două numere prime p, q pentru a stabili structurile matematice necesare.

     • Alege un număr prim $q$ de $N$ biți.
     • Alege un număr prim $p$ de $L$ biți astfel încât $p-1$ să fie un multiplu al lui $q$. Alegerea lui $p$ specifică grupul $(\mathbb{Z}_p)^{\times}$
     • Alege un număr întreg $1 < h < p-1$ aleatoriu și calculează $g = h^{(p-1)/q}~mod~p$. Dacă $g=1$, ceea ce se întâmplă rar, încearcă cu un alt h.
     • Verifică că $g^q~mod~p = 1$. g este astfel un generator al unui subgrup ciclic $\langle g \rangle$ al lui $(\mathbb{Z}_p)^{\times}$ de ordin prim q.

     Parametrii $(q, p, g)$ specifică o instanță a algoritmului și sunt informații publice. De obicei, $N \sim 256$ și $L \sim 3072$ în aplicațiile reale.

     Protocolul necesită, de asemenea, o funcție hash criptografică $H : \{0,1\}^L \rightarrow \{0, 1\}^N$ care mapează șiruri binare de $L$ biți la șiruri de $N$ biți, de exemplu, SHA-256.

   • Generarea perechii de chei: Semnatarul trebuie să genereze o pereche de chei pe partea sa.

     • Alege un număr întreg secret aleatoriu $x \in \{1,2...q-1\}$. $x$ este cheia privată.
     • Generează $y = g^{x}~mod~p$. $y$ este cheia publică a semnatarului.

2. Distribuirea cheilor:

   Următoarele informații sunt partajate cu oricine dorește să valideze o semnătură

   • Parametrii folosiți $(p,q,g)$ care descriu algoritmul
   • Funcția hash $H$
   • Cheia publică $y$

3. Semnarea:

   • Semnatarul poate acum semna un mesaj $m$. Semnătura rezultată este $(r,s)$
   • Mesajul și semnătura sunt acum trimise destinatarului

   Detalii matematice ale semnării unui mesaj

   Semnatarul semnează un mesaj $m$ astfel:

   • Alege un număr întreg secret k aleatoriu din $\{1,2...q-1\}$
   • Calculează $r = (g^k~mod~p)~mod~q$. În cazul rar când $r=0$, încearcă cu un alt k aleatoriu.
   • Calculează $s = (k^{-1} (H(m) + xr))~mod~q$. În cazuri rare dacă $s=0$, încearcă cu un alt k aleatoriu.
   • Semnătura este tuplul $(r, s)$.
   • Semnatarul transmite mesajul $m$ și semnătura $(r,s)$ verificatorului.

   Deoarece atât $r, s$ sunt numere întregi, modulo $q$ dimensiunea semnăturii este de ordinul a $N$ biți și nu a lungimii mai mari $L$ biți.

4. Verificarea:

   Destinatarul dorește acum să verifice autenticitatea expeditorului. Are acces la informațiile publice $(q, p, g, H, y, (r,s), m)$ Poate executa un calcul care dovedește că expeditorul a avut acces la cheia privată $x$

   și caută să stabilească că semnatarul este cineva cu acces la cheia privată $x$.

   Detalii matematice ale schemei de verificare DSA

   • Verifică că $0 \lt r \lt q$ și $0 \lt s \lt q$, adică $r, s$ sunt numere întregi valide modulo~q.
   • Calculează $w = s^{-1}~mod~q$.
   • Calculează $u_1 = H(m)w~mod~q$.
   • Calculează $u_2 = rw~mod~q$.
   • Calculează $v = (g^{u_1}y^{u_2}~mod~p)~mod~q$.
   • Semnătura este verificată dacă $v = r$.

   Pentru semnăturile legitime, corectitudinea algoritmului DSA se demonstrează ușor astfel:

   • Pe partea semnatarului: $s = (k^{-1} (H(m) + xr))~mod~q \implies k = ((H(m) + xr)s^{-1})~mod~q$
   • Considerând membrul drept al ultimei egalități, un verificator poate calcula $s^{-1}, H(m)$ deoarece $s, q, m, H$ sunt informații publice.
   • Astfel, verificatorul calculează $w = s^{-1}~mod~q$ și $u_1 = H(m)w~mod~q = H(m)s^{-1}~mod~q$.
   • Verificatorul calculează, de asemenea, $u_2 = rw~mod~q = rs^{-1}~mod~q$ deoarece $r$ este, de asemenea, public.
   • Observă că $k = (u_1 + xu_2)~mod~q$.
   • Cu toate acestea, un verificator nu are acces la $x$ deoarece este cheia privată a semnatarului, deci $k$ însuși nu poate fi calculat direct. Schema se bazează în schimb pe faptul că, chiar dacă verificatorul nu poate calcula $k$, cu un semnatar legitim, verificatorul ar trebui să poată recalcula $(g^k~mod~p)~mod~q = r$ cu ajutorul cheii publice a semnatarului $y = g^{x}~mod~p$.
   • Deci, verificatorul calculează $v = (g^{u_1}y^{u_2}~mod~p)~mod~q = (g^{u_1}g^{xu_2}~mod~p)mod~q = (g^{u_1+xu_2}~mod~p)mod~q = (g^k~mod~p)mod~q$.
   • Ultima egalitate urmează deoarece $g$ are ordinul $q$ și stabilește $v = r$ pentru semnăturile valide.

Ilustrarea DSA în Python

În acest exemplu, vom folosi numere prime mici pentru a ilustra procesul DSA într-un scenariu în care Alice trimite un mesaj semnat lui Bob. Vom folosi numere întregi mici în acest exemplu. Un scenariu real ar folosi numere prime mult mai mari, de ordinul a 2048-3072 de biți.

notă

Poți încerca să rulezi din nou acest exemplu cu valori diferite pentru a vedea cum se comportă algoritmul, dar asigură-te că începi rularea de la prima celulă din această secțiune.

Începem prin importarea bibliotecilor necesare și alegerea parametrilor noștri. Parametrii întregi $p$, $q$, $g$ sunt informații publice și satisfac următoarele reguli:

• $p$, $q$ sunt ambele prime
• $(p-1) \mod\ q = 0$
• $g \ge 2$
• $g \le (p-2)$
• $g^{(p-1)/q} \mod\ p \neq 1$

from random import randint

# parameter generation: select the primes q, p and generator g:
# EXPERIMENT with the values, they must meet certain rules
# this example code does not verify p,q are prime

q = 11
p = 23
g = 4

assert (p - 1) % q == 0
assert g >= 2
assert g <= (p - 2)
assert (pow(g, (p - 1) / q) % p) != 1

print(f"Public information is good: q={p}, p={q}, g={g}")

Urmează generarea cheii private de către semnatară, Alice.

Cheia privată, k (alice-private-key în codul python) trebuie să satisfacă:

• $k \ge 2$
• $k \le (q-1)$

# Alice chooses an integer randomly from {2..q-1}
# EXPERIMENT with the values

alice_private_key = randint(2, q - 1)
# alice_private_key =

assert alice_private_key >= 2
assert alice_private_key <= (q - 1)

print(f"Alice's private key is {alice_private_key}")

Alice își ține cheia privată secretă.

Urmează calcularea cheii publice de către Alice folosind exponențierea modulară. Inversarea acestui pas pentru a recupera cheia privată este o instanță a DLP, deci dificilă de calculat pe calculatoarele clasice unde se folosesc numere prime mari.

Din explicația matematică de mai sus, știm că aceasta poate fi calculată folosind formula:

$y = g^{x} \mod\ p$

alice_public_key = pow(g, alice_private_key, p)
# Alternatively can use (g ** alice_private_key) % p

print(f"Alice's public key is {alice_public_key}")

Ca de obicei, Alice face publică cheia sa publică printr-un canal nu neapărat secret.

Acum Alice poate semna un mesaj.

Pentru schema de semnătură digitală, trebuie să generăm un hash $H(m)$ al mesajului $m$ ce urmează a fi semnat.

Să presupunem că Alice și Bob convin să folosească un anumit algoritm de hashing cu lungimea hash-ului $N$ egală cu numărul de biți din $q$. În acest exemplu simplu, vom limita rezultatele funcției noastre mock de hash la $q$. Funcția hash de aici este trivială, generând pur și simplu un număr întreg aleatoriu.

hash_dict = {}

def mock_hash_func(input_message):
    print(input_message)
    if input_message not in hash_dict:
        hash_dict[input_message] = randint(1, q)
    return hash_dict[input_message]

alice_message = "Inspection tomorrow!"
alice_hash = mock_hash_func(alice_message)  # In reality, you'd use a hash function
print(f"Alice's message hash is: {alice_hash}")

Urmează generarea de către Alice a unui număr secret aleatoriu per mesaj $k$, cât și a inversului său multiplicativ modulo $q$ pentru a calcula semnătura.

Un algoritm simplu prin forță brută poate fi folosit pentru a calcula inversul modular. Totuși, este mai bine să folosești una dintre funcțiile Python încorporate pow, așa cum se arată mai jos.

# brute-force implementation to find modular inverse
def modular_inverse(k, q):
    for i in range(0, q):
        if (k * i) % q == 1:
            return i
    print(f"error! no inverse found! for {k},{q}")
    return 0

# Let's compare this algorithm with the standard python 'pow' function

n1 = modular_inverse(3, 7)
n2 = modular_inverse(4, 11)
n3 = modular_inverse(7, 5)
m1 = pow(3, -1, 7)
m2 = pow(4, -1, 11)
m3 = pow(7, -1, 5)

assert n1 == m1
assert n2 == m2
# assert(n3==m3)

print(f"modular_inverse(3,7) = {m1}")
print(f"modular_inverse(4,11) = {m2}")
print(f"modular_inverse(7,5) = {m3}")

# Some numbers don't have modular inverses - our function throws an error
n4 = modular_inverse(2, 6)

# The python library will throw an exception, which must be caught
if math.gcd(2, 6) == 1:
    m4 = pow(2, -1, 6)
else:
    print("Exception from pow() - no modular inverse found!")

Alice poate calcula acum semnătura.

• $r = (g^{k} \mod p) \mod\ q$
• $s = (k^{-1} (H(m) + xr)) \mod q$

Observă că există anumite condiții particulare care ne vor cere să alegem o valoare diferită pentru $k$ în cazul în care fie $r$, fie $s$ calculează la $0$. În acest caz vom genera o nouă valoare și vom repeta.

# Start an infinite loop; we will 'break' out of it once a valid signature is found.
while True:
    k = randint(1, q - 1)  # Should be different for every message
    print("Using random k =", k)

    r = pow(g, k, p) % q
    # If r is 0, the value is invalid. Try again with a new k.
    if r == 0:
        print(f"{k} is not a good random value to use to calculate r. Trying another k")
        continue

    s = (pow(k, -1, q) * (alice_hash + alice_private_key * r)) % q
    # If s is 0, the value is also invalid. Try again with a new k.
    if s == 0:
        print(f"{k} is not a good random value to use to calculate s. Trying another k")
        continue

    # If we've reached this point, both r and s are valid. Break the loop.
    signature = (r, s)
    print(f"Alice's signature is : {(r,s)}")
    break

# After the loop, the valid r and s values can be used here.
# print(f"Generated Signature -> r: {r}, s: {s}")

Alice transmite mesajul și semnătura sa destinatarului sau verificatorului, Bob.

Bob a interceptat anterior cheia publică a lui Alice și poate acum verifica semnătura pentru a-i autentifica mesajul.

Pentru aceasta, efectuează câteva verificări, apoi regenerează un hash al mesajului transmis de Alice și calculează cantitățile auxiliare $w, u_1, u_2$ și $v$.

• $0 < r < q$
• $0 < s < q$
• $w = s^{-1} \mod\ q$
• $u_{1} = H(m) . w \mod\ q$
• $u_{2} = r . w \mod\ q$
• $v = (g^{u1}y^{u2} \mod\ p) \mod\ q$

În final, Bob verifică dacă $v$ este egal cu $r$. Dacă sunt egale, semnătura este verificată.

# Bob re-generates message hash using Alice's broadcast message
bob_hash = mock_hash_func(alice_message)

# Bob computes auxiliary quantities w (using modular inverse), u1, u2 and v
w = (pow(s, -1, q)) % q
u1 = (bob_hash * w) % q
u2 = (r * w) % q
v = ((g**u1 * alice_public_key**u2) % p) % q

if v == r:
    print("Signature is valid!")
else:
    print("Signature is invalid!")

Securitatea DSA

Cu calculul clasic, securitatea DSA poate fi influențată de mai mulți factori:

1. Dimensiunea cheii: Ca întotdeauna, dimensiunea cheii oferă protecție de bază împotriva atacurilor prin forță brută. Aplicațiile moderne care folosesc DSA utilizează dimensiuni de cheie de cel puțin 2048 de biți.

2. Calitatea lui $k$: În DSA, fiecare semnătură are nevoie de o valoare $k$ unică, aleatorie și secretă (vezi mai sus). Unicitatea, entropia și secretul lui $k$ sunt critice, iar slăbiciunea în oricare dintre aceste aspecte ar putea duce la compromiterea cheii private $x$. Generatoarele de numere aleatoare folosite pentru generarea lui $k$ trebuie să fie ele însele securizate.

3. Robustețea funcției hash: Deoarece DSA folosește o funcție hash ca parte a procesului de generare și verificare a semnăturii, o funcție hash slabă ar putea compromite securitatea semnăturii digitale. De exemplu, utilizarea SHA-1 cu DSA este depreciată și se recomandă SHA-2 sau mai mare.

Pe lângă acestea, o implementare robustă a DSA ar trebui, de asemenea, să se protejeze împotriva altor tipuri de atacuri care vizează criptografia cu cheie asimetrică, așa cum s-a conturat anterior.

Schimbul de chei autentificat cu Diffie-Hellman și DSA

Protocoalele moderne de securitate a rețelelor, cum ar fi Transport Layer Security (TLS) și multe altele, implică combinarea funcționalităților de schimb de chei și autentificare. În contextul Diffie-Hellman, autentificarea este necesară pentru a proteja împotriva atacurilor MITM. În următoarele celule de cod, ilustrăm un exemplu în care Alice și Bob efectuează un schimb de chei autentificat combinând protocoalele Diffie-Hellman și DSA. Pentru aceasta, vom folosi biblioteca Python cryptography.

Figura 2. Schimb de chei autentificat cu Diffie-Hellman și DSA

Mai întâi, Alice și Bob convin asupra unui set de parametri DH și generează un set de perechi de chei publice-private DH.

# import necessary library modules
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import dh, dsa

# Generate DH parameters
parameters = dh.generate_parameters(generator=2, key_size=2048)

# Generate Alice's DH private key and public key
alice_dh_private_key = parameters.generate_private_key()
alice_dh_public_key = alice_dh_private_key.public_key()

# Generate Bob's DH private key and public key
bob_dh_private_key = parameters.generate_private_key()
bob_dh_public_key = bob_dh_private_key.public_key()

print("Public and private keys generated for Bob and Alice")

Cheile publice DH sunt transmise public. Apoi, atât Alice, cât și Bob generează fiecare o pereche separată de chei pentru utilizare cu DSA. Aceste chei vor fi folosite la rândul lor pentru a semna cheile publice DH care urmează să fie schimbate.

# Generate DSA keys for Alice and Bob
alice_dsa_private_key = dsa.generate_private_key(key_size=2048)
alice_dsa_public_key = alice_dsa_private_key.public_key()
bob_dsa_private_key = dsa.generate_private_key(key_size=2048)
bob_dsa_public_key = bob_dsa_private_key.public_key()

print("Additional key pair generated for signing")

Alice semnează cheia sa publică DH folosind cheia sa privată DSA.

# Alice signs
alice_public_bytes = alice_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
alice_signature = alice_dsa_private_key.sign(alice_public_bytes, hashes.SHA256())

print("Alice signed public key")

Similar, Bob semnează cheia sa publică DH folosind cheia sa privată DSA.

bob_public_bytes = bob_dh_public_key.public_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PublicFormat.SubjectPublicKeyInfo,
)
bob_signature = bob_dsa_private_key.sign(bob_public_bytes, hashes.SHA256())

print("Bob signed public key")

Cheile publice DH și semnăturile corespunzătoare sunt acum transmise public de ambii Alice și Bob. După ce au primit cheia publică și semnătura contrapartidei, fiecare parte verifică că semnătura este validă. Astfel, un atac MITM poate fi prevenit, deoarece Alice, de exemplu, știe că cheia publică DH a lui Bob a fost într-adevăr semnată de Bob și invers.

# Alice and Bob verify each other's DH public keys using DSA public keys
# An InvalidSignature exception will occur if they are not valid
alice_dsa_public_key.verify(alice_signature, alice_public_bytes, hashes.SHA256())
bob_dsa_public_key.verify(bob_signature, bob_public_bytes, hashes.SHA256())

print("Signatures are valid")

După verificarea semnăturii, Alice și Bob generează secretul partajat, ceea ce finalizează schimbul de chei.

# Perform key exchange
alice_shared_key = alice_dh_private_key.exchange(bob_dh_public_key)
bob_shared_key = bob_dh_private_key.exchange(alice_dh_public_key)

print("Shared secrets generated")

Opțional, pentru securitate suplimentară, Alice și Bob pot folosi o funcție specializată de derivare a cheilor, cum ar fi HKDF, pentru a genera o cheie simetrică mai sigură din secretul lor partajat folosind tehnici de extindere a cheilor.

# Derive a shared symmetric key using key-stretching
def derive_key(shared_key):
    return HKDF(
        algorithm=hashes.SHA256(),
        length=32,
        salt=None,
        info=None,
    ).derive(shared_key)

alice_symmetric_key = derive_key(alice_shared_key)
bob_symmetric_key = derive_key(bob_shared_key)

assert alice_symmetric_key == bob_symmetric_key
print("Keys checked to be the same")

Spargerea Diffie-Hellman și DSA

Atât protocoalele Diffie-Hellman (DH), cât și DSA implică generarea de chei publice de forma $y = g^{x}~mod~p$, unde cheia privată $x$ este logaritmul discret.

Un atacator care poate rezolva o instanță a DLP poate expune cheia privată a uneia dintre cele două părți și, combinând-o cu cheia publică a celei de-a doua părți, poate obține acces la secretul partajat. În cazul DSA, un atacator care poate rezolva DLP poate recupera cheia privată a semnatarului, anulând premisa de bază a unei semnături digitale.

Pe sistemele de calcul clasice, se consideră că DLP nu are o soluție în timp polinomial. Dar, așa cum a demonstrat Peter Shor în lucrarea sa originală din 1994, algoritmul lui Shor rezolvă și DLP în timp polinomial pe calculatoarele cuantice.

Algoritmul lui Shor și problema logaritmului discret

Algoritmul lui Shor este capabil să rezolve problema logaritmului discret în timp polinomial. Își atinge eficiența în principal prin utilizarea algoritmilor cuantici care pot găsi perioada unei funcții ce depinde de intrarea problemei — care este combinată apoi cu operații mai convenționale.

Detalii matematice ale algoritmului lui Shor

Algoritmul lui Shor oferă o soluție eficientă la DLP mapând-o la o problemă mai generală în teoria grupurilor, cunoscută sub numele de problema subgrupului ascuns (HSP).

În HSP, este dat un grup algebric $G$ și o funcție $f: G \rightarrow X$ de la $G$ la o mulțime $X$ astfel încât $f$ este constantă pe fiecare coset al unui subgrup $H$ al lui $G$ (și distinctă pe coset-uri diferite). Sarcina este să se determine $H$. Se știe că calculatoarele cuantice pot rezolva HSP pe grupuri Abeliene finite în timp polinomial în $log~|G|$ unde $|G|$ este ordinul grupului.

În cazul DLP întreg discutat în această lecție, maparea la HSP este următoarea:

• Fie $p$ un număr prim și consideră DLP dat de $y = g^r~mod~p$ unde $g$ este un generator al lui $(\mathbb{Z}_p)^{\times}$. Deoarece $g^{p-1} \equiv 1~mod~p$, $g$ are ordinul $p-1$.
• Alege $G = \mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$ unde $\mathbb{Z}_{p-1}$ este grupul numerelor întregi modulo $(p-1)$.
• Alege $f : G \rightarrow (\mathbb{Z}_p)^{\times}$ dat ca $f(a, b) = g^a y^{-b}~mod~p \equiv g^{a-rb}~mod~p$ .
• Nucleul lui $f$ este atunci subgrupul $H_0 = \langle (r, 1) \rangle = \{(a,b) \in G | f(a,b) \equiv 1~mod~p\} = \{ (a, b) \in G | a - rb \equiv 0~mod~(p-1)\}$.
• $f$ este constantă pe coset-urile $(\delta, 0) + H_0$ și „ascunde" subgrupul $H_0$ configurând un HSP.

Dat cele de mai sus, algoritmul cuantic al lui Shor pentru DLP întreg folosește un oracol cuantic pentru a evalua funcția $f$ pe o stare reprezentând o superpoziție uniformă peste $G$, și apoi folosește transformata Fourier cuantică și măsurători cu estimarea de fază pentru a produce stări cuantice care permit identificarea generatorului $(r, 1)$ al lui $H_0$. Din aceasta, $r$, logaritmul discret de interes, poate fi extras.

Lucrarea originală a lui Shor conține o descriere detaliată a algoritmului.

Criptografia cu curbe eliptice

Criptografia cu curbe eliptice (ECC), bazată pe matematica curbelor eliptice, oferă o abordare puternică a criptografiei cu cheie asimetrică. ECC este cunoscută pentru că oferă un nivel de securitate similar cu metode precum RSA, dar cu chei mai scurte, ceea ce o face mai eficientă și deosebit de potrivită pentru sisteme cu resurse limitate, cum ar fi sistemele incorporate și dispozitivele mobile, unde economiile de stocare și calcul oferite de dimensiunile mai mici ale cheilor sunt foarte dezirabile.

Principii de bază ale criptografiei cu curbe eliptice

O curbă eliptică are de obicei forma $y^2 = x^3 + ax + b$ și prezintă câteva proprietăți interesante.

• Este simetrică față de axa orizontală. Astfel, pentru orice punct $(x,y)$ de pe curbă, reflecția sa $(x,-y)$ se află de asemenea pe curbă
• Orice dreaptă non-verticală va intersecta curba în cel mult trei puncte

Figura 1. Operații de adunare și dublare a punctelor pe o curbă eliptică. Fațeta 1 definește P + Q = -R. Fațeta 2 ilustrează dublarea punctului 2Q = -P. Fațeta 3 definește inversul aditiv al unui punct ca reflecția sa față de axa x, adică P = -Q

Criptografia cu curbe eliptice folosește aplicarea unei serii de operații aritmetice asupra punctelor de pe curbă. Fiecare operație navighează efectiv spre un nou punct de pe curbă. Acesta este un proces simplu de urmat într-o direcție și, cu dimensiuni mai mici ale cheilor, este mai eficient decât alți algoritmi precum RSA, dar inversarea sa este foarte dificilă, de unde și aplicarea sa în criptografie.

Principii matematice ale criptografiei cu curbe eliptice

O curbă eliptică peste un câmp algebric $K$ este definită printr-o ecuație matematică, de obicei de forma $y^2 = x^3 + ax + b$ cu coeficienții $a, b \in K$ și descrie punctele $(x, y) \in K \otimes K$, cu cerința suplimentară ca respectiva curbă să nu aibă colțuri sau auto-intersecții.

Proprietățile curbelor eliptice permit definirea operațiilor de „adunare" și „înmulțire scalară" implicând puncte de pe curbă.

Adunarea: Dacă $P$ și $Q$ sunt două puncte pe o curbă eliptică, atunci $P + Q$ descrie un al treilea punct unic identificat astfel: se trasează dreapta care intersectează $P$ și $Q$ și se găsește al treilea punct, $R$, în care dreapta intersectează din nou curba. Definim apoi $P + Q = −R$, punctul opus lui $R$ reflectat față de axa $x$ (a se vedea figura de mai jos). Când dreapta ce trece prin $P, Q$ nu intersectează curba în niciun $(x, y)$ finit, spunem că intersectează curba în punctul de la infinit $\mathbf{O}$.

Adunarea pe curbe eliptice satisface proprietățile algebrice de grup, cu punctul de la infinit ca element neutru aditiv.

Dublarea și înmulțirea scalară: Operația de dublare a punctului, care corespunde înmulțirii scalare cu $2$, se obține prin setarea $P = Q$ în operația de adunare și implică grafic tangenta în $P$. Înmulțirea scalară generală cu un număr întreg $n$, definită ca $nP = P + P + ...~n$ ori, se obține prin dublare și adunare repetate.

Problema logaritmului discret pe curbe eliptice

Problema logaritmului discret pe curbe eliptice (ECDLP) are multe similarități cu problema logaritmului discret discutată anterior, bazându-se pe dificultatea găsirii factorilor.

Operația de înmulțire scalară pe curbe eliptice permite definirea problemei logaritmului discret pe curbe eliptice:

Dat fiind punctele $P, Q$ pe o curbă eliptică astfel încât $Q = nP$, determină $n$.

Se știe că această problemă este intractabilă pe calculatoarele clasice pentru $n$ mare și oferă o bază pentru securitatea criptografică.

Descrierea matematică a ECDLP

Criptografia cu curbe eliptice se bazează în principal pe ECDLP formulată pe anumite câmpuri finite algebrice. În 1999, NIST a recomandat zece câmpuri finite pentru utilizare în ECC. Acestea sunt:

• Cinci câmpuri prime $\mathbb {F} _{p}$ pentru prime $p$ de dimensiune $\{192, 224, 256, 384, 521\}$ biți.
• Cinci câmpuri binare $\mathbb {F} _{2^{n}}$ pentru $n \in \{163, 233, 283, 409, 571\}$.

Cu configurația de mai sus, un criptosistem cu cheie asimetrică bazat pe ECC în cazul câmpurilor prime poate fi specificat astfel:

• Se alege un $p$ din lista de valori recomandate de NIST pentru a specifica $\mathbb {F} _{p}$.

• Se selectează parametrii $a, b$ ai curbei eliptice.

• Se alege un punct de bază $G$ care „generează" un subgrup ciclic pe curbă cu ordinul $n$; adică cel mai mic număr întreg astfel încât $nG = \mathbf{O}$.

• Se calculează cofactorul $h = |E(\mathbb {F} _{p})|/n$, unde $|E(\mathbb {F} _{p})|$ este numărul de puncte de pe curbă. $h$ este de obicei un număr întreg mic.

• Parametrii de domeniu $(p, a, b, G, n, h)$ permit specificarea cheilor asimetrice în acest mod:

  • Cheia privată este un număr întreg ales aleatoriu $d$ cu același număr de biți ca numărul prim $p$. Trebuie păstrată secretă.
  • Cheia publică este rezultatul „înmulțirii" punctului de bază $G$ cu cheia privată $d$. Aceasta este de obicei notată ca $Q = dG$.

Recuperarea lui $d$ este echivalentă cu rezolvarea ECDLP, care se presupune a fi intractabilă pentru $d$ mare. Prin urmare, ECDLP formează baza pentru schemele de schimb de chei și semnătură digitală, prin analogie directă cu schemele Diffie-Hellman și DSA definite peste $(\mathbb{Z}_p)^{\times}$ discutate anterior.

Schimbul de chei cu ECC

Una dintre utilizările principale ale ECC este în protocolul de schimb de chei cunoscut sub numele de Diffie-Hellman pe curbe eliptice (ECDH). În ECDH, fiecare parte generează o pereche de chei privat-public și apoi schimbă cheile publice. Fiecare parte folosește apoi propria cheie privată și cheia publică a celeilalte părți pentru a calcula un secret comun, care poate fi utilizat ca și cheie pentru criptarea simetrică.

Deși este relativ ușor să efectuezi adunarea de puncte pe o curbă eliptică și să derivezi o cheie publică dintr-o cheie privată, este imposibil din punct de vedere computațional să inversezi procesul și să derivezi cheia privată din cheia publică. Acest comportament „unidirecțional" asigură securitatea schimbului de chei ECDH.

Aici vom ilustra un exemplu de cum ai putea efectua un schimb de chei ECDH folosind Python și biblioteca cryptography.

from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.primitives import hashes

# Each party generates a private key
private_key1 = ec.generate_private_key(ec.SECP384R1())
private_key2 = ec.generate_private_key(ec.SECP384R1())

# They exchange public keys
public_key1 = private_key1.public_key()
public_key2 = private_key2.public_key()

# Each party uses their own private key and the other party's public key
# to derive the shared secret
shared_key1 = private_key1.exchange(ec.ECDH(), public_key2)
shared_key2 = private_key2.exchange(ec.ECDH(), public_key1)

# The shared secrets are the same
assert shared_key1 == shared_key2
print("Keys checked to be the same")

Semnături digitale cu ECC

ECC poate fi folosită și pentru a genera semnături digitale utilizând Algoritmul de Semnătură Digitală pe Curbe Eliptice (ECDSA). În ECDSA, semnatarul creează o semnătură folosind cheia sa privată, iar alții pot verifica semnătura folosind cheia publică a semnatarului. La fel ca în cazul ECDH, securitatea ECDSA se bazează pe ECDLP. Este imposibil din punct de vedere computațional ca cineva să falsifice o semnătură fără acces la cheia privată a semnatarului.

Mai jos este un exemplu de tranzacție simplă de semnare și verificare folosind ECDSA cu Python și cryptography.

from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import ec

# Generate a private key for use in the signature
private_key = ec.generate_private_key(ec.SECP384R1())

message = b"A message to be signed"

# Sign the message
signature = private_key.sign(message, ec.ECDSA(hashes.SHA256()))

# Anyone can verify the signature with the public key
public_key = private_key.public_key()

def check_ecdsa_signature(public_key, signature, message):
    try:
        public_key.verify(signature, message, ec.ECDSA(hashes.SHA256()))
        return True
    except InvalidSignature:
        return False

if check_ecdsa_signature(public_key, signature, message):
    print("The signature is valid.")
else:
    print("The signature is invalid.")

În codul de mai sus, dacă modifici mesajul după ce a fost semnat, verificarea va eșua, oferind o garanție de autenticitate și integritate pentru mesaj.

Spargerea ECDH și ECDSA

Într-un mod analog cu problema logaritmului discret pe numere întregi, ECDLP se dovedește a fi dificilă pe calculatoarele clasice, dar are o soluție eficientă pe calculatoarele cuantice, din nou prin algoritmul lui Shor. Te îndreptăm spre literatura recentă pentru o discuție referitoare la generalizarea algoritmului lui Shor la cazul ECDLP.

Rezumat

În această lecție, am început prin a examina caracteristicile principale ale criptografiei cu cheie asimetrică (AKC) și am discutat considerațiile de securitate de bază care stau la temelia criptosistemelor asimetrice. În special, am introdus cele două aplicații principale ale AKC — și anume, schimbul de chei și semnăturile digitale — ambele fiind componente esențiale ale comunicațiilor moderne bazate pe internet.

Am examinat apoi criptosistemul RSA, care din anii 1970 s-a dovedit a fi de o valoare imensă pentru securizarea comunicațiilor digitale moderne, permițând schimbul de chei și semnăturile digitale într-un cadru simplu și versatil. Securitatea criptografică a RSA față de calculul clasic se bazează pe dificultatea factorizării numerelor întregi mari și necesită dimensiuni ale cheilor de ordinul a 2048 de biți pentru a asigura că numerele întregi utilizate în aplicațiile practice sunt suficient de mari pentru a rezista factorizării.

Am examinat apoi schimbul de chei Diffie-Hellman (DH) și Algoritmul de Semnătură Digitală (DSA). Securitatea acestor scheme se bazează pe problema logaritmului discret pe numere întregi (DLP), cheia privată fiind greu de extras din punct de vedere computațional din cheia publică, fără o soluție în timp polinomial pe calculatoarele clasice. Utilizarea cheilor aleatoare și unice oferă securitate suplimentară împotriva atacurilor. Atât varianta câmpului finit de numere întregi, cât și varianta curbei eliptice ale protocoalelor DH și DSA sunt utilizate în prezent pe scară largă în multe protocoale moderne de comunicații digitale, cum ar fi TLS, SSH și altele.

În final, am examinat criptografia cu curbe eliptice. Cu dimensiunea eficientă a cheilor și proprietățile sale puternice de securitate, aceasta reprezintă în prezent o alegere excelentă pentru multe aplicații criptografice, de la schimbul de chei până la semnăturile digitale.

Toți acești algoritmi sunt expuși la atacuri din partea algoritmilor cuantici, deoarece pot fi dezvoltate soluții pentru rezolvarea problemelor matematice care au stat la baza proiectării lor. Un astfel de exemplu este algoritmul lui Shor. Prin urmare, vor trebui înlocuiți cu criptosisteme asimetrice sigure cuantic, care sunt mai rezistente la atacurile cuantice, menținând în același timp securitatea față de algoritmii clasici. Problemele matematice de care se bazează pot fi rezolvate eficient de calculatoarele cuantice, necesitând dezvoltarea unor criptosisteme asimetrice sigure cuantic care să reziste atacurilor cuantice, menținând în același timp securitatea clasică.

O lecție viitoare va examina criptosistemele sigure cuantic și va discuta abordarea necesară pentru a menține securitatea criptografică.