本题来自于：2019年工业信息安全技能大赛个人线上赛，第二场第一题，破解加密数据，题目如下，即解密密文109930883401687215730636522935643539707对应的明文数据
m = "unknown"
e = 2
n = 0x6FBD096744B2B34B423D70C8FB19B541
assert(int(m.encode('hex'), 16) < n)
c = pow(int(m.encode('hex'), 16),e,n)
print c
#109930883401687215730636522935643539707
加密方法是，把明文转码成16进制，再转成对应的十进制的一个大数，然后平方后模n，看着非常像rsa，不过这其实是rabin算法。解法参考：RSA 衍生算法——Rabin 算法
解题思路
发现把n分解为两个质数
利用yafu分解命令：factor(148525842361836932303997638207312868673)，得到p和q，然后测试：
>>> p = 13691382465774455051
>>> q = 10848126018911527523
>>> p % 4
3L
>>> q % 4
3L
可以发现这两个质数都是模四余三，根据e=2可知，这是一个rabin算法，n是公钥，pq为私钥，所以解出pq就可以直接解密了：
运算规则
按照上图q在模p上的逆和p在模q上的逆可以直接用扩展欧几里得求出：
m1 = pow(c,(p+1)/4,p)
m2 = (p-pow(c,(p+1)/4)) % p
m3 = pow(c,(q+1)/4,q)
m4 = (q-pow(c,(q+1)/4)) % q
a=q*ModReverse(q,p)
b=p*ModReverse(p,q)
M1 = (a*m1+b*m3)%n
M2 = (a*m1+b*m4)%n
M3 = (a*m2+b*m3)%n
M4 = (a*m2+b*m4)%n
但其中m2 = (p-pow(c,(p+1)/4)) % p因为太大不能直接运算，所以利用模运算性质：
(a-b)%p == (a%p - b%p)%p
故:
m2
= (p-pow(c,(p+1)/4)) % p
= (p%p - pow(c,(p+1)/4,p))%p
= (-pow(c,(p+1)/4),p)%p
= (-m1)%p
同理：
m4 = (-m3)%p
负数取模直接用python计算即可
解密脚本
def EX_GCD(a,b,arr):
if b == 0:
arr[0] = 1
arr[1] = 0
return a
g = EX_GCD(b, a % b, arr)
t = arr[0]
arr[0] = arr[1]
arr[1] = t - int(a / b) * arr[1]
return g
def ModReverse(a,n):
arr = [0,1,]
gcd = EX_GCD(a,n,arr)
if gcd == 1:
return (arr[0] % n + n) % n
else:
return -1
def decrypt_rabin(c,p,q):
n = p*q
m1 = pow(c,(p+1)/4,p)
m2 = (-m1)%p
m3 = pow(c,(q+1)/4,q)
m4 = (-m3)%q
a=q*ModReverse(q,p)
b=p*ModReverse(p,q)
M1 = (a*m1+b*m3)%n
M2 = (a*m1+b*m4)%n
M3 = (a*m2+b*m3)%n
M4 = (a*m2+b*m4)%n
print str(hex(M1))[2:-1].decode("hex")
print str(hex(M2))[2:-1].decode("hex")
print str(hex(M3))[2:-1].decode("hex")
print str(hex(M4))[2:-1].decode("hex")
if __name__ == '__main__':
c = 109930883401687215730636522935643539707
p = 13691382465774455051
q = 10848126018911527523
decrypt_rabin(c,p,q)
解密出四组数据，有意义的为flag_EnCryp1即为flag
思考区别
rabin和rsa的区别是什么呢？