Schmidt-Samoa 密码体系

原理

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

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

类似RSA

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

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

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

加密和解密

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

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

计算$pq$pq

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

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

得到$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)))