Kryptosystém batoh Merkle – Hellman - Merkle–Hellman knapsack cryptosystem

The Kryptosystém batoh Merkle – Hellman byl jedním z prvních veřejný klíč kryptosystémy. To bylo publikováno Ralph Merkle a Martin Hellman v roce 1978. Polynomiální časový útok publikoval Adi Shamir v roce 1984. Výsledkem je, že kryptosystém je nyní považován za nejistý.^[1]^:465 ^[2]^:190

Dějiny

Koncept kryptografie veřejného klíče byl představen Whitfield Diffie a Martin Hellman v roce 1976^[3]. V té době navrhli pouze obecný koncept „funkce padacích dveří“, což je funkce, kterou je výpočetně nemožné vypočítat bez nějakých tajných „informací o padacích dveřích“, ale dosud nenalezli praktický příklad takové funkce. Několik konkrétních kryptosystémů s veřejným klíčem poté v průběhu příštích několika let navrhli jiní vědci, například RSA v roce 1977 a Merkle-Hellman v roce 1978.^[4]

Popis

Merkle – Hellman je kryptosystém veřejného klíče, což znamená, že jsou použity dva klíče, veřejný klíč pro šifrování a soukromý klíč pro dešifrování. Je založen na problém s podmnožinou (zvláštní případ batoh problém ).^[5] Problém je následující: daný soubor celých čísel ${ displaystyle A}$ a celé číslo ${ displaystyle c}$ , najít podmnožinu ${ displaystyle A}$ které součty ${ displaystyle c}$ . Obecně je o tomto problému známo, že je NP-kompletní. Pokud však ${ displaystyle A}$ je superzvýšení, což znamená, že každý prvek množiny je větší než součet všech čísel v množině menší, je problém „snadný“ a řešitelný v polynomiálním čase s jednoduchým chamtivý algoritmus.

V Merkle – Hellman dešifrování zprávy vyžaduje vyřešení zjevně „tvrdého“ problému s batohem. Soukromý klíč obsahuje mimořádně rostoucí seznam čísel ${ displaystyle W}$ a veřejný klíč obsahuje nepřesahující seznam čísel ${ displaystyle B}$ , což je ve skutečnosti "maskovaná" verze ${ displaystyle W}$ . Soukromý klíč také obsahuje některé informace o „poklopu“, které lze použít k transformaci problému s pevným batohem pomocí ${ displaystyle B}$ do snadného použití batohu ${ displaystyle W}$ .

Na rozdíl od některých jiných kryptosystémů veřejného klíče, jako je RSA, dva klíče v Merkle-Hellman nejsou zaměnitelné; soukromý klíč nelze použít k šifrování. Merkle-Hellman tedy není přímo použitelný pro autentizaci pomocí kryptografické podepisování, ačkoli Shamir zveřejnil variantu, kterou lze použít k podpisu.^[6]

Generování klíčů

1. Vyberte velikost bloku ${ displaystyle n}$ . Celá čísla až ${ displaystyle n}$ tímto klíčem lze zašifrovat bity na délku.

2. Vyberte náhodnou superrychlou sekvenci ${ displaystyle n}$ kladná celá čísla

{ displaystyle W = (w_ {1}, w_ {2}, tečky, w_ {n})}

To znamená velmi vysoký požadavek

{ displaystyle w_ {k}> součet _ {i = 1} ^ {k-1} w_ {i}}

, pro

