基于ＲＳＡ的多重簽密方案

摘要：指出原有多重簽密方案存在的缺陷，并提出一種新的基于RSA的多重簽密方案。本方案以RSA密碼體制為基礎(chǔ)，借鑒了原有多重簽密方案的結(jié)構(gòu)特點(diǎn)。改善了原有多重簽密方案的缺陷，在安全性上實(shí)現(xiàn)了消息保密性、不可偽造性、不可否認(rèn)等特性，同時(shí)考慮了原始消息的安全發(fā)送問題。在同等安全下，本方案比傳統(tǒng)的先簽名再加密方式，在執(zhí)行效率和執(zhí)行靈活性方面具有更多優(yōu)勢(shì)。基于RSA密碼體制的廣泛應(yīng)用，方案簡(jiǎn)潔且易于建立，適合在電子政務(wù)和電子商務(wù)環(huán)境下為消息的安全傳遞提供認(rèn)證加密保護(hù)。

關(guān)鍵詞：簽密； 多重簽密；RSA； 承諾方案； 保密性； 不可偽造性； 不可否認(rèn)

中圖分類號(hào)：TN918.2

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2008)06－1836－03

多重簽密是多用戶環(huán)境下對(duì)簽密技術(shù)的一種擴(kuò)展。相比多重簽名技術(shù)，多重簽密能在實(shí)現(xiàn)消息完整性保護(hù)的同時(shí)提供對(duì)消息的機(jī)密性保護(hù)。多重簽密在電子政務(wù)和電子商務(wù)方面具有現(xiàn)實(shí)意義。比如在電子政務(wù)中，某公文在公開發(fā)布之前需要多個(gè)部門進(jìn)行審批或修訂。這一過程中需要對(duì)公務(wù)進(jìn)行保密傳遞，并確保在審批過程中各部門對(duì)公文的授權(quán)修改。一個(gè)安全靈活的多重簽密方案應(yīng)該滿足消息保密、消息不可偽造、消息不可否認(rèn)等安全特性，同時(shí)還要求方案執(zhí)行效率高、執(zhí)行順序靈活、易于構(gòu)建。

1相關(guān)工作

多重簽密在文獻(xiàn)[1]中由Mitomi等人首先提出，Mitomi方案是在多重簽名的基礎(chǔ)上附加了加密功能。遺憾的是該方案中任何人都可以恢復(fù)驗(yàn)證參數(shù)從而進(jìn)行密文解密，因此方案完全不具備保密特性；Pang等人在文獻(xiàn)[2]中提出了對(duì)Mitomi方案的修改方案，但方案限定只能由最初的消息發(fā)送者作為最后的接收驗(yàn)證者，且簽密執(zhí)行順序必須事先固定，因此該方案缺乏靈活性。Seung等人在文獻(xiàn)[3]中提出新的多重簽密方案。該方案能提供消息機(jī)密性和完整性保護(hù)，且簽密執(zhí)行順序靈活。但該方案與Pang方案一樣，限定只能由消息的原始發(fā)送者進(jìn)行最后的驗(yàn)證。張鍵紅等人在文獻(xiàn)[4]中提出了一個(gè)多重簽密模型，該模型實(shí)現(xiàn)了消息機(jī)密性完整性保護(hù)，執(zhí)行順序靈活，且對(duì)最終的驗(yàn)證者沒有限制。但該方案中，最終的多重簽密密文長(zhǎng)度會(huì)隨著簽密人數(shù)的增多而增大，降低了通信過程中的傳輸效率。值得注意的是，以上多重簽密方案都是基于最初的Zheng簽密[5]。因此這些方案不可避免地繼承了Zheng簽密在不可否認(rèn)性上存在的不足，即進(jìn)行不可否認(rèn)驗(yàn)證必須公開接收方的私鑰，而公開用戶的私鑰在實(shí)際的應(yīng)用中是不可取的。

