A descriptografia de RSA

Question

Como podemos descriptografar um RSA mensagem se temos apenas a chave pública?

Por exemplo, Mensagem:21556870,12228498 Chave Pública: (e = 15852553, n = 44331583)

Eu sei que estas fórmulas existir:

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

então a minha ideia era a de que eu poderia colocar o valor de e na primeira fórmula, em seguida, derivar d, que é uma parte da chave privada.No entanto, eu não acho que é matematicamente possível encontrar φ(n) aqui.Então, quanto mais eu posso decifrar uma RSA mensagem com apenas a chave pública?

Answer 1

"Como nós podemos descriptografar um RSA mensagem se temos apenas a chave pública?"

Bem, temos que encontrar a chave privada a partir da chave pública.Isso deve ser muito difícil de fazer em situações práticas, em geral, desde RSA algoritmos são testados pelo tempo testado no campo de segurança, algoritmos, e as pessoas estão usando-o cuidadosamente com longa o suficiente bits em geral.

No entanto, o exercício atribuído a você é projetado para a prática de algoritmo RSA.Os números não são grandes o suficiente para impedir você de obter a chave privada, dada a chave pública. Você deve ser capaz de fazer todos os cálculos por simples de programação utilizando a linguagem de programação favorita e computador.

Tente mais difícil antes de olhar a resposta abaixo.

---

Chave Pública: (e = 15852553, n = 44331583)

Deixe-nos o fator de n.Aqui é um simples programa Python.

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

Execução factor(44331583), obtemos que 44331583 = 5003 * 8861.

Então, φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

Encontrar o inverso de e módulo φ(n).Aqui é um simples programa Python.

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

Execução inverse(15852553, 44317720), obtemos que 15852553 * 1951097 = 1 (mod 44317720).Isto é, o inverso da e módulo φ(n) é d=1951097.

Assim, a chave privada correspondente é (d = 1951097, n = 44331583).

---

Computação m**d (mod n) para descriptografar um RSA (mensagem de um.k.um.mensagem cifrada) m.Aqui é o popular modular-exponenciação função.

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) + ")")

Execução modulo_pow(21556870, 1951097, 44331583) e modulo_pow(71, 15852553, 44331583), obteve-se, respectivamente,

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

Portanto, a mensagem descriptografada é 71,111.Você pode encontrar o que isso significa?

Answer 2

Você vai precisar de levar a base da chave pública RSA para ser capaz de decifrar.Que é de todo o ponto:cracking RSA é equivalente ao factoring, e o factoring é (presumivelmente) muito difícil.