说实话，其中很多思路也没搞懂，先附个自己写的部分推论，很神奇的论证，但自己yp，yq的论证是很完美的
Rabin加密是一种基于模平方和模平方根的非对称加密算法。
举个例子：a=x^2 mod m 称a为x模m时的平方，x为a模m时的平方根。
加密过程
设私钥p q为两个素数，且p，q满足：p≡q≡3mod4 公钥n=p*q，对于明文m和密文c，定义一下加密过程：c=m^2 mod n
解密过程
一般先通过其他方法分解得到 p,q
，然后解密。带入解密函数会返回四个数，这其中只有一个是我们想要的明文，需要通过其他方式验证（一般需要根据验证码来对应）。
附推论，（markdown）
点击查看代码
Rabin加密过程
$$
\\ m_p \equiv c^{\frac{p+1}{4}}\mod(p)
\\ m_q \equiv c^{\frac{q+1}{4}}\mod(q)
\\\
\\由贝祖定理
\\存在y_p,y_q使得
\\y_p*p+y_q*q = (p,q)
\\p,q为素数
\\则 y_p*p+y_q*q = 1
\\yp*p \equiv 1 \mod(q)
\\yq*q \equiv 1 \mod(p)
\\yp = invert(p, q)
\\yq = invert(q, p)
\\\
\\四个明文解分别为
\\ a = (yp * p * mq + yq * q * mp) \mod(n)
\\ b = n - a
\\ c = (yp * p * mq - yq * q * mp) \mod(n)
\\ d = n - c
$$
点击查看代码
import gmpy2
def rabin_decrypt(c, p, q, e=2):
n = p * q
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
yp = gmpy2.invert(p, q)
yq = gmpy2.invert(q, p)
r = (yp * p * mq + yq * q * mp) % n
rr = n - r
s = (yp * p * mq - yq * q * mp) % n
ss = n - s
return (r, rr, s, ss)
c =
p =
q =
m = rabin_decrypt(c,p,q)
for i in range(4):
try:
print(bytes.fromhex(hex(m[i])[2:]))
except:
pass