Zádový kryptosystém Merkle-Hellman

Kryptosystém batohu Merkle-Hellman , založený na „ problému batohu “, byl vyvinut Ralphem Merklem a Martinem Hellmanem v roce 1978 [1] . Byl to jeden z prvních kryptosystémů s veřejným klíčem , ale ukázalo se, že je kryptograficky slabý [2] a v důsledku toho si nezískal popularitu.

Popis

"Problém batohu" je následující: pokud známe podmnožinu nákladů zabalených do batohu, je snadné vypočítat celkovou hmotnost , ale při znalosti hmotnosti není snadné určit podmnožinu nákladů. Podrobněji budiž posloupnost n kladných čísel (n je "velikost" batohu)

w = ( w 1 , w 2 , …, w n ) a s .

Úkolem je takový binární vektor najít

x = ( x 1 , x 2 , …, x n ), ( x i = 0 nebo 1),

{\displaystyle s=\sum _{i=1}^{n}x_{i}w_{i))

Pokud je každé binární číslo x spojeno s nějakým písmenem abecedy, pak by mohlo být přenášeno v zašifrované podobě jednoduše jako součet s . Pro libovolnou množinu čísel w i je problém obnovení x z s NP-těžký .

Merkleovi se podařilo získat funkci inverzní k číslu s , která by dala vektor x , znal pouze jistý „tajný“ klíč a nabídl 100 dolarů někomu, kdo by mohl objevit zádový systém Merkle-Hellman.

Podívejme se na to podrobněji.

Merkle nepoužil libovolnou posloupnost w i , ale superrostoucí, tedy takovou, že

{\displaystyle w_{k+1}>\sum _{i=1}^{k}w_{i))

Je snadné vidět, že pro takový soubor čísel je řešení úlohy triviální. Abychom se této triviality zbavili, bylo nutné zavést „tajný klíč“, konkrétně dvě čísla: q takové, že a r takové, že gcd(r, q) =1. A nyní místo původní množiny čísel w i použijeme čísla b i =r w i mod q . V původních dokumentech Merkle doporučoval používat n řádově 100, kde n je počet prvků v supernarůstající posloupnosti ("velikost" batohu). ${\displaystyle q>\sum _{i=1}^{n}w_{i))$

Ve výsledku získáme: veřejný klíč - ( b 1 , b 2 , ..., b n ), soukromý klíč - ( w 1 , w 2 , ..., w n ; q , r ).

Šifrování

– zpráva x = ( x 1 , x 2 , ..., x n ) - vypočítat y = b 1 x 1 + b 2 x 2 + , ..., + b n x n

Dešifrování

- vypočítat s = yr -1 mod q - vyřešit úlohu pro s pro superrostoucí posloupnost ( w 1 , w 2 , ..., w n ), tzn. najít binární číslo x

Ocenění získal A. Shamir poté, co v březnu 1982 zveřejnil zprávu o odhalení zádového systému Merkle-Hellman s jednou iterací. Všimněte si, že Shamir dokázal sestrojit klíč, který se nemusí nutně rovnat tajemství, ale umožňuje vám otevřít šifru .

Takže to byl jeden z neúspěšných, ale velmi zajímavých pokusů vybudovat kryptosystém založený na problému batohu.

Generování klíčů

V systému Merkle-Hellman se klíče skládají ze sekvencí. Veřejný klíč je „komplexní“ posloupnost, soukromý klíč se skládá z „jednoduché“ nebo supernarůstající posloupnosti a také dvou dalších čísel – násobiče a modulu, které se používají k převodu supernarůstající posloupnosti na „komplexní“ jeden (generování veřejného klíče) a na transformaci součtu podmnožiny "komplexní" sekvence na součet podmnožiny "jednoduché" sekvence (dešifrování). Poslední problém je řešen v polynomiálním čase .

Šifrování

