一种新的基于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的广播加密方案。与已提出的方案相比，方案明显地降低了解密开销以及密钥存储耗费，减少了对广播接收者计算和存储能力的要求。在方案中，广播者可以在用户无需改变私钥的情況下动态调整授权用户集合，广播接收用户只需要进行固定次数的运算即可解密，解密计算量与用户数量无关。由于广播集合固定，所以方案适用于付费电视、数字版权保护以及云存储的访问控制等广播者较为固定的应用。由于加密效率随广播系统中用户数量增加而呈线性增长，所以减少加密时的计算量是进一步要研究的内容。