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