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 redaguoti

Ši kriptosistema remiasi taip vadinamos aibės poaibio sumos problemos sprendimo sudėtingumu. Šios problemos esmė yra tokia: turint aibę skaičių  ir kitą skaičių  , nustatyti, ar kurio nors poaibio elementų suma lygi duotajam skaičiui, t. y. ar

 

čia   – 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 redaguoti

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

Raktų parinkimo algoritmas redaguoti

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

 

Š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   – yra sparčiai didėjanti seka. Pasirenkame skaičių   taip, kad būtų:

 

Tagu skaičiai   yra tarpusavyje pirminiai su  , t. y.  .

Sudarome raktus. Viešas raktas:

 

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

Privatus raktas:

 

Šifravimas/dešifravimas redaguoti

Tarkime, kad   – pranešimas.

Šifravimas:

 

  – pranešimo   šifras. Dešifravimas:

 
 
 

Dabar, naudojantis algoritmu spręsti poaibio sumos SDS atveju problemą, surandame   – o tai ir yra dešifruotas pranešimas.

Literatūra redaguoti

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

Kitos viešo rakto kriptosistemos redaguoti

  • Rivest-Shamir-Adleman kriptosistema, RSA