# 公钥加密算法(三) Rabin

The Rabin Cryptosystem is based on the idea that computing square roots modulo a composite N is simple when the factorization is known, but the very complex when it is unknown.

Rabin加密系统是基于在已知合数N的因式分解的情况下，可以计算出二次剩余的平方根；但是在因式分解N未知的情况下很难求解的原理。

It is possible to prove that the hardness of breaking the Rabin cryptosystem is equivalent to the hardness of facting。

Rabin加密系统的安全性源于计算二次剩余平方根( square roots modulo a composite N) 和 因式分解N 具有相同的难度。

## Rabin构造模型

### Encrypt

$$Enc_K(m) = m^2\;(mod\;n) = c$$

*注: $$Enc_K$$ 不是一个permutation function(一对一关系的函数)

### Decrypt

$$Dec_K(c) = \sqrt{c}\;(mod\;n) = m$$

, this is to calculate:

$$m^2 = c\;(mod\;n)$$, exists 4 square roots of $$c\;(mod\;n)\$$.

One way to be able to recognize which of all messages was the sent message is adding some information of the message, called redundant information.

## 举则列子

### Key Generate

$$p = 7, q = 11, n = 77$$

Alice的密钥为$$K = \left \{ n= 77, p = 7, q = 11 \right \}$$

Bob拿到Alice的公钥即$$n = 77$$

### Encrypt

Bob将消息$$m = 32$$用公钥$$n$$加密，然后发送给Alice：$Enc_{77}(32) = 32^2\;(mod\;77) = 23 = c$

### Decrypt

Alice收到Bob发送的密文$$c = 23$$，用私钥$$K$$解密。

## 扩展阅读

The Rabin Cryptosystem
Naiara Escudero Sanchez

## Rabin Signature

There are 4 roots that all map to the same value.

The keys: $$V_k = N = p * q , S_k = (p,q)$$

Signing: $$Sig(S_k, m)$$ – computes the square root of the hash of $$m$$ ($$H(m)\text{ or }-H(m)$$); equals to $$\sigma$$

Verifying: $$Ver(N,m,\sigma)$$ – this verifies that $$\sigma^2\;mod\;N = H(m)\text{ or }-H(m)$$

*For large message m’s, the hash of the message (H(m)) is signed instead.

## Rabin加密 bit by bit

### Key Generate

$$N = p * q\;,\; P_k = N\;, S_k = (N,p,q)$$

### Encrypt

1. $$Z_n \text{ 中取一个随机数 } r$$
2. 密文 $$c = (-1)^b*r^2\;(mod\;N)$$, 其中b代表消息中的每1bit

### Decrypt

1. 计算 Legendre Symbol $$(\frac{c}{p}) \text{ 和 } (\frac{c}{q})$$
2. If $$(\frac{c}{p}) \neq (\frac{c}{q}) , \text{内部错误}$$

Otherwise 输出解密结果 $$b = \begin{cases} 0 & \text{, iff } (\frac{c}{q}) = 1\\ 1 & \text{, iff } (\frac{c}{q}) = -1 \end{cases}$$

$$(\frac{a}{p}) = \begin{cases} 0 & \text{, if } p|a & \text{ 表示p能整除a } \\ 1 & \text{, if } a \in Q_p & \text{ 表示a属于 模p的二次剩余 } \\ -1 & \text{, if } a \in \overline{Q_p} & \text{ 表示a不属于 模p的二次剩余 } \end{cases}$$

 Tweet