Accueil > Día escolar de las matemáticas 2014 > Concurso RSA > Criptosistema RSA

Criptosistema RSA

En 1977, Ronald Linn Rivest, Adi Shamir y Leonard Adleman crean el sistema de encriptación de clave pública, el RSA (iniciales de sus creadores), basado en los números primos y en la dificultad de entrar la descomposición factorial de un número cualquiera.

El RSA consta de dos claves : una pública, que todo el mundo conoce, y otra privada que solo conoce el propietario. Veamos como funciona.

Se toman dos números primos p y q, con ellos generamos  n = p \cdot q

Usando la función de Euler \phi , que nos da el número de números primos con n, menores o iguales a n, obtenemos \phi(n) .

 \phi(n)= \phi(p \cdot q)= (p-1)\cdot(q-1)

Para generar la clave pública buscamos un número primo con \phi(n) y menor que \phi(n) . A este número le llamamos e.

El siguiente paso es encontrar un número, que normalmente se desgina con la letra d, de forma que su producto con e se pueda dividir entre \phi(n) dando como resto 1, es decir, que d · e -1 sea divisible entre \phi(n) , o como diría Gauss  d=e^{-1} mod \ph(n) , d es el inverso modular de e mod \phi(n) .

Como resultado obtenemos dos números e y d que nos permitirán crear nuestro sistema de encriptación. ¿Cómo encriptar con este método ?

El texto cifrado, C, de un mensaje de texto normal P, se transmite por la regla :

 C=P^e \ mod \ n

El texto cifrado lo descifra el receptor de acuerdo a la regla :

 P = C^d \ mod \ n

Ejemplo

Lo primero que necesitamso es una tabla para codificar las letras :

Elegimos dos números primos p y q, por ejemplo : p=13 q= 17. Por tanto, n= 221 y
\phi(n) = 192 .

Bien, ahora podemos elegir e, cumpliendo la condición m.c.d.(e, \phi(n) =1. Tomamos e=47.

Para encontrar d tenemos que asegurarnos que d ·e -1 es divisible por 192, podemos tomar por ejemplo d=143.

Ya tenemos nuestro sistema montado :
Clave pública (e,n)=(47, 221) y la clave privada (d,n)=(143,221).

Ya podemos cifrar la palabra SENO

Observando la tabla anterior, SENO se codifica como 20 5 14 16
Ahora encriptamos con nuestra clave pública.

20  20^{47} \ mod \ 221 210
5  5^{47} \ mod \ 221 177
14  14^{47} \ mod \ 221 79
16  16^{47} \ mod \ 221 152

El mensaje encriptado es 210 177 79 152

Para desencriptarlo solo tenemos que hacer el proceso con la d.

210  210^{143} \ mod \ 221 20
177  177^{143} \ mod \ 221 5
79  79^{143} \ mod \ 221 14
152  152^{143} \ mod \ 221 16

Répondre à cet article