破解RSA密钥

Question

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

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

Answer 1

你的老师给了你:

公钥:(10142789312725007,5)

意思是

n = 10142789312725007
e = 5 

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

另外,你得到了

私钥:(10142789312725007,8114231289041741)

意思是

 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位数,因此必须使用模幂运算技巧.

在"真实世界"中,n显然要大得多.如果你想看到一个真实的例子,说明HTTPS如何在617位n和e为65537的情况下使用RSA ,请参阅我的博客文章" HTTPS连接的前几毫秒 ".

Answer 2

这是一个相对简单的方法来看待它(以及一个可以手工操作的方法).如果你要完全考虑数字,那么你需要考虑的最高因素是sqrt(N):

sqrt(10142789312725007) = 100711415.9999997567

这下面的第一个素数是100711409,比sqrt(N)低6.

10142789312725007 / 100711409 = 100711423 

因此,这是N的两个因素.你的教授很容易 - 诀窍是要认识到没有人会选择一个小的 p或q所以从底部开始你的检查(如在某人发布的python脚本中)是一个坏主意.如果手动实用,那么大的p和q必须靠近sqrt(N).

Answer 3

有各种快速算法来解决的融通问题n给出的n,e和d.您可以在"应用密码学手册" 第8章第8.2.2节中找到对这种算法的一个很好的描述.你可以在网上找到这些章节免费下载这里.

Answer 4

Wolframalpha告诉我,因子是100711409和100711423

我刚写了一个天真的Python脚本来强制它.正如amdfan指出的那样,从顶部开始是一种更好的方法:

p = 10142789312725007
for i in xrange(int(p**0.5+2), 3, -2):
    if p%i == 0:
        print i
        print p/i
        break

这可能会有很大的改进,但它仍然没有问题.你可以通过测试primfactors来改进它,但对于像你这样的小值,这应该足够了.