Criptografia post-cuantică

Criptografia post-cuantică este o parte a criptografiei care rămâne relevantă chiar și odată cu apariția computerelor cuantice și a atacurilor cuantice. Deoarece computerele cuantice depășesc semnificativ arhitecturile clasice de computer în ceea ce privește viteza de calcul a algoritmilor criptografici tradiționali , sistemele criptografice moderne devin potențial vulnerabile la atacurile criptografice . Cele mai multe criptosisteme tradiționale se bazează pe probleme de factorizare întregi sau probleme de logaritm discret , care vor fi ușor de rezolvat pe computere cuantice suficient de mari folosind algoritmul Shor [1] [2] . Mulți criptografi dezvoltă în prezent algoritmi care sunt independenți de calculul cuantic, adică rezistenți la atacurile cuantice.

Există criptosisteme clasice care se bazează pe probleme complexe din punct de vedere computațional și au o serie de diferențe semnificative față de sistemele de mai sus, ceea ce le face mult mai dificil de rezolvat. Aceste sisteme sunt independente de calculul cuantic și, prin urmare, sunt considerate criptosisteme rezistente la cuanți sau „post-cuantice”.

Criptografia post-cuantică, la rândul său, diferă de criptografia cuantică , care se ocupă de metodele de securitate a comunicațiilor bazate pe principiile fizicii cuantice .

Algoritmi

Construcțiile criptografice post-cuantice sunt capabile să salveze lumea criptografică de atacurile cuantice. Deși un computer cuantic va distruge majoritatea algoritmilor tradiționali ( RSA , DSA , ECDSA ), calculul ultra-rapid nu va scăpa complet de criptografie, deoarece criptografia post-cuantică se concentrează în principal pe cinci abordări diferite care rezolvă problema atacurilor cuantice. [2] [3] .

Criptografie bazată pe funcții hash

Un exemplu clasic este semnătura cheii publice Merkle bazată pe un arbore hash. Ralph Charles Merkle a propus acest algoritm de semnătură digitală în 1979 ca o alternativă interesantă la semnăturile digitale RSA și DSA. Principalul dezavantaj al schemei Merkle este că, pentru orice cheie publică bazată pe hash , există o limită a numărului de semnături care pot fi obținute din setul corespunzător de chei private. Acest fapt a redus nivelul de interes pentru semnăturile de acest tip, până când a fost nevoie de o criptografie rezistentă la efectele calculatoarelor cuantice.

Criptografie bazată pe coduri de corectare a erorilor

Este unul dintre cei mai promițători candidați pentru criptosisteme post-cuantice. Exemplul clasic este schemele de criptare McEliece și Niederreiter .

Criptografia bazată pe zăbrele

Exemplul clasic de scheme de criptare sunt Ring - Learning with Errors [4] [5] [6] [7] sau mai vechi NTRU , GGH și criptosistemul Michiancio .

Criptografie bazată pe sisteme pătratice multidimensionale

Una dintre cele mai interesante scheme este semnătura cheii publice HFE a lui Jacques Patarin , propusă de el în 1996 ca o generalizare a propunerilor Matsumoto și Imai [2] .

Criptare cheie privată

Un exemplu notabil este cifrul Rijndael , propus în 1998, redenumit ulterior AES (Advanced Encryption Standard).

Criptare folosind izogenie supersingulară

Acesta este un analog al protocolului Diffie-Hellman , bazat pe o plimbare într-un graf izogenic suprasingular, care permite două sau mai multe părți să obțină o cheie secretă partajată folosind un canal de comunicare neprotejat [8] .

Exemple de atacuri criptografice asupra RSA [2]

În 1978, o lucrare publicată de dezvoltatorii algoritmului criptografic cu cheie publică RSA ( un acronim pentru Rivest, Shamir și Adleman) a menționat noul algoritm liniar sieve” al lui Richard Schreppel , care factoriza orice modul de lungime a biților RSA folosind operații simple. Astfel, pentru ca acest algoritm să necesite operații cel puțin simple, este necesar să alegeți lungimi cel puțin nu mai mici de un bit. Deoarece înseamnă că ceva converge la , este necesară o analiză mai amănunțită a vitezei „sită liniară” pentru a afla dimensiunea corectă la finit . $n$ $[\log _{2}n]+1$ $2^{(1+o(1))(\log _{2}n)^{1/2}(\log _{2}\log _{2}n)^{1/2} }$ $2^{b}$ $n$ $(0,5+o(1))b^{2}/{\log _{2}b)$ $0{,}5+o(1)$ $0{,}5$ $b\to\infty$ $n$ $b$

