Rabin密码体制详解

1.相关数学基础

如果gcd（a，n）=1，m为正整数，且x^m≡a（mod n）这个m次同余方程有解，则称a为模n的m次剩余；否则，称a为模n的m次非剩余。特别地，当m=2时，称a为模n的平方剩余（非平方剩余）或二次剩余（非二次剩余）。模n的平方剩余的集合记为QR_n，平方非剩余的集合记为QNR_n。

【例5-23】 考虑下列同余式

x²≡1（mod 5）

x²≡2（mod 5）

x²≡3（mod 5）

x²≡4（mod 5）

不难发现：存在x=1，x=4满足x²≡1（mod 5）；存在x=2，x=3满足x²≡4（mod 5）。

但不存在整数满足：

x²≡2（mod 5）或x²≡3（mod 5）

即1、4为模5的平方剩余，2、3为模5的非平方剩余。

若p是奇素数，a是模p的平方剩余，则x²≡a（mod p）有两个解，分别为x和-x。

奇素数模p的剩余类{1，2，…，p-1}中，有（p-1）/2个是p的平方剩余，它们分别与1²，2²，3²，…，[（p-1）/2]²同余，其他的（p-1）/2个是p的非平方剩余。

设p为奇素数，gcd（a，p）=1，则a是模p的平方剩余的充要条件是a^（p-1）/2≡1（mod p）；a是模p的非平方剩余的充要条件是a^（p-1）/2≡-1（mod p）。如果素数p≡3（mod 4），a是模p的平方剩余，那么a模p的平方根是±a^（p+1）/4mod p。证明：根据a是模p的平方剩余，可知

a^（p-1）/2（mod p）≡1

于是

【例5-24】 a=2是否为二次剩余方程为x²≡a（mod 23）的平方剩余？如果是，求方程的根。

【解析】 p=23为奇素数，由

知a=2确为模23的平方剩余。

于是模23运算下a=2的两个根是：

2.Rabin密码体制

Rabin公钥密码体制的基本框架类似于RSA密码体制，Rabin既可被看成是RSA的一个特例，也可被看成是对它的一个修正。RSA中选取的公钥e满足1＜e＜φ（n），且gcd（e，φ（n））=1。Rabin密码体制则取e=2。Rabin密码体制的安全性基于求解合数模下的平方根的困难性，即依赖于以两个大素数之积为模数的模指数运算，但它对模数的选择和加密/解密模指数运算提出了特别的要求。

Rabin密码体制有以下两个特点：

●它不是以一一对应的单向陷门函数为基础，对同一密文，可能有两个以上对应的明文；

●破译该体制等价于对大整数的分解。

Rabin密码体制的加密/解密过程如下：

（1）密钥的产生

选取两个相异的满足p≡q≡3（mod 4）的大素数p和q，计算n=p×q。以n为公钥，p，q为私钥。

（2）加密算法

c≡m²（mod n）(www.xing528.com)

其中，m是明文分组；c是对应的密文分组。

它相当于同时满足：

c≡m²（mod p）和c≡m²（mod q）

表明c是两个素数共同的平方剩余。

（3）解密算法

解密问题是求c模n的平方根，即解x²≡c（mod n）。

方程x²≡c（mod n）有四个解：

当p≡q≡3（mod 4）时

方程x²≡c（mod p）的两个解是

x≡±c^（p+1）/4（mod p）

方程x²≡c（mod q）的两个解是

x≡±c^（q+1）/4（mod q）

因此，可以组合得到四个一次同余方程组

利用中国剩余定理解这四个同余方程组得到四个解，它们是c模n的四个平方根。要寻找的明文就是四个解的其中之一。

由上面的解法可看出，Rabin算法的加密函数不是一一映射，解密具有不确定性，合法用户不能确切地知道到底哪一个解是真正的明文。如果加密之前在明文消息中插入一些冗余信息，比如用户的身份数字、日期、时间或者事先约定的某个数值等，则可以帮助接收者准确地识别出解密后的明文。

【例5-25】 假定模数n=19×23=437，对明文m=183使用Rabin密码体制加密并解密。

对明文m=183加密，所得密文为

c≡m²（mod n）≡183²（mod 437）≡277

如果要对密文c=277进行解密，首先需要计算出277模19和模23的平方根。由于19和23都是模4同余3的，因此可得

277模19的平方根

±277^（19+1）/4≡±277⁵≡±7（mod 19）

277模23的平方根

±277^（23+1）/4≡±277⁶≡±1（mod 23）

再解下面的同余方程组：

利用中国剩余定理，可解出上面四个同余方程组的解，分别是

x≡254，45，392，183（mod 437）

由此可见，原始明文m=183是这四个解之一。

Rabin算法的解密过程是寻找c模n的平方根，这个问题的难度等价于n的因子分解。尽管计算模为素数的平方根是多项式时间可解的，但其过程仍然很复杂。要求p与q是模4同余3的限制条件是为了使解密的计算和分析变得容易。

Rabin算法对选择明文攻击是安全的，但已经证明它确实不能抵抗选择密文攻击。此外，针对RSA算法的一些攻击方法对Rabin算法也有效。因此，与RSA安全性有关的一些问题，比如如何选择系统参数等，对Rabin算法也同样适用。