Calculatoare cuantice: Sfârșitul criptografiei?

Publicitate

Calcularea cuantică este una dintre acele tehnologii care sunt atât de arcane încât numele personajelor TV o dau atunci când vor să sune inteligent.

Calculul cuantic ca idee a existat de ceva vreme - posibilitatea teoretică a fost inițial introdusă de Yuri Manin și Richard Feynman în 1982. Cu toate acestea, în ultimii ani, domeniul s-a apropiat în mod îngrijorător de practic.

Companii precum Google și Microsoft, precum și agenții guvernamentale precum NSA au urmărit febril computerele cuantice de ani buni. O companie numită D-Wave a produs și vinde dispozitive care (deși nu sunt computere adecvate și pot execută doar câțiva algoritmi) exploatează proprietățile cuantice și sunt un alt pas incremental pe drumul către a complet Turing-completă Care este testul Turing și va fi vreodată bătut?Testul de Turing este menit să determine dacă mașinile cred. Programul Eugene Goostman a trecut cu adevărat testul Turing sau creatorii au trișat pur și simplu? Citeste mai mult mașină cuantică

Nu pare nejustificat să spunem că ar putea apărea progrese care să permită construirea primului computer cuantică pe scară largă într-un deceniu.

Atunci de ce tot interesul? De ce ar trebui să-ți pese? Calculatoarele devin mai rapide tot timpul Care este Legea lui Moore și ce are de-a face cu tine? [FaceUseOf Explică]Norocul nu are nicio legătură cu Legea lui Moore. Dacă aceasta este asocierea pe care o aveai, o confundați cu Legea lui Murphy. Cu toate acestea, nu ai fost departe pentru că Legea lui Moore și Legea lui Murphy ... Citeste mai mult - ce este atât de special în ceea ce privește computerele cuantice?

Pentru a explica de ce aceste mașini sunt atât de importante, va trebui să facem un pas înapoi și să explorăm exact ce sunt calculatoarele cuantice și de ce funcționează. Pentru a începe, să vorbim despre un concept numit „complexitate runtime”.

Ce este complexitatea Runtime?

Una dintre marile surprize din primele zile ale informaticii a fost descoperirea că, dacă ai un computer care rezolvă o problemă de o anumită dimensiune într-o anumită perioadă de timp, dublarea vitezei computerului nu-l lasă neapărat să rezolve problemele de două ori mare.

Unii algoritmi cresc în timpul total de execuție foarte, foarte repede pe măsură ce dimensiunea problemei crește - unii algoritmi pot fi completate rapid dat 100 de puncte de date, dar completarea algoritmului dat 1000 de puncte de date ar necesita un computer cu dimensiunea Pământului care rulează pentru un miliard ani. Complexitatea de rulare este o formalizare a acestei idei: analizează curba cât de rapid crește complexitatea unei probleme și folosește forma curbei respective pentru a clasifica algoritmul.

În general, aceste clase de dificultate sunt exprimate ca funcții. Un algoritm care devine proporțional mai greu atunci când datele își creează funcționarea în creșteri (cum ar fi o simplă funcție de numărare) se spune că este o funcție cu o complexitate de rulare de „n“ (ca în, este nevoie n unități de timp pentru procesare n puncte de date).

În mod alternativ, s-ar putea numi „liniară”, deoarece atunci când o graficezi, obții o linie dreaptă. Alte funcții ar putea fi n ^ 2 sau 2 ^ n sau n! (n factorial). Acestea sunt polinomiale și exponențiale. În ultimele două cazuri, cele exponențiale cresc atât de repede încât în ​​aproape toate cazurile nu pot fi rezolvate pentru nimic, cu excepția unor exemple foarte banale.

Complexitatea Runtime și criptografia

Dacă auziți aceste lucruri pentru prima dată și sună lipsit de sens și arcane, să încercăm să fundamentăm această discuție. Complexitatea de rulare este esențială pentru criptografie, care se bazează pe simplificarea mult mai ușor pentru persoanele care știu o cheie secretă decât pentru cei care nu. Într-o schemă criptografică ideală, decriptarea ar trebui să fie liniară dacă aveți cheia și 2 ^ k (unde k este numărul de biți din cheie) dacă nu.

