Kryptografia ristikoilla

Hila kryptografia on lähestymistapa epäsymmetristen salausalgoritmien rakentamiseen käyttämällä hilateoriaongelmia , eli optimointiongelmia joukossa määritellyille diskreeteille additiivisille alaryhmille . $\mathbb {R} ^{n}$

Muiden postkvanttisalauksen menetelmien ohella sitä pidetään lupaavana, koska kvanttitietokone pystyy rikkomaan laajalti käytettyjä epäsymmetrisiä salausjärjestelmiä, jotka perustuvat kahdentyyppisiin lukuteoriaongelmiin: kokonaislukujen tekijöihin jaon ja diskreettien logaritmien ongelmiin. Hiloihin rakennettujen krakkausalgoritmien monimutkaisuus on erittäin korkea, parhaat algoritmit voivat ratkaista tämän ongelman vaikeudella eksponentiaalisessa ajassa. 2010-luvun puolivälistä lähtien ei tiedetä yhtään kvanttialgoritmia, joka olisi tehokkaampi kuin perinteinen tietokone.

Luomisen edellytykset

Vuonna 1995 Peter Shor esitteli polynomialgoritmin julkisen avaimen salausjärjestelmien murtamiseen kvanttitietokoneella, mikä määritti näiden järjestelmien olemassaolon ajan ennen riittävän mittaisten kvanttitietokoneiden syntymistä.

Vuonna 1996 Lov Grover esitteli yleisen tietokannan hakumenetelmän, joka pystyi purkamaan symmetristen salausalgoritmien salauksen, mikä vastaa salausavaimen puolittamista.

Vuonna 2001 IBM:n työryhmä esitteli Shorin faktorointialgoritmin suorittamisen luvulle 15. Luku kerrottiin 3:lla ja 5:llä käyttämällä kvanttitietokonetta, jossa on 7 kubittia ja joka rakennettiin 18 10 molekyylistä, joka koostuu viidestä fluoriatomista ja kahdesta hiiliatomista. radiosignaaleilla tallennetulla tiedolla ja ydinmagneettiresonanssimenetelmillä luetulla tiedolla [1] .

1990-luvun toisesta puoliskosta lähtien tuli tarpeelliseksi etsiä kryptoresistenttejä ongelmia kvanttitietokoneille salauksen jälkeistä aikakautta varten , koska yhtenä lähestymistavana ehdotettiin hilan käyttöä todellisen vektorin diskreetissä alaryhmissä. avaruus, jonka lineaariset jännevälit ovat yhtäpitäviä sen kanssa: $\mathbb {R} ^{n}$

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

Laskennallisesti monimutkaisia ongelmia

Lyhyimmän vektorin ( SVP , eng. Shortest Vector Problem ) löytämisen tehtävänä on löytää nollasta poikkeava vektori annetusta hilakantasta suhteessa tiettyyn normaaliin [2] .

Ongelmaa löytää (likimäärin) ihanteellinen lyhin vektoriongelma ( ISVP , englanniksi (likimääräinen) ideaalin lyhimmän vektorin ongelma ) ei pidetä NP-kovana. Pelkistysmenetelmään perustuvia hiloja, jotka olisivat merkittävästi tehokkaampia ihanteellisissa rakenteissa kuin yleisillä rakenteilla, ei kuitenkaan tunneta [3] .

Toinen ongelma on löytää (likimääräinen) lyhimpien itsenäisten vektoreiden ongelma ( SIVP , englanniksi (approximate) lyhimpien riippumattomien vektorien ongelma ), jossa hilan kanta on annettu ja vaaditaan lineaarisesti riippumattomien vektorien löytämistä [4] . $B$ $n$

Lähimmän vektorin löytämisen ongelma ( CVP , eng. Closest Vector Problem ) on löytää hilasta vektori tietyn kantan mukaan ja jokin vektori, joka ei kuulu hilaan, samalla kun se on pituudeltaan mahdollisimman samanlainen kuin annettu. vektori.

LLL-algoritmi

Kaikki nämä ongelmat ovat ratkaistavissa polynomiajassa käyttämällä tunnettua LLL-algoritmia, jonka vuonna 1982 keksivät Arjen Lenstra , Hendrik Lenstra ja Laszlo Lovas [5] .

Tietyssä kannassa , n - ulotteisilla kokonaislukukoordinaateilla, hilassa , jossa , LLL-algoritmi löytää lyhyemmän (mittaus $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $L$ $\mathbb {R} ^{n}$ $\d\leq n$ [ selventää ] ) ortogonaalinen perusta ajan myötä:

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

missä on vektorin suurin pituus tässä avaruudessa. $B$ $b_{i}$

Perussalausrakenteet ja niiden suojaus

Salaus

GGH - CVP:hen perustuva salausjärjestelmä, nimittäin yksisuuntainen toiminto, jossa on salainen sisäänkäynti , joka perustuu hilan pienentämisen monimutkaisuuteen. Julkaistu vuonna 1997. Kun tiedämme kantakohdan, voimme luoda vektorin lähelle annettua pistettä, mutta tämän vektorin tunteessa tarvitsemme alkuperäisen kantakohdan alkupisteen löytämiseksi. Algoritmi testattiin vuonna 1999.

GGH:n käyttöönotto

GGH koostuu julkisesta avaimesta ja yksityisestä avaimesta.

Salainen avain on hilan ja unimodulaarisen matriisin perusta . $B$ $L$ $U$

Julkinen avain on jonkinlainen perusta hilassa muodossa . $L$ $B'=UB$

Joillekin viestiavaruus koostuu vektorista , jossa . $M$ $(\lambda _{1},...,\lambda _{n})$ $-M<\lambda _{i}<M$

