RSA 素数对称式泄露

原理

RSA 加密需要两个大数，p 和 q（这两个都是质数）

把 p 和 q 乘起来，得到 n（也就是 n = p * q），n 是公开的

如果要解密，就必须把 n 拆回 p 和 q。正常情况下，这几乎不可能做到，因为 p 和 q 太大了

但如果生成 p 和 q 时偷了懒，让它们之间存在某种 “对称” 关系，攻击者就能利用这个关系轻松地把 n 分解开

实战案例

EasyRSA（素数对称式泄露）

pasted_1784305467850_tpvmb4.png

题目给出条件

1
z = Fraction(1, Derivative(arctan(p), p)) - Fraction(1, Derivative(arth(q), q))

  • Derivative(arctan(p), p)：求反正切函数对 p 的导数

  • 我们知道 d(arctan(p))/dp = 1 / (1 + p²)

  • Fraction(1, ...)：用 1 除以这个导数

  • 所以第一项变成：1 / (1/(1+p²)) = 1 + p²

  • 第二项：Derivative(arth(q), q)，其中 arth 是反双曲正切函数

  • 它的导数是 d(arth(q))/dq = 1 / (1 - q²)

  • 再用 1 除以它，得到：1 / (1/(1-q²)) = 1 - q²

  • 最后相减：z = (1 + p²) - (1 - q²) = p² + q²

所以这行代码实际计算的是 z = p² + q²，又因为 n = pq

利用完全平方公式

1
2
3
4
5
(p + q) ^ 2 = p ^ 2 + 2pq + q ^ 2
            = z + 2n

(p - q) ^ 2 = p ^ 2 - 2pq + q ^ 2
            = z - 2n

因此

pasted_1784316507559_o2s682.png

pasted_1784316551011_rcndmv.png

令：

1
2
s = p + q = sqrt(z + 2n)
t = p - q = sqrt(z - 2n)

假设 p > q，则

pasted_1784316614375_izk9gl.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from math import isqrt
from Crypto.Util.number import long_to_bytes, inverse

e = 65537

c = int("7922547866857761459807491502654216283012776177789511549350672958101810281348402284098310147796549430689253803510994877420135537268549410652654479620858691324110367182025648788407041599943091386227543182157746202947099572389676084392706406084307657000104665696654409155006313203957292885743791715198781974205578654792123191584957665293208390453748369182333152809882312453359706147808198922916762773721726681588977103877454119043744889164529383188077499194932909643918696646876907327364751380953182517883134591810800848971719184808713694342985458103006676013451912221080252735948993692674899399826084848622145815461035")
z = int("32115748677623209667471622872185275070257924766015020072805267359839059393284316595882933372289732127274076434587519333300142473010344694803885168557548801202495933226215437763329280242113556524498457559562872900811602056944423967403777623306961880757613246328729616643032628964072931272085866928045973799374711846825157781056965164178505232524245809179235607571567174228822561697888645968559343608375331988097157145264357626738141646556353500994924115875748198318036296898604097000938272195903056733565880150540275369239637793975923329598716003350308259321436752579291000355560431542229699759955141152914708362494482")
n = int("15310745161336895413406690009324766200789179248896951942047235448901612351128459309145825547569298479821101249094161867207686537607047447968708758990950136380924747359052570549594098569970632854351825950729752563502284849263730127586382522703959893392329333760927637353052250274195821469023401443841395096410231843592101426591882573405934188675124326997277775238287928403743324297705151732524641213516306585297722190780088180705070359469719869343939106529204798285957516860774384001892777525916167743272419958572055332232056095979448155082465977781482598371994798871917514767508394730447974770329967681767625495394441")

# isqrt：整数平方根
s_square = z + 2 * n
s = isqrt(s_square)

t_square = z - 2 * n
t = isqrt(t_square)

p = (s + t) // 2
q = (s - t) // 2

phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, n)
flag = long_to_bytes(m)

print(flag.decode())