De Fermat a RSA

Aquesta càpsula explica com una observació que Fermat va anotar en una carta el 1640, sense demostrar-la i sense cap aplicació a la vista, es va convertir tres-cents anys després en la peça que protegeix pràcticament totes les comunicacions d'internet. El camí passa per Euler, per un problema que semblava lògicament impossible, i per una asimetria de l'aritmètica que encara no sabem si és real o només un límit del nostre enginy.

1. El problema que semblava insoluble

Durant milers d'anys, tota la criptografia va compartir una mateixa forma: emissor i receptor comparteixen un secret —una clau— i el fan servir tots dos, un per tancar i l'altre per obrir. El xifratge del Cèsar, la màquina Enigma i els sistemes moderns de clau simètrica funcionen així.

Això arrossega un problema que es coneix com el problema de la distribució de claus, i és més greu del que sembla. Per parlar en secret amb algú, primer cal haver acordat una clau en secret. I per acordar-la en secret cal… un canal segur, que és exactament el que encara no tens. Durant segles l'única solució va ser física: valises diplomàtiques, missatgers, llibres de codis lliurats en mà.

Pitjor encara: amb N persones que vulguin parlar entre elles dues a dues calen N(N−1)/2 claus diferents. Per a mil persones, mig milió de claus. Per a internet, la xifra deixa de tenir sentit.

El 1976, Whitfield Diffie i Martin Hellman van publicar un article que proposava una idea que semblava contradictòria: una clau que serveix per tancar però no per obrir. Si existís, la podries publicar al diari. Qualsevol et podria enviar missatges secrets, i tu series l'únic capaç de llegir-los. Diffie i Hellman van descriure què hauria de fer un sistema així, però no en van trobar cap. El van trobar, un any després, Ron Rivest, Adi Shamir i Leonard Adleman.

2. L'eina bàsica: elevar a potències en aritmètica modular

Tot el que ve depèn d'una operació: calcular a^k mod n. Fer-ho ingènuament —multiplicar a per si mateix k vegades— és inviable quan k té centenars de xifres. La solució és l'exponenciació per quadrats repetits, i és molt més eficient del que sembla.

La idea: en comptes de pujar d'un en un, vas quadrant. Amb a, a², a⁴, a⁸, a¹⁶… arribes a exponents enormes en molt pocs passos, i qualsevol exponent es reconstrueix sumant-ne uns quants, perquè cada número s'escriu en binari.

Una cosa que convé notar: els números mai creixen. Es redueix mòdul n a cada pas, així que tot es manté per sota de n encara que l'exponent sigui astronòmic. Aquesta és la raó per la qual RSA és computable.

3. El petit teorema de Fermat

El 18 d'octubre de 1640, Fermat va escriure a Bernard Frénicle de Bessy explicant-li que si p és primer i a no és múltiple de p, aleshores p divideix a^p−1 − 1. Va afegir que li n'enviaria la demostració «si no temés ser massa llarg». No la va enviar mai, i com passa sovint amb Fermat, no se n'ha trobat cap rastre.

La primera demostració publicada és d'Euler, gairebé un segle després, el 1736. I n'hi ha una que val la pena veure perquè és purament combinatòria:

Fixa't que la cancel·lació final és el pas delicat, i és exactament on entra la primalitat: mòdul un número compost no sempre es pot cancel·lar. És el mateix punt que trencava el teorema xinès del residu amb mòduls no coprimers.

4. La generalització d'Euler i la funció φ

Euler no es va aturar a demostrar-lo: el va estendre a mòduls qualssevol. Per fer-ho va definir φ(n), la quantitat d'enters entre 1 i n que no comparteixen cap factor amb n. Aleshores, per a tot a coprimer amb n:

$$a^{\phi \left(n\right)}\equiv 1\left(\mathrm{mod}n\right)$$

Quan n = p és primer, tots els números de 1 a p−1 hi són coprimers, φ(p) = p−1, i es recupera Fermat com a cas particular.

El que fa φ utilitzable és que es calcula a partir de la factorització: és multiplicativa sobre factors coprimers, cosa que surt del teorema xinès del residu. Per a n = p·q amb p i q primers diferents:

$$\phi \left(pq\right)=(p-1)(q-1)$$

I aquí hi ha la trampa que fa possible RSA: calcular φ(n) és tan difícil com factoritzar n. Si saps que 55 = 5·11, φ(55) = 4·10 = 40 és immediat. Si només veus 55 i no en coneixes els factors, no tens cap drecera.

5. Per què funciona RSA

Amb Euler a la mà, la construcció és sorprenentment curta.

Que desxifrar desfaci exactament el xifratge és el que cal comprovar. Per construcció, e·d ≡ 1 (mod φ(n)), és a dir e·d = 1 + k·φ(n) per a algun enter k. Aleshores:

$$c^d={\left(m^e\right)}^d=m^{1+k\phi \left(n\right)}=m·{\left(m^{\phi \left(n\right)}\right)}^k$$

I pel teorema d'Euler el parèntesi val 1, així que tot plegat és m. El missatge torna intacte.

Un detall tècnic honest: aquest argument suposa que m és coprimer amb n. Quan no ho és —quan m és múltiple de p o de q— el teorema d'Euler no s'aplica directament, però el resultat continua sent cert. Es demostra amb el teorema xinès del residu, comprovant la igualtat per separat mòdul p i mòdul q. És per això que RSA necessita que n sigui producte de primers diferents.

6. Què fem a l'element interactiu

Les tres vistes recorren el camí sencer, i cadascuna alimenta la següent.

A «El teorema» hi ha la taula de totes les potències a^k mod n. Arrossegant la barra de l'exponent il·lumines una columna i el comptador et diu quantes bases hi donen 1. Amb un mòdul primer, el comptador s'omple de cop justament a l'exponent p−1. Amb un de compost, les files de bases no coprimeres es marquen en vermell i no arriben mai a 1 —són exactament les que el teorema exclou—, i la primera columna plena apareix abans, a λ(n).

A «Les claus» tries p i q i es construeix tot el sistema: n, φ(n), les e vàlides, i la d calculada amb Euclides estès escrit pas a pas. Les caselles estan acolorides per recordar què és públic (verd) i què és secret (vermell).

A «Xifrar» escrius una paraula i veus cada lletra convertida en número, xifrada i desxifrada. A sota hi ha el càlcul complet d'una lletra per quadrats repetits, amb tots els quadrats intermedis.

7. Recorregut complet: construir un sistema i xifrar

8. Per què és segur (i què vol dir «segur» aquí)

Val la pena ser precís sobre què se sap i què no. Ningú ha demostrat que RSA sigui segur. El que se sap és que trencar-lo pel camí evident requereix factoritzar n, i que ningú ha trobat cap manera ràpida de factoritzar.

L'asimetria és brutal. Multiplicar dos primers de 1.024 bits és instantani. El millor algorisme conegut per desfer-ho, el garbell general del cos de nombres, té un cost que creix de manera subexponencial: prou lent perquè, amb claus de 2.048 bits, superi qualsevol capacitat de còmput imaginable amb la tecnologia actual.

Però «no s'ha trobat» no és «no existeix». No hi ha cap demostració que factoritzar sigui difícil. I ja sabem que amb un ordinador quàntic prou gran no ho seria: l'algorisme de Shor, publicat el 1994, factoritza en temps polinòmic. Cap ordinador quàntic actual s'hi acosta ni de lluny, però la possibilitat és el motiu pel qual s'estan estandarditzant sistemes «postquàntics» basats en problemes diferents.

9. Aparicions fora de les matemàtiques

El cadenat del navegador. Cada connexió HTTPS comença amb un intercanvi de clau pública. Avui la part de xifratge sovint la fan corbes el·líptiques, però l'esquema conceptual —clau pública per acordar, clau simètrica per parlar— és el que van inventar Diffie, Hellman i RSA.

Signatures digitals. El mateix mecanisme al revés: xifres amb la clau privada i qualsevol ho verifica amb la pública. Com que només tu tens la privada, això prova que el missatge ve de tu. És el que fa que el teu telèfon accepti una actualització i rebutgi un programari manipulat.

Passaports i targetes. Els xips dels passaports biomètrics, del DNI electrònic i de les targetes bancàries fan aritmètica modular amb claus RSA per demostrar que són autèntics sense revelar el seu secret.

