Módulo n
φ(n) (p − 1)(q − 1)
Clave pública (e, n)
Clave privada d e · d mod φ(n) = 1

Las claves

    Cómo se halla d: el algoritmo de Euclides extendido

    Cada fila divide las dos filas que tiene encima. En la fila con resto 1, la última columna es d (súmale φ(n) si es negativo).

    CocienteRestoCoeficiente de e

    El mensaje

    Carácter Código m Resultado

    Enviado por la red

    BitCuadradoMultiplicar por m

    Romper la clave

    Qué hacer

    Más información sobre RSA

    Demostración del cifrado RSA

    RSA permite que cualquiera cierre un mensaje con tu clave pública, mientras que solo tú puedes abrirlo con tu clave privada. Detrás hay unas pocas líneas de aritmética escolar: dos números primos, una multiplicación, un resto y un ingenioso inverso. Crea un par de claves a partir de primos que elijas tú, cifra y descifra un mensaje carácter a carácter, fírmalo para que cualquiera pueda comprobar que viene de ti y, después, ponte en el papel del atacante y factoriza n para ver por qué las claves reales necesitan cientos de cifras. Elige dos números primos p y q, o pulsa Nuevos primos. La aplicación crea la clave pública (e, n) y la clave privada d, y muestra cómo el algoritmo de Euclides extendido halla d. Escribe un mensaje: cada carácter se cifra con la clave pública y se descifra con la clave privada. Haz clic en una fila para ver la potencia calculada mediante cuadrados sucesivos. Cambia a Firmar para firmar en su lugar con la clave privada, y pulsa Factorizar n para ver lo rápido que se rompen las claves pequeñas.

    Cómo funciona

    1. Introduce dos primos p y q, o elige un tamaño y pulsa Nuevos primos; la aplicación calcula n, φ(n), e y d, y muestra cómo se halla d.
    2. Escribe un mensaje y elige Cifrar o Firmar. Cada carácter se convierte en un número y se eleva a una potencia mod n; haz clic en una fila para ver los cuadrados sucesivos.
    3. Pulsa Factorizar n para que Eve descomponga n en sus dos primos y recupere la clave privada.

    Cómo funcionan las claves

    Multiplica dos primos: n = p × q. Con p = 61 y q = 53, n = 3233. El número φ(n) = (p − 1)(q − 1) = 3120 cuenta los números menores que n que no comparten ningún factor con él, y solo puede calcularlo quien conoce p y q. Elige e = 17, que no comparte ningún factor con 3120, y halla d tal que e × d sea 1 más que un múltiplo de φ(n): aquí d = 2753, porque 17 × 2753 = 46801 = 15 × 3120 + 1. Publica (e, n) y guarda d. Un mensaje m se convierte en c = mᵉ mod n, y el teorema de Euler garantiza que cᵈ mod n devuelve m.

    Por qué es difícil de romper

    Todo lo que necesita un atacante está oculto en los factores de n. Con n = 3233 eso no protege nada: probando divisores impares se encuentra el 53 tras unas dos docenas de intentos. Pero el esfuerzo crece con la raíz cuadrada de n. Un módulo de 2048 bits tiene unas 617 cifras, y ningún método conocido, en ningún ordenador que exista hoy, puede factorizarlo en un tiempo útil. Firmar es aplicar RSA al revés: s = mᵈ mod n solo puede generarse con la clave privada, y cualquiera puede comprobar que sᵉ mod n devuelve m.

    Preguntas frecuentes

    ¿Por qué nadie puede calcular d a partir de la clave pública?

    Para hallar d necesitas φ(n) = (p − 1)(q − 1), y para obtener φ(n) necesitas p y q. Recuperarlos a partir de n significa factorizarlo, y para números de cientos de cifras no se conoce ningún método rápido. La demostración te permite factorizar claves de juguete en una fracción de segundo, lo que muestra exactamente por qué las claves reales son tan grandes.

    ¿Por qué se cifra el mensaje carácter a carácter?

    Porque las claves de juguete son pequeñas: RSA solo puede cifrar un número menor que n. Con n = 3233 cabe el código de cualquier carácter, pero no una frase entera. El RSA real usa un módulo de 2048 bits o más, rellena el mensaje con bytes aleatorios para que el mismo mensaje nunca se cifre dos veces igual y, en la práctica, solo cifra una clave corta para un cifrado más rápido como AES.

    ¿Qué hacen los cuadrados sucesivos?

    Calculan potencias enormes como m²⁷⁵³ mod n sin escribir nunca el número enorme. Escribe el exponente en binario y recorre sus bits: eleva al cuadrado el resultado acumulado en cada bit y multiplica por m en cada 1, tomando cada vez el resto mod n. Un exponente de 2048 bits solo necesita unas 2048 elevaciones al cuadrado.

    ¿Qué diferencia hay entre cifrar y firmar?

    Para cifrar se usa la clave pública del destinatario, de modo que solo la clave privada del destinatario puede deshacerlo. Para firmar se usa la clave privada del remitente, de modo que cualquiera puede comprobar la firma con la clave pública del remitente y saber que el mensaje procede del titular de esa clave y no se ha modificado.

    ¿Se envía mi mensaje a algún sitio?

    No. Todo se calcula en tu navegador, y tus primos y tu mensaje se quedan en el almacenamiento local de este navegador.

    ¿Listo para probarlo?

    Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

    Ir al editor