ABONAMENTE VIDEO REDACȚIA
RO
EN
NOU
Numărul 125
Numărul 124 Numărul 123 Numărul 122 Numărul 121 Numărul 120 Numărul 119 Numărul 118 Numărul 117 Numărul 116 Numărul 115 Numărul 114 Numărul 113 Numărul 112 Numărul 111 Numărul 110 Numărul 109 Numărul 108 Numărul 107 Numărul 106 Numărul 105 Numărul 104 Numărul 103 Numărul 102 Numărul 101 Numărul 100 Numărul 99 Numărul 98 Numărul 97 Numărul 96 Numărul 95 Numărul 94 Numărul 93 Numărul 92 Numărul 91 Numărul 90 Numărul 89 Numărul 88 Numărul 87 Numărul 86 Numărul 85 Numărul 84 Numărul 83 Numărul 82 Numărul 81 Numărul 80 Numărul 79 Numărul 78 Numărul 77 Numărul 76 Numărul 75 Numărul 74 Numărul 73 Numărul 72 Numărul 71 Numărul 70 Numărul 69 Numărul 68 Numărul 67 Numărul 66 Numărul 65 Numărul 64 Numărul 63 Numărul 62 Numărul 61 Numărul 60 Numărul 59 Numărul 58 Numărul 57 Numărul 56 Numărul 55 Numărul 54 Numărul 53 Numărul 52 Numărul 51 Numărul 50 Numărul 49 Numărul 48 Numărul 47 Numărul 46 Numărul 45 Numărul 44 Numărul 43 Numărul 42 Numărul 41 Numărul 40 Numărul 39 Numărul 38 Numărul 37 Numărul 36 Numărul 35 Numărul 34 Numărul 33 Numărul 32 Numărul 31 Numărul 30 Numărul 29 Numărul 28 Numărul 27 Numărul 26 Numărul 25 Numărul 24 Numărul 23 Numărul 22 Numărul 21 Numărul 20 Numărul 19 Numărul 18 Numărul 17 Numărul 16 Numărul 15 Numărul 14 Numărul 13 Numărul 12 Numărul 11 Numărul 10 Numărul 9 Numărul 8 Numărul 7 Numărul 6 Numărul 5 Numărul 4 Numărul 3 Numărul 2 Numărul 1
×
▼ 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:

iar Bob la:

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

VIDEO: NUMĂRULUI 125

Sponsori

  • BT Code Crafters
  • Accesa
  • Bosch
  • Betfair
  • MHP
  • Connatix
  • BoatyardX
  • AboutYou
  • Colors in projects

VIDEO: EXTRA