NTRUSign

NTRUSign , også kendt som NTRU Signature Algorithm , er en digital signatur offentlig-nøgle krypteringsalgoritme baseret på GGH signaturskemaet .

Historie

Algoritmen blev først præsenteret på en:Asiacrypt-sessionen i 2001 og udgivet i peer-reviewed form på RSA-konferencen i 2003 [1] . 2003-udgaven indeholdt parameteranbefalinger for 80-bit sikkerhedsniveauet. Den næste publikation i 2005 reviderede anbefalingerne for 80-bit sikkerhedsniveauet og præsenterede også parametrene for de nødvendige sikkerhedsniveauer på 112, 128, 160, 192 og 256 bit og beskrev algoritmer til opnåelse af parametersæt for ethvert ønsket sikkerhedsniveau. NTRU Cryptosystems, Inc. ansøgte om patent på denne algoritme.[ hvornår? ]

Funktioner

NTRUSign inkluderer visning af en besked for et tilfældigt punkt i et 2N-dimensionelt rum, hvor N er en af NTRUSign-parametrene, og løsning af problemet med at finde den nærmeste vektor i et gitter , tæt relateret til NTRUEncrypt- gitteret . Dette gitter har den egenskab, at et bestemt 2N-dimensionelt grundlag for gitteret kan beskrives ved hjælp af 2 vektorer, som hver består af N koefficienter og et grundlag, der kan defineres af en separat N-dimensionel vektor. Dette tillader offentlige nøgler at blive repræsenteret i rummet i stedet for , som det er tilfældet med andre gitterbaserede signatursystemer. Operationerne tager tid, i modsætning til elliptisk kurvekryptografi og RSA. Derfor er NTRUSign hurtigere end disse algoritmer ved lave sikkerhedsniveauer og betydeligt hurtigere ved høje sikkerhedsniveauer. $O(N)$ $O(N^{2})$ $O(N^{2})$ $O(N^{3})$

NTRUSign er under overvejelse til standardisering af IEEE P1363-arbejdsgruppen.

Beskrivelse af algoritmen

Ligesom i NTRUEncrypt udføres i NTRUSign beregninger i en ring , hvor multiplikationen „ “ er en cyklisk modulo-foldning . Produktet af to polynomier og er . $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 kan være baseret på standard eller transponerede gitter. Den største fordel ved det transponerede gitter er, at koefficienterne for polynomiet hører til {-1,0,1}. Dette øger multiplikationshastigheden.

Nøglegenerering

Inputdata: heltal , streng eller . $N,q,d_{f},d_{g},B>0$ $t=standard$ $transponere$
Generering af lukkede gitterbaser og en åben gitterbasis $B$

Installer . Indtil :

i=B

i>0

Vælg vilkårligt , ∈ , coprime med hhv . $f$ $g$ $\mathbb {R}$ ${\displaystyle d_{f))$ ${\displaystyle d_{g))$
Find små sådan . $F,G\in R$ $f*GF*g=q$
Hvis , indstil og . $t=standard$ $f_{i}=f$ $f'_{i}=F$

Hvis , indstil og .

t=transponere

f_{i}=f

f'_{i}=g

Beregn . Installer .

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

i=i-1

Offentlig nøgle: inputparametre og . $h=ho=f_{0}^{-1}*f'_{0}\operatørnavn {mod} q$
Privat nøgle: til . ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ $i=0...B$

Signatur

Signaturen kræver en hash -funktion på dokumentets digitale rum . $H:{\mathcal {D}}\rightarrow R$ $\mathcal{D}$

Inputdata: digitalt dokument og privat nøgle til . $D\in {\mathcal {D}}$ ${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ $i=0...B$
Installer . $r=0$
Installer og . Repræsenter som en streng af bits. Indstil hvor angiver sammenkædning . Installer . $s=0$ $i=B$ $r$ $m_{o}=H(D||r)$ $||$ ${\displaystyle m=m_{o))$

${\displaystyle \left\{f_{i},f'_{i},h_{i}\right\))$ - base $jeg$
Beregn $x=\lfloor -{\frac {1}{q}}m_{i}*f'_{i}\rceil$
Beregn $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$
Underskrift: ${\displaystyle s=s+s_{i))$

Signaturbekræftelse

Verifikation kræver den samme hash-funktion , "normaliserende forhold" og polynomiel norm . Normen for et polynomium er defineret som , hvor (hvor sidstnævnte er den euklidiske norm). $H$ ${\mathcal {N}}\in \mathbb {R}$ $||.||$ $||t||$ $t$ ${\displaystyle \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}$

Inputdata: Signerede data og offentlig nøgle . $(D,r,s)$ $h$
Repræsenter r som en streng af bits. Installer . $m=H(D||r)$
Beregn . $b=||(s,s*hm\operatørnavn {mod} g))||$
Signaturen anses for korrekt, hvis . $b<{\mathcal {N}}$

Bemærk

Anbefalede indstillinger $(N,q,d_{f},d_{g},B,t,{\mathcal {N)))=(251,128,73,71,1,transponere,310)$

Noter

↑ Jeffrey Hoffstein, Nick Howgrave-Graham, Jill Pipher, Joseph H. Silverman, William Whyte. NTRUSign: Digitale signaturer ved hjælp af NTRU-gitteret . Arkiveret fra originalen den 30. januar 2013.

Links

Seneste NTRUSign-papir, inklusive parametersæt for flere sikkerhedsniveauer
En Java-implementering af NTRUSign Arkiveret 23. december 2015 på Wayback Machine

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