Rabin算法

加密过程

选取两个大素数 $p$ 与 $q$，满足 $p,q \equiv 3 \pmod{4}$
对于明文 $m$ 和密文 $c$，定义以下加密过程：$c \equiv m^2 \pmod{n}$（一般情况下 $e$ 取 2，$e$ 也可取 2 的倍数）

解密过程

解密就是求解 $c$ 模 $n$ 的平方根，即求解同余式
$$
x^2 \equiv c \pmod{n}
$$
由中国剩余定理可知，求解同余式等价于解同余方程组
$$
\begin{cases}
x^2 \equiv c \pmod{p} \\
x^2 \equiv c \pmod{q}
\end{cases}
$$
由于 $p,q \equiv 3 \pmod{4}$，可知每个方程有两个解
$$
\begin{cases}
x \equiv \pm c^{\frac{1}{4}(p+1)} \pmod{p} \\
x \equiv \pm c^{\frac{1}{4}(q+1)} \pmod{q}
\end{cases}
$$
通过拓展的欧几里得定理分别求得整数 $s,t$ 满足
$$
\begin{cases}
sq \equiv 1 \pmod{p} \\
tp \equiv 1 \pmod{q}
\end{cases}
$$
根据中国剩余定理得到四个解
$$
[\pm c^{\frac{1}{4}(p+1)} \pmod{p}]sq + [\pm c^{\frac{1}{4}(q+1)} \pmod{q}]tp \pmod{n}
$$

例题

在这一道题中e=11*2**16

#Rabin算法只有在p，q都%4=3的情况下才能使用,还有一个特征是e=2的倍数  
from Crypto.Util.number import *
import gmpy2

def Rabin_decrypt(p, q, c):
    n = p * q
    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
    return (r, rr, s, ss)

def Rabin(p, q, e, c):
    assert p % 4 == 3 and q % 4 == 3
    assert e & (e-1) == 0  # 确保 e 是 2 的幂次方
    cs = [c]
    for i in range(int(gmpy2.log2(e))):
        ps = []
        for c_ in cs:
            ps.extend(Rabin_decrypt(p, q, c_))
        cs = list(set(ps))
    # 最后一层的四个明文
    for m in cs:
        print(long_to_bytes(m))

p = 7789591348561112069062036258358846485064075647678305757108894839399612845301208683326183281448934541308319593732293251449480952381682222481111712823689403
q = 11843985748190035400123239047046120615842488890207046522632012792661959669466825284114805235100514154443418211946648772038611835569684484924078305412048239
c = 56375886252330945863796100146788284026284575124540705402766406570186848250541965030413492814326044028889436839480443287548796428401787742194995976041781857264225844371755006942983206638749208098849661879359667211157469234559833948233580696384823163040243094991418212296959615785232531545231813567101713253539
#e是2的几次方就Rabin几次，Rabin了16次,e=720896=11*2**16
e_ = 2**16
n = p * q
#余数11拿来计算d
d = gmpy2.invert(11, (p-1)*(q-1))
cd = pow(c, d, n)

Rabin(p, q, e_, cd)
'''
b'\x83a\xe0O\xaa.R/rjk\xff\xec\xb5]\xe8\xb4\xe0\x9bO\x8e\xbc\x97yS\x90\xfd\x9eC[\xde\x875\x9c\xf4\xfa:\x04e3\x10\x97\x81j\xef\xba,B\x826\x95\xe6s<[\xa4Qk\xe4\xf6c\xed\x90\xa0\xcd\xbd\xab\x1dv\xc2W\x0b\x84\xe1J\x8f\x17\x1f\x0f\\\xc4I%\x7f\x8c\x0c]^_n\xde\x98\x83\xb5\xf7)\xa0\x93s8\xa8\x07!7\x11\xe9\x1fJkx0\x03\xd8\xbd\x95\x8c\xd9\x80\xfc5\t\x05E\xdf\xdd\xd9\xa5\x98'
b'flag{5b8743c3-8ffb-4b00-a54a-afc93c8e7252}'
b'jk;\xba"T\xd9\x92\xbb\xca\x180\x00\xd1W\xde\xc3\x93\xedB\x95y\'\xbf79 /J\x01\xae\xb5\xcd\xee6\xc4H\xa1}Lv\'\xfd\xb2\x85#:c"G\xfe\x0e(\x0e\xfd\x99\\\xdcCG\x8d\x83\x9c<\x1f(f\x1f\x99\xb2\xde\xc0! \xb8\x1e.]\x07\xc6\xbc.\x80t\xcb;pHs@\xc5B,\xb2\x9b\xd3~*r\xb3G\x971@\x81\xc7\xec25\xd5"\xa6\xcd\x11\xd7}\x7f\xe4\xaba}\xc7\x86\xf7*:4K'
b'\x18\xf6\xa4\x95\x87\xd9x\x9c\xb6\xa0S\xcf\xeb\xe4\x06\t\xf1L\xae\x0c\xf9Co\xba\x1cW\xddn\xf9Z/\xd1g\xae\xbe5\xf1b\xe7\xe6\x9ao\x83\xb8j\x96\xf1\xdf_\xee\x97\xd8K-^\n\xf4\x8f\xa1\xae\xd6i\xf4d\xae\x95D\xfd\xdd\x0fxKc\xc0\x92p\xe8\xc2\x07\x96\x08\x1a\xa5\n\xc0\xd1S\x82M\x95\x94\x8b\xb9;\x92\x8aU\xcc3\xb2\x98\xd6VX\xbdU\x95He\xd0n\x92@\x0c\xebp\xbf\xff\x8a\x06\xeev$\x1f\xe5\xd4\xa3\xca'
'''