Kryptografie na mřížce a ortogonalizace

Metody asymetrické kryptografie umožňují navázat šifrované spojení přes nezabezpečený kanál. Většina stávajících implementací v oblasti asymetrické kryptografie se přitom opírá buď o problém faktorizace složeného čísla (algoritmus RSA), nebo o problém diskrétního logaritmu (Diffieho-Hellmanova výměna klíčů). S příchodem dostatečně výkonných kvantových počítačů by však bylo možné oba problémy efektivně řešit pomocí Shorova algoritmu a současné šifrovací systémy by již nebyly bezpečné. V článku Základy mřížkové kryptografie jsme se začali zabývat vytvářením asymetrického šifrovacího systému, jehož bezpečnost by byla založena na problémech známých ze studia mřížek. Seznámili jsme se s pojmem mřížka, což je množina celočíselných lineárních kombinací tvaru \[ L=\left\{ \sum_{i=1}^n a_i v_i \,\Big\vert\, a_i\in\mathbb{Z}\right\}, \] nalezli jsme vztah mezi bázemi $(v_1,\ldots,v_n)$ a $(w_1,\ldots,w_n)$ téže mřížky a zavedli determinant mřížky. Představili jsme také dvě NP-těžké úlohy spojené s mřížkami, konkrétně problém hledání nejkratšího nenulového vektoru $v\in L$ (SVP) a problém hledání nejbližšího vektoru $v\in L$ (CVP) pro předem zadaný vektor $w\in\mathbb{R}^n$. Na příkladech jsme si ukázali, že řešení uvedených problémů je v některých bázích velmi jednoduché, zatímco pro jiné může být obtížné. Co je tedy tou vlastností odlišující "dobré" a "špatné" báze?

Ortogonalizace

Předpokládejme nyní, že naše mřížka $L$ je zadána pomocí ortogonální báze $(v_1,\ldots, v_n)$, tedy báze, pro jejíž vektory platí \[ \langle v_i,v_j \rangle = 0 \text{ pro } i\neq j, \] kde $\langle .,. \rangle$ je standardní skalární součin. Pro velikost libovolného vektoru $x\in L$ pak dostaneme \begin{align*} ||x||^2 & =\langle x, x\rangle=\langle a_1 v_1+\ldots+a_n v_n,a_1 v_1+\ldots+a_n v_n\rangle=\\ &=a_1^2\langle v_1, v_1\rangle + \ldots +a_n^2\langle v_n, v_n\rangle =a_1^2||v_1||^2 + \ldots +a_n^2||v_n||^2. \end{align*} Jelikož $a_i\in\mathbb{Z},\ i\in\{1,\ldots,n\}$, nejkratší nenulové vektory mřížky leží v množině $\{\pm v_1, \ldots, \pm v_n\}$. Řešením SVP je tedy nejkratší vektor ortogonální báze.

Hledejme nyní vektor $v=\sum_{i=1}^n a_i v_i,\ a_i \in \mathbb{Z}$, ležící v $L$ takový, že jeho vzdálenost od daného $w\in \mathbb{R}^n$ je minimální. Vektory $v_i$ tvoří bázi $\mathbb{R}^n$ a $w$ lze vyjádřit jako $w=\sum_{i=1}^n \alpha_i v_i$, kde ovšem $\alpha_i \in \mathbb{R}$. Pro vzdálenost $w$ a $v$ bude platit \[ ||w-v||^2=(\alpha_1-a_1)^2||v_1||^2 + \ldots +(\alpha_n-a_n)^2||v_n||^2. \] Tento výraz lze zjevně minimalizovat tak, že za $a_i$ vybereme celá čísla nejbližší koeficientům $\alpha_i$. Řešením CVP je tedy vektor $v=\sum_{i=1}^n \lfloor\alpha_i\rceil v_i$, kde symbol $\lfloor . \rceil$ značí zaokrouhlení na nejbližší celé číslo.

Příklad 1

Uvedené metody řešení SVP a CVP jsme již minule demonstrovali na příkladu mřížky $L$ generované bázemi $(v_1,v_2)=((1,0),(0,1))$ a $(w_1,w_2)=((3,2),(2,1))$. Vektory báze $(v_1, v_2)$ mají velikost $1$ a tudíž řeší SVP. Pro $(w_1, w_2)$ to neplatí. Pro $w=(0.8,1.2)$ je řešením CVP vektor $(1,1)$, který lze získat jako \[ w=0.8 \cdot v_1 + 1.2\cdot v_2, \qquad \lfloor 0.8 \rceil \cdot v_1 + \lfloor 1.2 \rceil\cdot v_2 = v_1 + v_2 = (1,1). \] V bázi $(w_1, w_2)$ bychom ale touto metodou dostali vektor $(2,2)$.