Salaus

Annettu viesti , vääristymä , julkinen avain : $m=(\lambda _{1},...,\lambda _{n})$ $e$ $B'$

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

Matriisimuodossa:

v=m\cdot B'

$m$ koostuu kokonaislukuarvoista, hilapisteestä ja v on myös hilapiste. Sitten salateksti: $b'$

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

Salauksen purku

Salauksen purkamiseksi on laskettava:

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}

Osa on poistettu likimääräisistä syistä. Viesti: $e\cdot B^{-1}$

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

Esimerkki

Valitsemme hilan pohjalta : $L\subset \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}}

missä

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

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

Tuloksena:

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

Olkoon sanoma ja virhevektori . Sitten salateksti: $m=(3,-7)$ $e=(1,-1)$

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

Salauksen purkamiseksi sinun on laskettava:

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

Pyöristys antaa , palauta viesti: $(-15,-26)$

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

NTRUEncrypt on SVP-pohjainen salausjärjestelmä, joka on vaihtoehto RSA:lle ja ECC:lle. Laskennassa käytetään polynomirengasta .

Allekirjoitus

GGH-allekirjoitusjärjestelmä, jota ehdotti ensimmäisen kerran vuonna 1995 ja julkaisi vuonna 1997 Goldrich, perustuu vaikeuteen löytää lähin vektori. Ajatuksena oli käyttää hiloja, joiden "huono" kanta, vektorit ovat pitkiä ja melkein yhdensuuntaisia, on avoin ja "hyvä" kanta, jossa on lyhyitä ja lähes ortogonaalisia vektoreita, on suljettu. Heidän menetelmänsä mukaan viesti on hajautettava hilan kattamaan tilaan, ja tietyn tiivisteen allekirjoitus tässä tilassa on hilan lähin solmu. Järjestelmällä ei ollut muodollista turvallisuustodistetta, ja Nguyen mursi sen perusversion vuonna 1999 . Vuonna 2006 Nguyen ja Regev mursivat muokatun version uudelleen .

NTRUSign on erityinen, tehokkaampi versio GGH-allekirjoituksesta, jossa on pienempi avain ja allekirjoituksen koko. Se käyttää vain hiloja kaikkien polynomirenkaiden joukon osajoukosta. NTRUSignia on ehdotettu IEEE P1363.1 -standardiksi.

Muistiinpanot

↑ Vandersypen, Lieven M.K.; Steffen, Matthias; Breyta, Gregory & Yannoni, Costantino S. (2001), Shorin kvanttifaktorointialgoritmin kokeellinen löytö ydinmagneettista resonanssia käyttäen , Nature T. 414 (6866): 883–887, PMID 11780055 , doi : 8:414055, doi : 8 : 41408 . /cryptome.org/shor-nature.pdf > Arkistoitu 29. maaliskuuta 2017 Wayback Machinessa
↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Polynomien faktorointi rationaalisilla kertoimilla] , <www.cs.elte.hu/~lovasz/scans/lll.pdf>
↑ Yleiset kompaktit reput ovat törmäyksenkestäviä. Julkaisussa: Kansainvälinen kollokviumi automaateista, kielistä ja ohjelmoinnista , < https://link.springer.com/content/pdf/10.1007/11787006.pdf >
↑ Hilaongelmien monimutkaisuus: kryptografinen näkökulma. Kluwerin kansainvälinen tekniikan ja tietojenkäsittelytieteen sarja , < http://cseweb.ucsd.edu/~daniele/papers/book.bib > Arkistoitu 29. toukokuuta 2015 Wayback Machinessa
↑ Lenstra, AK; Lenstra, HW, Jr.; Lovasz, L. Polynomien faktorointi rationaalisilla kertoimilla (neopr.) // Mathematische Annalen . - 1982. - T. 261 , nro 4 . - S. 515-534 . - doi : 10.1007/BF01457454 .

Julkisen avaimen salausjärjestelmät

Algoritmit

Kokonaislukujen faktorointi	Benalon kryptojärjestelmä Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskreetti logaritmi	BLS Cramer - Shoup Diffie-Hellman-protokolla DSA ECDH Käyrä 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Salatun avaimen vaihto ElGamalin kaava allekirjoitusmalli MQV Schnorrin kaava SPEKE SRP STS
Kryptografia ristikoilla	NTRUEncrypt NTRUSign Oppimiseen perustuva avainten vaihto virheineen Allekirjoituspohjainen koulutus, jossa virheitä kehässä AUTUUS Uusi toivo
Muut	AE CEILIDH EPOC Piilotettu kenttäyhtälöt IES Lamportin allekirjoitus McEliece Merkle-Hellmanin selkärepun salausjärjestelmä Naccache-Stern selkäreppujen salausjärjestelmä Kolmivaiheinen protokolla XTR

Teoria

Diskreetti logaritmi elliptisellä käyrällä
Elliptinen kryptografia
Hash-pohjainen kryptografia
Ei-kommutatiivinen kryptografia
RSA ongelma
Yksisuuntainen toiminto salaisella sisäänkäynnillä

Standardit

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvanttisalaus

Aiheet

Sähköinen allekirjoitus
OAEP
Sormenjälki
PKI
luottamuksen verkko
Avaimen koko
Identiteettiin perustuva kryptografia
Postkvanttisalaus
OpenPGP-kortti

Kryptografia ristikoilla

Luomisen edellytykset

Laskennallisesti monimutkaisia ​​ongelmia

LLL-algoritmi

Perussalausrakenteet ja niiden suojaus

Salaus

Allekirjoitus

Muistiinpanot

Laskennallisesti monimutkaisia ongelmia