Merkle-Hellman kriptosistema

Merkle-Hellman kriptosistema – viena pirmųjų viešo rakto kriptosistemų, sukurta 1978 metais Ralph Merkle ir Martin Hellman. Sistema paprastesnė už RSA, tačiau nepatikima – nepatikimumą įrodė Adi Shamir 9-o dešimtmečio pradžioje.

Aibės poaibio sumos problema

Ši kriptosistema remiasi taip vadinamos aibės poaibio sumos problemos sprendimo sudėtingumu. Šios problemos esmė yra tokia: turint aibę skaičių $A=\{a_1,a_2,...,a_n\},n\in N$ir kitą skaičių $x$, nustatyti, ar kurio nors poaibio elementų suma lygi duotajam skaičiui, t. y. ar

$\mathrm{\exists }\hat{A}\subset A:\sum _{i\in I}{a}_i=x,a_i\in \hat{A}$

čia $I$ – indeksų aibė. Bendru atveju problema priklauso NPC problemų klasei, tačiau tam tikri „paprasti“ atvejai lengvai išsprendžiami.

Merkle-Hellman kriptosistema išnaudoja tą faktą, kad poaibio problemą galima iš išsprendžiamos per polinominį laiką, t. y. iš atskiro išsprendžiamo atvejo, paversti į problemą, kurią sunku išspręsti.

Kuprinės problema

Kuprinės problema (ang. knapsack problem) yra aibės poaibio sumos problemos atskiras atvejis.

Raktų parinkimo algoritmas

Skaičiai $w_i$ sudaro sparčiai didėjančią seką (SDS), jeigu visiem $i>1$ tesinga nelygybė:

$w_1+w_2+\dots +w_{i-1}<w_i$

Šiuo atveju kuprinės problema išsprendžiama per polinominį laiką sekančio algoritmo pagalba:

ĮVESTIS: $(w_1,w_2,\dots ,w_n)$ – SDS, $x$ – skaičius
IŠVESTIS: $(x_1,x_2,\dots ,x_n),x_i\in \{1,0\}$, ir $\sum _{i=1}^n{x}_i{w}_i=x$
  1. $i\leftarrow n$
  2. Kai $i\ge 1$:
    2.1 Jei $s\ge b_i$, tai $x_i\leftarrow 1$, kitaip $x_i\leftarrow 0$
    2.2 $i\leftarrow i-1$
  3. Rezultatas: $(x_1,x_2,\dots ,x_n),x_i\in \{1,0\}$

Tarkime, kad $W=w_1,w_2,\dots ,w_n$ – yra sparčiai didėjanti seka. Pasirenkame skaičių $p$ taip, kad būtų:

$p>\sum _{i=1}^n{w}_i$

Tagu skaičiai $s,t$ yra tarpusavyje pirminiai su $p$, t. y. $st\equiv 1(\mathrm{mod}p)$.

Sudarome raktus. Viešas raktas:

$K_v=V=\{v_1,v_2,\dots ,v_n\},v_i\equiv w_{i}t(\mathrm{mod}p)$

Pastebėsime, kad $V$ nėra sparčiai didėjanti seka.

Privatus raktas:

$K_p=<W,s>$

Šifravimas/dešifravimas

Tarkime, kad $M=m_1{m}_2\dots m_n\in \{0,1{\}}^n$ – pranešimas.

Šifravimas:

$C=e(M,K_v)=m_1{v}_1+m_2{v}_2+\dots +m_n{v}_n$

$C$ – pranešimo $M$ šifras. Dešifravimas:

$C_1=d(C,K_p)\equiv Cs(\mathrm{mod}p)$

$C_1=m_{1}s{v}_1+m_{2}s{v}_2+\dots +m_{n}s{v}_n(\mathrm{mod}p)\equiv$

$m_1{w}_1+m_2{w}_2+\dots +m_n{w}_n(\mathrm{mod}p)$

Dabar, naudojantis algoritmu spręsti poaibio sumos SDS atveju problemą, surandame $m_i,i=\{1,2,\dots ,n\}$ – o tai ir yra dešifruotas pranešimas.

Literatūra

• A. Menezes, P. van Oorschot, S. Vanstone, 1996, Handbook of Applied Cryptography

Kitos viešo rakto kriptosistemos

• Rivest-Shamir-Adleman kriptosistema, RSA