Základy mřížkové kryptografie

Kryptografie veřejného klíče

Většina z nás je zvyklá běžně komunikovat prostřednictvím sítě internet. Pro navázání bezpečného, tedy šifrovaného, spojení přes jinak nezabezpečený kanál je však nezbytné použití nástrojů asymetrické kryptografie. Asymetrická kryptografie, označovaná též jako kryptografie veřejného klíče, nepožaduje, aby si komunikující strany před navázáním spojení vyměnily šifrovací klíč. Zprávy jsou zašifrovány prostřednictvím veřejného klíče příjemce, který je dešifruje prostřednictvím svého soukromého klíče. Aby byl systém prakticky použitelný, je nutné, aby při znalosti příslušného klíče umožňoval snadno šifrovat či dešifrovat. Na druhou stranu, aby systém poskytoval dostatečnou bezpečnost, musí zaručit, že při neznalosti soukromého klíče bude velmi obtížné zprávu dešifrovat. Konkrétně útočník nesmí být schopen z veřejného klíče odvodit klíč soukromý.

Přestože asymetrická kryptografie poskytuje celou řadu schémat ustanovení zabezpečené komunikace, bezpečnost prakticky všech stávajících implementací se opírá o jeden ze dvou matematických problémů.

• problém faktorizace složeného čísla $n$, kdy při vhodně zvolených parametrech je těžké spočíst prvočísla $p$ a $q$ taková, že $p q = n$ (algoritmus RSA)

• problém diskrétního logaritmu, kdy při vhodně zvolených parametrech je pro daná $A, g \in \mathbb{N}$ a prvočíslo $p$ těžké spočíst $a$ takové, že $g^a \equiv A \pmod p$ (Diffieho-Hellmanova výměna klíčů)

Celá řada brilantních matematiků se neúspěšně zabývala hledáním algoritmů, které by umožnily tyto problémy efektivně řešit. Je proto pochopitelné, že Peter Shor způsobil v roce 1994 přímo senzaci když představil algoritmus, který oba problémy řeší s využitím kvantového počítače. Shorův algoritmus umožňuje z veřejného klíče spočíst klíč soukromý a tím zcela narušit bezpečnost šifrovacího systému, a to nezávisle na jeho implementaci.

Kvantové počítače v té podobě která by byla potřeba pro implementaci Shorova algoritmu nejsou momentálně k dispozici, ale na jejich vývoji intenzivně pracují vědci po celém světě. Není proto překvapivé, že kryptografové hledají šifrovací systémy, jejichž bezpečnost by byla založena na jiných obtížně řešitelných problémech, takových, pro něž není znám ani klasický ani kvantový algoritmus umožňující snadné nalezení řešení. Slibné kandidáty poskytuje zkoumání mřížek. V tomto článku se seznámíme s těmito objekty, představíme si s nimi spojené obtížně řešitelné úlohy a některé metody jejich řešení. Čtenář znalý lineární algebry zde najde celou řadu známých pojmů a postupů, které ovšem pro naše potřeby poněkud upravíme.

Mřížka

Seznámíme se nyní se základními pojmy. Začneme samotnou definicí mřížky. Neuvádíme ji zde v plné obecnosti, pro naše potřeby ale postačí, neboť obecnější případy lze vždy převést na ten náš.

Mějme soubor lineárně nezávislých vektorů $(v_1,\ldots,v_n)$, kde $v_i\in\mathbb{R}^n$ pro všechna $i\in\{1,\ldots, n\}$. Množinu $L$ 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\} \] nazveme mřížkou generovanou vektory $v_1,\ldots,v_n$.

Číslo $n$ nazýváme dimenzí mřížky $L$. Bází mřížky $L$ rozumíme libovolný lineárně nezávislý soubor vektorů generující $L$ ve smyslu předchozí definice, tedy pomocí celočíselné lineární kombinace. Z praktických důvodů bývá zvykem volit i složky vektorů celočíselné, neboť pak lze všechny výpočty na počítači provádět v přesné aritmetice racionálních čísel. Vyhneme se tak zaokrouhlovacím chybám vznikajícím při manipulaci s čísly reprezentovanými ve formátu float.

