Els humans tenim secrets des de l’antiguitat. Amb ells, neix la necessitat d’enviar-los de forma segura, és a dir, que només els pugui llegir la persona interessada. La criptografia és la part de les matemàtiques que s’encarrega de donar mètodes per a fer-ho i s’ha usat habitualment per a fins polítics o militars. Juli Cèsar és famós per enviar missatges a les seves tropes fent córrer 3 posicions l’alfabet. Així, quan volia transmetre una a, enviava una d. Si algú interceptava el missatge, el trobava il·legible.
Actualment, la criptografia és imprescindible a les nostres vides, ja que totes les comunicacions que fem per internet poden ser fàcilment interceptades. Però, podem fer servir els mateixos mètodes que en Cèsar quan enviem, per exemple, el número de targeta en comprar per internet?
Sistemes criptogràfics
Antigament, quan es volia enviar un missatge secret, com quan en Cèsar es volia comunicar amb algun general, prèviament s’havia d’acordar una clau. Imaginem que tenim un missatge secret com per exemple “M’agrada Ciència Oberta” que volem enviar a un conegut. Aleshores tots dos tenim una clau (que prèviament hem acordat a través d’algun canal segur) i codifiquem el missatge amb la clau. Podem imaginar aquest procés com col·locar el missatge en una caixa amb un pany. Llavors el podem enviar pel canal insegur i el nostre amic el podrà obrir amb la seva clau i llegir-lo. Si algú l’intercepta, com que no té la clau, no el pot obrir i per tant no el pot llegir.
Ara, però, volem enviar el missatge al nostre banc. El banc d’alguna forma ens ha d’enviar la clau i aquesta ha de ser única, perquè si tothom tingués la mateixa, ens podrien espiar la nostra comunicació. A part, ens l’ha d’enviar per algun canal segur -no serveix fer-ho per internet-, si no l’espia ens podria robar la clau i llegir els nostres missatges secrets. Podríem quedar una tarda amb el nostre banquer i acordar una encriptació. Però ara imaginem que també ho haguéssim de fer amb el correu electrònic, les xarxes socials, cada pàgina on volem comprar, etc. No donaríem l’abast!
Per això, es va idear un mètode criptogràfic diferent
En lloc de repartir claus, el banc reparteix cadenats, dels quals només ell en té la clau per obrir-los. Aleshores, tu només has de posar el missatge dins la caixa, tancar-la amb el cadenat i enviar-la pel canal insegur. Quan arribi al banc, ells podran obrir-la amb la seva clau i llegir el missatge.
Aquest model que pot semblar tan senzill va costar molt de posar-lo en pràctica. Finalment va ser un equip del MIT de tres matemàtics, Ron Rivest, Adi Shamir i Leonard Adleman, que es van inventar la criptografia RSA -batejada així per les inicials dels seus cognoms- l’any 1977 seguint aquest esquema dels cadenats. Clifford Cocks va arribar als mateixos resultats de forma independent 3 anys abans però no es va saber fins l’any 1997 quan la intel·ligència britànica, on treballava, va desclassificar el resultat i per això no se’l inclou al nom.
Els nombres primers
El sistema RSA usa els nombres primers. Recordem que un nombre primer és un nombre natural -els de comptar 1, 2, 3, etc.- que només es pot dividir enterament entre ell mateix o entre 1. Dit d’altra forma, si el dividim entre qualsevol altre nombre el resultat dona decimal. Per exemple, 7 és primer perquè només es pot dividir entre 1 i ell mateix: 7/7=1 i 7/1=7. Per els altres nombres com per exemple dos, 7/2=3,5; obtenim un decimal i per tant 2 no divideix 7 i així amb la resta. En canvi 8 no ho és, ja que 8/2=4. Com que 2 divideix 8, aquest no és primer. Una particularitat és que el número 1 no es considera primer pel motiu que veurem a continuació.
Els nombres primers són indispensables per aquest mètode per a dues propietats molt importants -i que tenen molta transcendència en totes les matemàtiques més enllà de la criptografia. La primera és que n’hi ha infinits; no s’acaben. Sempre podem trobar un nombre primer més gran que l’anterior. La segona és que tot nombre natural es pot descompondre de forma única en nombres primers.
En aquest sentit, els nombres primers són com els àtoms que constitueixen la resta de nombres. Si prenem qualsevol nombre, per gran que sigui, el podrem expressar com la multiplicació de nombres primers. Així 8 és igual a 2·2·2 o 1625 a 5·5·5·13 i no trobarem primers diferents que multiplicats donin 8 o 1625. Aquest és el motiu pel qual 1 no es considera primer; sinó la descomposició en primers seria única llevat de multiplicar per 1 -ja que no afecta el resultat. En aquest sentit, 8 és igual a 2·2·2 o a 2·2·2·1 o a 2·2·2·1·1, etc.
Quan nosaltres busquem primers mirem si trobem algun divisor del número. Per això, quan mirem si 21 és primer, veiem que no, ja que es pot dividir entre 3 i 7. En canvi, sabem que 19 sí que ho és ja que no es pot dividir ni per 2, ni 3, ni cap altre número -excepte per 1 i ell mateix. En fer-ho estem fent-ne la descomposició en primers. Anomenem factoritzar el fet de buscar aquesta descomposició. En números molt grans és extremadament lent de fer, inclús per als ordinadors potents. El sistema RSA s’aprofita d’aquest fet.
Fem l’encriptació!
El banc busca dos primers molt grans, anomenem-los p i q. Això es pot fer usant un mètode que ens diu si un número és o no primer. Aquest mètode és computacionalment molt més ràpid que el de factoritzar. Així, trobar-los és relativament fàcil. Aquests dos primers els guarda en secret, però abans els multiplica. Diguem n al nombre resultant de la multiplicació, és a dir, n=p·q. El banc fa públic n.
El banc calcula dos números més relacionats amb p, q i n. Un el fa públic juntament amb n i l’altre el manté secret. El teu ordinador, quan ha d’enviar les dades de la teva targeta de crèdit el que fa és elevar i dividir el número usant els dos números públics fins a tenir el número encriptat. Per desencriptar-lo cal fer l’operació inversa.
Què vol dir fer la operació inversa?
Imaginem que el número que volem enviar és 24 i que el procés d’encriptació (un molt senzill per entendre-ho) és sumar-li 5. El número encriptat serà 24+5=29. Per desencriptar-lo només caldrà fer l’operació inversa a sumar 5, en aquest cas restar 5: 29-5=24 i reobtenim el missatge encriptat.
Aquesta encriptació no ens serveix ja que usem el mateix número per encriptar i desencriptar. La gràcia de la criptografia RSA és que per fer el procés invers “només” necessitem factoritzar n en nombres primers. És a dir, descompondre’l com a producte de primers (recordeu que eren com els àtoms de tots els nombres). Això és extremadament difícil si n és molt gran. En canvi, el banc ha creat n multiplicant dos primers (que manté en secret), com que la descomposició és única ja tenim aquesta factorització que volíem.
És a dir, ells poden desxifrar el nostre missatge mentre que un lladre d’internet no, ja que no és capaç de descompondre n.
Com de segur és aquest mètode?
Tot es basa en la dificultat de trobar la descomposició de n, trobar-ne els constituents. Com de difícil és fer-ho? De moment no s’ha descobert un algorisme ràpid per aconseguir-ho. La manera en què es fa no dista molt del que fèiem quan volíem saber si 19 era primer: anar comprovant un a un els possibles divisors. Però, en ser números tan grossos se n’ha de comprovar una quantitat ingent.
Quan Rivest, Shamir i Adleman van proposar el seu sistema l’any 1977, van llençar el repte de descompondre un número de 129 xifres creat a partir de dos primers com abans. No es va aconseguir fins l’any 1994 usant internet i 1600 ordinadors de l’època treballant en xarxa.
114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
Número que van proposar per factoritzar com a repte
A 2020, el número més gran que s’ha aconseguit factoritzar i se n’ha fet el descobriment públic té 250 xifres, i per encriptar s’usen números de més de 600 xifres. Per tant, sembla que estem segurs. Es preveu, però, que si s’aconsegueix desenvolupar amb èxit un ordinador quàntic, el procés de factorització serà bastant més ràpid.
Ja per acabar…
Aquest mètode criptogràfic es basa en gran mesura en el petit teorema de Fermat. Va ser un teorema que va enunciar el matemàtic francès Pierre de Fermat l’any 1636. Aquest teorema ens diu que si agafem un número qualsevol, l’elevem a un primer p i al resultat li restem el número inicial, obtenim un número que es podrà dividir per p (és a dir, p forma part de la factorització).
Vegem-ho amb un exemple, agafem el número 6 i el primer 5. Calculem 6 elevat a 5,
6^5=7776
i ara li restem 6, el resultat segur que es pot dividir per 5, garantit pel teorema,
6^5-6=7776-6=7770
que efectivament té cinc com a divisor, ja que 7770/5=1554. Aquest teorema va ser considerat una curiositat matemàtica durant molt de temps. Ara, en canvi, cada vegada que comprem alguna cosa per internet, escrivim un correu electrònic o fem qualsevol gestió amb el banc, l’estem usant per evitar que ens robin les dades! Això ens dona una idea del poder amagat en moltes de les propietats aparentment ‘inútils’ que es van descobrint en el món de les matemàtiques.
Per saber-ne més
Numberphile – RSA-129
Ramón Antoine, Rosa Camps i Jaume Moncasi – Introducció a l’àlgebra abstracta amb elements de matemàtica discreta
Wikipedia – RSA (cryptosystem)
