ABONAMENTE VIDEO REDACȚIA
RO
EN
×
▼ LISTĂ EDIȚII ▼
Numărul 89
Abonament PDF

Criptografie: Alice and Bob strike again

Daniel Butean
Software developer @ Siemens



Alex Ghiran
Software developer @ Siemens



Călin Manea
Java developer @ Siemens
PROGRAMARE

Un exercițiu de imaginație prin care devenim personajul principal în seria James Bond, (adică ,,Bond. James Bond"), ne poate facilita înțelegerea optimă a complexului domeniu al criptografiei. Așadar... Suntem în pielea lui James Bond pentru câteva minute. Am primit dosarele a două personaje deosebite, Alice și Bob. Aceștia sunt suspecții care au mereu ceva de ascuns și se fac nevăzuți când cineva e pe urmele lor. După eforturi considerabile, am reușit să interceptăm canalul lor de comunicare, iar acum avem acces la discuțiile lor. Trebuie să aflam ce pun la cale, dar înainte, haideți să punem problema în context.

Criptografia se referă la procesul de encoding (codare) și decoding (decodare) a unui mesaj utilizând un algoritm, cu scopul de a proteja conținutul mesajului față de persoanele neautorizate. Algoritmii criptografici se bazează pe o cheie criptografică (cryptographic key) cunoscută ambelor părți, dar necunoscută publicului. Această cheie este folosită în procesul de criptare și de decriptare a mesajului.

Pentru ca algoritmii să funcționeze această cheie trebuie schimbată înainte ca cei doi interlocutori să intre în contact. O astfel de metodă stă la baza criptografiei simetrice (symmetric cryptography)[1]. Un aspect problematic al acestei abordări se referă la necesitatea utilizării unui mecanism securizat pentru transmiterea cheilor. O astfel de metodă este complicat de implementat în condițiile în care comunicarea se face pe Internet între interlocutori care nu se cunosc în prealabil.

O altă metodă prezentată în acest articol este utilizarea unei chei private, care nu trebuie comunicată celorlalți interlocutori. În acest fel, un shared secret key (o cheie secretă folosită de ambele părți) este construit de un interlocutor folosind cheia sa privată și cheia publică a celuilalt. Această abordare se numește criptare asimetrică (asymmetric cryptography) sau public-key cryptography[2] și face parte din algoritmii folosiți pentru securizarea comunicării în unele protocoale moderne precum SSH și SSL/TLS.

Să ne întoarcem la Alice și Bob. Se pare că există ceva activitate…

Alice: Bob, cred că acest canal de comunicare nu mai este sigur.

Bob: Trebuie să ne criptăm mesajele. Pentru o criptare simetrică avem nevoie de o cheie comună.

Alice: Dar nu putem să alegem această cheie direct, pentru că acest canal de comunicare nu este sigur. Așa că vom proceda astfel:

Bob: Ok, voi face și eu la fel:

Alice: Mulțumesc, Bob. Acum voi calcula următoarea valoare: formS_B Te rog să faci la fel folosind valoarea lui A,pe care ți-am trimis-o și numărul tău secret b: formS_A și S va fi cheia noastră comună, pe care o vom folosi pentru a cripta mesajele viitoare!

La finalul acestei transmisii să facem un rezumat al informațiilor interceptate:

În primul rând, să vedem dacă această metodă funcționează și anume dacă Alice și Bob au ajuns la aceeași valoare pentru S(shared password).

Astfel, Alice a ajuns la:

eq1

iar Bob la:

eq2

Prin urmare, Alice și Bob au ajuns la aceeași valoare pentru cheia comună.

Pentru aflarea shared key, S, avem nevoie să determinăm valorile cheilor private a și b. Pentru exemplul de mai sus durează câteva secunde să ajungem la a

Timpul necesar pentru această operație crește exponențial în funcție de p, a și b. De exemplu, să presupunem că folosim o abordare brute force pentru a găsi cheile private:

Să presupunem că a și b sunt generate aleatoriu (dar valorile lor sunt mai mici decât p), iar p și g (primitive root modulo p)[3,4,5] utilizate în generarea shared key, S, sunt:

număr de biți p g număr de biți p g
3 5 3 11 1831 3
4 13 2 12 3319 6
5 19 3 13 6547 2
5 23 5 14 9817 5
6 61 2 15 16493 2
7 103 5 16 26449 7
8 233 3 16 44123 2
9 419 2 17 83987 2
10 797 2 18 231529 17
10 1013 3 19 400871 7

Folosind aceste date, se poate observa că timpul necesar pentru aflarea lui a, b și S crește exponențial în funcție de valoarea lui p.

Nivelul de securitate al acestei metode poate fi crescut prin schimbarea regulată a lui g și p.

Diffie - Hellman key exchange

Algoritmul criptografic descris mai sus se numește Diffie - Hellman key exchange[6]. Whitfield Diffie și Martin Hellman au publicat această metodă în 1976. Diffie - Hellman key exchange reprezintă un exemplu foarte simplu de criptare asimetrică. A și B sunt cheile publice pe care Alice și Bob le-au trimis pe un canal de comunicare nesecurizat. Cheile private a și b nu sunt dezvăluite nimănui. Cel mai important rol în acest algoritm îl joacă funcția modulo. Această funcție este foarte ușor de calculat, dar necesită un efort mult mai mare pentru calcularea funcției inverse. Codurile criptografice complexe moderne combină mai mulți algoritmi pentru a asigura securitatea unui canal de comunicare, iar Diffie - Hellman key exchange rămâne, încă, o componentă importantă a acestora și a criptografiei moderne.

Calculatoarele cuantice ar putea schimba regulile jocului

În teorie este posibilă determinarea cheii private folosind cheia publice, pe baza relației matematice dintre aceste valori, dar în practică acest lucru nu este fezabil. Algoritmii pentru criptare asimetrică utilizează metode care fac ca timpul pentru determinarea cheilor să crească exponențial. Acești algoritmi folosesc numere foarte mari, de ordinul a sute de cifre, astfel încât determinarea lor devine practic imposibilă. Totuși, calculatoarele cuantice ar putea, teoretic, să facă această determinare realizabilă în viitor[7].

Bibliografie

  1. Symmetric-key algorithm - Wikipedia
  2. Public-key cryptography - Wikipedia
  3. Primitive root modulo n - Wikipedia
  4. A000040 - OEIS - The prime numbers
  5. A046145 - OEIS - Smallest primitive root modulo n
  6. Diffie-Hellman key exchange - Wikipedia
  7. Quantum Computing Poses An Existential Security Threat, But Not Today

Sponsori

  • comply advantage
  • ntt data
  • 3PillarGlobal
  • Betfair
  • Telenav
  • Accenture
  • Siemens
  • Bosch
  • FlowTraders
  • MHP
  • Connatix
  • UIPatj
  • MetroSystems
  • Globant
  • Colors in projects