Vizualizare sursă pentru „Criptosistemul Merkle-Hellman”

'''Merkle-Hellman''' ('''MH''') este unul dintre primele [[criptografie|criptosisteme]] cu [[cheie publică]], inventat de [[Ralph Merkle]] și [[Martin Hellman]] în [[1978]]<ref>Ralph Merkle și Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, ''IEEE Trans. Information Theory'', 24(5), septembrie 1978, pag. 525&ndash;530.</ref>. Deși ideile de la baza acestuia sunt mai elegante și mai simple decât cele ale criptosistemului [[RSA]], a fost spart <ref>Adi Shamir, A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pag. 279&ndash;288. http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/C82/279.PDF</ref>. Sistemul Merkle-Hellman se bazează pe problema sumelor de submulțimi (un caz special al [[Problema rucsacului|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'' [[bit|biți]], alegeți o secvență supercrescătoare

:''w'' = (''w''<sub>1</sub>, ''w''<sub>2</sub>, ..., ''w''<sub>''n''</sub>) 

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''&nbsp;&ge;<math>\sum_{i = 1}^n w_i</math>, 

ș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  
:&beta;&nbsp;= (&beta;<sub>1</sub>, &beta;<sub>2</sub>, ..., &beta;<sub>''n''</sub>)
unde &beta;<sub>''i''</sub>&nbsp;= ''rw''<sub>''i''</sub> (mod ''q''). Cheia publică este &beta;, îm timp ce cheia privată este (''w'', ''q'', ''r'').

===Criptare===
Pentru a cripta mesajul de ''n'' biți

:&alpha; = (&alpha;<sub>1</sub>, &alpha;<sub>2</sub>, ..., &alpha;<sub>''n''</sub>),

unde &alpha;<sub>''i''</sub> este al ''i''-lea bit al mesajului și &alpha;<sub>''i''</sub> <math> \boldsymbol{\in}</math> {0, 1}, calculați 

:<math>c = \sum_{i = 1}^n  \alpha_i \beta_i</math>. 
Cripotextul este atunci ''c''.

===Decriptare===
Ideea decriptării este determinarea lui ''s'' = ''r''<sup>-1</sup> (mod ''q'').  ''s'' este cheie privată în acest criptosistem. Acum se poate converti problema NP-completă, extrapolând &alpha; din ''c'' (utilizând un rucsac umplut aleator), într-o problemă ușoară de extrapolare a lui &alpha; 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'' = &beta;*''s (mod ''q'').

''c'' este încă o formă criptată a lui &alpha;, 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''<sub>''k''</sub>.  Dacă ''w''<sub>''k''</sub> > ''c'', atunci &alpha;<sub>''k''</sub> = 0, dacă ''w''<sub>''k''</sub>&le;''c'', atunci &alpha;<sub>''k''</sub> = 1.  Atunci, scădeți  ''w''<sub>''k''</sub> * &alpha;<sub>''k''</sub> din ''c'', și repetați acești pași până când obțineți &alpha;.

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==
<references/>

[[Categorie:Criptosisteme cu cheie asimetrică]]