基于纠错码的AW数字签名方案的分析术.pdfVIP

中 国 柳 (E 辑) 第 33卷 第 2期 SCIENCEINCHINA(SeriesE) 2003年 2月 基于纠错码的AW 数字签名方案的分析术 张振峰 冯登国 戴宗铎 (中国科学院研究生院信息安全 国家重点实验室，北京 1~ 39) 摘要 1993年Alabbadi和Wicker对基于纠错码的Xinmei数字签名方案提出了一种 改进方案，通常称为AW 方案．证明了该方案存在严重的安全问题：任何人仅利用签名 用户的公钥就可以构造等价的签名私钥，从而成功地实现伪造签名．同时指出，基于大 矩阵分解的困难性很难构造出安全性较高的数字签名方案． 关键词 数字签名 纠错码 密码分析 利用一般线性码的译码问题是 NP完全问题，结合 Goppa码具有快速译码算法 的特点， McEliecel’1于 1978年首次提 出了一个基于纠错码的公钥密码体制，人们认为该体制只能用于 数据加密，而不具有数字签名的能力．1990年，王新梅 2【提出了一类基于纠错码的数字签名方 案(Xinmei方案)．自Xinmei方案提出来之后，不少学者对其安全性进行 了分析．1992年Alabbadi 和Wicker13,41对Xinmei方案提出了两种选择明文攻击方法，并且在此基础上提出了一个改进方 案，通常称之为 AW 方案5【】．本文用叶顶峰等 6【利用求矩阵广义逆实现伪造攻击的思想，证明 了 AW 方案存在严重的安全漏洞：任何人仅利用签名用户的公钥就可以构造出等价的签名私 钥，从而成功地实现伪造签名；同时指 出，建立在大矩阵分解困难性 的基础上很难构造出安全 性较高的数字签名方案． 1 AW 数字签名方案介绍 假定通信双方是用户A和B．首先用户A选择一个非线性函数f(，y)并把它公开，这里 是二进制 k重向量，Y是二进制 n重向量，其输出是二进制 k重向量． 用户 A选择一个 n【，Ii：，d≥2t+1】二进制 Goppa码 以及其生成矩阵G和校验矩阵H．矩 阵G满足GG =，，尸是 上一个满秩的随机矩阵， 是一个秩为 n的n×，矩阵，这里 ln， 矩阵 满足 =，．用户A的公钥为 (G，H ，w ，H，t，)其中 G =P—lG H ：P—lH t f． ， ， A保留其私钥G，P，G ，w． 产生签名的方法如下：用户 A随机地选取一个 Hamming重量co(E)≤f的二进制 n重向量 E，以及长度为 z的二进制随机向量z满足co(z) z／2．对消息 的签名是长度为 z的序列： C：“E+(f(M，E)+EG)G)P+ZW}W+Z． (1) 2001．12—17收稿，2002．05．09收修改稿 }国家重点基础研究发展规划 “九七三 ” 资助项 目(G1999035802)和国家杰出青年科学基金项 目 E—mail：zfzhang@ is．ac．cn 第 2期 张振峰等：基于纠错码的AW 数字签名方案的分析 165 用户A把 ( ，C)发送给用户 B． 当用户B接收到 ( ，C)后，实施以下步骤验证签名： 首先计算 = CW={(E+(，(，EG)G)P+ZW)删+ZW = {(E+(，(㈤+EG)G)P+ZW)+ZW = EP+lf(M，E)+EG’)GP， 这里用到了删 =，．然后利用A的公钥H =P H 计算伴随式 VH={+(，(M，￡)+EG)GP}PH=EH， 因为GH =0．从而利用 Berlekamp．Massey算法译码 即可得到 E．另一方面 = {+(，(，E)+EG)GP}PG=嬲+f(M +EGfM( ． (2) 用户B使用收到的消息M和译码得到的E