Criptografie #2: Securitatea și geometria28 min read

Securitatea cibernetică bazată pe numere prime are avantajul vechimii, deci al experienței: algoritmii sunt cercetați, auditați și revalidați periodic. Dar viitorul computațional și mai ales cel cuantic impun o regândire a uneltelor criptografiei.

Când te gândești la comunicare codificată, coduri și criptare, imaginea cea mai populară este de tip James Bond: secrete bine păzite, cu proceduri pe care cei implicați nu le divulgă nici sub cele mai crunte amenințări. Realitatea, însă, nu mai face din metodele criptografice un secret. Dimpotrivă, criptografia cu chei publice este principalul domeniu de cercetare și aplicare, la cele mai înalte niveluri academice, tehnologice și industriale.

Acum peste cincizeci de ani, securizarea informațiilor necesita chei secrete. Doar câteva persoane, implicate și responsabile direct cunoșteau metoda, care, în mâinile unor atacatori, ar fi însemnat furtul unor informații prețioase. 

Astfel de metode au dezavantaje evidente, dintre care cel mai important este că pun o țintă pe capul celor responsabili. Atacatorii — hackerii, în termeni moderni — puteau folosi orice metodă, de la pașnica inginerie socială sau manipulare, până la tortură, pentru a afla algoritmul de securizare. Apoi, lucrurile erau simple, pentru că procedura de criptare era simetrică, adică aceeași metodă care a funcționat pentru criptare putea fi folosită și pentru decriptare. 

Inovațiile în tehnologie, creșterea accelerată a puterii de calcul, dar și colaborarea tot mai strânsă între matematicieni și informaticieni au dus cercetările într-o altă direcție, mai complicată și mai sigură. Așa s-a născut criptarea cu chei publice, mai întâi prin americanii Whitfield Diffie, Martin Hellman și Ralph Merkle, care în 1976 au propus un algoritm matematic prin care două persoane pot obține independent aceeași cheie de comunicare, cu care își pot securiza apoi interacțiunea. 

Alice și Bob (numele standard ale actorilor în criptografie) își aleg câte un număr, independent, care este singurul secret din procedură. Apoi, cei doi convin asupra altor două numere, pe care le pot face publice, și aplică operații matematice (de asemenea publice) prin care, deși au pornit cu numere diferite, ajung la un rezultat comun. Acesta se numește cheia comună (shared key), pe care o folosesc apoi pentru securizarea canalului de comunicare.

Uite un exemplu concret: când accesezi un site web, unul dintre pașii până la conexiune se numește TLS handshake, un fel de „negociere“ în care computerul tău (numit client) și cel care-ți servește site-ul dorit (numit, previzibil, server) fac alegerile și operațiile din algoritmul Diffie-Hellman. Când termină, „își dau mâna“, convenind asupra comunicării criptate de atunci încolo. Astfel de aplicații arată, printre altele, și cât de importantă este eficiența acestor algoritmi. Când ai așteptat ultima dată mai mult de una-două secunde pentru afișarea unui site?

Noutatea în abordarea Diffie, Hellman & Merkle a fost că procedura nu mai trebuia să fie păstrată în secret – metoda a devenit publică și toți cei interesați o puteau afla. Chiar și cheia comună putea fi interceptată sau chiar publicată, fără teama de a compromite securitatea. 

Cum de mai rămânea sigură o astfel de procedură? Motivele sunt pur matematice: algoritmul Diffie-Hellman, cum a ajuns să fie cunoscut (Merkle a contribuit la prototip), se bazează pe operații practic imposibil de inversat. Este vorba mai ales de exponențiere sau ridicarea la putere, care, împreună cu procedura inversă, logaritmul, sunt foarte scumpe din punct de vedere computațional. 

Altfel spus, teoria matematică arată că operațiile sunt perfect posibile, dar rezultatele intermediare și cel final se obțin prin calcule care încetinesc majoritatea computerelor dacă se folosesc numere suficient de mari. La nivelul puterii de calcul din anul 2025, numerele între 600 și 1000 de cifre sunt considerate potrivite. Așadar, singurele secrete al procedurii, numerele individuale cu care au pornit Alice și Bob, sunt ascunse în spatele unor etape practic imposibil de inversat și care nu mai sunt un secret.

