Criptografia pe zăbrele

Criptografia lattice este o abordare pentru construirea de algoritmi de criptare asimetrică folosind probleme de teoria rețelei , adică probleme de optimizare pe subgrupuri aditive discrete definite pe o mulțime . $\mathbb {R} ^{n}$

Alături de alte metode de criptografie post-cuantică , este considerată promițătoare datorită capacității unui computer cuantic de a sparge sistemele de criptare asimetrică utilizate pe scară largă, bazate pe două tipuri de probleme de teoria numerelor: probleme de factorizare a întregilor și probleme de logaritm discret. Complexitatea algoritmilor de cracare construiti pe retele este extrem de mare, cei mai buni algoritmi pot rezolva cu dificultate aceasta problema in timp exponential. De la mijlocul anilor 2010, nu se cunoaște niciun algoritm cuantic care să depășească un computer convențional.

Condiții preliminare pentru creare

În 1995, Peter Shor a demonstrat un algoritm polinom pentru spargerea sistemelor criptografice cu cheie publică folosind un computer cuantic, determinând astfel perioada de existență a acestor sisteme înainte de apariția computerelor cuantice de dimensiune suficientă.

În 1996, Lov Grover a demonstrat o metodă generală de căutare a bazelor de date care ar putea decripta algoritmi de criptare simetrică, echivalent cu înjumătățirea cheii de cifrare.

În 2001, o echipă IBM a demonstrat execuția algoritmului de factorizare al lui Shor pentru numărul 15. Numărul a fost factorizat cu 3 și 5 folosind un computer cuantic cu 7 qubiți , construit din 18 10 molecule, constând din cinci atomi de fluor și doi atomi de carbon, cu informații înregistrate cu ajutorul semnalelor radio și citire prin metode de rezonanță magnetică nucleară [1] .

Începând din a doua jumătate a anilor 1990, a devenit necesară căutarea unor probleme criptorezistente pentru calculatoarele cuantice pentru era post-cuantică a criptării , ca una dintre abordările a fost propusă utilizarea rețelelor în - subgrupuri discrete ale vectorului real. spațiu, ale cărui intervale liniare coincid cu el: $\mathbb {R} ^{n}$

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

Probleme complexe din punct de vedere computațional

Sarcina de a găsi cel mai scurt vector ( SVP , ing. Shortest Vector Problem ) este de a găsi un vector diferit de zero într-o bază de rețea dată în raport cu o anumită normală [2] .

Problema găsirii unei probleme a vectorului cel mai scurt ideal (aproximativ) ( ISVP , în engleză (aproximativ) problema vectorului cel mai scurt ideal ) nu este considerată NP-hard. Cu toate acestea, nu există rețele cunoscute bazate pe metoda reducerii care să fie semnificativ mai eficiente pe structurile ideale decât pe cele generale [3] .

O altă problemă este găsirea celei mai scurte probleme de vectori independenți ( SIVP , în engleză (aproximate) shortest independent vectors problem ), în care este dată baza rețelei și este necesar să se găsească vectori liniar independenți [4] . $B$ $n$

Problema găsirii celui mai apropiat vector ( CVP , ing. Closest Vector Problem ) este găsirea unui vector într-o rețea în conformitate cu o bază dată și a unui vector care nu aparține rețelei, având în același timp cât mai asemănător ca lungime cu un anumit vector. vector.

Algoritmul LLL

Toate aceste probleme sunt rezolvabile în timp polinomial folosind binecunoscutul algoritm LLL inventat în 1982 de Arjen Lenstra , Hendrik Lenstra și Laszlo Lovas [5] .

Într-o bază dată , cu coordonate întregi n -dimensionale, într-o rețea de , unde , algoritmul LLL găsește o mai scurtă (măsurând $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ $L$ $\mathbb {R} ^{n}$ $\d\leq n$ [ clarifica ] ) bază ortogonală în timp:

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

unde este lungimea maximă a vectorului în acest spațiu. $B$ $b_{i}$

Construcții criptografice de bază și securitatea acestora

Criptare

GGH - un criptosistem bazat pe CVP, și anume pe o funcție unidirecțională cu intrare secretă bazată pe complexitatea reducerii rețelei. A fost publicată în 1997. Cunoscând baza, putem genera un vector apropiat de punctul dat, dar cunoscând acest vector, avem nevoie de baza originală pentru a găsi punctul de plecare. Algoritmul a fost testat în 1999.

