BUUCTF-坏蛋是雷宾

题目描述：

老牌刺客之王混进了女王的住所。一天，女王得到了一个匿名举报，说她的侍卫里有一个刺客，叫做Rabin，而他的信息就在一份文件里，文件中有附带一个Pk，是523798549，密文是162853095，校验码二进制值是111001，根据说明是放在明文后一起加密的，明文与密文长度相同。加密算法和这位老牌刺客同名。快拯救女王，答案是求得的明文，进行32位md5小写哈希字符串，提交即可。

第一次接触这个Rabin算法，查阅了资料：

[*]PK是公钥的意思，Rabin的公钥密码体制和RSA有点类似，公钥n=p*q，私钥就是p和q。
[*]加密过程由明文m在平方后与n求模得到c，其次就是二次同余的过程。解密的时候就求出密文的平方根在两个私钥模值（p或者q）下的同余即可。
[*]即找到一个数，使得其平方值与密文对于模值n同余。

一知半解。。按照思路写了这个：

for i in range(111111111,1000000000):
    if((i*i)%523798549==162853095):
        print(str(i)+" ",end="")

得到这些数字：
115739001
214318436
309480113
408059548
639537550
738116985
833278662
931858097

二进制来看以0结尾的是偶数，以1结尾的是奇数。
所以偶数都排除掉，
115739001
309480113
738116985
931858097

做到这步说一下，BUUCTF里的题目给错了，校验码应该是：110001

根据校验值，后面六位是110001的，经测试是309480113：
>>> bin(309480113)
'0b10010011100100100101010110001'
>>> int("10010011100100100101010",2)
4835626
得到flag（已打码）
flag{c**cec****27347****6d78***e90f35}

还是没太弄明白原理，以后会补全