破解短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

这将为我提供以下密文:

This will give me the following ciphertext:

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如何在底下使用617位 n 和 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屋！