Note de curs, clasele 11-12, 15 martie 2013

Problemă de logică

• Ești un împărat. Ai 240 de butoaie de vin, din care unul este otrăvit. Otrava își face efectul în maxim 24h. Ai 5 sclavi pe care ești dispus să-i sacrifici. Cum depistezi butoiul otrăvit în maxim 48h?
• Întrebare ajutătoare: 1000 de butoaie, 10 sclavi la dispoziție, maxim 24h

Criptografie

• Alice vrea să-i trimită un cufăr lui Bob, dar nu are încredere în curier. Alice și Bob au fiecare lacăte și chei
  • Metoda 1: Bob îi trimite un lacăt lui Alice; Alice îi trimite cufărul închis cu acel lacăt
  • Metoda 2: Alice pune un lacăt; Bob pune și el un lacăt; Alice scoate lacătul; Bob scoate lacătul
• Dorim să realizăm unul sau ambele din două lucruri:
  • semnături: Alice să poată dovedi că ea a trimis mesajul
  • securitate: numai Bob să poată citi mesajul
• Criptare cu cheie simetrică:
  • Alice și Bob aleg chei publice / secrete: P_A, S_A, P_B, S_B.
  • numele se referă și la funcțiile respective
  • funcțiile trebuie să fie bijective și inverse: P_A(S_A(M)) = S_A(P_A(M)) = M
  • cum funcționează criptarea și semnarea
  • semnarea face mesajul ilizibil, dar putem publica mesajul în clar împreună cu cel semnat
  • directoare de chei publice, web of trust, trusted party
  • exemplu (prost): P_A = rot+k, S_A = rot-k
    • rot13 e simetric și s-a bucurat de oarecare notorietate pe forumuri
• Algoritmul RSA
  • Alice alege p, q prime de circa 1000 biți, calculează n = pq
  • Alice alege e impar prim cu ϕ(n), calculează d = e^-1 (mod n)
    • notă: de aceea este bine ca p, q să nu aibă mulți divizori
  • P_A = (e, n); S_A = (d, n)
  • criptare: P(M) = M^e (mod n)
  • decriptare: S(C) = C^d (mod n)
  • de ce merge: DLP, factorizare
• Criptare cu cheie publică
  • Mai rapidă, dar partenerii trebuie să aibă aceeași cheie
• Diffie-Hellman - protocol pentru schimb de chei
  • cum ajungem la un secret comun pe un canal public?
  • Alice și Bob aleg p prim, g generator modulo p, ambele publice
  • Alice alege a secret, Bob alege b secret
  • Alice îi trimite lui Bob A = g^a mod p
  • Bob îi trimite lui Alice B = g^b mod p
  • Alice calculează s = B^a mod p
  • Bob calculează s = A^b mod p
  • de ce merge: DLP
• combinație: criptăm datele cu cheie simetrică, iar cheia însăși cu o cheie publică
  • diagramă PGP

Aritmetică modulară

• clase de resturi modulo n
• grup (definiția celor patru proprietăți, exemple)
  • dacă este și comutativ, se numește grup abelian
• propoziție: dacă d | a și d | b ⇒ d | (ax + by)
• teoremă: gcd(a, b) este cel mai mic element pozitiv al mulțimii {ax + by}
  • corolar: d | a și d | b ⇒ d | gcd(a, b)
  • corolar: gcd(na, nb) = n gcd(a, b)
  • corolar: n | ab și gcd(n, a) = 1 ⇒ n | b
• algoritmul lui Euclid extins (AEE)
• aflarea inverselor în Z_n^* cu AEE
• mica teoremă a lui Fermat: pentru orice p prim, a^p ≡ a (mod p)
  • demonstrație cu șiragurile de p mărgele rotite circular
• teorema chinezească a resturilor
  • să se găsească x astfel încât x ≡ 4 modulo 5, x ≡ 7 modulo 11
  • foarte pe fugă, am construit tabloul de 5x7 cu resturi modulo 5, modulo 7 și modulo 35
  • demonstrația că RSA merge: M^ed ≡ M (mod p, mod q, apoi mod n)