Všimněme si, že pokud bychom v předchozí definici připustili aby $a_i$ byly reálné koeficienty, dostali bychom přesně objekty známé z lineární algebry. $L$ by byl celý prostor $\mathbb{R}^n$, který bychom vnímali jako lineární obal souboru vektorů $(v_1,\ldots,v_n)$, $n$ by značilo dimenzi tohoto vektorového prostoru a vektory $v_i,\ i\in\{1,\ldots, n\}$ by tvořily jeho bázi. Pro $a_i\in\mathbb{Z}$ bude $L$ diskrétní množina o nekonečně mnoha prvcích.

Příklad 1

Uvažujeme-li vektory jako body prostoru $\mathbb{R}^2$, můžeme na obrázku 1 znázornit část mřížky generované vektory $v_1=(1,0)$ a $v_2=(0,1)$.

Z lineární algebry jsme zvyklí při výpočtech pracovat v nějaké bázi. Víme ovšem, že i když šikovná volba báze může výpočet usnadnit, konkrétní volba nebývá zásadní. Při řešení problémů spojených s mřížkami ovšem na volbě báze velmi záleží. Podívejme se tedy nejprve na vztah mezi bázemi jedné mřížky.

Máme-li k dispozici dva lineárně nezávislé soubory vektorů $(v_1,\ldots,v_n)$ a $(w_1,\ldots,w_n)$ generující stejnou mřížku $L$, musí platit, že vektory $w_i$ lze vyjádřit pomocí celočíselné lineární kombinace vektorů $v_i$. Je-li $\mathbb{A}$ matice koeficientů $a_{ij}\in\mathbb{Z},\ i,j\in\{1,\ldots,n\}$ pro které platí \begin{equation}\label{matice} \begin{matrix} a_{11}v_1 & + & \cdots & + & a_{1n}v_n & = & w_1, \\ \vdots & & \ddots & & \vdots & & \vdots \\ a_{n1}v_1 & + & \cdots & + & a_{nn}v_n & = & w_n, \end{matrix} \end{equation} pak vektory $v_i$ lze vyjádřit pomocí $w_i$ a koeficientů inverzní matice $\mathbb{A}^{-1}$. $w_i$ jsou ale vektory báze $L$ a $v_i\in L$, takže koeficienty $\mathbb{A}^{-1}$ jsou celočíselné. Z vlastností determinantu víme, že $\det(\mathbb{A})\cdot \det(\mathbb{A}^{-1})=1$, což v kombinaci s poznatkem že $\det(\mathbb{A}), \det(\mathbb{A}^{-1})\in \mathbb{Z}$ omezuje $\mathbb{A}$ na unimodulární matice, tedy matice s celočíselnými koeficienty jejichž determinant je roven $\pm 1$. Množinu takových $n\times n$ matic bývá zvykem značit $GL_n(\mathbb{Z})$. Libovolné dvě báze stejné mřížky jsou tedy ve vztahu \eqref{matice}, kde $a_{ij}$ jsou koeficienty matice $\mathbb{A}\in GL_n(\mathbb{Z})$. Lze dokázat i tvrzení které říká, že je-li $\mathbb{A}\in GL_n(\mathbb{Z})$, pak lineárně nezávislé soubory $(v_1,\ldots,v_n)$ a $(w_1,\ldots,w_n)$ splňující \eqref{matice} generují stejnou mřížku $L$. Poznamenejme ještě, že v terminologii základního kurzu lineární algebry je matice $\mathbb{A}$ transponovanou maticí přechodu od báze $W=(w_1,\ldots,w_n)$ do báze $V=(v_1,\ldots,v_n)$, tedy \[ \mathbb{A}=\left({}^W\mathbb{E}^V\right)^T. \]

