GGH titkosítási rendszer

A GGH titkosítási séma ( Eng. Goldreich–Goldwasser–Halevi ) egy rácsokon alapuló aszimmetrikus kriptográfiai rendszer . Van egy GGH aláírási séma is .

A titkosítási rendszer a legrövidebb vektor megtalálásának és a legközelebbi vektor megtalálásának problémájának megoldásán alapul . Az Oded Goldreich , Shafi Goldwasser és Shai Halevi tudósok által 1997-ben közzétett GGH titkosítási séma egyirányú titkos belépési függvényt használ , mivel bármilyen rácsalapon könnyen létrehozható egy rácsponthoz közeli vektor. Például egy rácspont felvétele és egy kis hibavektor hozzáadása. A hibavektorból a rács kezdőpontjába való visszatéréshez speciális alapra van szükség. 1999-ben Phong Q. Nguyen [1] finomította az eredeti GGH-titkosítási sémát, ami lehetővé tette az öt GGH-probléma közül négy megoldását és az utóbbiról részleges információk megszerzését. Míg a GGH bizonyos paraméterek megválasztásával biztonságos lehet, a hagyományos nyilvános kulcsú kriptorendszerekkel szembeni hatékonysága továbbra is vitatható [2] . A titkosításhoz gyakran nagy rácsdimenzióra van szükség, miközben a kulcs mérete megközelítőleg négyzetesen növekszik a rácsmérethez képest [2] .

Az egyetlen rácsséma, amely képes kezelni a nagy dimenziókat, az NTRU [3] .

Algoritmus

A GGH tartalmaz egy nyilvános kulcsot és egy privát kulcsot [4] . A privát kulcs az unimoduláris mátrixú rács alapja . $B$ $L$ $U$

A nyilvános kulcs egy másik alapja az űrlap rácsának . $L$ $B'=UB$

Álljon az M üzenettér az intervallumhoz tartozó vektorokból . $(m_{1},...,m_{n})$ $-M<m_{i}<M$

Titkosítás

Üzenet , hiba és nyilvános kulcs adott : $m=(m_{1},...,m_{n})$ $e$ $B'$

v=\sum m_{i}b_{i}'

Mátrix jelöléssel:

v=m\cdot B'

Emlékeztetni kell arra, hogy egész értékekből áll, egy rácspont, és ezért egyben rácspont is. Ekkor a titkosított szöveg: $m$ $b'$ $v$

c=v+e=m\cdot B'+e

Átirat

A rejtjelezett szöveg visszafejtéséhez a következőket kell kiszámítani:

c\cdot B^{-1}=(m\cdot B^{\prime }+e)B^{-1}=m\cdot U\cdot B\cdot B^{-1}+e\cdot B ^{-1}=m\cdot U+e\cdot B^{-1}

Az eltávolításhoz , ha elég kicsi, a Babai -féle kerekítési módszert [5] használjuk . $e\cdot B^{-1}$

Ezután a szöveghez:

m=m\cdot U\cdot U^{-1}

Biztonsági elemzés

Ez a rész a kriptorendszerek támadásának számos módját tárgyalja [6] .

Támadás kerekítéssel

A kerekítő támadás ennek a kriptográfiai rendszernek a legszembetűnőbb támadása, kivéve a brute force támadást - hibavektor keresését, melynek lényege, hogy a B nyilvános kulcs segítségével ugyanúgy invertálja a függvényt, mint az R privát kulcs használatakor. Mégpedig ismeretében ki tudja számolni . Így találhat egy vektort . 80 LLL alatti dimenzióknál az algoritmus képes helyesen meghatározni a bázist, azonban a 100-as és nagyobb méretektől kezdve ez a támadás rosszabb, mint a hibavektor triviális felsorolása. $e.$ $c=B\cdot v+e$ $B^{-1}\cdot c=v+B^{-1}\cdot e$ $d=B^{-1}\cdot e$

Vihartámadás

