[NPUCTF2020]认清形势，建立信心
题目描述：
from Crypto.Util.number import *
from gmpy2 import *
from secret import flagp = getPrime(25)
e = # Hidden
q = getPrime(25)
n = p * q
m = bytes_to_long(flag.strip(b"npuctf{").strip(b"}"))c = pow(m, e, n)
print(c)
print(pow(2, e, n))
print(pow(4, e, n))
print(pow(8, e, n))''' 169169912654178 128509160179202 518818742414340 358553002064450 '''
代码已知
x 1 ≡ 2 e ( m o d n ) x_1\equiv 2^e(mod~n) x1?≡2e(mod n)
x 2 ≡ 2 2 e ( m o d n ) x_2 \equiv 2^{2e}(mod~n) x2?≡22e(mod n)
x 3 ≡ 2 3 e ( m o d n ) x_3\equiv 2^{3e}(mod~n) x3?≡23e(mod n)
所以：
x 1 2 ? x 2 = k ? n x_1^2-x_2=k*n x12??x2?=k?n
x 1 ? x 2 ? x 3 = k ′ ? n x_1*x_2-x_3 = k'*n x1??x2??x3?=k′?n
求解两者之间的最大公因数（注意求得的最大公因数可能为依然为 k ′ ′ ? n k''*n k′′?n，但是 k ′ ′ k'' k′′一般很小）即为 n n n
分解 n n n再除以显然不是 p , q p,q p,q的数
得到真正的 n n n
再求 e e e；相当于离散对数问题，当然也可以直接爆破
使用封装函数sympy.discrete_log()
然后正常的RSA求解
代码实现：
import gmpy2
from Crypto.Util.number import *
import sympyc = 169169912654178
x1 = 128509160179202
x2 = 518818742414340
x3 = 358553002064450n = gmpy2.gcd(x1**2-x2,x1*x2-x3) // 2
p = 28977097
q = 18195301
e = sympy.discrete_log(n,x1,2)
fai_n = (p-1)*(q-1)
d = gmpy2.invert(e,fai_n)
m = pow(c,d,n)
print(long_to_bytes(m))