Cu alte cuvinte, cel mai bun algoritm pentru decriptarea mesajului fără cheie ar trebui să fie pur și simplu ghicirea unor chei posibile, ceea ce este intractabil pentru taste doar doar câteva sute de biți.

Pentru criptografia cu cheie simetrică (în care cele două părți au șansa de a schimba un secret în siguranță înainte de a începe comunicarea) este destul de ușor. Pentru criptografia asimetrică, este mai greu.

Criptografia asimetrică, în care tastele de criptare și decriptare sunt diferite și nu pot fi ușor calculate una de cealaltă, este mult mai grea structură de implementat decât criptografie simetrică, dar este și mult mai puternică: criptă asimetrică vă permite să aveți conversații private, chiar și peste linii! De asemenea, vă permite să creați „semnături digitale” care să vă permită să verificați de la cine a venit un mesaj și că nu a fost modificat.

Acestea sunt instrumente puternice și constituie fundamentul confidențialității moderne: fără criptografie asimetrică, utilizatorii dispozitivelor electronice nu ar avea nicio protecție fiabilă împotriva ochilor induriști.

Deoarece criptografia asimetrică este mai greu de construit decât simetrica, schemele standard de criptare care sunt utilizate astăzi nu sunt la fel de puternice așa cum ar putea fi: cel mai obișnuit standard de criptare, RSA, poate fi fisurat dacă puteți găsi eficient factorii primi ai unui număr. Vestea bună este că aceasta este o problemă foarte grea.

Cel mai cunoscut algoritm pentru factorizarea numerelor mari în primele componentelor lor se numește sita de câmpuri cu număr general și are o complexitate de rulare care crește puțin mai lent decât 2 ^ n. În consecință, cheile trebuie să fie de aproximativ zece ori mai lungi pentru a oferi o securitate similară, ceea ce oamenii tolerează în mod normal ca cost de afaceri. Vestea proastă este că întregul câmp de joc se schimbă atunci când calculatoarele cuantice sunt aruncate în mix.

Calculatoare cuantice: Schimbarea jocului Crypto

Calculatoarele cuantice funcționează deoarece pot avea mai multe stări interne în același timp, printr-un fenomen cuantic numit „superpoziție”. Asta înseamnă că pot ataca diferite părți ale unei probleme simultan, împărțind versiunile posibile ale universului. De asemenea, pot fi configurate astfel încât ramurile care rezolvă problema să se lichideze cu cea mai mare amplitudine, astfel încât atunci când deschideți caseta de pe Pisica lui Schrodinger, versiunea stării interne cu care este cel mai probabil să fiți prezentată este o pisică cu aspect de contrabandă care deține un decriptat mesaj.

Pentru mai multe informații despre computerele cuantice, consultați articolul nostru recent pe această temă Cum funcționează calculatoarele optice și cuantice?Epoca Exascale vine. Știți cum funcționează calculatoarele optice și cuantice și aceste noi tehnologii vor deveni viitorul nostru? Citeste mai mult !

Acest aspect este că computerele cuantice nu sunt doar liniar mai rapide, așa cum sunt computerele normale: obținerea a două sau zece sau o sută de ori mai repede nu ajută prea mult atunci când vine vorba de criptografie convențională, încât sute de miliarde de ori sunt prea lent pentru procesare. Calculatoarele cuantice acceptă algoritmi care au complexități de timp de execuție mai mici decât este posibil. Acest lucru face ca computerele cuantice să fie fundamental diferite de alte tehnologii de calcul viitoare, cum ar fi calcul grafen și memrister Ultima tehnologie computerizată pe care trebuie să o vedeți pentru a credeConsultați unele dintre cele mai noi tehnologii informatice, care vor fi transformate în lumea electronică și a computerelor în următorii câțiva ani. Citeste mai mult .

Pentru un exemplu concret, algoritmul lui Shor, care poate fi executat doar pe un computer cuantic, poate determina un număr mare de log (n) ^ 3 timpul, care este drastic mai bun decât cel mai bun atac clasic. Folosind sita de câmp cu număr general pentru a factoriza un număr cu 2048 biți, este nevoie de aproximativ 10 ^ 41 unități de timp, ceea ce înseamnă mai mult de un trilion de trilioane de trilioane. Folosind algoritmul lui Shor, aceeași problemă durează doar aproximativ 1000 de unități de timp.

