Robert Brook/Science Photo Library via Getty Images

Criptografie #1: Secretul numerelor prime23 min read

De Adrian Manea 17.01.2025, ultima actualizare: 03.02.2025

„Particule elementare“ ale aritmeticii, numerele prime apar în multe probleme nerezolvate de secole. Chiar și așa, securitatea cibernetică din întreaga lume se bazează pe ele. De ce sunt atât de importante și cât de vulnerabile sunt în fața viitorului (post)cuantic?

Se știe din Antichitate că există o infinitate de numere prime și că, dacă înmulțești două sau mai multe (eventual cu repetiții), obții toate numerele naturale. De exemplu, 12 = 2 × 3 × 3 sau 100 = 2 × 2 × 5 × 5. Ambele rezultate generale au fost găsite și demonstrate de Euclid, în secolul al treilea înaintea erei noastre, într-o perioadă în care descoperirile se dădeau ca fapte, fără justificări sau argumente riguroase. De altfel, Euclid a fost printre primii care au folosit metode formale pentru demonstrații matematice, precum reducerea la absurd.

S-ar crede că, după mai bine de două milenii, se știe cam tot ce ar fi de știut despre numere naturale, numere prime și numere în general. Problemele matematicii din secolul XXI sunt mult mai complexe decât niște înmulțiri din aritmetică, nu? Da și nu. 

În primul rând, teoria numerelor (sau aritmetica) a produs unele dintre cele mai complicate probleme în matematică de-a lungul istoriei, dintre care câteva se leagă tocmai de numere prime. Tocmai aparenta simplitate a făcut ca unele dintre ele să fie rezolvate abia după mai bine de trei secole. Altele// Cum ar fi Conjectura lui Goldbach: wikipedia.org // se apropie de aceeași vârstă și soluția tot nu se întrezărește. 

În plus, aplicațiile aritmeticii au atins domenii sofisticate ale științelor naturii și tehnologiei, încât, indirect, numerele prime se află în centrul unei ramuri de cercetare esențiale pentru prezent și viitor: securitatea cibernetică. Iar ca lucrurile să fie și mai interesante, cele două aspecte sunt legate strâns: poate cea mai importantă problemă a matematicii, propusă în urmă cu aproape două secole, are implicații majore atât în aritmetică în general și numere prime în particular, cât și în criptografie și securitate cibernetică.

În căutarea numerelor prime

Faptul că se poate obține orice număr natural prin înmulțirea a două sau mai multe numere prime – ceea ce le justifică rolul de „particule elementare“ ale aritmeticii – este doar una dintre proprietățile lor fascinante. Surprinzător, majoritatea rezultatelor spectaculoase, dar și a întrebărilor încă fără răspuns tratează cea mai simplă curiozitate: cum știi dacă un număr dat este sau nu prim?

Șirul numerelor prime este infinit, dar distribuția lor printre celelalte numere naturale (numite compuse) este o enigmă. Primele numere prime sunt 2, 3, 5, 7, 11, 13, 17. Lista continuă, dar, de la un punct încolo, cunoștințele se termină. Asta pentru că până în anul 2025 cel puțin, nu există o regulă generală, o formulă care să producă doar numere prime. 

Altfel spus, se știe cum arată un număr prim oarecare doar prin definiție și o listă de caracterizări, dar nu se poate încadra într-un tipar. Există, de pildă, numere prime gemene, consecutive, precum 2 și 3, 3 și 5, 5 și 7, 11 și 13, 17 și 19 sau 461 și 463. Nu se cunoaște nici dacă există o infinitate de prime la această distanță minimă, dar se știe de exemplu, că ele se pot găsi și la distanță oricât de mare. Între 1129 și 1151, ambele prime, există 22 de numere dintre care niciunul nu mai este prim.

