代密码学第十一讲基于身份的密码体制

1基于身份的密码体制《现代密码学》第十一章2精品课程网站测试用户名：student1,…,student9密码1111113作业5月31日之前，作业提交作业提交名单查询6月10日之前，作业补交，之后提交作业不再记录4上节主要内容身份鉴别的定义口令认证协议挑战应答协议对身份识别协议的攻击和对策5本讲主要内容基于身份的密码系统（IBC）的提出基于身份的加密体制（IBE）的定义Boneh-FranklinIBE方案基于身份的签名体制（IBS）的定义ShamirIBS方案基于身份的密钥协商（IBKA）的定义ScottIBS方案IBC的应用公开问题6基于身份的密码体制IBC是一种非对称密码体系，与以往公钥密码系统的不同在于任意的字符串可以作为用户的公钥，例如每个人的身份标识，email地址，电话号码等。不需要CA系统将用户的身份和用户的公钥绑定。7基于IBC的安全电子邮件系统使用公钥加密邮件“[e-mail]”master-keyCA/PKG基于身份的密码体制是否可以像PKI系统，由用户自己生成私钥？8基于身份的密码体制私钥生成（PKG）系统的PKG中心拥有一对主密钥（masterkey），它公布主密钥中的公钥，自己保存私钥；PKG中心输入自己的私钥和用户的公钥，得到用户的公钥，并安全传回给用户；用户输入这个私钥和PKG中心的公钥，检查收到的私钥是否正确。9基于身份的加密体制1984年以色列科学家Shamir提出了基于身份的密码系统的概念（IBC）。2001年，D.Boneh和M.Franklin,R.Sakai,K.Ohgishi和M.Kasahara利用椭圆曲线上的双线性对设计了基于身份的加密算法。2001年C.Cocks利用平方剩余难题设计了基于身份的加密算法。D.Boneh和M.Franklin提出的IBC(BF-IBC)的安全性可以证明并且有较好的效率，所以引起了极大的反响。10基于身份的加密体制初始化输入:安全参数t输出:系统参数params和主密钥master-key提取私钥输入:系统参数params和主密钥master-key用户身份ID∈{0,1}*输出:用户私钥dID11基于身份的加密体制加密输入:系统参数params,明文M∈M，明文接收者公钥（身份）ID∈{0,1}*,输出:密文C解密输入:系统参数params,密文C∈C，接收者私钥dID,输出:明文M12双线性映射e:G1×G1→G2G1和G2是阶为p的循环群双线性映射任给x,y∈G1和任意整数a,b∈Zpe(ax,by)=e(x,y)ab非退化性（Non-Degenerate）存在x,y∈G1使得e(x,y)≠1G2可计算性（Computable）对于任意给定的x,y∈G1，计算e(x,y)是容易的13安全性假设BilinearDiffie-Hellman问题(BDHP)阶为q的循环群G1,G2,群上的双线性映射e给定G1上的一个生成元g和其上的任意三个元素ag,bg,cg∈G1，其中a,b,c∈Zp,计算e(g,g)abc安全性假设:BDHP是困难的14Boneh-FranklinIBEScheme初始化(t)用t生成一个素数q生成阶为q的循环群G1,G2,及一个双线性映射e:G1×G1→G2任意选取一个生成元g∈G1选取一个随机数s∈Zq*令P=sg选取两个密码学hash函数:H1:{0,1}*→G1*和H2:G2→{0,1}n15初始化(t)M={0,1}nC=G1*×{0,1}nparams=q,G1,G2,e,n,g,P,H1,H2master-key=s私钥生成(ID)dID=sH1(ID)Boneh-FranklinIBEScheme16加密(M)选取随机数r∈Zq*R=rg,M⊕H2(e(H1(ID),P)r)解密(C=(U,V))V⊕H2(e(dID,U))正确性证明H2(e(dID,U))=H2(e(sH1(ID),rg))=H2(e(H1(ID),g)sr=H2(e(H1(ID),sg)r)=H2(e(H1(ID),P)r)Boneh-FranklinIBEScheme17Boneh-FranklinIBEScheme效率加密：1scalarmultiplicationinG11map-to-pointhashoperation,1pairingoperation,1groupexponentinG2,1hash(H2)operation,and1XORoperation.效率解密：1pairingoperation,1hashoperation(H2)1XORoperation.安全性假设：BDHP困难:C,P,H(ID),求(g,g)^rst，其中C=rg,P=sg,H(ID)=tg,18基于身份的签名体制初始化（Setup）输入:安全参数t输出:系统参数params和主密钥master-key提取私钥（Extract）输入:系统参数params和主密钥master-key用户身份ID∈{0,1}*输出:用户私钥dID19签名（Sign）输入:系统参数params,消息M∈M，签名者的私钥dID.输出:签名σ∈S验证（Verify）输入:系统参数params,签名σ∈S，签名者公钥（身份）ID∈{0,1}*,消息M∈M.输出:“Accept”或者“Reject”.基于身份的签名体制20Shamir提出了一个采用RSA算法的IBS算法。初始化:1.选取两个大素数p，q，计算它们的乘积n；选取与Φ(n)互素的整数e;选取一个单向函数h.参数:n,e,h；主密钥:n的因子.提取私钥:给定用户的ID,PKG计算用户的私钥g，满足g^e=IDmodn.ShamirIBSScheme21签名:A用私钥g签署消息m:1.选取随机整数r，计算t=r^emodn2.计算s=g*r^h(t,m)modnSignature:σ=s,t∈Zn×Zn.验证:验证者收到签名σ=s’,t’，消息m’和签名者的公钥(身份ID),验证下式是否成立s’^e=ID*t’^h(t’,m’)modn.ShamirIBSScheme22ShamirIBSScheme效率签名和验证分别需要2integerexponentiations,1integermultiplicationand1hashoperation.安全性：分解因子问题困难IntegerFactorizationProblem(IFP).23初始化（Setup）输入:安全参数t输出:系统参数params和主密钥master-key提取私钥（Extract）输入:系统参数params和主密钥master-key用户身份ID∈{0,1}*输出:用户私钥dID密钥协商（KeyAgreement）输入:系统参数params和用户私钥dID输出：会话密钥K基于身份的密钥协商体制24（基于Weil对和Tate对）初始化:PKG选取一个满足p=3mod4且p+1=c*r，其中c,r亦为素数；选取一个将0-1数据映射到椭圆曲线上点的hash函数H:{0,1}∗→G1.；选取一个随机数s∈Fq作为主密钥.params:G1,G2,e,P,q,H；master-key:s提取私钥:设用户A的身份是IDA,PKG计算他的私钥QA=H(IDA).；SA=sQA.ScottIBKeyAgreement25密钥协商:1.A选取一个随机数ar,计算TA=e(sA,QB)^a;把TA发送给B.2.B选取一个随机数br,计算TB=e(sB,QA)^b;把TB发送给A.3.A计算KAB=TB^a，同样地，B计算KBA=TA^b如果A和B正确执行协议，他们将计算出共享的密钥：KAB=KBA=e(QA,QB)^{sab}是否存在中间人攻击ScottIBKeyAgreement26ScottIBKeyAgreementBAe(sB,QA)be(sA,QB)ae(QA,QB)abse(QA,QB)abs27ScottIBKeyAgreementBMAe(sB,QA)be(sA,QB)ae(QA,QB)me(QA,QB)mae(QA,QB)asm28ScottIBKeyAgreementBMAe(sB,QA)be(sA,QB)ae(P,QB)me(g,QB)smae(QA,QB)asmM发送其它值是否可行？29ScottIBKeyAgreementBMA求e(sA,QB)QA,P求e(QA,QB)sQA,QB,PQB,P求e(sB,QA)sAsBK=e(QA,QB)s=e(g,g)sAB30效率（单个用户的计算复杂度）1pairingoperation,1map-to-pointhashfunction(H),1groupadditioninG12groupexponentiationsinG2.安全性：基于BDHP的困难性.ScottIBKeyAgreement31多方密钥协商1轮3方密钥协商:A:发送aQ，计算e(bQ,cQ)^a；B:发送bQ，计算e(aQ,cQ)^b；C:发送cQ，计算e(aQ,bQ)^c；共享密钥：e(Q,Q)^{abc}猜想：若存在n次线性对，则存在1轮n方密钥协商一轮通信的3方密钥协商协议32IBC的应用Boneh和Franklin的团队的努力,IBE被应用于DebianGNU/Linux.ShamusSoftware也开发了包含BF-IBE的密码文库，称为“MIRACL”sourcecodeisavailableat和Shamus图书馆开发使用C/C++.似乎还没有JavaimplementationofIBE33IBC的应用现实应用中，VoltageSecurity开发了包含IBE的email系统，它为Outlook,pine,hotmail,andYahoo提供插件.HewlettPackardLab(布里斯托尔Bristol,UK)的研究员开发健康保健信息系统使用了IBE系统.34IBC的应用IEEEP1363.3的基于标识的密码技术工作组正在进行相关算法的标准化工作。ISO/IEC已经标准化了两个基于身份的签名算法。2007年，国家密码局组织了国家标识密码体系IBC标准规范(Identity-BasedCryptograph)的编写和评审工作。由五位院士和来自党政军、科研院所的密码专家组成了评审组，对该标准规范在安全性、可靠性、实用性和创新性等方面进行了多次严格审查,2007年12月16日国家IBC标准正式通过了评审。35公开问题密钥托管问题.所有IBC密码方案都有“密钥托管”的弱点。在IBE和IBS方案中,用户的私钥是由PKG用他的主密钥来计算发布.因此，PKG拥有用户的私钥，可以解读相关的密文，冒充用户签名。对策：Boneh和Franklin提出利用Shamir提出的秘密共享技术分散单个PKG的权利缺点：增加系统负担是否有更好的方法？36公开问题密钥撤销问题.在基于身份的密码系统中，公钥是用户的身份信息，但是用户的私钥泄露时该公钥/私钥对将不能再使用（或者按策略需要定期更新密钥对），是否更换用户的身份（如电子邮箱等）？对策Boneh和Franklin建议用户在身份信息后缀上密钥的生存期，如[e-mail]||June,2004作为真正的公钥，这样公钥可以定期撤销更换。PKI需要用CRL来公布撤销的公钥，用户在加密或者签名验证时首先要检查用户的公钥是否已经被撤销？37公开问题效率问题：目前的IBE系统有两种实现方式，一种是基于双线性对（Weilpairing和Tatepairi