Merkle-Hellman

De la Wikipedia, enciclopedia liberă

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.

Cuprins 1 Descriere 1.1 Generarea cheii 1.2 Criptare 1.3 Decriptare 2 Vezi şi 3 Referinţe

[modifică] Descriere

[modifică] 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 ≥,

ş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).

[modifică] Criptare

Pentru a cripta mesajul de n biţi

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

unde α_i este al i-lea bit al mesajului şi α_i {0, 1}, calculaţi

.

Cripotextul este atunci c.

[modifică] 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.

[modifică] Vezi şi

• Algoritmul extins al lui Euclid

[modifică] Referinţe

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