Din cauză că nu există o metodă generală prin care să producem numere prime, rezultă că și problema inversă, de recunoaștere a lor este dificilă, chiar imposibilă pentru un număr arbitrar. Știți teorema despre maimuța care ar putea tasta opera lui Shakespeare,// „Monkeys will never type Shakespeare, study finds”, bbc.com // dacă ar avea timp și resurse infinite? O provocare asemănătoare pentru numere prime ar fi imposibil de decis. Un număr generat aleatoriu, de o maimuță sau de un computer, poate reprezenta o problemă la care să nu existe răspuns, dacă este suficient de mare. 

De remarcat, totuși, că afirmația conține două adevăruri relative: „suficient de mare“ înseamnă, conform puterii de calcul din 2025, aproximativ 41 milioane de cifre, dar limitarea este și teoretică, din cauza unor conjecturi pentru care matematica încă nu a produs o demonstrație sau un contraexemplu.

Așa se face că lumea matematicii și a tehnologiei are o provocare la care se poate înscrie oricine: găsirea celui mai mare număr prim. Din mai multe motive, parțial matematice, parțial tehnologice, în această competiție se caută doar unele anume: prime Mersenne. În secolul al XVII-lea, Marin Mersenne a propus numere prime care sînt cu 1 mai mici decât puterile lui 2.

 Nu toate numerele prime au această formă și nu toate numerele Mersenne sunt prime, dar forma particulară este suficient de simplă și oferă una dintre puținele șanse de reușită. De exemplu, 7 = 8 – 1, 31 = 32 – 1, 127 = 128 – 1; toate sînt prime Mersenne. Întrebarea generală, dacă există o infinitate de numere prime de tip Mersenne, este încă un exemplu de conjectură la care se lucrează de secole.

Proiectul GIMPS (Greatest Internet Mersenne Prime Search),// Mai multe detalii pe mersenne.org // pornit în 1996, implică cercetători care încearcă să găsească următorul număr prim de tip Mersenne. Pe 21 octombrie 2024, Luke Durant, fost angajat al Nvidia și cel mai important colaborator al proiectului, a obținut supremația printr-un număr cu peste 41 milioane de cifre: 2136279841-1. Căutarea l-a costat peste un milion de dolari, iar numărul găsit încheie un interval de șase ani de la anteriorul.

Durant, ca majoritatea cercetătorilor în domenii care necesită putere de calcul imensă, s-a bazat pe hardware și software concepute special pentru astfel de provocări, iar costurile și expertiza necesare nu sunt la îndemâna oricui. Una dintre implicații este că această competiție nu e tocmai pentru toată lumea, în primul rând din motive financiare. 

Dar mai există o metodă, mult mai accesibilă (cel puțin din punct de vedere material), prin care aproape oricine poate pune capăt definitiv acestor căutări. 

În 1859, germanul Bernhard Riemann propune o problemă de analiză complexă, un domeniu aparent fără legătură cu aritmetica. Formularea originală, ipoteza lui Riemann, cum a ajuns să fie denumită problema, nu pare să aibă legătură cu numerele prime. Dar de-a lungul celor aproape două secole de cercetări, matematicienii au demonstrat că rezultatul, dacă va ajunge să fie confirmat (sau contrazis), va atrage numeroase alte concluzii, printre care și răspunsul final pentru distribuția numerelor prime. O eventuală soluție la ipoteza lui Riemann – fie o demonstrație a adevărului, fie un contraexemplu – aduce, printre multe alte recompense, și ordinea în șirul numerelor prime: vei ști cum să le obții și recunoști pe toate.

Coduri și securitate

Matematicianul britanic Godfrey H. Hardy (1877-1947), cu rezultate importante în teoria numerelor, la care a contribuit și indirect, prin descoperirea indianului de geniu Srinivasa Ramanujan, spunea către finalul vieții că nimic din cercetările sale nu va fi vreodată de folos practic omenirii. Hardy scria aceste rînduri în eseul Apologia matematicianului (1940), în care plasa matematica în sfera artelor, fiind complet neinteresat de aplicații tehnologice sau militare, mai ales în contextul vremurilor.

După doar câțiva ani, un compatriot avea să-l contrazică, iar Hardy a apucat să vadă cât de tare se înșelase. Prin descifrarea principiilor de funcționare a mașinii Enigma, Alan Turing a dat o lovitură importantă Germaniei naziste și a legat definitiv aritmetica de criptografie.

Istoria codurilor este veche, pierdută aproape în trecut. Se știe, de exemplu, că Grecia antică folosea metode criptografice (de aici și cuvîntul, kryptos + graphia = scriere ascunsă). La fel Imperiul Roman, de la care a rămas cifrul Caesar, o procedură prin care se deplasează literele din alfabet cu un număr fixat de poziții. Însă criptanaliza, adică studiul matematic al metodelor de ascundere și recuperare a informației, este un domeniu apărut, practic, în urma celui de-al doilea Război Mondial.

Metodele de criptare se bazează pe rezultate complicate de matematică, împreună cu multe trucuri inginerești, informatice. Din punct de vedere practic, cele mai importante nu sunt codurile demonstrabil invincibile (încadrate de matematicieni la securitate perfectă), ci acelea pentru care este nefezabilă o decriptare din partea unui eventual atacator. Se pot lansa diverse atacuri, cu șanse mai mici sau mai mari de reușită, dar ele necesită fie timpi de lucru uriași, chiar de ordinul vârstei Universului, sau resurse computaționale practic inaccesibile.

Algoritmii criptografici populari sînt cei cu cheie publică: toată lumea știe procedura și mare parte a numerelor folosite în calculele complexe. Însă aplicarea inversă a operațiilor, descifrarea sau decriptarea, durează atît de mult încât fie atacatorii abandonează, fie oferă timp de răspuns sau de interceptare.

Mulți astfel de algoritmi, implementați în sisteme variate, de la aplicații de comunicare de tip chat sau email la rețele sociale și sisteme bancare se bazează pe operații cu numere prime. Avantajele rezultă din explicațiile de până acum: orice număr natural se poate obține cu ajutorul numerelor prime, iar dacă se dă un număr oarecare, primalitatea lui este foarte greu de testat.

Nu e necesar să se apeleze la numere prime de tipul celor descoperite de GIMPS, pentru că operațiile cu ele ar fi complicate și costisitoare nu doar pentru atacatori (ceea ce este de dorit), ci și pentru cei care implementează sistemul. În realitate, sistemele criptografice din aplicații ca WhatsApp, Telegram, Signal, Facebook, Gmail ș.a. securizează conținutul în mai puțin de o secundă, așa că trebuie să se țină cont și de eficiența algoritmilor.

Una dintre cele mai populare astfel de metode, apărută în 1977, este rezultatul colaborării a trei cercetători: Ron Rivest, Adi Shamir și Leonard Adleman, care îi dau numele — RSA. Ideea matematică e foarte simplă, dar extrem de eficientă: se folosesc două numere prime mari care se înmulțesc. Rezultatul are proprietatea că nu se împarte decît la acei doi factori, deci dacă un atacator ar încerca să-l descompună, ca un prim pas în decriptare, ar avea foarte mult de lucru. Un exemplu: dat numărul 213443, nu se găsește niciun divizor de la 2 la 461 — deci sunt 460 pași irosiți —, pentru că 213443 = 461 × 463.

Principiul matematic după care funcționează sistemul RSA se poate implementa cu numere oricât de mari, dar conform testelor de la nivelul anului 2024, securitatea este, practic, asigurată dacă se folosesc numere de aproximativ 600 de cifre. Numere și mai mari ar face un atacator să muncească mai mult, dar ar încetini și procesul de criptare. În practică, ești obișnuit ca interacțiunile online să se întâmple în cel mult câteva secunde, așa că majoritatea utilizatorilor probabil nu ar fi de acord să aștepte nici măcar un minut pentru a trimite un e-mail criptat dacă astfel le-ar scădea șansele de atac cu doar câteva procente, de exemplu.

Viitorul cuantic și post-cuantic

În decembrie 2024, Google a lansat Willow, un procesor cuantic, care a finalizat în mai puțin de cinci minute o sarcină de calcul ce ar fi durat 1025 ani pentru un computer clasic. În general, computerele cuantice s-au remarcat tocmai prin faptul că întrec orice bariere de performanță ale celor clasice. Atunci, dacă puterea de calcul devine aproape nemărginită, pe parcurs ce tot mai mulți jucători importanți de pe scena tech ajung să dezvolte computere cuantice impresionante, la ce te poți aștepta din punctul de vedere al securității cibernetice?

