Descifrado de RSA

Question

¿Cómo podemos descifrar un mensaje RSA si solo tenemos la clave pública?

Por ejemplo, mensaje:21556870,12228498Llave pública: (e = 15852553, n = 44331583)

Sé que existen estas fórmulas:

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

entonces mi idea era que podría poner el valor de e en la primera fórmula y luego derivar d que es parte de la clave privada.Sin embargo, no creo que sea matemáticamente posible encontrar φ(n) aquí.Entonces, ¿de qué otra manera puedo descifrar un mensaje RSA solo con la clave pública?

Answer 1

"¿Cómo podemos descifrar un mensaje RSA si sólo tenemos la clave pública?"

Bien, Tenemos que encontrar la clave privada a partir de la clave pública..Esto debería ser demasiado difícil de hacer en situaciones prácticas en general, ya que los algoritmos RSA son algoritmos de seguridad probados en el tiempo y probados en el campo, y la gente los usa con cuidado con bits lo suficientemente largos en general.

Sin embargo, el ejercicio que se te ha asignado está diseñado para que practiques el algoritmo RSA.Los números utilizados no son lo suficientemente grandes como para impedirle obtener la clave privada dada la clave pública. Debería poder realizar todos los cálculos mediante una programación sencilla utilizando su lenguaje de programación y su computadora favoritos.

Esfuércese más antes de mirar la respuesta a continuación.

---

Llave pública: (e = 15852553, n = 44331583)

factoricemos n.Aquí hay un programa Python simple.

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

Correr factor(44331583), obtenemos que 44331583 = 5003 * 8861.

Entonces φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

Encuentra la inversa de e módulo φ(n).Aquí hay un programa Python simple.

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

Correr inverse(15852553, 44317720), obtenemos que 15852553 * 1951097 = 1 (mod 44317720).Es decir, lo inverso de e módulo φ(n) es d=1951097.

Entonces, la clave privada correspondiente es (d = 1951097, n = 44331583).

---

Calcular m**d (mod n) para descifrar un mensaje RSA (también conocido comotexto cifrado) m.Aquí está la popular función de exponenciación modular.

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

Correr modulo_pow(21556870, 1951097, 44331583) y modulo_pow(71, 15852553, 44331583), obtuvimos, respectivamente,

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

Por lo tanto, el mensaje descifrado es 71,111.¿Puedes encontrar lo que significa?

Answer 2

Necesitará factorizar la base de la clave pública RSA para poder descifrar.Ese es todo el punto: el agrietamiento RSA es equivalente a factoring, y el factoring es (presumido que es) muy duro.