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

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

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

中圖分類號：TN918.2

文獻標志碼：A

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

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

1相關(guān)工作

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

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

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

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

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

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

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

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

設(shè)RSA(e，n)(x)為RSA加密/簽名驗證算法描述。其中，（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）用戶密鑰建立和管理

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

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

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

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

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

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

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

3．1安全性分析

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

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

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

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

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

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

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

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

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

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

4結(jié)束語

簽密是一種新的認證加密技術(shù)，它把原本各自獨立的加密和簽名進行了有效結(jié)合，能在一個邏輯步驟中為消息提供保密性和數(shù)據(jù)完整性服務(wù)。文中基于RSA提出一種新的多重簽密方案，該方案在安全性和靈活性方面優(yōu)于原有多重簽密方案。該方案中各密碼構(gòu)件可以靈活選取，且基于RSA密碼體制的廣泛使用，在選擇適當(dāng)安全參數(shù)的條件下易于構(gòu)建。因此，本方案對于解決電子政務(wù)和電子商務(wù)中消息的安全轉(zhuǎ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é)報:自然科學(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)容請以PDF格式閱讀原文