一、Rabin's RSA
题目信息
from Crypto.Util.number import *
from secret import flag
p = getPrime(64)
q = getPrime(64)
assert p % 4 == 3
assert q % 4 == 3
n = p * q
e = 2
m = bytes_to_long(flag)
c = pow(m,e,n)
print('n =', n)
print('c =', c)
# n = 201354090531918389422241515534761536573
# c = 20442989381348880630046435751193745753典型的Rabin加密算法
脚本
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
p=13934102561950901579
q=14450452739004884887
e = 2
c = 20442989381348880630046435751193745753
n = p*q
# Rebin算法
mp = gmpy2.powmod(c, (p+1)//4, p)
mq = gmpy2.powmod(c, (q+1)//4, q)
gcd1, a, b= gmpy2.gcdext(p, q) # 欧几里得扩展a*p+b*q=gcd1
r=(a*p*mq+b*q*mp)%n
r_=n-r
s=(a*p*mq-b*q*mp)%n
s_=n-s
print(f"r={libnum.n2s(int(r))}")
print(f"r_={libnum.n2s(int(r_))}")
print(f"s={libnum.n2s(int(s))}")
print(f"s_={libnum.n2s(int(s_))}")
#flag{r4b1n#4c58}