În 1988, John Pollard a un nou algoritm de factorizare numit General Number Field Sieve Method . Acest algoritm a factorizat unitatea RSA de dimensiune de biți folosind operații simple. Astfel, este necesar să alegeți lungimi nu mai mici de un bit, astfel încât algoritmul să aibă nevoie de operații cel puțin simple. $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}$

Din 2008, cei mai rapidi algoritmi de factorizare pentru arhitecturile clasice de computere folosesc cel puțin operații simple. Au existat unele îmbunătățiri în ceea ce privește valorile și detaliile , dar nu este greu de ghicit care este optim și că alegerea unui modul aproximativ egal cu un pic în lungime va face posibilă rezistența tuturor atacurilor posibile asupra computerelor clasice. $2^{(const+o(1))(\log _{2}n)^{1/3}(\log _{2}\log _{2}n)^{2/3} }$ $const$ $o(1)$ $1/3$ $n$ $b^{3}$

În 1994, Peter Shor a propus un algoritm care factorizează orice unitate RSA bidimensională folosind (mai precis ) operații cu qubit pe un computer cuantic de dimensiunea qubit (și o cantitate mică de calcule auxiliare pe un computer clasic). Folosind algoritmul lui Shor, este necesar să alegem cel puțin un modul cu o dimensiune de bit nu mai mică de un bit, care este un număr prea mare pentru oricare dintre interesele noastre [9] . $n$ $b=\log _{2}n$ $b^{{2+o(1)}}$ $b^{2}\cdot \log(b)\cdot \log(\log(b))$ $2\cdot b^{1+o(1))$ $n$ $2^{{(0,5+o(1))b}}$ $b$

Aplicații practice ale constructelor criptografice [2]

Există foarte puține exemple de algoritmi care sunt rezistenți la atacurile cuantice. Dar, în ciuda nivelului mai mare de stabilitate criptografică, algoritmii post-cuantici nu sunt capabili să înlocuiască criptosistemele moderne (RSA, DSA, ECDSA etc.).

Luați în considerare atacurile asupra unui sistem criptografic cu cheie publică, și anume algoritmul de criptare McEliece , care utilizează coduri Goppa binare . Inițial , Robert McAlice a prezentat lucrări în care codurile lungi sunt sparte în operațiuni simple. Astfel, este necesar să alegeți cel puțin un bit pentru ca algoritmul să necesite operații cel puțin simple. Câteva lucrări ulterioare au redus numărul de operațiuni de atac la , dar semnificativ mai puțin dacă este mare. Prin urmare, atacurile îmbunătățite folosesc încă operațiuni simple. În ceea ce privește calculatoarele cuantice, utilizarea lor va duce doar la o scădere a constantei , ceea ce va reduce doar puțin numărul de operațiuni necesare pentru a sparge acest 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}$ $0{,}5n/{\log _{2}n)$ $n$ $2^{(0,5+o(1))n/{\log _{2}n))$ $0,5$

Dacă sistemul de criptare McEliece este atât de sigur, de ce nu înlocuiește RSA? Totul ține de eficiență - în special, de dimensiunea cheii. Cheia publică McEliece folosește aproximativ ≈ biți, în timp ce cheia publică RSA folosește aproximativ un bit. Dacă , atunci un pic pentru McEliece va fi mai puțin decât un pic pentru RSA, dar nivelurile reale de securitate, cum ar fi , permit RSA să aibă o cheie publică de câteva mii de biți, în timp ce pentru McEliece, dimensiunea cheii se apropie de un milion de biți. ${n^{2}}/4$ ${b^{2}}(\log _{2}b)^{2}$ $(0{,}016\dots )b^{3}/(\log _{2}b)^{2}$ $b\to\infty$ $b^{{2+o(1)}}$ $b^{{3+o(1)}}$ $b=128$

Conferința PQCrypto

Din 2006, au avut loc o serie de conferințe dedicate criptografiei post-cuantice.

