参考文档：http://www.cnblogs.com/iptables/p/5598049.html                   http://www.jianshu.com/p/a81f5eaf445d Rabin加密是一种基于模平方和模平方根的非对称加密算法。 a=x^2 mod m    称a为x模m时的平方，x为a模m时的平方根。
1、加密过程 设私钥p q为两个素数，公钥n=p*q，对于明文m和密文c，定义一下加密过程： c=m^2 mod n
2、解密过程 根据以下公式计算出mp和mq: mp = c^((1/4)(p+1)) mod p mq = c^((1/4)(q+1)) mod q
根据以下公式推导出一个可用的yp和yq: yp * p + yq * q = 1 根据以下公式计算最终结果： r = (yp * p * mq + yq * q * mp) mod n -r = n - r s = (yp * p * mq - yq * q * mp) mod n -s = n - s 可以证明每一个密文对应四个原文，而真正的原文一般需要根据验证码来对应。
CTF 中应用Rabin加密的题：https://www.jarvisoj.com/challenges (hardRSA) 解题思路：先用openssl解出参数，发现e=2，则说明用了Rabin加密，于是找脚本爆破即可。 c = int(open('flag.enc','r').read().encode('hex'),16) #print c p = 275127860351348928173285174381581152299 q = 319576316814478949870590164193048041239 n = p*q mp = pow(c,(p+1)/4,p) mq = pow(c,(q+1)/4,q) yp = gmpy.invert(p,q) yq = gmpy.invert(q,p) a = (yp*p*mq + yq*q*mp)%n b = n - int(a) c = (yp*p*mq - yq*q*mp)%n d = n - int(c)