Algoritmul Diffie-Hellman a deschis un nou domeniu de cercetare teoretică și implementare. A fost urmat de RSA, introdus de Ron Rivest, Adi Shamir și Leonard Adleman la doar un an, în 1977, iar domeniul criptării cu chei publice a devenit standardul în industrie și cercetare.

Deși se bazează pe operații sofisticate cu numere prime, toate aceste criptosisteme au slăbiciuni cunoscute. Avantajul cercetărilor publice este că oricine poate inspecta fundamentul teoretic, pe lîngă auditurile de specialitate asupra diverselor implementări. Mitigarea problemelor s-a făcut prin combinații între teorie și practică: numerele cu care se lucrează au devenit tot mai mari, dar astfel încît timpul de așteptare pentru realizarea criptării să nu crească nerezonabil.

Totuși, când manipularea atinge cote alarmante și cu ajutorul inteligenței artificiale, iar puterea de calcul face salturi de neînchipuit prin computere cuantice, algoritmii de criptare au trebuit să țină pasul. Nu se mai puteau baza doar pe numere din ce în ce mai mari – astfel de soluții amână problema, nu o rezolvă.

Siguranța în curbe

Fenomenul este cunoscut: teorii matematice seculare își găsesc aplicații în tehnologiile prezentului și mai ales ale viitorului. Una dintre ramurile relativ tinere ale matematicii, cu doar două secole vechime, este geometria algebrică. Numele îi arată subiectele de studiu: ecuațiile algebrice tratate cu ajutorul reprezentărilor geometrice corespunzătoare. La fel cum în gimnaziu și apoi în liceu știai că o ecuație de forma y = ax + b reprezintă o dreaptă, iar y = ax2 + bx + c se desenează ca o parabolă.

Dreapta și parabola, reprezentate cu GeoGebra.

Interacțiunea dintre geometrie și algebră s-a dovedit foarte fructuoasă pentru multe probleme care au primit o abordare nouă. Printre altele, a condus la demonstrarea, după mai bine de 350 ani (1637-1995), a Marii Teoreme a lui Fermat – efortul final i-a aparținut britanicului Sir Andrew Wiles. Mai mult, cercetările pe această temă au arătat încă o legătură fascinantă și aparent improbabilă: cea între geometrie și aritmetică. Numită și teoria numerelor, aritmetica se ocupă de probleme care folosesc cele mai simple tipuri de numere: cele întregi, ca 0, 1, 2, 3 și variantele lor negative. 

Cum ar putea astfel de numere, puncte izolate, să fie relevante pentru geometrie, care se ocupă de curbe, suprafețe, volume? Intră în scenă curbele eliptice.

În general, curbele, suprafețele și toate celelalte obiecte geometrice, indiferent de dimensiune, sunt utile ca imagine de ansamblu a uneia sau mai multe ecuații care le generează. Dar, în cazul aritmeticii, aspectul e mai puțin important și mai mult anumite puncte. Și în exercițiile din liceu, de altfel, forma parabolei era mai puțin importantă decât punctul din vîrf și punctele de intersecție cu axa orizontală, care dau rădăcinile ecuației asociate.

Cum teoria numerelor folosește predominant numere întregi, orice curbă definită de o ecuație specifică este importantă în primul rând pentru punctele cu coordonate întregi pe care le conține sau uneori, cele raționale. Astfel de ecuații se numesc diofantice, după Diofant din Alexandria, care le-a folosit sistematic în secolul III.

Curbele eliptice sunt definite prin ecuații deloc complicate, cu forma generală y2 = x3 + ax + b. Pentru aplicațiile în aritmetică și, implicit, în criptografie, cauți puncte cu coordonate întregi (sau raționale) care se află pe graficul lor. În funcție de valorile coeficienților a și b, curbele eliptice au diverse forme. Dar, așa cum am spus, aspectul este mai puțin important; ce contează este să o privești ca pe o ecuație și să-i cauți soluțiile.

De exemplu, pentru ecuația (curba eliptică) y2 = x3 – 2x, există patru perechi de puncte cu coordonate numere întregi (x, y): (0, 0), (-1, 1), (2, 2) și (338, 6214). Imaginea curbei, împreună cu primele trei puncte, arată așa:

Curbă eliptică și punctele sale raționale, reprezentare cu GeoGebra.

Vânătoarea de puncte cu coordonate întregi (numite, în general, puncte raționale) seamănă parțial cu căutarea numerelor prime – cele din urmă sunt o infinitate și e clar că mereu există încă unul și încă unul, tot mai mari, chiar dacă metodele pentru a le obține sunt tot mai complicate. În schimb, punctele raționale de pe curbe eliptice depind în mod esențial de curba în sine. Și, pentru că problema vine din start cu o componentă de geometrie algebrică – prin ecuația definitorie și imaginea corespunzătoare –, căutarea este cu mult mai sofisticată decât obținerea unui nou număr prim.

Ar putea părea că, tocmai datorită faptului că poți folosi și metode algebrice, și geometrice în studiul curbelor eliptice, ele sunt mai ușor de înțeles. În realitate, această diversitate aduce probleme suplimentare și nu puține sunt conjecturile care se referă la curbe eliptice aparent simple. Similar cu ipoteza lui Riemann, cea mai importantă conjectură privitoare la numerele prime, și curbele eliptice au propriile probleme fundamentale. 

Conjectura BSD, denumită după Bryan J. Birch și Peter Swinnerton-Dyer, care au formulat-o în anii 1960, tratează tocmai mulțimea de puncte raționale de pe o curbă eliptică arbitrară. Dificultatea problemei se datorează și calculelor complicate care sînt necesare, încît autorii înșiși au fost nevoiți să folosească diverse supercomputere pentru câteva teste. Până în prezent, răspunsul general se știe doar pentru câteva cazuri particulare, așa că problema este una deschisă, inclusă pe lista celor șapte Probleme ale Mileniului, pentru care Institutul Clay din SUA oferă câte o recompensă de un milion de dolari.

Secrete mai bine ascunse

Criptarea cu ajutorul curbelor eliptice preia din algoritmii Diffie-Hellman și RSA principalele trăsături de securitate, pe care le combină și le îmbunătățește, totul cu scăderea costului computațional. 

Schimbul de chei din algoritmul Diffie-Hellman se bazează pe operații de exponențiere (ridicare la putere) și, implicit, operațiile inverse, de logaritmare. De aceea, numerele implicate devin foarte rapid greu de stăpânit, întrucât operația de ridicare la putere produce o creștere uriașă și rapidă. Imaginează-ți, de exemplu, simpla ridicare la pătrat, aplicată succesiv, pornind cu 2. Calculezi de fiecare dată pătratul (puterea a doua) și obții un șir care crește extrem de rapid: 2, 4, 16, 256, 65536, 4294967296… E clar acum că, dacă folosești numere cu sute de cifre, rezultatele explodează, din punctul de vedere al ordinului de mărime. 

Problema inversă, a logaritmului, aduce și ea dificultăți matematice care contribuie la securitate. Logaritmul unui număr într-o bază fixată înseamnă puterea la care trebuie ridicată baza pentru a obține numărul inițial. De exemplu, logaritmul în bază 2 al lui 8 este 3, pentru că 2 trebuie ridicat la puterea a treia pentru a da 8 (2 × 2 × 2 = 8). În general, orice logaritm al unui număr pozitiv se poate calcula, dar dacă vrei să obții doar rezultate numere întregi, cum se cer în aritmetică, atunci problema se complică foarte mult. În plus, căutarea nu are mereu soluție, deci riști să pierzi timp și cicluri de procesor pentru un rezultat care nu există. Ambele trăsături – creșterea exponențială foarte rapidă și dificultatea problemei logaritmice – fac algoritmul Diffie-Hellman suficient de sigur pentru multe situații reale.

De cealaltă parte, algoritmul RSA se bazează pe o matematică mult mai simplă: descompunerea unui număr în factori primi. Cum numerele prime sunt greu de găsit (imposibil, deocamdată, în cazul general), atunci și descompunerea unui număr cu sute de cifre este o operație extrem de costisitoare, de unde rezultă încrederea în criptarea RSA.

Aplicațiile de criptare care folosesc curbele eliptice se bazează mai ales pe găsirea punctelor raționale, cum am explicat. Detaliile tehnice matematice fac problema asemănătoare cu cea a logaritmului, cu restricții suplimentare: nu cauți doar rezultate numere întregi, ci ele trebuie să corespundă și unor puncte care se află, geometric, pe curba dată. 