Máme-li k dispozici ortogonální bázi mřížky, je řešení obou problémů poměrně přímočaré. Díky zkušenosti získané v předchozím příkladu očekáváme, že čím více se zadaná báze liší od ortogonální, tím méně budou uvedené metody spolehlivé. Zkusme se tedy podívat, jak lze ortogonální báze hledat.

Je-li $(v_1,\ldots,v_n)$ zadaná báze vektorového prostoru $\mathbb{R}^n$, lze ortogonální bázi $\mathbb{R}^n$ tvořenou vektory $(v_1^*,\ldots,v_n^*)$ nalézt pomocí následujícího Grammova-Schmidtova algoritmu:

1. polož $v_1^*:=v_1$,

2. pro $i= 2, 3, \ldots, n$ postupně spočti \[ v_i^*:=v_i - \sum_{j=1}^{i-1} \mu_{ij} v_j^*, \quad \text{kde } \mu_{ij}=\frac{\langle v_i, v_j^*\rangle}{||v_j^*||^2}. \]

Algoritmus postupně hledá ortogonální báze podprostorů vyšší a vyšší dimenze generovaných soubory $(v_1,\ldots,v_i),\ i=1, 2, \ldots, n$. Na začátku zvolíme jako bazický vektor $v_1^*$ přímo vektor $v_1$. Ortogonální bázi podprostoru generovaného souborem $(v_1, v_2)$ pak nalezneme jako vhodnou lineární kombinaci $v_1$ a $v_2$. Takových kombinací existuje nekonečně mnoho, my ale budeme hledat ortogonální bázi $(v_1^*,v_2^*)$ tak, aby $v_1^*=v_1$ a $v_2^*$ bylo ve tvaru \[ v_2^*=v_2-\mu_{21}v_1^*, \qquad \mu_{21}\in\mathbb{R}. \] Hodnotu $\mu_{21}$ určíme z požadavku aby $v_1^*$ a $v_2^*$ byly kolmé. To nastane tehdy, když je splněna podmínka \[ \langle v_2^*, v_1^*\rangle=\langle v_2-\mu_{21}v_1^*, v_1^*\rangle=\langle v_2, v_1^*\rangle -\mu_{21}\langle v_1^*, v_1^*\rangle = 0, \] tedy když \[ \mu_{21}=\frac{\langle v_2, v_1^*\rangle}{||v_1^*||^2}. \] V předchozí úpravě jsme využili linearity skalárního součinu. Ortogonální bázi prostoru generovaného $(v_1, v_2, v_3)$ pak nalezneme ve tvaru $(v_1^*,v_2^*,v_3^*)$, kde $v_1^*$ a $v_2^*$ jsou již spočtené a vektor \[v_3^*=v_3-\mu_{31}v_1^*-\mu_{32}v_2^*, \qquad \mu_{31},\mu_{32}\in\mathbb{R} \] získáme odečtením vhodných násobků $v_1^*$ a $v_2^*$ od $v_3$ tak, aby \begin{align*} \langle v_3^*, v_1^*\rangle &=\langle v_3-\mu_{31}v_1^*-\mu_{32}v_2^*, v_1^*\rangle=\langle v_3, v_1^*\rangle -\mu_{31}\langle v_1^*, v_1^*\rangle -\mu_{32}\underbrace{\langle v_2^*, v_1^*\rangle}_{0} = 0,\\ \langle v_3^*, v_2^*\rangle &=\langle v_3-\mu_{31}v_1^*-\mu_{32}v_2^*, v_2^*\rangle=\langle v_3, v_2^*\rangle -\mu_{31}\underbrace{\langle v_1^*, v_2^*\rangle}_{0} -\mu_{32}\langle v_2^*, v_2^*\rangle = 0. \end{align*} Odtud vidíme, že \[ \mu_{31}=\frac{\langle v_3, v_1^*\rangle}{||v_1^*||^2},\qquad \mu_{32}=\frac{\langle v_3, v_2^*\rangle}{||v_2^*||^2}. \] Analogicky postupujeme dále dokud nenalezneme celou bázi $(v_1^*,\ldots,v_n^*)$.

