RSA (algoritmo)

RSA es un algoritmo de criptografía de clave pública que se basa en la pretendida dificultad de factorizar números grandes, el problema de la factorización .

RSA es sinónimo de Ron Rivest , Adi Shamir y Leonard Adleman , que lo describió públicamente por primera vez en 1978.

Un usuario del sistema RSA crea y publica el producto de dos grandes números primos , junto con un valor auxiliar, como su clave pública.

Los factores primos deben mantenerse en secreto. Cualquier persona puede utilizar la clave pública para cifrar un mensaje, pero con los métodos actualmente publicados, si la clave pública es lo suficientemente grande, sólo alguien con el conocimiento de los factores primos factible descifrar el mensaje.

Ya sea que romper el cifrado RSA es tan difícil como el factoring es una pregunta abierta conocido como el problema del RSA .

Su descubrimiento, sin embargo, no fue revelado hasta 1998 debido a su alto secreto de clasificación, y Rivest, Shamir y Adleman RSA creado de forma independiente del trabajo de los genios.

Adi Shamir, uno de los autores de RSA: Rivest , Shamir y Adleman

El algoritmo RSA fue descrito públicamente en 1978 por Ron Rivest , Adi Shamir y Leonard Adleman en el MIT , las letras RSA son las iniciales de sus apellidos, que figuran en el mismo orden que en el papel.

MIT se concedió la patente de EE.UU. 4.405.829 para un "sistema de comunicación cifrado y el método" que utiliza el algoritmo en el año 1983. La patente habría expirado el 21 de septiembre de 2000 (el plazo de la patente era de 17 años en el momento), pero el algoritmo fue lanzado al dominio público por RSA Security , el 6 de septiembre de 2000, dos semanas antes.


Dado que un documento describe el algoritmo había sido publicado en agosto de 1977, antes de la 12 1977 fecha de presentación de la solicitud de patente , las regulaciones en gran parte del resto de los mundiales impedía patentes en otros lugares y sólo la EE.UU. fue concedida. Si hubiera sido el trabajo de los gallos de conocimiento público, una patente en los EE.UU. no hubiera sido posible.

Desde el DWPI abstracta @ s de la patente,

El sistema incluye un canal de comunicaciones acoplado a por lo menos un terminal que tiene un dispositivo de codificación y por lo menos a un terminal que tiene un dispositivo de descodificación.


Un mensaje-a-ser-se cifra transferida al texto cifrado en el terminal de codificación mediante la codificación del mensaje como un número M en un grupo predeterminado.

Ese número se eleva entonces a una primera potencia predeterminada (asociado con el receptor previsto) y calcula finalmente.


El resto o residuo, C, es ... calculado cuando el número exponenciada se divide por el producto de dos números primos predeterminados (asociado con el receptor previsto).

Operación

El algoritmo RSA consta de tres pasos: clave de la generación, el cifrado y descifrado.


La generación de claves

RSA consiste en una clave pública y una clave privada .

La clave pública puede ser conocida por todos y se utiliza para el cifrado de mensajes. Los mensajes cifrados con la clave pública sólo pueden ser descifrados con la clave privada. Las teclas para el algoritmo RSA se generan de la siguiente manera:

Elija dos distintos números primos p y q.

Por razones de seguridad, los enteros p y q deben ser elegidos al azar, y deben ser de similares bits de longitud. Primeros números enteros pueden ser eficientemente encontrado con un test de primalidad .

Calcular n = pq.
n se utiliza como el módulo , tanto para las claves públicas y privadas Calcular φ (n) = (p - 1) (q - 1), donde φ es la función de Euler totient .

Elija un correo número entero tal que 1 <e <φ (n) y máximo común divisor de (e, φ (n)) = 1, es decir, ey φ (n) son primos entre sí .

e es liberado como el exponente de clave pública.

e que tiene una corta longitud de bits y pequeñas de peso Hamming resultados en el cifrado más eficientes - con mayor frecuencia 0x10001 = 65537.

Sin embargo, los pequeños valores de correo (por ejemplo, 3) han demostrado ser menos seguro en algunos entornos.

Determinar d = e -1 mod φ (n), es decir, d es el inverso de la multiplicación de φ e mod (n).

Esto es más claramente como resolver dada d (d * e) φ mod (n) = 1
Esto a menudo se calcula utilizando el algoritmo de Euclides extendido .
d se mantiene como el exponente clave privada.

La clave pública consiste en el módulo n y el público (o cifrado) e exponente.

La clave privada consiste en el módulo n y lo privado (o descifrado) exponente d que debe mantenerse en secreto.

Notas:

Una alternativa, utilizada por PKCS # 1 , es elegir a juego de d ≡ 1 mod con λ λ = mcm (p - 1, q - 1), donde mcm es el mínimo común múltiplo .

Uso de λ en lugar de φ (n) permite más opciones para d. λ también se pueden definir utilizando la función de Carmichael , λ (n).

El ANSI X9.31 norma prescribe, IEEE 1363 describe y PKCS # 1 permite, que p y q coincida con los requisitos adicionales: ser primos fuertes , y ser tan diferentes que la factorización de Fermat no.

Cifrado

Alice envía su clave pública (N, E) a Bob y lo mantiene en secreto la clave privada. Bob entonces quiere enviar mensaje M a Alicia.