Implementarea GGH

GGH constă dintr-o cheie publică și o cheie privată.

Cheia secretă este baza rețelei și a matricei unimodulare . $B$ $L$ $U$

Cheia publică este o bază în zăbrele în forma . $L$ $B'=UB$

Pentru unii , spațiul mesajului este format dintr - un vector , unde . $M$ $(\lambda _{1},...,\lambda _{n})$ $-M<\lambda _{i}<M$

Criptare

Mesajul dat , distorsiunea , cheia publică : $m=(\lambda _{1},...,\lambda _{n})$ $e$ $B'$

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

Sub formă de matrice:

v=m\cdot B'

$m$ constă din valori întregi, un punct de rețea și v este, de asemenea, un punct de rețea. Apoi textul cifrat: $b'$

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

Decriptare

Pentru a decripta este necesar să se calculeze:

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}

Partea este eliminată, din motive de aproximare. Mesaj: $e\cdot B^{-1}$

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

Exemplu

Alegem o zăbrele cu bază : $L\subset \mathbb {R} ^{2}$ $B$

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

și

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

Unde

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

și

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

Ca urmare:

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

Fie mesajul și vectorul de eroare . Apoi textul cifrat: $m=(3,-7)$ $e=(1,-1)$

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

Pentru a decripta, trebuie să calculați:

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

Rotunjirea dă , restabiliți mesajul: $(-15,-26)$

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

NTRUEncrypt este un criptosistem bazat pe SVP, care este o alternativă la RSA și ECC. Calculul folosește un inel polinomial .

Semnătura

Schema de semnătură GGH, propusă pentru prima dată în 1995 și publicată în 1997 de Goldrich, se bazează pe dificultatea de a găsi cel mai apropiat vector. Ideea a fost să se folosească rețele pentru care baza „rele”, vectorii sunt lungi și aproape paraleli, este deschisă și baza „bună”, cu vectori scurti și aproape ortogonali, este închisă. Conform metodei lor, mesajul trebuie să fie indexat într-un spațiu acoperit de o rețea, iar semnătura pentru un anumit hash în acest spațiu este cel mai apropiat nod al rețelei. Schema nu avea nicio dovadă formală de securitate, iar versiunea sa de bază a fost spartă în 1999 de Nguyen . În 2006, versiunea modificată a fost spartă din nou de Nguyen și Regev .

NTRUSign este o versiune specială, mai eficientă a semnăturii GGH, cu o cheie și o dimensiune mai mică a semnăturii. Folosește numai rețelele unui submult al mulțimii tuturor rețelelor asociate cu unele inele polinomiale. NTRUSign a fost propus ca standard IEEE P1363.1.

Note

↑ Vandersypen, Lieven M.K.; Steffen, Matthias; Breyta, Gregory & Yannoni, Costantino S. (2001), Experimental discovery of Shor's quantum factoring algorithm using nuclear magnetic resonance , Nature T. 414 (6866): 883–887, PMID 11780055 , doi : 10.1038 /a , < 10.1038/a 414 /cryptome.org/shor-nature.pdf > Arhivat 29 martie 2017 la Wayback Machine
↑ [www.cs.elte.hu/~lovasz/scans/lll.pdf Factorizarea polinoamelor cu coeficienți raționali] , <www.cs.elte.hu/~lovasz/scans/lll.pdf>
↑ Rucsacii compacti generalizati sunt rezistenti la coliziune. În: Colocviu internațional despre automate, limbaje și programare , < https://link.springer.com/content/pdf/10.1007/11787006.pdf >
↑ Complexitatea problemelor latice: o perspectivă criptografică. Seria internațională Kluwer în inginerie și informatică , < http://cseweb.ucsd.edu/~daniele/papers/book.bib > Arhivat 29 mai 2015 la Wayback Machine
↑ Lenstra, AK; Lenstra, HW, Jr.; Lovasz, L. Factorizarea polinoamelor cu coeficienți raționali (neopr.) // Mathematische Annalen . - 1982. - T. 261 , nr 4 . - S. 515-534 . - doi : 10.1007/BF01457454 .

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP