Kryptografi på gitter

Gitterkryptografi er en tilgang til at bygge asymmetriske krypteringsalgoritmer ved hjælp af gitterteoriproblemer , det vil sige optimeringsproblemer på diskrete additive undergrupper defineret på et sæt . $\mathbb {R} ^{n}$

Sammen med andre metoder til post-kvantekryptografi anses det for lovende på grund af en kvantecomputers evne til at bryde udbredte asymmetriske krypteringssystemer baseret på to typer talteoretiske problemer: heltalsfaktoriseringsproblemer og diskrete logaritmeproblemer. Kompleksiteten af cracking algoritmer bygget på gitter er ekstrem høj, de bedste algoritmer kan løse dette problem med vanskeligheder i eksponentiel tid. Fra midten af 2010'erne er der ingen kendt kvantealgoritme, der overgår en konventionel computer.

Forudsætninger for oprettelse

I 1995 demonstrerede Peter Shor en polynomial algoritme til at knække kryptografiske systemer med offentlig nøgle ved hjælp af en kvantecomputer, og derved bestemme perioden for eksistensen af disse systemer før fremkomsten af kvantecomputere af tilstrækkelig dimension.

I 1996 demonstrerede Lov Grover en generel databasesøgningsmetode, der kunne dekryptere symmetriske krypteringsalgoritmer, svarende til at halvere chiffernøglen.

I 2001 demonstrerede et IBM-hold udførelsen af Shors faktoriseringsalgoritme for tallet 15. Tallet blev faktoriseret med 3 og 5 ved hjælp af en kvantecomputer med 7 qubits , bygget af 18 10 molekyler, bestående af fem fluoratomer og to carbonatomer, med information optaget ved hjælp af radiosignaler og aflæsning ved metoder til kernemagnetisk resonans [1] .

Fra anden halvdel af 1990'erne blev det nødvendigt at søge efter krypto-resistente problemer for kvantecomputere til krypteringens post-kvante æra , da en af tilgangene det blev foreslået at bruge gitter i - diskrete undergrupper af den virkelige vektor rum, hvis lineære spænd falder sammen med det: $\mathbb {R} ^{n}$

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

Beregningsmæssigt komplekse problemer

Opgaven med at finde den korteste vektor ( SVP , eng. Shortest Vector Problem ) er at finde en ikke-nul vektor i en given gitterbasis i forhold til en vis normal [2] .

Problemet med at finde et (ca.) ideelt korteste vektorproblem ( ISVP , engelsk (omtrent) ideal shortest vector problem ) betragtes ikke som NP-hårdt. Der er dog ingen kendte gitter baseret på reduktionsmetoden, der er væsentligt mere effektive på ideelle strukturer end på generelle [3] .

Et andet problem er at finde det (tilnærmelsesvis) korteste uafhængige vektorproblem ( SIVP , engelsk (approximate) shortest independent vectors problem ), hvor grundlaget for gitteret er givet, og det kræves at finde lineært uafhængige vektorer [4] . $B$ $n$

Problemet med at finde den nærmeste vektor ( CVP , eng. Closest Vector Problem ) er at finde en vektor i et gitter efter et givet grundlag og en eller anden vektor, der ikke hører til gitteret, samtidig med at den i længden er så ens i længden som en given given. vektor.

LLL-algoritme

Alle disse problemer kan løses i polynomisk tid ved hjælp af den velkendte LLL-algoritme opfundet i 1982 af Arjen Lenstra , Hendrik Lenstra og Laszlo Lovas [5] .

På en given basis , med n - dimensionelle heltalskoordinater, i et gitter på , hvor , finder LLL-algoritmen en kortere (måling $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $L$ $\mathbb {R} ^{n}$ $\d\leq n$ [ klargør ] ) ortogonalt grundlag over tid:

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

hvor er den maksimale længde af vektoren i dette rum. $B$ $b_{i}$

Grundlæggende kryptografiske konstruktioner og deres sikkerhed

Kryptering

GGH - et kryptosystem baseret på CVP, nemlig på en envejsfunktion med en hemmelig indgang baseret på kompleksiteten af reduktionen af gitteret. Udgivet i 1997. Når vi kender grundlaget, kan vi generere en vektor tæt på det givne punkt, men når vi kender denne vektor, har vi brug for det oprindelige grundlag for at finde udgangspunktet. Algoritmen blev testet i 1999.

