Cifra RSA

Introducción

RSA es un algoritmo asimétrico de criptografía con clave pública. Muy utilizado en comercio electrónico y para el intercambio de datos confidenciales por internet.

Este algoritmo fue descrito en 1977 por Ronald Rivest, Adi Shamir y Leonard Adleman, lo que explica sus siglas.

La codificación RSA se basa en la factorización de un número entero muy grande. Si [p] y [q] son dos números primos, es fácil calcular su producto [n = p . q] Sin embargo, dado [n], resulta prácticamente imposible encontrar [p] y [q] (es decir factorizar [n]) en un tiempo razonable.

↑↑↑

Elección de la clave

Bob eligió dos grandes enteros naturales primos [p] y [q] (con aproximadamente 100 dígitos cada uno o más) y efectúa su producto n = p . q.

A continuación calcula lo que denominamos indicador de Euler; Ê(n)=(p-1) . (q-1).

Después elige un entero [e] de tal modo que [e] y [Ê] sean números primos entre sí.

Finalmente, publica, por ejemplo en su web, su clave pública (n, e).

Tomemos por ejemplo (p = 53, q = 97, n = 5141, y e = 7) que es efectivamente primo con 52 . 96 = 4992.La clave pública sera la siguiente: (n = 5141, e = 7).

↑↑↑

Cifrado

Alice quiere enviar un mensaje a Bob. Busca en la web la clave publica de cifrado de Bob y comprueba que debe utilizar los números n = 5141 y e = 7. Trasforma su mensaje en números, sustituyendo por ejemplo cada letra por su rango en el alfabeto.

Por ejemplo [je vous aime] (Te quiero) se convierte en [10, 05, 22, 15, 21, 19, 01, 09, 13, 05]

Después, agrupa los dígitos en bloques de la misma longitud, de forma que cada uno de ellos sea un número inferior al valor de [n]. Como en este ejemplo n = 5141, si agrupamos los números de tres(3) en tres cumplimos la condición. (Esta operación es esencial, ya que si dejáramos bloques de dos en dos -en nuestro ejemplo-, estaríamos trabajando con una cifra de sustitución simple que puede ser atacada con un análisis de frecuencias.)

En nuestro caso el mensaje se convierte en:

[10052215211901091305]

Y agrupando los dígitos ….

10052215211901091 305

10052215211901 091 305

10052215211 901 091 305

. . . .

10 052 215 211 901 091 305

Y para que sean todos paquetes de tres dígitos añadimos por la izquierda los ceros que necesitemos. En este ejemplo, solo hay que añadir un cero por la izquierda

010 052 215 211 901 091 305

Cada bloque [B] se cifra mediante la fórmula C=Be (mod n), siendo [C] un bloque cifrado y [B] un bloque en claro.

Tras haber codificado cada bloque, el mensaje cifrado tomara el siguiente aspecto

{0755 1324 2823 3550 3763 2237 2052}

↑↑↑

Descifrado

Bob calcula a partir de [p] y [q] que ha guardado en secreto, la clave [d] de descifrado (es su clave privada). Esta debe satisfacer la ecuación [e x d mod Ê(n) = 1.]

Buscara el numero entero más pequeño posible [m] de tal modo que m . Ê(n) sea divisible por e = 7.

Aquí para [m] tendremos 6 . 4992 + 1 = 7 . 4279, por lo tanto d = 4279

Cada uno de los bloques cifrados [C] se descifran mediante la siguiente formula B = Cd (mod n)

Realizando las operaciones obtenemos 010 052 215 211 901 091 305

Volviendo a agrupar las cifras de dos en dos y reemplazando los números asi obtenidos por sus letras correspondientes, se descubre el mensaje en claro.

Observa que aunque Eva conozca la clave pública (n = 5141, e = 7), no puede descifrar el mensaje, ya que necesitara disponer de la cave secreta (d = 4279), que únicamente conoce Bob. Y, para obtener esa cifra, deberá descomponer [n] en factores primos, lo que ciertamente resulta fácil con el numero [5141], pero que hoy por hoy es imposible con un numero de 200 cifras.

Cifra RSA

Descripción general

[TOC] Tabla de Contenidos

Cifra RSA

Introducción

Elección de la clave

Cifrado

Descifrado

A.2.Enlaces

Codificación
Fecha de creación
Última actualización