RSA Cripto

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 2

Si lo escondo, lo encuentras?

Aritmtica del reloj


Para saber ms: cifrado RSA

M Joaquina Berral Yern, Inmaculada Serrano Gmez

El cifrado RSA
Este mtodo se basa en la dificultad de hallar los factores primos de un nmero n que sea producto
de dos primos muy grandes. En principio es lo mismo tener los dos nmeros primos que tener su
producto: dados dos nmeros es fcil multiplicarlos, y dado un nmero es tericamente posible
factorizarlo en producto de nmeros primos1. Pero cuando hablamos de un nmero de tamao 1024
bits (309 cifras en sistema decimal), intentar factorizarlo es computacionalmente impracticable.
Los ordenadores encuentran con rapidez nmeros primos grandes y tambin pueden multiplicarlos
en una milsima de segundo para obtener un resultado de doscientas cifras. Por ejemplo, esto se hace
cada vez que se visita una pgina segura, el navegador genera sobre la marcha una nueva clave de usar
y tirar. Pero, cunto cuesta descomponer en factores primos un nmero con doscientas cifras? Es
prcticamente imposible, esto es lo que garantiza la seguridad del sistema.
El RSA es un algoritmo asimtrico que cifra en bloque y que utiliza una clave distribuida
pblicamente y otra privada guardada en secreto por su propietario. Si dos personas A y B se quieren
comunicar con este mtodo es el receptor B quien tiene toda la clave; el emisor A conoce la parte
pblica de la clave, que sirve para cifrar mensaje. El receptor guarda cuidadosamente la parte privada
de la clave, que sirve para descifrar.
Vamos a ir haciendo todos juntos los pasos que se deben seguir para enviar un mensaje. Para
entender bien el proceso usaremos nmeros pequeos y cifraremos carcter a carcter. Ve calculando
cada uno de los valores de los pasos y completa las tablas.
1. Generacin de las claves (por parte del receptor del mensaje)
Paso 1. El receptor B selecciona dos nmeros primos suficientemente grandes, p y q.
Por ejemplo, p =17 y q =2.
Paso 2. Halla N = p q = 17 2 = 34.
Paso 3. Calcula la funcin indicador de Euler: (N) = (p 1)(q 1) = 16 1 = 16
Esta funcin nos da la cantidad de nmeros primos relativos con N y menores que N. Esto quiere
decir que hay 16 nmeros enteros x, tales que mcd(34, x)=1.
Paso 4. Selecciona un nmero e menor que (N) y tal que mcd(e, (N)) = 1. Tomamos e =3 ya que
mcd(3,16) = 1.

Una forma posible de descomponer un nmero n en sus factores es probar a dividirlo por todos los nmeros
enteros positivos comprendidos entre 2 y la raz de n. Por supuesto, a lo largo del tiempo los matemticos han
inventado otros mtodos de factorizacin ms eficientes, pero ninguno ha conseguido un algoritmo con un
orden de complejidad que permita factorizar en un tiempo razonable nmeros de tamaos como los empleados
en RSA actualmente, aun con la potencia de los mejores ordenadores de hoy en da.
Elaborado por:
SECRETARA DE ESTADO DE
EDUCACIN Y FORMACIN
PROFESIONAL

Profundi a

DIRECCIN GENERAL DE
FORMACIN PROFESIONAL

Si lo escondo, lo encuentras?
Aritmtica del reloj
Para saber ms: cifrado RSA

M Joaquina Berral Yern, Inmaculada Serrano Gmez


Paso 5. Calcula el inverso de e en un reloj con (N) horas. Es decir el nmero d que verifique que:
e d 1(mod (N))
Si e = 3 puedes comprobar que d = 11, si el reloj tiene 16 horas: 3 11 = 33 = 1(mod16)
Precisamente el pequeo teorema de Fermat y el resultado de Euler garantizan que este nmero
existe y es nico. Los clculos anteriores se pueden hacer con relativa facilidad. Para obtener d se
puede usar el Algoritmo extendido de Euclides (consulta el apartado para saber ms)
Paso 6. La clave pblica est constituida por (N, e) = (34, 3) y la secreta por (N, d) = (34, 11)
Ahora que B tiene la clave, anuncia la parte pblica a todo el mundo que nos quiera mandar
mensajes (la misma clave pblica sirve para cualquier persona que se quiera comunicar con l). La
clave secreta la conserva celosamente el receptor. Ese par de claves es tal que an conociendo una de
ellas es casi imposible calcular la otra.
2. Cifrado del mensaje (por parte del emisor)
Para cifrar, el emisor A realiza los pasos siguientes:
Paso 7. Localiza la clave pblica del destinatario para conocer los valores de N y e.
En nuestrao caso: (N, e) = (34, 3)
Paso 8. Utiliza la funcin: C Me (mod N) siendo M del mensaje original y C del cifrado.
Texto claro

Texto expresado en numerous (M)

26

32

Mensaje cifrado C M (mod N)

Paso 9. Enva al destinatario el criptograma C.


3. Descifrado del criptograma por parte del receptor
Paso 10. Si el destinatario B quiere recuperar el mensaje que ha recibido usa su clave privada d para
calcular: M Cd (mod N)
Texto recibido

32

Texto descifrado: D = C (mod N)

26

Texto claro

30

18

21

30

25

Con este ejemplo has aprendido a cifrar usando un sistema de clave pblica pero no olvides que
en realidad es bastante ms complicado ya que en nuestra simulacin se han usado valores de p, q
y e muy pequeos y se ha cifrado carcter a carcter. En la realidad se usan nmeros primos
enormes y se cifra en bloque pero esto requiere el uso de clculos tan enormes que se necesitan
ordenadores de gran potencia para calcularlos.
Elaborado por:
SECRETARA DE ESTADO DE
EDUCACIN Y FORMACIN
PROFESIONAL

Profundi a

DIRECCIN GENERAL DE
FORMACIN PROFESIONAL

También podría gustarte