Ez az algoritmus a kerekítési támadás nyilvánvaló finomítása. Itt a legjobb közelítési algoritmust használjuk a legrövidebb vektorproblémára. A Babai kerekítési algoritmus helyett a legközelebbi sík algoritmusát használják. Ez így működik. Adott egy pont és redukált bázis c = { } LLL -re . Minden affin szóköz = { + } : } figyelembe vehető. Mindenesetre létezik a ponthoz legközelebb eső hipersík . Továbbá egy pontot vetítünk az (n - 1)-dimenziós térre, amelyet = { } fed le . Ez egy új pontot és egy új bázist ad = { }. Az algoritmus most rekurzív módon halad , hogy megtaláljon egy pontot ebben az (n - 1) dimenziós rácsban a -hoz közel . Végül az algoritmus beállítja . Ez a módszer sokkal gyorsabban működik, mint az előző. A rácsdimenzióval azonban a munkaterhelése is exponenciálisan növekszik. A kísérletek azt mutatják, hogy ha LLL -t használunk rácsredukciós algoritmusként, némi keresési időre van szükség, 110-120 mérettől kezdve. A támadás 140-150 mérettől kezdődően kivitelezhetetlenné válik. $c$ $B$ ${b_{1}},\dots {b_{n}}$ ${H_{k))$ $k\cdot {b_{n))$ $\sum _{i=0}^{n-1}{a_{i}}\cdot {b_{i}}$ ${a_{i}}\in {\mathcal {R}}$ $k\in {\mathcal {Z))$ ${H_{k))$ $c$ $B$ ${b_{1}},\dots {b_{n}}$ $ck\cdot {b_{n))$ $c'$ $B'$ ${b_{1}},\dots {b_{n}}$ $p'$ $c'$ $p=p'+k\cdot {b_{n))$

Injekciós támadás

Egy másik módszer, amelyet gyakran használnak a legközelebbi vektor megtalálásának problémájának közelítésére , az n bázisvektor beágyazása és egy olyan pont beágyazása , amelyhez közeli rácspontot kell találni egy (n + 1) dimenziós rácsban. $c$

$B'={\begin{pmatrix}\vdots &\vdots &\vdots &\cdots &\vdots \\c&b_{1}&b_{2}&\cdots &b_{n}\\\vdots &\vdots &\vpontok &\dpontok &\vpontok \\1&0&0&\cdots &0\end{pmatrix}}$