由于在實(shí)際應(yīng)用中對(duì)認(rèn)證加密的需求，最近許多新的簽密體制被陸續(xù)提出[6~8]。其中一類基于陷門置換的簽密體制借鑒了構(gòu)造可證明安全的公鑰加密體制填充技術(shù)，使得明文在經(jīng)過隨機(jī)填充后，可以通過任意的陷門置換同時(shí)進(jìn)行加密和簽名。這類簽密體制在安全性、實(shí)現(xiàn)的靈活性和兼容性方面都具有顯著的優(yōu)勢(shì)。Dodis等人[8]提出的填充并行簽密是這類簽密技術(shù)的佼佼者。首先，在內(nèi)部安全模式下（insider security model），該簽密體制能達(dá)到選擇密文攻擊下加密的語義安全性(IND－CCA2)、選擇消息攻擊下簽名的強(qiáng)不可偽造性 (sUF－CMA )以及消息不可否認(rèn)性(non－repudiation)；其次，由于允許加密和簽名的并行處理，該簽密體制比傳統(tǒng)的利用陷門置換先簽名再加密的方式減少了近一半的計(jì)算時(shí)間開銷。

RSA是目前使用最為廣泛的一種陷門置換函數(shù)，已成為眾多實(shí)際安全協(xié)議、安全標(biāo)準(zhǔn)的核心算法，它既可以用于消息加密也可以用于消息簽名。本文根據(jù)填充并行簽密提出一種新的RSA的多重簽密方案，并對(duì)該方案進(jìn)行了分析。新的多重簽密方案改善了原有多重簽密方案的缺陷，在安全性上實(shí)現(xiàn)了消息保密性、不可偽造性、不可否認(rèn)性等特性。同時(shí)，本方案能向后兼容PKCS#1公鑰密碼基礎(chǔ)結(jié)構(gòu)，支持發(fā)送方和接收方不同的RSA密鑰長(zhǎng)度，且在執(zhí)行順序上更具有靈活性。本方案適合在電子政務(wù)和電子商務(wù)環(huán)境下為消息的安全傳遞提供認(rèn)證加密保護(hù)。

2基于RSA的多重簽密方案

根據(jù)對(duì)現(xiàn)有簽密方案結(jié)構(gòu)的分析，基于RSA密碼體制，給出一種新的多重簽密方案。該方案分為以下幾個(gè)執(zhí)行階段。

1）系統(tǒng)建立

設(shè)(u，v)←Commit(m)是一個(gè)消息可恢復(fù)的承諾方案，若(u，v)是m的有效承諾和公開承諾對(duì)，那么對(duì)應(yīng)的消息恢復(fù)算法可以恢復(fù)消息m←Open(u，v)；否則⊥←Open(u，v)；

(E，D)是對(duì)稱加密和解密函數(shù)； H是一個(gè)碰撞免疫的強(qiáng)密碼hash函數(shù)。

設(shè)RSA(e，n)(x)為RSA加密/簽名驗(yàn)證算法描述。其中，（e，n）是用戶的RSA公鑰，即RSA(e，n）(x){y=xe mod n}

設(shè)RSA(e，n)(x)為RSA解密/簽名算法描述。其中，d是用戶的RSA私鑰，即RAS（d，n)-1(x){y=xd mod n}

公開〈(Commit， open)，(E，D)，H，(RSA，RSA-1)〉

2）用戶密鑰建立和管理

每個(gè)系統(tǒng)用戶Ui通過執(zhí)行RSA密鑰生成算法：

首先，選取兩個(gè)大素?cái)?shù)pi和qi，計(jì)算ni=piqi和ni的歐拉函數(shù)(ni)=(pi-1)(qi-1)；隨機(jī)選取與(ni)互素的整數(shù)ei，1＜ei＜(ni)，滿足gcd(ei，(ni))=1；根據(jù)歐幾里得算法計(jì)算民主一的整數(shù)di(1＜di＜(ni))，使得eidi≡1 mod (ni)。秘密銷毀pi、qi、(ni)，公布公鑰(ei，ni)用于加密和簽名驗(yàn)證，保存di作為私鑰用于解密和數(shù)字簽名。

基于PKCS#1公鑰密碼基礎(chǔ)結(jié)構(gòu)，設(shè)定系統(tǒng)存在一個(gè)可信第三方CA，CA執(zhí)行RSA密鑰生成算法，生成公鑰(eCA，nCA)向全體用戶廣播，私鑰dCA自己保留。

