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

王戌琦　程相國　王越

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

關鍵詞：廣播加密;RSA;標準模型;抗完全同謀

中圖分類號：TP309? ? ? ? ? 文獻標識碼：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]是一種在不安全信道上給一組用戶傳輸加密信息的密碼體制，廣播者可以動態地調整授權用戶集合，只有授權用戶才可以解密密文。

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

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

2? 預備知識

2.1 RSA加密方案

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

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

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

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

設置公鑰為和私鑰。

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

（4） 解密：計算。

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

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

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

：系統根據中每一個用戶標識以及主密鑰計算出每個用戶獨立的私鑰。

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

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

2.3 安全模型

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

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

：挑戰者運行算法生成廣播者密鑰和主密鑰。將中虛擬用戶（Virtual User）標識發送給挑戰者并保密，其余參數公開。

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

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

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

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

攻擊者贏得游戲的優勢為。

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

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

3 基于RSA的廣播加密方案

3.1 具體方案

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

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

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

：給定授權用戶集合，用戶標識以及系統公鑰，隨機選取秘密值。對稱密鑰。令，對進行加密得到，。計算得到，其中，，。

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

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

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

3.2 安全性分析

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

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

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

（3）抗完全同謀，所有的被撤銷授權用戶聯合起來也無法恢復系統密鑰以及獲取廣播明文信息，也不會獲取到自己或其他用戶標識信息。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4? 實驗與性能分析

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

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

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

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

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

方案的加密解密效率仿真結果如圖 1和圖 2所示，測試數據見表2。測試的內容有兩方面。

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

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

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

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

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

5 結束語

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