Postkvantkryptografi

Postkvantkryptografi är en del av kryptografi som förblir relevant även med tillkomsten av kvantdatorer och kvantattacker. Eftersom kvantdatorer avsevärt överträffar klassiska datorarkitekturer i beräkningshastighet för traditionella kryptografiska algoritmer , blir moderna kryptografiska system potentiellt sårbara för kryptografiska attacker . De flesta traditionella kryptosystem förlitar sig på heltalsfaktoriseringsproblem eller diskreta logaritmproblem , som lätt kan lösas på tillräckligt stora kvantdatorer med Shor-algoritmen [1] [2] . Många kryptografer utvecklar för närvarande algoritmer som är oberoende av kvantberäkning, det vill säga resistenta mot kvantattacker.

Det finns klassiska kryptosystem som förlitar sig på beräkningsmässigt komplexa problem och har ett antal betydande skillnader från ovanstående system, vilket gör dem mycket svårare att lösa. Dessa system är oberoende av kvantberäkning och anses därför vara kvantresistenta eller "postkvant"-kryptosystem.

Postkvantkryptografi skiljer sig i sin tur från kvantkryptografi , som handlar om kommunikationssäkerhetsmetoder baserade på kvantfysikens principer .

Algoritmer

Post-kvantkryptografiska konstruktioner kan rädda den kryptografiska världen från kvantattacker. Även om en kvantdator kommer att förstöra de flesta av de traditionella algoritmerna ( RSA , DSA , ECDSA ), kommer ultrasnabb datoranvändning inte helt att bli av med kryptografi, eftersom post-kvantkryptografi huvudsakligen fokuserar på fem olika tillvägagångssätt som löser problemet med kvantattacker [2] [3] .

Kryptografi baserad på hashfunktioner

Ett klassiskt exempel är Merkles publika nyckelsignatur baserad på ett hashträd. Ralph Charles Merkle föreslog denna digitala signaturalgoritm 1979 som ett intressant alternativ till digitala RSA- och DSA-signaturer. Den största nackdelen med Merkle-schemat är att för alla hashbaserade offentliga nycklar finns det en gräns för antalet signaturer som kan erhållas från motsvarande uppsättning privata nycklar. Detta faktum minskade intresset för signaturer av denna typ, tills det fanns ett behov av kryptografi som var resistent mot effekterna av kvantdatorer.

Kryptografi baserad på felkorrigeringskoder

Det är en av de mest lovande kandidaterna för post-kvantkryptosystem. Det klassiska exemplet är McEliece och Niederreiters krypteringsscheman .

Gitterbaserad kryptografi

Det klassiska exemplet på krypteringsscheman är Ring - Learning with Errors [4] [5] [6] [7] eller det äldre NTRU , GGH och Michiancio-kryptosystemet .

Kryptografi baserad på flerdimensionella kvadratiska system

Ett av de mest intressanta uppläggen är Jacques Patarins HFE - nyckelsignatur , som föreslogs av honom 1996 som en generalisering av Matsumoto och Imai [2] förslag .

Privat nyckelkryptering

Ett anmärkningsvärt exempel är Rijndael- chifferet , som föreslogs 1998, senare omdöpt till AES (Advanced Encryption Standard).

Kryptering med supersingular isogeni

Detta är en analog till Diffie-Hellman-protokollet , baserat på en vandring i en supersingular isogen graf, som tillåter två eller flera parter att få en delad hemlig nyckel med hjälp av en oskyddad kommunikationskanal [8] .

Exempel på kryptografiska attacker mot RSA [2]

1978 nämnde en artikel publicerad av utvecklarna av RSA-krypteringsalgoritmen med offentlig nyckel ( en akronym för Rivest, Shamir och Adleman) Richard Schreppels nya linjära sikt" -algoritm , som faktoriserade alla RSA - bitlängdsmoduler med enkla operationer. Således, för att denna algoritm ska kräva åtminstone enkla operationer, är det nödvändigt att välja längder åtminstone inte mindre än en bit. Eftersom det betyder att något konvergerar till vid , krävs en mer grundlig analys av den "linjära sikten"-hastigheten för att ta reda på den korrekta storleken vid finita . $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\till\infty$ $n$ $b$

