基于身份和私钥隔离的密码系统.doc

第4期周渊等：基于身份和私钥隔离的密码系统25基于身份和私钥隔离的密码系统周渊1，秦宝山2，曹珍富3（1. 国家计算机网络与应急技术处理协调中心，北京 100029；2. 北京邮电大学，北京 100876；3. 上海交通大学 电子信息与电气工程学院，上海 200030）摘 要：利用私钥隔离的思想来缓解基于身份密码系统中的私钥泄漏问题。首先构建了基于身份和私钥隔离的密码学原语，给出了这个原语的形式化安全模型，然后构造了一个具体的方案，并且证明了该方案的安全性。关键词：基于身份的密码；私钥隔离的密码系统；双线性配对中图分类号：TP301.6 文献标识码：A 文章编号：1000-436X(2009)04-0021-06Identity based and key insulated cryptosystemZHOU Yuan1, QIN Bao-shan 2, CAO Zhen-fu 3(1. National Computer Network Emergency Response Technical Team/Coordination Center of China, Beijing 100029, China;2. Beijing University of Posts and Telecommunications, Beijing 100876, China; 3. School of Electronic and Information Electrical Engineering, Shanghai Jiaotong University, Shanghai 200030, China)Abstract: The method of key insulation to identity-cryptosystems was applied, for solving the key exposure problem existing in the identity-based schemes were applied. After developing the formal secure model for identity-based and key insulated cryptosystems, a concrete scheme proved secure under this model was constructed.Key words: identity-based cryptosystem; key insulated cryptosystem; bilinear pairing1 引言收稿日期：2008-12-12；修回日期：2009-02-12基金项目：国家重点基础研究发展计划（“973”计划）基金资助项目（2007CB311100）；国家高技术研究发展计划(“863”计划)基金资助项目(2007AA01Z446)；国家自然科学基金资助项目（60873217）Foundation Items: The National Basic Research Program of China (973 Program) (2007CB311100); The National High Technology Research and Development Program of China (863 Program) (2007AA01Z446)；The National Natural Science Foundation of China (60873217)在传统公钥密码系统的密钥生成过程中，往往先生成私钥，然后再由私钥生成对应的公钥，因此公钥看似一段随机的乱码。因而如何将公钥与其对应主体的身份进行绑定就成为了一个难题。而这个问题能否有效解决恰恰是公钥密码系统或者数字签名能否被实用化的关键。为了解决这个问题，Kohnfelder在1979年提出了“公钥证书”的概念1。公钥证书通常包含这样一些内容，由公钥持有者的身份信息、公钥参数等组成的消息，以及由可信第三方(称为证书权威，或CA)对该消息的一个数字签名。在此基础上，提出了基于目录的公钥认证框架。目前流行的基于目录的公钥认证框架有X.509证书框架2、PGP“信任网”1和简单公钥基础设施(SPKI)3。然而，建立和维护基于目录的公钥认证框架会使系统异常复杂，且成本异常的高1。由于传统的公钥密码系统受到公钥与其主体的身份绑定问题的挑战，人们一直希望能够找到一种途径来简化这个问题。1984年，Shamir4试图绕开基于目录的公钥认证框架的束缚，提出了基于身份的密码系统的思想。在这种密码系统的密钥产生过程中，公钥直接就是公钥拥有者的身份信息，因此这种公钥密码系统可以很自然地解决公钥与实体身份的绑定问题。基于身份的密码系统之所以可直接将身份信息作为公钥，是因为在其密钥产生过程中，先由实体的身份信息产生公钥，然后再由公钥产生对应的私钥，当然，由公钥产生对应私钥的过程只为私钥生成器(PKG, private key generator)所知，对其他实体是保密的。对于一个公钥密码系统而言，私钥的泄漏意味着系统安全性的完全丧失。在现实世界里，从一个无知的用户偷盗私钥往往比攻破公钥系统所依赖的困难问题更加容易得多。在利用目录来进行公钥认证的公钥系统中，私钥的泄漏问题可以通过公钥证书的撤销功能得以缓解。一旦发现用户的私钥泄漏，那么可以利用目录认证框架中的公钥证书撤销功能对相应的公钥证书实施撤销操作，此后用户可以重新申请一张新的证书。相对于利用目录来进行公钥认证的公钥系统，在基于身份的公钥系统中，私钥的泄漏几乎没有缓解的余地。在基于身份的公钥系统中，公钥就是用户的身份信息（包括标准的大家共同约定的密钥对的使用信息）。一旦私钥泄漏，对应的公钥无法更换，意味着用户将不得不(在一段时间内) 退出该系统。为了解决私钥泄漏而造成系统失效，人们考虑了很多方法。Shamir5提出秘密共享的思想，即将私钥分拆成n个子私钥分别在n台服务器，要求这n个服务器中任意的k台服务器协同工作才能完成解密或签名操作，而任意k1台服务器协同工作的时候相当于对私钥一无所知，并由此开创了门限密码学6。然而，秘密共享的方式代价非常高，只有大公司或者证书权威(CA)中心才有可能使用这种方式，对于只拥有一台计算机或一台手持设备的普通用户来说，秘密共享的方式显然是不现实的。Anderson提出的前向安全的概念7是解决私钥泄漏问题的又一条思路。在具有前向安全性质的公钥密码学原语中，当前私钥的泄漏不会危及到以前时间段系统的安全性。然而，前向安全还不是一个很有效的做法。一旦私钥泄漏，虽然能够保障以前时间段里系统的安全性，但是在以后的时间段里系统的安全性就完全不能保障，因此被泄漏私钥所对应的公钥也就作废了。为了有效地解决私钥泄漏的问题，Dodis等8提出了一个非常有效的办法（直接把私钥与外界不安全环境隔离）。具体的思想如下。针对一对公钥密码学的密钥对(pk, sk)，将私钥sk置于一个物理上相对安全的设备（SD）之中，并不参与实际的解密或签名操作；所有的解密或签名操作都是在相对不太安全的设备（NSD）中进行；将密钥对(pk, sk)的生命周期划分为N个时间段，在每个时间段t，SD利用私钥sk产生临时私钥skt，然后将skt导入到NSD中；NSD可以利用这个临时私钥skt在对应时间段进行解密或者结合时间戳服务器进行数字签名操作；信息加密的第三方不管在什么时候对消息加密，始终都是将公钥pk和当前时间段t结合起来，形成一个临时公钥pkt，然后利用pkt进行加密操作；对数字签名进行验证的第三方将公钥pk和时间戳服务器提供的时间戳所对应的时间段结合起来形成一个临时公钥pkt，然后利用pkt进行签名验证操作。私钥隔离的概念其实质也是一个授权问题，即NSD代理SD来进行加密或解密操作。Dods等还在论文中给出了具有私钥隔离功能的公钥密码原语和数字签名原语的形式化安全模型。本文将基于私钥隔离的思想用于基于身份的密码系统中，可以很好地缓解基于身份密码系统的私钥泄漏问题。建立基于身份和私钥隔离的密码学原语，并在此基础上建立形式化安全模型和设计安全的基于身份和私钥隔离的公钥体制是有意义的工作，这也是本文的主要贡献。2 基于身份和私钥隔离的密码系统密码学原语为了解决公钥密码系统和数字签名系统中私钥泄漏而引发的安全性问题，本文对Dodis等8工作进行扩展，将私钥隔离的概念合理地定义到基于身份的密码系统中，形成一个新的密码学原语基于身份和私钥隔离的公钥密码系统。2.1 基于身份和私钥隔离的密码系统语法定义1 基于身份和密钥隔离的公钥加密系统语法。基于身份的公钥和私钥隔离的密码系统ID-KI-C =(S, EXT , E, D)定义如下。系统建立算法S。以整数（k为系统安全参数）作为输入，产生系统私钥mk，输出全局参数PM。系统私钥mk由私钥生成器保密，全局参数PM公开。私钥提取算法EXT。以全局参数PM、系统私钥和任意字符串ID0, 1作为输入，输出私钥d。其中，ID用作公钥，d是ID对应的私钥。临时私钥导出算法TKD。以全局参数PM、密钥对（ID, d）和时间段作为输入，输出临时私钥。加密算法E。以全局参数PM、身份ID、时间段和消息作为输入，输出一条密文。解密算法D。以全局参数PM、临时私钥、时间段和某一密文作为输入，输出M或“？”。这里，“？”表示密文不是一条合法的密文或不是一条授权解密的密文。这些算法满足如下标准的正确性要求。对于任意由TKD(PM, ID, d, t) 产生的二元组（ID, ）和消息M，存在等式：M = D(PM, ID, ,E(params, ID, t, M)。2.2 基于身份和私钥隔离的密码系统的形式化安全模型在考虑由定义1定义的身份和私钥隔离的密码系统的形式化安全模型之前，首先从非形式化的角度对其安全性进行考察。放在SD中的私钥d只有一个用处，为NSD生成临时私钥。因此，恶意攻击者可能通过破解NSD而得到临时私钥，从而发起针对SD的选择时间段提取私钥的攻击。当然，在基于身份的环境中还会存在私钥提取攻击。如果能够应对这样的攻击，那么系统就达到了语义安全。此外，针对NSD发起适应性选择密文当然是恶意攻击者可以采用的更强的攻击手段。如果系统还可以抵御这种攻击，那么系统就达到了适应性选择密文安全。本文将在下文中首先阐述基于语义的安全模型，然后阐述安全性要求更高的适应性选择密文攻击的安全模型。2.2.1 基于身份和私钥隔离的密码系统的语义安全模型通过一个挑战者C与一个攻击者A之间的游戏来对语义安全作一个精确的表达，将这个游戏记为ID-KI-IND-CPA-GAME。建立挑战者C运行算法S，产生全局参数PM和系统私钥，将PM发给攻击者A。阶段1私钥提取询问（ID）。挑战者C运行算法EXT 产生私钥，并将发送给A。临时私钥提取询问（ID, ）。 挑战者C运行算法EXT 产生私钥d，然后运行算法TKD产生临时私钥，并将发送给A。挑战 一旦攻击者A认为阶段1结束，它输出挑战明文组（ID*,*,），其中和为2个等长的明文消息，且ID*没有在阶段1的私钥提取询问中被询问过，以及在时间段*，（ID *,*）没有在阶段1的临时私钥提取询问中被询问过。挑战者C接收到A的输出后，随机选择一个比特0, 1，计算的挑战密文 = E(PM, (ID*,*,)，然后将发给攻击者A。阶段2攻击者A可以根据自己的需要继续向挑战者C按照阶段1的方式发起私钥查询询问和临时私钥提取询问。只是在进行私钥提取询问时，（ID）（ID*），在进行临时私钥提取询问时，（ID,）（ID*,*）。猜测 一旦攻击者A认为阶段2可以结束，它必须通过输出一个比特 来回答在挑战阶段挑战者C选择的那个比特是0还是1。如果回答正确，也就是 = ，那么攻击者就赢得游戏的胜利。通过上述游戏来定义基于身份和私钥隔离的密码系统的机密性，令攻击者A的优势Adv ()为。定义2 ID-KI-IND-CPA。基于身份和私钥隔离的密码系统方案ID-KI-C是语义安全的，如果对于任何概率多项式攻击者A，Adv()是可以忽略的。2.2.2 基于身份和私钥隔离的密码系统的适应性选择密文安全模型通过一个挑战者C与一个攻击者A之间的游戏来对适应性选择密文安全作一个精确的表达，将这个游戏记为ID-KI-IND-CCA-GAME。建立挑战者C运行算法S，产生全局参数PM和系统私钥，将PM发给攻击者A。阶段1私钥提取询问（ID）。挑战者C运行算法EXT 产生私钥，并将发送给A。临时私钥提取询问（ID, ）。 挑战者C运行算法EXT 产生私钥，然后运行算法TKD产生临时私钥，并将发送给A。解密询问（ID, C, ）。挑战者C运行算法EXT 产生私钥，然后运行算法D，并将解密结果返回给A。挑战 一旦攻击者A认为阶段1结束，它输出挑战明文组（ID*,*,），其中和为2个等长的明文消息，且ID*没有在阶段1的私钥提取询问中被询问过，以及在时间段*，（ID*,*）没有在阶段1的临时私钥提取询问中被询问过。挑战者C接收到攻击者A的输出后，随机选择一个比特0, 1，计算的挑战密文= E(PM, (ID*,*, )，然后将发给攻击者A。阶段2攻击者A可以根据自己的需要继续向挑战者C按照阶段1的方式发起私钥查询询问、临时私钥提取询问和解密询问。只是在进行私钥提取询问时 (ID)(ID*)；在进行临时私钥提取询问时，(ID,)(ID*,*)；在解密询问时，(ID,C,) (ID*,*)。猜测 一旦攻击者A认为阶段2可以结束，它必须通过输出一个比特来回答在挑战阶段挑战者C选择的那个比特是0还是1。如果回答正确，也就是 = ，那么攻击者就赢得游戏的胜利。通过上述游戏来定义基于身份和私钥隔离的密码系统的机密性，令攻击者A的优势 Adv()为。定义3 ID-KI-IND-CCA。基于身份和私钥隔离的密码系统方案ID-KI-C是语义安全的，如果对于任何概率多项式攻击者A，Adv()是可以忽略的。3 计算双线性Diffie-Hellman假设Boneh等形式化了双线性Diffie-Hellman（CBDH）问题9,10，由于这个问题的困难假设是本文所涉及密码系统依赖的数学难题，因此本节对这些事实进行了回顾。3.1 双线性配对令，分别是相同阶q的加法循环群和乘法循环群，其中q是素数。如果映射: 满足下列条件，那么称为双线性映射。1) 双线性：对于所有的P, Q以及a, b，其中表示模q整数集，都有(aP, bQ) =(P,Q)。2) 非退化性：存在着P，Q，使得(P,Q) 1。3) 可计算性：对于任意P，Q，存在着有效的算法来计算(P, Q)。3.2 计算双线性Diffie-Hellman假设定义4 计算双线性Diffie-Hellman(CBDH)、参数生成器所谓CBDH生成器IG就是输入，在的多项式时间输出CBDH参数，也就是输出q阶加法群G1和q阶乘法群（这里，q是k bit的素数）、双线性映射:以及四元组（P, aP, bP, abP），其中P是的生成元，a, b是在中选择的3个随机数。定义5 计算双线性Diffie-Hellman(CBDH)问题：由CBDH参数生成器IG产生的CBDH参数作为输入，计算(P, P)abc。设一个概率多项式算法A能够完成定义5所述CBDH问题的概率是e。下面给出CBDH假设。计算双线性Diffie-Hellman(CBDH)假设：对于CBDH生成器IG，当k足够大时，任意对k多项式不可忽略的概率e 0，不存在由IG生成的CBDH问题的求解方法，那么就说IG是满足CBDH假设。4 基于计算双线性Diffie-Hellman假设的方案4.1 系统建立算法S以（为系统安全参数）为输入，执行以下步骤。1) 运行CBDH参数IG()，产生q阶加法群和q阶乘法群 (这里，q是k bit的素数)，双线性映射:；2) 随机选择的生成元P，随机选择，计算=；3) 定制明文空间为 = ，0，定制密文空间为 = ；4) 选择4个密码学散列函数：: 、:、:和:；5) 将作为系统私钥，输出系统参数PM = (, , P, ,)。4.2 私钥提取算法EXT以（PM, , ID）作为输入，执行以下步骤。1) 计算=(ID) ；2) 利用系统私钥计算与ID对应的私钥= ，并输出。4.3 临时私钥导出算法TKD以（PM, ID, ,t）作为输入，执行以下步骤。1) 计算=(ID)；2) 随机选择d，分别计算=+ 和=，输出临时私钥=(,)。4.4 加密算法E以（PM, ID, t, ）作为输入，执行以下步骤。1) 计算=(ID)；2) 随机选择，计算=，然后计算= ；3) 计算= ；4) 计算=(,)，然后计算= 。5) 输出密文= (,)。4.5 解密算法D以（PM, ID, , , C）作为输入，执行以下步骤。1) 计算=(, )( ,)；2) 计算=；3) 计算=，验证关系式=是否成立，如果不成立，认为密文不合法，输出“?”，否则执行下一步；4) 输出M，这里，M是的前(nl) bit。5 方案安全性分析关于这个方案的安全性，可以用如下定理加以描述。定理1 如果CBDH假设成立，那么此基于身份和私钥隔离的密码体制是满足定义3所阐述的ID-KI-IND-CCA安全的。首先构造一个基于私钥隔离的密码体制(称这个体制为BasicKIC)是适应性选择密文安全的，然后证明如果BasicKIC是适应性选择密文安全的，那么定理1就成立。BasicKIC的描述具体如下。(1) 参数产生算法G以(是系统安全参数)为输入，执行以下步骤。1) 运行CBDH参数IG()，产生q阶加法群G1和q阶乘法群G2(这里，q是k bit的素数)，双线性映射: G1 G1G2；2) 随机选择的2个生成元P和；3) 定制明文空间=，这里，0 。定制密文空间 = ；4) 选择3个密码学散列函数：:、H2:和H3: G2；5) 将作为系统私钥，输出公共系统参数PM = (, , P, Q,)。(2) 密钥产生算法K以PM为输入，执行以下步骤。1) 随机选择s，计算= ，= sQ；2) 公钥pk =，私钥sk =。(3) 临时私钥导出算法TKD以（PM, pk, , ）为输入，执行如下。随机选择d，分别计算=+和=dP，输出临时私钥skt=(,)。(4) 加密算法E以（PM, pk, t, M）为输入，执行以下步骤。1) 随机选择，计算=H2，然后计算C1 = r2P；2) 计算C2 = ；3) 计算g=(,Q)，然后计算C3= ；4) 输出密文C = (t,C1,C2, C3)。(5)解密算法D以（PM, pk, skt, t, C）作为输入，执行以下步骤。1) 计算=( C1, )(, C2)；2) 计算= C3；3) 计算=)，验证关系式=是否成立，如果不成立，认为密文不合法，输出“?”，否则执行下一步；4) 输出M，这里，M是的前(l) bit。由于篇幅限制，本文只给出大致证明思路。容易证明，如果CBDH假设成立，那么BasicKIC是满足定义2阐述的KI-IND-CPA安全的；然后证明对于BasicKIC，能够构造一个()-知识提取器（其中，为12/q1/2n），因而BasicKIC是符合文献12明文感知定义的，从而BasicKIC是满足适应性选择密文安全的；最后证明如果BasicKIC是满足适应性选择密文安全的，那么本章描述的基于身份和私钥隔离的密码系统体制是满足定义3定义的ID-KI-IND-CCA安全的，即定理1得证。6 结束语本文利用私钥隔离的概念构建基于身份和私钥隔离的密码学原语，给出这个原语的形式化安全模型，并在此基础上构造了一个基于身份和私钥隔离的密码系统方案，并且证明了方案的安全性。参考文献：1MAO W. Modern Cryptography: Theory and PracticeM. Prentice Hall PTR, 2003.2ITU-T, Rec X.509 (revised) the Directory - Authentication FrameworkS. Geneva, Swithzerland, 1993.3ELLISON C, FRANTZ B, LAMPSON B, et al. SPKI Certidicate TheoryS. The IETF RFC 2693, 1999.4SHAMIR A. Identity based cryptosystems and signature schemesA. Advances in Cryptology-Crypto84C. Santa Barbara, USA, 1984. 47-53.5SHAMIR A. How to share a secretJ. Comm of the ACM, 1999, 22(11): 612-613.6DESMEDT Y, FRANKEL Y. Thres