Zavazadlový algoritmus

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

Zavazadlový algoritmus je jeden z nejstarších způsobů šifrování s veřejným klíčem. Byl vyvinut Ralphem MerklemMartinem Hellmanem v roce 1978.[1] Je jednodušší než RSA a bylo již prokázáno, že jej lze v polynomiálním čase prolomit.[2]

Popis[editovat | editovat zdroj]

Zavazadlový algoritmus je způsob asymetrického šifrování, což znamená, že jsou pro komunikaci potřeba dva klíče: veřejný a soukromý. Kromě toho, na rozdíl od RSA, je pouze jednosměrný: veřejný klíč je používán pouze pro šifrování a soukromý klíč pouze pro dešifrování. Proto se nedá využívat pro autentizaci elektronickým podpisem.

Zavazadlový algoritmus je založen na problému součtu podmnožiny (speciální případ problému batohu). Problém je následující: je dána množina čísel a číslo a je potřeba najít takovou podmnožinu , jejíž součet je roven . Obecně je tento problém považován za NP-úplný. Pokud je však tato posloupnost superrostoucí, tedy každý prvek množiny je větší než součet všech menších prvků množiny, je tento problém „snadný“ a řešitelný v polynomiálním čase jednoduchým hladovým algoritmem.

Generování klíčů[editovat | editovat zdroj]

V zavazadlovém algoritmu jsou klíči dvě „zavazadla“. Veřejným klíčem je „složité“ zavazadlo a soukromým klíčem je „snadné“ zavazadlo , spolu s dalšími dvěma čísly, násobitelem a modulem. Násobitel a modul mohou být použity k převedení superrostoucí posloupnosti do složitého zavazadla. Stejná čísla jsou použita k převedení součtu podmnožiny složitého zavazadla na součet podmnožiny snadného zavazadla, což je problém řešitelný v polynomiálním čase.

Šifrování[editovat | editovat zdroj]

K zašifrování zprávy je vybrána podmnožina složitého zavazadla , a to porovnáním množiny bitů (plaintextu) s touto množinou. Každý prvek veřejného klíče, který odpovídá číslu 1 plaintextu, je prvkem podmnožiny , zatímco prvky odpovídající číslu 0 v plaintextu jsou při tvorbě ignorovány – nejsou prvky klíče. Prvky této podmnožiny jsou sečteny a výsledný součet je šifrovým textem.

Dešifrování[editovat | editovat zdroj]

Dešifrování je možné, protože násobitel a modul požité k převedení snadného zavazadla na veřejný klíč mohou být rovněž použity k transformaci čísla představujícího šifrového textu na součet příslušných prvků superrostoucí posloupnosti. Poté, použitím jednoduchého hladového algoritmu, může být snadné zavazadlo převedeno pomocí O(n) aritmetických operací na plaintext.

Matematická metoda[editovat | editovat zdroj]

Generování klíčů[editovat | editovat zdroj]

K zašifrování -bitové zprávy je vybrána superrostoucí posloupnost

nenulových přirozených čísel. Je vybráno náhodné celé číslo pro které platí, že

a náhodné celé číslo , pro které platí, že gcd() (tzn. jsou nesoudělná).

je voleno tímto způsobem proto, aby byla zajištěna unikátnost šifrového textu. Pokud by bylo menší, bylo by možné více než jeden plaintext zašifrovat tím samým šifrovým textem. Vzhledem k tomu, že je větší než součet jakékoliv podmnožiny , žádný součet není kongruentní modulo a tudíž žádný ze soukromých klíčů nebude stejný. musí být nesoudělné s , v opačném případě nebude mít inverzní modulo . Bez něj by nebylo možné dešifrování.

Nyní je spočítána posloupnost

kde

Veřejným klíčem je , zatímco soukromým klíčem je .

Šifrování[editovat | editovat zdroj]

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

kde je -tý bit zprávy a , je určeno

Šifrovým textem je potom .

Dešifrování[editovat | editovat zdroj]

Aby byl příjemce schopen dešifrovat šifrový text , musí najít zprávu s bity takovými, aby platilo, že

V případě náhodných hodnot by se jednalo o složitý problém, protože by příjemce musel vyřešit problém součtu podmnožiny, jenž je považován za NP-obtížný. Nicméně hodnoty byly zvoleny tak, aby bylo dešifrování při znalosti soukromého klíče snadné.

Je potřeba najít celé číslo , jenž je modulární inverzí modulo . To znamená, že splňuje rovnici nebo ekvivalentně existuje celé číslo takové, že . Protože bylo zvoleno tak, že gcd(), je možné nalézt pomocí rozšířeného Euklidova algoritmu. Dále příjemce šifrového textu spočítá

A proto

Protože , platí dále, že

A proto

Součet všech hodnot je menší než a proto je také v intervalu . Z toho důvodu musí příjemce vyřešit problém součtu podmnožiny

Ten je však jednoduchý, protože je superrostoucí posloupnost. Příjemce vezme největší prvek , dále označený jako . Pokud je , potom . Pokud je , potom . Poté odečte od  a postup opakuje, dokud nezjistí .

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Merkle–Hellman knapsack cryptosystem na anglické Wikipedii.

  1. MERKLE, Ralph; HELLMAN, Martin. Hiding information and signatures in trapdoor knapsacks. IEEE Transactions on Information Theory. Roč. 24, čís. 5, s. 525–530. DOI:10.1109/TIT.1978.1055927. (anglicky) 
  2. SHAMIR, Adi. A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem. IEEE Transactions on Information Theory. Roč. 30, čís. 5, s. 699–704. DOI:10.1109/TIT.1984.1056964. (anglicky)