El primero se convierte en M un entero m, de tal manera que 0 <m <n mediante el uso de un protocolo acordado reversible conocido como un esquema de relleno . A continuación, calcula el texto cifrado c correspondiente a

c = m ^ e el texto {(mod} n text {)} .

Esto puede hacerse rápidamente usando el método de exponenciación elevando al cuadrado . Bob entonces transmite c a Alicia.

Tenga en cuenta que al menos nueve valores de m producirá un texto cifrado c igual a m, Pero esto es muy poco probable que ocurra en la práctica.


Descifrado

Alice puede recuperar m de c utilizando su clave privada exponente d a través de la informática

m = c ^ d texto {(mod n} texto {)} .

Dado m , Se puede recuperar el mensaje original M invirtiendo el esquema de relleno.

(En la práctica, hay métodos más eficientes de cálculo c ^ d utilizando los anteriores valores calculados por debajo.)


Usando el algoritmo chino del resto

Para una mayor eficacia muchos de los populares bibliotecas de cifrado (. Como OpenSSL, Java y NET) usar la optimización de los siguientes para el descifrado y firma: Los siguientes valores se calcula previamente y se almacenan como parte de la clave privada:

p y q : Los primos de la generación de claves,
d_P = d texto {(mod p-1} text {)} ,
d_Q = d texto {(mod q-1} texto {)} y
Q_ {Inv} = q ^ {-1} text {(mod p} text {)} .

Estos valores permiten al receptor calcular la exponenciación m = c ^ d texto {(mod pq} texto {)} más eficientemente como sigue:

m_1 = c ^ {d_P} text {(mod p} text {)}
m_2 = c ^ {d_Q} text {(mod} q text {)}

h = Q_ {Inv} * (m_1-m_2) text {(mod p} texto {)} (Si m_1 <m_2 a continuación, algunas bibliotecas, como calcular h Q_ {Inv} * (m_1 + p-m_2) text {(mod p} texto {)} )
m = m_2 + (h * q) ,

Esto es más eficiente que la computación m = c ^ d texto {(mod pq} texto {)} a pesar de que dos exponenciación modular tiene que ser calculada. La razón es que estos dos exponenciación modular tanto utilizar un exponente menor y un módulo más pequeño.

Un ejemplo de trabajo

Aquí está un ejemplo de cifrado y descifrado RSA. Los parámetros utilizados aquí son artificialmente pequeño, pero también se puede usar OpenSSL para generar y examinar un par de claves reales .

Elige dos números primos distintos, tales como

p = 61 y q = 53 .

Calcular n = p q dando

n = 61 · 53 = 3233.

Calcular la totient del producto como Phi (n) = (p-1) (q-1) dando

Phi (3.233) = (61-1) (53-1) = 3120 .

Elija cualquier número 1 <e <3120 que es coprimero a 3120. La elección de un número primo para e nos deja sólo para comprobar que e no es un divisor de 3120.

Dejar e = 17 .

Calcular d , El inverso multiplicativo modular de e texto {(mod} phi (n) text {)} dando

d = 2753 .

La clave pública es ( n = 3233 , e = 17 ). Para un acolchado de texto claro mensaje m , La función de encriptación es m ^ {17} text {(mod 3233} text {)} .

La clave privada es ( n = 3233 , d = 2753 ). Para un cifrado cifrado c , La función de descifrado es c ^ {} texto 2753 {(mod 3233} texto {)} .

Por ejemplo, con el fin de cifrar m = 65 , Calculamos

c = 65 ^ {17} texto {(mod 3233} texto {)} = 2790 .

Para descifrar c = 2790 , Calculamos

m = 2790 ^ {2753} text {(mod 3233} text {)} = 65 .

Ambos de estos cálculos se puede calcular de manera eficiente con el cuadrado y multiplicar el algoritmo de exponenciación modular .


En las situaciones de la vida real los números primos seleccionados sería mucho más grande, en nuestro ejemplo sería relativamente trivial para el factor n , 3233, que se obtiene de la parte posterior de teclas de libre disposición del público a los números primos p y q . Dado e , También de la clave pública, podríamos calcular d y así adquirir la clave privada.

Las implementaciones prácticas utilizar el teorema chino del resto para acelerar el cálculo utilizando el módulo de factores (mod p * q con mod mod p y q).

Los valores de DP, DQ y qInv, que forman parte de la clave privada se calcula como sigue:

dp = d texto {mod} (p-1) = 2,753 texto {mod} (61-1) = 53
dq = d texto {mod} (q-1) = 2,753 texto {mod} (53-1) = 49
qInv = q ^ {-1} text {} mod p = 53 ^ {-1} text {} mod 61 = 38 (Por lo tanto: qInv * q text {} mod p = 38 * 53 texto {} mod 61 = 1 )

Así es como DP, DQ y qInv se utilizan para la decodificación eficiente. (El cifrado es eficiente por la elección de e exponente público)

m1 = c ^ {dp} texto {mod} p = 2,790 ^ {53} text {} mod 61 = 4
m2 = c ^ {dq} text {} mod q = 2790 ^ {49} texto {mod} 53 = 12
h = (qInv * (m1 - m2)) texto {mod} p = (38 * -8) texto {} mod 61 = 1
m = h * m2 + q = 12 + 1 * 53 = 65 (Igual al anterior, pero calcula de manera más eficiente)