NewStarCTF2023week3-Rabin‘s RSA

根据题目提示是Rabin算法

先将N分解得到P和Q

导入e，n，p，q，c

使用Rabin算法直接计算明文，再将明文转字符串即可

我们也可以通过脚本来理解原理

import gmpy2
import libnum
 
p = 13934102561950901579
q = 14450452739004884887
n = 201354090531918389422241515534761536573
 
c = 20442989381348880630046435751193745753
 
e = 2
 
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
# 因为rabin 加密有四种结果，全部列出。
aa = [a, b, c, d]
 
for i in aa:
 
    print(i)
 
    print(libnum.n2s(int(i)))

运行得到 flag{r4b1n#4c58}