­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)