每個(gè)合法用戶需要將自己的公鑰(ei，ni)、身份IDi以及簽名消息RSA(di，ni)-1((ni，ei)‖IDi)發(fā)送給CA。CA利用用戶公鑰驗(yàn)證合法后，為用戶產(chǎn)生并發(fā)放公鑰證書Certi={RSA(dCA，nCA)-1((ni，ei)‖IDi)，(ni，ei)‖IDi，Exi}，為用戶公鑰數(shù)據(jù)的真實(shí)性進(jìn)行證實(shí)。其中，Exi為證書有效時(shí)限、證書號(hào)等其他信息。

3）原始消息的安全發(fā)放和恢復(fù)

用戶 Us作為原始消息的擁有者，需要安全地將原始消息M0發(fā)送給多個(gè)簽密的用戶并指定最終的密文接收者。假定需要對(duì)消息進(jìn)行修訂并簽密的用戶為{U1，…，Un}，他們構(gòu)造一個(gè)簽密用戶子群。由發(fā)送者Us指定最終的接收者為Ur。Us首先從CA處獲得簽密用戶{U1，…，Un}的公鑰證書，隨后選擇一個(gè)隨機(jī)數(shù)K0←{0，1}

3安全性與執(zhí)行效率分析

3．1安全性分析

本方案使用的填充并行簽密的安全性在文獻(xiàn)[8]中進(jìn)行了詳細(xì)證明，指出若承諾方案Commit滿足可證明消息隱藏性和消息安全可恢復(fù)性，那么該簽密是強(qiáng)可證明安全的。直觀地在多重簽密的執(zhí)行過程中，可以看出對(duì)消息的加密實(shí)際使用了隨機(jī)選取密鑰的對(duì)稱加密算法實(shí)現(xiàn)。而會(huì)話密鑰通過承諾方案進(jìn)行了信息隱藏。隨后又對(duì)會(huì)話密鑰的承諾與參與者的身份信息的計(jì)算得到hash值與會(huì)話密鑰的公開承諾進(jìn)行一次Feistel交換，交換的目的在于獲得了更大程度的數(shù)據(jù)擴(kuò)散。最后才采用RSA對(duì)這些置亂后、具有隨機(jī)性的信息進(jìn)行了加密和數(shù)字簽名。原始的RSA加密算法和簽名算法都屬于確定性加密算法和確定性簽名算法，通過隨機(jī)填充使得輸入的加密消息和簽名消息分別更隨機(jī)，從容獲得更高的安全性。

如果攻擊者截獲某簽密用戶Ui發(fā)送的(IDi，Ci，ai，βi)希望解密恢復(fù)消息，那么必須獲得隨機(jī)選擇的會(huì)話密鑰Ki。而Ki由承諾方案進(jìn)行了信息隱藏，如果要恢復(fù)Ki必須計(jì)算得到有效的承諾和公開承諾對(duì)(ui，vi)。在簽密中Ki的承諾ui由接收者的公鑰加密。在接收者私鑰保密的前提下，由RSA的陷門逆置換特性決定了恢復(fù)ui是困難的；另外對(duì)于Ki的公開承諾vi=H(￡i，ui)si。其中：si利用發(fā)送者的公鑰是可恢復(fù)的。但在ui未知的條件下，因?yàn)镠是抗碰撞的強(qiáng)密碼雜湊函數(shù)，計(jì)算H(￡i，*)=H(￡i，ui)是困難的，從而也無法恢復(fù)公開承諾vi。在獲得Ki的有效承諾和公開承諾對(duì)困難的條件下，根據(jù)承諾方案消息安全可恢復(fù)特性獲得會(huì)話密鑰Ki是困難的，因此攻擊者無法解密恢復(fù)消息，本方案保證了消息的機(jī)密性。

消息的完整性保護(hù)是要抗擊消息未經(jīng)授權(quán)修改的安全服務(wù)。在本文的多重簽密體制中，每個(gè)簽密用戶Ui都對(duì)利用RSA簽名算法和自己的私鑰對(duì)si進(jìn)行數(shù)字簽名，即

