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.^[1] Je jednodušší než RSA a bylo již prokázáno, že jej lze v polynomiálním čase prolomit.^[2]

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 ${\displaystyle A}$ a číslo ${\displaystyle b}$ a je potřeba najít takovou podmnožinu ${\displaystyle A}$, jejíž součet je roven ${\displaystyle 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 ${\displaystyle 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.

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

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

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

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

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

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

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

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

Nyní je spočítána posloupnost

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

kde

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

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

K zašifrování ${\displaystyle n}$-bitové zprávy

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

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

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

Šifrovým textem je potom ${\displaystyle c}$.

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

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

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

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

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

A proto

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

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

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

A proto

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

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

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

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

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