Samotný problém ale vyřešen nebyl. Zádrhel je totiž v tom, že navržené kryptografické schéma neodpovídalo matematickému problému úplně. Privátní klíč, jak se po zkoumání zjistilo, je možné možné vypočítat z klíče veřejného i bez řešení příslušné obtížné úlohy, tj. batohu v dané konfiguraci (viz dále). Problém řešení batohu nebyl prostě s problémem výpočtu tajného klíče ekvivalentní. Kdyby šifrovací algoritmus byl přesnou logickou kopií batohu, byl by dodnes bezpečný minimálně tak bezpečný, jak těžké je řešení jakéhokoliv NP-complete problému.
Zadání
Batohový problém má následující jednoduché zadání. Máme k dispozici množinu věcí, každou o určité kladné hmotnosti. Naším úkolem je vybrat takovou podmnožinu, aby její celková "hmotnost" byla rovna nějaké hodnotě w.
Jak se úloha může jevit na první pohled jednoduchá, ve skutečnosti čas potřebný k řešení narůstá exponenciálně s celkovým počtem předmětů. Není znám postup, jak dojít k úspěšnému řešení v polynomiálním čase a mnoho lidí věří, že v něm na deterministickém Turningově stroji není řešitelná. To je velmi dobrý model dnešních počítačů (na nedeterministickém stroji úloha řešitelná je, nicméně v tomto případě se připouští možnost paralelního výpočtu "větví" backtrackingu).
Nicméně existují batohy, jejichž řešení je triviální. Je to v případě, že hmotnost každé položky není nižší, než hmotnost položek předcházejících dohromady. Takovýto batoh nazýváme superrostoucí (superincreasing).
Při výpočtu řešení budeme postupovat následovně. Nejprve vezmeme nejtěžší objekt. Pokud je jeho hmotnost menší než celková požadovaná hmotnost w, zařadíme jej do “použitých” věcí a od w odečteme jeho hmotnost. Pokud ne, necháme jej být a pokračujeme dále. Pokud jsme po prozkoušení všech věcí nedosáhli chtěné hmotnosti (tj. když w != 0), nemá úloha s tímto zadáním řešení.
Máme tedy k dispozici lehkou a těžkou variantu problému. K jeho přetvoření na šifrovací algoritmus s veřejným (a soukromým) klíčem potřebujeme ještě dvě věci. Jednak musíme vymyslet, jak budeme vlastní data šifrovat (tj. jak bude vypadat matematická funkce, která převádí s účastí klíče otevřený text na text zašifrovaný) a jak budeme konvertovat batoh "lehký" na batoh "těžký". Merkle a Hellman navrhli následující metodu.
Konverze z tajného klíče, tj. ze superrostoucího batohu, na klíč veřejný, tj. na normální obtížně řešitelný batoh) bude probíhat následujícím způsobem. Zvolíme modulo m, což bude číslo větší než celkový součet hodnot ("hmotnost") w.
Dále zvolíme druhé číslo n tak, že (n,m)=1, jinými slovy v a m nemají žádného společného dělitele, jsou nesoudělná (v anglické literatuře také často označováno jako relative prime).
Vynásobíme každou hodnotu prvku množiny číslem n (mod m). Některé zdroje na tomto místě ještě udávají vhodnost (pseudo-) náhodné permutace výsledku, která hraje důležitou roli při luštění této šifry. Zde jsem ji pro zjednodušení vypustil.
K zašifrování jednoho bitu použijeme 1, pokud jsme příslušný objekt do batohu zahrnuli a 0 pokud ne.
Příjemce vynásobí hodnoty zašifrovaného textu z-1 mod m, což představuje inverzi n mod m a použije vzniklý superrostoucí batoh k dešifrování zprávy. Pokud tedy platí, že a*z je kongruentní s 1 (mod m), snadno ukážeme, že (a*n mod m)*z mod m = a. Tohoto vztahu budeme využívat při vzájemném přepočítávání (tj. vlastně šifrování a dešifrování) z normálního batohu do superrostoucího a naopak.
Není nad praktickou ukázku
Názorný příklad je vždy nad vší teorii, uvažme tedy batoh [3,4,9,19,38,77]. Zvolíme modul m, větší než součet všech položek batohu, například 155. Jako s m nesoudělné n zvolíme třeba 27. Nyní vypočítáme hodnoty obtížně řešitelného batohu.
3*27 mod 155 = 81
4*27 mod 155 = 108
9*27 mod 155 = 88
19*27 mod 155 = 48
38*27 mod 155 = 96
77*27 mod 155 = 64
Budeme tedy šifrovat s veřejným klíčem [81,108,88,48,96,64]. Zprávu 100110001101010001 si nejprve rozdělíme do jednotlivých bloků, v tomto případě po šesti bitech (naše sada "věcí" má šest hodnot).
100110 001101 010001
Podíváme-li se na první blok, nalezneme hodnoty 1 na prvním, čtvrtém a pátém místě. To odpovídá číslům 81, 48 a 96 ve veřejném batohu, zašifrovaný text tedy bude 81+48+96=225. Obdobně
001101 odpovídá 88+48+64=200
a
010001 odpovídá 108+64=172.
Výsledný zašifrovaný text je tedy [255,200,172]. Pro dešifrování musíme znát inverzi n mod m. Jak už bylo řečeno, je to taková hodnota n*z, pro kterou platí n*z = = 1 (mod m) (= = zde představuje kongruenci). S pomocí tohoto čísla jednoduše pro každý blok spočítáme b*z (mod m). V našem případě z=23.
225*23 mod 155 = 60 = 3+19+38 = 100110
200*23 mod 155 = 105 = 9+19+77 = 001101
172*23 mod 155 = 81 = 4+77 = 010001
Dostali jsme výslednou hodnotu 100110001101010001, která odpovídá původní zprávě.
Později bylo batohové schéma „obohaceno“ o možnost digiálního podpisu dokumentů, obdobně jak je tomu možné jako například u algoritmu RSA. O prolomení tohoto schématu si můžete přečíst například na stránce
http://www.cs.wm.edu/~hallyn/public_key/break.html (z tohoto webu byl převzat příklad). Později byl tento algoritmus zkoušen jako iterační. Říká se, že se Ralph Merkle vsadil o tisíc dolarů, že nikdo nerozluští zprávu 40ti-násobně zašifrovanou. Prohrál.
