對Marc Fischlin強(qiáng)RSA簽名方案的改進(jìn)

楊艷華,洪亮,呂克偉

（1.信陽農(nóng)業(yè)高等?？茖W(xué)校,河南信陽 464000；2.信陽師范學(xué)院,河南信陽 464000；3.中科院研究生院，北京 100049）

2000年Cramer和Shoup[1]基于強(qiáng)RSA假設(shè),提出了一個可以抵御適應(yīng)性選擇消息攻擊的簽名方案,該方案利用一個1 024比特RSA模和一個160比特消息雜湊值,產(chǎn)生一個大約2 200比特的數(shù)字簽名.近年來,Fischlin[2]在強(qiáng)RSA的假設(shè)下對Cramer-Shoup的簽名方案進(jìn)行了修改,使其簽名長度縮短了近一半.但方案中涉及到了異或運(yùn)算,因此較難被應(yīng)用于分布式系統(tǒng).本文對Fischlin的簽名方案進(jìn)行了改進(jìn)，使其有更加廣泛的應(yīng)用.

1 預(yù)備知識

1.1 數(shù)字簽名

數(shù)字簽名方案一般包括三部分：鑰生成算法、簽名生成算法和驗(yàn)證算法.

密鑰生成：輸入1k（其中k為安全參數(shù)）,算法產(chǎn)生一個公、私鑰對（kp，ks）.

簽名生成：給定一個消息m和一個公、私鑰對（Kp，Ks）,算法產(chǎn)生一個簽名δ.

驗(yàn)證ver：驗(yàn)證者得到消息及簽名δ,利用公共數(shù)據(jù)對簽名δ進(jìn)行驗(yàn)證.如果ver（m，δ）為真,則該簽名有效.否則，簽名無效.

目前,對數(shù)字簽名的攻擊主要有兩類攻擊：唯密鑰攻擊、已知-消息攻擊，其中已知-消息攻擊又分為以下情形：已知消息攻擊、一般選擇消息攻擊、定向選擇消息攻擊、適應(yīng)性選擇消息攻擊,它們的攻擊強(qiáng)度依次增加.

數(shù)字簽名的攻擊結(jié)果有如下情形：揭示簽名者的私鑰、構(gòu)造一個高效的算法、提供一個新的有效的消息簽名對,此攻擊也稱為“存在性偽造”,它們的破壞程度依次減少.

1.2 數(shù)字簽名方案的安全性

本文主要針對“存在性偽造”攻擊進(jìn)行分析.一個數(shù)字簽名是安全的,若在適應(yīng)性的消息攻擊下,存在性偽造計(jì)算是不可能的.

1.3 強(qiáng)RSA假設(shè)

強(qiáng)RSA假設(shè)：給定一個隨機(jī)生成的RSA模n以及一個隨機(jī)z∈Z*n，較難找到一個大于1的整數(shù)r和 y∈使得 yr∈Z.

目前為止,解決RSA問題的唯一已知方法是解決整數(shù)分解問題.

1.4 Fishlin簽名方案

2 改進(jìn)的Fishlin簽名方案

3 安全性分析

定理1：在強(qiáng)RSA假設(shè)下,改進(jìn)的Fishlin方案是可以抵御適應(yīng)性選擇消息攻擊的安全的簽名方案.

適應(yīng)性選擇消息攻擊是最強(qiáng)的一種攻擊.因此,本文在該攻擊下討論改進(jìn)方案的安全性.

由上面分析可以看出：本文改進(jìn)的簽名方案是可以抵御適應(yīng)性選擇消息攻擊的安全的數(shù)字簽名方案.

4 結(jié)論

本文基于強(qiáng)RSA假設(shè)改進(jìn)了Fischlin的簽名方案，改進(jìn)后的方案仍為可以抵御適應(yīng)性選擇消息攻擊的安全的數(shù)字簽名方案,并且該簽名方案與原方案相比簽名長度和效率均相當(dāng).但是由于本文將Fischlin方案當(dāng)中的無碰撞函數(shù)值以及隨機(jī)比特串均縮短一個比特,又將異或運(yùn)算改為了加法運(yùn)算,因而改進(jìn)后的方案有了更加廣泛的應(yīng)用，特別適用于分布式系統(tǒng).

雖然本文基于強(qiáng)RSA假設(shè)改進(jìn)了原數(shù)字簽名方案并將其加以推廣,但是改進(jìn)的方案在安全性證明方面仍未擺脫強(qiáng)RSA假設(shè),如果有更加好的假設(shè)條件對新方案安全性加以證明那將是更大的創(chuàng)新.

[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.