Rabin 密码体制

Thm1 (Rabin密码体制)设$n=pq$,其中p和q是素数,且$p,q\equiv3\mod 4$,设$ P=C=Z_n^*$,且定义
κ={(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\equiv3\mod 4$
可以省去,条件P=C=Zn⋆也可以弱化为P=C=Zn,只是在使用更多的限制性描述的时候,简化了许多方面的计算和密码体制分析。

当$p\equiv3\mod 4$时,有一个简单公式来计算模p的二次剩余的平方根,假定y是一个模p的二次剩余,且$y\equiv3\pmod 4$那么有
$(\pm y^\frac{p+1}{4})^2 \equiv y^\frac{p+1}{2}\pmod p\equiv y^\frac{p-1}{2}y\pmod p$
由欧拉准则我们可以知道,当y是一个模p的二次剩余时,有$y^\frac{p-1}{2}\equiv1\pmod p$
所以就有$(\pm y^\frac{p+1}{4})^2 \equiv y\pmod p$
$\sqrt{y}\pmod p\equiv \pm y^\frac{p+1}{4}$
所以我们可以解出$\pm y_1\equiv x\pmod p, \pm y_2\equiv x\pmod q$
运用中国剩余定理构造$s_1,s_2$
$s_1=q(q^{-1}\pmod p)$
$s_2=p(p^{-1}\pmod q)$
则x可能的四个值为
$x\equiv\pm y_1s_1\pm y_2s_2\pmod {n}$