Kriptográfia rácsokon

A rácsos kriptográfia egy megközelítés aszimmetrikus titkosítási algoritmusok felépítésére rácselméleti problémákkal , azaz optimalizálási problémákkal egy halmazon meghatározott diszkrét additív alcsoportokon . $\mathbb {R} ^{n}$

A posztkvantum kriptográfia más módszereivel együtt ígéretesnek tekinthető, mivel a kvantumszámítógép képes feltörni a széles körben használt aszimmetrikus titkosítási rendszereket, amelyek kétféle számelméleti probléma: egészszám-faktorizációs és diszkrét logaritmus-problémák alapján történnek. A rácsokra épített feltörő algoritmusok bonyolultsága rendkívül magas, a legjobb algoritmusok ezt a problémát exponenciális idő alatt nehezen tudják megoldani. A 2010-es évek közepétől nem ismert olyan kvantum algoritmus, amely felülmúlná a hagyományos számítógépeket.

A létrehozás előfeltételei

1995-ben Peter Shor egy polinomiális algoritmust mutatott be nyilvános kulcsú kriptográfiai rendszerek kvantumszámítógép segítségével történő feltörésére, ezáltal meghatározva e rendszerek létezésének időtartamát a megfelelő méretű kvantumszámítógépek megjelenése előtt.

1996-ban Lov Grover bemutatott egy általános adatbázis-keresési módszert, amely képes visszafejteni a szimmetrikus titkosítási algoritmusokat, ami egyenértékű a rejtjelkulcs felezésével.

2001-ben egy IBM csapat bemutatta a Shor-féle faktorizációs algoritmus végrehajtását a 15-ös számra. A számot 3-ra és 5-re faktorálták egy 7 qubites kvantumszámítógép segítségével , amely 18 10 molekulából épült fel, amely öt fluoratomból és két szénatomból állt. rádiójelekkel rögzített és mágneses magrezonancia módszerekkel leolvasott információval [1] .

Az 1990-es évek második felétől kezdődően szükségessé vált a kvantumszámítógépek kripto-rezisztens problémáinak keresése a titkosítás kvantum utáni korszakára , mivel az egyik megközelítés a rácsok alkalmazását javasolták a valós vektor diszkrét alcsoportjaiban. tér, amelynek lineáris fesztávja egybeesik vele: $\mathbb {R} ^{n}$

L=\left\{\sum _{i=1}^{n}\lambda _{i}b_{i}\mid \lambda _{i}\in \mathbb {Z} \right\}

Számításilag összetett problémák

A legrövidebb vektor ( SVP , eng. Shortest Vector Problem ) megtalálásának feladata, hogy egy adott rácsbázisban egy nem nulla vektort találjunk egy bizonyos normálhoz képest [2] .

Egy (körülbelül) ideális legrövidebb vektor probléma megtalálásának problémája ( ISVP , angol (approximate) ideális legrövidebb vektor probléma ) nem tekinthető NP-nehéznek. Nem ismertek azonban olyan redukciós módszeren alapuló rácsok, amelyek ideális struktúrákon lényegesen hatékonyabbak lennének, mint az általánosakon [3] .

További probléma a (közelítőleg) legrövidebb független vektorok probléma ( SIVP , angol (approximate) legrövidebb független vektorok probléma ) megtalálása, amelyben a rács alapja adott , és lineárisan független vektorokat kell találni [4] . $B$ $n$

A legközelebbi vektor megtalálásának problémája ( CVP , eng. Closest Vector Problem ) az, hogy egy vektort találjunk egy rácsban egy adott bázis szerint, és egy olyan vektort, amely nem tartozik a rácshoz, miközben a lehető leghasonlóbb az adotthoz. vektor.

LLL algoritmus

Mindezek a problémák polinomiális időben megoldhatók a jól ismert LLL algoritmus segítségével, amelyet Arjen Lenstra , Hendrik Lenstra és Laszlo Lovas [5] talált ki 1982-ben .

Adott bázison , n - dimenziós egész koordinátákkal, egy rácsában , ahol , az LLL algoritmus rövidebb (mérési $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $L$ $\mathbb {R} ^{n}$ $\d\leq n$ [ pontosítás ] ) ortogonális alap az idő függvényében:

O(d^{5}n\log ^{3}B)

ahol a vektor maximális hossza ebben a térben. $B$ $kettős}$

Alapvető kriptográfiai konstrukciók és biztonságuk

Titkosítás

