RSA Cripto
RSA Cripto
RSA Cripto
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
26
32
32
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