Efectul devine mai accentuat cu cât tastele sunt mai lungi. Aceasta este puterea calculatoarelor cuantice.

Nu mă înțelegeți greșit - calculatoarele cuantice au o mulțime de utilizări potențiale non-rele. Calculatoarele cuantice pot rezolva eficient problema vânzătorului în călătorie, permițând cercetătorilor să construiască rețele de transport mai eficiente și să proiecteze circuite mai bune. Calculatoarele cuantice au deja utilizări puternice în inteligența artificială.

Acestea fiind spuse, rolul lor în criptografie va fi catastrofal. Tehnologiile de criptare care permit lumii noastre să funcționeze depind de problema de factorizare integră care este greu de rezolvat. RSA și schemele de criptare conexe sunt ceea ce vă permite să aveți încredere că sunteți pe site-ul web potrivit, în fișierele pe care le aveți descărcarea nu este plină de malware și că oamenii nu spionează pe navigarea dvs. pe Internet (dacă utilizați Tor).

Criptografia păstrează contul dvs. bancar în siguranță și asigură infrastructura nucleară a lumii. Când computerele cuantice devin practice, toată tehnologia respectivă nu mai funcționează. Prima organizație care a dezvoltat un computer cuantic, dacă lumea încă mai lucrează la tehnologiile pe care le folosim astăzi, va fi într-o poziție înfricoșător de puternică.

Deci, este inevitabilă apocalipsa cuantică? Există ceva ce putem face în acest sens? După cum se dovedește... da.

Criptografia post-cuantică

Există mai multe clase de algoritmi de criptare care, din câte știm, nu sunt semnificativ mai rapide de rezolvat pe un computer cuantic. Acestea sunt cunoscute colectiv sub numele de criptografie post-cuantică și oferă o speranță că lumea poate trece la criptosisteme care vor rămâne sigure într-o lume de criptare cuantică.

Candidații promițători includ criptarea bazată pe zăbrele, cum ar fi Ring-Learning With Error, care își derivă securitatea dintr-un complex demonstrabil problemă de învățare a mașinilor și criptografie multivariată, care derivă securitatea sa din dificultatea de a rezolva sisteme foarte mari de simple ecuații. Puteți citi mai multe despre acest subiect pe site Articolul Wikipedia. Atenție: o mulțime de aceste lucruri sunt complexe și este posibil să descoperiți că fondul dvs. de matematică trebuie îmbunătățit considerabil înainte de a putea săpa cu adevărat în detalii.

A lua multe din acest lucru este că criptoschemele post-cuantice sunt foarte misto, dar și foarte tinere. Au nevoie de mai multă muncă pentru a fi eficiente și practice, precum și pentru a demonstra că sunt sigure. Motivul pentru care suntem capabili să avem încredere în criptosisteme este pentru că le-am aruncat suficient de multe gene genial paranoice din punct de vedere clinic că orice deficiențe evidente ar fi fost descoperite până acum, iar cercetătorii au dovedit diverse caracteristici care le fac puternic.

Criptografia modernă depinde de lumină ca dezinfectant, iar majoritatea schemelor criptografice post-cuantice sunt pur și simplu prea noi pentru a avea încredere în securitatea mondială. Cu toate acestea, acolo ajung și, cu puțin noroc și ceva pregătire, experții în securitate pot finaliza comutarea înainte ca primul computer cuantic să vină online.

Dacă nu reușesc, însă, consecințele pot fi grave. Gândul că oricine are acest tip de putere este neliniștitor, chiar dacă ești optimist cu privire la intențiile lor. Întrebarea cine dezvoltă pentru prima dată un computer cuantic care funcționează este una pe care toată lumea ar trebui să o privească cu atenție pe măsură ce trecem în următorul deceniu.

Ești preocupat de insecuritatea criptografiei față de computerele cuantice? Ce faceți? Partajează-ți gândurile în comentariile de mai jos!

Credite imagine: Orb binar Via Shutterstock