| He-Wu数字签名方案的攻击方法 |
|
|
|
作者：佚名 文章来源：不详 点击数： 更新时间：2006-12-5 16:20:26  |
Rabin根据二次剩余问题设计一种公钥密码体制和数字签名方案，分别称为Rabin
密码和Rabin数字签名方案［1］.从此以后，改进的Rabin密码体制相继提出［2，3］.
最近，He和Wu提出一种快速签名验证和小秘钥量的数字签名方案(称为H-W数字签名方
案)，这种数字签名方案的安全性建立在二次剩余问题之上.然而，H-W数字签名方案是
不安全的.本文对H-W数字签名方案的安全性进行分析，根据Morrison-Brillhart素因
子分解算法，对H-W数字签名方案给出一种攻击方法.在H-W数字签名方案中，n=pq,其
中p和q为两个大素数.系统用户公钥为n,私钥为(p,q).在已知多组消息和消息签名的情
况下，系统攻击者利用本文提出的攻击方法，可以对公钥n进行素因子分解，从而得到
系统用户的私钥(p,q).因此在已知多组消息和消息签名的情况下，H-W签名方案是不安
全的.
假定要对数n进行素因子分解，给定一组模n的同余方程：xi=y2imod
n,i∈N.其中N是正整数组成的集合.选择t，产生一t初始素因子集合，
分别将xi在t初始素因子集合上进行完全素因子分解：
通过求解模2的线性方程组可以求出一子集UN，使得对任意1≤j≤t，有eij=0mod
n.另一方面，xi=(yi)2modn,所以,(yi)2=(2e13e2…pett)2mod
n.当｜yi｜=｜2e13e2…pett｜时，(yi-2e13e2…pett)或(yi 2e13e2…pett)为数n的
平凡因子；当｜yi｜≠｜2e13e2…pett｜时，(yi-2e13e2…pett)或(yi 2e13e2…pett)
为数n的非平凡因子，因此上述方法就可以对数n进行素因子分解.
对上述方法进行分析可得，选择一个子集，至少可以以1/2的概率对数n进行素因子
分解.选择多个不同的子集，重复上述过程，可以以任意高的概率对数n进行素因子分解.
上述算法的复杂度同参数t的选取有关，如果t很小，只有少数的xi可以完全素因子
分解；如果t很大，算法中的模2线性方程组的求解就非常困难.因此上述算法要根据xi的
平均大小，选取适当的t.如果数n是｜n｜比特位，数xi平均包含｜x｜比特，那么上述
算法的复杂度为：.其中f(x)为一多项式函数，｜x｜表示数x的比特位数(以下相同).
在上述算法中，如果随机选取同余方程有｜x｜≈｜n｜；但当｜x｜≈1/2｜n｜时，
则，上述算法是非常有效的素因子分解的算法.
假定系统中有两个用户A和B，用户A发送消息m到用户B并且对消息m进行签名.用户B
收到用户A发送的消息和消息签名后要对签名进行验证.H-W数字签名方案包含三个过程：
系统的初始化、签名的产生过程和签名的验证过程.
系统的初始化：用户A随机选取两个大素数p，q分别满足p=3(mod8)和q=7(mod8)，计
算n=pq.那么用户A的公钥为n，私钥为(p，q).
签名的产生过程：用户A根据下述情况选择参数t，
其中m′=H(m)，H为hash压缩函数，L(m′/q)为广义Legendre符号.
用户A根据参数t的值计算签名，那么(s,t)为消息m的签名，将签名消息组(m,(s,t))
通过公开信道发送到用户B.
签名验证过程：用户B收到用户A发送的消息(m,(s,t))后，验证等式s2=tm′modn是
否成立，如果等式成立，用户B接受用户A对消息m的签名,否则拒绝签名.
假定系统中有一攻击者C，从系统用户A和B的通信中获得多组消息mi以及相应的数字
签名(si,ti)，i∈K.由H-W数字签名方案的签名验证方程得到：s2i=tim′imodn,i∈K.其
中m′=H(m).系统攻击者C从集合K中选择一子集N使得对任意的
i∈NK，有｜m′i｜≤k＜1/2｜n｜.那么有方程：s2i=tim′imodn,i∈N.其中｜m′i｜≤k.
利用本文第1节素因子分解方法，由上述方程组可以对模数n进行素因子分解，复杂度为.
从而系统攻击者C可以获得用户A的私钥(p，q).下面对上述攻击方法进行分析.
(1)系统攻击者C可以获得多组用户A发送到B的消息和消息签名(mi,(si,ti)).A和B的
通信是公开的，因此用户A发送到用户B的消息和消息签名也是公开的，任何一个系统攻
击者，比如C可以从A和B的通信中获得A发送到用户B的消息mi和相应的消息签名(si,ti).
(2)上述攻击方法的复杂度为.攻击方法的复杂度同参数k的选取有关，如果参数k很
小，寻找满足条件｜m′i｜≤k的消息比较困难；如果参数k很大，上述攻击方法的复杂
度也很大，攻击效率下降，因此，要根据实际情况选择合适的参数k.实际上当k≈1/2｜n｜
时，，上述攻击已是非常有效的攻击方法.
本文对H-W数字签名方案提出一种攻击方法，这种攻击方法利用Morrison-Brillhart
素因子分解方法，在已知多组消息签名的情况下，对系统中用户的公钥进行分解，从而获
得用户的私钥.对于H-W数字签名方案，消息为m，对消息m的签名为(s，t)，签名验证方程
为：s2=tm′modn,其中m′=H(m).签名验证方程同Morrison-Brillhart素因子分解方法中
同余方程相同，因此选择满足一定条件的消息m，利用Morrison-Brillhart素因子分解方
法可以对用户的公钥进行素因子分解.由上述分析可见，在基于二次剩余问题密码体制设
计方法中一定要避免上述类似方程的出现.在H-W方案中要避免上述攻击，需要对签名验证
方程s2=tm′modn右端进行控制，使得对乘积项tm′完全素因子分解非常困难.对H-W方案
有两种改进方案，一种是在签名消息中隐藏t，另一种对m′的大小进行控制，使得对m′
完全素因子分解非常困难.如何设计出安全的基于二次剩余问题的H-W数字签名方案有待进
一步的研究.
*国家自然科学基金资助项目(69772035；69882002)
作者简介：李子臣 34岁，男，博士生
作者单位：北京邮电大学信息工程系，北京 100876；
参考文献
Electronics Letter, 1989, 25(11): 726～728
quadratic residue problem. Electronics Letter, 1997, 33(11): 205～206
signature scheme. Electronics Letter, 1997, 33(22): 1 861～1 862
|
| 文章录入：wuyongjian 责任编辑：wuyongjian |
|
上一篇文章： 上传文件又有新方法
下一篇文章： 如何成为一位 hacker 3 |
| 【字体：小 大】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】 |
