教育部：重点高校招农村和贫困地区学生严防违规

百度 始终要把人民放在心中最高的位置，始终全心全意为人民服务，始终为人民利益和幸福而努力工作。

Zavazadlovy algoritmus je jeden z nejstar?ích zp?sob? ?ifrování s ve?ejnym 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

Zavazadlovy algoritmus je zp?sob asymetrického ?ifrování, co? znamená, ?e jsou pro komunikaci pot?eba dva klí?e: ve?ejny a soukromy. Kromě toho, na rozdíl od RSA, je pouze jednosměrny: ve?ejny klí? je pou?íván pouze pro ?ifrování a soukromy klí? pouze pro de?ifrování. Proto se nedá vyu?ívat pro autentizaci elektronickym podpisem.

Zavazadlovy 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-úplny. Pokud je v?ak tato posloupnost superrostoucí, tedy ka?dy prvek mno?iny $A$ je vět?í ne? sou?et v?ech men?ích prvk? mno?iny, je tento problém ?snadny“ a ?e?itelny v polynomiálním ?ase jednoduchym hladovym algoritmem.

Generování klí??

V zavazadlovém algoritmu jsou klí?i dvě ?zavazadla“. Ve?ejnym klí?em je ?slo?ité“ zavazadlo $A$ a soukromym klí?em je ?snadné“ zavazadlo $B$, spolu s dal?ími dvěma ?ísly, násobitelem a modulem. Násobitel a modul mohou byt 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?itelny 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?dy prvek ve?ejného klí?e, ktery 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 vysledny sou?et je ?ifrovym 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?ejny klí? mohou byt rovně? pou?ity k transformaci ?ísla p?edstavujícího ?ifrového textu na sou?et p?íslu?nych prvk? superrostoucí posloupnosti. Poté, pou?itím jednoduchého hladového algoritmu, m??e byt snadné zavazadlo p?evedeno pomocí O(n) aritmetickych 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$ nenulovych p?irozenych ?í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 samym ?ifrovym textem. Vzhledem k tomu, ?e $q$ je vět?í ne? sou?et jakékoliv podmno?iny $w$, ?ádny sou?et není kongruentní modulo $q$ a tudí? ?ádny ze soukromych klí?? nebude stejny. $r$ musí byt 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?ejnym klí?em je $\beta$, zatímco soukromym 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$-ty bit zprávy a $\alpha _{i}\in \{0,1\}$, je ur?eno

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

?ifrovym textem je potom $c$.

De?ifrování

Aby byl p?íjemce schopen de?ifrovat ?ifrovy text $c$, musí najít zprávu s bity $\alpha _{i}$ takovymi, aby platilo, ?e

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

V p?ípadě náhodnych hodnot $\beta _{i}$ by se jednalo o slo?ity 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í?ny. 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 jednoduchy, proto?e $w$ je superrostoucí posloupnost. P?íjemce vezme největ?í prvek $w$, dále ozna?eny 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.