Probleme nesoluționate ale informaticii (I): factorizarea (desigur, rapidă!)

Istoria secretizării comunicațiilor a fost, oricât ar părea de hazardată afirmația - o preocupare dintotdeauna a societății.  Probabil, intuirea legăturii (unii spun - identității) între cunoaștere și putere a condus la precauția transmiterii informațiilor, spre a nu fi folosite de cei nedoriți. Șoapta și memorarea sunt extrem de limitative, alterabile și lente pentru transmitere. Cu expeditor și destinatar presupuși „de încredere”, s-a conștientizat repede că siguranța și eficiența comunicării „la distanță” stau în canalul de transmitere și în curier. Ascultătorul RRC care parcurge aceste rânduri este invitat să identifice ipostazele noțiunilor, de-a lungul timpului.

S-a înțeles rapid că mesajele trebuie nu numai transmise prin „canale” fiabile și „curieri” de încredere, ci trebuie și să fie secretizate. Transformate, adică, folosind procedee care să le facă neinteligibile intrușilor, dar repede și ușor de „citit” de cei în drept.

Au devenit esențiale preocupările intense pentru găsirea „codului ideal”, care să facă informația purtată imposibil de văzut „în clar”. A fost generat și se dezvoltă un întreg domeniu de studiu - criptografia - populat de personalități de vârf, în principal matematicieni. O „galerie a celebrităților” din domeniu ar fi interesantă, dar depășește cadrul acestui episod.

În esență, asemena „transformare în neinteligibil” se poate face doar folosind funcții matematice, ca „reguli de schimbare” precum și așa-numite „chei” - adică șiruri de caractere (numere, litere) care se pun în funcții pentru a coda și decoda, apoi, mesajul.

S-a înțeles, de asemenea, repede, că schimbarea periodică a funcțiilor și cheilor, pentru a evita să fie reconstituite, este o reală problemă:  comunicarea actualizărilor între expeditor și destinatar trebuie, la rându-i ... secretizată! Adesea, peste mii de kilometri!  Astfel încât, problema siguranței transmisiilor nu ar fi rezolvată superior... ci doar „translatată”.

Ați observat, deja, stimați cititori și RRCascultători ?... cele descrise până acum implică nevoia ca „ambele capete” incluse în comunicare să cunoască „cheia” și procedura  codare-decodare.  Pe această premiză s-a lucrat până prin anii 1970;  acțiuni temerare de descifrare insesizabilă au rămas  secrete sau au devenit legende.  Posesia celebrei mașină Enigma și decriptarea codului naval japonez au determinat - se spune - chiar cursul celui de-al doilea război mondial!

Transmisiile secretizate astfel se numesc, azi, „simetrice” - cu egală „încărcătură de cunoștințe și tehnologie  confidențială”  între cei care comunică.  Dar, formidabila dezvoltare a instituțiilor societății și a telecomunicațiilor a multiplicat astronomic nevoia de comunicare în siguranță, răspândind-o la „banale” aplicații civile: azi, orice operațiune online trebuie protejată!  Și nu este posibil de „împuternicit” fiecare (cetățean) utilizator cu secretele codării/decodării.  „Clientul” - cum i se spune în jargon IT - trebuie „descărcat” de grijile păstrării secretului, fie el personal sau profesional!

Astfel, mințile strălucite și investițiile și-au mutat obiectivele către tehnologii de codare zise  „asimetrice” - în care doar „stăpânul inelelor” - fie-ne iertată metafora - știe să citească, de exemplu, o autentificare  trimisă de Popescu.  Iar lui Popescu i se dau doar gadget-uri, adică mici dispozitive sau - mai nou - aplicații pe mobil care 1) îl identifică și - crucial - 2) secretizează, fără ca Popescu sau vreun  spion pe traseu să aibă, respectiv să poată avea „cheia” decodării.  În timp util.

În paranteză fie spus, asimetria este o constantă a arhitecturilor tehnologice moderne, care implică un producător sau ofertant (să spunem - de programe de televiziune) și un utilizator - clientul final - Ionescu.  În mod deliberat, compresoarele de semnal (codoarele) sunt obiecte ale investițiilor și performanței situate la sursa de program - în acest caz - stația TV. Scopul este reducerea fluxului digital cu păstrarea calității imaginii, astfel încât mai multe programe să poată fi „înghesuite” într-o bandă dată și plătită.  Iar telespectatorul este dotat cu un decodor relativ banal, puternic asimetric în complexitate și cost. Paranteză închisă... deși principiul asimetriei în tehnologia comunicațiilor este o veritabilă idee care a schimbat lumea!

