RSA型基于證書簽名方案

郭亞峰, 黃 慧, 陳紅英

(1.漳州城市職業(yè)學(xué)院 電子信息工程系,福建 漳州 363000; 2.閩南師范大學(xué) 計(jì)算機(jī)學(xué)院,福建 漳州 363000)

密碼學(xué)家Gentry[1]在2003年歐密會(huì)上首次提出基于證書公鑰密碼(certificate-based public key cryptog-raphy,CB-PKC)的概念.在CB-PKC系統(tǒng)中,公鑰的證書直接被用作解密或簽名密鑰的一部分,解決了傳統(tǒng)公鑰基礎(chǔ)設(shè)施(public key infrastructure, PKI)證書管理問題;另一方面,由于證書只是密鑰的一部分,還有另一部分密鑰只有用戶才知道,也解決了基于身份公鑰密碼[2](identity-based cryptography, IBC)的密鑰托管問題,證書的分發(fā)也不需要保密信道.2004年Kang等[3]將基于證書概念平移到數(shù)字簽名,研究基于證書簽名(certificate-based signature,CBS), 文獻(xiàn)[3]給出CBS的安全模型和第一個(gè)可證明安全的CBS方案.Wu等[4]對(duì)CBS與無(wú)證書簽名方案[5](certificateless signature,CLS)之間的關(guān)系進(jìn)行了研究,提出一種從CLS到CBS的通用轉(zhuǎn)換方法,并證明該方案是安全的.2012年Li等[6]提出只有一個(gè)群元素的短CBS,其方案的簽名只是一個(gè)群元素,但方案在簽名過程、驗(yàn)證過程都需要3個(gè)雙線對(duì)運(yùn)算,效率并不高.為了提高CBS簽名方案的效率.Hung等[7]基于CDH假設(shè)提出了一種短CBS方案,然而,Kumar等[8]指出Hung等[7]方案不能抵抗無(wú)證書用戶的攻擊.Lu等[9]提出了一種改進(jìn)的不需要隨機(jī)預(yù)言機(jī)假設(shè)的CBS方案.在標(biāo)準(zhǔn)模型下,Zhou等[10]與Wang等[11]分別提出了基于雙線性對(duì)的CBS方案.基于格和短整數(shù)解(SIS)假設(shè),Tseng等[12]提出了一個(gè)新的高效CBS方案.Wu等[13]提出了抗泄漏CBS,可以防止側(cè)信道攻擊.左黎明等[14]也提出了一個(gè)短CBS方案. 2022年Khan等[15]將基于證書簽名方案應(yīng)用于工業(yè)物聯(lián)網(wǎng)系統(tǒng),為其提供安全保障.上述方案都使用雙線對(duì),因此計(jì)算開銷比較大.榮維堅(jiān)等[16]基于整數(shù)分解問題提出了一個(gè)可證明安全的基于證書數(shù)字簽名方案.本文主要目的是基于RSA困難性假設(shè),提出一個(gè)新的基于證書簽名方案.提高基于證書簽名方案的效率,與已有的方案比較表明,所提出的方案在證書生成、簽名生成和簽名驗(yàn)證、簽名長(zhǎng)度方面都有明顯的優(yōu)勢(shì),可用于對(duì)帶寬需求較小的系統(tǒng)中.

1 預(yù)備知識(shí)

定義2(RSA困難性假設(shè))不存在能以不可忽略的概率解RSA問題的概率多項(xiàng)式算法.

2 基于證書簽名

2.1 基于證書簽名的定義

基于證書簽名方案由下列5個(gè)算法組成:

建立算法:該算法通常由權(quán)威機(jī)構(gòu) (certificate authority, CA)進(jìn)行,用以產(chǎn)生系統(tǒng)主密鑰對(duì)及公開參數(shù).

用戶密鑰生成:該算法通常由用戶進(jìn)行,用以產(chǎn)生系統(tǒng)用戶的主密鑰對(duì).

證書生成:該算法通常由CA進(jìn)行,用以產(chǎn)生用戶簽名密鑰的組成部分的證書.

簽名生成:該算法通常由用戶進(jìn)行,用以產(chǎn)生用戶待簽名消息的簽名.

簽名驗(yàn)證:該算法通常由第三方進(jìn)行,對(duì)消息簽名對(duì)進(jìn)行驗(yàn)證,判定消息簽名對(duì)是否有效.

2.2 基于證書簽名的安全定義

2.2.1游戲1

2.2.2游戲2

3 本文方案

本文方案的算法組成如下.

建立算法(Setup):輸入系統(tǒng)安全參數(shù)1k,證書機(jī)構(gòu)選取隨機(jī)安全大素?cái)?shù){pCA,qCA},然后計(jì)算NCA=pCAqCA.選取隨機(jī)eCA滿足gcd(eCAφ(NCA))=1.計(jì)算dCA滿足eCAdCA=1(modNCA).秘密保存{pCA,qCA,dCA}作為系統(tǒng)主私鑰SKCA, 公開{NCA,eCA}作為系統(tǒng)主公鑰PKCA.

用戶密鑰生成(Userkeygen):輸入系統(tǒng)安全參數(shù)1k,用戶ID選取隨機(jī)安全大素?cái)?shù){pID,qID},然后計(jì)算NID=pIDqID.選取隨機(jī)eID滿足gcd(eID,φ(NID))=1,及dID滿足eIDdID=1(modNID).設(shè)置用戶私鑰SKID={pID,qID,dID},用戶公鑰PKID={NID,eID}.

(ⅰ)計(jì)算R=reCA(modNCA).

σ2=rVh1(modNCA).

消息m的簽名為σ={σ1,σ2}.

