Descifrado RSA débil con el teorema del resto chino

Requisito previo: Algoritmo RSA

¿Por qué el descifrado RSA es lento?
El descifrado RSA es más lento que el cifrado porque, al realizar el descifrado, el parámetro de clave privada «d» es necesariamente grande. Además, los parámetros – «p y q» son dos números primos muy grandes.

Dados los enteros c, e, p y q, encuentre m tal que c = pow(m, e) mod (p * q) (descifrado RSA para enteros débiles).

Fundamentos:

• RSA es un sistema de cifrado de clave pública que se utiliza para la transmisión segura de mensajes.
• RSA involucra cuatro pasos típicamente:
  (1) Generación de claves
  (2) Distribución de claves
  (3) Cifrado
  (4) Descifrado
• El cifrado de mensajes se realiza con una «clave pública».
• El descifrado de mensajes se realiza con una «clave privada»: parámetros (p, q, d) generados junto con la clave pública.
• La clave privada es conocida únicamente por el usuario, y la clave pública puede ser conocida por cualquier persona que desee enviar un mensaje encriptado a la persona con la clave privada correspondiente.
• Una clave pública representada por dos parámetros n (módulo) ye (exponente). El módulo es un producto de dos números primos muy grandes (p y q como se muestra a continuación). El descifrado de este mensaje requeriría que el usuario factorizara n en dos factores primos (la razón principal, RSA es seguro), y luego encontrar el inverso modular de e, donde radica la tarea difícil.
• Un mensaje de texto se convierte primero al valor decimal respectivo, que es el parámetro ‘m’ que encontramos a continuación. Ahora encriptamos este mensaje haciendo c = pow(m, e) mod (p * q) , donde c es el texto encriptado.

En este código, explotamos valores débiles de módulo y exponente para intentar descifrar el cifrado generando la clave privada al encontrar los valores de p, q y d. En estos ejemplos, intentaremos encontrar d dados p y q.

NOTA:
Aquí, en este ejemplo, estamos usando valores pequeños de p y q , pero en realidad usamos valores muy grandes de p y q para hacer que nuestro sistema RSA sea seguro.

Ejemplos:

Input : 
c = 1614
e = 65537
p = 53
q = 31

Output :
1372

Explanation :
We calculate c = pow(m, e)mod(p * q). 
Insert m = 1372. 
On calculating, we get c = 1614.

Input : 
c = 3893595
e = 101
p = 3191
q = 3203

Output :
6574839

Explanation :
As shown above, if we calculate pow(m, e)mod(p * q)
with m = 6574839, we get c = 3893595

Normalmente, podemos encontrar el valor de m siguiendo estos pasos:

(1) Calcular el inverso modular de e.
Podemos hacer uso de la siguiente ecuación, d = e^(-1)(mod lambda(n)) ,
donde lambda es la función Carmichael Totient .
Lectura : función de Carmichael

(2) Calcular m = pow(c, d)mod(p * q)

(3) Podemos realizar este cálculo más rápido usando el Teorema del Resto Chino,
como se define a continuación en la función
Se pueden realizar lecturas adicionales sobre el Teorema del Resto Chino en
RSA (criptosistema)

A continuación se muestra la implementación de Python de este enfoque:

# Function to find the gcd of two 
# integers using Euclidean algorithm
def gcd(p, q):
      
    if q == 0:
        return p
          
    return gcd(q, p % q)
  
# Function to find the
# lcm of two integers 
def lcm(p, q):
    return p * q / gcd(p, q)
  
# Function implementing extended
# euclidean algorithm
def egcd(e, phi):
      
    if e == 0:
        return (phi, 0, 1)
    else:
        g, y, x = egcd(phi % e, e)
        return (g, x - (phi // e) * y, y)
  
# Function to compute the modular inverse
def modinv(e, phi):
      
    g, x, y = egcd(e, phi)
    return x % phi
  
  
# Implementation of the Chinese Remainder Theorem
def chineseremaindertheorem(dq, dp, p, q, c):
      
    # Message part 1
    m1 = pow(c, dp, p)
      
    # Message part 2
    m2 = pow(c, dq, q)
      
    qinv = modinv(q, p)
    h = (qinv * (m1 - m2)) % p
    m = m2 + h * q
    return m
  
# Driver Code
p = 9817
q = 9907
e = 65537
c = 36076319
d = modinv(e, lcm(p - 1, q - 1))
  
"""
pow(a, b, c) calculates a raised to power b 
modulus c, at a much faster rate than pow(a, b) % c
Furthermore, we use Chinese Remainder Theorem as it
splits the equation such that we have to calculate two
values whose equations have smaller moduli and exponent  
value, thereby reducing computing time.
"""
  
dq = pow(d, 1, q - 1)
dp = pow(d, 1, p - 1)
print chineseremaindertheorem(dq, dp, p, q, c)

Producción :

41892906