Criptosistema de Merkle-Hellman

Merkle-Hellman (MH) va ser un dels primers criptosistemas de clau pública i va ser inventat per Ralph Merkle i Martin Hellman en 1978.^[1] Encara que les seues idees eren elegants, i molt més simples que RSA, no va tindre el mateix èxit que este últim, degut a que MH ya va ser trencat,^[2] i ademés no oferix funcionalitats per a firmar.

Descripció

Merkle-Hellman és un criptosistema asimètric, açò significa que per a la comunicació, es necessiten dos claus: una clau pública i una privada. Una atra diferència en RSA, és que servix solament para sifrat, és dir, la clau pública és usada solament per a sifrar (no per a verificar firma) i la clau privada és usada solament per a dessifrar (no per a firmar). D'esta manera, no es pot usar per a tasques d'autentificació per firma electrònica.

L'algoritme de Merkle-Hellman està basat en el problema de la mochila de decisió (un cas especial del problema de la mochila d'optimisació): donats una seqüència de números i un número, determinar si existix un subconjunt de la seqüència que la seua sumixca done dit número. En general, és sabut que este problema és de classe NP-complet. No obstant, si la seqüència de números és supercreciente —açò és, si cada element de la seqüència és major que la suma de tots els anteriors— el problema és "fàcil", i és possible resoldre-ho en temps polinòmic en un simple algoritme voraç.

Generació de les claus

En Merkle-Hellman, les claus estan compostes per seqüències. La clau pública és una seqüència "difícil", i la clau privada és una "fàcil", o seqüència de valors supercrecientes, junt en dos números adicionals, un multiplicador i un mòdul, els quals són usats per a convertir la seqüència supercreciente en una seqüència difícil. Estos mateixos números són usats per a transformar la suma de la subsecuencia de la seqüència "difícil" en la suma de la subsecuencia de la seqüència "fàcil", la qual es pot solucionar en temps polinòmic.

Sifrat

Per a sifrar un mensage, el qual deu ser una seqüència de bits de la mateixa llongitut de la seqüència difícil, s'elegixen els elements de la seqüència difícil que corresponguen a bits en 1 del mensage (mentres que els elements corresponents a bits en 0 són descartats). Després se sumen els elements aixina elegits, i el resultat d'açò és el text sifrat.

En cas que el mensage no siga de la mateixa llongitut de la clau, es subdivide en seqüències que tinguen esta llongitut i s'aplica el mateix procediment.

Dessifrat

