Schmidt-Samoa 密码体系

原理

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

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

类似RSA

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

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

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

加密和解密

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

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

计算$pq$pq

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

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

得到$pq=gcd(n,2^{nd}-2)$pq=gcd(n,2nd−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)))