簽名驗(yàn)證(Verify):當(dāng)接收者想判定σ={σ1,σ2}是否為消息m在公鑰PKCA和PKID下的有效簽名時(shí),按下列方式進(jìn)行簽名驗(yàn)證.

4 安全性證明

4.1 正確性

通過下列簡(jiǎn)單驗(yàn)算可知方案生成的簽名可以通過驗(yàn)證:

reCA(modNCA)=R(modNCA).

4.2 不可偽造性

本文方案的安全性基于RSA困難性假設(shè),即若存在攻擊者A可以攻破上述基于證書簽名方案,則挑戰(zhàn)者C可以解RSA問題.

式中E為一次冪指數(shù)運(yùn)算的時(shí)間,k為安全參數(shù).

若coin=1,則令

由此可得RSA問題的解

概率分析:根據(jù)以上交互模擬可知,當(dāng)且僅當(dāng)以下事件都發(fā)生時(shí),C可以解RSA問題.

ξ′=Pr[E1∧E2∧E3]=

Pr[E1]·Pr[E2/E1]·Pr[E3/E1∧E2].

若E1發(fā)生,則表明在簽名詢問交互過程中C的應(yīng)答沒有中止,其概率至少為

此外有

式中:E為一次冪指數(shù)運(yùn)算的時(shí)間,k為安全參數(shù).

當(dāng)IDj≠IDt時(shí),令

當(dāng)IDj=IDt時(shí),C隨機(jī)選取coin∈{0,1}使得概率Pr(coin=0)=δ.若coin=0,則C令

若coin=1,則C令

無(wú)論哪種情形,若H1j=0(modeCA),則重新選擇σ,重新計(jì)算H1j.

當(dāng)coin=0時(shí), 簽名失敗,終止交互.當(dāng)coin=1時(shí),令

概率分析:根據(jù)以上交互模擬可知,當(dāng)且僅當(dāng)以下事件都發(fā)生時(shí)C可以解RSA問題.

因此C的優(yōu)勢(shì)為

ξ′=Pr[E1∧E2∧E3]=

Pr[E1]·Pr[E2/E1]·Pr[E3/E1∧E2].

若E1發(fā)生,則表明在私鑰詢問交互過程中C沒有中止.在簽名詢問交互過程中C的應(yīng)答沒有中止,故

此外

交互模擬所用時(shí)間為

由引理1和引理2直接可得下列結(jié)論.

定理1在RSA困難性假設(shè)和隨機(jī)預(yù)言機(jī)模型下,上述方案是能夠抵抗敵手適應(yīng)性存在性不可偽造的.

5 性能分析

5.1 效率比較

雙線性對(duì)是公認(rèn)的計(jì)算開銷比較大的運(yùn)算,本文方案基于RSA困難問題,不需要雙線性對(duì),因此效率較高.表1是本文新方案與近年來(lái)提出的已知效率較高方案的比較,其中, P、M、E分別用于標(biāo)識(shí)雙線性對(duì)運(yùn)算、標(biāo)量乘法運(yùn)算、指數(shù)運(yùn)算.

表1 效率比較

比較結(jié)果顯示:本文方案在證書生成和簽名驗(yàn)證方面是所有方案中最優(yōu)的.雖然在簽名生成方面略差于文獻(xiàn)[14]的短簽名方案,但通常情況下簽名只進(jìn)行一次,而簽名驗(yàn)證可能會(huì)由不同人在不同時(shí)間進(jìn)行多次,因此簽名驗(yàn)證的效率更有意義.

5.2 實(shí)驗(yàn)仿真

我們對(duì)本方案進(jìn)行了實(shí)驗(yàn)仿真測(cè)試,運(yùn)行環(huán)境如下:操作系統(tǒng): Windows 10 專業(yè)版 64位;主板: 華碩 TUF GAMING B550M-PLUS (WI-FI);處理器: AMD Ryzen 5 3500X 6-Core六核;內(nèi)存:16 GB(威剛 DDR4 3 200 MHz). 采用Python語(yǔ)言實(shí)現(xiàn)本文簽名方案.

實(shí)驗(yàn)結(jié)果見圖1.結(jié)果表明,本文方案在證書生成、簽名生成、簽名驗(yàn)證方面非常高效.當(dāng)選取安全參數(shù)1 024位時(shí),對(duì)方案進(jìn)行100次實(shí)驗(yàn)測(cè)試,證書生成時(shí)間平均僅為0.023 s,簽名生成時(shí)間平均僅為0.051 s,簽名驗(yàn)證時(shí)間平均僅為0.029 s. 當(dāng)選取安全參數(shù)2 048位時(shí),對(duì)方案進(jìn)行100次測(cè)試,方案證書生成時(shí)間平均僅為0.163 s,簽名生成時(shí)間平均僅為0.344 s,簽名驗(yàn)證時(shí)間平均僅為0.184 s.

圖1 不同安全參數(shù)方案生成時(shí)間

實(shí)驗(yàn)結(jié)果表明:安全參數(shù)1 024位方案是非常高效的,非常適用于帶寬較小的設(shè)備系統(tǒng);安全參數(shù)2 048位的方案非常適用于對(duì)安全要求較高的系統(tǒng).

6 結(jié)語(yǔ)

本文基于RSA困難性假設(shè)構(gòu)造了一種全新的基于證書簽名方案,與已有的方案相比,該方案具有明顯的效率優(yōu)勢(shì).下一步將研究將本簽名方案運(yùn)用到云計(jì)算、物聯(lián)網(wǎng)、區(qū)塊鏈等實(shí)際的應(yīng)用系統(tǒng)中,為數(shù)字信息系統(tǒng)提供安全性保障.