密码学笔记（5）——Rabin密码体制和语义安全性⼀、Rabin密码体制 Rabin密码体制是RSA密码体制的⼀种，假定模数n=pq不能被分解，该类体制对于选择明⽂攻击是计算安全的。
因此，Rabin密码体制提供了⼀个可证明安全的密码体制的例⼦：假定分解整数问题是整数上不可⾏的，那么Rabin密码体制是安全的。
Thm1 (Rabin密码体制)设n=pq，其中p和q是素数，且p,q \equiv 3 (mod \, 4)，设P=C=Z^{\star}_{n}，且定义\kappa =\{(n,p,q)\}对K=(n,p,q)，定义e_{K}(x)=x^{2} (mod \, n)和d_{K}=\sqrt{y} (mod \, n)n为公钥，p和q为私钥。
注：条件p,q \equiv 3 (mod \, 4)可以省去，条件P=C=Z^n_{\star}也可以弱化为P=C=Z^n，只是在使⽤更多的限制性描述的时候，简化了许多⽅⾯的计算和密码体制分析。
注意看到这个函数y=x^{2}对于加密来说不是⼀个单射，所以解密不能以⼀种明显的⽅式完成，特别的，对于y \equiv x^{2} (mod \, n)，对于某⼀个x \in Z^{\star}_{n}，存在y模n的是个解，除⾮有其他的冗余信息，否则⽆法确认是那⼀个值。
从Bob的观点来看解密问题，它有⼀个密⽂y，要想得到x使得x^2 \equiv y(mod \, n)这是⼀个关于Z_{n}中未知元x的⼆次⽅程，解密需要求出模n的平⽅根，等价于求解以下两个同余⽅程。
z^{2} \equiv y (mod \, p)z^{2} \equiv y (mod \, q)虽然我们可以利⽤Euler准则来判断y是否为⼀个模p或模q的⼆次剩余。
事实上，如果加密正确的执⾏，y是⼀个模p和模q的⼆次剩余，遗憾的是它并不能帮助我们找到y。
当p \equiv 3(mod \, 4)时，有⼀个简单公式来计算模p的⼆次剩余的平⽅根，假定y是⼀个模p的⼆次剩余，且y \equiv 3 (mod \, 4)那么有\begin{align} (\pm y^{\frac {p+1}{4}})^{2} \equiv & y^{\frac{p+1}{2}} (mod \, p) \\ \equiv & y^{\frac{p-1}{2}}y (mod \, p) \\ \equiv & y(mod \, p) \\ \end{align}这⾥⼜⼀次使⽤了Euler准则，即当y是⼀个模p的⼆次剩余时，有y^{\frac{p-1}{2}} \equiv 1 (mod \, p)，因此，y模p的两个平⽅根为\pm y^{\frac{p+1}{4}} (mod \, p)，同样的讨论可以知道，y模q的两个平⽅根为\pm y^{\frac{p+1}{4}} (mod \, q)，再利⽤中国剩余定理可以得到y模n的四个平⽅根。