Episodul anunța, însă, o „problemă nesoluționată a informaticii”. Nimic despre aceasta, până aici ?

Ei bine, codarea asimetrică induce acea problemă cu un pragmatism care obligă, forțează la exercițiul teoretic matematico-informatic; și vom vedea cum.

În cel mai simplu scenariu de comunicare folosind codarea asimetrică, protagonistul  A (să zicem, banca) deține două numere prime, cu ajutorul produsului cărora mesajul „în clar” este secretizat. Numai produsul respectivelor două numere prime, să-l numim P1 x P2 este cunoscut în exterior și numit „cheie publică”.

Tot A îi trimite lui B (clientului), împreună cu cheia publică, un număr - în fapt, un exponent, notat „e”.   Clientul mai deține deja, de la începutul cooperării cu A, și o funcție matematică (tot nesecretă!) de produsul cheie publică și „e”.

Aici găsim o „pepită de aur” a inteligenței: Funcția matematică folosită (fixă!) este o succesiune de operații în care figurează produsul (P1 x P2) - cheia publică, dar NU P1 sau P2 separat!  Găsirea formei acestei funcții a fost pasul crucial pentru aplicarea practică a ideii codării asimetrice.

Clientul B folosește funcția de (P1 x P2) și „e” și codează mesajul pe care îl are de transmis lui A (băncii). Din acel moment, este aproape imposibil ca mesajul să poată fi decodat de altcineva decât A. Cum așa? Deoarece  este necesară calcularea funcției inverse, pentru care trebuie cunoscute numerele P1 și P2 („cheia privată”) separat, nu numai produsul lor. Doar A (banca) știe numerele separat.

Dificultatea, pentru potențialul „spărgător de cod” este aflarea celor două numere prime, P1 și P2, cunoscându-le produsul P1 x P2. Altfel, nu poate determina inversa funcției, respectiv decoda mesajul. Și, dacă numerele prime - factori sunt suficient de mari (de exemplu,  exprimate prin câte 2048 de biți sau puțin peste 600 de cifre zecimale, cum se practică în prezent), aflarea lor, zisă  factorizare, poate dura zeci de ani !  De înțeles, „grăuntele de aur”,  funcția (succesiunea de operații) care permite  clientului B procedeul codării cu „cheia publică”  lasă doar pe destinatarul A să decodeze folosind cei doi factori cunoscuți numai de el - numerele prime !

Ca exemplu, poate uimitor pentru neavizați, aflarea celor doi factori ai produsului infim 2173 implică multe raționamente și operații, în orice tactică aplicată.  Încercați și dv, stimați cititori, să aflați că numerele prime respective sunt...  41 și 53.  Darămite dacă numerele, prime, ar fi lungi de câte zece cifre!

Acest tip de algoritm de criptare asimetrică - primul care s-a impus - a fost publicat în 1977 și este cunoscut ca „RSA”, după numele „dezvoltatorilor” (cum li se spune în jargon corect politic)  Ron Rivest, Adi Shamir și Leonard Adleman.  Înainte de a continua tema de bază, li se cuvin, în acest episod, câteva elemente de prezentare. Cum este de așteptat, sunt „minți brici” ale domeniului, cu performanțe profesionale de excepție. În anul 2002 au fost laureații premiului Turing - echivalentul Nobel în informatică.

Ron Rivest (n.1947, american) are diplomă de matematician la Yale și de IT-st la Stanford. Este co-autor al „Bibliei domeniului” - Introduction to Algorithms  https://en.wikipedia.org/wiki/Introduction_to_Algorithms  (o carte vândută fizic în peste 500.000 de exemplare!)  și al unor algoritmi de criptare simetrică apăruți după 1987. Ultima observație nu este lipsită de interes: secretizarea informațiilor în creștere galopantă se face eficient folosind, după caz,  ambele tipuri de algoritmi - simetrici și asimetrici - fiecare având calități la care nu se poate renunța.  Anticul - la propriu ! - procedeu  simetric al împăratului roman Iulius Cezar rămâne, principial, valid.  În fine - Ron Rivest este un protagonist de mare prestigiu al criptografiei moderne; cititorul interesat este invitat să-l descopere.

Adi Shamir (n.1952, israelian) este autorul a numeroase invenții în criptografie, premiat și recunoscut în lume, aparținând, prin deja-menționatul premiu Turing, elitei domeniului IT.  Personlitate complexă, Adi Shamir a fost ales, în 2019, membru al foarte selectivei American Philosophical Society.

În fine - dar nicidecum în cele din urmă - Leonard Adleman (n. 1945, american) este tot un corifeu al informaticii: referirea la Adleman ca Tata-l metodei de calcul ADN (Father of DNA Computing) indică, totdată și una dintre direcțiile de lucru în tehnologia informației (și nu numai!) - raportarea la soluțiile naturii, revelate de microbiologie, în abordarea problemelor.  Subiectul este fascinant, fie și într-o observare nespecializată!  Revenind la Len Adleman - desigur că nici el nu este banal: a practicat boxul amator, inclusiv ca sparring  partner al unui „greu” de culoare  american.

Informaticienii buni sunt  foarte riguroși la lucru. Motivarea juriului Premiului Turing din 2002 a fost - „pentru ingenioasa lor contribuție la a face criptografia cu cheie publică utilizabilă practic” (sn. red.). Formularea recunoaște că ideea trimiterii mesajelor cifrate fără nevoia trimiterii cheii secrete apăruse deja. Într-adevăr, criptologii  Whitfield Diffie și Martin Hellman  (ei înșiși laureați Turing în 2015!) o prezentaseră  într-un articol seminal, de referință,  publicat în 1976, fără însă a furniza metode realiste de implementare practică. Era nevoie de acea funcție matematică - ingredient, alături de chei.  Golul, deloc neglijabil, a fost „umplut” de Rivest-Shamir-Adleman,  doar un an mai târziu. Se spune că Rivest a (de)scris „dintr-un condei”, formalismul funcției-lipsă după noaptea albă petrecută de Paștele evreiesc.  Aura realizării este completată de mențiunile privind cunoașterea timpurie a codării asimetrice și ținerea secretă de către serviciile britanice. Au existat și alți protagoniști sclipitori...  Oricare ar fi povestea completă, necesarul colosal de comunicare în siguranță al instituțiilor societății n-a mai avut răbdare. Codarea RSA explodase!

Paranteze necesare, precum cea de mai sus, dedicată străluciților inventatori ai algoritmilor de codare asimetrici, pot ușor divaga de la subiectul-titlu: unde este descrierea problemei nesoluționate a informaticii - factorizarea, în acest episod ?

Prezentarea de mai sus cuprinde câteva referiri la elemente-cheie esențiale pentru funcționarea secretizării RSA: cele două numere prime suficient de mari. Reamintim - produsul  lor (P1 x P2), public, intervine la codare, însă doar cunoașterea lor separată, ca factori, P1 și P2, permite decodarea, la destinatar. Obiectivul eventualilor intruși  este, astfel, aflarea celor două numere prime, cunoscând produsul lor.

Reamintim cititorilor că numărul prim este cel care se divide (se împarte) doar la 1 (normal, desigur) și la el însuși.  Numerele prime încep, convențional, cu 2. Apoi 3, 5, 7, 11, 13, 17, 19, 23, 29...

Urmează că un produs de două numere prime poate avea doar doi factori - numerele respective. Precum în exemplul deja dat: 2173 = 41 x 53. Nu există alte două numere naturale care, înmulțite, să dea 2173 !  Particularizând pe acest exemplu (și simplificând la maximum), codarea RSA se face folosindu-l pe 2173, dar decodarea este posibilă doar cunoscându-i factorii: 41 și 53.  Timpul necesar aflării acestor factori, fie sistematic în varii feluri „pe încercate”, fie aplicând observații, este - din nou, simplificând la extrem -  lung. Atât de lung, încât „fereastra de oportunitate” a intrusului (hackerului) expiră cu mult înainte de a afla numerele 41 și 53.

Dar, interesul „băieților buni” este ca hackerul  să nu poată afla cele două numere, oricâte încercări ar face, timp de - să spunem - un an. Sau 10 ani, sau 20... astfel încât canalul de transmisie să rămână sigur timp îndelungat, fără schimbarea cheilor.

Ei bine, probabilistic s-a arătat că, dacă s-ar folosi numere prime de câte 600 cifre zecimale (nu de două, precum 41 și 53),  factorizarea - adică aflarea lor cunoscându-le produsul - ar dura zeci de ani, la tehnica disponibilă și algoritmii cunoscuți în prezent. Această mărime a cheilor (2048 biți) este folosită azi în tranzacțiile obișnuite, de pildă bancare.

Cu toate acestea, mai ales pentru transmisiile critice, numerele prime P1 și P2 au ajuns la 4096 biți sau  1234 cifre zecimale!

Șansa teoretică, infinitesimală, a găsirii  lor cunoscându-le produsul există, dar este tratată (adică redusă) și cu alte măsuri de protecție și detecție, foarte interesante și acestea, dar care depășesc cadrul și tema acestui episod.

Și totuși... de ce am anunțat factorizarea ca problemă nesoluționată a informaticii ?  Ei bine, este pentru că nu s-a aflat, cu toate eforturile, un algoritm de factorizare rapidă. Adică, găsirea factorilor primi P1 și P2 cunoscându-se produsul lor.

De la sine înțeles că nu este o banală „declarație de necunoaștere”: din anii 1970, când s-a născut codarea asimetrică RSA, generații de informaticieni și matematicieni  au încercat să obțină o rezolvare  teoretică „trăznet” a factorizării, ajutați de performanțele exponențiale în viteza de procesare. În timp, unele metode de factorizare au devenit clasice, purtând numele autorilor, cum ar fi Algoritmul (Hendrick) Lenstra după curbă eliptică;  sau Metoda „ρ” (ro, a lui John) Pollard .

(Din nou) o paranteză: timp de zeci de ani, s-au acumulat în domeniu câteva astfel de probleme nerezolvate, nodale,  cărora li se adaugă cele de eșalon secund, tot foarte importante, privite ca eliberatoare  de drumuri, de continuări.  Știați că există câteva, așa numitele „probleme de 1 milion de dolari” - indicând premiul, real, oferit pentru găsirea unei soluții ?

Revenind la factorizare, dar aplicabil și altor probleme nerezolvate: nu doar că nu s-a aflat soluția-fulger, dar mai mult, încă: nu se știe dacă un algoritm de factorizare rapidă există !

Ar fi, probabil, greșit să ne imaginăm performeri ai info-matematicii chinuiți de imposibilitatea unei rezolvări definitive: pentru ei (sau angajatorii lor) este mult mai profitabil să construiască, să „complice” pe baze virtual inatacabile, decât să se irosească în căutări „fără garanții”.

Pentru un filozof al științei însă, conteplarea situației ca, pe lângă a nu găsi un răspuns la o problemă scurtă și clară, să nu știe nici dacă răspunsul există ... poate bulversa!

În strânsă legătură cu explicațiile privind algoritmul RSA, cititorul este invitat să sesizeze că nivelul de siguranță al secretizării crește odată cu mărimea numerelor prime din componența cheii private. De aici și o explicație a interesului pentru aflarea de numere prime suficient de mari. Trebuie „loc” destul pentru milioane de chei private diferite! Milioane? E-un fleac! Microscopic! Estimările arată că în zona numerelor exprimate cu 4096 biți (sau 1234 cifre binare) s-ar găsi 2,8 x 10150 numere prime!  Deci, există chei private atât de multe, încât nici măcar nu pot fi cuprinse pe o listă!

De dragul divagației - la „capătul îndepărtat” găsirile se produc din ce în ce mai greu, deoarece (după cum s-aputut  arăta), numerele prime sunt, pe măsura creșterii, în general  din ce în ce mai rare.  „Recordul” actual datează din anul 2018:  cel mai mare număr prim cunoscut are 24.861.808 cifre zecimale!  Colosal, față de dimensiunea cheii private RSA considerate, azi și pentru viitorul rezonabil, sigură: 4096 cifre binare - echivalentul a numai 1234 cifre zecimale.  Discrepanța dimensională vorbește de la sine: este de necrezut că numere prime de milioane de cifre vor servi, vreodată, la codarea mesajelor. De fapt, în majoritatea percepțiilor, acești coloși speciali nu vor folosi la nimic.

Acest episod nu descrie o Erezie modernă , ci se apropie de aceasta. Este vorba despre percepția unor probleme sau întrebări  la care Știința nu doar că nu are răspuns de zeci de ani; acesta ar putea fi, elegant și pozitivist, lăsat în seama progresului !  Greu cu adevărat ar fi să nu se știe dacă însuși răspunsul... există!  Încheind cu o semi-glumă... câte stele sunt pe cer?

redactor Florin Vasiliu