Grammův-Schmidtův algoritmus je dobře známý, ale pozorný čtenář si jistě všiml, že pro mřížky nastává problém. Hodnoty $\mu_{ij}$ totiž nemusí být celočíselné. Vektory $v_i^*$ potom neleží v mřížce generované $(v_1,\ldots,v_n)$ a báze $(v_1^*,\ldots,v_n^*)$ generuje jinou mřížku. V této podobě tedy algoritmus nedává dobré výsledky. Přesto ale tvoří důležitou součást většiny používaných algoritmů a i my se s ním v lehce upravené podobě ještě setkáme.

Příklad 2

Aplikací Grammova-Schmidtova algoritmu na bázi $W$ tvořenou vektory $w_1=(3,2)$ a $w_2=(2,1)$ dostaneme ortogonální bázi $W^*$ tvořenou vektory \[ w_1^* = w_1 = (3,2), \qquad w_2^* = w_2-\frac{\langle w_2, w_1^* \rangle}{||w_1^*||^2}w_1=\left(\frac{2}{13},-\frac{3}{13}\right), \] která ovšem generuje jinou mřížku než soubor $((3,2),(2,1))$. Všimněme si, že determinant mřížky generované vektory $(w_1^*, w_2^*)$ je roven $1$ a je tedy stejný jako determinant původní mřížky. To platí obecně, neboť díky předpisu pro Grammovu-Schmidtovu ortogonalizaci lze nahlédnout, že matice přechodu od ortogonální báze k bázi původní je horní trojúhelníková matice s jednotkami na diagonále. Její determinant je proto roven $1$. Podle vztahu který jsme uváděli v předchozím příspěvku jsou si tudíž rovny i determinanty mřížek. Speciálně pro naše báze $W^*$ a $W$ je matice přechodu rovna \[ \mathbb{}^{W^*}{\mathbb{E}}^W=\left(\begin{matrix} 1 & -\frac{8}{13} \\ 0 & 1 \end{matrix}\right). \] Nejedná se ovšem o unimodulární matici, neboť její složky nejsou celočíselné. Mohli bychom vektor $w_2^* =\left(\frac{2}{13},-\frac{3}{13}\right)$ šikovně znásobit $13$ tak, aby měl celočíselné složky. Snadno pak ověříme, že $z_2^*=13 \cdot w_2^*=(2,-3)$ je ortogonální na vektor $w_1^*=(3,2)$. Mřížka generovaná vektory $w_1^*$ a $z_2^*$ ale opět není stejná jako mřížka původní, což lze dokázat například výpočtem jejího determinantu, který je roven $13$.

Pro danou mřížku nemusí ortogonální báze vůbec existovat. Lze v takovém případě vůbec nějak zjistit jestli je nějaká báze "lepší" než jiná? Odpověď lze nalézt díky tvrzení které říká, že pro libovolnou mřížku $L$ generovanou vektory $(v_1,\ldots,v_n)$ platí \[ \det(L) \leq ||v_1||\cdot ||v_2||\cdots ||v_n||. \] Předchozí nerovnost se nazývá Hadamardova. Rovnost přitom nastává právě tehdy, když je báze tvořená vektory $v_i$ ortogonální. Tehdy je součin na pravé straně minimální. Můžeme proto zavést důležitou veličinu, pomocí níž lze ohodnotit míru ortogonality dané báze.

Buď $L$ mřížka generovaná bází $\mathcal{B}=(v_1,\ldots,v_n)$. Hadamardovým poměrem báze $\mathcal{B}$ nazveme hodnotu \[ \mathcal{H}(\mathcal{B})=\left(\frac{\det(L)}{||v_1||\cdots ||v_n||}\right)^{\frac{1}{n}}. \]

Z definice determinantu mřížky a Hadamardovy nerovnosti vidíme, že pro libovolnou bázi $\mathcal{B}$ mřížky $L$ platí \[ 0< \mathcal{H}(\mathcal{B})\leq 1. \] Čím více se přitom hodnota $\mathcal{H}(\mathcal{B})$ blíží $1$, tím blíže je příslušná báze bázi ortogonální a tím lepší také budou naše výsledky při řešení SVP a CVP jednoduchými metodami popsanými výše. Dříve jsme ukázali, že $\det(L)$ nezávisí na volbě báze. $\mathcal{H}(\mathcal{B})$ je proto maximální tehdy, když součin délek bazických vektorů je minimální.

Příklad 3

Pro báze $\mathcal{B}_1=((1,0),(0,1))$ a $\mathcal{B}_2=((3,2),(2,1))$ jsou hodnoty Hadamardových poměrů následující: \[ \mathcal{H}(\mathcal{B}_1)= 1, \qquad \mathcal{H}(\mathcal{B}_2)\approx 0.352. \]

