密码学之公钥密码体系（4）：Rabin公钥密码方案

📢 声明：
🥭 作者主页：【Janice主页】。
⚠️ 未经作者允许，禁止转载。
⚠️ 本文为非盈利性质，目的为个人学习记录及知识分享。因能力受限，存在知识点分析不正确的可能。若您参考本文造成了不良后果，本人不承担相关责任。
⚠️ 若本文所采用图片或相关引用侵犯了您的合法权益，请联系我进行删除。
😄 欢迎大家指出文章错误，欢迎同行与我交流 ~

一、Rabin公钥密码方案

Rabin密码体制，被认为是对RSA密码体制的改进，其安全性基于求合数的模平方根的难度。而这个困难性等价于求解因子分解。RSA算法中只要素数被分解，密码就会被破解。而Rabin方案其实可以看做为RSA方案的一个特例，但被证明破译的难度和分解大整数一样难度。
Rabin方案的特点：

1. Rabin 方案不是一一映射的，对于同一个密文，可能会有多个对应的明文；
2. Rabin算法的安全性基于求解合数模平方根困难性问题，破解难度和大整数分解相当；
3. Rabin算法可以看做为RSA算法的一个特例，即指数取2

二、Rabin公钥密码加、解密方案

1. 密钥生成

首先，随机选择两个大素数 $p,q$，并满足如下条件：

$$p≡q≡3 mod 4$$

即$q,p$可以表示为$4k+3$的数学形式，在将得到的素数相乘:

$$n=q*p$$

其中，$n$即为公钥，$q,p$即为私钥。
想要破解通过公钥n破解对应的私钥，这是十分困难的。

2. 加密方案

加密过程为：

$$c≡m^2 \mod n$$

加密的过程很简单，与RSA相比，只是将指数改为常数$2$。当攻击者不知道私钥的情况下，拿到密文$c$时，想要恢复明文$m$,相当于需要求解密文$c$在模$n$时的平方根，这与大整数分解的难度是等价的。

3. 解密方案

解密时，求解密文$c$在模$n$下的平方根。即求解：

$$x^2≡c \mod n$$

由于n可以分解为$p$和$q$，因此，根据中国剩余定理，可以将上面方程等价于如下方程组：

$$\begin{cases} x^2≡c \mod p,\\ x^2≡c \mod q, \end{cases}$$

由于$p≡q≡3 \mod 4$,因此，很容易求解方程组：

$$x≡y \mod p, x≡-y \mod p \\ x≡z \mod q, x≡-z \mod q$$

经过组合，可以得到如下四个方程组：

$$\begin{cases} x≡y \mod p\\ x≡z \mod q \end{cases} \\$$ $$\begin{cases} x≡-y \mod p\\ x≡z \mod q \end{cases}\\$$ $$\begin{cases} x≡y \mod p\\ x≡-z \mod q \end{cases}\\$$ $$\begin{cases} x≡-y \mod p\\ x≡-z \mod q \end{cases}\\$$

因此，有中国剩余定理可以解出每一个方程组的解，一共有$4$组解，因此可以看出，每一个密文所对应的明文均不唯一。
为了解决这个办法，可以在加密$m$时，在$m$的明文信息中加入私人信息，供解密使用。

三、Rabin方案具体案例

1. 选择$p=7,q=11, n=77$,因此，明文空间为$P={0,1,2,…,76}$
2. 选择加密明文为$m=20$， 加密之后密文$c=20^2 mod 77 =15$
3. 当$n$很大，无法破解时，我们无法计算，如果我们假设以及知道了$77$的两个因子为$7$和$11$，已知密文为$15$，求解明文$m$. $$m=\sqrt{c} \mod p \\ m=\sqrt{c} \mod q$$ 由于$p≡q≡3 \mod 4$,因此，有如下公式成立： $$m=c^{1/4(p+1)} \mod p,m=-c^{1/4(p+1)} \mod p\\ m=c^{1/4(q+1)} \mod q,m=-c^{1/4(q+1)} \mod q$$ 两两一组，可以求解$m$为${64,20,13,57}$