RSA的解密

Question

如果我们只有公钥，我们如何解密RSA消息？

例如, 信息:21556870,12228498 公钥: (e = 15852553, n = 44331583)

我知道这些公式存在:

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

所以我的想法是，我可以把e的值放在第一个公式中，然后推导出作为私钥一部分的d。但是，我认为在数学上不可能找到 φ(n) 这儿。那么，除了公钥之外，我还可以如何解密RSA消息？

Answer 1

"如果我们只有公钥，我们如何解密RSA消息？"

好吧, 我们必须从公钥中找到私钥.这在一般的实际情况下应该太难做到，因为RSA算法是经过时间考验的现场测试的安全算法，并且人们通常使用足够长的位仔细使用它。

但是，分配给您的练习是为您练习RSA算法而设计的。使用的数字不足以阻止您获得给定公钥的私钥。 您应该能够通过使用您最喜爱的编程语言和计算机进行简单编程来完成所有计算。

在查看下面的答案之前，请更加努力。

---

公钥: (e = 15852553, n = 44331583)

让我们考虑一下 n.下面是一个简单的Python程序。

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

跑步 factor(44331583), ，我们得到 44331583 = 5003 * 8861.

所以 φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

求逆 e 模数,模数 φ(n).下面是一个简单的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

跑步 inverse(15852553, 44317720), ，我们得到 15852553 * 1951097 = 1 (mod 44317720).也就是说，逆 e 模数,模数 φ(n) 是 d=1951097.

所以，对应的私钥是 (d = 1951097, n = 44331583).

---

计算/计算 m**d (mod n) 解密RSA消息(a.k.a.).密文） m.这是流行的模幂函数。

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

跑步 modulo_pow(21556870, 1951097, 44331583) 和 modulo_pow(71, 15852553, 44331583), ，我们分别获得,

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

因此，解密的消息是 71,111.你能找到它的意思吗？

Answer 2

您需要考虑RSA公钥的基础才能解密。这就是重点:破解RSA相当于保理，保理（推定为）非常困难。