Criptografie (4) - Algoritmul RSA (Rivest-Shamir-Adleman)

Descrierea algoritmului RSA (Rivest-Shamir-Adleman)

Algoritmul RSA (Rivest-Shamir-Adleman) a fost introdus în 1977 de către trei criptografi americani: Ron Rivest, Adi Shamir și Leonard Adleman. Această metodă de criptare a fost revoluționară și a adus contribuții semnificative la domeniul criptografiei, oferind o soluție eficientă pentru problemele de securitate legate de schimbul de chei în comunicațiile securizate.

Iată o scurtă istorie a algoritmului RSA:

• Anii 1970: Fondarea RSA:

  • În 1973, Whitfield Diffie și Martin Hellman au introdus conceptul de schimb de chei cu cheie publică (public-key cryptography), marcând un avans major în criptografie.
  • În 1977, Rivest, Shamir și Adleman au publicat articolul "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" în care au descris algoritmul RSA.

• Inovația Cheilor Publice și Private:

  • Algoritmul RSA este notabil pentru introducerea conceptului de pereche de chei: una publică, folosită pentru criptare, și una privată, folosită pentru decriptare.
  • Securitatea algoritmului se bazează pe dificultatea factorizării unui număr mare în produsul a două numere prime mari.

• Popularizarea în Criptografie:

  • Datorită eficienței și securității sale teoretice, algoritmul RSA a devenit rapid popular și a fost adoptat ca standard în domeniul criptografiei.
  • A devenit esențial în protocolul SSL/TLS, folosit în securizarea comunicațiilor pe internet.

• Contribuții ulterioare:

  • De-a lungul anilor, au existat variante și îmbunătățiri ale algoritmului RSA, dar conceptul de bază al criptării asimetrice cu chei publice și private a rămas neschimbat.

• RSA în Zilele Noastre:

  • Algoritmul RSA rămâne unul dintre cele mai utilizate și studiate metode de criptare.
  • Cu toate acestea, cu avansul tehnologiei și cu creșterea puterii de calcul, lungimile cheilor trebuie ajustate pentru a menține un nivel adecvat de securitate.

Algoritmul RSA a jucat un rol semnificativ în evoluția securității informațiilor și a comunicării online și rămâne un element esențial în domeniul criptografiei moderne.

 Cum funcționeză ?

RSA (Rivest-Shamir-Adleman) este un algoritm de criptare și decriptare cu chei publice. Acesta utilizează o pereche de chei: o cheie publică, care poate fi distribuită liber, și o cheie privată, care trebuie păstrată secretă.

Iată o descriere a pașilor algoritmului RSA:

• Generarea Cheilor:

  • Se aleg două numere prime mari, notate p și q.
  • Se calculează produsul p * q, notat n. Acesta va fi folosit ca un modul în algoritmul RSA.
  • Se calculează funcția totient, φ(n) = (p-1) * (q-1).

• Alegerea Cheii Publice:

  • Se alege un exponent de exponențiere public, notat e, astfel încât 1 < e < φ(n) și e este relativ prim față de φ(n) (nu are alți divizori comuni cu φ(n) în afară de 1).

• Calculul Cheii Private:

  • Se calculează exponentul de exponențiere privat, notat d, astfel încât (d * e) mod φ(n) = 1. Practic, d este inversul modular al lui e în raport cu φ(n).

• Distribuirea Cheii Publice:

  • Cheia publică constă în perechea (n, e) și poate fi distribuită liber.

• Criptarea:

  • Mesajul M pe care vrei să-l criptezi este reprezentat ca un număr întreg, iar operația de criptare este:
    
  • C ≡ M^e (mod n).

• Decriptarea:

  • Mesajul criptat C este decriptat cu ajutorul cheii private d, folosind operația:
  • M ≡ C^d (mod n).

Cheia publică poate fi folosită de oricine pentru a cripta mesaje către posesorul cheii private, dar numai posesorul cheii private poate decripta aceste mesaje. Această asimetrie în capacitatea de criptare și decriptare oferă securitate și confidențialitate.

Este important de menționat că RSA are o lungime de cheie asociată (de exemplu, 2048 biți sau 3072 biți), iar securitatea algoritmului este strâns legată de lungimea cheii. Cu cât cheia este mai lungă, cu atât este mai rezistent algoritmul la diverse atacuri criptografice.

Accelerare hardware

Acceleratorul RSA oferă suport hardware pentru calculul de înaltă precizie utilizat în diverși algoritmi de criptare asimetrică RSA, îmbunătățind semnificativ timpul lor de execuție și reducând complexitatea software-ului asociat. De asemenea, acceleratorul RSA susține operații cu operanzi de lungimi diferite, oferind astfel o mai mare flexibilitate în timpul calculului. Spre exemplu placa ESP32 C6 oferă acest feature și suportă accelerare hardware pentru RSA.

Schema algoritmului RSA

Sursa: https://www.researchgate.net/figure/Figure-213-The-RSA-Algorithm_fig12_328828460

Implementare

• https://github.com/SimedruF/Simple_RSA/tree/main

 La implementare am folosit o bibliotecă foarte cunoscută pentru interfețe GUI numita Dear Imgui, iar rezultatul se poate observa în imaginea de mai jos.

Pentru a compila această aplicație o să aveți nevoie de cl.exe (compilerul de linie de comandă C/C++) din suita Visual Studio. In batch-ul care executa compilarea am adăugat și apelul către utilitarul "...\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat" care setează variabilele de environment pentru a putea executa direct compilatorul, și probabil o să fie nevoie să ajustați calea către acest utilitar.

Bonus - Cum se poate compila o aplicație care folosește ImGui in RaspberyPi OS (Linux)

Documentație

• https://en.wikipedia.org/wiki/RSA_(cryptosystem)
• https://www.geeksforgeeks.org/rsa-algorithm-cryptography/
• https://blog.espressif.com/build-affordable-secure-connected-devices-with-esp32-h2-b8d542df8cb4 
• https://github.com/ocornut/imgui 

Mulțumesc pentru atenție! Pentru întrebări și/sau consultanță tehnică vă stau la dispoziție pe blog mai jos în secțiunea de comentarii sau pe email simedruflorin@automatic-house.ro.
O zi plăcută tuturor !
Back to top of page