RSA

Rivest Shamir Adleman

Introduccion

RSA es uno de los algoritmos de encriptación mas usados para la transmisión segura de datos a través de canales inseguros.

Esta basado en la siguiente idea, es muy simple multiplicar números, especialmente con computadoras. Pero puede ser mas difícil factorizar números.

Introduccion

Por ejemplo, si queremos multiplicar dos números como 34537 y 99991, es suficiente con utilizar una calculadora y nos dará el resultado 3453389167. Pero el problema inverso es mucho mas difícil. Supongamos que tenemos el numero 1459160519, la única pista que tenemos es que se obtiene de multiplicar dos números enteros. Podemos saber cuales son?

Introduccion

Es un problema mucho mas difícil. Una computadora puede factorizar este numero con bastante rapidez, pero lo hace al tratar con todas las combinaciones posible.Sin embargo, no es difícil de comprobar si un número es primo (en otras palabras, para comprobar que no se puede factorizar) . Si no es primo, es difícil factorizar, pero si es primo, no es dificil demostrarlo.

RSA

La encriptación con RSA trabaja de manera similar. Si tenemos dos números primos p y q que tienen 100 o 200 dígitos cada uno, estos serán nuestra clave privada, los multiplicaremos para obtener un numero N = pq . Este numero N es básicamente nuestra clave publica. Es relativamente fácil para nosotros obtener N, solo necesitamos multiplicar dos números.

RSA

Pero si conocemos solamente N es casi imposible encontrar p y q . Para obtenerlos necesitamos factorizar N, lo cual es un problema increíblemente difícil.

Pero como es usado N para codificar un mensaje, y como p y q son usados para decodificarlo?

Ejemplo

Supongamos que la persona A quiere hacer una clave publica y que la persona B quiere usar la clave para enviar a la persona A un mensaje. En este ejemplo supondremos que el mensaje que A envía a B es solamente un numero. Asumimos que A y B han acordado un método para codificar su texto en números.

Paso 1

La persona A selecciona dos números primos. P = 23q = 41

** Hay que tener en cuenta que en la practica se debería seleccionar un numero m.ucho mas largo

Paso 2

La persona A multiplica p y q para obtener pq = (23)(41) = 943

943 es la clave publica, la cual proporcionara a la persona B (y al resto del mundo si quisiera)

Paso 3

La persona A tambien escoge otro numero e el cual debe ser relativamente primo para (p-1)(q-1). En este caso, (p-1)(q-1) = (22)(40) = 880, de manera que e = 7 servirá. e es también parte de la clave publica, por lo tanto la persona B también debe saber el valor de e.

Paso 4

Ahora la persona B tiene la información necesaria para codificar el mensaje a la persona A. Para este ejemplo el mensaje será

M = 35

Paso 5

B calcula el valor de C =

Paso 6

(mod 943) = 545

El numero 545 es el mensaje codificado que B envía a la persona A.

Paso 7

Ahora A quiere decodificar 545. Para hacerlo, necesita encontrar un numero d tal que ed = 1 ( mod ( p-1 ) ( q-1 ) ) ,o en este caso así como 7d = 1(mod 880)

Una solución es d = 503 , ya que7 * 503 = 3521 = 4 (880) + 1 = 1 (mod 880)

Paso 8

Para encontrar la decodificación. A debe calcular

Esto parece un calculo complicado, y así es, pero notemos que 503 = 256 + 128 + 64 + 32 + 16 + 4 + 2 + 1( es solo la expansión binaria de 503) lo que significa que

Paso 8

Pero solamente nos importa el resultado de (mod 943), podemos calcular todos los resultados parciales . Por ejemplo

Y así sucesivamente obtenemos lo siguiente.

Paso 8

Paso 8

De manera que el resultado que necesitamos es

Usando este algoritmo , la persona A decodifico el mensaje de B y obtuvo el mensaje original

M = 35

Cryptool y RSA

Para la demostración de nuestro ejemplo usaremos cryptoolEn el menu

Cifrar/Descifrar >> Asimétrico

>> RSA DemostraciónIngresaremos los 2 números primos de nuestra clave privada y el numero e de nuestra clave publica y el texto a cifrar (en nuestro caso el numero 35)

Encryptar usando Cryptool

Para encryptar un mensaje usando el algoritmo RSA primero debemos generar una llave PKI la cual debe poseer tanto el emisor como el receptor. Esto lo hacemos desde el menu “Firma Digital/PKI” de cryptool

Generando la clave PKI

Para generar la clave se solicitaran nombre y apellido y ademas un “PIN” el cual es importante para la desencriptacion del mensaje. Sin este codigo no sera posible realizar esta tarea. Este codigo tambien debe saberlo el receptor.

Encriptar

Nos dirigimos al menu de encriptar / desencriptar de cryptool

Y seleccionamos la clave PKI con la que vamos encryptar nuestro mensaje

Y obtenemos nuestro texto cifrado utilizando una llave PKI

Desencriptar

Para desencriptar el procedimiento es similar, utilizamos la misma llave con la que encriptamos y se nos solicitara el codigo PIN que ingresamos al generar la clave PKI

RSA Desencriptar

Y obtenemos nuestro mensaje original

que en nuestro caso era el numero 35.