Merkle-Hellman kriptosistema

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigacija, 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ų 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[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 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[taisyti | redaguoti kodą]

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[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