Příklad 2

Mřížku zmíněnou v příkladu 1 lze generovat i pomocí báze tvořené vektory $w_1=(3,2)$ a $w_2=(2,1)$. Změnu báze realizují matice \[ \mathbb{A}=\left(\begin{matrix} 3 & 2 \\ 2 & 1 \end{matrix}\right), \qquad \mathbb{A}^{-1}=\left(\begin{matrix} -1 & 2 \\ 2 & -3 \end{matrix}\right), \] jejichž determinant je roven $-1$. Několik bodů mřížky je znázorněno na obrázku 2.

Důležitou veličinou spjatou s danou mřížkou je její determinant. Buď $L$ mřížka generovaná bází $(v_1,\ldots,v_n)$. Označme $\mathbf{B}_v$ matici o rozměrech $n\times n$, jejíž $i$-tý řádek je tvořen složkami vektoru $v_i$. Hodnotu $|\det(\mathbf{B}_v)|$ nazveme determinantem mřížky $L$ a budeme jej značit $\det(L)$.

Význam determinantu mřížky tkví především v tom, že jeho hodnota nezávisí na volbě báze dané mřížky. Díky \eqref{matice} lze totiž snadno najít vztah mezi maticí $\mathbf{B}_w$ odpovídající bázi tvořené vektory $w_i$ a maticí $\mathbf{B}_v$ odpovídající bázi tvořené vektory $v_i$. Platí, že \[ \mathbf{B}_w = \mathbb{A}\cdot \mathbf{B}_v. \] Z předchozí diskuze ale víme, že $\det(\mathbb{A})=\pm 1$, a proto \[ |\det(\mathbf{B}_w)|=|\det(\mathbb{A}\cdot \mathbf{B}_v)|=|\det(\mathbb{A})|\cdot|\det(\mathbf{B}_v)|=|\det(\mathbf{B}_v)|. \]

Problémy nejkratšího a nejbližšího vektoru

Prostor $\mathbb{R}^n$ lze přirozeně vybavit standardním skalárním součinem $\langle ., . \rangle$, definovaným pro libovolné dva vektory $x=(x_1,\ldots,x_n)$ a $y=(y_1,\ldots,y_n)$ jako \[ \langle x, y \rangle = \sum_{i=1}^n x_i y_i, \] a také Euklidovou normou $||.||$, která udává velikost vektoru a je definovaná jako \[ || x || = \sqrt{\langle x, x \rangle} = \sqrt{\sum_{i=1}^n x_i^2}. \] Nyní můžeme představit dva důležité problémy na jejichž (ne)řešitelnosti je založena bezpečnost několika šifrovacích systémů.

• Mějme mřížku $L$ zadanou pomocí báze $(v_1,\ldots,v_n)$. Problém hledání nenulového vektoru $v\in L$ minimální velikosti $||v||$ nazýváme problémem nejkratšího vektoru (shortest vector problem – SVP).

• Mějme mřížku $L$ zadanou pomocí báze $(v_1,\ldots,v_n)$ a vektor $w\in\mathbb{R}^n$. Problém hledání vektoru $v\in L$ jehož vzdálenost $||w-v||$ od $w$ je minimální nazýváme problémem nejbližšího vektoru (closest vector problem – CVP).

O obou těchto problémech je známo, že pro velké hodnoty dimenze $n$ jsou v obecném případě obtížně řešitelné (dokonce jsou NP-těžké). Jelikož s každým vektorem $v$ obsahuje mřížka i vektor $-v$ o stejné velikosti, není řešení SVP jednoznačné. Stejně tak nemusí být jednoznačné ani řešení CVP.

Příklad 3

