王戌琦　程相國　王越

摘? ?要：在對基于身份廣播加密IBBE研究的基礎(chǔ)上，提出了基于RSA加密技術(shù)的新廣播加密方案，并給出了新方案的形式化定義和安全模型。在標(biāo)準模型下，證明了新方案具有針對靜態(tài)對手的選擇明文攻擊安全性。新方案中用戶的私鑰長度僅為，并且在滿足抗完全同謀攻擊前提下，新方案降低了解密開銷。實驗結(jié)果表明，新方案在解密計算量和存儲量上更具有優(yōu)勢，更適用于廣播集合固定的應(yīng)用。

關(guān)鍵詞：廣播加密;RSA;標(biāo)準模型;抗完全同謀

中圖分類號：TP309? ? ? ? ? 文獻標(biāo)識碼：A

A new broadcast encryption scheme based on RSA

Wang Xuqi， Cheng Xiangguo， Wang Yue

（College of Computer Science and Technology， Qingdao University， ShandongQingdao 266071）

Abstract： A new broadcast encryption scheme based on RSA encryption and the research of identity-based broadcast encryption （IBBE） is proposed， and the formal definition and security model of the new scheme are presented. The new scheme was proven IND-sID-CPA security under the standard model. In this new scheme， users private key length is only ， and this scheme reduces decryption overhead under the premise of satisfying the fully collusion resistant. The experimental results show that the new scheme has advantages in decrypting computation and storage， and is more suitable for the applications only specially selected individuals can broadcast.

Key words： broadcast encryption; RSA; standard model; fully collusion resistant

Abstract： A new broadcast encryption scheme based on RSA encryption and the research of identity-based broadcast encryption （IBBE） is proposed， and the formal definition and security model of the new scheme are presented. The new scheme was proven IND-sID-CPA security under the standard model. In this new scheme， users private key length is only ， and this scheme reduces decryption overhead under the premise of satisfying the fully collusion resistant. The experimental results show that the new scheme has advantages in decrypting computation and storage， and is more suitable for the applications only specially selected individuals can broadcast.

Key words： broadcast encryption; RSA; standard model; fully collusion resistant

1 引言

廣播加密（Broadcast Encryption，BE）[1，2]是一種在不安全信道上給一組用戶傳輸加密信息的密碼體制，廣播者可以動態(tài)地調(diào)整授權(quán)用戶集合，只有授權(quán)用戶才可以解密密文。

廣播加密典型的應(yīng)用是付費電視，數(shù)字版權(quán)保護等。付費電視等應(yīng)用由一個廣播者和一組接收廣播的用戶組成，廣播者使用密鑰對明文進行加密然后廣播給全體用戶，只有授權(quán)用戶才可以使用自己的私鑰解密廣播密文得到明文，而撤銷授權(quán)用戶無法使用自己的私鑰解密廣播密文獲得明文。在現(xiàn)有的方案中[3-16]，構(gòu)造的廣播加密系統(tǒng)對廣播接收者的存儲和計算能力要求較高，每一套廣播系統(tǒng)中的用戶都需要存儲一個較大的公鑰、系統(tǒng)參數(shù)和自己獨立私鑰。其中，具有代表性的三個方案：BGW[3]方案中公鑰長度隨著系統(tǒng)中用戶總量呈線性變化，用戶實際的密鑰存儲量為;C Delerablée[4]方案較BGW方案對公鑰長度有一定優(yōu)化，該方案的公鑰長度與授權(quán)用戶數(shù)量相關(guān)，為，但是如果在一個大授權(quán)者集合中，C Delerablée方案公鑰實際長度可以認為是，用戶的密鑰存儲量也為;Liu[5]基于多項式插值和雙線性技術(shù)的廣播加密方案，雖然將公鑰大小減少為，但是用戶的私鑰大小卻增加到了，用戶密鑰存儲量為。