其中：si←H(￡i，ui)vi‖RSAdCA，nCA)-1((ei，ni)‖IDi))包含了會(huì)話密鑰承諾和雙方身份的雜湊值、CA對(duì)用戶身份和公鑰的簽名。攻擊者在不知道合法用戶私鑰的前提下無法偽造對(duì)si的簽名。另外在消息安全發(fā)放階段，實(shí)際已經(jīng)由消息的原始擁有者Us確定了一個(gè)多重簽密合法用戶的子群，執(zhí)行過程中每個(gè)簽密用戶Ui都首先會(huì)對(duì)接收到的簽密密文進(jìn)行驗(yàn)證，如果其中某次驗(yàn)證不成功則拒絕該密文，并發(fā)出警告。最后接收者在恢復(fù)消息的過程中，還要逐一地對(duì)每個(gè)簽密密文進(jìn)行驗(yàn)證。這樣本方案中每一環(huán)節(jié)都包含了對(duì)消息完整性的驗(yàn)證。

3．2執(zhí)行效率分析

密碼方案的執(zhí)行效率一般從計(jì)算時(shí)間開銷和通信帶寬開銷兩方面進(jìn)行分析，同時(shí)也需要考慮明文消息的長(zhǎng)度以及能獲得的安全程度。本文提出的多重簽密方案實(shí)際的執(zhí)行效率與具體選用各密碼元件密切相關(guān)，因此本方案的執(zhí)行效率分析將不著眼于與某個(gè)原有多重簽密方案進(jìn)行比較。

