破解短 RSA 密钥 [英] Cracking short RSA keys

问题描述

给定以下 RSA 密钥，如何确定 p 和 q 的值是什么?

Given the following RSA keys, how does one go about determining what the values of p and q are?

Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)

推荐答案

你的老师给了你:

公钥:(10142789312725007, 5)

Public Key: (10142789312725007, 5)

这意味着

n = 10142789312725007
e = 5 

其中 n 是模数，e 是公共指数.

where n is the modulus and e is the public exponent.

另外，你得到了

私钥:(10142789312725007, 8114231289041741)

Private Key: (10142789312725007, 8114231289041741)

意思是

 d = 8114231289041741

其中 d 是应该保密的解密指数.

where d is the decryption exponent that should remain secret.

您可以通过知道如何将n"分解为p"和q"素因数来破解"RSA:

You can "break" RSA by knowing how to factor "n" into its "p" and "q" prime factors:

n = p * q

最简单的方法可能是检查从 n 的平方根以下开始的所有奇数:

The easiest way is probably to check all odd numbers starting just below the square root of n:

Floor[Sqrt[10142789312725007]] = 100711415

您将在 4 次尝试中获得第一个因素:

You would get the first factor in 4 tries:

10142789312725007 mod 100711415 = 100711367
10142789312725007 mod 100711413 = 100711373
10142789312725007 mod 100711411 = 100711387
10142789312725007 mod 100711409 = 0 <-- Winner since it evenly divides n

所以我们有

 p = 100711409

现在，

 q = n / p 
   = 10142789312725007 / 100711409
   = 100711423

为什么这很重要?这是因为 d 是一个特殊的数字，使得

Why is this important? It's because d is a special number such that

d = e^-1 mod phi(n)
  = e^-1 mod (p-1)*(q-1)

我们可以验证这一点

d * e = 40571156445208705 = 1 mod 10142789111302176

这很重要，因为如果你有一个明文消息 m 那么密文是

This is important because if you have a plaintext message m then the ciphertext is

c = m^e mod n

然后你解密它

m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)

例如，我可以使用您老师的公钥加密"消息 123456789:

For example, I can "encrypt" the message 123456789 using your teacher's public key:

m = 123456789

这会给我以下密文:

c = m^e mod n 
  = 123456789^5 mod 10142789312725007
  = 7487844069764171

(请注意，e"在实践中应该大得多，因为对于较小的m"值，您甚至不会超过 n)

(Note that "e" should be much larger in practice because for small values of "m" you don't even exceed n)

无论如何，现在我们有了c"并且可以用d"反转它

Anyways, now we have "c" and can reverse it with "d"

m = c^d mod n
  = 7487844069764171^8114231289041741 mod 10142789312725007
  = 123456789

显然，您不能直接计算7487844069764171^8114231289041741"，因为它有 128,808,202,574,088,302 位数字，因此您必须使用 模取幂技巧.

Obviously, you can't compute "7487844069764171^8114231289041741" directly because it has 128,808,202,574,088,302 digits, so you must use the modular exponentiation trick.

在真实世界"中，n 显然要大得多.如果您想查看 HTTPS 如何在幕后使用 RSA 的真实示例，其中 n 为 617 位，e 为 65537，请参阅我的博客文章HTTPS 连接的前几毫秒."

In the "Real World", n is obviously much larger. If you'd like to see a real example of how HTTPS uses RSA under the covers with a 617-digit n and an e of 65537, see my blog post "The First Few Milliseconds of an HTTPS Connection."

这篇关于破解短 RSA 密钥的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！