RSA-Rabin加密中的N可被分解

Rabin加密是RSA的衍生算法，e==2是Rabin加密典型

解密方法：
先通过其他方法获得p和q，然后上脚本

例子hardRSA

import gmpy2,libnum
n=0xC2636AE5C3D8E43FFB97AB09028F1AAC6C0BF6CD3D70EBCA281BFFE97FBE30DD
p=275127860351348928173285174381581152299
q=319576316814478949870590164193048041239
e=2
c=int(open('hardRSA.rar/flag.enc','rb').read().encode('hex'),16)
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
print libnum.n2s(r)
print libnum.n2s(rr)
print libnum.n2s(s)
print libnum.n2s(ss)