Așa se face că numere mult mai mici, dar care corespund unor puncte raționale de pe curbe eliptice, pot fi folosite în algoritmi de criptare ca RSA. Și, din cauza dificultății sporite de a găsi punctele respective, sunt implicate numere mult mai mici. Într-un articol// „Elliptic Curve Cryptography”, cyberhoot.com // publicat de experții în securitate de la CyberHoot, criptarea cu algoritmi de tip RSA, dar implementați prin curbe eliptice, oferă aceeași securitate cu algoritmul RSA clasic (bazat pe factorizare) cu chei de zece ori mai mari. Concret, curbele eliptice care folosesc numere cu 70-100 cifre oferă o securitate comparabilă cu numerele prime de 700-1000 de cifre.

Viitorul și post-viitorul criptografiei

Criptarea care folosește curbe eliptice (prescurtată ECC, Elliptic Curve Cryptography) este o soluție de eficientizare a securizării informației în primul rând. În plus, dacă vreodată se vor rezolva principalele probleme din domeniu, adică ipoteza lui Riemann sau conjectura Birch-Swinnerton-Dyer, eficiența poate doar să crească. Asta pentru că eventualele demonstrații ale acestor probleme îți vor arăta cum să găsești mai rapid oricîte numere prime, respectiv puncte raționale pe curbe eliptice. Cercetătorii vor putea folosi, atunci, metode generale, fără să se mai bazeze pe proceduri ad-hoc ce funcționează doar pe unul sau câteva cazuri. 

De reținut, însă, că securitatea algoritmilor criptografici ca RSA sau Diffie-Hellman stă în dificultatea matematicii corespunzătoare, nu imposibilitatea ei. Pentru un matematician, problema are soluție, dar pentru un programator care trebuie să o implementeze, soluția este ca și inexistentă, câtă vreme nu se poate aplica într-un timp rezonabil. Acest timp scade odată cu creșterea puterii de calcul, însă este puțin probabil ca el să ajungă de ordinul secundelor în viitorul apropiat. 

Mai e, însă, ceva care amenință securitatea cibernetică bazată pe tehnologii clasice. În 1994, americanul Peter W. Shor a propus un algoritm care „sparge“ atît problema factorizării, cât și pe cea a logaritmului discret în timp cu mult mai scurt decât toate încercările de până atunci. Numai că procedura se bazează pe computere cuantice. Mai mult, îmbunătățirea semnificativă a timpului de execuție apare doar cînd s-ar folosi procesoare cuantice pe care este puțin probabil să le dezvolte cineva în viitorul foarte apropiat. 

O altă problemă, care nu apare la calculatoarele clasice, este că sistemele cuantice introduc zgomot, un defect datorat exclusiv fizicii cuantice (mai precis, naturii probabilistice care guvernează legile subatomice) și care este cu atât mai pronunțat cu cât procesoarele folosesc mai mulți qubiți.

În ce privește securitatea algoritmilor Diffie-Hellman și RSA, standardele în domeniu, amenințarea cuantică este încă departe. Conform unui raport// „Setting the Record Straight on Quantum Computing and RSA Encryption”, rsa.com // din octombrie 2024, în care se citează o cercetare// „How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, arxiv.org // din 2021, un computer cuantic ar putea să spargă algoritmul RSA în circa opt ore. 

Computerele clasice ar fi, practic, inutile, fiindcă ar necesita aproximativ tri triliarde de ani pentru aceeași sarcină. Însă rezultatul are două neajunsuri: analiza este pur teoretică, întrucât a imaginat folosirea unui computer cuantic cu 20 milioane de qubiți, în condițiile în care IBM plănuiește să preia supremația cuantică în 2025 prin construcția unuia cu „doar“ 4000 de qubiți. În al doilea rând, zgomotul dintr-un computer de asemenea putere nu ar mai fi neglijabil. Așa s-a și ajuns la cele opt ore – un timp nu foarte mic, pentru că, teoretic vorbind, sunt suficiente zece secunde pentru aceeași operație, executată de un computer perfect.

Algoritmul lui Shor nu ridică, deci, o problemă urgentă, ci mai mult prezintă o metodă bazată pe o tehnologie proof of concept. Mesajul este că, atunci cînd sistemele cuantice vor deveni accesibile publicului larg, criptografia trebuie regândită din temelii. Securitatea digitală va lăsa loc securității cuantice, cînd informația nu va mai circula pe baza electronicii digitale, binare – bits & bytes –, ci pe calea qubiților. 

Cum, însă, în domeniul securității informației nu poți fi niciodată exagerat de precaut, cercetări ca ale lui Shor invită și la studiul algoritmilor cuantici, dar și la dezvoltarea unora post-cuantici. Fiecare pas înainte de timpul lui.