Za prvé, zdrojový text musí být reprezentován v binární formě a rozdělen do bloků, které mají stejnou délku jako veřejný klíč. Dále, ze sekvence, která tvoří veřejný klíč, se vyberou pouze ty prvky, které odpovídají v pořadí 1 v binárním zápisu zdrojového textu, přičemž se ignorují prvky odpovídající bitu 0 . Poté jsou přidány prvky výsledné podmnožiny. Výsledný součet je šifrový text.

Dešifrování

Dešifrování je možné, protože multiplikátor a modul použitý pro generování veřejného klíče ze supernarůstající sekvence se také používá k převodu šifrovaného textu na součet odpovídajících prvků supernarůstající sekvence. Dále pomocí jednoduchého chamtivého algoritmu lze zprávu dešifrovat pomocí aritmetických operací O(n).

Matematický popis algoritmu

Generování klíčů

Pro zašifrování n - bitové zprávy zvolíme super rostoucí posloupnost n nenulových přirozených čísel

w = ( w1 , w2 , … , wn ) .

Dále náhodně vybereme koprimá celá čísla q a r taková, že

{\displaystyle q>\sum _{i=1}^{n}w_{i))

Číslo q je zvoleno tak, aby byla zaručena jedinečnost (jedinečnost) šifrového textu. Pokud je to alespoň o něco méně, může nastat situace, že jednomu šifrovanému textu bude odpovídat více zdrojových (otevřených) textů. r musí být coprime s q , jinak nebude mít multiplikativní inverzní modulo q , jehož existence je nezbytná pro dešifrování.

Nyní sestavíme sekvenci

β = (β 1 , β 2 , …, β n ),

kde každý prvek se vypočítá podle následujícího vzorce

β i = rw i mod q .

β bude veřejný klíč, zatímco soukromý klíč tvoří sekvenci ( w , q , r ).

Šifrování

K zašifrování n - bitové zprávy

α = (α 1 , α 2 , …, α n ),

kde je i -tý bit, tedy {0, 1}, vypočítáme číslo c, které bude šifrovým textem. $\alpha_i$ $\alpha _{i}{\boldsymbol {\in }}$

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Dešifrování

Pro přečtení původního textu musí příjemce určit bity zprávy , které by odpovídaly vzorci $\alpha_i$

c=\sum _{i=1}^{n}\alpha _{i}\beta _{i}.

Takový problém by byl NP-těžký , kdyby β i byly náhodně vybrané hodnoty. Hodnoty βi však byly zvoleny tak, že dešifrování je jednoduchý úkol, za předpokladu, že je znám soukromý klíč ( w , q , r ).

Klíčem k nalezení zdrojového textu je najít celé číslo s , které je multiplikativní inverzí k r modulo q . To znamená, že s splňuje rovnici sr mod q = 1, což je ekvivalentní existenci celého čísla k takové, že sr = kq + 1. Protože r je coprime k q , je možné najít s a k pomocí rozšířeného euklidovského algoritmu . Dále počítá příjemce šifrovaného textu

c'\equiv cs{\pmod {q)).

Odtud

c'\equiv cs\equiv \sum _{i=1}^{n}\alpha _{i}\beta _{i}s{\pmod {q)).

Z toho, že rs mod q = 1 a βi = rwi mod q

\beta _{i}s\equiv w_{i}rs\equiv w_{i}{\pmod {q)).

Pak

c'\equiv \sum _{i=1}^{n}\alpha _{i}w_{i}{\pmod {q)).

Součet všech w i je menší než q . Hodnota je tedy také v intervalu [0,q-1]. Příjemce tedy musí z podmínky určit, že $\sum _{i=1}^{n}\alpha _{i}w_{i}$ $\alpha_i$

c'=\sum _{i=1}^{n}\alpha _{i}w_{i}.

A to je již snadný úkol, protože w je superrostoucí posloupnost. Nechť w k je největší prvek v w . Jestliže w k > c' , pak α k = 0; jestliže w k ≤c' , pak α k = 1. Dále odečtěte součin w k × α k od c' a tyto kroky opakujte, dokud nevypočítáme α.

Příklad