在上述方案中，用戶解密需要用到公鑰（或者部分公鑰[12]），所以用戶需要預(yù)先存儲廣播系統(tǒng)的公鑰，這無疑增加了用戶的存儲開銷。為了減小在特定應(yīng)用環(huán)境（如衛(wèi)星電視、云訪問等廣播集合固定的應(yīng)用）下用戶存儲開銷和提高解密速度，方案規(guī)定廣播者和接收者分屬于兩個不同的固定集合，廣播接收者只接收信息而不廣播信息。在這種前提下，方案的解密只需要用到自己的私鑰，而無需公鑰和用戶身份集合的參與，最大程度地減少廣播接收者存儲和計算開銷。在對現(xiàn)有廣播加密方案研究的基礎(chǔ)上，本文基于RSA加密方案提出了新的廣播加密方案。方案滿足抗完全同謀性質(zhì)，公鑰大小為，私鑰的大小、廣播的通信量以及廣播接收者密鑰存儲量都為，而廣播者密鑰存儲量為。本文進一步證明了該方案在標(biāo)準模型下，具有針對靜態(tài)對手的不可區(qū)分密文的選擇明文攻擊安全性（IND-sID-CPA）[17]。

2? 預(yù)備知識

2.1 RSA加密方案

RSA加密算法是一種公鑰加密算法，對大整數(shù)分解的困難性決定了RSA算法的安全性。

RSA加密方案包括幾個算法。

（1） 密鑰生成：選擇兩個滿足需要的大素數(shù)和，計算和的歐拉函數(shù)。

（2） 選擇一個整數(shù)，滿足，計算使得。

設(shè)置公鑰為和私鑰。

（3） 加密：給定消息，，計算。

（4） 解密：計算。

2.2 基于RSA廣播加密方案的一般模型

基于RSA廣播方案加密方案要求系統(tǒng)在建立時，就要確定廣播者和接收者的集合以生成并分發(fā)密鑰，它由四個算法組成。

：輸入安全參數(shù) ，PKG輸出廣播者集合的密鑰以及主密鑰。

：系統(tǒng)根據(jù)中每一個用戶標(biāo)識以及主密鑰計算出每個用戶獨立的私鑰。

：給定授權(quán)用戶集合和撤銷授權(quán)用戶集合，廣播者隨機選取對稱密鑰，加密明文生成密文，并采取密鑰封裝機制（Key Encapsulation Mechanism，KEM）將封裝成廣播的密文頭，廣播。

：用戶使用自己的私鑰以及進行解密，只有授權(quán)集合中的用戶可以順利解密，得到對稱密鑰，進而對密文進行解密。而撤銷授權(quán)用戶盡管擁有私鑰但無法計算出對稱密鑰，因此也無法解密。

2.3 安全模型

本文在IBBE（Identity-Based Broadcast Encryption）安全模型基礎(chǔ)上定義本方案的對靜態(tài)對手的不可區(qū)分密文的選擇明文攻擊安全性（IND-sID-CPA）。靜態(tài)對手會首先確定一個要攻擊的用戶身份集合，然后進行一系列對不在集合中用戶的私鑰提取查詢以及針對某用戶的解密查詢。挑戰(zhàn)者隨機選擇一個對稱密鑰，其中，并用公鑰對進行加密得到密文頭，之后隨機選擇一個對稱密鑰，挑戰(zhàn)者將發(fā)送給對手，此時對手可以進行推測或者再次執(zhí)行查詢后做出推測，得出的值進而完成一次攻擊。下面通過攻擊者和挑戰(zhàn)者游戲來定義安全性。

：攻擊者首先輸出一組想要攻擊的用戶集合。

：挑戰(zhàn)者運行算法生成廣播者密鑰和主密鑰。將中虛擬用戶（Virtual User）標(biāo)識發(fā)送給挑戰(zhàn)者并保密，其余參數(shù)公開。

：攻擊者自適應(yīng)地發(fā)出一組查詢。對每次查詢，選擇用戶，其中為全體用戶集合，將用戶的私鑰發(fā)送給。