Test de primalitat. Fora de la criptografia, el teorema de Fermat és la base del test de Fermat: si aⁿ⁻¹ ≢ 1 (mod n) per a alguna base a, aleshores n és compost amb tota seguretat, i sense haver-lo factoritzat. És l'avantpassat dels tests de Miller–Rabin que fan servir tots els sistemes que necessiten generar primers grans —incloent-hi, irònicament, la generació de claus RSA.

10. Curiositats

Ja s'havia inventat, però era secret. El 1973, quatre anys abans de RSA, Clifford Cocks va descriure essencialment el mateix sistema mentre treballava al GCHQ britànic. Estava classificat i no es va desclassificar fins al 1997. Cocks no va rebre cap crèdit públic durant vint-i-quatre anys, i el seu descobriment no va tenir cap efecte sobre el món precisament perquè era secret —una ironia notable per a un sistema el propòsit del qual és fer públic el que abans era secret.

Les paraules màgiques són l'aufrany llepafils. El 1977, Martin Gardner va publicar a Scientific American un repte de RSA amb una clau de 129 dígits, i va escriure que trencar-la requeriria una quantitat de temps astronòmica amb els algorismes coneguts. Es va trencar el 1994, amb 600 voluntaris coordinats per internet i vuit mesos de càlcul. El missatge amagat era «the magic words are squeamish ossifrage», una frase escollida perquè fos impossible d'endevinar. Cap dels tres autors de RSA havia previst internet.

Els números que enganyen el test de Fermat. Hi ha compostos que passen el test de Fermat per a totes les bases coprimeres: es diuen nombres de Carmichael. El més petit és 561 = 3·11·17. Són prou rars perquè el test sigui útil a la pràctica, però prou reals perquè calgui una versió més forta (Miller–Rabin). El tercer nombre de Carmichael és 1729, el mateix número del taxi que Ramanujan va reconèixer des del llit d'hospital com el més petit expressable com a suma de dos cubs de dues maneres diferents.

Fermat no va demostrar res. El «petit» teorema es diu així per distingir-lo del «gran» o «últim» teorema de Fermat, aquell que va anotar al marge dient que en tenia una demostració meravellosa que no hi cabia. Del petit tampoc no en va donar cap demostració —i en aquest cas la comunitat matemàtica només va haver d'esperar 96 anys, no 358.

El nom hauria pogut ser un altre. L'ordre dels cognoms a «RSA» es va decidir alfabèticament. Adleman, de fet, va estar a punt de demanar que no el hi posessin: considerava que la seva contribució havia estat sobretot trencar les propostes prèvies de Rivest i Shamir fins que una va resistir.

11. Connexió amb altres àrees

Aquesta càpsula tanca el bloc recollint-ne totes les peces. El sedàs i el ritme dels primers proporciona la matèria primera: RSA necessita primers grans, i el fet que n'hi hagi molts —conseqüència directa del teorema dels nombres primers— és el que fa possible generar-ne a l'atzar en mil·lisegons. Si els primers fossin escassos, el sistema no existiria.

Rellotges que encaixen hi apareix dues vegades: per demostrar que φ és multiplicativa i, sobretot, en el pas final de la demostració de correcció, quan el missatge no és coprimer amb n. A la pràctica, el teorema xinès del residu també és el que fa que desxifrar sigui unes quatre vegades més ràpid, calculant per separat mòdul p i mòdul q.

Reciprocitat quadràtica comparteix el terreny: els residus quadràtics mòdul un primer són el cas e = 2, i entendre quan una cosa és quadrat mòdul n és una peça de molts altres criptosistemes.

Cap a l'àlgebra, el marc natural de tot això és la teoria de grups. Els invertibles mòdul n formen un grup de φ(n) elements, i el teorema d'Euler no és més que el teorema de Lagrange aplicat a aquest grup: l'ordre de qualsevol element divideix l'ordre del grup, i per tant elevar a φ(n) torna a la identitat. Quan a Taules de Cayley comprovis que elevar un element a l'ordre del grup dona sempre l'element neutre, estaràs demostrant el teorema de Fermat sense saber-ho.