Zavazadlový algoritmus

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

Popis

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$ a číslo $b$ a je potřeba najít takovou podmnožinu $A$, jejíž součet je roven $b$. Obecně je tento problém považován za NP-úplný. Pokud je však tato posloupnost superrostoucí, tedy každý prvek množiny $A$ 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íčů

V zavazadlovém algoritmu jsou klíči dvě „zavazadla“. Veřejným klíčem je „složité“ zavazadlo $A$ a soukromým klíčem je „snadné“ zavazadlo $B$, 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í

K zašifrování zprávy je vybrána podmnožina složitého zavazadla $A$, 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 $A_{m}$, zatímco prvky odpovídající číslu 0 v plaintextu jsou při tvorbě $A_{m}$ 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í

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

Generování klíčů

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

$w=(w_{1},w_{2},...,w_{n})$

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

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

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

$q$ 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 $q$ je větší než součet jakékoliv podmnožiny $w$, žádný součet není kongruentní modulo $q$ a tudíž žádný ze soukromých klíčů nebude stejný. $r$ musí být nesoudělné s $q$, v opačném případě nebude mít inverzní modulo $q$. Bez něj by nebylo možné dešifrování.

Nyní je spočítána posloupnost

$\beta =(\beta _{1},\beta _{2},...,\beta _{n})$

kde

$\beta _{i}=rw_{i}\;{\bmod {\;}}q$

Veřejným klíčem je $\beta$, zatímco soukromým klíčem je $(w,q,r)$.

Šifrování

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

$\alpha =(\alpha _{1},\alpha _{2},...,\alpha _{n})$

kde $\alpha _{i}$ je $i$-tý bit zprávy a $\alpha _{i}\in \{0,1\}$, je určeno

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

Šifrovým textem je potom $c$.

Dešifrování

Aby byl příjemce schopen dešifrovat šifrový text $c$, musí najít zprávu s bity $\alpha _{i}$ takovými, aby platilo, že

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

V případě náhodných hodnot $\beta _{i}$ 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 $\beta _{i}$ byly zvoleny tak, aby bylo dešifrování při znalosti soukromého klíče $(w,q,r)$ snadné.

Je potřeba najít celé číslo $s$, jenž je modulární inverzí $r$ modulo $q$. To znamená, že $s$ splňuje rovnici $sr\;{\bmod {\;}}q=1$ nebo ekvivalentně existuje celé číslo $k$ takové, že $sr=kq+1$. Protože $r$ bylo zvoleno tak, že gcd($r,q$)$=1$, je možné nalézt $s$ a $k$ pomocí rozšířeného Euklidova algoritmu. Dále příjemce šifrového textu $c$ spočítá

$c'\equiv cs{\pmod {q}}$

A proto

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

Protože $sr\;{\bmod {\;}}q=1$ a $\beta _{i}=rw_{i}\;{\bmod {\;}}q$, platí dále, že

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

A proto

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

Součet všech hodnot $w_{i}$ je menší než $q$ a proto $\sum _{i=1}^{n}\alpha _{i}w_{i}$ je také v intervalu $[0;q-1]$. Z toho důvodu musí příjemce vyřešit problém součtu podmnožiny

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

Ten je však jednoduchý, protože $w$ je superrostoucí posloupnost. Příjemce vezme největší prvek $w$, dále označený jako $w_{k}$. Pokud je $w_{k}>c'$, potom $\alpha _{k}=0$. Pokud je $w_{k}\leq c'$, potom $\alpha _{k}=1$. Poté odečte $w_{k}\times \alpha _{k}$ od $c'$ a postup opakuje, dokud nezjistí $c'$.

Reference

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