{ displaystyle 1

.

3. Vyberte náhodné celé číslo ${ displaystyle q}$ takhle

{ displaystyle q> součet _ {i = 1} ^ {n} w_ {i}}

4. Vyberte náhodné celé číslo ${ displaystyle r}$ takhle ${ displaystyle gcd (r, q) = 1}$ (to znamená, ${ displaystyle r}$ a ${ displaystyle q}$ jsou coprime ).

5. Vypočítejte posloupnost

{ displaystyle B = (b_ {1}, b_ {2}, tečky, b_ {n})}

kde

{ displaystyle b_ {i} = rw_ {i} { bmod {q}}}

.

Veřejný klíč je ${ displaystyle B}$ a soukromý klíč je ${ displaystyle (W, q, r)}$ .

Šifrování

Nechat ${ displaystyle m}$ být ${ displaystyle n}$ -bitová zpráva skládající se z bitů ${ displaystyle m_ {1} m_ {2} tečky m_ {n}}$ , s ${ displaystyle m_ {1}}$ bit nejvyššího řádu. Vyberte každý ${ displaystyle b_ {i}}$ pro který ${ displaystyle m_ {i}}$ je nenulová a sečtěte je dohromady. Ekvivalentně vypočítat

{ displaystyle c = sum _ {i = 1} ^ {n} m_ {i} b_ {i}}

.

Šifrovací text je ${ displaystyle c}$ .

Dešifrování

K dešifrování šifrovacího textu ${ displaystyle c}$ , musíme najít podmnožinu ${ displaystyle B}$ které součty ${ displaystyle c}$ . Děláme to transformací problému na jeden z hledání podmnožiny ${ displaystyle W}$ . Tento problém lze od té doby vyřešit v polynomiálním čase ${ displaystyle W}$ je superincreasing.

1. Vypočítejte modulární inverzní z ${ displaystyle r}$ modulo ${ displaystyle q}$ za použití Rozšířený euklidovský algoritmus. Inverzní bude existovat od ${ displaystyle r}$ je coprime ${ displaystyle q}$ .

{ displaystyle r ': = r ^ {- 1} { pmod {q}}}

Výpočet

{ displaystyle r '}

je nezávislá na zprávě a lze ji provést pouze jednou, když je vygenerován soukromý klíč.

2. Vypočítat

{ displaystyle c ': = cr' { bmod {q}}}

3. Vyřešte problém se součtem podmnožiny pro ${ displaystyle c '}$ pomocí superincreasing sekvence ${ displaystyle W}$ jednoduchým chamtivým algoritmem popsaným níže. Nechat ${ displaystyle X = (x_ {1}, x_ {2}, tečky, x_ {k})}$ být výsledným seznamem indexů prvků ${ displaystyle W}$ který součet ${ displaystyle c '}$ . (To znamená, ${ displaystyle c '= součet _ {i = 1} ^ {k} w_ {x_ {i}}}$ .)

4. Vytvořte zprávu ${ displaystyle m}$ s 1 v každém ${ displaystyle x_ {i}}$ bitová pozice a 0 ve všech ostatních bitových pozicích:

{ displaystyle m = suma _ {i = 1} ^ {k} 2 ^ {n-x_ {i}}}

Řešení problému součtu podmnožiny

Tento jednoduchý chamtivý algoritmus najde podmnožinu superrychlé sekvence ${ displaystyle W}$ které součty ${ displaystyle c '}$ , v polynomiálním čase:

1. Inicializujte

{ displaystyle X}

do prázdného seznamu.

2. Najděte největší prvek v

{ displaystyle W}

což je menší nebo rovno

{ displaystyle c '}

, řekněme

{ displaystyle w_ {j}}

.

3. Odečíst:

{ displaystyle c ': = c'-w_ {j}}

.

4. Připojit

{ displaystyle j}

do seznamu

{ displaystyle X}

.

5. Pokud

{ displaystyle c '}

je větší než nula, vraťte se ke kroku 2.

Příklad

Generování klíčů

Vytvořte klíč k šifrování 8bitových čísel vytvořením náhodné superzvýšené sekvence 8 hodnot:

{ displaystyle W = (2,7,11,21,42,89,180,354)}

Součet z nich je 706, proto vyberte větší hodnotu pro ${ displaystyle q}$ :

{ displaystyle q = 881}

.

Vybrat ${ displaystyle r}$ být coprime ${ displaystyle q}$ :

{ displaystyle r = 588}

.

Vytvořte veřejný klíč ${ displaystyle B}$ vynásobením každého prvku v ${ displaystyle W}$ podle ${ displaystyle r}$ modulo ${ displaystyle q}$ :

{ displaystyle { begin {aligned} & (2 * 588) { bmod {8}} 81 = 295 & (7 * 588) { bmod {8}} 81 = 592 & (11 * 588 ) { bmod {8}} 81 = 301 & (21 * 588) { bmod {8}} 81 = 14 & (42 * 588) { bmod {8}} 81 = 28 & (89 * 588) { bmod {8}} 81 = 353 & (180 * 588) { bmod {8}} 81 = 120 & (354 * 588) { bmod {8}} 81 = 236 end {zarovnáno}}}

Proto ${ displaystyle B = (295 592 301,14,28 353 120 236)}$ .

Šifrování

Nechť je 8bitová zpráva ${ displaystyle m = 97 = 01100001_ {2}}$ . Násobíme každý bit odpovídajícím číslem v ${ displaystyle B}$ a přidejte výsledky:

  0 * 295+ 1 * 592+ 1 * 301+ 0 * 14+ 0 * 28+ 0 * 353+ 0 * 120+ 1 * 236    = 1129

Šifrový text ${ displaystyle c}$ je 1129.

Dešifrování

K dešifrování 1129 nejprve použijte Extended Euclidean Algorithm k nalezení modulární inverze ${ displaystyle r}$ mod ${ displaystyle q}$ :

{ displaystyle r '= r ^ {- 1} { bmod {q}} = 588 ^ {- 1} { bmod {8}} 81 = 442}

.

Vypočítat ${ displaystyle c '= cr' { bmod {q}} = 1129 * 442 { bmod {8}} 81 = 372}$ .

Pomocí chamtivého algoritmu rozložte 372 na součet ${ displaystyle w_ {i}}$ hodnoty:

{ displaystyle { begin {zarovnáno} c '& = 372 & w_ {8} = 354 leq 372 c' & = 372-354 = 18 & w_ {3} = 11 leq 18 c '& = 18-11 = 7 & w_ {2} = 7 leq 7 c' & = 7-7 = 0 end {zarovnáno}}}

Tím pádem ${ displaystyle 372 = 354 + 11 + 7 = w_ {8} + w_ {3} + w_ {2}}$ a seznam indexů je ${ displaystyle X = (8,3,2)}$ . Zprávu lze nyní vypočítat jako

{ displaystyle m = sum _ {i = 1} ^ {3} 2 ^ {n-x_ {i}} = 2 ^ {8-8} + 2 ^ {8-3} + 2 ^ {8-2 } = 1 + 32 + 64 = 97}

.

Kryptoanalýza

V roce 1984 Adi Shamir zveřejnil útok na kryptosystém Merkle-Hellman, který dokáže dešifrovat šifrované zprávy v polynomiálním čase bez použití soukromého klíče. ^[7] Útok analyzuje veřejný klíč ${ displaystyle B = (b_ {1}, b_ {2}, tečky, b_ {n})}$ a hledá dvojici čísel ${ displaystyle u}$ a ${ displaystyle m}$ takhle ${ displaystyle (ub_ {i} { bmod {m}})}$ je superrychle rostoucí sekvence. The ${ displaystyle (u, m)}$ pár nalezený útokem se nemusí rovnat ${ displaystyle (r ', q)}$ v soukromém klíči, ale stejně jako tento pár může být použit k transformaci problému s pevným batohem pomocí ${ displaystyle B}$ do snadného problému s použitím superincidující sekvence. Útok funguje pouze na veřejném klíči; není nutný přístup k šifrovaným zprávám.

Reference

^ Schneier, Bruce (1996). Aplikovaná kryptografie. New York: John Wiley & Sons. ISBN 0-471-12845-7.
^ Stinson, Douglas R. (1995). Kryptografie: teorie a praxe. Boca Raton: CRC Press. ISBN 0-8493-8521-0.
^ Whitfield Diffie; Martin Hellman (1976). "Nové směry v kryptografii". Transakce IEEE na teorii informací. 22 (6): 644. CiteSeerX 10.1.1.37.9720. doi:10.1109 / TIT.1976.1055638.
^ Merkle, Ralph; Hellman, Martin (1978). "Skrytí informací a podpisů v batohu padacích dveří". Transakce IEEE na teorii informací. 24 (5): 525–530. doi:10.1109 / TIT.1978.1055927.
^ Cherowitzo, William (02.03.2002). „Kryptosystém Merkle-Hellman Knapsack Cryptosystem“. Math 5410 - Modern Cryptology. Citováno 2019-08-18.
^ Shamir, Adi (červenec 1978). "Schéma rychlého podpisu". Technické memorandum o laboratoři MIT pro informatiku. 79 (MIT / LCS / TM – 107): 15240. Bibcode:1978STIN ... 7915240S.
^ Shamir, Adi (1984). "Algoritmus polynomiálního času pro rozbití základního kryptosystému Merkle - Hellman". Transakce IEEE na teorii informací. 30 (5): 699–704. doi:10.1109 / SFCS.1982.5.

[schneier-1] Schneier, Bruce (1996). Aplikovaná kryptografie. New York: John Wiley & Sons. ISBN 0-471-12845-7.

[stinson-2] Stinson, Douglas R. (1995). Kryptografie: teorie a praxe. Boca Raton: CRC Press. ISBN 0-8493-8521-0.

[newdirections-3] Whitfield Diffie; Martin Hellman (1976). "Nové směry v kryptografii". Transakce IEEE na teorii informací. 22 (6): 644. CiteSeerX 10.1.1.37.9720. doi:10.1109 / TIT.1976.1055638.

[merkle_hellman-4] Merkle, Ralph; Hellman, Martin (1978). "Skrytí informací a podpisů v batohu padacích dveří". Transakce IEEE na teorii informací. 24 (5): 525–530. doi:10.1109 / TIT.1978.1055927.

[5] Cherowitzo, William (02.03.2002). „Kryptosystém Merkle-Hellman Knapsack Cryptosystem“. Math 5410 - Modern Cryptology. Citováno 2019-08-18.

[6] Shamir, Adi (červenec 1978). "Schéma rychlého podpisu". Technické memorandum o laboratoři MIT pro informatiku. 79 (MIT / LCS / TM – 107): 15240. Bibcode:1978STIN ... 7915240S.

[shamir-7] Shamir, Adi (1984). "Algoritmus polynomiálního času pro rozbití základního kryptosystému Merkle - Hellman". Transakce IEEE na teorii informací. 30 (5): 699–704. doi:10.1109 / SFCS.1982.5.

[1]

[2]

[3]

[4]

[5]

[6]

[7]