El dessifrat és possible, perque el multiplicador i el mòdul usats per a transformar la seqüència supercreciente (la clau privada) i per tant "fàcil" en la seqüència general (la clau pública) i per tant difícil, també poden ser usats per a transformar el text sifrat (representat per un número) en la suma dels elements que conformen la subsecuencia supercreciente (una subsecuencia d'una seqüència supercreciente, també és supercreciente). Després, usant un algoritme voraç, el problema "fàcil" de la mochila pot ser resolt usant O(n) operacions, en la qual cosa es conseguix dessifrar el mensage.

Método Matemàtic

Generació de les claus

Per a sifrar un mensage de n-bits, elegir una seqüència supercreciente :

w = (w_{1}, w_{2}, ..., w_{n}) tal que w_{i + 1} > \sum_{j = 1}^{i} w_{j}

de n número natural (distints de zero). Elegir un número q (preferiblement a l'encert), tal que

q > \sum_{i = 1}^{n} w_{i}

i un atre número entero, r tal que mcd(r,q) = 1.

q és triat d'esta forma per a assegurar l'unicitat del text sifrat. Si fora menor, podria haver varis texts clars que resultarien en el mateix text sifrat. r deu ser coprimo en q posat que d'una atra forma podria no tindre invers en $(\mod q)$ . L'existència de l'invers de r és necessària per a que es puga realisar el dessifrat.

A continuació, es calcula la seqüència:

𝜷 = (β_{1}, β_{2}, ..., β_{n}) tal que β_{i} = r w_{i} (\mod q)

La clau pública és $β$ , mentres que la clau privada és $(w, q, r)$ .

Sifrat

Per a sifrar un mensage de n-bits

𝜶 = (α_{1}, α_{2}, ..., α_{n})

a on $𝜶_{i}$ és el i-ésimo bit del mensage i $𝜶_{i} \in {0, 1}$ , calcular

c = \sum_{i = 1}^{n} α_{i} β_{i}

.

El criptograma o text sifrat és c.

Dessifrat

Per a dessifrar el criptograma c, el receptor té que trobar els bits del mensage $α_{i}$ tals que satisfan

c = \sum_{i = 1}^{n} α_{i} β_{i}

.

Este problema seria difícil de resoldre si els $β_{i}$ anaren valors aleatoris, degut a que el receptor tindria que resoldre una instància del problema de la mochila, el qual se sap que és NP-hard. No obstant, els valors $β_{i}$ varen ser elegits de manera que el dessifrat siga fàcil si la clau privada $(w, q, r)$ és coneguda.

Per al dessifrat es deu trobar un sancer s tal que és l'invers de r mòdul q. Açò és, s satisfà l'equació:

r s \equiv 1 (\mod q)

o equivalentemente, existix un sancer k tal que sr = kq + 1. Ya que r va ser triat com un coprimo de q és possible trobar s i k usant l'Algoritme de Euclides estés. Després el receptor del criptograma c calcula:

c^{'} \equiv c s (\mod q) .

Per tant

c^{'} \equiv c s \equiv \sum_{i = 1}^{n} α_{i} β_{i} s (\mod q) .

Ya que $r s \equiv 1 (\mod q)$ i $𝜷_{i} \equiv r w_{i} (\mod q)$ llavors

β_{i} s \equiv w_{i} r s \equiv w_{i} (\mod q) .

En açò

c^{'} \equiv \sum_{i = 1}^{n} α_{i} w_{i} (\mod q) .

La suma de tots els valors $w_{i}$ és menor que q i per això $\sum_{i = 1}^{n} α_{i} w_{i} mod q$ també està en l'interval $[0, q - 1]$ .

D'esta manera el receptor té que resoldre el següent problema de la mochila.

c^{'} = \sum_{i = 1}^{n} α_{i} w_{i} .

Este problema és fàcil degut a que la seqüència w és supercreciente.

L'algoritme avaro per a resoldre açò consistix en lo següent:

   Prendre l'element més gran en  $w$ , digam  $w_{k}$ . 
   Si  $w_{k} > c^{'}$ , després  $α_{k} = 0$ ,
   Sino  $α_{k} = 1$ 
   Disminuímos  c'  en  $w_{k} α_{k}$  
   i repetim estos passos fins que s'haja alcançat c'.

El pseudo còdic per a este algoritme seria:

   While  $(c^{'} > 0)$ {
        $w_{k} = extract-max (w)$ 
       If  $(w_{k} > c^{'})$ 
          then  $α_{k} = 0$ ,
       Else  $α_{k} = 1$ 
           $c^{'} = c^{'} - w_{k} * α_{k}$ 
   }

Este algoritme no es pot usar per a firmar lloc que el criptograma és un número (c) i no un text, d'esta manera no es pot dessifrar un mensage clar i per això no es pot firmar.

Referències

↑ Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.
↑ Adi Shamir, A Polynomial Clave Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279–288. «Copia archivada». Archivat des d'el original, el 24 d'abril de 2005. Consultat el 24 d'abril de 2005.

Referències

Este artícul conté una traducció derivada de «Criptosistema de Merkle-Hellman» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Ralph Merkle and Martin Hellman, Hiding Information and Signatures in Trapdoor Knapsacks, IEEE Trans. Information Theory, 24(5), September 1978, pp525–530.

[2] Adi Shamir, A Polynomial Clave Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. CRYPTO 1982, pp279–288. «Copia archivada». Archivat des d'el original, el 24 d'abril de 2005. Consultat el 24 d'abril de 2005.

[1]

[2]