Criptosistemes de tipus RSA
Artur Travesa
(versió 2021-04)

Introducció general

L'origen d'aquestes notes es remunta a diferents cursos d'Aritmètica o de Criptografia, a càrrec de l'autor, per a estudiants de Matemàtiques o d'Informàtica de la Universitat de Barcelona.

La idea bàsica és descriure algunes aplicacions importants de l'Aritmètica bàsica (diguem, de nivell de primer curs) a les transmissions xifrades d'informació.

En cap cas es tracta d'un curs de Criptografia, que caldria encabir en espais més amplis de coneixements, que haurien d'incloure, probablement, parts de teoria de la comunicació, de complexitat algorítmica o computacional, d'aprenentatge automàtic, o d'estudi de teories de compartició de secrets, entre d'altres.

El format triat per a la presentació és el d'un notebook de Mathematica, per la facilitat que té aquest programari per a poder desenvolupar els càlculs no trivials de manera prou senzilla i entenedora, d'una banda, i per a permetre fer una presentació escrita prou raonable des del punt de vista de material escrit, de l'altra. En particular, la possibilitat d'incloure els càlculs dins del text de manera natural en fan una bona eina comunicativa i, alhora, facilita molt el càlcul amb exemples no trivials.

A fi de veure tot el contingut del notebook convé executar-lo. Això es pot fer de cop o bé, més recomanable, cel·la a cel·la a mesura que s'avança en la lectura i comprensió dels diferents continguts. 
Observació: Per al cas en què no es disposi del programari, hi ha la versió executada del notebook en format pdf.

Amb la finalitat doble d'una banda, de no fer textos molt llargs o amb molts continguts, i de l'altra de poder ampliar de manera senzilla els continguts que s'hi tractin, el material s'ha dividit en diferents notebooks, que desrivim a continuació, en l'apartat de referències.

Referències

[Cripto-1]: Criptografia bàsica (1).
Travesa, A.: CriptografiaBasica-1; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una iniciació a la codificació de missatges. El criptosistema de Cèsar. El criptosistema de Vigenère.

[Cripto-2]: Criptografia bàsica (2). 
Travesa, A.: CriptografiaBasica-2; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Els criptosistemes lineals. Els criptosistemes afins. Sufixació de missatges. Farciment de missatges.

[Eratostenes]: Un garbell d'Eratòstenes.
Travesa, A.: Eratostenes; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Un garbell d'Eratòstenes.

[Cripto-3]: Primeritat. Construcció de primers. 
Travesa, A.: ConstruccioDePrimers; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Test de primeritat de Solovay-Strassen. Test de primeritat de Miller-Rabin. Un  certificat congruencial de primeritat. Construcció certificada de nombres primers de mida prefixada. Aplicació al càlcul de claus RSA. Aplicació (exercici) al càlcul de claus ElGamal.

[Cripto-4]: Factorització. 
Travesa, A.: Factoritzacio; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Un garbell d'Eratòstenes. Tests de primeritat de Solovay-Strassen i de Miller-Rabin. Un certificat congruencial de primeritat. Un algoritme bàsic de divisó per nombres primers petits. Un algoritme bàsic de divisó per nombres petits. El mètode de factorització de Fermat. El mètode de factorització p-1 de Pollard. El mètode de factorització rho de Pollard.

[RSA]: Criptosistemes de tipus RSA. 
Travesa, A.: RSA; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una descripció bàsica dels criptosistemes de tipus RSA: les claus; xifratge; desxifratge; observacions sobre la seguretat.

[ElGamal]: El criptosistema ElGamal. 
Travesa, A.: ElGamal; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Logaritmes discrets. Una descripció bàsica del criptosistema ElGamal: el grup cíclic; les claus; xifratge i desxifratge.

[RSA-1]: Rivest, R.L.; Shamir, A.; Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21 (1978), p. 120-126. (Received April 4, 1977; revised, September 1, 1977.)

[RSA-Standard]: Jonsson, J.; Kaliski, B.: RFC 3447. Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1. RSA Laboratories, February 2003.

[Tr-1]: Travesa, A.: Aritmetica. Edicions de la Universitat de Barelona, col·lecció UB, n. 25. Barcelona, 1998. ISBN:84-8338-031-5.

Introducció

La sigla RSA prové de les inicials dels cognoms de Ronald L. Rivest, Adi Shamir i Leonard Adleman que, en 1977, van fer la primera descripció practicable d'un criptosistema de clau pública, conegut des de ben aviat per RSA (cf. la referència [RSA-1]).

La seguretat del criptosistema proposat per Rivest, Shamir i Adleman es basa en la dificultat (conjectural) de factoritzar nombres enters arbitraris. En efecte, donats dos nombres primers p, q, el càlcul del seu producte, N=p·q, es pot fer en temps polinòmic en la longitud en bits de p i q; en canvi, no es coneix cap algoritme tal que, donat N, trobi els nombres p i q en temps polinòmic en la longitud en bits de N (el millor algoritme que es coneix actualment és subexponencial). Notem que parlem d'algoritmes clàssics, perquè actualment ja hi ha algoritmes quàntics polinòmics per a resoldre aquest problema.

A continuació proporcionem una descripció i, simultàniament, un exemple de criptosistema de tipus RSA.

1. Les claus

Com succeeix en qualsevol criptosistema de clau pública, cada usuari d'un criptosistema RSA disposa de dues claus: la clau pública, coneguda (o cognoscible) per tothom, i la clau privada, només cognoscible (i coneguda) per l'usuari propietari de la clau.

Tant les claus públiques com les claus privades d'un criptosistema RSA són parelles de nombres naturals.

La clau pública

Una clau pública per a un criptosistema de tipus RSA és una parella (N, e) en la qual N, que s'anomena el mòdul de la clau, és el producte de dos o més nombres naturals primers senars diferents, (Subscript[p, 1]),..., (Subscript[p, r]); a més a més, si M:=mcm((Subscript[p, 1])-1, ..., (Subscript[p, r])-1) designa el mínim comú múltiple dels nombres (Subscript[p, 1])-1, ..., (Subscript[p, r])-1, el nombre e, que s'anomena l'exponent de la clau pública, és un nombre natural menor que M i sense factors comuns amb M; és a dir, e és un nombre natural tal que 1≤e≤M i que mcd(e, M)=1.

Observació 1

La clau pública només conté els nombres N i e i no ha de proporcionar cap informació addicional sobre els nombres primers (Subscript[p, 1]), ..., (Subscript[p, r]) ni tampoc sobre el nombre M.

Observació 2

En moltes descripcions del criptosistema RSA es canvia el mínim comú múltiple, M, pel producte, que coincideix amb el valor de la phi d'Euler de N, ϕ(N)=((Subscript[p, 1])-1)···((Subscript[p, r])-1). Per qüestions de seguretat, però, convé usar M enlloc de ϕ(N) (cf. [RSA-1, secció IX, C], o bé [RSA-Standard, 3.2, pàg. 7]).

La clau privada

La clau privada associada a la clau pública (N, e) és la parella (N, d), on d és l'únic nombre natural menor que M i tal que e·d≡1 (mod M); s'anomena l'exponent de la clau privada.

Restriccions

Observació 2

A fi que les claus d'un criptosistema RSA siguin criptogràficament útils, en el sentit que proporcionin una certa seguretat de privacitat, cal que el problema de la descomposició de N com a producte de nombres primers sigui computacionalment intractable. En l'actualitat (abril de 2021), encara sembla prou segur utilitzar nombres N de l'ordre de 1024 bits que siguin producte de dos nombres primers d'aproximadament 512 bits cadascun, i que satisfacin algunes altres restriccions que detallarem més avall. Una possible construcció de nombres primers d'aquestes mides es detalla en [Cripto-3].

Observació 3

Tot i que en aquests moments sigui suficient una longitud de les claus de 1024 bits, aquestes longituds sovint es dupliquen o, fins i tot, es quadripliquen. Cada cop és més usual utilitzar claus de 4096 bits.

Observació 4

Una altra de les restriccions que cal tenir en compte per als nombres primers p i q és que cal triar-los de manera aleatòria entre els nombres primers p per als quals p-1 és divisible per un nombre primer gran; per exemple, es poden prendre nombres primers p de 508 a 516 bits de manera que p-1 sigui divisible per algun nombre primer d'aproximadament 480 bits.

Observació 5

Un cop triats els nombres primers p i q, cal triar els nombres d i e. La manera més adient de fer-ho és triar primerament d i calcular e a continuació. Per a evitar els atacs a la clau per força bruta, cal que d no sigui previsible; en particular, no pot ésser gaire petit, perquè un criptoanalista podria provar tots els valors menors que una certa fita com a valors de d fins a trobar-lo. Notem que, com que p i q són senars, el nombre M és parell, de manera que d i e són també nombres senars. A la pràctica, es pren a l'atzar un nombre enter d', de la mateixa mida aproximada que M, i se cerca el menor nombre enter d>d' que sigui invertible mòdul M; i, a continuació, es calcula e; o bé es pren com a valor de d un nombre primer triat a l'atzar entre els nombres primers de la mateixa mida aproximada que M.

Notem que el càlcul de la clau privada és senzill per al creador de la parella de claus, perquè coneix els valors (Subscript[p, 1]), ..., (Subscript[p, r]). En canvi, no es coneix cap algoritme polinòmic per a poder calcular d només a partir de N i e.

Observació 6

Els nombres d i e de les claus del criptosistema RSA juguen un paper idèntic; tots dos són nombres naturals i actuen com a tals en els processos de xifratge i de desxifratge; de fet, els nombres d i e són intercanviables. Això permet definir de manera molt senzilla algoritmes de signatura digital per als criptosistemes del tipus RSA.

Exemple

Per a la resta d'aquesta descripció, farem servir els valors següents de p, q, N, d i e. (Els nombres p0 i q0 són primers.)

p0=10223394250696657745547049541395995120684418584824466802584974011498764981401616681070815186151390802302178122231665344108180224113191525070808408691034701;

q0=11452522278093321206485035663495848931701242503536169278573695301471421096715928105987831838742796896790992699854150126748952176288081079459340728485305911;

N0=p0*q0;

e0=;

d0=;

ClauRSAPublica0={N0,e0}

ClauRSAPrivada0={N0,d0}

Mod[d0 e0,LCM[p0-1,q0-1]]==1

2. Xifratge i desxifratge de missatges

Xifratge

Missatges que es poden xifrar

Les unitats de missatge que es poden xifrar amb el criptosistema RSA són els elements de ℤ/Nℤ. En particular, el conjunt d'unitats vàlides de missatge és diferent per a cada usuari, perquè cadascun treballa en un anell diferent, que depèn del seu propi valor de N.

Aquest fet fa necessari que hi hagi un algoritme estàndard, igual per a tots els usuaris del criptosistema, per a convertir els missatges plans que es volen xifrar en nombres mòdul N i, recíprocament, reconvertir els nombres mòdul N que provenen de desxifrar els missatges xifrats en missatges plans. Això es pot fer de manera semblant a com es tracta el problema de la codificació, sufixació i farciment de missatges per a la criptografia elemental (cf. [Cripto-1], [Cripto-2]) i aquí no ens hi entretindrem.

El missatge xifrat

Suposem, per tant, que la unitat de missatge que es vol xifrar per a l'usuari U és un element m de ℤ/Nℤ, on (N, e) és la clau pública de U. L'usuari V que vol xifrar el missatge m per a U, calcula el nombre c:=(m^e) (mod N), amb 0≤c≤N-1; el missatge xifrat associat a m és el nombre natural c.

Observació 7

Notem que aquest càlcul es pot fer molt ràpidament amb l'algoritme binari d'exponenciació mòdul N, i que només cal conèixer les dades m, e i N.

Observació 8

Cal notar que, en el nostre exemple pràctic, c és un nombre de, com a màxim, 1024 bits, perquè N és de 1024 bits.

Desxifratge

Per a desxifrar el missatge, l'usuari U utilitza la seva clau privada (N, d) i calcula el nombre (c^d) (mod N); això reconstrueix el missatge m.

Demostració

En efecte, es té que (c^d) (mod N)=((((m^e)))^d) (mod N)=(m^(e·d)) (mod N). Però, per a cadascun dels nombres primers p que divideixen N, és (m^(e·d))=m (mod p); en efecte, podem aplicar el petit teorema de Fermat, perquè p-1 divideix M=mcm((Subscript[p, 1])-1, ..., (Subscript[p, r])-1) i M divideix e·d-1. Ara, pel teorema xinès del residu, és (m^(e·d))=m (mod N), com calia veure. □

Observació 9

Cal notar que els càlculs que es realitzen per a xifrar el missatge són anàlegs als que es realitzen per a desxifrar-lo.

Exemple (cont.)

La funció següent pren com a entrades una llista d'unitats de missatge i una clau pública RSA i produeix una llista d'unitats de missatge xifrades amb aquesta clau pública.

RSAX0[mc_,clau_]:=Table[PowerMod[mc[[i]],clau[[2]],clau[[1]]],{i,1,Length[mc]}]

Inventem-nos un missatge

Ja disposem d'una parella de claus pública i privada per al criptosistema RSA. Són en una llista anomenada ClauRSAPublica0 i ClauRSAPrivada0.

Ara, ens inventem un missatge (de fet, cinc unitats de missatge).

m1=Table[RandomInteger[{0,N0-1}],{i,1,5}]

Xifrem el missatge

I el xifrem amb la clau pública.

x1=RSAX0[m1,ClauRSAPublica0]

Desxifrem el missatge xifrat

Notem que podem desxifrar-lo exactament igual amb la clau privada.

y1=RSAX0[x1,ClauRSAPrivada0]

y1==m1

3. Observacions sobre la seguretat

Consideracions bàsiques

A l'hora de dur a la pràctica una implementació del criptosistema RSA, cal tenir en compte algunes consideracions.

Mida de les claus

En primer lloc, cal tenir en compte la mida que poden tenir les claus. No és el mateix una mida de claus de 128 o 256 bits, per exemple, que una mida de claus de 1024 o 2048 o 4096 bits. I no és recomanable que en el mateix criptosistema les mides de les claus siguin molt diferents les unes de les altres. A priori, una clau molt llarga pot proporcionar més seguretat que una clau no tan llarga. El fet que alguns usuaris disposessin de claus llargues, podria fer pensar que el criptosistema és molt segur, de manera que qualsevol altre usuari podria triar una clau molt més curta (per exemple, per a facilitar el procés de xifratge/desxifratge, si disposa de menys capacitat de càlcul); però això produiria un punt feble en el sistema, i els atacs a aquest usuari serien més factibles. Al contrari, si la majoria de les claus fossin d'una determinada mida i un usuari triés una clau molt més llarga, això podria fer pensar que els missatges d'aquest usuari són "més interessants" que els altres (per què, si no, cerca més seguretat?) i podria ésser el blanc dels atacs al criptosistema; ell o bé els usuaris amb qui es comuniqués.

Codificació dels missatges

No només això, sinó que si es limita la llargada de les claus, llavors es pot usar un mètode comú per a codificar els missatges com a elements dels diferents anells ℤ/Nℤ, quan N recorre les diferents claus. 
Suposem que la llargada de les claus es fixa entre n+1 i n+k bits. Això significa que tots els nombres N de les claus públiques pertanyen a l'interval (2^n)≤N<(2^(n+k)); llavors, es pot usar una codificació dels missatges plans com a successions de n bits, tothom igual, i una codificació dels missatges xifrats com a successions de n+k+1 bits, també tothom igual. 
En efecte, tots els nombres naturals de l'interval 0≤x<(2^n) són menors que N, per a tot N, de manera que cadascun determina un element únic de ℤ/Nℤ. Un cop xifrat el missatge, tindrem un element y de ℤ/Nℤ, que podrem interpretar de manera única com un nombre enter de l'interval 0≤x<(2^(n+k)), perquè N<(2^(n+k)). D'aquesta manera, els missatges plans poden ésser nombres qualssevol de l'interval 0≤x<(2^n), el mateix per a tothom, i els missatges xifrats seran nombres de l'interval 0≤y<(2^(n+k)), també el mateix per a tothom.

Longitud dels missatges

Una altra consideració que cal tenir en compte a l'hora de fixar la longitud de les claus, i que és vàlida per a tots els criptosistemes en general, és la longitud efectiva dels missatges plans que s'han d'enviar.
Suposem que els missatges plans que cal enviar són molt curts, posem de menys de 16 bits (per exemple, els PIN d'un caixer automàtic són nombres naturals de quatre xifres decimals de manera que podem representar-los amb només 14 bits). No té sentit usar un criptosistema amb claus molt llargues, perquè la quantitat de missatges plans possibles és de (2^16)=65536, una quantitat prou petita com per què qualsevol pugui xifrar-los tots amb la clau pública del destinatari (coneguda per tothom) i comparar els resultats amb el missatge xifrat que li és destinat. Això determina el missatge pla sense necessitat de trencar el criptosistema ni la clau del destinatari, però fa impossible la confiança en la confidencialitat de les comunicacions.
En aquests casos, s'imposa la necessitat de farcir els missatges plans abans de xifrar-los, a fi que els conjunts de missatges plans que poden ésser xifrats siguin molt grans i es puguin evitar, d'aquesta manera, els atacs per força bruta.

Algunes consideracions sobre la seguretat del criptosistema RSA

Observem que, coneguts p i q, es pot calcular M en temps polinòmic i, amb l'algoritme d'Euclides, també es pot calcular el nombre d, invers de e mòdul M, en temps polinòmic.
Recíprocament, existeix un algoritme probabilístic que, coneguts N, e i d, permet (probablement) factoritzar N en temps polinòmic.

Demostració

En efecte. Notem que M és parell i que, per tant, e i d són senars, de manera que e·d-1 és parell. Llavors, podem escriure el nombre e·d-1 en la forma e·d-1=(2^v)·s, amb v≥1 i s senar, sense cap dificultat, perquè coneixem e i d i sabem dividir per 2 tants cops com faci falta. Això produeix els nombres v i s.
Seguidament, prenem a l'atzar un nombre m, 2≤m≤N-2, i calculem (Subscript[x, 0])=(m^s) (mod N) (de nou, podem fer-ho sense dificultat). Ara, amb l'algoritme d'Euclides, calculem t:=mcd((Subscript[x, 0])-1,N). Pot ser que t sigui 1, N, o bé un factor propi de N.
Si t és un factor propi de N, ja hem factoritzat N i acabem.
Si t=N, cal canviar el valor de m.
Finalment, si t=1, calculem (Subscript[x, 1]):=((Subscript[x, 0])^2) (mod N) i, de nou amb l'algoritme d'Euclides, calculem mcd((Subscript[x, 1])-1,N).
I apliquem el mateix algoritme de decisió que més amunt:
si és un factor propi de N, ja hem factoritzat N; si és N, canviem el valor de m; i si és 1, podem repetir el procés: calculem (Subscript[x, 2]):=((Subscript[x, 1])^2) (mod N) i mcd((Subscript[x, 2])-1,N). 
Successivament, podrem repetir el procés fins a arribar, com a màxim, al càlcul de (Subscript[x, v]), perquè es té que (Subscript[x, v])=(m^((2^v)·s))=(m^(e·d-1))=1 (mod N), de manera que mcd((Subscript[x, v])-1,N)=N, i no hauríem aconseguit factoritzar amb aquest valor de m.
El fet que N és compost, producte de r≥2 nombres primers, fa que la probabilitat que un m triat a l'atzar en les condicions anteriors permeti factoritzar N sigui més gran o igual que 1 - (1/(2^(r - 1)))≥(1/2).  Per tant, és d'esperar que només calgui provar uns quants valors de m triats a l'atzar. □

Obervació

Encara que el valor de m es prengui a l'atzar, i diferent de 1 i de -1 mòdul N, el valor de (Subscript[x, 0]) pot ser 1 mòdul N, de manera que mcd((Subscript[x, 0])-1,N)=N i tampoc no factoritzaríem.

Exemple

Suposem, doncs, que coneixem la clau pública (N,e) i la clau privada (N,d). Es tracta de factoritzar N.

n=;

e=;

d=;

Calcul de v i s:

v=0;
s=e d -1;
While[EvenQ[s],s=s/2; v++];

Notem que coneixem els valors de v i de s.

v

s

Fem el càlcul per a un primer valor de m (factorització a la primera).

Prenem a l'atzar un valor de m en l'interval adequat.

m=RandomInteger[{2,n-2}];

m=;

Calculem  (Subscript[x, 0])=(m^s) (mod n) i mcd((Subscript[x, 0])-1,n):

x0=PowerMod[m,s,n];

p1=GCD[x0-1,n]

Mirem si hem factoritzat n:

p1==n

Si surt True és que no hem factoritzat i cal canviar de valor de m; si surt False, és que hem trobat un dels factors de n.

p1==p0

p1==q0

Efectivament, hem factoritzat.

Fem el càlcul per a un altre valor de m (també factorització a la primera).

m=RandomInteger[{2,n-2}];

m=

x0=PowerMod[m,s,n];

p1=GCD[x0-1,n]

p1==n

p1==p0

p1==q0

Efectivament, hem factoritzat, i hem trobat l'altre factor de n.

Fem el càlcul per a un altre valor de m (cal elevar al quadrat).

m=RandomInteger[{2,n-2}];

m=

x0=PowerMod[m,s,n];

p1=GCD[x0-1,n]

Ara no hem factoritzat, perquè hem trobat que el mcd és 1; cal elevar al quadrat.

x1=PowerMod[x0,2,n];

p2=GCD[x1-1,n]

p2==n

p2==p0

p2==q0

Efectivament, també hem factoritzat n.

Fem el càlcul per a un altre valor de m (no factorització).

m=RandomInteger[{2,n-2}];

m=

x0=PowerMod[m,s,n];

p1=GCD[x0-1,n]

p1==n

No hem factoritzat i cal canviar de valor de m.

Fem el càlcul per a un altre valor de m (també cal elevar al quadrat i no factorització).

m=RandomInteger[{2,n-2}];

m=

x0=PowerMod[m,s,n];

p1=GCD[x0-1,n]

Encara no hem factoritzat, perquè hem trobat que el mcd és 1; cal elevar al quadrat.

x1=PowerMod[x0,2,n];

p2=GCD[x1-1,n]

p2==n

Ara, però, hem trobat que el mcd és n i hem de canviar de valor de m.