：詢問結(jié)束，生成挑戰(zhàn)撤銷用戶集合，包含中所有的被進行私鑰提取查詢的用戶以及系統(tǒng)建立時設(shè)置的虛擬用戶。輸入公共參數(shù)以及，運行加密算法生成，隨機選擇，然后令，選擇一個隨機的會話密鑰，令。然后發(fā)送給。

：攻擊者再次發(fā)起類似于的查詢，提取用戶私鑰。

：輸出猜測，如果，那么稱在這場游戲中獲勝。

攻擊者贏得游戲的優(yōu)勢為。

定義：如果對于所有時間內(nèi)的算法，總共做出次私鑰提取查詢，贏得上述游戲的優(yōu)勢至多為，則廣播加密系統(tǒng)是-IND-sID-CPA安全的。

在方案的安全模型下，挑戰(zhàn)者的身份是固定的，只有廣播者才可以迎接挑戰(zhàn)，用戶標(biāo)識信息是廣播者才能持有的。

3 基于RSA的廣播加密方案

3.1 具體方案

方案提出了新的基于RSA廣播方案加密方案并對其安全性和效率進行分析。

：是安全參數(shù)，是用戶上限，PKG選擇兩個大素數(shù)和，計算以及，選一個與互素的值，求的逆元，即。和是廣播系統(tǒng)加密的和。同樣的方法選取和，使得且，，注意。任取，設(shè)置由廣播者保存且對用戶保密。主密鑰。

：為每一個用戶任意選取且。生成用戶私鑰。 其中，，。

：給定授權(quán)用戶集合，用戶標(biāo)識以及系統(tǒng)公鑰，隨機選取秘密值。對稱密鑰。令，對進行加密得到，。計算得到，其中，，。

為了計算方便，PKG在發(fā)送給廣播者時，同時將和的值也一并給廣播者，當(dāng)時，為了減少計算量，廣播者則只需要計算和 即可分別得到和。

：用戶使用自己的私鑰和計算，計算過程如下：

為了實現(xiàn)抗完全同謀，假設(shè)方案用戶上限數(shù)量為，但是其中實際的用戶數(shù)量為，且，其中為虛擬用戶的數(shù)量。系統(tǒng)建立時，需要PKG為虛擬用戶生成標(biāo)識，需要注意的是，虛擬用戶標(biāo)識和實際用戶的標(biāo)識生成方式和存儲位置是完全一樣的，唯一不同的是虛擬用戶標(biāo)識只在加密的時候由廣播者使用，不產(chǎn)生私鑰分發(fā)給實際用戶。虛擬用戶根據(jù)需要動態(tài)地在授權(quán)用戶集合和撤銷授權(quán)集合調(diào)整，為了保證廣播系統(tǒng)安全，避免惡意用戶推測授權(quán)用戶集合，要求虛擬用戶的數(shù)量。

3.2 安全性分析

方案要保證三個安全原則。

（1） 授權(quán)與加密分離，用戶標(biāo)識決定用戶的解密權(quán)限，在廣播系統(tǒng)安全的情況下，用戶的標(biāo)識信息是不會泄露的，系統(tǒng)中的廣播者也應(yīng)該擔(dān)任維護用戶標(biāo)識安全的角色，而且用戶標(biāo)識信息對破解私鑰沒有幫助。

（2） 有限權(quán)限原則，即廣播者無法利用已有的信息偽造生成新的用戶密鑰，也無法恢復(fù)出RSA算法對于對稱密鑰加密的私鑰，即PKG一次性生成。

（3）抗完全同謀，所有的被撤銷授權(quán)用戶聯(lián)合起來也無法恢復(fù)系統(tǒng)密鑰以及獲取廣播明文信息，也不會獲取到自己或其他用戶標(biāo)識信息。

方案對于廣播密文加解密的是通過RSA算法進行的，所以安全性基于大整數(shù)分解難題。

