Criptarea cu cheie publica

Criptarea cu cheie publica

• Schema de criptare cu cheie publica

este o tripleta (G, E, D) de algoritmi PTP care satisfac urmatoarele:

• algoritmul de generare a cheii
  un algoritm PTP, G, care primeste ca intare o sceventa l^k (parametrul de securitate) si produce o pereche (e, d) unde e se numeste cheia publica si d este cheia privata corespondenta; (e, d) ∈ G(l^k) este o pereche de chei de criptare/decriptare
• algoritmul de criptare
  un algoritm PTP, E, care primeste ca intrare:
• un parametru de securitate l^k
• o cheie publica e ∈ G(l^k)
• un text in clar m ∈ ^k

si produce un text cifrat c ∈ ^k, c ∈ E(l^k, e, m)

• algoritmul de decriptare
  un algoritm PTP, D, care primeste ca intrare
• un parametru de securitate l^k
• o cheie privata d ∈ G(l^k)
• un text cifrat c ∈ E(l^k, e, m)

si produce un text m' ∈ ^* ai

• ∀ (e, d) ∈ G(l^k)
• ∀ m
• ∀ c ∈ E(l^k, e, m)
• prob(D(l^k, e, m) ≠ m') este neglijabila
• Obs. definitie
• singura diferenta fata de definitia unui sistem de criptare cu cheie secreta (vezi blogul 'Cifru') este ca adversarul cunoaste cheia publica
• textele in clar cu lungime diferita de k (lungimea cheii de criptare) vor fi criptate dupa spargerea in blocuri de lungime k ai
  E_e(a₁a₂a_la_l+1) = E_e(a₁)E_e(a₂)E_e(a_l)E_e(a_l+1) unde |a₁|=|a₂|==|a_l|=k si |a₁|⇔k
• Modelul functiei cu trapa
• G primeste ca intare parametrul de securitate l^k si prduce perechi (f, t_f) unde f este o functie cu trapa si t_f este trapa
• ∀ m, E(f, m) = f(m)
• fiind date c ∈ E(f, m) si t_f, D(t_f,c) = f^-1(c) = f^-1(f(m)) = m

probleme

• alegerea spatiului de mesaje faptul ca f este o functie cu trapa nu implica ca inversarea lui f(x) este grea at cand x este prost ales
• informatie partiala faptul ca este o functie cu trapa nu implica faptul ca f(x) ascunde toate informatiile despre x
• relatii intre textele criptate trimiterea de mai multe ori a aceluiasi mesaj este detectabila
• RSA
• colectii RSA de posibile functii cu trapa
  fie p, q prime, Z_n^* grupul multiplicativ cu ordinul φ(n) = (p-1)(q-1) si e ∈ Z_p-1 relativ prim cu φ(n); setul de indici va fi I= si trapa ptr. (n, e) este d ai ed = 1 mod φ(n); RSA = _{(n, e) ∈ I} unde RSA_{(n, e)}(x) = x^e mod n
• spatii rare de mesaje
  ptr o pereche (n, e) fie este greu de inversat RSA_{(n, e)} pentru toti x din Z_n^* in afara unei fractiuni neglijabile, fie este usor de inversat pentru orice x
• generarea cheilor

o entitate A executa:

se genereaza aleator doua numere prime distincte de aceeasi marime, p si q

se calculeaza n = pq si φ=(p-1)(q-1)

se selecteaza aleator un interg, e, 1 < e < φ ai cmmdc(e, φ) = 1

se calculeaza (Euclid extins) intregul d, 1 < d < φ ai ed ≡ 1 mod φ

cheia publicA A este (n, e) si cheia privata a lui A este d

e se numeste exponent de criptare, d se numeste exponent de decriptare si n se numeste modul

• criptarea/decriptarea B cripteaza un mesaj m pentru A pe care acesta il va decripta

criptarea

1. obtine cheia publica (n, e) autentica a lui A
2. reprezinta mesajul m ca un intreg in intervalul [0, n-1]
3. calculeaza c = m^e mod n
4. trimite c lui A

decriptarea

1. foloseste cheia privata, d, pentru a obtine m = e^d mod n
• Rabin
• f_n(m) ≡ m² mod n unde n = pq cu p si q prime
• f_n^-1(m²) = x ai x² = m² mod n
  si ptr. a identifica una dintre cele 4 radacini se poate poate folosi intreg spatiul de mesaje daca acesta este rar in Z_n^*
• generarea cheilor

fiecare entitate, A, creeaza o cheie publica si o cheie privata

se genereaza aleator doua numere prime distincte de aceeasi marime, p si q

se calculeaza n = pq

cheia publica a lui A este n, cheia privata a lui A este (p, q)

• criptarea/decriptarea

B cripteaza un mesaj, m, pentru A pe care acesta il decripteaza

criptarea

1. obtine cheia publica a lui A
2. reprezinta mesajul, m, ca un intreg in multimea
3. calculeaza c = m² mod n
4. trimite c lui A

decriptarea

1. calculeaza cele 4 radacini m₁, m₂, m₃, m₄ pentru c
2. A decide care dintre radacini este m
• rucsace

sisteme bazate pe problema NP-completa, a rucsacului:
fie un vector a=(a₁, a₂, , a_n) de intregi si C o valoare tinta; sa se determine daca exista un vector x ∈ ⁿ ai a x = C
vectorul a este cheia publica; textul criptat c = m a unde m este textul clar

• Merkle-Hellman
• Chor-Rivest
• ElGamal
• generarea cheilor

entitatea A creeaza cheile

genereaza aleator un numar prim, p si un generator, α, al grupului multiplicativ Z_p^*

selecteaza aleator un inter, a, 1 ≦ a ≦ p-2 si calculeaza α^a mod p

cheia publica a lui A este (p,α,α^a) iar cheia privata este a

• criptarea/decriptarea

B cripteaza un mesaj, m, pentru A pe care A il decripteaza

criptarea

1. obtine cheia publica, (p,α,α^a), autentica
2. reprezinta mesajul ca un intreg in multimea
3. selecteaza aleator un intreg, k, 1 ≦ k ≦ p-2
4. calculeaza γ = α^k mod p si δ = m (α^a)^k mod p
5. trimite textul cifrat c = (γ, δ) lui A

decriptarea

A decripteaza c pentru a obtine m

1. foloseste cheia privata α pentru a calcula γ^p-1-a mod p
2. afla pe m calculand (γ^-a) δ mod p
• McEliece
• probabilistic

schemele RSA, Rabin si rucsac sunt deterministe: ptr. o cheie publica fixata un text in clar este intotdeuana criptat in acelasi text criptat

• Goldwasser-Micali
• Blum-Goldwasser