原理

随机生成两个素数，$p$ , $q$

令$N = p^2\cdot q$，$e=N$

类似RSA

有$Public\ Key=(e,N)$

计算$d=N^{-1}\ mod\ \varphi (pq)$

有$Private\ Key=(d,N)$

加密和解密

加密：$c=m^N\ mod\ N$

解密：$m=c^d\ mod\ pq$

计算$pq$

依据$d$的产生有$n\cdot d\equiv 1\ mod\ \varphi(pq)$

任取一个数如2，有$2^{nd}\equiv 2\ mod\ pq$

得到$pq=gcd(n,2^{nd}-2)$

实例[2024 国城杯]babyRSA

from Crypto.Util.number import *
n = ?
d = ?
c = ?
pq = GCD(pow(2,n*d,n)-2,n)
print(long_to_bytes(pow(c,d,pq)))