A rácsredukciós algoritmust ezután arra használjuk, hogy megtaláljuk a legrövidebb nem nulla vektort abban a reményben, hogy ennek a vektornak az első n eleme lesz a legközelebbi pont ehhez . Az ezzel a támadással végzett kísérletek (az LLL -t használva a legrövidebb vektorok megtalálására) azt mutatják, hogy 110-120 körüli dimenzióig működik, ami jobb, mint a kerekítő támadás, ami rosszabb, mint a 100-as dimenzió utáni triviális keresés. $L(B')$ $c$

A támadások hatékonyságának becslése [7]

Becsült támadás kerekítéssel

Minden dimenzióban hozzunk létre öt zárt bázist. Minden bázist = + rand - nak választunk , ahol I az azonosságmátrix , a rand pedig egy négyzetmátrix , amelynek tagjait a tartományból egyenletesen választjuk ki . Minden bázishoz az = értéket számítjuk ki , ahol a legnagyobb sor euklideszi normája , és . Minden zárt bázishoz öt nyitott bázis jön létre $n$ ${R_{i))$ $4\left|{\sqrt {n}}\right|\cdot I$ $(\pm 4)$ $(\pm 4)$ ${-4,...,4}$ ${R_{i))$ ${\sigma _{i))$ ${\displaystyle ({\gamma _{i)){\sqrt {8\ln({2n}/{\varepszilon }))))^{-1))$ ${\gamma _{i))$ ${R_{i}}^{-1}$ $\varepsilon =10^{-5}$ ${R_{i))$ ${B_{ij))$

${work-load_{ij))$ = , ahol a kettős ortogonalitási hiba: ahol a mátrix sorát jelöli . ${\displaystyle ({\pi }e)^{n/2))$ $\cdot {\sigma _{i}^{n))$ $\cdot {\frac {orth-defect^{*}({B_{ij)))}{det|{B_{ij}}|}}$ $orth-defect^{*}$ $orth-defect^{*}(B)=|det(B)|\cdot \prod _{i}\|{\hat {b_{i))}\|,$ ${\displaystyle {\kalap {b_{i))))$ $B^{{-1}}$

Assault score

A támadás értékeléséhez ugyanazokat a nyitott és zárt bázisokat használtuk, mint a kerekítéssel történő támadásnál.

Injekciós támadás értékelése

Mivel az injekciós támadás „munkaterheléséről” nem beszélhetünk, megmértük azt a maximális értéket (a hibavektorral kapcsolatban), amelyre ez a támadás működik. Ezekhez a kísérletekhez ugyanazokat a zárt és nyitott bázisokat használtuk, mint az előző két támadásnál. Ezután minden nyitott alapot felhasználtunk a funkció több ponton történő értékelésére, több különböző érték használatával , és ellenőriztük, hogy az injekciós támadás helyreállítja-e a titkosított üzenetet. ${\sigma}$ ${R}$ ${B_{ij))$ $\sigma$

Példa

Legyen a rács bázissal és annak reciproka : $L\subset \mathbb {R} ^{2}$ $B$ $B^{{-1}}$

B={\begin{pmatrix}7&0\\0&3\\\end{pmatrix}}

és

B^{-1}={\begin{pmatrix}{\frac {1}{7}}&0\\0&{\frac {1}{3}}\\\end{pmatrix}}

Unimoduláris mátrixszal:

U={\begin{pmatrix}2&3\\3&5\\\end{pmatrix}}

és

U^{-1}={\begin{pmatrix}5&-3\\-3&2\\\end{pmatrix}}

Kapunk:

B'=UB={\begin{pmatrix}14&9\\21&15\\\end{pmatrix}}

Legyen az üzenet és a hibavektor, majd a rejtjelezett szöveg: $m=(3,-7)$ $e=(1,-1).$

c=mB'+e=(-104,-79)

A visszafejtéshez szüksége lesz:

cB^{-1}=\left({\frac {-104}{7)),{\frac {-79}{3}}\jobb)

Ez felfelé kerekít $(-15,-26).$

És az üzenet visszaáll a következővel:

m=(-15,-26)U^{-1}=(3,-7).\,

Források és további olvasmányok

Oded Goldreich, Shafi Goldwasser és Shai Halevi. Nyilvános kulcsú kriptorendszerek rácsredukciós problémákból. In CRYPTO '97: Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, 112-131 pages, London, UK, 1997. Springer-Verlag.
Phong Q. Nguyen. A Goldreich-Goldwasser-Halevi kriptorendszer kriptoanalízise a Crypto '97-ből. In CRYPTO '99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 288-304, London, UK, 1999. Springer-Verlag.

Jegyzetek

↑ Phong Q. Nguyen. A Goldreich-Goldwasser-Halevi kriptorendszer kriptoanalízise a Crypto '97-ből. . - S. 1-17 . Archiválva az eredetiből 2018. július 16-án.
↑ 1 2 Phong Q. Nguyen. A Goldreich-Goldwasser-Halevi kriptorendszer kriptoanalízise a Crypto '97-ből. S. - 1-2. . Archiválva az eredetiből 2018. július 16-án. (határozatlan)
↑ Phong Q. Nguyen. A Goldreich-Goldwasser-Halevi kriptorendszer kriptoanalízise a Crypto '97-ből. S. - 1. . Archiválva az eredetiből 2018. július 16-án. (határozatlan)
↑ Oded Goldreich, Shafi Goldwasser és Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Nyilvános kulcsú kriptorendszerek rácsredukciós problémákból]. - S. 112-114 . Archiválva : 2019. május 4.
↑ Phong Q. Nguyen. A Goldreich-Goldwasser-Halevi kriptorendszer kriptoanalízise a Crypto '97-ből. . - S. 4 . Archiválva az eredetiből 2018. július 16-án.
↑ Oded Goldreich, Shafi Goldwasser és Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Nyilvános kulcsú kriptorendszerek rácsredukciós problémákból]. — S. 122-124 . Archiválva : 2019. május 4.
↑ Oded Goldreich, Shafi Goldwasser és Shai Halevi. [ https://link.springer.com/content/pdf/10.1007%2FBFb0052231.pdf Nyilvános kulcsú kriptorendszerek rácsredukciós problémákból]. - S. 127-130 . Archiválva : 2019. május 4.