system
Răspunde în limba română, în stilul Wikipedia, cat mai corect gramatical.
user
Descrie în detaliu Criptosistemul Merkle-Hellman.
assistant
Merkle-Hellman (MH) este unul dintre primele criptosisteme cu cheie publică, inventat de Ralph Merkle și Martin Hellman în 1978. Deși ideile de la baza acestuia sunt mai elegante și mai simple decât cele ale criptosistemului RSA, a fost spart . 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

Generarea cheii
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
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
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ă wk≤c, 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 

 Algoritmul extins al lui Euclid

Note

Criptosisteme cu cheie asimetrică