本文根據(jù)[14]和[15]的證明過程給出方案的安全性證明。

定理：若沒有敵手以不可忽略的優(yōu)勢解決大數(shù)分解難題，那么方案是IND-sID-CPA安全的。

證明：假設(shè)存在攻擊者，能以不可忽略的優(yōu)勢攻破所構(gòu)造的廣播加密方案的密鑰封裝機制，那么可以構(gòu)造一個算法，能以不可忽略的優(yōu)勢解決大數(shù)分解難題。

下面模擬一個真實的攻擊過程。

：攻擊者首先輸出一組想要攻擊的用戶集合。

：算法運行算法生成廣播者密鑰和主密鑰。中虛擬用戶標(biāo)識保密，其余參數(shù)公開。

：攻擊者發(fā)出一組私鑰查詢。對每次查詢，選擇用戶，其中為全體用戶集合，算法將計算用戶的私鑰發(fā)送給，其中，，。此時若發(fā)起詢問的用戶為虛擬用戶時，算法生成三個不同的隨機數(shù)（），并保存為該用戶的私鑰，將結(jié)果返回給攻擊者。

：詢問結(jié)束，生成挑戰(zhàn)撤銷用戶集合，包含中所有的被進行私鑰提取查詢的用戶以及部分系統(tǒng)建立時設(shè)置的虛擬用戶。輸入公共參數(shù)和，運行加密算法，隨機選取秘密值。對稱密鑰。令，對對稱密鑰進行加密得到，。計算得到，其中，，。

生成，隨機選擇，然后令，選擇一個隨機的會話密鑰，令。然后發(fā)送給。

：攻擊者再次發(fā)起類似于的查詢，提取用戶私鑰。

：輸出猜測，如果，那么稱在這場游戲中獲勝。

當(dāng)攻擊者在獲得所有已知信息進行解密時，需要計算。其中，攻擊者無法從已經(jīng)獲取的用戶私鑰中得到用戶標(biāo)識，參數(shù)和私鑰，并且由于虛擬用戶的存在，攻擊者無法根據(jù)有效的用戶私鑰計算得到，所以是對的有效加密。

若攻擊者在進行次私鑰詢問后，攻擊本方案成功的優(yōu)勢至少為，那么需要算法在至少的優(yōu)勢下解決大數(shù)分解難題。若攻擊者在至少優(yōu)勢下猜測正確，那么算法解決大數(shù)分解難題的概率為：

若攻擊者在沒有優(yōu)勢下猜測正確，那么算法解決大數(shù)分解難題的概率為：

算法解決大數(shù)分解難題的優(yōu)勢為。若有攻擊者有不可忽略的優(yōu)勢攻破方案的密鑰封裝機制，那么算法就有不可忽略的優(yōu)勢解決大數(shù)分解難題。由于多項式時間敵手解決大數(shù)分解問題是困難的，所以沒有多項式時間敵手能以不可忽略的優(yōu)勢解決大數(shù)分解難題，故定理1得證。

4? 實驗與性能分析

本節(jié)從存儲開銷和計算開銷兩個方面對方案進行性能分析。

在存儲開銷方面，方案用戶私鑰大小和密文頭是固定長度的，而且廣播接收者不需要存儲公鑰，這樣使得廣播接收者存儲和管理密鑰的成本減少。本文將BGW中構(gòu)造的兩個方案分別簡稱為 BGW-1和BGW-2，并用n表示廣播加密系統(tǒng)中所有用戶的數(shù)目，即所有可以接收廣播密文的用戶數(shù)目。用m表示廣播加密系統(tǒng)中授權(quán)用戶數(shù)目的最大值，用r表示撤銷授權(quán)用戶總數(shù)，方案跟上述雙線性對的方案在公鑰大小、私鑰大小、密文頭長度以及密鑰存貯量方面的對比如表1所示。

