纠错码数字签名方案的修正
电子学报
ACTA ELECTRONICA SINCA
2000 Vol.28 No.2 P.110-112
纠错码数字签名方案的修正
王新梅
摘 要：对基于纠错码基础上构造的Xin-mei数字签名方案进行了修正，并指出在目前已知攻击方法下修正方案是安全的.
关键词：数字签名；纠错码；密码
分类号：TB112 文献标识码：A
文章编号：0372-2112 (2000) 02-0110-03
Modification of the Digital Signature Scheme Based on Error-Correcting Codes
WANG Xin-mei
(Xidian University,National Key Lab.on ISN,Xi′an 710071,China)
Abstract：The modifications of the Xin-mei digital signature scheme based on error-correcting are presented in this paper.It is showed that the two modificatory schemes are computationally secare on the attacks of AW and universal forgeries.
Key words：digital signature;error-correcting code;cryptography▲
1 引言
1990年作者提出了基于纠错码基础上的数字签名方案——Xin-mei方案［1］.自此以后，不少作者对其进行了修正与攻击［2～7］，其中Alabhadi和Wieker于1992年提出的选择性明文攻击［3］(以下简称AW攻击)的工作因子仅为O(n3).1993年他们针对Xin-mei方案的弱点，提出了一个改进方案［6］(以下简称AW方案)，并指出在AW攻击下该方案是安全的.1994年他们又对Xin-mei方案和AW方案提出了通用伪造攻击方法［7］，这也是一种选择性明文攻击.
本文针对Xin-mei方案的弱点提出了另一种修正方案，并指出此方案在AW和通用伪造攻击下是计算上安全的.
2 Xin-mei数字签名方案和AW方案以及AW攻击
Xin-mei方案是基于纠错码基础上构造出来的第一个数字签名方案，它的签名和验签过程这里不再重复，请参见文献［1，2］.Xin-mei签名方案对长为kbit的消息M的签名是
C=E e(M)=(E+MS A G A)P A (1)
式中：E是一个重量为w(E)≤t的随机错误图样；S A是k×k阶的满秩随机二进制矩阵；G A是［n,k,
d≥2t+1］二进制Goppa码的生成矩阵；P A是n×n阶满秩随机二进制矩阵.
AW攻击对Xin-mei方案的攻击过程如下.假设攻击者能设法使用户A对同一消息M进行n+1次签名，得到C1，C2，…，C n,C n+1,且它们之中n个签名和C1,C2,…,C n线性无关，则计算：
(2)
上式可表示成以下形式 X=YP A
这里X和Y分别是n×n阶矩阵：
若X矩阵满秩(如不满秩则重选C n+1，直至满秩)，则Y也必是n×n阶满秩矩阵，只要经过O(n3)次计算就可得到Y-1，由此可得：P A=Y-1X.得到了P A后，用以下方法就可得到S A G A.
若攻击者有k个不同消息M1，M2，…，M k的签名C1，C2，…，C k.这里
C j=(E j+M j S A G A)P A,j=1,2,…,k
由此可得：C j P-1A=E j+M j S A G A
通过译码计算得到E j，从而得到
C j P-1A+E j=M j S A G A (3)
由上式得到以下k个n重集合：
{C j P-1A+E j=M j S A G A|j=1,2,…,k}
由此可组成以下方程
D=MS A G A (4)
D和M分别是以下形式的k×n阶和k×k阶矩阵：
若消息集合{M j|j=1,2,…,k}中的k个消息线性无关，则M有逆阵M-1，由式(4)得
M-1D=M-1MS A G A=S A G A
求M-1的工作因子仅为O(k3).
由上可知利用这种选择性明文攻击，仅需O(n3)就能破译Xin-mei方案，对于Harn提出的修正方案［2］，也可以用该AW攻击破译.
除了上述攻击方法之外，文献［5］中也提出了一种攻击方法，但仔细分析后可知，这种攻击方法不能成立.
为了抗击上述的AW攻击，Alabhadi和Wieker提出了一个改进方案——AW方案［6］.在AW方案中，用户对消息M j的签名是长为l的序列：
{(E j+［f(M j,E j)+E j G*A］G A)P A
+Z j W*A}W A+Z j (5)
用户把(M j,C j,f(M j,E j))送给别的用户B.
式(5)中的f(x,y)是一非线性函数，它是公开的；E j是W(E j)≤t的二进制随机n重，W A是一个秩为n 的n×l阶矩阵，l＞n；且W*A和W A及G*A与G A分别满足以下关系
W A W*A=I k，G*A G A=In
Z j是长为l的二进制随机n重；且W(Z j)≈l/2，有关AW方案的签名和验签过程，这里不再重复，请读者参阅文献［6］.
3 修正Xin-mei方案及其安全性分析
事实上，类似于AW方案和Harn的修正方案［2］，可对原来的Xin-mei方案进行修正，得到比AW 方案更为简单比Harn方案更为安全的修正Xnmei方案.
修正Xin-mei方案的签名算法如下：
C j=(E j+h(M,E j,t j)S A G A)P A (6)
这里h(x,y,t)是非线性单向hash函数(它是公开的)，t i是签名的时间，h(M,E j,t j)是长为k的二进制序列.其它符号与前所述的Xin-mei方案中的符号相同.可知修正Xin-mei方案的公钥、私钥及签名算法与原Xin-mei方案相同，仅仅是多了一次hash函数计算.
用户A把(M,C j,t j)作为对消息M的签名，送给用户B.用户B的验签过程如同原来的Xin-mei方案，这里不再赘述.用户B在验签过程中得到h′(M,E j,t j)和E′j后，再由收到的M、t j，计算h(M,E′j,t j)，若
h′(M,E j,t j)=h(M,E′j,t j)
则签名有效，否则签名无效，要求用户A重发签名.
比较(5)、(6)二式可知，修正Xin－mei方案要比AW方案更为简单，且传送的签名信
息仅是(M,C j,t j)比(M j,C j,f(M j,E j))要少.
下面分析修正Xin－mei方案的安全性.在该修正方案中，由于h(M,E j,t j)函数的变量包含了错误图样E j和签名时间t j，故对同一消息M进行另一次签名后所得的C j不仅不相同，且其中的 h(M,E j,t j)≠h(M,E′j,t j+A).因此
h(M,E j,t j)S A G A≠h(M,E′j,t j+A)S A G A
故式(2)不能成立，从而无法由AW攻击得到P A，可知该修正方案能抵抗AW攻击.事实上，在式(6)的h (M,E j,t j)的二个变量E j,t j中，也可以只选一个，如选E j(或t j)则仅只要计算h(M,E j)(或h(M,t j)),此时仍有
h(M,E j)S A G A≠h(M,E′j)S A G A
在这情况下，用户A对消息M的签名是(M,C j),
C j=(E j+h(M,E j)S A G A)P A (7)
这种修正方案要传送的签名信息比(M,C j，t j)更少.
1994年文献［7］中对AW方案和Xin-mei方案提出了通用的伪造攻击方法.
由Xin-mei方案可知，用户A对消息M j的签名是
C j=(E j+M j S A G A)P A=E j P A+M j S A G A P A
=E′j+M j Q A (8)
对上述的修正Xin-mei方案，其签名是
C jm=(E j+h(M j,E j,t j)S A G A)P A=E j P A+h(M j,E j,t j)
.S A G A P A=E′j+h(M j,E j,t j)Q A (9)
这里E′j=E j P A,Q A=S A G A P A
若攻击者已知Q A以及至少知道任一个E′j，(对修正方案来说还需知道与E′j对应的E j)，则用以下方法伪造签名.
设攻击者需对消息M l伪造签名，则仅需计算
C′l=C′j+M l Q A (10)
显然C′l能通过Xin-mei方案中的验签运算，这种伪造签名方法对AW方案同样有效［7］.
下面讨论本文提出的修正方案在攻击下的安全性.由式(9)知，对修正方案来说，若要使伪造成功，不仅要知道E′j，还要知道与其对应的E j.这时有二种情况.
一是知道了E′j，但不知道其对应E j.由式(8)和(9)知
E′j=E j P A, E j=E′j P-1A
要从E′j得到E j或相反，都必须知道P A.由前讨论可知，用AW攻击，显然不能找到P A.如果用穷搜索方法找n×n阶二进制随机阵P A，则计算复杂性是O(2n2)，当n较大时，这种方法是行不通的.
另一是攻击者不仅知道了E′j，还得到了与其对应的E j，这时攻击者仅需计算
C l=E′j+h(M e,E j,t j)Q A (11)
显然C l能通过修正方案的验签运算.因此要使这种方法攻击成功的关键是找Q A.
用以下方法找到Q A.设C j和C′j分别是消息M j和M′j的签名，E j是这二个签名过程中所用的、同一错误图样，则
C j+C′j=E′j+h(M j,E j,t j)Q A+E′j+h(M′j,E j,t′j)Q A
如果能得到k对消息的签名:C j,C′j,j=1,2,…,k.且每对所用的E j相同，则可得
由此可得 C=MQ A (12)
式中
若M为满秩矩阵，则可以找到Q A=M-1C，其工作因子仅为O(k3).因此只要找到k对线性无关的h(M j,E j, t j)+h(M′j,E j,t′j)，且每对消息使用相同的E j，就可得到Q A.
可知，这种攻击方法成功的关键是得到使用相同E j的签名C j和C′j.假定用户A在签名过程中，在所有可能的错误图样N中等概选取E j，这里
(13)
由Stirling公式不难得到上面的最后一个不等式.
由生日攻击可知［8］、预期所需的签名数目约为，就能得到一对有相同E j的签名.因此，得到一对有相同E j的签名的概率
(14)
另一方面，要找到式(12)的M矩阵中k个线性无关的h(M j,E j,t j)+h(M′j,E j,t j)k重，相当于在2k个k重中找一组基底，找到这组基底的概率
由文献［7］知，当k较大时p C2≈0.29.可知找到Q A矩阵的概率
(15)
所以用广义伪造攻击修正Xin-mei方案成功的概率
(16)
因而攻击成功的工作因子大约是O(P-1C)＞O(p-1C1).当n选取n=500，t A=30，则由(13)、(14)二式可知，攻击成功的工作因子大约是O(287).所以在这种攻击下，修正Xin-mei方案是计算上安全的.
4 讨论
本文提出了如式(6)和(7)所示的二种修正Xin-mei方案，并指出在AW攻击和通用伪造攻击下，这二种修正方案均是计算上安全的.
虽然利用纠错码可以构造出一类数字签名方案，但有以下一些弱点.一是由于所用的码是线性码，因此攻击者往往可以利用这种线性性，进行各种组合伪造签名，或从公钥中解出私钥.所以必须
利用非线性码或非可换的码如秩距离码构造.二是为了阻止错误图样E被攻击者所利用，在验签或译码过程中，最好不要泄露错误图样E，但这一点似乎很难做到.此外，在本文的修正方案中引入了单向hash函数和时戳，看来，在用纠错码构造的各类密码体制(如McEliece公钥体制)中这是必须的.否则，这类密码体制的安全性很难得到充分保证.特别，如果所用的码是线性码，则更是必不可少的.■基金项目：高等学校博士学科点专项科研基金(No.98070104)资助课题由此可组成以下方程
作者简介：王新梅 西安电子科技大学教授，博士生导师，中国电子学会和中国通信学会会士.长期从事信息论、编码和密码学的教学和科研工作.
作者单位：王新梅（西安电子科技大学综合业务网国家重点实验室，西安 710071）
参考文献：
［1］W.Xin-mei.Digital signalture scheme based on error-correcting codes.IEE Electronics Letters,1990,26 (13):898～899
［2］L.Harn and D.C.Wang.Cryptanalysis and modification of digital signature scheme based on error-correcting codes.IEE Electronics letters,1992,28(2):157～159
［3］M.Albbadi and S.B.Wicker.Security of Xin-mei digital signature scheme.IEE Electronics letter,1992,28 (9):890～891
［4］M.Alabbadi and S.B.Wicker.Cryptanalysis of the Harn and Wang modification of the Xin-mei digital signature scheme.IEE Electronics Letters,1992,28(18):1756～1757
［5］Yuan-xing Li.An attack on Xin-mei′s digital signature scheme.IEEE,ISIT'93,1993,236
［6］M.Alabbadi and S.B.Wicker.Digital signature schemes based on error-correcting codes.IEEE ISIT′93,1993,199
［7］M.Alabbad;and S.B.Wicker.Susceptibility of digital signature schemes based on error-correcting codes to universal forgery.IEEE ISIT'94,P.494,1994;Computer Science,1993,829:9～11
［8］D.R.Stinson.Cryptography-Theory and Practise,CRC,Prea,Ins,1995
收稿日期：1998-11-02
修订日期：1999-01-22
纠错码数字签名方案的修正
作者：王新梅， WANG Xin-mei
作者单位：西安电子科技大学综合业务网国家重点实验室,西安,710071
刊名：
电子学报
英文刊名：ACTA ELECTRONICA SINICA
年，卷(期)：2000,28(2)
被引用次数：5次
参考文献(8条)
1.W Xin-mei Digital signalture scheme based on error-correcting codes[外文期刊] 1990(13)
2.L Harn.D C Wang Cryptanalysis and modification of digital signature scheme based on error-correcting codes[外文期刊] 1992(02)
3.M Albbadi.S B Wicker Security of Xin-mei digital signature scheme[外文期刊] 1992(09)
4.M Alabbadi.S B Wicker Cryptanalysis of the Harn and Wang modification of the Xin-mei digital signature scheme 1992(18)
5.Yuan-xing Li An attack on Xin-mei's digital signature scheme 1993
6.M Alabbadi.S B Wicker Digital signature schemes based on error-correcting codes 1993
7.M Alabbad.S B Wicker Susceptibility of digital signature schemes based on error-correcting codes to universal forgery[外文会议] 1994
8.D R Stinson Cryptography-Theory and Practise 1995
引证文献(5条)
1.邓仰明.杜伟章.陈克非构造数字签名方案的一种新方法[期刊论文]-计算机工程与应用 2003(9)
2.徐伶燕基于纠错码的数字签名[期刊论文]-大众科技 2007(10)
3.基于纠错码的数字签名的分析[期刊论文]-计算机工程与应用 2009(29)
4.张振峰.冯登国.戴宗铎基于纠错码的AW数字签名方案的分析[期刊论文]-中国科学E辑 2003(2)
5.张振峰.冯登国.戴宗锋Cryptanalysis on AW digital signature scheme based on error-correcting codes[期刊论文]-中国科学F辑(英文版) 2002(5)
本文链接：https://www.wendangku.net/doc/4e3618405.html,/Periodical_dianzixb200002032.aspx