GGH - CVP-n alapuló kriptorendszer, mégpedig egy egyirányú funkción, titkos bejárattal a rács redukciójának összetettsége alapján. 1997-ben jelent meg. A bázis ismeretében az adott ponthoz közeli vektort generálhatunk, de ennek a vektornak a ismeretében szükségünk van az eredeti bázisra a kiindulópont megtalálásához. Az algoritmust 1999-ben tesztelték.

A GGH megvalósítása

A GGH egy nyilvános kulcsból és egy privát kulcsból áll.

A titkos kulcs a rács és az unimoduláris mátrix alapja . $B$ $L$ $U$

A nyilvános kulcs valamilyen alap a rácsban a formában . $L$ $B'=UB$

Egyesek számára az üzenettér egy vektorból áll , ahol . $M$ $(\lambda _{1},...,\lambda _{n})$ $-M<\lambda _{i}<M$

Titkosítás

Adott üzenet , torzítás , nyilvános kulcs : $m=(\lambda _{1},...,\lambda _{n})$ $e$ $B'$

v=\sum \lambda _{i}b_{i}'

Mátrix formában:

v=m\cdot B'

$m$ egész értékekből áll, egy rácspontból, és v is egy rácspont. Aztán a rejtjelezett szöveg: $b'$

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

Dekódolás

A visszafejtéshez ki kell szá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}

Közelítési okokból egy alkatrész eltávolítva. Üzenet: $e\cdot B^{-1}$

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

Példa

Kiválasztunk egy rácsot , amelynek alapja : $L\subset \mathbb {R} ^{2}$ $B$

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

és

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

ahol

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

és

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

Ennek eredményeként:

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

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

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

A visszafejtéshez ki kell számolnia:

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

A kerekítés megadja , visszaállítja az üzenetet: $(-15,-26)$

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

Az NTRUEncrypt egy SVP-alapú titkosítási rendszer, amely az RSA és az ECC alternatívája. A számítás polinomiális gyűrűt használ .

Aláírás

A GGH aláírási séma, amelyet először 1995-ben javasoltak és 1997-ben tett közzé Goldrich, a legközelebbi vektor megtalálásának nehézségén alapul. Az ötlet az volt, hogy olyan rácsokat használjunk, amelyeknél a "rossz" bázis, a vektorok hosszúak és majdnem párhuzamosak, nyitottak, a "jó" bázis pedig rövid és csaknem ortogonális vektorokkal zárva van. Módszerük szerint az üzenetet egy rács által átívelt térbe kell hashelni, és ebben a térben az adott hash aláírása a rács legközelebbi csomópontja. A rendszernek nem volt hivatalos biztonsági bizonyítéka, és az alapverziót 1999-ben Nguyen feltörte . 2006-ban a módosított változatot Nguyen és Regev ismét feltörte .

Az NTRUSign a GGH aláírás speciális, hatékonyabb változata, kisebb kulccsal és aláírásmérettel. Csak néhány polinomgyűrűhöz társított összes rácshalmaz egy részhalmazának rácsait használja. Az NTRUSignt IEEE P1363.1 szabványként javasolták.

Jegyzetek

↑ Vandersypen, Lieven M.K.; Steffen, Mátyás; Breyta, Gregory & Yannoni, Costantino S. (2001), Shor kvantumfaktoring algoritmusának kísérleti felfedezése mágneses magrezonanciával , Nature T. 414 (6866): 883–887, PMID 11780055 , doi : 8 : 3/1408 . /cryptome.org/shor-nature.pdf > Archivált : 2017. március 29. a Wayback Machine -nél
↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Polinomok faktorálása racionális együtthatókkal] , <www.cs.elte.hu/~lovasz/scans/lll.pdf>
↑ Az általánosított kompakt hátizsákok ütközésállóak. In: Nemzetközi kollokvium automatákról, nyelvekről és programozásról , < https://link.springer.com/content/pdf/10.1007/11787006.pdf >
↑ A rácsproblémák összetettsége: kriptográfiai perspektíva. A Kluwer nemzetközi mérnöki és számítástechnikai sorozat , < http://cseweb.ucsd.edu/~daniele/papers/book.bib > Archivált : 2015. május 29. a Wayback Machine -nél
↑ Lenstra, AK; Lenstra, HW, Jr.; Lovasz, L. Polinomok faktorálása racionális együtthatókkal (neopr.) // Mathematische Annalen . - 1982. - T. 261 , 4. sz . - S. 515-534 . - doi : 10.1007/BF01457454 .

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya