Abans que res, demanaré disculpes i comprensió per la poca qualitat del següent text. Aquesta baixa qualitat es deu al fet que tot allò exposat al Hackmeeting va ser fruit de la més absoluta i sorprenent (també per al propi autor) improvització. Considere aquest, un document obert on no només no està tot ben dit (espere que les incorreccions siguen poques) sinó que, a més, falta molt per dir.
Correccions, comentaris i crítiques constructives a topi@phreaker.net
Criptografia
Criptografia de clau pública
Àlgebra modular
Algorisme de creació de claus
Creació de claus RSA6 i codificació d'un missatge
de longitud ridícula
Còm es 'podria' trencar RSA?
Per què no es pot trencar RSA?
A diferència de la criptografia tradicional (o criptografia de clau secreta), en la criptografia de clau pública no existeix una única clau amb la qual codificar i descodificar. N’existeixen dues, cadascuna de les quals invertirà el procés que realitze l’altra.
Si entenem que els missatges poden ser codificats com a
números, per exemple, substituint els caràcters pel seu
corresponent codi ASCII, podem equiparar la codificació a una
operació matemàtica senzilla (com podria ser la
multiplicació):
| Si el missatge a transmetre és, per exemple, 5 |
| i la clau de codificació és (multiplicar per 3) |
| aleshores el missatge codificat serà 15 |
com veiem, ningú que no sàpia que la clau de decodificació és una multiplicació per 3, no podrà deduir que 15 correspon a 5 (una volta descodificat) i el missatge podrà viatjar segur per canals insegurs. Per sort, o per desgràcia, l’RSA és un poc més difícil que no una simple multiplicació, encara que no molt més.
Ara exposarem l’esquema d’un criptosistema de
clau pública, que és el següent:
| Alícia | crea m |
| aplica la clau pública de Benito | |
| envia c | |
| Benito | rep c |
| aplica la clau privada de Benito | |
| obté m |
m: missatge en clar (abans de codificar)
c: missatge codificat
La clau pública de Benito que utilitza Alícia, estarà disponible per tothom, mentre que la privada la conservarà Benito (de la manera més segura possible). Els principis esmentats per Diffie i Hellman, en 1976, asseguren la impossibilitat de deduir la clau privada de la clau pública; açò en RSA queda garantit per la impossibilitat de factoritzar eficientment (com es veu a l'apartat Per què no es pot trencar RSA? )
Per tal de poder fer comprensible, posteriorment, el raonament que justifica l’eficàcia de l’RSA, cal que esmentem un seguit de definicions, comenceu a llevar la pols dels vells llibres de matemàtiques d’EGB (qui diu que hi ha coses que només pertanyen al passat?). De totes maneres, no calen grans coneixements matemàtics per entendre-ho, molt probablement si torneu a aquest apartat després de llegir tot el document ho voreu molt més clar.
| operació mòdul (mod) | residu de la divisió entera entre dos nombres, és a dir, 5 mod 3=2 (ja que 5 dividit entre 3 cap a 1 i ens sobren 2 unitats com a residu) |
| màxim comú divisor (MCD) | donats dos nombres, l’MCD és el nombre més gran que divideix de manera entera tots dos |
| nombre primer | nombre que no pot ser descomposat en factors, és a dir, només és divisible entre 1 i ell mateix (el contrari és ‘nombre compost’) |
| nombres coprimers | dos nombres són coprimers quan no tenen factors comuns diferents d’1, es a dir, el seu MCD és igual a 1 (també s'anomenen 'primers un respecte de l'altre') |
| Z={···, -1, 0, 1, 2, ···} | conjunt de tots els nombres enters, sense decimals |
| Zn={0, 1, 2, ···, n-1} | subconjunt de Z, conjunt de nombres enters entre 0 i n-1 |
| Z*n | subconjunt de Zn, inclou els nombres menors que n i coprimers amb ell |
Aplicant els conceptes anteriors a nombres concrets, tindrem:
| Z15={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} |
| Z*15={1, 2, 4, 7, 8, 11, 13, 14} |
com es veu els nombres comuns a Z*15 i Z15 són tots coprimers amb 15, la resta no
Així, doncs, tenim les expressions següents:
| Suma | 14 + 27=18 (mod 23) | d’una manera més simple és com si realitzem una operació i quan excedim n-1, passem a 0... una mena de cercle viciós (perquè es repeteix, no perquè tinga vicis, eh!) | |
| Resta | 4 - 27=0 (mod 23) | ||
| Multiplicació | 8 · 27=9 (mod 23) |
veiem que si n és un nombre primer:
| Z13={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} | |
| Z*13={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} | com es veu l’única diferència és que el 0 no hi és |
L'indicador d'Euler, fi(n), representa el número de nombres naturals menors o iguals a n i coprimers amb n. fi(n) coincideix amb la quantitat d'elements del conjunt Z*n.
L'indicador d'Euler té les propietats següents:
Aleshores, vist que a l'algorisme RSA, n és producte de dos nombres primers s'acomplirà la relació fi(n)=(p-1)·(q-1)
I sense més preàmbuls, esmentarem el que constitueix la base teòrica de l'RSA: el Petit Teorema de Fermat. Segons aquest teorema donats dos nombres x i n coprimers entre ells (mira què són els nombres coprimers si no ho recordes), es compleix que:
El procés de creació de claus (a part de ser EUA-patentable) és molt simple. Es basa en la correcta elecció de dos nombres primers que permetran generar-ne uns altres, amb unes característiques tals que siga mútuament reversible la transformació feta per l'altre. Abans d'entrar a vore l'algorisme, cal fer un apunt (esperem que obvi): una clau RSA pot tindre qualsevol longitud (de fet, i a tall d'exemple, crearem una clau RSA6... que no riga ningú, una clau de 6 bits també és molt digna!)
Pas a pas:
| Es calcula | n=p·q |
| fi(n)=(p-1)·(q-1) |
A partir de les dades calculades al procés anterior tenim que la parella de nombres (e,n) és la clau pública i la parella (d,n) és la clau privada.
En aquest exemple, per raons òbvies, utilitzem nombres primers realment xicotets respecte d'aquells usats a les aplicacions reals però que serviran al nostre propòsit de la mateixa manera; per exemple,
d'on
l'indicador d'Euler,
Ara generem un valor per a e que siga primer respecte de fi(n), per exemple e=23. Podem comprovar que 23 no té cap factor comú amb 40, ja que MCD(23,40)=1.
Usant l'Algorisme Estès d'Euclides calculem d, que en aquest cas val 7, verifiquem que 23·7 mod 40=1.
| Per tant, tenim el parell de claus següent: | Clau Pública | (23,55) |
| Clau Privada | (7,55) |
Ara codificarem un missatge, per comprovar visualment que l'RSAno és cap engany:
Suposem que el missatge a codificar és: m=43,
el valor 26 seria el missatge codificat per al nostre missatge original. Ningú (ni tan sols els que hem codificat el missatge) podrà recuperar el valor original; només ho podrà fer la persona destinatària que conserva (esperem que ben amagada) la seua clau privada.
Però ara situem-nos a la part d'aquesta persona destinatària: què hem de fer per convertir el valor 26 en el valor original? Doncs el mateix procediment que abans s'ha fet per codificar-lo però amb la clau privada.
Novament la màgia de Fermat es compleix!
Amb l'objectiu fix en donar confiança (i confiar) en l'algorisme que garanteix la privacitat a totes les persones amb independència de la seua extracció social, cultural, política, racial, sexual, etc; estudiem els passos necessaris per deduir la clau privada a partir de la clau pública. Com sabem, la clau pública ens l'ofereixen de diverses maneres (servidors de claus, pàgines web, correu electrònic, CD-ROM, disquet, paper i boli, etc) per tal de poder comunicar segurament. Ara, si fóra possible deduir la clau de descodificació a partir de la de codificació?
Piano, piano... com dirien els companys italians. Els passos a seguir són tan simples com açò:
Sembla clar que el procés és, si més no, tan fàcil com el de creació de les claus però... ha d'haver algun problema que explique per què no es pot trencar RSA?
Com s'ha vist, el procés de creació de claus, la codificació i decodificació són processos que utilitzen operacions simples (multiplicacions, nombres aleatoris, divisions enteres, etc). Aquestos processos es poden realitzar amb algorismes que tenen temps d'execució polinomials.
Un algorisme té un temps d'execució polinomial quan en funció de la seua entrada el temps en que es executat varia amb la relació:
En canvi, un algorisme té un temps d'execució exponencial quan en funció de la seua entrada el temps en que es executat varia amb la relació:
Afortunadament, després de molts anys de mantindre matemàtics treballant dia i nit, encara no s'ha trobat un algorisme de factorització que treballe en temps polinomial. Per tant, amb longituds de clau grans, mentre el procés de creació de claus es realitza en pocs minuts (o fint i tot, menys) la factorització requereix mooooooolts anys com s'observa a la taula següent (per cert, com totes les dades, aquestes no són diferents, en passar d'unes mans a unes altres, ningú no pot assegurar que la font és fiable... però bé, coses pitjors s'han vist!)
| Grandària de la clau | MIPS-any necessaris per a la factorització |
| 512 | 30 000 |
| 768 | 200 000 000 |
| 1024 | 300 000 000 000 |
| 2048 | 300 000 000 000 000 000 000 |
Fent un últim intent de sintetitzar les dificultats de trencar RSApodriem dir: