Rabin加密算法

记录新知识（1）——Rabin加密算法

今天刷BUUCTF的一道Crypto题遇到一个新的加密算法Rabin，所以记录一下新知识。
首先我也看了几篇师傅们的博客：
浅谈二次剩余
中国剩余定理（孙子定理)
RSA攻击之Rabin密码*
RSA 衍生算法——Rabin 算法
第二篇写的不错，但是对于我这种没学过数论的不太友好(模运算比较简单就自己百度了)，结合这几篇算是看懂了。
手写过程：

脚本：

import gmpy2
n=523798549
p=10663
q=49123
e=2
c=162853095
a,inv_q ,inv_p= gmpy2.gcdext(q,p)
mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)
a = (inv_p * p * mq + inv_q * q * mp) % n
b = n - int(a)
c = (inv_p * p * mq - inv_q * q * mp) % n
d = n - int(c)
for i in(a,b,c,d):
    print(i)