Algoritmul de criptografie Merkle-Hellman

Articol postat de:

criptografie

Merkle-Hellman (MH) este unul dintre primele criptosisteme cu cheie publica, inventat de Ralph Merkle si Martin Hellman in 1978. Desi ideile de la baza acestuia sunt mai elegante si mai simple decat cele ale criptosistemului RSA, a fost spart.

Sistemul Merkle-Hellman se bazeaza pe problema sumelor de submultimi (un caz special al problemei rucsacului): data o lista cu numere si un alt numar, care este suma unei submultimi a listei de numere, determinati submultimea.

In general, aceasta problema este considerata a fi NP-completa dar exista niste cazuri usoare care pot fi rezolvate eficient. Schema Merkle-Hellman este bazata pe transformarea unui caz usor intr-unul dificil, si invers.

In orice caz, schema a fost sparta de Adi Shamir, nu prin atacarea problemei rucsacului, ci prin coruperea conversiei de la rucsacul usor la cel dificil.

Generarea cheii

Pentru a cripta un mesaj de n biti, alegeti o secventa supercrescatoare

w = (w1w2, …, wn)

de n numere naturale (excluzand zero).

O secventa supercrescatoare este o secventa in care fiecare element este mai mare decat suma tuturor celor dinaintea sa, de exemplu {1, 2, 4, 8, 16}.

Alegeti un numar intreg q, astfel incat

si un numar intreg aleator, r, astfel incat cmmdc(r,q) = 1.

q trebuie sa fie ales astfel incat sa se asigure unicitatea mesajul criptat, dupa aritmetica modulara. Daca este mai mic, mai multe mesaje normale vor fi criptate cu acelasi criptotext, facand astfel decriptarea imposibila din punct de vedere functional. r trebuie sa fie coprim cu q sau altfel nu va avea un invers modulo q. Existenta inversului modular al lui r este necesara pentru a face posibila decriptarea.

Acum calculati secventa

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

unde βi = rwi (mod q). Cheia publica este β, im timp ce cheia privata este (wqr).

Criptare

Pentru a cripta mesajul de n biti

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

unde αi este al i-lea bit al mesajului si αi ∈ {0, 1}, calculati

Cripotextul este atunci c.

Decriptare

Ideea decriptarii este determinarea lui s = r-1 (mod q). s este cheie privata in acest criptosistem. Acum se poate converti problema NP-completa, extrapoland α din c (utilizand un rucsac umplut aleator), intr-o problema usoara de extrapolare a lui α folosind un rucsac supercrescator, care este rezolvabila in timp liniar.

Pasii decriptarii necesita calcularea lui c = c*s (mod q) si w = β*s (modq).

c este inca o forma criptata a lui α, dar rucsacul care il cripteaza este doar o secventa supercrescatoare, w. Problema rucsacului supercrescator este simpla de rezolvat datorita structurii unei secvente supercrescatoare. Luati cel mai mare element din w, sa zicem wk. Dacawk > c, atunci αk= 0, daca wkc, atunci αk= 1. Atunci, scadeti wk* αkdin c, si repetati acesti pasi pana cand obtineti α.

Cand q este destul de mare, este foarte greu sa se calculeze s (poate lua mult timp, dar algoritmul face apel la multiplicarea modulara). Dificultatea aflarii lui s este faptul pentru care acest criptosistem a fost considerat imposibil de spart.

Sursa: Wikipedia


Add Comment Register



Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile necesare sunt marcate *


*

Poți folosi aceste etichete HTML și atribute: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>