Když už umíme posoudit "kvalitu" dané báze, je na čase podívat se na způsob, jak pro danou mřížku najít bázi s co možná nejvyšším Hadamardovým poměrem. Procesu hledání takové báze se říká redukce mřížky (resp. redukce báze) a patřičné algoritmy se nazývají redukční. Nejpoužívanějším redukčním algoritmem je slavný LLL (Lenstra, Lenstra, Lovász) algoritmus a jeho varianty, které umožňují pro danou bázi mřížky nalézt takzvanou LLL-redukovanou bázi. Algoritmus lze použít pro mřížky libovolných dimenzí. Pro vysoké hodnoty dimenze mřížky se jedná o jediný prakticky proveditelný způsob hledání vhodné báze, pomocí které lze nalézt alespoň přibližná řešení SVP a CVP. Ani s pomocí tohoto algoritmu ale nemusíme získat správný výsledek.

Popis a analýza LLL algoritmu je nad rámec tohoto příspěvku. Pro ilustraci základní myšlenky stojící v pozadí LLL algoritmu se nyní omezíme na nejjednodušší případ redukce mřížky o dimenzi $n=2$ generované bází $(v_1, v_2)$. Inspirováni Grammovým-Schmidtovým algoritmem představíme Lagrangeův-Gaussův redukční algoritmus:

1. pro dané $v_1$ a $v_2$ spočti nové $v_2$ jako \[ v_2:=v_2 - \lfloor\mu\rceil v_1, \quad \text{kde } \mu=\frac{\langle v_1, v_2\rangle}{||v_1||^2}, \]

2. dokud platí, že $||v_2||<||v_1||$ prováděj následující smyčku:

   i) zaměň $v_1 \leftrightarrow v_2$,

   ii) spočti nové $v_2$ jako \[ v_2:=v_2 - \lfloor\mu\rceil v_1, \quad \text{kde } \mu=\frac{\langle v_1, v_2\rangle}{||v_1||^2}, \]

3. vrať výsledné $v_1$ a $v_2$.

Při provádění algoritmu tedy střídavě odčítáme násobky jednoho vektoru od druhého tak dlouho, dokud je možné vytvářet kratší vektory. Vidíme, že díky celočíselnému zaokrouhlování $\lfloor\mu\rceil$ napočítané vektory vždy leží v mřížce. Výsledná redukovaná báze sestává z uspořádané dvojice vektorů $(v_1, v_2)$ a lze dokázat, že pro libovolný vektor $v\in L$ platí $||v_1||\leq ||v||$, tedy že $v_1$ je řešením SVP. Velikosti redukovaných vektorů jsou přitom menší nebo rovny velikostem vektorů původní báze, takže nová báze má příznivější Hadamardův poměr. Výše popsané řešení CVP bude proto dávat lepší výsledky. Měli bychom ale zdůraznit, že toto platí jen pro dimenzi $n=2$. Modifikace algoritmu (např. LLL) pro vyšší dimenze již nemusí dávat "nejlepší" bázi obsahující nejkratší vektor. Navíc, podobně jako u Grammova-Schmidtova algoritmu, výsledná redukovaná báze a její Hadamardův poměr závisí na pořadí vektorů báze použité na vstupu algoritmu. Přesto je redukce báze nejlepším známým způsobem řešení obtížných mřížkových problémů.

Příklad 4

Použitím Lagrangeova-Gaussova redukčního algoritmu na bázi tvořenou vektory $w_1=(3,2)$ a $w_2=(2,1)$ z předchozích příkladů dostaneme postupně vektory uvedené v následující tabulce. \[ \begin{array}{| c | c | c | c|}\hline v_1 & v_2 & \lfloor\mu\rceil & v_2 - \lfloor\mu\rceil v_1\\ \hline (3,2) & (2,1) & 1 & (-1,-1)\\ (-1,-1) & (3,2) & -2 & (1,0)\\ (1,0) & (-1,-1) & -1 & (0,-1)\\ \hline (1,0) & (0,-1) & & \\ \hline \end{array} \] Výsledná redukovaná báze je tvořena vektory $((1,0), (0,-1))$, je ortogonální a $(1,0)$ je řešením SVP. Graficky můžeme redukci báze znázornit na obrázku 3, kde postupně zobrazujeme vektory vstupní báze (červeně), částečně redukované vektory (modře) a výslednou redukovanou bázi (zeleně).

Útok na GGH

