- 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 lk (parametrul de securitate) si produce o pereche (e, d) unde e se numeste cheia publica si d este cheia privata corespondenta; (e, d) ∈ G(lk) este o pereche de chei de criptare/decriptare
- algoritmul de criptare
un algoritm PTP, E, care primeste ca intrare:
- un parametru de securitate lk
- o cheie publica e ∈ G(lk)
- un text in clar m ∈ {0,1}k
si produce un text cifrat c ∈ {0,1}k, c ∈ E(lk, e, m)
- algoritmul de decriptare
un algoritm PTP, D, care primeste ca intrare
- un parametru de securitate lk
- o cheie privata d ∈ G(lk)
- un text cifrat c ∈ E(lk, e, m)
si produce un text m' ∈ {0, 1}* ai
- ∀ (e, d) ∈ G(lk)
- ∀ m
- ∀ c ∈ E(lk, e, m)
- prob(D(lk, 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
Ee(a1a2...alal+1) = Ee(a1)Ee(a2)...Ee(al)Ee(al+1) unde |a1|=|a2|=...=|al|=k si |a1|⇔k
- Modelul functiei cu trapa
-
- G primeste ca intare parametrul de securitate lk si prduce perechi (f, tf) unde f este o functie cu trapa si tf este trapa
- ∀ m, E(f, m) = f(m)
- fiind date c ∈ E(f, m) si tf, D(tf,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, Zn* grupul multiplicativ cu ordinul φ(n) = (p-1)(q-1) si e ∈ Zp-1 relativ prim cu φ(n); setul de indici va fi I={(n, e) / n = pq, |p|=|q|} si trapa ptr. (n, e) este d ai ed = 1 mod φ(n); RSA = {RSA(n, e) : Zn* → Zn*}(n, e) ∈ I unde RSA(n, e)(x) = xe mod n
- spatii rare de mesaje
ptr o pereche (n, e) fie este greu de inversat RSA(n, e) pentru toti x din Zn* 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
- obtine cheia publica (n, e) autentica a lui A
- reprezinta mesajul m ca un intreg in intervalul [0, n-1]
- calculeaza c = me mod n
- trimite c lui A
- decriptarea
- foloseste cheia privata, d, pentru a obtine m = ed mod n
- Rabin
-
- fn(m) ≡ m2 mod n unde n = pq cu p si q prime
- fn-1(m2) = x ai x2 = m2 mod n
si ptr. a identifica una dintre cele 4 radacini se poate poate folosi intreg spatiul de mesaje daca acesta este rar in Zn*
-
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
- obtine cheia publica a lui A
- reprezinta mesajul, m, ca un intreg in multimea {0, 1, ..., n-1}
- calculeaza c = m2 mod n
- trimite c lui A
- decriptarea
- calculeaza cele 4 radacini m1, m2, m3, m4 pentru c
- A decide care dintre radacini este m
- rucsace
-
sisteme bazate pe problema NP-completa, a rucsacului:
fie un vector a=(a1, a2, ..., an) de intregi si C o valoare tinta; sa se determine daca exista un vector x ∈ {0, 1}n 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 Zp*
- 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
- obtine cheia publica, (p,α,αa), autentica
- reprezinta mesajul ca un intreg in multimea {0, 1, ..., p-1}
- selecteaza aleator un intreg, k, 1 ≦ k ≦ p-2
- calculeaza γ = αk mod p si δ = m (αa)k mod p
- trimite textul cifrat c = (γ, δ) lui A
- decriptarea
A decripteaza c pentru a obtine m
- foloseste cheia privata α pentru a calcula γp-1-a mod p
- 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
-
| schema | problema de calcul |
| RSA | descompunerea in factori, problema RSA |
| Rabin | descompunerea in factori, radacina patrata modul n compozit |
| ElGamal | logaritm discret, problema Diffie-Hellman |
| McEliece | decodarea unui cod liniar |
| Merkle Hellman | problema rucsacului |
| Chor-Rivest | problema rucsacului |
| Goldwasser-Micali | reziduri patratice |
| Blum-Goldwasser | descompunerea in factori |
# posted by Sorin Badescu @ 3:12 PM
