给定以下 RSA key ，如何确定 p 和 q 的值？
Public Key: (10142789312725007, 5)
Private Key: (10142789312725007, 8114231289041741)
最佳答案
你的老师给了你:
意思是
n = 10142789312725007
e = 5
其中 n 是模数， e 是公共(public)指数。
此外，你被赋予
意思是
d = 8114231289041741
其中 d 是应该保密的解密指数。
您可以通过知道如何将“n”分解为“p”和“q”素因子来“破坏”RSA:
n = p * q
最简单的方法可能是检查从 n 的平方根以下开始的所有奇数:
Floor[Sqrt[10142789312725007]] = 100711415
您将在 4 次尝试中获得第一个因素:
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 是一个特殊的数字，使得
d = e^-1 mod phi(n)
= e^-1 mod (p-1)*(q-1)
我们可以验证这一点
d * e = 40571156445208705 = 1 mod 10142789111302176
这很重要，因为如果您有一条明文消息 m 那么密文是
c = m^e mod n
然后你解密它
m = c^d = (m^e)^d = (m^(e*d)) = (m^(e*e^-1)) = m^1 (mod n)
例如，我可以使用您老师的公钥“加密”消息 123456789:
m = 123456789
这会给我以下密文:
c = m^e mod n
= 123456789^5 mod 10142789312725007
= 7487844069764171
(请注意，“e”在实践中应该大得多，因为对于较小的“m”值，您甚至不会超过 n)
无论如何，现在我们有“c”并且可以用“d”反转它
m = c^d mod n
= 7487844069764171^8114231289041741 mod 10142789312725007
= 123456789
显然，您不能直接计算“7487844069764171^8114231289041741”，因为它有 128,808,202,574,088,302 位数，因此您必须使用 modular exponentiation 技巧。
在“真实世界”中， n 显然要大得多。如果您想查看 HTTPS 如何在幕后使用 RSA 的真实示例，其中包含 617 位 n 和 e 0x2518161521 的 0x2518161521 的 0x2518162521 的 0x2518162521 博文 0x2518162521 0x2318162521"
关于math - 破解短 RSA key ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4078902/