在計算開銷方面，由于本文只考慮用戶的加密解密速度，系統(tǒng)建立時，PKG只需要一次性生成所有的密鑰和用戶標(biāo)識即可離線。廣播加密方案計算耗時與授權(quán)用戶數(shù)量線性相關(guān)，當(dāng)授權(quán)用戶數(shù)量增長時，加密過程的耗時也隨之增加。為了提高計算效率，本文在原有加密過程的基礎(chǔ)上，優(yōu)化了加密的算法，廣播者預(yù)先計算并存儲和的值，廣播時則只需要計算和，即可分別得到和。尤其是當(dāng)授權(quán)用戶數(shù)量遠大于撤銷授權(quán)用戶數(shù)量，即，優(yōu)化算法將會有很好的計算效率，但是不能忽視的是，廣播者需要存儲額外的參數(shù)和，這樣會增加額外的存儲需求。

此外，方案解密難度與用戶數(shù)量無關(guān)，與上述雙線性映射構(gòu)造的方案相比，本方案解密時無需進行配對計算，只需要常數(shù)次指數(shù)運算即可完成解密，解密效率上有較大優(yōu)勢。

為了證實上述方案計算效率分析，本文對該方案的加解密效率進行了實驗仿真。仿真環(huán)境：Intel Core i3 3.30GHz處理器，4G內(nèi)存;操作系統(tǒng)：Ubuntu 18.04.1 LTS;代碼庫：The GNU Multiple Precision Arithmetic Library（GMP）;使用的安全參數(shù)取1024 bit。

方案的加密解密效率仿真結(jié)果如圖 1和圖 2所示，測試數(shù)據(jù)見表2。測試的內(nèi)容有兩方面。

（1） 對于不同大小的用戶集合，本文方案的加密解密開銷。

（2） 在相同用戶數(shù)量情況下，加密的優(yōu)化算法和加密的初始算法的效率對比。

用戶全集大小選取為100、500、1000、2500、5000、10000，默認（實驗中?。?。

顯然，在存儲空間充足的情況下，優(yōu)化后的加密方案的計算效率與初始的加密方案相比有了很大提高。廣播系統(tǒng)內(nèi)的授權(quán)用戶和撤銷授權(quán)用戶數(shù)量差距越大，方案優(yōu)化對計算效率上的提升便會越明顯。

如圖2所示，當(dāng)模數(shù)以及用戶標(biāo)識大小確定后，解密的計算開銷也隨之確定，用戶的解密開銷與用戶數(shù)量無關(guān)。BGW-2方案和[11]方案的加密和解密的計算開銷與授權(quán)用戶的數(shù)量線性相關(guān)，即隨著授權(quán)用戶數(shù)量的增加，加解密計算難度也隨之增加。方案廣播者加密的計算開銷與上述兩個方案相似，計算效率上與前者相比略有不足，但是廣播接收者的解密開銷要優(yōu)于上述兩個方案，特別是在一個大的（>104）授權(quán)用戶集合廣播加密系統(tǒng)中，方案在解密效率上的優(yōu)點尤為突出，而且廣播接收者只需要使用自己的私鑰即可完成解密，不需要公鑰參與解密計算，所以方案對廣播接收者的計算能力和存儲能力要求比上述兩個方案都要低。

5 結(jié)束語

本文提出了一個新的基于RSA的廣播加密方案。與已提出的方案相比，方案明顯地降低了解密開銷以及密鑰存儲耗費，減少了對廣播接收者計算和存儲能力的要求。在方案中，廣播者可以在用戶無需改變私鑰的情況下動態(tài)調(diào)整授權(quán)用戶集合，廣播接收用戶只需要進行固定次數(shù)的運算即可解密，解密計算量與用戶數(shù)量無關(guān)。由于廣播集合固定，所以方案適用于付費電視、數(shù)字版權(quán)保護以及云存儲的訪問控制等廣播者較為固定的應(yīng)用。由于加密效率隨廣播系統(tǒng)中用戶數(shù)量增加而呈線性增長，所以減少加密時的計算量是進一步要研究的內(nèi)容。