Zavazadlový algoritmus

způsob šifrování s veřejným klíčem
(přesměrováno z Merkle-Hellman)

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]

PopisEditovat

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

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

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

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á metodaEditovat

Generování klíčůEditovat

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

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

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í  .

ReferenceEditovat

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)