Merkle-Hellman kriptosistema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

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[taisyti | redaguoti kodą]

Š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[taisyti | redaguoti kodą]

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

Raktų parinkimo algoritmas[taisyti | redaguoti kodą]

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

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

Privatus raktas:

K_p=<W,\ s> \,

Šifravimas/dešifravimas[taisyti | redaguoti kodą]

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.

Literatūra[taisyti | redaguoti kodą]

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

Kitos viešo rakto kriptosistemos[taisyti | redaguoti kodą]

  • Rivest-Shamir-Adleman kriptosistema, RSA