RSA解密python

Question

如果 p、q、a 是随机的，如何求它们？ 我有这个脚本

from Crypto.Util.number import getPrime

p,q = getPrime(256), getPrime(256)
n = p*q
a = getPrime(128)
c1 = (p-a)**2>>128
c2 = (q+a)**2>>128
e = 65537
ct = pow(int.from_bytes(b'qupiya{fake_flag}','little'), e, n)
print(f"{n=}")
print(f"{c1=}")
print(f"{c2=}")
print(f"{ct=}")
print(f"{a=}")
print(f"{q=}")
print(f"{p=}")

我需要解密这个： n=651261764374929430258909543867561877616793872084389010175889519715739035613792432324130447144432955718341297716173462711 6921570790884877938134980599305707 c1=10907285669560468551647268462406489962787063891723057307575398016663082759381321634953803867684535258520696953786905 c2=335826980925287722940800296531333275670665396243438255829051457928307809349340703410415434062259818693740005488773964 ct=21272645883211272398540019866988919058753357633810832359614530347177955773624879528679276882621050051810679897449940237 93619461569137294308259815910038249

我尝试了所有破解 RSA 的工具，但数据库中没有一个

Answer 1

这看起来像是一个家庭作业问题。 所以我只会给你如何做的基本轮廓，但你需要自己做这项工作。

你有

c1

。 您应该可以毫无问题地弄清楚

p-a

是什么。

c1 << 128

和

(c1 + 1) << 128

之间只有一个正方形。 同样，从

c2

你可以找出

q + a

是什么。 所以把这两个数字相加你就知道

p + q

是什么了。我们称这个总和为

s

所以你知道两个素数的乘积

n

以及两个素数的和

s

。

让我们

s = p + q

。 当 x = 0 时，函数 f(x) = x * (s - x) 具有最小值，然后单调增加直到 x = s / 2。因此，进行二分查找，直到找到 x 的值，使得 f( x) = n。 现在您有了两个素因数 x 和 s - x。

您拥有解码消息所需的一切。