Criptosistemul Merkle-Hellman

(Redirecționat de la Merkle-Hellman)

Merkle-Hellman (MH) este unul dintre primele criptosisteme cu cheie publică, inventat de Ralph Merkle și Martin Hellman în 1978[1]. Deși ideile de la baza acestuia sunt mai elegante și mai simple decât cele ale criptosistemului RSA, a fost spart [2]. Sistemul Merkle-Hellman se bazează pe problema sumelor de submulțimi (un caz special al problemei rucsacului): dată o listă cu numere și un alt număr, care este suma unei submulțimi a listei de numere, determinați submulțimea. În general, această problemă este considerată a fi NP-completă; dar există niște cazuri ușoare care pot fi rezolvate eficient. Schema Merkle-Hellman este bazată pe transformarea unui caz ușor într-unul dificil, și invers. În orice caz, schema a fost spartă de Adi Shamir, nu prin atacarea problemei rucsacului, ci prin coruperea conversiei de la rucsacul ușor la cel dificil.

Descriere

modificare

Generarea cheii

modificare

Pentru a cripta un mesaj de n biți, alegeți o secvență supercrescătoare

w = (w1, w2, ..., wn)

de n numere naturale (excluzând zero). (O secvență supercrescătoare este o secvență în care fiecare element este mai mare decât suma tuturor celor dinaintea sa, de exemplu {1, 2, 4, 8, 16} ) Alegeți un număr întreg q, astfel încât

q ≥ ,

și un număr întreg aleator, r, astfel încât cmmdc(r,q) = 1.

q trebuie să fie ales astfel încât să se asigure unicitatea mesajul criptat, după aritmetica modulară. Dacă este mai mic, mai multe mesaje normale vor fi criptate cu același criptotext, făcând astfel decriptarea imposibilă din punct de vedere funcțional. r trebuie să fie coprim cu q sau altfel nu va avea un invers modulo q. Existența inversului modular al lui r este necesară pentru a face posibilă decriptarea.

Acum calculați secvența

β = (β1, β2, ..., βn)

unde βi = rwi (mod q). Cheia publică este β, îm timp ce cheia privată este (w, q, r).

Criptare

modificare

Pentru a cripta mesajul de n biți

α = (α1, α2, ..., αn),

unde αi este al i-lea bit al mesajului și αi   {0, 1}, calculați

 .

Cripotextul este atunci c.

Decriptare

modificare

Ideea decriptării este determinarea lui s = r-1 (mod q). s este cheie privată în acest criptosistem. Acum se poate converti problema NP-completă, extrapolând α din c (utilizând un rucsac umplut aleator), într-o problemă ușoară de extrapolare a lui α folosind un rucsac supercrescător, care este rezolvabilă în timp liniar.

Pașii decriptării necesită calcularea lui c = c*s (mod q) și w = β*s (mod q).

c este încă o formă criptată a lui α, dar rucsacul care îl criptează este doar o secvență supercrescătoare, w. Problema rucsacului supercrescător este simplă de rezolvat datorită structurii unei secvențe supercrescătoare. Luați cel mai mare element din w, să zicem wk. Dacă wk > c, atunci αk = 0, dacă wkc, atunci αk = 1. Atunci, scădeți wk * αk din c, și repetați acești pași până când obțineți α.

Când q este destul de mare, este foarte greu să se calculeze s (poate lua mult timp, dar algoritmul face apel la multiplicarea modulară). Dificultatea aflării lui s este faptul pentru care acest criptosistem a fost considerat imposibil de spart.

Vezi și

modificare
  1. ^ Ralph Merkle și Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), septembrie 1978, pag. 525–530.
  2. ^ Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pag. 279–288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF