Criptografía RSA
La criptografía (la manera en la que mantenemos seguros los mensajes) utiliza matemáticas y números primos en particular.
En esencia, es mucho más fácil multiplicar números primos que calcular qué primos se multiplicaron para formar un número.
Ejemplo: ¿Cuánto es 101 × 131?
Al poco tiempo podemos obtener la respuesta de 13231.
Pero ¿qué pasaría si la pregunta fuera "¿Cuáles son los factores primos de 13231?"
¡Podríamos estar trabajando mucho tiempo en esa pregunta!
Lo mismo se aplica a las computadoras pero los números involucrados son mucho más grandes.
RSA
El algoritmo RSA (que lleva el nombre de sus creadores Rivest, Shamir y Adleman) se basa en esa idea.
Es un algoritmo de cifrado de clave pública/clave privada que utiliza números primos como este:
- Generación de claves: se seleccionan dos números primos
distintos p y q. Suelen ser muy grandes y elegidos al
azar. Se mantienen en secreto pero a partir de ellos creamos tres
números (veremos cómo pronto):
- n = p × q
- e para la clave pública
- d para la clave privada
- Cifrado: el mensaje se divide en bloques y se convierte en formato numérico. Luego, cada bloque se multiplica por sí mismo e veces seguido de "mod n" (mira: función modulo).
- Descifrado: para descifrar el mensaje cifrado, cada número de bloque codificado se multiplica por sí mismo d veces seguido de "mod n" y obtenemos el número original. Haz esto para cada bloque y tendremos los números y el mensaje originales.
La clave pública codifica fuertemente el mensaje.
Pero sólo la clave privada puede decodificarla fácilmente.
Puedes probarlo en RSA Interactivo
Paso a paso
Sigamos los pasos reales usando algunos números pequeños (pero cuando se usan para comunicaciones seguras, los números tienen cientos de dígitos).
Crear claves
- Elige dos números primos distintos p y q: usemos 11 y 17
- Calcula n = pq = 11×17 = 187
- Calcula la función totiente de Euler φ(n) = (p−1)(q−1) = (11−1)(17−1) = 160
- Elige un número e (el número de cifrado) que sea menor que
φ(n) y coprimo a φ(n):
Los números menores de 160 que son coprimos con respecto a 160 incluyen 7, 11, 13 y más. Elijamos 7
- Elige d (el número de decodificación) de modo que
(de) mod φ(n) = 1
- Probemos con d=2: (2×7) mod 160 = 14 mod 160 = 14 (no 1)
- Probemos con d ≈ 1607, digamos 22: (22×7) mod 160 = 154 mod 160 = 154 (no 1)
- Probemos con d=23: 23×7 mod 160 = 161 mod 160 = 1
Ya tenemos nuestras claves:
- Clave pública: 7,187
- Clave privada: 23,187
Codificar el mensaje
Nuestro mensaje es realmente simple: hi (hola en inglés)
- Divide el mensaje en bloques: h e i
- Convierte cada bloque en un número (usemos valores Unicode*): 104 y 105
- Para cada número m calcula me mod n, donde "mod"
es la función del módulo
1047 mod 187 = 179
1057 mod 187 = 96
- Envía ese mensaje: "179,96"
Decodificar el mensaje
- Para cada número recibimos, k, calculamos kd mod n
17923 mod 187 = 104
9623 mod 187 = 105
- Convertir 104,105 a texto: hi
¡Vaya, funciona!
*Unicode es un estándar para convertir caracteres (letras, números, puntuación, etc.) en números. En Unicode a=97, b=98, etc. Podrías usar cualquier sistema que desees, como a=1, b=2, etc.
¡Refuerza tu aprendizaje resolviendo los siguientes retos sobre este tema! (Nota: están en inglés).