Vezmeme-li si mřížku generovanou vektory $v_1=(1,0)$ a $v_2=(0,1)$, snadno zjistíme, že nejkratšími vektory $L$ jsou $\pm v_1$ a $\pm v_2$, které mají shodně velikost $1$. Za řešení SVP lze tedy brát jeden z vektorů báze. Je-li ovšem tatáž mřížka zadána pomocí báze tvořené vektory $w_1=(3,2)$ a $w_2=(2,1)$, pak bez obrázku 2 budeme nejkratší vektory těžko hledat. Na obrázku 3 vidíme, jak bychom si vedli, kdybychom postupně zkoušeli lineární kombinace ve tvaru \[ a_1 \cdot w_1 + a_2 \cdot w_2 \] pro různé hodnoty koeficientů $a_1 \in \{-2,-1,0,1,2\},\ a_2 \in \{-1,0,1\}$. Nejkratším vektorem, který takto dostaneme, je $(1,1)$, což ale není řešení SVP.

Zvolme nyní vektor $w=(0.8, 1.2)$ znázorněný na obrázku 4. Vektorem ležícím v mřížce nejblíže $w$ je zřejmě $(1,1)$. Báze tvořená $v_1$ a $v_2$ je i bází $\mathbb{R}^2$ a $w$ lze vyjádřit jako \[ w=0.8\cdot v_1 + 1.2\cdot v_2. \] Zaokrouhlením koeficientů $a_1=0.8$ a $a_2=1.2$ v lineární kombinaci na celá čísla získáme vektor \[ v=1\cdot v_1 + 1\cdot v_2=(1,1) \] představující pro $w$ řešení CVP. Pokusíme-li se stejnou proceduru zopakovat s bází zadanou vektory $w_1$ a $w_2$, dostaneme \[ w=1.6\cdot v_1 -2\cdot v_2. \] Po zaokrouhlení prvního koeficientu ovšem vektor \[ v'=2\cdot w_1 -2\cdot w_2=(2,2) \] není pro $w$ nejbližším vektorem mřížky.

V předchozím příkladu jsme viděli, že řešení problému nejkratšího či nejbližšího vektoru je v některých bázích velmi jednoduché, zatímco pro jiné může být obtížné. Podívejme se nyní, jak lze navrhnout konkrétní šifrovací schéma založené na mřížkách.

Šifrovací systém GGH

Šifrovací systém GGH (Goldreich, Goldwasser, Halevi) je asi nejjednodušším mřížkovým šifrovacím systémem, neboť přímo využívá koncepty představené výše. Základními kameny systému jsou dvě vhodně zvolené báze téže mřížky $L$, které označíme jako $\mathcal{B}_{good}=(v_1,\ldots,v_n)$ a $\mathcal{B}_{bad}=(w_1,\ldots,w_n)$. Báze $\mathcal{B}_{good}$ slouží jako soukromý klíč, zatímco $\mathcal{B}_{bad}$ slouží jako veřejný klíč. Před začátkem komunikace musí Alice zvolit $\mathcal{B}_{good}$ a unimodulární matici $\mathbb{A}$. Pomocí $\mathbb{A}$ a $\mathcal{B}_{good}$ spočte $\mathcal{B}_{bad}$ díky \eqref{matice}. $\mathcal{B}_{bad}$ potom Alice zveřejní. Chce-li Bob poslat Alici šifrovanou zprávu, musí otevřený text vyjádřit ve tvaru vektoru $m=(m_1,\ldots,m_n)\in\mathbb{Z}^n$, náhodně zvolit vektor $r$ o malé velikosti $||r||$ a spočíst šifrový text jako vektor \[ e=\sum_{i=1}^n m_i w_i +r. \] Takto spočtené $e$ Bob pošle Alici. Vhodné volby $r$ jsou takové, kdy $e$ neleží v mřížce, ale leží blízko jistého bodu mřížky. Alice zprávu dešifruje tak, že vektor $e$ vyjádří ve své bázi $\mathcal{B}_{good}$, která by měla být zvolena tak, aby v ní bylo možno snadno najít řešení CVP pro vektor $e$. Řešením CVP v této "dobré" bázi Alice získá $f\in L$ jako vektor mřížky nejbližší vektoru $e$ a vyřeší soustavu rovnic \[ n_1\cdot w_1 + n_2\cdot w_2 + \ldots + n_n \cdot w_n = f \] pro neznámé $n_1,\ldots,n_n$. Tato $n_1,\ldots,n_n$ jsou ale složky Bobovy zprávy $m$, neboť $f=e-r=\sum_{i=1}^n m_i w_i$.

Příklad 4

Šifrovací schéma GGH můžeme předvést na následujícím příkladu, kde zadání přebíráme z neřešených úloh uvedených v knize [1]. Alice se rozhodla používat soukromý klíč představovaný bází \[ v_1=(4,13),\qquad v_2=(-57,-45) \] a veřejný klíč představovaný bází \[ w_1=(25453,9091),\qquad w_2=(-16096,-5749). \] Jedná se skutečně o báze generující stejnou mřížku, neboť pro $\mathbb{A}$ v rovnici \eqref{matice} platí \[ \mathbb{A}=\left( \begin{array}{cc} -1118 & -525 \\ 707 & 332 \\ \end{array} \right),\qquad \det(\mathbb{A})=-1. \] Determinant mřížky $L$ je v tomto případě roven \[ \det(L)= 561, \] zjevně se tedy nejedná o mřížku se kterou jsme pracovali dříve.

Alice obdržela od Boba šifrovanou zprávu $e=(155340, 55483)$. Aby zprávu dešifrovala, vyjádří vektor $e$ ve tvaru lineární kombinace vektorů báze $\mathcal{B}_{good}$ jako \[ e=(155340, 55483)= -\frac{115993}{17} \cdot v_1 -\frac{163408}{51} \cdot v_2 \] a zaokrouhlením koeficientů získá \[ f= -6823 \cdot v_1 -3204 \cdot v_2=(155336, 55481). \] Vzdálenost $||e-f||$ takto nalezeného vektoru $f\in L$ od $e$ je rovna \[ ||e-f||=||r|| \approx 4.47 \] a můžeme si být vcelku jisti, že se jedná o řešení CVP. Vektor $f$ lze dále vyjádřit jako \[ f= 8 \cdot w_1 +3 \cdot w_2, \] takže nezašifrovaná zpráva zní $m=(8,3)$.

Pokud šifrovanou zprávu $e=(155340, 55483)$ zachytí nepřítel a rozhodne se řešit CVP v bázi $\mathcal{B}_{bad}$ tvořené veřejným klíčem, dostane \[ e=(155340, 55483)= -\frac{428}{51} \cdot w_1 -\frac{1169}{51} \cdot w_2, \] což po zaokrouhlení koeficientů dá \[ f'= -8 \cdot w_1 -23 \cdot w_2=(166584, 59499). \] Vzdálenost $||e-f'||$ vektoru $f'\in L$ od $e$ je ale dost velká, přesněji je rovna \[ ||e-f'||\approx 11939.7, \] takže znalost $f'$ útočníkovi k ničemu nebude. Takto dešifrovaná zpráva zní $(-8,-23)$ a s původní zprávou nemá nic společného.

V předchozím textu jsme záměrně vynechali diskusi důležitých aspektů systému GGH. Například jsme zatajili jak vhodně volit "dobré" a "špatné" báze. Mohlo by se zdát, že při vhodné volbě parametrů bude systém vybudovaný na mřížce dimenze $2$ bezpečný. Ve skutečnosti tomu tak vůbec není. Jak volit $\mathcal{B}_{good}$ a $\mathcal{B}_{bad}$? Jak systém napadnout a jak lze díky mřížkám zkonstruovat prakticky použitelný šifrovací systém? Na tyto otázky odpovíme v pokračování tohoto článku nazvaném Kryptografie na mřížce a ortogonalizace, kde si také představíme základní metody řešení mřížkových problémů.

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).

---