Postkvantekryptografi

Postkvantekryptografi er en del af kryptografi , der forbliver relevant selv med fremkomsten af kvantecomputere og kvanteangreb. Da kvantecomputere markant udkonkurrerer klassiske computerarkitekturer i beregningshastigheden af traditionelle kryptografiske algoritmer , bliver moderne kryptografiske systemer potentielt sårbare over for kryptografiske angreb . De fleste traditionelle kryptosystemer er afhængige af heltalsfaktoriseringsproblemer eller diskrete logaritmeproblemer , som let kan løses på tilstrækkeligt store kvantecomputere ved hjælp af Shor 's algoritme [1] [2]. Mange kryptografer udvikler i øjeblikket algoritmer, der er uafhængige af kvanteberegning, det vil sige modstandsdygtige over for kvanteangreb.

Der er klassiske kryptosystemer , der er afhængige af beregningsmæssigt komplekse problemer og har en række væsentlige forskelle fra ovenstående systemer, hvilket gør dem meget sværere at løse. Disse systemer er uafhængige af kvanteberegning og betragtes derfor som kvante-resistente eller "post-kvante" kryptosystemer.

Postkvantekryptografi adskiller sig til gengæld fra kvantekryptografi , som omhandler kommunikationssikkerhedsmetoder baseret på kvantefysikkens principper .

Algoritmer

Post-kvantekryptografiske konstruktioner er i stand til at redde den kryptografiske verden fra kvanteangreb. Selvom en kvantecomputer vil ødelægge de fleste af de traditionelle algoritmer ( RSA , DSA , ECDSA ), vil ultrahurtig computing ikke helt slippe af med kryptografi, da post-kvantekryptografi hovedsageligt er fokuseret på fem forskellige tilgange, der løser problemet med kvanteangreb [2] [3] .

Kryptografi baseret på hash-funktioner

Et klassisk eksempel er Merkles offentlige nøglesignatur baseret på et hash-træ. Ralph Charles Merkle foreslog denne digitale signaturalgoritme i 1979 som et interessant alternativ til RSA og DSA digitale signaturer. Den største ulempe ved Merkle-ordningen er, at der for enhver hash- baseret offentlig nøgle er en grænse for antallet af signaturer, der kan opnås fra det tilsvarende sæt private nøgler. Dette faktum reducerede niveauet af interesse for signaturer af denne type, indtil der var et behov for kryptografi, der var modstandsdygtig over for virkningerne af kvantecomputere.

Kryptografi baseret på fejlkorrektionskoder

Det er en af de mest lovende kandidater til post-kvantekryptosystemer. Det klassiske eksempel er McEliece og Niederreiter krypteringsordninger .

Gitterbaseret kryptografi

Det klassiske eksempel på krypteringssystemer er Ring - Learning with Errors [4] [5] [6] [7] eller det ældre NTRU , GGH og Michiancio kryptosystem .

Kryptografi baseret på flerdimensionelle kvadratiske systemer

En af de mest interessante ordninger er Jacques Patarins HFE offentlige nøglesignatur , foreslået af ham i 1996 som en generalisering af Matsumoto og Imai [2] forslag .

Privat nøglekryptering

Et bemærkelsesværdigt eksempel er Rijndael -chifferet , foreslået i 1998, senere omdøbt til AES (Advanced Encryption Standard).

Kryptering ved hjælp af supersingular isogeni

Dette er en analog af Diffie-Hellman-protokollen , baseret på en tur i en supersingular isogen graf, som gør det muligt for to eller flere parter at opnå en delt hemmelig nøgle ved hjælp af en ubeskyttet kommunikationskanal [8] .

Eksempler på kryptografiske angreb på RSA [2]

I 1978 nævnte et papir udgivet af udviklerne af RSA public-key kryptografisk algoritme ( et akronym for Rivest, Shamir og Adleman) Richard Schreppels nye lineære si" algoritme, som faktoriserede enhver RSA bitlængde modulus ved hjælp af simple operationer. For at denne algoritme skal kræve i det mindste simple operationer, er det således nødvendigt at vælge længder i det mindste ikke mindre end en smule. Da det betyder, at noget konvergerer til ved , kræves en mere grundig analyse af den "lineære sigte"-hastighed for at finde ud af den korrekte størrelse ved finite . $n$ $[\log _{2}n]+1$ $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2} }$ $2^{b}$ $n$ ${\displaystyle (0,5+o(1))b^{2}/{\log _{2}b))$ $0{,}5+o(1)$ $0{,}5$ $b\til\infty$ $n$ $b$

I 1988 John Pollard en ny faktoriseringsalgoritme kaldet General Number Field Sieve Method . Denne algoritme faktoriserede RSA-enheden for bitdimension ved hjælp af simple operationer. Det er således nødvendigt at vælge længder ikke mindre end en smule, så algoritmen i det mindste har brug for simple operationer. $n$ $\log _{2}n$ $2^{(1,9\dotso +o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{ 2/3}}$ $n$ $(0.016\dotso +o(1))b^{3}/(\log _{2}b)^{2}$ $2^{b}$

Siden 2008 bruger de hurtigste faktoriseringsalgoritmer til klassiske computerarkitekturer i det mindste simple operationer. Der er sket nogle forbedringer i værdierne og i detaljerne , men det er ikke svært at gætte, hvad der er optimalt, og at valget af et modul nogenlunde lig med en smule i længden vil gøre det muligt at modstå alle mulige angreb på klassiske computere. $2^{(const+o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3} }$ $konst$ $o(1)$ $1/3$ $n$ $b^{3}$

I 1994 foreslog Peter Shor en algoritme, der faktoriserede enhver bitdimensionel RSA -enhed ved hjælp af (mere præcist ) qubit-operationer på en qubit-størrelse kvantecomputer (og en lille mængde hjælpeberegninger på en klassisk computer). Ved at bruge Shors algoritme er det nødvendigt i det mindste at vælge et modul med en bitstørrelse ikke mindre end en bit, hvilket er et for stort tal for nogen af vores interesser [9] . $n$ $b=\log _{2}n$ $b^{{2+o(1)}}$ $b^{2}\cdot \log(b)\cdot \log(\log(b))$ ${\displaystyle 2\cdot b^{1+o(1)))$ $n$ $2^{{(0,5+o(1))b}}$ $b$

Praktiske anvendelser af kryptografiske konstruktioner [2]

Der er meget få eksempler på algoritmer, der er modstandsdygtige over for kvanteangreb. Men på trods af det større niveau af kryptografisk stabilitet, er post-kvantealgoritmer ikke i stand til at fortrænge moderne kryptosystemer (RSA, DSA, ECDSA osv.).

Overvej angreb på et offentlig nøglekryptosystem, nemlig McEliece- krypteringsalgoritmen , som bruger binære Goppa-koder . Indledningsvis præsenterede Robert McAlice artikler, hvor lange koder knækkes i simple operationer. Det er således påkrævet at vælge i det mindste en smule for at algoritmen i det mindste kræver simple operationer. Flere efterfølgende værker har reduceret antallet af angrebsoperationer til , men væsentligt færre , hvis de er store. Derfor bruger forbedrede angreb stadig simple operationer. Hvad angår kvantecomputere, vil deres brug kun føre til et fald i konstanten , hvilket kun vil reducere antallet af operationer, der kræves for at knække denne algoritme. $n$ $2^{(0.5+o(1))n/{\log _{2}n))$ $n$ $(2+o(1))b\log _{2}b$ $2^{b}$ $n^{\log _{2}n}=2^{(\log _{2}n)^{2))$ $(\log _{2}n)^{2}$ ${\displaystyle 0{,}5n/{\log _{2}n))$ $n$ $2^{(0.5+o(1))n/{\log _{2}n))$ $0,5$

Hvis McElieces krypteringssystem er så sikkert, hvorfor erstatter det så ikke RSA? Det handler om effektivitet – især størrelsen på nøglen. Den offentlige McEliece-nøgle bruger ca. ≈ bit, mens den offentlige RSA-nøgle bruger ca. en smule. Hvis , så vil en smule for McEliece være mindre end lidt for RSA, men reelle sikkerhedsniveauer såsom , tillader RSA at have en offentlig nøgle på flere tusinde bit, mens for McEliece nærmer nøglestørrelsen sig en million bit. ${n^{2}}/4$ ${b^{2}}(\log _{2}b)^{2}$ ${\displaystyle (0{,}016\dots )b^{3}/(\log _{2}b)^{2))$ $b\til\infty$ $b^{{2+o(1)}}$ $b^{{3+o(1)}}$ $b=128$

PQCrypto Conference

Siden 2006 er der blevet afholdt en række konferencer dedikeret til post-kvantekryptografi.

PQCrypto 2006. KU Leuven , Belgien , 23.-26. maj [10]
PQCrypto 2008. University of Cincinnati , USA , 17.-19. oktober [11]
PQCrypto 2010. Darmstadt , Tyskland , 25.-28. maj [12]
PQCrypto 2011. Taipei , Taiwan, 29. november til 2. december [13]
PQCrypto 2013. Limoges , Frankrig , 4.-7. juni [14]
PQCrypto 2014. University of Waterloo , Canada, 1.-3. oktober [15]
PQCrypto 2016. Foreløbig plan: Fukuoka , Japan, februar 2016

Se også

Noter

↑ Peter Shor (1995-08-30), Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, arΧiv : quant-ph/9508027 .
↑ 1 2 3 4 5 Daniel J. Bernstein . Introduktion til postkvantekryptografi (neopr.) // (Introduktionskapitel til bogen "Postkvantekryptografi"). – 2009.
↑ Spørgsmål og svar med Post-Quantum Computing Cryptography Researcher Jintai Ding , IEEE Spectrum (1. november 2008). Arkiveret fra originalen den 8. oktober 2015. Hentet 26. november 2014.
↑ Russisk læring med fejl
↑ Peikert, Chris Lattice Kryptografi til internettet . IACR (2014). Hentet 10. maj 2014. Arkiveret fra originalen 12. maj 2014. (ubestemt)
↑ Guneysu, Tim Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems . INRIA (2012). Hentet 12. maj 2014. Arkiveret fra originalen 18. maj 2014. (ubestemt)
↑ Zhang, jiang Autentificeret nøgleudveksling fra Ideal Lattices . iacr.org . IACR (2014). Hentet 7. september 2014. Arkiveret fra originalen 7. september 2014. (ubestemt)
↑ Diffie-Hellman-protokol, der bruger supersingular isogeni . (ubestemt)
↑ http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Arkivkopi dateret 15. december 2017 på Wayback Machine side 9
↑ PQCrypto 2006 officielle hjemmeside . Hentet 19. november 2014. Arkiveret fra originalen 26. oktober 2014. (ubestemt)
↑ officielle hjemmeside for PQCrypto 2008 (utilgængeligt link) . Hentet 19. november 2014. Arkiveret fra originalen 19. oktober 2014. (ubestemt)
↑ PQCrypto 2010 officielle hjemmeside . Dato for adgang: 19. november 2014. Arkiveret fra originalen 9. oktober 2014. (ubestemt)
↑ PQCrypto 2011 officielle hjemmeside . Hentet 19. november 2014. Arkiveret fra originalen 27. december 2014. (ubestemt)
↑ PQCrypto 2013 officielle hjemmeside . Hentet 19. november 2014. Arkiveret fra originalen 23. december 2014. (ubestemt)
↑ officielle hjemmeside for PQCrypto 2014 (utilgængeligt link) . Hentet 19. november 2014. Arkiveret fra originalen 26. oktober 2014. (ubestemt)

Links

PQCrypto, post-kvantekryptografikonferencen
Post- kvantekryptering (neopr.) . - Springer, 2008. - S. 245. - ISBN 978-3-540-88701-0 .
ETSI Quantum Security
NIST's Post-Quantum Crypto Project
PQCrypto-brug og -implementering

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher

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

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE