Kryptografi på galler

Gitterkryptografi är ett tillvägagångssätt för att bygga asymmetriska krypteringsalgoritmer med hjälp av gitterteoriproblem , det vill säga optimeringsproblem på diskreta additiva undergrupper definierade på en uppsättning . $\mathbb {R} ^{n}$

Tillsammans med andra metoder för post-kvantkryptografi anses det lovande på grund av förmågan hos en kvantdator att bryta allmänt använda asymmetriska krypteringssystem baserade på två typer av talteoretiska problem: heltalsfaktoriseringsproblem och diskreta logaritmproblem. Komplexiteten hos sprickalgoritmer byggda på gitter är extremt hög, de bästa algoritmerna kan lösa detta problem med svårighet i exponentiell tid. I mitten av 2010-talet är ingen kvantalgoritm känd för att överträffa en konventionell dator.

Förutsättningar för att skapa

1995 demonstrerade Peter Shor en polynomalgoritm för att knäcka kryptografiska system med offentlig nyckel med hjälp av en kvantdator, och därigenom bestämma perioden för existensen av dessa system innan uppkomsten av kvantdatorer av tillräcklig dimension.

1996 demonstrerade Lov Grover en allmän databassökningsmetod som kunde dekryptera symmetriska krypteringsalgoritmer, motsvarande halvering av chiffernyckeln.

År 2001 demonstrerade ett IBM-team exekveringen av Shors faktoriseringsalgoritm för talet 15. Antalet faktoriserades med 3 och 5 med hjälp av en kvantdator med 7 qubits , byggd av 18 10 molekyler, bestående av fem fluoratomer och två kolatomer, med information inspelad med hjälp av radiosignaler och avläsning med metoder för kärnmagnetisk resonans [1] .

Från och med andra hälften av 1990-talet blev det nödvändigt att söka efter kryptoresistenta problem för kvantdatorer för krypteringen efter kvanttiden , eftersom ett av tillvägagångssätten föreslogs att använda gitter i - diskreta undergrupper av den verkliga vektorn rymden, vars linjära spann sammanfaller med det: $\mathbb {R} ^{n}$

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

Beräkningsmässigt komplexa problem

Uppgiften att hitta den kortaste vektorn ( SVP , eng. Shortest Vector Problem ) är att hitta en vektor som inte är noll i en given gitterbas med avseende på en viss normal [2] .

Problemet med att hitta ett (ungefärligt) idealiskt kortaste vektorproblem ( ISVP , engelska (ungefärligt) ideal shortest vector problem ) anses inte vara NP-hårt. Det finns dock inga kända gitter baserade på reduktionsmetoden som är betydligt effektivare på ideala strukturer än på allmänna [3] .

Ett annat problem är att hitta det (ungefärliga) kortaste oberoende vektorproblemet ( SIVP , engelska (approximate) shortest independent vectors problem ), där basen för gittret anges och det krävs att hitta linjärt oberoende vektorer [4] . $B$ $n$

Problemet med att hitta den närmaste vektorn ( CVP , eng. Closest Vector Problem ) är att hitta en vektor i ett gitter enligt en given grund och någon vektor som inte hör till gittret, samtidigt som den är så lik i längden som möjligt en given vektor.

LLL-algoritm

Alla dessa problem är lösbara i polynomtid med hjälp av den välkända LLL-algoritmen som uppfanns 1982 av Arjen Lenstra , Hendrik Lenstra och Laszlo Lovas [5] .

I en given bas , med n - dimensionella heltalskoordinater, i ett gitter på , där , hittar LLL-algoritmen en kortare (mätning $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $L$ $\mathbb {R} ^{n}$ $\d\leq n$ [ förtydliga ] ) ortogonal bas över tid:

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

var är den maximala längden på vektorn i detta utrymme. $B$ $bi}$

Grundläggande kryptografiska konstruktioner och deras säkerhet

Kryptering

GGH - ett kryptosystem baserat på CVP, nämligen på en enkelriktad funktion med en hemlig ingång baserad på komplexiteten i reduktionen av gittret. Utgavs 1997. Genom att känna till basen kan vi generera en vektor nära den givna punkten, men när vi känner till denna vektor behöver vi den ursprungliga basen för att hitta startpunkten. Algoritmen testades 1999.

