标准模型下基于认证的混合加密算法.doc

第6期康立等：标准模型下基于认证的混合加密算法19标准模型下基于认证的混合加密算法康立，唐小虎，范佳（西南交通大学 信息安全与国家网格计算实验室，四川 成都 610031)摘 要：为了构建一个较公钥基础设施(PKI)要求更为简单的公钥密码系统，Gentry提出了基于认证的公钥加密方案。在基于认证的公钥加密方案中，第三方对认证申请者的公钥或身份进行签名，并将该签名作为认证发送给申请者，申请者保留认证作为解密时的部分私钥。接收方对密文解密需要同时拥有第三方对其公钥的认证和接收方公钥对应的私钥，因而基于认证的加密方案同时具备基于身份加密方案中公钥的可认证性和传统公钥加密方案中私钥的免撤销性。基于Gentry身份加密算法提出一种高效、短公钥的基于认证的混合加密算法，新算法能在标准(非随机预言机)模型下被证明抗适应性选择密文攻击。关键词：基于认证的加密; 基于身份的加密；标准模型中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2009)06-0013-06Certificate-based hybrid encryption scheme in the standard modelKANG Li, TANG Xiao-hu, FAN Jia(Information Security and National Grid Computing Laboratory, Southwest Jiaotong University, Chengdu 610031, China)Abstract: For construction a public cryptosystem that requiring fewer infrastructures than public key infrastructure (PKI), a certificate-based public-key encryption (CBE) scheme was proposed by Gentry. In CBE scheme, a certification was signed by a third part on an applicants public key or identity and sent to the applicant, the applicant saved it and used it as partial private key (decryption key). A receiver wanted to decrypt a ciphertext, the certification was needed from the third party and his own public-private keys, so CBE combined the best aspects of identity-based encryption (implicit certification) and public key encryption (no escrow). A new efficient certificate-based hybrid encryption scheme with short public key was proposed, which based on Gentrys identity-based encryption scheme, the new scheme can be proved resistance adaptive chosen ciphertext attack in the standard model(without random oracle).Key words: certificate-based encryption; identity-based encryption; standard model1 引言收稿日期：2007-06-19；修回日期：2009-03-04基金项目：西南交通大学博士创新基金资助项目Foundation Item: Creative Foundation for the PH. D Student of Southwest Jiaotong University在传统的基于公钥基础设施(PKI)的加密方案中，认证中心对用户公钥的认证是体系的核心，它将用户和其公钥绑定起来，它包括公钥证书的发放、维护、撤销和更新。信息发送者要加密消息首先得查看并验证接收方的公钥证书。基于身份密码系统的概念在1984年由Shamir提出1，在基于身份的密码系统中，信息发送者不利用户公钥证书队列获得公钥，只需使用接收方身份信息来代替公钥。而接收方要解密密文，必需向可信第三方证明身份获得身份对应的私钥。向第三方证明身份的过程可以视为是对其身份(公钥)的认证。2001年Boneh和Franklin给出了第一个安全且高效的基于身份的加密方案2，该方案的安全性在非标准模型(基于随机预言机)下得到了证明。2003年，Gentry提出了基于认证加密的概念3。Gentry提出将用户身份或公钥的认证作为一部分私钥，用户自选公私钥对的私钥作为另一部分私钥。对比基于身份加密和传统公钥加密，基于认证的加密方案具有以下特点。1) 基于认证加密中用户无需私钥撤销，因为这里的公钥认证只是部分私钥，另一部分私钥是由用户自己生成。由于认证只是部分私钥，因此传输时用户和第三方之间甚至不需要安全信道，这样大大降低了对系统的要求；2) 基于认证的加密对用户认证的撤销变的简单，只需对认证附加过期时间，如果新周期中用户需要证书，他必须再次向第三方申请认证；3) 第三方的权力被大大削减，因为它只能掌握部分私钥，不能再像基于身份密码系统中那样可以任意解密用户密文。Gentry利用Boneh和Franklin基于身份的加密方案2在随机预言机模型下实现了基于认证的加密。但随机预言机模型要求对任意输入，预言机的输出是随机独立均匀分布，这一要求在真实环境中较难实现。因而在随机预言机模型下证明安全的方案在实际应用时并不安全。2005年，Waters提出了一种基于身份的加密方案4，该方案的安全证明不需要随机预言机。2006年，Morillo和Rafols利用Waters基于身份的加密方案构造了在非随机预言机模型下证明安全的基于认证的加密算法(MR算法)5。2006年，Gentry在非随机预言机模型下提出了新的基于身份的加密方案6。本文利用Gentry基于身份的加密方案6给出一种新的基于认证的混合加密算法，新算法能在非随机预言机模型下规约为判定性缩减(truncated) q-ABDHE问题，新算法与MR算法相比更为紧凑、高效、公钥数量更少。新算法为密钥封装算法、对称加密算法的混合加密算法。混合加密算法对被加密消息没有长度限制，更适合于对长消息的加密，而直接加密算法中则要求被加密消息满足一定长度限制。 2 基于认证的加密方案模型及其安全要求2.1 基于认证的加密方案模型基于认证的加密算法由下述5个算法组成。系统建立Setup：由第三方生成系统参数，公布系统公钥MPK，保留系统私钥MSK。生成公私钥SetKeyPair：用户利用系统公钥生成自己的公私钥对。认证Certify：用户向第三方申请认证，用户提交，ID中包含用户身份信息、公钥的有效期等，第三方利用用户身份ID，PK，MPK，MSK和约定的认证有效期生成用户公钥认证Cert并发送给用户。加密Enc：信息发送者利用接收方的身份ID，公钥PK和第三方公钥MPK，加密消息M返回密文C。解密Dec：密文C的接收方利用身份信息ID，公私钥对，第三方公钥MPK和认证信息Cert，应用解密算法来恢复明文M。2.2 安全模型由Gentry3中基于认证的公钥加密方案安全模型给出下述2个攻击者与挑战者的Game：基于认证的公钥加密算法可抵抗如下2类攻击。Game 1：未认证用户攻击。系统建立：挑战者运行加密系统建立算法Setup，获得系统公钥MPK和系统私钥MSK，将MPK发送给攻击者。询问阶段1：攻击者能够适应性的进行如下2类询问：1) 认证询问：攻击者给出任意要求挑战者给出对应的认证；2) 解密询问：攻击者给出任意，要求挑战者返回相应的明文M。挑战阶段：攻击者给出。挑战者随机选择bit返回C*=Enc。 询问阶段2：除了认证询问和解密询问外，攻击者能够像询问阶段1一样适应性的进行询问。猜测：攻击者返回对bit的猜测值。攻击者在=时赢得Game1，定义攻击者A1的优势为Adv A1=|Pr= -1/2|。Game 2：第三方(认证者)攻击。系统建立：挑战者运行加密系统建立算法Setup (生成的参数与Game1中独立)，获得系统公钥MPK和系统私钥MSK，挑战者生成随机的挑战公私钥对，将发送给攻击者。询问阶段1：攻击者能够适应性的进行解密询问：攻击者给出任意，要求挑战者返回相应的明文M。挑战阶段：攻击者给出。挑战者随机选择bit返回C*=Enc。询问阶段2：除了解密询问外，攻击者能够像询问阶段1一样适应性的进行询问。猜测：攻击者返回对bit的猜测值。攻击者在=时赢得Game2，定义攻击者A2的优势为Adv A2=|Pr= -1/2|。定义1 如果攻击者A1和A2在上述Game1或Game2中不能取得多项式时间下不可忽略的优势，那么基于认证的加密算法是适应性选择密文攻击安全的(IND-CBE-CCA)。2.3 Pairing运算G，G1为阶为素数p的群，双线性Pairing映射满足：1) 双线性：；2) 不退化性：对群G的任意生成元g，有；3) 可计算性：存在高效的算法对任意ga，gbG计算。2.4 困难问题在文献6中给出了计算扩展(augmented)双线性Diffle-Hellman指数(q-ABDHE)难题。输入如下2q+2个元素：输出。Gentry在文献6中证明基于身份的加密方案时用到了判断性缩减(truncated) q-ABDHE难题：阶为素数p的群G，；a在Zp中均匀随机选择，T在G1中随机选择，挑战者随机选择bit，如果=1挑战者给出，如果=0挑战者给出。攻击者来猜测，攻击者在=时赢得Game，定义攻击者A的优势为：Adv A=|Pr= -1/2|。定义2 如果没有攻击者在多项式时间内能以不可忽略的优势攻破群中判断性缩减(truncated) q-ABDHE难题，则判断性缩减(truncated) q-ABDHE在群G中成立。2.5 算法定义对称加密算法：加密算法E和解密算法D满足，对任意密钥k和消息M，M=Dk(Ek(M)。假设对随机选择的k、M0和M1, Ek(M0)和Ek(M1) 对攻击者是不可区分的。消息认证码MAC：输入消息C和密钥k，输出t=MACk(C)。假设攻击者给出C*，挑战者给出(每一个C*每次对应随机的k*)，攻击者不能给出且满足CC*。密钥分割算法KDF：对任意密钥k，KDF(k)=(k1，k2)，k1用于对称加密算法，k2用于消息认证码。3 基于认证的混合加密算法系统建立Setup：设G和G1是阶为素数p的群，g为G上的生成元，双线性Pairing映射是可以高效计算的。抗碰撞的Hash函数H1：。 在中随机选择a，在G中随机选择h。计算：。系统主私钥MSK为(a)；主公钥MPK为(g，g1，h，H1)。生成公私钥对SetKeyPair：用户在中随机选择并利用系统公钥生成自己的公私钥对。认证Certify：用户给出，认证者计算v=H1 (ID，PK)，如果v=a，终止认证；否则认证者在中随机选择r(要求对同样的v，r相同)，给出用户的认证信息CertID，PK=(Cert1，Cert2)：加密Enc：信息发送者计算v=H1(ID，PK)，在Zp中随机选择s，利用认证者的MPK计算： ； ； ； ； ； 。将发送给接收者，加密时要求gv不等于，如果相等终止加密。解密Dec：密文接收者利用私钥、认证信息CertID，PK，计算v=H1 (ID，PK)对密文进行解密： ； 。验证，如果成立接受此消息，否则拒绝。4 效率及安全性分析4.1 安全性证明这里给出新算法抵抗适应性选择密文攻击的启发式证明。定理1 假设判断性缩减(truncated) q-ABDHE难题在群G中成立，且在2.5算法定义中给出的对称加密解算法、消息认证码MAC算法是安全的，那么上述基于认证的公钥加密算法是适应性选择密文攻击安全的。将在Game1和Game2模型下分别证明上述定理成立。证明1 如果有攻击者A1能在Game1中攻破上述基于认证的公钥加密算法，那么存在攻击者B1能攻破判断性缩减(truncated) q-ABDHE难题。给定阶为素数p的群G，；a在Zp中均匀随机选择，T在G1中随机均匀选择，挑战者随机选择bit，如果=1挑战者给出，如果=0挑战者给出。攻击者猜测，攻击者在=时赢得Game。 B1将利用A1来猜测，B1作为挑战者给A1提供Game1的仿真环境，具体执行如下。系统建立：B1随机选择度为q的多项式，q为认证提问次数和解密询问次数的和。按照Gentry论文6中方法可由(，)计算出。随机选择抗碰撞的散列函数H1：。系统主私钥MSK为(a) (未知)；主公钥MPK为(g，g1，h，H1)。可以看出，在分布上仿真参数设置与真实环境相同。B1将系统公钥发送给攻击者A1。询问阶段1：认证询问：攻击者A1给出任意，B1计算v=H1 (ID，PK)，如果v等于a，B1可以直接求解判断性缩减(truncated) q-ABDHE难题(下述证明中均同样处理)。令表示度为q-1的多项式。B1给出v=H1(ID，PK)的认证：=是关于v=H1(ID，PK) 的有效认证。这里约定，如果攻击者已经询问过某公钥的认证，将不再对进行解密询问。解密询问：攻击者给出任意，B1计算v=H1(ID，PK)，按照认证询问求出并计算出会话私钥：完成解密。挑战阶段：攻击者A1给出。B1计算v*=H1(ID*，PK*)，随机选择bit给出挑战密文。B1首先利用认证询问算法计算出v*的认证：=令，为q+1次的多项式。B1给出挑战密文：；，这里是多项式中的系数；。将发送给接收者。令(未知)。如果，此时有，, 。由于是均匀随机的，所以s是均匀随机的，因此是关于合法密文，如果Z是随机的，那么如Gentry论文6中分析，也是随机独立的。询问阶段2：除了认证询问和解密询问外，攻击者能够像询问阶段1一样适应性的进行询问。猜测：攻击者A1最后返回对的猜测值，如果=，B1返回判断性缩减(truncated) q-ABDHE挑战者=1，反之返回=0。如果攻击者A1能在Game1下攻破上述基于认证的加密算法，那么B1作为挑战者能攻破判断性缩减(truncated) q-ABDHE困难问题，故基于认证的加密算法在Game1下是安全的。我们在上述证明中要求攻击者给出的应是合法的用户公私钥对。证明2 如果有攻击者A2能在Game2中攻破上述基于认证的公钥加密算法，那么存在攻击者B2能攻破判断性缩减(truncated) q-ABDHE困难问题。B2作为挑战者给A2提供Game2的仿真环境并利用A2攻破判断性缩减(truncated) q-ABDHE困难问题，具体执行如下。系统建立：系统建立过程和Game1中相同，其中：系统主私钥MSK为()，主公钥MPK为(g，g1=，h，H1)，注意这里的g1区别于。B2选择挑战的用户公私钥对。可以看出，在分布上仿真参数设置与真实环境相同。B2将系统公钥，系统私钥和挑战用户公钥PK*=发送给攻击者A2。询问阶段1：解密询问：攻击者A2给出任意，B2计算v=H1(ID，PK*)，令表示度为q-1的多项式。B2可以计算出 。由于已知，计算：得到了会话私钥，完成解密。挑战阶段：攻击者A2给出。B2计算v*=H1(ID*，PK*)，随机选择bit给出挑战密文。B2首先利用上述解密询问中的办法求出。虽然不再是关于v*的认证，但由于结构相同，为证明中便于表示这里仍然记为。令，为q+1次的多项式。B2像Game1中挑战阶段一样给出挑战密文：；这里是多项式中的系数，；。挑战密文的正确性分析及或是随机值T时情况的分析同Game1。询问阶段2：除了解密询问外，攻击者能够像询问阶段1一样适应性的进行询问。猜测：攻击者A2最后返回对的猜测值，如果=，B2返回(truncated) q-ABDHE挑战者=1，反之返回=0。如果攻击者A2能在Game2下攻破上述基于认证的加密算法，那么B2作为挑战者能求解判断性缩减(truncated) q-ABDHE难题，故基于认证的加密算法在Game2下是安全的。在非随机预言机模型下新的基于认证的公钥加密算法的安全性被证明在适应性选择密文攻击模型Game1和Game2中规约为判断性缩减(truncated) q-ABDHE问题，因此新算法抗适应性选择密文攻击。4.2 效率分析新算法中，加密和解密一共需要3次pairing运算，其中加密的2次pairing运算可在系统建立阶段预计算，而MR算法5中需要5次。新算法使用了混合加密方法，减少了MR方法中对加密消息长度的限制。就通信量而言，每次加密MR需要(5p+128)bit，p为群G1中的元素个数，128bit为MAC码的输出长度；而新算法只需(3p+128) bit。由于新算法基于Gentry身份加密方案构建，所以在公钥数量上有明显优势。对比2个算法，无论在计算量上，还是通信量上，新算法都有显著的提高。表1算法比较算法第三方公钥(p)用户公钥(p)通信量/bitPairing计算量新CBE算法323p+1281(3)MR CBE算法n+625p+1284(5)说明：用户公钥和第三方公钥数目为素数p阶群中元素个数。Pairing运算是算法中最费时的运算，这里比较2个算法中Pairing运算次数。考虑到加密时Pairing计算可以在系统建立阶段预计算处理，因而不记入总量。括号中是不考虑预计算的情况。5 结束语Gentry提出了基于认证的公钥加密方案，并用Boneh和Franklin的身份加密方案实现了第一个基于认证的公钥加密算法。Morillo和Rafols第一个实现了在非随机预言机模型下证明安全的基于认证的公钥加密算法。MR算法基于Waters身份加密方案。本文在Gentry身份加密算法的基础上给出了一个新的基于认证的加密算法，新算法在非随机预言机模型下被证明能抵抗适应性选择密文攻击。新算法利用了Gentry身份加密的优势，在公钥数量，计算效率和通信量上与MR算法相比有了较大的提高。另外，新算法使用了密钥封装算法加对称加密算法的混合密码算法，这样减少了对被加密消息长度的要求，更适应于实际应用。参考文献：1SHAMIR A. Identity-Based cryptosystems and signature schemesA. Advances in Cryptology-Proceedings of Crypto84C. Springer- Verlag, 1985. 47-53.2BONEH D, FRANKLIN M. Identity-based encryption from the weil pairingA. Proceedings of the 21st Annual International Cryptology Conference on Advances