Rabin算法

1.简介

Rabin 密码系统是一种基于模合数平方根困难问题的非对称加密算法，其安全性依赖于 大整数分解的困难性。换句话说，如果能够快速分解 n，就能破解 Rabin 加密。

2.特点

e=2，n=p*q

3.数学原理

$$Ⅰ.若p \equiv -1 \pmod 4$$

首先

$$由于x^2 \equiv a \pmod p,且a^{(p-1)/2} \equiv 1 \pmod p$$

$$那么x \equiv +-a^{(p+1)/4} \pmod p$$

所以

$$记m_p \equiv c^{(p+1)/4} \pmod p,m_q \equiv c^{(q-1)/4} \pmod q$$

$$Ⅱ.若p \equiv 1 \pmod 4$$

参考AMM算法

AMM算法-Crypto-25-Lamb

1adb894e6161a2becf5e7a9a78213b46.png

Ⅲ.那么我们会得到四个方程组

$$（1）m \equiv m_p \pmod p,m \equiv m_q \pmod q$$

$$（2）m \equiv -m_p \pmod p,m \equiv m_q \pmod q$$

$$（3）m \equiv m_p \pmod p,m \equiv -m_q \pmod q$$

$$（4）m \equiv -m_p \pmod p,m \equiv -m_q \pmod q$$

用CRT得到四个解，根据题目判断哪个是正确明文

4.另一种方法

f3aa57445145f17639ee01b2f8491be2.png

脚本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from Crypto.Util.number import *
from gmpy2 import *
p = 
q = 
e = 2
c = 
n = p*q
def rabin(c):
    mp = pow(c, (p + 1) // 4, p)
    mq = pow(c, (q + 1) // 4, q)
    yp = inverse(p,q)
    yq = inverse(q,p)
    a = (yp * p * mq + yq * q * mp) % n
    b = n - int(a)
    c = (yp * p * mq - yq * q * mp) % n
    d = n - int(c)
    aa = [a, b, c, d]
    for i in aa:
        print(i)
        print(long_to_bytes(i))
m = rabin()