Pojďme nyní demonstrovat sílu redukčního algoritmu na příkladu šifrovacího systému GGH v mřížce dimenze $n=2$. Parametry systému volíme stejně jako v neřešeném příkladu uvedeném v [1].

Příklad 5

Alice používá jako soukromý klíč bázi $\mathcal{B}_{good}=(v_1,v_2)$, kde \[ v_1=(4,13),\qquad v_2=(-57,-45). \] Veřejný klíč je dán bází $\mathcal{B}_{bad}=(w_1,w_2)$, kde \[ w_1=(25453,9091),\qquad w_2=(-16096,-5749). \] Pro obě báze můžeme spočíst Hadamardův poměr \[ \mathcal{H}(\mathcal{B}_{good})\approx 0.7536 , \qquad \mathcal{H}(\mathcal{B}_{bad})\approx 0.0011. \] Báze soukromého klíče má vysoký Hadamardův poměr, což je potřeba k tomu, aby při dešifrování Alice dostala původní zprávu. Hadamardův poměr veřejné báze je naopak velmi nízký.

Předpokládejme, že Bob posílá Alici zprávu, jejíž otevřený text lze zapsat jako vektor $m=(8,3)$. Pro šifrování náhodně zvolil vektor $r=(4,2)$ a Alici poslal šifrovou zprávu \[ e= m_1 \cdot w_1 + m_2 \cdot w_2 + r = (155340, 55483). \] V předchozím článku jsme předvedli, jak může Alice zprávu dešifrovat díky znalosti soukromého klíče. Také jsme viděli, že dešifrování pomocí veřejného klíče nedává správný výsledek, neboť, jak teď již víme, $\mathcal{B}_{bad}$ má velmi malý Hadamardův poměr.

Nepřítel znalý Lagrangeova-Gaussova algoritmu se ale může pokusit najít v mřížce generované $\mathcal{B}_{bad}$ bázi s vyšším Hadamardovým poměrem. Použitím redukčního algoritmu na bázi $(w_1, w_2)$ velmi rychle získá bázi $\mathcal{B}_{bad}^{red}$ tvořenou vektory \[ w_1^{red}=(4,13),\qquad w_2^{red}=(41,-7), \] jejíž Hadamardův poměr je \[ \mathcal{H}(\mathcal{B}_{bad}^{red})\approx 0.9958. \] Pro útočníka je pak jednoduché vyjádřit zachycenou zprávu $e$ jako \[ e=(155340, 55483)= \frac{305653}{51} \cdot w_1^{red} +\frac{163408}{51} \cdot w_2^{red}, \] zaokrouhlit koeficienty v lineární kombinaci a spočíst \[ f= 5993 \cdot w_1^{red} + 3204 \cdot w_2^{red}=(155336, 55481). \] To je pro $e$ nejbližší vektor mřížky, neboť \[ ||e-f||=||r|| \approx 4.47. \] Vyjádřením $f$ jako \[ f= 8 \cdot w_1 +3 \cdot w_2 \] útočník zjistí, že nezašifrovaná zpráva zní $m=(8,3)$. Díky redukci báze bylo možné systém prolomit a dešifrovat zprávu aniž by bylo potřeba znát Alicin soukromý klíč. Pro ilustraci ještě dodejme, že bázi $\mathcal{B}_{good}$ tvořící soukromý klíč lze redukovat na bázi tvořenou vektory \[ v_1^{red}=(4,13),\qquad v_2^{red}=(-41,7), \] jejíž Hadamardův poměr je také přibližně $0.9958$.

Viděli jsme, že šifrovací schéma GGH není v dimenzi 2 bezpečné. Vzhledem k efektivitě redukčních algoritmů se ukazuje, že pro kryptografické účely je z bezpečnostních důvodů nutné pracovat s mřížkami v podstatně vyšší dimenzi ($n=300$ a vyšší), kdy je i redukce prostřednictvím LLL algoritmu výpočetně velmi náročná. I v tak vysoké dimenzi jsou mřížkové šifrovací algoritmy stále dostatečně rychlé. GGH už ale naráží na problém nutnosti přenosu a uskladnění velkého množství dat, neboť je potřeba distribuovat a uchovávat všechny složky vektorů báze ve veřejném klíči. Praktičtějším schématem je systém NTRU, kterému se ale budeme věnovat zase jindy.

1. Hoffstein J., Pipher J., Silverman J. H., An Introduction to Mathematical Cryptography, Springer, 2008

---

Tento článek byl vznikl v rámci řešení projektu Institucionální podpora Českého vysokého učení technického v Praze (CZ.02.2.69/0.0/0.0/16_015/0002382).

---