Note de curs, clasele 11-12, 29 mai 2014

From Algopedia
Jump to navigationJump to search

Algoritmi de compresie (încheiere)

Vom continua de unde am rămas ora trecută:

  • detalii de implementare pentru algoritmul LZW
  • algoritmul LZ-77

Criptografie

Algebră modulară

Toți algoritmii de criptare comuni folosesc proprietăți ale algebrei modulare. Vom prezenta, foarte pe sărite, câteva proprietăți care ne vor fi utile.

Grupuri

Un grup (G, +) este o pereche formată dintr-o mulțime și o operație pe acea mulțime care, împreună, întrunesc patru proprietăți: închiderea, asociativitatea, elementul neutru și elementele inverse. Grupurile care, în plus, respectă și proprietatea de comutativitate se numesc grupuri comutative sau abeliene.

De interes particular pentru criptografie sunt grupurile:

  • (Zn, +), unde Zn = {0, 1, ..., n - 1}
  • (Zn*, ∙), unde Zn* = { aZn | gcd(a, n) = 1 }

Divizibilitate

Propoziție: dacă d | a și d | bd | (ax + by).

Teoremă: gcd(a, b) este cel mai mic element pozitiv al mulțimii {ax + by}. Schiță de demonstrație: Fie s minimul pozitiv al acelei mulțimi și fie s = ax + by pentru niște valori x și y. Trebuie să arătăm că s ≤ gcd(a, b) și că gcd(a, b) | s.

De aici decurg 3 corolare utile:

  • dacă d | a și d | b ⇒ d | gcd(a, b)
  • gcd(na, nb) = n gcd(a, b)
  • dacă n | ab și gcd(n, a) = 1 ⇒ n | b. Schiță de demonstrație: ax + ny = 1abx + nby = b ⇒ b mod n = 0.

Algoritmul lui Euclid extins

Pe lângă d = gcd(a, b), algoritmul lui Euclid extins calculează și cele două numere x și y astfel încât d = ax + by.

Anexez media:extendedEuclid.cpp pentru o implementare recursivă și una iterativă.

Algoritmul lui Euclid extins poate fi folosit pentru a afla inversele elementelor în Zn*. Pentru a calcula inversul lui a, aplicăm algoritmul lui Euclid extins pentru a și n. Prin definiție gcd(a, n) = 1, deci fie x și y a. î. ax + ny = 1. Rezultă în mod trivial că ax ≡ 1 (mod n), deci x este inversul lui a.

Mica teoremă a lui Fermat

Pentru orice p prim și orice a întreg,

Iată o demonstrație elegantă, numită „metoda mărgelelor”. Să considerăm toate colierele de lungime p mărgele, folosind mărgele de a culori. Evident, există ap coliere distincte. Acum să le eliminăm pe cele a formate din mărgele de o singură culoare. Trebuie să demonstrăm că cele ap - a rămase pot fi grupate câte p, fără rest. Putem face aceasta grupând fiecare colier cu cele p rotații ale sale. Deoarece p este prim, știm sigur că există exact p rotații (niciun colier nu este format din x copii a câte y mărgele).

Generalizarea acestei teoreme este teorema lui Euler: Pentru orice n > 1 și orice a,

Teorema chinezească a resturilor

Fie , unde factorii sunt primi între ei. Pentru orice număr calculăm . Atunci corespondența

este bijectivă.

Nu demonstrăm această teoremă, dar iată un exemplu pentru n = 35 = 5 x 7

x 0 1 2 3 4 5 6
0 0 15 30 10 25 5 20
1 21 1 16 31 11 26 6
2 7 22 2 17 32 12 27
3 28 8 23 3 18 33 13
4 14 29 9 24 4 19 34

În particular, observăm că dacă , atunci

Noțiuni de criptografie