Implementering av GGH

GGH består av en publik nyckel och en privat nyckel.

Den hemliga nyckeln är grunden för gittret och den unimodulära matrisen . $B$ $L$ $U$

Den publika nyckeln är någon grund i gittret i formuläret . $L$ $B'=UB$

För vissa består meddelandeutrymmet av en vektor , där . $M$ $(\lambda _{1},...,\lambda _{n})$ $-M<\lambda _{i}<M$

Kryptering

Givet meddelande , distorsion , offentlig nyckel : $m=(\lambda _{1},...,\lambda _{n})$ $e$ $B'$

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

I matrisform:

v=m\cdot B'

$m$ består av heltalsvärden, en gitterpunkt och v är också en gitterpunkt. Sedan chiffertexten: $b'$

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

Dekryptering

För att dekryptera är det nödvändigt att beräkna:

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}

En del tas bort, av ungefärliga skäl. Meddelande: $e\cdot B^{-1}$

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

Exempel

Vi väljer ett galler med grund : $L\subset \mathbb {R} ^{2}$ $B$

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

och

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

var

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

och

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

Som ett resultat:

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

Låt meddelandet och felvektorn vara . Sedan chiffertexten: $m=(3,-7)$ $e=(1,-1)$

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

För att dekryptera måste du beräkna:

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

Avrundning ger , återställ meddelandet: $(-15,-26)$

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

NTRUEncrypt är ett SVP-baserat kryptosystem som är ett alternativ till RSA och ECC. Beräkningen använder en polynomring .

Signatur

GGH-signaturschemat, som först föreslogs 1995 och publicerades 1997 av Goldrich, är baserat på svårigheten att hitta den närmaste vektorn. Tanken var att använda gitter för vilka den "dåliga" basen, vektorer är långa och nästan parallella, är öppen och den "bra" basen, med korta och nästan ortogonala vektorer, är stängd. Enligt deras metod måste meddelandet hashas in i ett utrymme som sträcks av ett gitter, och signaturen för en given hash i detta utrymme är den närmaste noden i gittret. Systemet hade inget formellt säkerhetsbevis, och dess grundläggande version knäcktes 1999 av Nguyen . 2006 knäcktes den modifierade versionen igen av Nguyen och Regev .

NTRUSign är en speciell, mer effektiv version av GGH-signaturen, med en mindre nyckel och signaturstorlek. Den använder bara gitter av en delmängd av uppsättningen av alla gitter som är associerade med vissa polynomringar. NTRUSign har föreslagits som en IEEE P1363.1-standard.

Anteckningar

↑ Vandersypen, Lieven M.K.; Steffen, Matthias; Breyta, Gregory & Yannoni, Costantino S. (2001), Experimentell upptäckt av Shors kvantfaktoriseringsalgoritm med hjälp av kärnmagnetisk resonans , Nature T. 414 (6866): 883–887, PMID 11780055 , doi .148a / , doi .1483 , http:38/ . /cryptome.org/shor-nature.pdf > Arkiverad 29 mars 2017 på Wayback Machine
↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Faktorering av polynom med rationella koefficienter] , <www.cs.elte.hu/~lovasz/scans/lll.pdf>
↑ Generaliserade kompakta ryggsäckar är kollisionsbeständiga. I: Internationellt kollokvium om automater, språk och programmering , < https://link.springer.com/content/pdf/10.1007/11787006.pdf >
↑ Gitterproblemens komplexitet: ett kryptografiskt perspektiv. Kluwer internationella serie inom teknik och datavetenskap , < http://cseweb.ucsd.edu/~daniele/papers/book.bib > Arkiverad 29 maj 2015 på Wayback Machine
↑ Lenstra, AK; Lenstra, HW, Jr.; Lovasz, L. Faktorering av polynom med rationella koefficienter (neopr.) // Mathematische Annalen . - 1982. - T. 261 , nr 4 . - S. 515-534 . - doi : 10.1007/BF01457454 .

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort