RSA
Los mensajes enviados se representan mediante números, y el funcionamiento se basa en el producto, conocido, de dos números primos grandes elegidos al azar y mantenidos en secreto.
[1] El algoritmo fue descrito en 1977 por Ron Rivest, Adi Shamir y Leonard Adleman, del Instituto Tecnológico de Massachusetts (MIT); las letras RSA son las iniciales de sus apellidos.
Debido al elevado coste de las computadoras necesarias para implementarlo en la época su idea no trascendió.
Dado que Cocks trabajó en un organismo gubernamental, una patente en Estados Unidos tampoco hubiera sido posible.
El algoritmo consta de tres pasos: generación de claves, cifrado y descifrado Supongamos que Bob quiere enviar a Alicia un mensaje secreto que solo ella pueda leer.
Bob envía la caja a Alicia y ella la abre con su llave.
, mediante un protocolo reversible conocido como padding scheme («patrón de relleno»).
a Bob y Alicia mantiene su propia clave privada en secreto.
de la clave privada mediante el siguiente cálculo: Ahora que tiene
El procedimiento anterior funciona porque Esto es así porque, como hemos elegido
Esto muestra que se obtiene el mensaje original: Aquí tenemos un ejemplo de cifrado/descifrado con RSA.
Los parámetros usados aquí son pequeños y orientativos con respecto a los que maneja el algoritmo, pero podemos usar también OpenSSL para generar y examinar un par de claves reales.
Para cifrar el valor del texto sin cifrar 123, nosotros calculamos: Para descifrar el valor del texto cifrado, nosotros calculamos: Los cálculos de potencias grandes y del módulo pueden ser eficientemente realizados por el algoritmo de multiplicación cuadrática para exponenciación modular.
Un mensaje consiste en un solo carácter ASCII NUL (cuyo valor es 0) se codificaría como m=0, produciendo un texto cifrado de 0 sin importar qué valores de e y N son usados.
Probablemente, un solo ASCII SOH (cuyo valor es 1) produciría siempre un texto cifrado de 1.
Para sistemas convencionales al usar valores pequeños de e, como 3, un solo carácter ASCII mensaje codificado usando este esquema sería inseguro, ya que el máximo valor de m sería 255, y 255³ es menor que cualquier módulo razonable.
La última característica es la incrementación del diccionario haciendo este intratable a la hora de realizar un ataque.
Supongamos que Alicia desea enviar un mensaje autentificado a Bob.
Eleva la firma recibida a la potencia de e≡ mod n (como hace cuando cifra mensajes), y compara el resultado hash obtenido con el valor hash del mensaje.
El descifrado completo de un texto cifrado con RSA es computacionalmente intratable, no se ha encontrado un algoritmo eficiente todavía para ambos problemas.
No se ha encontrado ningún método en tiempo polinómico para la factorización de enteros largos.
Si n tiene 256 bits o menos, puede ser factorizado en pocas horas con un ordenador personal, usando software libre.
Si n tiene 512 bits o menos, puede ser factorizado por varios cientos de computadoras como en 1999.
Sin embargo, las computadoras cuánticas no se esperan que acaben su desarrollo hasta dentro de muchos años.
Buscando números primos grandes p y q por el test de aleatoriedad y realizando tests probabilísticos de primalidad los cuales eliminan virtualmente todos los no-primos (eficientemente).
En particular, se debe utilizar un buen generador aleatorio de números primos para el valor empleado.
No son el mismo criterio; un número podría haber sido elegido por un proceso aleatorio, pero si este es predecible de cualquier forma (o parcialmente predecible), el método usado resultará en una baja seguridad.
Aunque valores de e tan bajos como 3 se han usado en el pasado, los exponentes pequeños en RSA están actualmente en desuso, por razones que incluyen el no relleno del texto sin cifrar, vulnerabilidad listada antes.
Supongamos que Eve puede interceptar transmisiones entre Alicia y Bob.
Eve envía a Bob su propia clave pública, como Bob cree que es de Alicia, Eve puede entonces interceptar cualquier texto cifrado enviado por Bob, descifrarlo con su propia clave secreta, guardar una copia del mensaje, cifrar el mensaje con la clave pública de Alicia, y enviar el nuevo texto cifrado a Alicia.