1988 John Pollard en ny faktoriseringsalgoritm som kallas General Number Field Sieve Method . Denna algoritm faktoriserade RSA-enheten för bitdimension med hjälp av enkla operationer. Således krävs det att välja längder inte mindre än en bit, så att algoritmen behöver åtminstone enkla operationer. $n$ $\log _{2}n$ $2^{(1,9\dotso +o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{ 2/3}}$ $n$ ${\displaystyle (0.016\dotso +o(1))b^{3}/(\log _{2}b)^{2))$ $2^{b}$

Sedan 2008 använder de snabbaste faktoriseringsalgoritmerna för klassiska datorarkitekturer åtminstone enkla operationer. Det har skett en del förbättringar i värdena och i detaljerna , men det är inte svårt att gissa vilket som är optimalt, och att välja en modul ungefär lika med en bit i längden kommer att göra det möjligt att motstå alla möjliga attacker på klassiska datorer. $2^{(const+o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3} }$ $konst$ $o(1)$ $1/3$ $n$ $b^{3}$

1994 föreslog Peter Shor en algoritm som faktoriserade vilken bitdimensionell RSA -enhet som helst med hjälp av (mer exakt ) qubit-operationer på en kvantdator i qubit-storlek (och en liten mängd kompletterande beräkningar på en klassisk dator). Med Shors algoritm är det nödvändigt att åtminstone välja en modul med en bitstorlek inte mindre än en bit, vilket är ett för stort tal för något av våra intressen [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$

Praktiska tillämpningar av kryptografiska konstruktioner [2]

Det finns väldigt få exempel på algoritmer som är resistenta mot kvantattacker. Men trots den högre nivån av kryptografisk stabilitet kan postkvantalgoritmer inte ersätta moderna kryptosystem (RSA, DSA, ECDSA, etc.).

Överväg attacker på ett kryptosystem med offentlig nyckel, nämligen McEliece- krypteringsalgoritmen , som använder binära Goppa-koder . Inledningsvis presenterade Robert McAlice artiklar där långa koder knäcks i enkla operationer. Det krävs alltså att man väljer åtminstone lite för att algoritmen ska kräva åtminstone enkla operationer. Flera efterföljande arbeten har minskat antalet attackoperationer till , men betydligt färre om de är stora. Därför använder förbättrade attacker fortfarande enkla operationer. När det gäller kvantdatorer kommer deras användning bara att leda till en minskning av konstanten , vilket endast kommer att minska antalet operationer som krävs för att knäcka denna algoritm. $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$

Om McElieces krypteringssystem är så säkert, varför ersätter det inte RSA? Allt handlar om effektivitet - i synnerhet storleken på nyckeln. Den offentliga McEliece-nyckeln använder ungefär ≈ bitar, medan den offentliga RSA-nyckeln använder ungefär en bit. Om , så kommer lite för McEliece att vara mindre än lite för RSA, men verkliga säkerhetsnivåer som , tillåter RSA att ha en publik nyckel på flera tusen bitar, medan för McEliece närmar sig nyckelstorleken en miljon bitar. ${n^{2}}/4$ ${b^{2}}(\log _{2}b)^{2}$ ${\displaystyle (0{,}016\dots )b^{3}/(\log _{2}b)^{2))$ $b\till\infty$ $b^{{2+o(1)}}$ $b^{{3+o(1)}}$ $b=128$

PQCrypto Conference

Sedan 2006 har en serie konferenser dedikerade till postkvantkryptografi hållits.

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 till 2 december [13]
PQCrypto 2013. Limoges , Frankrike , 4-7 juni [14]
PQCrypto 2014. University of Waterloo , Kanada, 1-3 oktober [15]
PQCrypto 2016. Preliminär plan: Fukuoka , Japan, februari 2016

Se även

Anteckningar

↑ 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 till postkvantkryptering (neopr.) // (Introduktionskapitel till boken "Postkvantkryptering"). — 2009.
↑ Frågor och svar med post-kvantberäkningskrypteringsforskaren Jintai Ding , IEEE Spectrum (1 november 2008). Arkiverad från originalet den 8 oktober 2015. Hämtad 26 november 2014.
↑ Ryska lära sig med fel
↑ Peikert, Chris Lattice Kryptografi för Internet . IACR (2014). Hämtad 10 maj 2014. Arkiverad från originalet 12 maj 2014. (obestämd)
↑ Guneysu, Tim Praktisk gitterbaserad kryptografi: ett signaturschema för inbyggda system . INRIA (2012). Hämtad 12 maj 2014. Arkiverad från originalet 18 maj 2014. (obestämd)
↑ Zhang, jiang Autentiserat nyckelutbyte från Ideal Lattices . iacr.org . IACR (2014). Hämtad 7 september 2014. Arkiverad från originalet 7 september 2014. (obestämd)
↑ Diffie-Hellman-protokoll som använder supersingular isogeni . (obestämd)
↑ http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Arkivkopia daterad 15 december 2017 på Wayback Machine sida 9
↑ PQCrypto 2006 officiella webbplats . Hämtad 19 november 2014. Arkiverad från originalet 26 oktober 2014. (obestämd)
↑ officiella webbplats för PQCrypto 2008 (otillgänglig länk) . Hämtad 19 november 2014. Arkiverad från originalet 19 oktober 2014. (obestämd)
↑ PQCrypto 2010 officiella webbplats . Datum för åtkomst: 19 november 2014. Arkiverad från originalet den 9 oktober 2014. (obestämd)
↑ PQCrypto 2011 officiella webbplats . Hämtad 19 november 2014. Arkiverad från originalet 27 december 2014. (obestämd)
↑ PQCrypto 2013 officiella webbplats . Hämtad 19 november 2014. Arkiverad från originalet 23 december 2014. (obestämd)
↑ officiella webbplats för PQCrypto 2014 (otillgänglig länk) . Hämtad 19 november 2014. Arkiverad från originalet 26 oktober 2014. (obestämd)

Länkar

PQCrypto, post-kvantkryptografikonferensen
Postkvantkryptering (neopr.) . - Springer, 2008. - S. 245. - ISBN 978-3-540-88701-0 .
ETSI Quantum Security
NIST:s Post-Quantum Crypto Project
PQCrypto användning och distribution

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort

Hash-funktioner
generell mening	Adler-32 CRC Fletcher kontrollsumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hashträd jenkins hash hash summa
Kryptografisk	Stribog GOST R 34,11-94 Bälte BLAKE bmw CubeHash EKO edonkey2k FSB Fuga Grostl HAVAL Hamsi J H 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 Bubbelpool
Nyckelgenereringsfunktioner	bcrypt PBKDF2 kryptera Argon 2 Lyra2
Kontrollnummer ( jämförelse )	Kontrollera summan Verhouffs algoritm Månen algoritm Jävla algoritm Streckkod bankkonton bankkort ÄR I SNILS OKPO TENN OKATO ISBN OGRN och OGRNIP VIN
Hashes	Jämförelse av checknummer Autentiseringsprotokoll Streckkodsjämförelse Kryptografi Magnet länk Merkle signatur ed2k URNA