RSA | algoritmo usted para cifrar y descifrar mensajes

Conceptos utilizados

RSA utiliza una serie de conceptos de la criptografía:

• Una función unidireccional que es fácil de calcular; encontrar una función que la invierta o calcular esta función es muy difícil.
• El RSA utiliza un concepto llamado logaritmo discreto. Este funciona de forma muy parecida al logaritmo normal: La diferencia es que sólo se utilizan números enteros y, en general, interviene una operación de módulo. Como ejemplo a^x =b, módulo n. El logaritmo discreto consiste en encontrar la x más pequeña que satisface la ecuación, cuando se proporcionan a b y n
• El algoritmo de Shor puede contrarrestarlo.

 

Generación de claves

Las claves para el algoritmo RSA se generan de la siguiente manera:

1. Elija dos grandes números primos aleatorios diferentes p {\displaystyle p} y q {\displaystyle q} . Esto debe mantenerse en secreto.
2. Calcule n = p q {\dice n=pq} .
• n {\displaystyle n} es el módulo de la clave pública y de las claves privadas.
3. Calcule el totiente: ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
4. Elija un número entero e {\displaystyle e} tal que 1 < e < ϕ ( n ) {\displaystyle 1<e<\phi (n)} , y e {\displaystyle e} es coprimo a ϕ ( n ) {\displaystyle \phi (n)} .
   es decir: e {\displaystyle e} y ϕ ( n ) {\displaystyle \phi (n)} no comparten más factores que 1 {\displaystyle 1} : gcd ( e , ϕ ( n ) ) = 1 {\displaystyle \gcd(e,\phi (n))=1} ; Ver máximo común divisor.