Nevoia de algoritmi criptografici apare atunci când două persoane doresc să comunice în secret. În particular, să considerăm că Alice vrea să îi transmită lui Bob un cufăr cu secrete. Presupunem că Alice și Bob au lacăte cu chei unice, imposibil de spart, iar cufărul însuși este imposibil de spart. Metoda naivă (Alice îi trimite lui Bob un cufăr încuiat, precum și cheia pentru lacăt) nu funcționează decât dacă corespondenții au încredere în curier și în siguranța transportului. Iată două metode care funcționează:

  1. Alice îi trimite lui Bob cufărul încuiat, fără cheie. Bob aplică propriul lacăt pe cufăr și îl trimite înapoi. Alice scoate lacătul său și retrimite cufărul. Bob scoate lacătul său și deschide cufărul.
  2. Bob îi trimite lui Alice un lacăt deschis prin poștă (dar păstrează cheia). Alice aplică lacătul și trimite cufărul. Bob deschide lacătul cu cheia pe care a păstrat-o.

Frumusețea acestor metode este că folosesc un canal public pentru a stabili un mod de comunicare privată. La niciun moment cufărul nu călătorește descuiat. Cheile nu călătoresc niciodată, numai lacătele.

În practică, criptografia răspunde la două cerințe comune (care se pot și combina):

  1. Criptarea: trimiterea unui mesaj astfel încât numai destinatarul să îl poată citi
  2. Semnarea: trimiterea unui mesaj astfel încât destinatarul să aibă garanția că expeditorul este autentic

Pentru criptarea unui mesaj, este nevoie ca Alice să-i transmită lui Bob un cufăr încuiat cu un lacăt al lui Bob, pentru care doar Bob are cheia. (Desigur, în lumea digitală avem avantajul că lacătele nu trebuie trimise prin poștă în prealabil, ci pot fi descărcate de pe un site).

Pentru semnarea unui mesaj, folosim un model invers: Alice își publică cheia, dar ține lacătul secret. Atunci ea poate trimite un cufăr (lui Bob sau în eter) încuiat cu lacătul ei secret. Deoarece oricine poate deschide cufărul folosind cheia publică a lui Alice, și deoarece nimeni nu poate produce un lacăt care să poată fi deschis cu acea cheie publică, rezultă că mesajul este autentic.

Criptografia cu chei publice este un sistem în care fiecare persoană își publică cheia și ține lacătul secret. În acest sistem, lacătele și cheile sunt interschimbabile, deci analogia cu lumea reală se rupe. Pe un cufăr poate fi aplicată un lacăt care se deschide cu cheia potrivită, dar și o cheie care se deschide cu lacătul potrivit. De aceea, valorile se numesc cheie publică, respectiv cheie privată.

Cum transpunem aceste protocoale în algoritmi? Cheia este să găsim operații pe numere mari, care să poată fi calculate în timp polinomial (cu numărul de biți), dar să nu poată fi inversate decât de către cineva care cunoaște un anumit secret. Există două astfel de operații.

Logaritmul discret

Fie:

  • un număr prim p;
  • un generator g în Zp*;
  • un număr aZp*;
  • x = ga (mod p).

Atunci a se numește 'logaritmul discret al lui x în baza g modulo p. Nu sunt cunoscuți algoritmi eficienți pentru aflarea lui a dându-se g, p și x.

Factorizarea numerelor mari

Fie n = pq, unde p și q sunt numere prime mari (pe 1.000 de biți). Nu există algoritmi eficienți pentru aflarea lui p și q dându-se n. Cel mai bun algoritm cunoscut funcționează în O(n1/4), care este exponențial în numărul de biți al lui n.

Algoritmul Diffie-Hellman

Algoritmul Diffie-Hellman se bazează pe dificultatea logaritmului discret. Alice și Bob doresc să comunice pe un canal pe care Eve ascultă toate comunicațiile (frumusețea alegerii numelui Eve este că amintește de eavesdropping = trasul cu urechea). Ei procedează astfel:

  • Aleg un număr prim uriaș p și un generator g modulo p. În practică, g poate fi mic: 2, 3, 5 etc.
  • Alice alege un număr secret a', Bob alege un număr secret b (ambele modulo p)
  • Alice îi trimite lui Bob valoarea A = ga (mod p)
  • Bob îi trimite lui Alice valoarea B = gb (mod p)
  • Alice calculează secretul S = Ba (mod p) = gab (mod p)
  • Bob calculează secretul S = Ab (mod p) = gab (mod p)

