一種新的基于RSA廣播加密方案

王戌琦　程相國　王越

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

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

中圖分類號(hào)：TP309? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：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]是一種在不安全信道上給一組用戶傳輸加密信息的密碼體制，廣播者可以動(dòng)態(tài)地調(diào)整授權(quán)用戶集合，只有授權(quán)用戶才可以解密密文。

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

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

2? 預(yù)備知識(shí)

2.1 RSA加密方案

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

RSA加密方案包括幾個(gè)算法。

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

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

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

（3） 加密：給定消息，，計(jì)算。

（4） 解密：計(jì)算。

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

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

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

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

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

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

2.3 安全模型

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

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

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

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

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

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

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

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

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

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

3 基于RSA的廣播加密方案

3.1 具體方案

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

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

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

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

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

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

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

3.2 安全性分析

方案要保證三個(gè)安全原則。

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

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

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

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

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

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

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

下面模擬一個(gè)真實(shí)的攻擊過程。

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

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

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

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

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

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

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

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

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

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

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

4? 實(shí)驗(yàn)與性能分析

本節(jié)從存儲(chǔ)開銷和計(jì)算開銷兩個(gè)方面對(duì)方案進(jìn)行性能分析。

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

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

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

為了證實(shí)上述方案計(jì)算效率分析，本文對(duì)該方案的加解密效率進(jìn)行了實(shí)驗(yàn)仿真。仿真環(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） 對(duì)于不同大小的用戶集合，本文方案的加密解密開銷。

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

用戶全集大小選取為100、500、1000、2500、5000、10000，默認(rèn)（實(shí)驗(yàn)中取）。

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

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

5 結(jié)束語

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