Cesko.wiki Zavazadlový algoritmus
Author
Albert FloresZavazadlový 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í. +more 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. +more 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. +more 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. +more 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. +more 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 = r w_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 s r\;\bmod\;q = 1 nebo ekvivalentně existuje celé číslo k takové, že sr = kq + 1. +more 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 s r\;\bmod\;q = 1 a \beta_i = rw_i\;\bmod\;q, platí dále, že
: \beta_i s \equiv w_i r s \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. +more 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'.