RSA_Rabin

RSA_Rabin解密过程

题目:

1
2
3
4
c = 3708354049649318175189820619077599798890688075815858391284996256924308912935262733471980964003143534200740113874286537588889431819703343015872364443921848
e = 16
p = 75000325607193724293694446403116223058337764961074929316352803137087536131383
q = 69376057129404174647351914434400429820318738947745593069596264646867332546443

一般的解密方式:

1
2
3
4
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(ct, d, n)
print(long_to_bytes(m))

但是, 我们不能直接这样解题.因为e是偶数, 所以e and λ(n) 的最大公约数不等于1.

在 Rabin 解密方法中, e是必须等于2的, 这样才能解密.

因为 16= 2^4, 所以脚本可以使用Rabin 解密方法

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
26
27
28
29
30
31
from Cryptodome.Util.number import *
import gmpy2
c = 3708354049649318175189820619077599798890688075815858391284996256924308912935262733471980964003143534200740113874286537588889431819703343015872364443921848
e = 16
p = 75000325607193724293694446403116223058337764961074929316352803137087536131383
q = 69376057129404174647351914434400429820318738947745593069596264646867332546443
phi = (p-1)*(q-1)
n = p*q

def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

g ,yp,yq = egcd(p,q)

mp = pow(c,(p+1)/4,p)
mq = pow(c,(q+1)/4,q)

for i in range(3):
mp = pow(mp,(p+1)/4,p)
mq = pow(mq,(q+1)/4,q)

r = (yp*p*mq + yq*q*mp) % n
mr = n - r
s = (yp*p*mq - yq*q*mp) % n
ms = n - s
for num in [r,mr,s,ms]:
print(long_to_bytes(num))

Flag

flag{d0nt_h4v3_4n_3v3n_3_175_34sy!!!}