�Hola All!


Interesante explicaci�n de Arturo Quirantes, en su blog[1], para hacer un poco m�s entendedor el funcionamiento a alto nivel de RSA.


*As� funciona el algoritmo RSA*

Arturo Quirantes
22 ene 18

RSA, el algoritmo de clave p�blica

Hace unos d�as la Fundaci�n BBVA otorg� su premio Fronteras del Conocimiento a cuatro de los principales impulsores de la criptograf�a de clave p�blica, entre
ellos dos de los creadores del algoritmo RSA. En este post voy a explicaros en qu� consiste ese algoritmo y por qu� es tan importante. Ser� breve y os remitir� a mi libro Cuando la criptograf�a falla para ampliar informaci�n.

Durante centenares de a�os la criptograf�a ha tenido un tal�n de Aquiles. La idea es tomar datos, procesarlos mediante un algoritmo y enviarlos al destinatario. En teor�a, si el algoritmo es robusto los datos estar�n seguros. Pero hay un problema, y es el de las contrase�as. Los algoritmos o sistemas de cifrado necesitan una clave, contrase�a o similar. Y el problema siempre ha sido: �c�mo enviar la clave a los interlocutores? Se puede buscar un sistema f�sicamente seguro (digamos un env�o en malet�n cerrado dentro de un furg�n blindado con guardias armados), pero en ese caso la seguridad no se basar� en sistemas matem�ticos sino f�sicos; adem�s, si tienes un sistema seguro para transportar la clave �por qu� no usarlo para enviar el mensaje?

En los a�os setenta lo imposible comenz� a hacerse realidad. Los investigadores
norteamericanos Whitfield Diffie, Martin Hellman y Ralph Merkle descubrieron el
concepto b�sico a finales de los a�os 70, algo conocido como criptograf�a de clave p�blica (PKC por sus siglas en ingl�s).

Hasta entonces, la criptograf�a era de clave sim�trica, es decir, la misma clave que se usa para cifrar sirve tambi�n para descifrar. La PKC se basa en dos claves, una p�blica y una privada. La p�blica, usada para cifrar, era conocida por todos; pero solamente el poseedor de la clave privada podr�a descifrar el mensaje. Ser�a an�logo a un buz�n de correos, donde d todo el mundo puede meter informaci�n dentro, pero solamente el due�o puede abrirlo con
su llave. De esa forma desaparece la necesidad de enviar la clave de forma segura, porque no tienes m�s que publicarla en Internet y cualquiera podr� usarla.

En teor�a se puede obtener la clave privada a partir de la clave p�blica, pero en la pr�ctica el proceso es muy dif�cil y exigente en t�rminos computacionales; es decir, la PKC basa su fortaleza en problemas dif�ciles. Durante los a�os setenta y ochenta se pusieron a prueba muchos problemas matem�ticos dif�ciles. Uno de ellos finalmente dio origen a un sistema de clave
p�blica conocido con el nombre de RSA, por las iniciales de sus creadores: Rivest, Shamir, Adleman. Fue uno de los m�s importantes hitos que permitieron crear una Internet segura, con p�ginas web protegidas mediante criptograf�a.

El problema matem�tico en que se basa RSA es la factorizaci�n de n�meros primos. Si les doy el n�mero 15, no tardar�n mucho en descubrir que es compuesto; pero si el n�mero es muy grande, obtener su factorizaci�n es una tarea ardua y larga. Vamos, pues, a escoger un n�mero n que sea producto de dos
n�meros primos p y q.

Pero espere, se�or explicador, �c�mo sabemos que p y q son primos? El algoritmo
que nos explican es que debemos intentar dividir p por todos los n�meros enteros inferiores a �l, a ver si alguno da un resto cero. Podemos refinarlo usando solamente los n�meros primos inferiores a la ra�z cuadarada de p, pero a�n as� la tarea es computacionalmente ardua para n�meros grandes.

Lo que se hace es tomar otro algoritmo de primalidad (es decir, que determina si un n�mero es primo o no) que sea m�s sencillo de usar. Uno de ellos, denominado Test de Primalidad de Fermat (TPF) est� basado en el Peque�o Teorema
de Fermat, que dice: "Si p es un n�mero primo, y a es un n�mero cualquiera entre 1 y p, entonces se cumple que la divisi�n a^(p-1) / p tiene resto igual a
uno"

Hay algunos problemas con este test, pero pueden resolverse. No voy a mostrar la resoluci�n aqu� por no extenderme demasiado, pero la tienen en mi libro, as�
que vamos con el algoritmo RSA. La idea es usar la llamada aritm�tica modular. Habitualmente, cuando hacemos la divisi�n c=a/b lo que suele interesarnos es el
cociente. Si a, b son dos n�meros reales, el cociente es c, y el resto es cero.
Si, como en el caso que nos ocupa, se trata de n�meros enteros, entonces el cociente no tiene por qu� ser exacto. Bien, pues en la aritm�tica modular no nos interesa el cociente, sino el resto.

Para esta nueva operaci�n, utilizaremos la notaci�n "mod." Cuando escribimos b mod n ("b m�dulo n") nos estamos refiriendo a "el resto que obtenemos al dividir b por n" Cuando queramos indicar que al dividir a entre n obtenemos resto b, lo escribiremos as�:

a = b mod n

Tambi�n podemos entenderlo diciendo que (a-b) es m�ltiplo entero de n, o que hay un entero k para el que se cumple que a=k*n+b.

Para construir nuestro sistema de PKC partiremos de dos n�meros primos grandes (p, q) y su producto n=p*q. Calculemos tambi�n el n�mero F=(p-1)(q-1). El n�mero n es p�blico, pero p y q no lo son. A continuaci�n crearemos la clave p�blica y la clave privada.

La clave p�blica e ser� un n�mero tal que F y e sean primos relativos. Con "primos relativos" queremos decir que no tengan divisores comunes, es decir, que su m�ximo com�n divisor sea uno. No tienen por qu� ser primos ellos mismos.
Por ejemplo, los n�meros 15 y 14, a pesar de ser n�meros compuestos, son primos
relativos.

La clave privada d es un n�mero que cumpla que e*d mod F = 1; se dice en este caso que d es el inverso (multiplicativo) de e m�dulo F. No siempre existe el inverso multiplicativo, y la condici�n necesaria para que exista inverso es que
los n�meros e y F sean primos relativos. Por eso le hemos exigido esa condici�n
espec�fica al n�mero e.

Ya estamos preparados para cifrar el mensaje M, que vamos a representar mediante un n�mero entero. Para obtener el mensaje cifrado C, realizaremos la siguiente operaci�n:

C = (M^e) mod n

F�jense que tenemos un n�mero M enorme, elevado a una potencia e, pero no importa porque, como ya hemos visto, la aritm�tica modular me permite operar con facilidad. El proceso opuesto, el descifrado, lo realizamos calculando el siguiente n�mero:

M=(C^d) mod n

�Lo ve claro? Seguro que no. El proceso de demostraci�n es algo elaborado (de nuevo, aqu� est� mi libro para una explicaci�n completa), pero el resultado final es ese. Lo importante es que el proceso de cifrado y descifrado es sencillo usado aritm�tica modular, y en ambas ocasiones seguimos los mismos pasos:

- Para cifrar, tomamos e y hacemos C = (M^e) mod n

- Para descifrar, tomamos d y hacemos M = (C^d) mod n

En todo ese proceso, recordemos, e es la clave p�blica, en tanto que d es la clave privada. El producto n=p*q tambi�n es p�blico, de modo que para reventar el problema no hay m�s que factorizar n, obtener el n�mero F y a partir de ah� recuperar d; en la pr�ctica, como n es muy grande, la factorizaci�n no puede realizarse en un tiempo razonable ni con equipos inform�ticos de tama�o razonables.

Posteriormente se han desarrollado otros sistemas de PKI, pero RSA fue el pionero y result� crucial para levantar una Internet segura, y eso ha sido reconocido recientemente con el premio Fronteras del Conocimiento BBVA. Pero hay algo que no entiendo: �Por qu� premiaron a Rivest y Shamir pero no a Adleman? No lo s�, pero se lo merece igual que los dem�s. En cualquier caso enhorabuena a todos, y gracias por haber hecho de Internet un lugar m�s seguro.

NOTA HIST�RICA. En rigor hay que reconocer que los primeros descubridores de la
criptograf�a de clave p�blica no fueron Diffie, Hellman y Merkle. Los brit�nicos James Ellis, Clifford Cocks y Malcolm Williamson hab�an descubierto los principios de la PKC pocos a�os antes. Para su desgracia, trabajaban para la agencia criptoanal�tica brit�nica GCHQ, y su trabajo se mantuvo en secreto durante muchos a�os. Solamente a finales de los a�os 90 se les permiti� hablar de su papel en la PKC. Los norteamericanos se llevaron todo el m�rito.





[1]http://elprofedefisica.naukas.com/2018/01/22/asi-funciona-el-algoritmo-rsa/


-
A reveure!!
Enric
__________________________________________________________________
FidoNet: 2:343/107.1 | beholderbbs.org | fidonet.cat | .es | .ws
InterNet: kishpa(at)kishpa(dot)com | kishpa.com | GPG#0xDCCB8CFC

... La sensaci�n es el �rgano de lo absoluto. (Ludwig Feuerbach)
--- crashmail + golded + binkd
* Origin: Black flag & crossed bones : Eye Of The Beholder BBS! (2:343/107.1)