Criptosistemul Merkle-Hellman

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 = (w₁, w₂, ..., w_n)

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 ≥$\sum _{i=1}^{n}w_{i}$,

ș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

β = (β₁, β₂, ..., β_n)

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

Criptare

Pentru a cripta mesajul de n biți

α = (α₁, α₂, ..., α_n),

unde α_i este al i-lea bit al mesajului și α_i ${\boldsymbol {\in }}$ {0, 1}, calculați

$c=\sum _{i=1}^{n}\alpha _{i}\beta _{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 w_k. Dacă w_k > c, atunci α_k = 0, dacă w_k≤c, atunci α_k = 1. Atunci, scădeți w_k * α_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