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ų 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 
Kuprinės problema (ang. knapsack problem) yra aibės poaibio sumos problemos atskiras atvejis.

Raktų parinkimo algoritmas 
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 

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 
 A. Menezes, P. van Oorschot, S. Vanstone, 1996, Handbook of Applied Cryptography

Kitos viešo rakto kriptosistemos 

 Rivest-Shamir-Adleman kriptosistema, RSA

Kriptografija