Merkle-Hellman kriptosistema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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.

Turinys

1 Aibės poaibio sumos problema
- 1.1 Kuprinės problema
2 Raktų parinkimo algoritmas
3 Šifravimas/dešifravimas
4 Literatūra
5 Kitos viešo rakto kriptosistemos

[taisyti] 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.

[taisyti] Kuprinės problema

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

[taisyti] 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:  – SDS,  – skaičius
IŠVESTIS: , ir 
  1. 
  2. Kai :
    2.1 Jei , tai , kitaip 
    2.2 
  3. Rezultatas:

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_it \pmod{p}\,$

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

Privatus raktas:

$K_p=<W,\ s> \,$

[taisyti] Šifravimas/dešifravimas

Tarkime, kad $M=m_1m_2 \ldots m_n \in \{0,1\}^n\,$ – pranešimas.

Šifravimas:

$C=e(M, K_v)=m_1v_1+m_2v_2+ \ldots +m_nv_n \,$

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

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

$C_1=m_1sv_1+m_2sv_2 + \ldots + m_nsv_n \pmod{p} \equiv \,$

$m_1w_1+m_2w_2+\ldots+m_nw_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.