2021西湖论剑hardrsa

2021西湖论剑hardrsa

1.第一步，先求x，因为c1已知，y已知，g已知 x就是取log就行。

2.x解出来了，然后现在就是解方程，使用在线的sage数学工具，解出p

当然这里也可以利用python去解方程

from z3 import *
p=Int('p')
s = Solver()
s.add(2019*p**2+2020*p**3+2021*p**4==x)
s.check()
print(s.model())

3.然后脚本跑结果，中间的推导利用一些数论知识和费马定理

c = m ^ e mod n
已知dp = d mod (p-1)
c^dp = m^(e*dp) mod n
# 两边模p
c^dp mod p = m^(e*dp) mod p
e*dp = e*d mod (p-1) = 1 mod (p-1)
c^dp mod p = m^(1+k*(p-1)) mod p
#费马小定理： m^(p-1)=1 mod p

所以，pow(c,dp,p) = m mod p