本方案中每個(gè)簽密用戶的計(jì)算時(shí)間開銷主要集中在對(duì)稱加密E計(jì)算、承諾方案Commit計(jì)算和RSA加密與簽名計(jì)算。對(duì)稱加密算法比公鑰密碼加密算法更適合加密長(zhǎng)消息，且執(zhí)行效率更高。直接利用RSA就可以對(duì)消息進(jìn)行加密和簽名，前文已指出，若直接使用RSA不能提供加密消息的不可區(qū)分性安全和簽名消息的不可偽造性安全。因此在進(jìn)行加密和簽名前需要對(duì)明文進(jìn)行填充，比如OAEP、PSS－R等都是可行的填充方法。本方案中使用Feistel交換后得到隨機(jī)化的消息對(duì)，可并行實(shí)現(xiàn)加密和簽名。在保證同等安全的前提下，比傳統(tǒng)的使用陷門置換先簽名再加密的方式節(jié)約計(jì)算時(shí)間開銷。因此承諾方案Commit的執(zhí)行效率是整個(gè)簽密執(zhí)行效率的關(guān)鍵。Dodis等人提出了簡(jiǎn)潔高效的承諾方案[8]可應(yīng)用于多重簽密方案，簡(jiǎn)述如下：輸入消息為m，對(duì)任意參數(shù)a∈[0，|m|]，將消息m分為兩部分，即m=m1‖m2，滿足|m1|=a且|m2|=|m|-a。選擇一個(gè)隨機(jī)數(shù)r，計(jì)算d←m2‖r，c←(m1G(r))‖G′(m2‖r）。該承諾方案與Feistel交換結(jié)合稱為概率簽名加密填充。該計(jì)算過程中涉及兩個(gè)抗碰撞的密碼雜湊函數(shù)G：{0，1}→{0，1}a和G′:{0，1}→{0，1}計(jì)算和一次異或運(yùn)算，計(jì)算時(shí)間開銷上優(yōu)于或等同于原有填充技術(shù)。

在通信帶寬開銷上，本方案比原有的多重簽密方案有很大提高。原有多重簽密方案中，最后輸出的多重簽密密文只是每個(gè)簽密用戶輸出密文的簡(jiǎn)單集合，密文形式上類似于{(ID1，C1，S1)，…，(IDn，Cn，Sn)}。因此隨著簽密用戶的增加，最后的多重簽密密文長(zhǎng)度必然會(huì)越來越大。而本文方案中，每個(gè)簽密用戶把接收到的密文作為加密明文的一部分，利用對(duì)稱加密算法對(duì)其加密，即Ci←EKi(Mi‖IDi-1‖Ci-1‖ai-1‖βi-1)。這樣一方面保護(hù)了簽密密文的安全性，同時(shí)也使得最后輸出的密文僅為(IDn，Cn，an，βn)消息。在接收者解密恢復(fù)該密文時(shí)能得到本次對(duì)應(yīng)消息，也能方便地得到上一個(gè)簽密用戶輸出的密文，這樣極大地縮短了多重簽密密文的長(zhǎng)度，在通信帶寬開銷上花費(fèi)更低。

在方案執(zhí)行過程中由當(dāng)前的簽密用戶指定下一個(gè)簽密用戶，而不需要事先固定一個(gè)簽密順序。在原始消息發(fā)放過程中消息的原始擁有者可以指定最終的多重簽密密文接收者，而不局限于只有消息擁有者才能接收驗(yàn)證多重簽密密文。這兩點(diǎn)使得本方案在實(shí)際的電子政務(wù)和電子商務(wù)中的執(zhí)行具有很大的靈活性。

值得一提的是，在本方案中并不要求用戶的RSA密鑰長(zhǎng)度相同，即方案可以支持用戶的不同模數(shù)長(zhǎng)度計(jì)算。這一特性在具體的方案執(zhí)行過程中具有很高的靈活性。比如在某些情況下，允許發(fā)送者使用1 024—比特RSA密鑰簽名，而在加密業(yè)務(wù)中只允許使用512—比特RSA密鑰。在本方案中加密和簽名是分別進(jìn)行的，即a←RSA(er，nr)(w);β←RSA(ds，ns)-1(s)因此并不需要發(fā)送方和接收方在密鑰長(zhǎng)度上是完全一致的，因此發(fā)送者不需要再生成一個(gè)512—比特臨時(shí)密鑰，而僅僅只需要利用他的1 024—比特密鑰和接受者的512—比特密鑰進(jìn)行簽名和加密即可。

4結(jié)束語

簽密是一種新的認(rèn)證加密技術(shù)，它把原本各自獨(dú)立的加密和簽名進(jìn)行了有效結(jié)合，能在一個(gè)邏輯步驟中為消息提供保密性和數(shù)據(jù)完整性服務(wù)。文中基于RSA提出一種新的多重簽密方案，該方案在安全性和靈活性方面優(yōu)于原有多重簽密方案。該方案中各密碼構(gòu)件可以靈活選取，且基于RSA密碼體制的廣泛使用，在選擇適當(dāng)安全參數(shù)的條件下易于構(gòu)建。因此，本方案對(duì)于解決電子政務(wù)和電子商務(wù)中消息的安全轉(zhuǎn)遞問題具有較好的參考價(jià)值和借鑒意義。

參考文獻(xiàn)：

[1]ZHENG Y. Digital signcryption or how to achieve cost (signature encryption)- cost (signature) + cost (Encryption)[C] //Advances in Cryptology—CRYPTO’97. Berlin:Springer－Verlag，1997:165－179.

[2]MITOMI S， MIYAJI A. A general model of multi－signature schemes with message flexibility， order flexibility and order verifiability[C] //Proc of ACISP 2000. Berlin: Springer－Verlag， 2000:328－342.

[3]PANG X， CATANIA B， TAN K.Securing your data in agent－based P2P systems[C] //Proc of the 8th International Conference on Database Systems for Advanced Applications. 2003:26－28.

[4]SEO S H， LEE S H. A secure and flexible multi－signcryption scheme[C] //Proc of ICCSA.Berlin: Springer－Verlag， 2004:689－697.

[5]張鍵紅，王繼林，王育民. 一種多重簽密模型及其應(yīng)用[J]. 西安電子科技大學(xué)學(xué)報(bào):自然科學(xué)版， 2004 ， 31(3):462－464.

[6]AN J， DODIS Y， RABIN T. On the security of joint signature and encryption[C] //Advances in Cryptology EUROCRYPT. Berlin: Springer－Verlag， 2002:83－107.

[7]DODIS Y， FREEDMAN M J， JARECKI S，et al.Optimal signcryption from any trapdoor permutation[EB/DL]. (2001). http://eprint.iacr.ogr/2001/20.

[8]DODIS Y， FREEDMAN M J， JARECKI S. Parallel signcryption with OAEP， PSS－R， and other feistel paddings[EB/DL]. (2003). http://eprint.iacr.org/2003/043.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文