PQCrypto 2006. KU Leuven , Belgia , 23-26 mai [10]
PQCrypto 2008. Universitatea din Cincinnati , SUA , 17-19 octombrie [11]
PQCrypto 2010. Darmstadt , Germania , 25-28 mai [12]
PQCrypto 2011. Taipei , Taiwan, 29 noiembrie - 2 decembrie [13]
PQCrypto 2013. Limoges , Franța , 4-7 iunie [14]
PQCrypto 2014. Universitatea din Waterloo , Canada, 1-3 octombrie [15]
PQCrypto 2016. Plan preliminar: Fukuoka , Japonia, februarie 2016

Vezi și

Note

^ Peter Shor ( 30.08.1995), Algoritmi polinomial-timp pentru factorizarea primelor și logaritmii discreti pe un computer cuantic, arΧiv : quant-ph/9508027 .
↑ 1 2 3 4 5 Daniel J. Bernstein . Introducere în criptografia post-cuantică (neopr.) // (Capitol introductiv la cartea „Criptografia post-cuantică”). — 2009.
↑ Întrebări și răspunsuri cu cercetător în criptografia post-cuantică Jintai Ding , IEEE Spectrum (1 noiembrie 2008). Arhivat din original pe 8 octombrie 2015. Preluat la 26 noiembrie 2014.
↑ rusă învăţarea cu erori
^ Peikert , Chris Lattice Criptografie pentru Internet . IACR (2014). Preluat la 10 mai 2014. Arhivat din original la 12 mai 2014. (nedefinit)
↑ Guneysu, Tim Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems . INRIA (2012). Preluat la 12 mai 2014. Arhivat din original la 18 mai 2014. (nedefinit)
↑ Zhang, jiang Schimb de chei autentificat de la Ideal Lattices . iacr.org . IACR (2014). Consultat la 7 septembrie 2014. Arhivat din original pe 7 septembrie 2014. (nedefinit)
↑ Protocolul Diffie-Hellman folosind izogenia supersingulară . (nedefinit)
↑ http://crypto.rsuh.ru/papers/bogdanov-kizhvatov-quantum.pdf Copie de arhivă din 15 decembrie 2017 pe Wayback Machine pagina 9
↑ Site-ul oficial al PQCrypto 2006 . Consultat la 19 noiembrie 2014. Arhivat din original la 26 octombrie 2014. (nedefinit)
↑ site-ul oficial al PQCrypto 2008 (link inaccesibil) . Consultat la 19 noiembrie 2014. Arhivat din original pe 19 octombrie 2014. (nedefinit)
↑ Site-ul oficial al PQCrypto 2010 . Data accesului: 19 noiembrie 2014. Arhivat din original pe 9 octombrie 2014. (nedefinit)
↑ Site-ul oficial al PQCrypto 2011 . Consultat la 19 noiembrie 2014. Arhivat din original pe 27 decembrie 2014. (nedefinit)
↑ Site-ul oficial al PQCrypto 2013 . Consultat la 19 noiembrie 2014. Arhivat din original pe 23 decembrie 2014. (nedefinit)
↑ site-ul oficial al PQCrypto 2014 (link inaccesibil) . Consultat la 19 noiembrie 2014. Arhivat din original la 26 octombrie 2014. (nedefinit)

Link -uri

PQCrypto, conferința post-criptografie cuantică
Criptografie post-cuantică (neopr.) . - Springer, 2008. - P. 245. - ISBN 978-3-540-88701-0 .
ETSI Quantum Security
Proiectul Crypto Post-Quantum al NIST
Utilizarea și implementarea PQCrypto

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher

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

Funcții hash
scop general	Adler-32 CRC Suma de control Fletcher FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash suma hash
Criptografic	Stribog GOST R 34.11-94 Centura BLAKE BMW CubeHash ECOU edonkey2k FSB Fugă 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 Piele Snefru Tigru Vârtej
Funcții de generare a cheilor	bcrypt PBKDF2 cripta Argon2 Lyra2
Numărul de verificare ( comparație )	Verificați suma Algoritmul lui Verhouff Algoritmul lunii Algoritmul Damm Cod de bare conturi bancare carduri bancare ESTE IN SNILS OKPO STANIU OKATO ISBN OGRN și OGRNIP VIN
Hashes	Comparația numerelor de cec Protocoale de autentificare Comparația codurilor de bare Criptografie Legătură magnetică Semnătura Merkle ed2k URNĂ