Gândește-te ca într-un business: fabricarea și întreținerea unui computer cuantic sunt extrem de scumpe, iar aceste costuri nu vor scădea prea curând. În multe situații, întreg ansamblul tehnologic trebuie menținut într-un mediu bine controlat, la niveluri de presiune și temperatură inaccesibile majorității laboratoarelor. Este de așteptat, așadar, ca astfel de instrumente să fie folosite pentru scopuri pe măsură și e nerealist să crezi că printre ele se află acțiuni de hacking, indiferent de țintă.

Pentru viitorul ceva mai îndepărtat în care chiar și tu ai putea avea un astfel de computer la birou, matematica și, implicit, industria securității cibernetice, sunt deja pregătite cu metode și mai sofisticate. Algoritmii rezistenți cuantic și criptarea post-cuantică sunt două dintre temele relevante; dar și matematica clasică are un răspuns, prin curbele eliptice

Acestea sînt obiecte folosite mai ales în algebră și geometrie, cu proprietăți și mai greu de găsit decît numerele prime. Astăzi, criptografia care folosește curbe eliptice (ECC, Elliptic Curve Cryptography) ocupă un rol important în cercetările din domeniu. În plus, spre deosebire de algoritmii (post)cuantici, cei bazați pe curbe eliptice pot fi implementați pe orice computer, iar matematica respectivă își are originile tocmai în secolele XIX-XX.

Obiecte enigmatice ca și numerele prime și cu o aparență tot așa de simplă, curbele eliptice sînt la fel de pregătite pentru evoluția securității cibernetice precum cele mai avansate sisteme cuantice, cu doar o fracțiune a costurilor implicate. Posibilele aplicații deschid și ele perspective noi, dar permit și continuitatea aplicațiilor curente. Un lucru e sigur, peste toate: indiferent de direcția clasică sau cuantică, viitorul sună computațional.



Text de

Adrian Manea

Adrian Manea este matematician și profesor, fondator al Poligon Educational, proiect prin care îmbină matematica și științele cu istoria, filosofia, literatura și jocurile. Scrie și pe Substack, Laturi ale științei.

SĂNĂTATE|OVERVIEW

Molecule și mindfulness: știința arată beneficiile meditației pentru sănătate

De
Cercetătorii sprijiniți financiar de UE investighează legătura dintre conștientizarea stării interioare și sănătate, și oferă noi posibile opțiuni pentru tratamentul și depistarea precoce a cancerului. 
ȘTIINȚĂ|RO-CERCETARE

Cercetarea românească în ianuarie: De ce îți este mai ușor să zici „I love you” decât „Te iubesc”

De
La început de an, cercetarea românească vine cu descoperiri interesante despre civilizația Cucuteni, confirmarea prezenței strămoșilor oamenilor pe teritoriul României și un studiu care arată că studenților scriu mai personal în engleză decât în română.
MEDIU|OVERVIEW

Copaci tăiați după ureche. Orașele din România nu au o infrastructură verde, deși legea o cere

De
Se taie fără discernământ, fără cunoștințe, fără logică. Se încastrează arbori în pavaj. Pornind de la o postare a peisagistei Diana Culescu despre tăierea rădăcinilor chiparoșilor de baltă din Herăstrău, am încercat să înțeleg mai bine ce consecințe are, de fapt, gestionarea defectuoasă a spațiilor verzi din România.
ȘTIINȚĂ|TRAVELING MINDS

Dana Mustață, povestea româncei care reconstituie istoria televiziunii comuniste

De
Predă la Universitatea din Groningen și studiază istoria televiziunilor comuniste. În cercetările ei, scoate la iveală aspecte mai puțin cunoscute ale televiziunii din fostele state comuniste și evidențiază legăturile culturale și politice care au marcat în trecut această industrie.