w = {2, 7, 11, 21, 42, 89, 180, 354} je superrostoucí sekvence.

Je základem pro generování soukromého klíče. Vypočítejte součet prvků posloupnosti

\sum w=706

Dále zvolíme prvočíslo q , které přesahuje hodnotu námi získaného součtu.

q = 881

Také volíme číslo r z intervalu [1,q]

r = 588

w , q a r tvoří soukromý klíč.

Abychom vygenerovali veřejný klíč , zkonstruujeme posloupnost β vynásobením každého prvku ze sekvence w r modulo q .

2 * 588 mod 881 = 295 7 * 588 mod 881 = 592 11 * 588 mod 881 = 301 21 * 588 mod 881 = 14 42 * 588 mod 881 = 28 89 * 588 mod 881 = 353 180 * 588 mod 881 = 120 354 * 588 mod 881 = 236 Dostaneme β = (295, 592, 301, 14, 28, 353, 120, 236).

Posloupnost β tvoří veřejný klíč.

Ať Alice chce zašifrovat „a“. Nejprve musí převést "a" na binární

01100001

Poté vynásobí každý bit odpovídajícím číslem ze sekvence β a součet hodnot odešle příjemci.

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

K dešifrování zprávy Bob vynásobí hodnotu, kterou obdržel, multiplikativní inverzí r modulo q .

1129 * 442 mod 881 = 372

Poté Bob rozloží 372 následovně. Nejprve vybere největší prvek z w, který je menší než 372 a vypočítá jejich rozdíl. Dále vybere další největší prvek, který je menší než výsledný rozdíl, a tyto kroky opakuje, dokud rozdíl nebude nulový.

372 - 354 = 18 18 - 11 = 7 7 - 7 = 0

Prvky, které byly vybrány z w , budou odpovídat 1 v binárním zápisu zdroje.

01100001

Zpětným překladem z binárního zápisu získá Bob konečně požadované „a“.

Viz také

Poznámky

↑ Ralph Merkle a Martin Hellman, Skrytí informací a podpisů v batohu Trapdoor, IEEE Trans. Information Theory , 24(5), září 1978, str. 525-530.
↑ Adi Shamir, Polynomiální časový algoritmus pro prolomení základního kryptosystému Merkle-Hellman. CRYPTO 1982, str. 279-288. Archivovaná kopie . Získáno 6. prosince 2005. Archivováno z originálu 24. dubna 2005. (neurčitý)

Literatura

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .

Odkazy

Problém s batohem
Aplikace	Problém batohu v kryptografii Řezací úkol
Kryptosystémy založené na problému batohu	Merkla-Hellman Naccasha - Stern Graham - Shamira
dodatečně	Seznam úkolů o batohu

Kryptosystémy s veřejným klíčem

Algoritmy

Faktorizace celých čísel	kryptosystém Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern zaplatit Rabin RSA Okamoto – Uchijama Schmidt-Samoa
Diskrétní logaritmus	BLS Cramer - Shoup protokol Diffie-Hellman DSA ECDH Křivka25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Výměna šifrovaných klíčů Schéma ElGamal podpisové schéma MQV Schnorrovo schéma SPEKE SRP STS
Kryptografie na mřížkách	NTRUEncrypt NTRUSsign Výměna klíčů založená na učení s chybami Trénink založený na podpisu s chybami v kruhu BLAHO Nová naděje
jiný	AE CEILIDH EPOC Rovnice skrytého pole IES Lamportův podpis McEliece Zádový kryptosystém Merkle-Hellman Zádový kryptosystém Naccache–Stern Tříkrokový protokol XTR

Teorie

Diskrétní logaritmus na eliptické křivce
Eliptická kryptografie
Kryptografie založená na hash
Nekomutativní kryptografie
Problém RSA
Jednosměrná funkce s tajným vstupem

Normy

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantová kryptografie

Témata

Elektronický podpis
OAEP
Otisk prstu
PKI
síť důvěry
Velikost klíče
Kryptografie založená na identitě
Postkvantová kryptografie
OpenPGP karta