Acum Alice și Bob au convenit asupra unei chei secrete comune, S, deși nu l-au trimis vreodată pe S pe fir. Eve are acces la valorile transmise: p, g, A = ga, B = gb, dar din acestea nu poate afla niciuna din valorile a, b sau S. Pentru a-l afla pe a, de exemplu, ar trebui să calculeze logaritmul discret al lui A în baza g modulo p.

În continuare, ei pot folosi cheia secretă comună pentru a cripta mesajele pe care doresc să le schimbe. O abordare simplistă ar fi cu XOR. Presupunând că cheia are 1.000 de biți (125 de octeți), fiecare porțiune de 125 de octeți din mesaj poate fi XOR-ată cu cheia, atât la criptare cât și la decriptare. Această abordare este susceptibilă de atacuri bazate pe frecvență. O abordare robustă va folosi secretul S drept cheie pentru un algoritm AES sau alt algoritm de criptare cu cheie simetrică (unde aceeași cheie este folosită și la criptare, și la decriptare).

Algoritmul Diffie-Hellman nu poate fi folosit pentru semnături.

Folosirea algoritmului Diffie-Hellman pentru criptografia cu chei publice

Alice alege p, g și a și publică cheia publică . Cheia secretă este . Pentru ca Bob să-i trimită un mesaj criptat:

  • alege un număr b
  • calculează și
  • criptează mesajul cu cheia (simetrică)
  • îi trimite lui Alice mesajul cifrat și valoarea B

Algoritmul RSA

Algoritmul RSA implementează un sistem criptografic cu chei publice, permițând criptarea și semnarea mesajelor. Pentru început, câteva generalități.

Alice caută o cheie publică și o cheie privată, notate cu și cu următoarele proprietăți:

  • ele sunt, efectiv, funcții care se pot aplica mesajelor
  • și sunt funcții inverse
  • prin criptare și decriptare se obține mesajul original, deci
  • dar aceste funcții trebuie să fie interschimbabile (necesar pentru semnare), deci
  • trebuie ca oricine să poată calcula eficient
  • trebuie ca doar Alice să poată calcula eficient

Criptarea mesajelor funcționează astfel:

  • Bob descarcă cheia publică a lui Alice,
  • Bob calculează mesajul criptat, și i-l trimite lui Alice
  • Alice recuperează mesajul original calculând

Semnarea mesajelor funcționează astfel:

  • Alice calculează semnătura mesajului M,
  • Alice îi trimite lui Bob (sau în eter) perechea
  • oricine poate verifica semnătura, căci
  • în practică, nu se semnează direct mesajul, ci un hash al lui, respectiv . Verificarea se face cu . În acest fel, semnătura nu este la fel de lungă ca mesajul. De asemenea, este mai greu de contrafăcut un mesaj (cu sens) ca venind de la Alice.

Și acum, partea matematică.

  • Alice alege două numere prime mari p și q. Apoi calculează n = pq.
  • Alice alege un număr mic e care să fie prim cu
  • Folosește algoritmul extins al lui Euclid pentru a găsi (luăm această afirmație fără demonstrație)
  • Cheia publică RSA este
  • Cheia secretă RSA este
  • Pentru a cripta un mesaj M, calculăm
  • Pentru a decripta un cifru C, calculăm

De ce merge acest sistem?

Analizăm întâi restul modulo p, folosind mica teoremă a lui Fermat pentru a-l simplifica:

Similar,

Din teorema chinezească a resturilor, rezultă:

Ca și la Diffie-Hellman, semnăturile se aplică, în general, unei funcții hash, nu mesajului întreg.

Cum ar putea fi atacat acest sistem? Dacă un atacator ar putea descompune n în factori primi și recupera p și q, ar putea, urmând același proces ca și Alice, să afle valoarea lui d, adică cheia secretă. Așadar, algoritmul RSA se bazează pe dificultatea factorizării numerelor mari.