对Marc Fischlin强RSA签名方案的改进

杨艳华,洪亮,吕克伟

（1.信阳农业高等专科学校,河南信阳 464000；2.信阳师范学院,河南信阳 464000；3.中科院研究生院，北京 100049）

2000年Cramer和Shoup[1]基于强RSA假设,提出了一个可以抵御适应性选择消息攻击的签名方案,该方案利用一个1 024比特RSA模和一个160比特消息杂凑值,产生一个大约2 200比特的数字签名.近年来,Fischlin[2]在强RSA的假设下对Cramer-Shoup的签名方案进行了修改,使其签名长度缩短了近一半.但方案中涉及到了异或运算,因此较难被应用于分布式系统.本文对Fischlin的签名方案进行了改进，使其有更加广泛的应用.

1 预备知识

1.1 数字签名

数字签名方案一般包括三部分：钥生成算法、签名生成算法和验证算法.

密钥生成：输入1k（其中k为安全参数）,算法产生一个公、私钥对（kp，ks）.

签名生成：给定一个消息m和一个公、私钥对（Kp，Ks）,算法产生一个签名δ.

验证ver：验证者得到消息及签名δ,利用公共数据对签名δ进行验证.如果ver（m，δ）为真,则该签名有效.否则，签名无效.

目前,对数字签名的攻击主要有两类攻击：唯密钥攻击、已知-消息攻击，其中已知-消息攻击又分为以下情形：已知消息攻击、一般选择消息攻击、定向选择消息攻击、适应性选择消息攻击,它们的攻击强度依次增加.

数字签名的攻击结果有如下情形：揭示签名者的私钥、构造一个高效的算法、提供一个新的有效的消息签名对,此攻击也称为“存在性伪造”,它们的破坏程度依次减少.

1.2 数字签名方案的安全性

本文主要针对“存在性伪造”攻击进行分析.一个数字签名是安全的,若在适应性的消息攻击下,存在性伪造计算是不可能的.

1.3 强RSA假设

强RSA假设：给定一个随机生成的RSA模n以及一个随机z∈Z*n，较难找到一个大于1的整数r和 y∈使得 yr∈Z.

目前为止,解决RSA问题的唯一已知方法是解决整数分解问题.

1.4 Fishlin签名方案

2 改进的Fishlin签名方案

3 安全性分析

定理1：在强RSA假设下,改进的Fishlin方案是可以抵御适应性选择消息攻击的安全的签名方案.

适应性选择消息攻击是最强的一种攻击.因此,本文在该攻击下讨论改进方案的安全性.

由上面分析可以看出：本文改进的签名方案是可以抵御适应性选择消息攻击的安全的数字签名方案.

4 结论

本文基于强RSA假设改进了Fischlin的签名方案，改进后的方案仍为可以抵御适应性选择消息攻击的安全的数字签名方案,并且该签名方案与原方案相比签名长度和效率均相当.但是由于本文将Fischlin方案当中的无碰撞函数值以及随机比特串均缩短一个比特,又将异或运算改为了加法运算,因而改进后的方案有了更加广泛的应用，特别适用于分布式系统.

虽然本文基于强RSA假设改进了原数字签名方案并将其加以推广,但是改进的方案在安全性证明方面仍未摆脱强RSA假设,如果有更加好的假设条件对新方案安全性加以证明那将是更大的创新.

[1]Cramer R,Shoup V.Signature Schemes Based on the Strong RSA Assumption [M].ACM Transactions on Information and System Security,2000：161-185.

[2]Marc Fischlin.The Cramer-Shoup Strong-RSA Signature Scheme Resvisited [M].PKC 2003,LNCS 2567,Springer-Verlag，2003：116-129.

[3]Goldwasser S,Micali S,Rivest R..A digital signature scheme secure Against adaptive chosen-message attacks[J].SIAM J.Comput,1988,17（2）：281-308.

[4]Guiliou L C,Quisquater J J.A practical zero-knowledge protocol fitted to security miscroprocessorminimizing both tranmission and memory[M].In Proceedings of EUROCRYPT’88,LNCS,Springer-Verlag,1988：123-139.

[5]Bellare M,Rogaway P.Random Oracles Are Practical:a Paradigm for Designing Efficient Protocols [M].In Proc of the 1st CCCS,ACM Press,New York,1993：62-73.