Introducere
În 1994, informaticianul Peter Shor a descoperit că, dacă computerele cuantice ar fi inventate vreodată, acestea ar decima o mare parte din infrastructura folosită pentru a proteja informațiile partajate online. Această posibilitate înspăimântătoare i-a făcut pe cercetători să se străduiască să producă noi scheme de criptare „post-cuantică”, pentru a salva cât de multe informații pot să nu cadă în mâinile hackerilor cuantici.
La începutul acestui an, Institutul Național de Standarde și Tehnologie dezvăluit patru finaliști în căutarea unui standard de criptografie post-cuantică. Trei dintre ei folosesc „criptografia latice” - o schemă inspirată de grile, aranjamente regulate de puncte în spațiu.
Criptografia latice și alte posibilități post-cuantice diferă de standardele actuale în moduri cruciale. Dar toate se bazează pe asimetria matematică. Securitatea multor sisteme de criptografie actuale se bazează pe multiplicare și factoring: orice computer poate înmulți rapid două numere, dar ar putea dura secole pentru a factora un număr criptografic mare în constituenții săi principali. Această asimetrie face secretele ușor de codificat, dar greu de decodat.
Ceea ce a dezvăluit Shor în algoritmul său din 1994 a fost că o particularitate de factoring îl face vulnerabil la atacul computerelor cuantice. „Este un lucru foarte specific, special pe care îl poate face computerul cuantic”, a spus Katherine Stange, un matematician la Universitatea din Colorado, Boulder. Deci, după Shor, criptografii au avut o nouă slujbă: găsiți un nou set de operații matematice care sunt ușor de făcut, dar aproape imposibil de anulat.
Criptografia lattice este una dintre cele mai reușite încercări de până acum. Dezvoltat inițial în anii 1990, se bazează pe dificultatea ingineriei inverse a sumelor de puncte.
Iată o modalitate de a descrie criptografia cu zăbrele: Imaginați-vă că prietenul dvs. are o rețea, care este doar o grămadă de puncte într-un model obișnuit, care se repetă pe tot planul. Prietenul tău vrea să numești 10 dintre aceste puncte. Dar el este dificil și nu va desena întreaga zăbrele. În schimb, el enumeră doar două puncte - primul cu un x-valoarea 101 si a y-valoarea 19, celălalt cu coordonatele [235, 44].
Din fericire, este ușor să găsești puncte noi pe o rețea, deoarece atunci când adunați și scădeți oricare două puncte de pe o rețea, obțineți un al treilea punct în aceeași rețea. Deci, tot ce trebuie să faci este să adunăm punctele pe care ți le-a dat prietenul tău sau să le înmulți cu numere întregi și apoi să le adunăm sau o combinație a celor două. Fă acest lucru în opt moduri diferite și vei putea răspunde la întrebarea prietenului tău.
Dar prietenul tău încă nu este mulțumit. El vă oferă aceleași două puncte de plecare și apoi vă întreabă dacă punctul [2, 1] se află pe aceeași rețea. Pentru a răspunde corect la această întrebare, trebuie să găsiți combinația dintre [101, 19] și [235, 44] care produce [2, 1]. Această problemă este mult mai grea decât prima și probabil vei ajunge să ghicești și să verifici pentru a obține răspunsul.* Această asimetrie este ceea ce stă la baza criptografiei în zăbrele.
Dacă doriți să folosiți criptografie cu zăbrele pentru a partaja informații, ați face următoarele. Imaginează-ți că un prieten (unul mai drăguț!) dorește să-ți trimită un mesaj sigur. Începi cu o grilă pătrată de numere. Să presupunem că are două rânduri și două coloane și arată astfel:
Acum vii cu o „cheie” privată pe care doar tu o cunoști. În acest exemplu, să presupunem că cheia dvs. privată este doar două numere secrete: 3 și -2. Înmulțiți numerele din prima coloană cu 3, iar pe cele din a doua coloană cu -2. Adunați rezultatele din fiecare rând pentru a obține o a treia coloană cu două intrări.
Lipiți noua coloană la capătul grilei. Această nouă grilă cu trei coloane este cheia dvs. publică. Distribuie-l liber!
(Un scenariu din lumea reală va fi puțin mai complicat. Pentru a împiedica hackerii să-ți decodifice cheia privată, trebuie să adaugi un pic de zgomot aleatoriu în ultima coloană. Dar aici vom ignora acest pas din motive de simplitate. )
Acum prietenul tău va folosi cheia publică pentru a-ți trimite un mesaj. Se gândește la două numere secrete ale ei: 2 și 0. Înmulțește numerele din primul rând cu 2 și pe cele din al doilea rând cu 0. Apoi adună rezultatele din fiecare coloană pentru a obține un al treilea rând.
Acum atașează noul rând în partea de jos a rețelei și ți-l trimite înapoi. (Din nou, într-un sistem real, ar trebui să adauge ceva zgomot rândului ei.)
Acum vei citi mesajul. Pentru a face acest lucru, verificați dacă ultimul rând al prietenului dvs. este corect. Aplicați propria cheie privată la primele două intrări ale rândului ei. Rezultatul ar trebui să se potrivească cu ultima intrare.
Prietenul tău poate alege, de asemenea, să-ți trimită un rând cu un număr greșit în ultima coloană. Ea știe că acest număr nu se va potrivi cu calculele tale.
Dacă prietenul tău trimite un rând în care ultimul număr este corect, vei interpreta asta ca un 0. Dacă ea trimite un rând în care numărul este incorect, îl vei interpreta ca un 1. Prin urmare, rândul codifică un singur bit: fie 0, fie 1.
Rețineți că un atacator extern nu va avea acces nici la cheia dvs. privată, nici la cea a prietenului dvs. Fără acestea, atacatorul nu va avea idee dacă numărul final este corect sau nu.
În practică, ați dori să trimiteți mesaje mai lungi de un bit. Deci, oamenii care doresc să primească, să zicem, un mesaj pe 100 de biți vor genera 100 de coloane noi în loc de doar una. Apoi, expeditorul mesajului va crea un singur rând nou, modificând ultimele 100 de intrări pentru a codifica fie un 0, fie un 1 pentru fiecare intrare.
Dacă criptografia lattice este implementată efectiv, aceasta va avea nenumărate nuanțe care nu sunt acoperite în acest scenariu. De exemplu, dacă doriți ca mesajul să fie cu adevărat protejat de privirile indiscrete, matricea trebuie să aibă un număr de neconceput de intrări, ceea ce face ca totul să fie atât de greu de manevrat încât nu merită să fie folosit. Pentru a evita acest lucru, cercetătorii folosesc matrici cu simetrii utile care pot reduce numărul de parametri. Dincolo de asta, există o suită întreagă de ajustări care pot fi aplicate problemei în sine, modului în care sunt încorporate erorile și multe altele.
Desigur, este întotdeauna posibil ca cineva să găsească un defect fatal în criptografia cu zăbrele, la fel cum a făcut Shor pentru factoring. Nu există nicio asigurare că o anumită schemă criptografică va funcționa în fața oricărui posibil atac. Criptografia funcționează până când este spartă. Într-adevăr, la începutul acestei veri o schemă promițătoare de criptografie post-cuantică a fost spartă folosind nu un computer cuantic, ci un laptop obișnuit. Pentru Stange, întregul proiect creează un paradox inconfortabil: „Ceea ce mi se pare atât de uimitor la criptografie este că am construit această infrastructură pentru rasa umană pe convingerea fermă că capacitatea noastră ca oameni este limitată”, a spus ea. „Este atât de înapoiat.”
*: Răspunsul, dacă ești curios, este 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [înapoi la articol]