Implementering af GGH

GGH består af en offentlig nøgle og en privat nøgle.

Den hemmelige nøgle er grundlaget for gitteret og den unimodulære matrix . $B$ $L$ $U$

Den offentlige nøgle er et eller andet grundlag i gitteret i formen . $L$ $B'=UB$

For nogle består beskedrummet af en vektor , hvor . $M$ $(\lambda _{1},...,\lambda _{n})$ $-M<\lambda _{i}<M$

Kryptering

Givet besked , forvrængning , offentlig nøgle : $m=(\lambda _{1},...,\lambda _{n})$ $e$ $B'$

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

I matrixform:

v=m\cdot B'

$m$ består af heltalsværdier, et gitterpunkt, og v er også et gitterpunkt. Derefter chifferteksten: $b'$

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

Dekryptering

For at dekryptere er det nødvendigt at beregne:

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 fjernes af omtrentlige årsager. Besked: $e\cdot B^{-1}$

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

Eksempel

Vi vælger et gitter med basis : $L\delsæt \mathbb {R} ^{2}$ $B$

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

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

hvor

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

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

Som resultat:

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

Lad meddelelsen og fejlvektor være . Derefter chifferteksten: $m=(3,-7)$ $e=(1,-1)$

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

For at dekryptere skal du beregne:

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

Afrunding giver , gendan beskeden: $(-15,-26)$

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

NTRUEncrypt er et SVP-baseret kryptosystem, der er et alternativ til RSA og ECC. Beregningen bruger en polynomialring .

Signatur

GGH-signaturordningen, først foreslået i 1995 og offentliggjort i 1997 af Goldrich, er baseret på vanskeligheden ved at finde den nærmeste vektor. Ideen var at bruge gitter, hvor den "dårlige" basis, vektorer er lange og næsten parallelle, er åbne og den "gode" basis, med korte og næsten ortogonale vektorer, er lukket. Ifølge deres metode skal meddelelsen hashes ind i et mellemrum spændt ud af et gitter, og signaturen for en given hash i dette rum er den nærmeste knude på gitteret. Ordningen havde ingen formel sikkerhedsbevis, og dens grundlæggende version blev knækket i 1999 af Nguyen . I 2006 blev den modificerede version knækket igen af Nguyen og Regev .

NTRUSign er en speciel, mere effektiv version af GGH-signaturen, der har en mindre nøgle og signaturstørrelse. Den bruger kun gitter af en delmængde af sættet af alle gitter forbundet med nogle polynomielle ringe. NTRUSign er blevet foreslået som en IEEE P1363.1-standard.

Noter

↑ Vandersypen, Lieven M.K.; Steffen, Matthias; Breyta, Gregory & Yannoni, Costantino S. (2001), Eksperimentel opdagelse af Shor's kvantefaktoreringsalgoritme ved hjælp af kernemagnetisk resonans , Nature T. 414 (6866): 883–887, PMID 11780055 , doi .148 / 10.148a/ .148a : /cryptome.org/shor-nature.pdf > Arkiveret 29. marts 2017 på Wayback Machine
↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Faktorering af polynomier med rationelle koefficienter] , <www.cs.elte.hu/~lovasz/scans/lll.pdf>
↑ Generaliserede kompakte rygsække er kollisionsbestandige. I: Internationalt kollokvium om automater, sprog og programmering , < https://link.springer.com/content/pdf/10.1007/11787006.pdf >
↑ Kompleksiteten af gitterproblemer: et kryptografisk perspektiv. Kluwer internationale serie i ingeniørvidenskab og datalogi , < http://cseweb.ucsd.edu/~daniele/papers/book.bib > Arkiveret 29. maj 2015 på Wayback Machine
↑ Lenstra, AK; Lenstra, HW, Jr.; Lovasz, L. Faktorering af polynomier med rationelle koefficienter (neopr.) // Mathematische Annalen . - 1982. - T. 261 , nr. 4 . - S. 515-534 . - doi : 10.1007/BF01457454 .

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort