NTRUSign

NTRUSign , cunoscut și ca algoritm de semnătură NTRU , este un algoritm de criptare cu cheie publică a semnăturii digitale bazat pe schema de semnătură GGH .

Istorie

Algoritmul a fost prezentat pentru prima dată la sesiunea en:Asiacrypt din 2001 și publicat în formă revizuită de colegi la conferința RSA din 2003 [1] . Ediția din 2003 a inclus recomandări de parametri pentru nivelul de securitate de 80 de biți. Următoarea publicație din 2005 a revizuit recomandările pentru nivelul de securitate pe 80 de biți și a prezentat, de asemenea, parametrii nivelurilor de securitate necesare de 112, 128, 160, 192 și 256 de biți și a descris algoritmi pentru obținerea seturilor de parametri pentru orice nivel de securitate dorit. NTRU Cryptosystems, Inc. a solicitat un brevet pentru acest algoritm.[ când? ]

Caracteristici

NTRUSign include afișarea unui mesaj pentru un punct aleatoriu într-un spațiu 2N-dimensional, unde N este unul dintre parametrii NTRUSign și rezolvarea problemei de a găsi cel mai apropiat vector într-o rețea , strâns legată de rețeaua NTRUEncrypt . Această rețea are proprietatea că o anumită bază 2N-dimensională pentru rețea poate fi descrisă folosind 2 vectori, fiecare dintre care constă din N coeficienți și o bază care poate fi definită printr-un vector N-dimensional separat. Acest lucru permite cheilor publice să fie reprezentate în spațiu, mai degrabă decât , așa cum este cazul altor scheme de semnătură bazate pe rețea. Operațiunile necesită timp, spre deosebire de criptografia cu curbă eliptică și RSA. Prin urmare, NTRUSign este mai rapid decât acești algoritmi la niveluri de securitate scăzute și semnificativ mai rapid la niveluri de securitate ridicate. $O(N)$ $O(N^{2})$ $O(N^{2})$ $O(N^{3})$

NTRUSign este în considerare pentru standardizare de către grupul de lucru IEEE P1363.

Descrierea algoritmului

La fel ca în NTRUEncrypt , în NTRUSign calculele se fac într-un inel , unde înmulțirea „ ” este o convoluție modulo ciclică . Produsul a două polinoame și este . $R=\mathbb {Z} _{q}[X]/(X^{N}-1)$ $*$ $q$ $f=[f_{0},f_{1},\ldots ,f_{N-1}]$ $g=[g_{0},g_{1},\ldots ,g_{N-1}]$ $f*g=\sum _{i+j\equiv k\mod N}f_{i}\cdot g_{j}\mod q$

NTRUSign se poate baza pe grile standard sau transpuse. Principalul avantaj al rețelei transpuse este că coeficienții polinomului aparțin lui {-1,0,1}. Aceasta crește viteza de înmulțire.

Generare cheie

Date de intrare: numere întregi , șir sau . $N,q,d_{f},d_{g},B>0$ $t=standard$ $transpunere$
Generarea de baze de zăbrele închise și o bază de zăbrele deschisă $B$

Instalați . Pana la :

i=B

i>0

Alegeți în mod arbitrar , ∈ , coprim cu , respectiv. $f$ $g$ $\mathbb {R}$ $d_{f)$ $d_{g)$
Găsiți unele mici astfel încât . $F,G\in R$ $f*GF*g=q$
Dacă , setați și . $t=standard$ $f_{i}=f$ $f'_{i}=F$

Dacă , setați și .

t=transpunere

f_{i}=f

f'_{i}=g

Calculați . Instalați .

h_{i}=f_{i}^{-1}*f'_{i}modq

i=i-1

Cheie publică: parametrii de intrare și . $h=ho=f_{0}^{-1}*f'_{0}\operatorname {mod} q$
Cheie privată: pentru . $\left\{f_{i},f'_{i},h_{i}\right\)$ $i=0...B$

Semnătura

Semnătura necesită o funcție hash în spațiul digital al documentului . $H:{\mathcal {D}}\rightarrow R$ $\mathcal{D}$

Date de intrare: document digital și cheie privată pentru . $D\in {\mathcal {D}}$ $\left\{f_{i},f'_{i},h_{i}\right\)$ $i=0...B$
Instalați . $r=0$
Instalați și . Reprezentați ca un șir de biți. Setați unde denotă concatenarea . Instalați . $s=0$ $i=B$ $r$ $m_{o}=H(D||r)$ $||$ $m=m_{o)$

$\left\{f_{i},f'_{i},h_{i}\right\)$ - baza $i$
calculati $x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil$
calculati $y=\lfloor {\frac {1}{q}}m_{i}*f_{i}\rceil$
$s_{i}=x*f+y*f'$
$m_{i}=si*(h_{i}-h_{i-1})\mod q$
Semnătură: $s=s+s_{i)$

Verificarea semnăturii

Verificarea necesită aceeași funcție hash , „relație de normalizare” și normă polinomială . Norma unui polinom este definită ca , unde (unde aceasta din urmă este norma euclidiană). $H$ ${\mathcal {N}}\in \mathbb {R}$ $||.||$ $||t||$ $t$ $\inf _{0\leq k<q}||t+kq||_{z)$ $||r||_{z}=\sum _{i=0}^{N-1}r_{i}^{2}-{\frac {1}{N))\sum _{ i=0}^{N}r_{i}$

Date de intrare: date semnate și cheie publică . $(D,r,s)$ $h$
Reprezentați r ca un șir de biți. Instalați . $m=H(D||r)$
Calculați . $b=||(s,s*hm\operatorname {mod} g))||$
Semnătura este considerată corectă dacă . $b<{\mathcal {N}}$

Notă

Setări recomandate $(N,q,d_{f},d_{g},B,t,{\mathcal {N)))=(251,128,73,71,1,transpunere,310)$

Note

^ Jeffrey Hoffstein , Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Semnături digitale utilizând rețeaua NTRU . Arhivat din original la 30 ianuarie 2013.

Link -uri

Cea mai recentă hârtie NTRUSign, inclusiv seturi de parametri pentru mai multe niveluri de securitate
O implementare Java a NTRUSign Arhivată la 23 decembrie 2015 la Wayback Machine

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