• e {\displaystyle e} se libera como el exponente de la clave pública.
5. Calcula d {\displaystyle d} para satisfacer la relación de congruencia d e ≡ 1 ( mod ϕ ( n ) ) {\displaystyle de\equiv 1\\\\\Nde \Nla que se ha hecho un hueco en el mercado de los productos de consumo, y que es la que se ha hecho en el mercado de los productos de consumo, .
   Es decir: d e = 1 + x ⋅ ϕ ( n ) {\displaystyle de=1+x\cdot \phi (n)} para algún número entero x {\displaystyle x} . (Simplemente decir: Calcular d = ( 1 + x ⋅ ϕ ( n ) ) / e {\displaystyle d=(1+x\cdot \phi (n))/e} para que sea un número entero)
• d {\displaystyle d} se mantiene como exponente de la clave privada.

Notas sobre los pasos anteriores:

• Paso 1: Los números pueden ser probados probabilísticamente para la primalidad.
• Paso 3: cambiado en PKCS#1 v2.0 a λ ( n ) = l c m ( p - 1 , q - 1 ) {\displaystyle \lambda (n)={rm {lcm}(p-1,q-1)} en lugar de ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} .
• Paso 4: Una elección popular para los exponentes públicos es e = 2 16 + 1 = 65537 {\displaystyle e=2^{16}+1=65537} . Algunas aplicaciones eligen valores más pequeños como e = 3 {\displaystyle e=3} , 5 {\displaystyle 5} , o 35 {\displaystyle 35} en su lugar. Esto se hace para que el cifrado y la verificación de la firma sean más rápidos en dispositivos pequeños como las tarjetas inteligentes, pero los exponentes públicos pequeños pueden conllevar mayores riesgos de seguridad.
• Los pasos 4 y 5 pueden realizarse con el algoritmo euclidiano ampliado [es]; véase la aritmética modular.

 La clave pública está formada por el módulo n {\displaystyle n\,} y el exponente público (o de cifrado) e {\displaystyle e\,} .
La clave personal está formada por p,q y el exponente privado (o de descifrado) d {\displaystyle d\,} que debe mantenerse en secreto.

• Para mayor eficacia, se puede almacenar una forma diferente de la clave privada:
• p {\displaystyle p} y q {\displaystyle q} : los primos de la generación de la clave;
• d mod ( p - 1 ) { {\bmod {(}p-1)} y d mod ( q - 1 ) {\bmod {(}q-1)} : a menudo llamados dmp1 y dmq1;
• q - 1 mod p {\displaystyle q^{-1}{\bmod {p}} : a menudo llamado iqmp.
• Todas las partes de la clave privada deben mantenerse en secreto en esta forma. p {\displaystyle p\,} y q {\displaystyle q\,} son sensibles ya que son los factores de n {\displaystyle n\,} , y permiten el cálculo de d {\displaystyle d\,} dado e {\displaystyle e\,} . Si p {\displaystyle p\,} y q {\displaystyle q\,} no se almacenan en esta forma de la clave privada, entonces se eliminan de forma segura junto con otros valores intermedios de la generación de la clave.
• Aunque esta forma permite un descifrado y una firma más rápidos mediante el uso del Teorema Chino del Resto (TCR), es considerablemente menos segura, ya que permite los ataques de canal lateral [es]. Esto es un problema particular si se implementa en tarjetas inteligentes, que son las que más se benefician de la mejora de la eficiencia. 
  (Empezar con y ≡ x e ( mod n ) {\año y\año x^{e}!\año!\año!\año}}} , y deja que la tarjeta lo descifre. Entonces calcula ( y d mod p ) {\displaystyle (y^{d}{bmod {p}})} o ( y d mod q ) {\displaystyle (y^{d}{bmod {q}})} , cuyos resultados dan algún valor z {\displaystyle z} . Ahora, induzca un error en uno de los cálculos. Entonces gcd ( z - x , n ) {\displaystyle \gcd(z-x,n)} revelará p {\displaystyle p} o q {\displaystyle q} .)

 

Mensaje de encriptación

Alice da su clave pública ( n , e ) {\displaystyle (n,e)} a Bob y mantiene su clave privada en secreto. Bob quiere enviar el mensaje M {\displaystyle M} a Alice.

Primero convierte M {\displaystyle M} en un número m {\displaystyle m} menor que n {\displaystyle n} utilizando un protocolo reversible acordado conocido como esquema de relleno. A continuación, calcula el texto cifrado c {\displaystyle c\,} correspondiente:

c = m e mod n {\displaystyle c=m^{e}\mod {n}}

Esto puede hacerse rápidamente utilizando el método de exponenciación por cuadrado. A continuación, Bob envía c {\año c\año,} a Alice.

 

Desencriptación del mensaje

Alicia puede recuperar m {\año m\año,} de c {\año c\año,} utilizando su clave privada d {\año d\año,} en el siguiente procedimiento:

Dado m {\displaystyle m\,} , puede recuperar los números primos originales distintos, aplicando el teorema del resto chino a estas dos congruencias se obtiene

m e d ≡ m mod p q {\edstyle m^{ed}\equiv m{\bmod {pq}} .

Así,

c d ≡ m mod n {\displaystyle c^{d}\equiv m{\bmod {n}}} .

Por lo tanto:

m = c d m o d n {\displaystyle m=c^{d}\ mod\ n}

Un ejemplo de trabajo

He aquí un ejemplo de cifrado y descifrado RSA. Los números primos utilizados aquí son demasiado pequeños para permitirnos encriptar algo de forma segura. Puede utilizar OpenSSL para generar y examinar un par de claves real.

1. Escoja dos números primos aleatorios p {\displaystyle p} y q {\displaystyle q\,} :

p = 61 {\displaystyle p=61} y q = 53 {\displaystyle q=53\ } ;

2. Calcule n = p q {\dice n=pq\,} :

n = 61 × 53 = 3233 {\dirección n=61\días 53=3233\} ;

3. Calcule el totiente ϕ ( n ) = ( p - 1 ) ( q - 1 ) {\displaystyle \phi (n)=(p-1)(q-1)} :

ϕ ( n ) = ( 61 - 1 ) ( 53 - 1 ) = 3120 {\displaystyle \phi (n)=(61-1)(53-1)=3120\} ;

4. Elija e > 1 {\displaystyle e>1} coprima a 3120 {\displaystyle 3120\,} :

e = 17 {\dice e=17,} ;

5. Elija d {\displaystyle d\,} para satisfacer e d ≡ 1 mod ϕ ( n ) {\displaystyle ed\equiv 1{\bmod {\phi (n)}} :

d = 2753 {\displaystyle d=2753\,} , con 17 × 2753 = 46801 = 1 + 15 × 3120 {\displaystyle 17\times 2753=46801=1+15\times 3120} .

 La clave pública es ( n = 3233 {\displaystyle n=3233} , e = 17 {\displaystyle e=17} ). Para un mensaje acolchado m {\displaystyle m\,} la función de cifrado c = m e mod n {\displaystyle c=m^{e}{bmod {n}}} se convierte en:

c = m 17 mod 3 233 {\displaystyle c=m^{17}{bmod {3}}233,}

La clave privada es ( n = 3233 {\displaystyle n=3233} , d = 2753 {\displaystyle d=2753} ). La función de descifrado m = c d mod n {\displaystyle m=c^{d}{bmod {n}}} se convierte:

m = c 2753 mod 3 233 {\displaystyle m=c^{2753}{\bmod {3}}233,}

 Por ejemplo, para encriptar m = 123 {\dice m=123} , calculamos

c = 123 17 mod 3 233 = 855 {\displaystyle c=123^{17}{bmod {3}}233=855}

Para descifrar c = 855 {\dice c=855} , calculamos

m = 855 2753 mod 3 233 = 123 {\displaystyle m=855^{2753}{\bmod {3}233=123}

Ambos cálculos pueden ser computados rápida y fácilmente utilizando el algoritmo de cuadrado y multiplicación para la exponenciación modular.

 

Derivación de la ecuación RSA a partir del teorema de Euler

El RSA puede derivarse fácilmente utilizando el teorema de Euler y la función totiente de Euler.

Empezando por el teorema de Euler,

m ϕ ( n ) ≡ 1 ( mod n ) {\displaystyle m^{\phi (n)}\equiv 1{\pmod {n}}

debemos demostrar que al descifrar un mensaje cifrado, con la clave correcta, se obtendrá el mensaje original. Dado un mensaje acolchado m, el texto cifrado c, se calcula mediante

c ≡ m e ( mod n ) {\displaystyle c\equiv m^{e}{pmod {n}}

Sustituyendo en el algoritmo de descifrado, tenemos

c d ≡ ( m e ) d ≡ m e d ( mod n ) {\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m^{ed}{pmod {n}}

Queremos demostrar que este valor también es congruente con m. Los valores de e y d se eligieron para satisfacer,

e d ≡ 1 ( mod ϕ ( n ) ) {\displaystyle ed\equiv 1{\pmod {\phi (n)}}

Es decir, existe algún número entero k, tal que

e d = k × ϕ ( n ) + 1 {\displaystyle ed=k\times \phi (n)+1}

Ahora sustituimos en el mensaje encriptado y descifrado,

m e d ≡ m k ϕ ( n ) + 1 ≡ m × m k ϕ ( n ) ≡ m × ( m ϕ ( n ) ) k ( mod n ) {\displaystyle {\begin{aligned}m^{ed}&\^equiv m^{k\phi (n)+1}\\\\\️&equiv m\️ m^{{k\phi (n)}\️&equiv m\️ ^{k}{pmod {n}}\️

Aplicamos el teorema de Euler y obtenemos el resultado.

m × ( 1 ) k ≡ m ( mod n ) {\displaystyle m\times (1)^{k}\equiv m{\pmod {n}}

 

Esquemas de relleno

Cuando se utiliza en la práctica, el RSA debe combinarse con algún tipo de esquema de relleno, para que ningún valor de M dé lugar a textos cifrados inseguros. El RSA utilizado sin relleno puede tener algunos problemas:

• Los valores m = 0 o m = 1 siempre producen textos cifrados iguales a 0 o 1 respectivamente, debido a las propiedades de la exponenciación.
• Cuando se encripta con exponentes de encriptación pequeños (por ejemplo, e = 3) y valores pequeños de la m, el resultado (no modular) de m e {{displaystyle m^{e}} puede ser estrictamente menor que el módulo n. En este caso, los textos cifrados pueden descifrarse fácilmente tomando la raíz et del texto cifrado sin tener en cuenta el módulo.
• El cifrado RSA es un algoritmo de cifrado determinista. No tiene ningún componente aleatorio. Por lo tanto, un atacante puede lanzar con éxito un ataque de texto plano elegido contra el criptosistema. Pueden hacer un diccionario encriptando probables textos planos bajo la clave pública, y almacenando los textos cifrados resultantes. El atacante puede entonces observar el canal de comunicación. En cuanto vean textos cifrados que coincidan con los de su diccionario, los atacantes podrán utilizar este diccionario para conocer el contenido del mensaje.

En la práctica, los dos primeros problemas pueden surgir cuando se envían mensajes ASCII cortos. En dichos mensajes, m puede ser la concatenación de uno o más caracteres codificados en ASCII. Un mensaje consistente en un único carácter ASCII NUL (cuyo valor numérico es 0) se codificaría como m = 0, lo que produce un texto cifrado de 0 independientemente de los valores de e y N que se utilicen. Del mismo modo, un solo carácter ASCII SOH (cuyo valor numérico es 1) produciría siempre un texto cifrado de 1. Para los sistemas que utilizan convencionalmente valores pequeños de e, como 3, todos los mensajes de un solo carácter ASCII codificados utilizando este esquema serían inseguros, ya que el mayor m tendría un valor de 255, y 255³ es menor que cualquier módulo razonable. Tales textos planos podrían recuperarse simplemente tomando la raíz cúbica del texto cifrado.

Para evitar estos problemas, las implementaciones prácticas de RSA suelen incrustar alguna forma de relleno estructurado y aleatorio en el valor m antes de cifrarlo. Este relleno garantiza que m no entre en el rango de los textos planos inseguros, y que un mensaje dado, una vez acolchado, se cifrará en uno de un gran número de posibles textos cifrados. Esta última propiedad puede aumentar el coste de un ataque de diccionario más allá de las capacidades de un atacante razonable.

Estándares como el PKCS han sido cuidadosamente diseñados para acolchar de forma segura los mensajes antes del cifrado RSA. Como estos esquemas acolchan el texto plano m con algún número de bits adicionales, el tamaño del mensaje sin acolchar M debe ser algo menor. Los esquemas de relleno RSA deben diseñarse cuidadosamente para evitar ataques sofisticados. Esto puede resultar más fácil si se cuenta con una estructura de mensaje predecible. Las primeras versiones del estándar PKCS utilizaban construcciones ad-hoc, que más tarde se descubrió que eran vulnerables a un práctico ataque de texto cifrado elegido adaptativo. Las construcciones modernas utilizan técnicas seguras como el relleno de cifrado asimétrico óptimo (OAEP) para proteger los mensajes y evitar al mismo tiempo estos ataques. El estándar PKCS también cuenta con esquemas de procesamiento diseñados para proporcionar seguridad adicional a las firmas RSA, por ejemplo, el Esquema de Firma Probabilística para RSA (RSA-PSS).

 

Firmar mensajes

Supongamos que Alicia utiliza la clave pública de Bob para enviarle un mensaje cifrado. En el mensaje, ella puede decir que es Alice, pero Bob no tiene forma de verificar que el mensaje procede realmente de Alice, ya que cualquiera puede utilizar la clave pública de Bob para enviarle mensajes cifrados. Así que, para verificar el origen de un mensaje, también se puede utilizar RSA para firmar un mensaje.

Supongamos que Alicia desea enviar un mensaje firmado a Bob. Ella produce un valor hash del mensaje, lo eleva a la potencia de d mod n (igual que cuando descifra un mensaje), y lo adjunta como "firma" al mensaje. Cuando Bob recibe el mensaje firmado, eleva la firma a la potencia de e mod n (igual que al cifrar un mensaje), y compara el valor hash resultante con el valor hash real del mensaje. Si ambos coinciden, sabe que el autor del mensaje estaba en posesión de la clave secreta de Alice, y que el mensaje no ha sido manipulado desde entonces.

Tenga en cuenta que los esquemas de relleno seguro, como el RSA-PSS, son tan esenciales para la seguridad de la firma de los mensajes como lo son para la encriptación de los mismos, y que nunca debe utilizarse la misma clave tanto para la encriptación como para la firma.