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

$\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}+\ldots +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},\ldots ,w_{n})\,$ – SDS, $x\,$ – skaičius
IŠVESTIS: $(x_{1},x_{2},\ldots ,x_{n}),\ x_{i}\in \{1,0\}\,$, ir $\sum _{i=1}^{n}x_{i}w_{i}=x\,$
  1. $i\leftarrow n\,$
  2. Kai $i\geq 1\,$:
    2.1 Jei $s\geq b_{i}\,$, tai $x_{i}\leftarrow 1\,$, kitaip $x_{i}\leftarrow 0\,$
    2.2 $i\leftarrow i-1\,$
  3. Rezultatas: $(x_{1},x_{2},\ldots ,x_{n}),\ x_{i}\in \{1,0\}\,$

Tarkime, kad $W={w_{1},w_{2},\ldots ,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{\pmod {p}}\,$.

Sudarome raktus. Viešas raktas:

$K_{v}=V=\{v_{1},v_{2},\ldots ,v_{n}\},\ v_{i}\equiv w_{i}t{\pmod {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}\ldots m_{n}\in \{0,1\}^{n}\,$ – pranešimas.

Šifravimas:

$C=e(M,K_{v})=m_{1}v_{1}+m_{2}v_{2}+\ldots +m_{n}v_{n}\,$

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

$C_{1}=d(C,K_{p})\equiv Cs{\pmod {p}}\,$

$C_{1}=m_{1}sv_{1}+m_{2}sv_{2}+\ldots +m_{n}sv_{n}{\pmod {p}}\equiv \,$

$m_{1}w_{1}+m_{2}w_{2}+\ldots +m_{n}w_{n}{\pmod {p}}\,$

Dabar, naudojantis algoritmu spręsti poaibio sumos SDS atveju problemą, surandame $m_{i},\ i=\{1,2,\ldots ,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