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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基于身份的密码体制,现代密码学第十一章,1,基于身份的密码体制现代密码学第十一章1,精品课程网站测试,http:/,用户名：student1,student9,密码111111,2,精品课程网站测试http:/,作业,5月31日之前，作业提交,作业提交名单查询,6月10日之前，作业补交，之后提交作业不再记录,3,作业5月31日之前，作业提交3,上节主要内容,身份鉴别的定义,口令认证协议,挑战应答协议,对身份识别协议的攻击和对策,4,上节主要内容身份鉴别的定义4,本讲主要内容,基于身份的密码系统（IBC）的提出,基于身份的加密体制（,IBE）的定义,Boneh-Franklin IBE方案,基于身份的签名体制（IBS）的定义,Shamir IBS方案,基于身份的密钥协商（IBKA）的定义,Scott IBS方案,IBC的应用,公开问题,5,本讲主要内容基于身份的密码系统（IBC）的提出5,基于身份的密码体制,IBC是一种非对称密码体系，与以往公钥密码系统的不同在于任意的字符串可以作为用户的公钥，例如每个人的身份标识，email地址，电话号码等。,不需要CA系统将用户的身份和用户的公钥绑定。,6,基于身份的密码体制IBC是一种非对称密码体系，与以往公钥密码,基于IBC的安全电子邮件系统,使用公钥加密邮件,“”,我是,“,”,私钥,master-key,CA/PKG,基于身份的密码体制,是否可以像PKI系统，,由用户自己生成私钥？,7,基于IBC的安全电子邮件系统使用公钥加密邮件我是“ali,基于身份的密码体制,私钥生成（PKG）,系统的PKG中心拥有一对主密钥（master key），它公布主密钥中的公钥，自己保存私钥；,PKG中心输入自己的私钥和用户的公钥，得到用户的公钥，并安全传回给用户；,用户输入这个私钥和PKG中心的公钥，检查收到的私钥是否正确。,8,基于身份的密码体制私钥生成（PKG）8,基于身份的加密体制,1984年以色列科学家Shamir提出了基于身份的密码系统的概念（IBC）。,2001年，D.Boneh和M.Franklin,R.Sakai,K.Ohgishi 和 M.Kasahara利用椭圆曲线上的双线性对设计了基于身份的加密算法。,2001年C.Cocks利用,平方剩余难题,设计了基于身份的加密算法。,D.Boneh和M.Franklin提出的IBC(BF-IBC)的安全性可以证明并且有较好的效率，所以引起了极大的反响。,9,基于身份的加密体制1984年以色列科学家Shamir提出了基,基于身份的加密体制,初始化,输入,:安全参数,t,输出,:,系统参数,params,和,主密钥,master-key,提取私钥,输入,:,系统参数,params,和,主密钥,master-key,用户身份,ID,0,1*,输出:用户私钥,d,ID,10,基于身份的加密体制初始化10,基于身份的加密体制,加密,输入,:,系统参数,params,明文,M,M，,明文接收者公钥（身份）,ID,0,1*,输出,:密文,C,解密,输入,:,系统参数,params,密文,C,C，,接收者私钥,d,ID,输出,:明文,M,11,基于身份的加密体制加密11,双线性映射,e:G1 G1 G2,G1 和 G2 是阶为p的循环群,双线性映射,任给,x,y,G1 和任意整数 a,b,Z,p,e(ax,by)=e(x,y),ab,非退化性（,Non-Degenerate）,存在,x,y,G1 使得 e(x,y)1,G2,可计算性（,Computable）,对于任意给定的,x,y,G1，计算 e(x,y)是容易的,12,双线性映射e:G1 G1 G212,安全性假设,Bilinear Diffie-Hellman 问题(BDHP),阶为q的循环群G1,G2,群上的双线性映射e,给定G1上的一个生成元 g 和其上的任意三个元素 ag,bg,cg,G1，其中 a,b,c,Z,p,计算 e(g,g),abc,安全性假设:BDHP 是困难的,13,安全性假设Bilinear Diffie-Hellman 问,Boneh-Franklin IBE Scheme,初始化,(,t,),用,t,生成一个素数,q,生成阶为q的循环群 G1,G2,及一个双线性映射e:G1G1 G2,任意选取一个生成元,g,G1,选取一个随机数,s,Z,q,*,令,P,=,sg,选取两个密码学hash函数,:H,1,:0,1*G1*和 H,2,:G2 0,1,n,14,Boneh-Franklin IBE Scheme初始化(,初始化,(,t,),M,=0,1,n,C,=G1*0,1,n,params,=q,G1,G2,e,n,g,P,H,1,H,2,master-key=s,私钥生成(ID),d,ID,=s,H,1,(,ID,),Boneh-Franklin IBE Scheme,15,初始化(t)Boneh-Franklin IBE Schem,加密,(,M,),选取随机数,r,Z,q,*,R,=,rg,M,H,2,(,e,(H,1,(,ID,),P,),r,),解密,(,C,=(,U,V,),V,H,2,(,e,(,d,ID,U,),),正确性证明,H,2,(,e,(,d,ID,U,),),=H,2,(,e(s,H,1,(,ID,),rg,)=H,2,(,e(,H,1,(,ID,),g,),sr,=H,2,(,e(,H,1,(,ID,),sg,),r,),=,H,2,(,e(,H,1,(,ID,),P,),r,),Boneh-Franklin IBE Scheme,16,加密(M)Boneh-Franklin IBE Schem,Boneh-Franklin IBE Scheme,效率,加密：,1 scalar multiplication in G1,1 map-to-point hash operation,1 pairing operation,1 group exponent in G2,1 hash(H2)operation,and 1 XOR operation.,效率,解密：,1 pairing operation,1 hash operation(H2),1 XOR operation.,安全性假设：BDHP困难:C,P,H(ID),求(g,g)rst，其中C=rg,P=sg,H(ID)=tg,17,Boneh-Franklin IBE Scheme效率效率安,基于身份的签名体制,初始化（Setup）,输入,:安全参数,t,输出,:,系统参数,params,和,主密钥,master-key,提取私钥（Extract）,输入,:,系统参数,params,和,主密钥,master-key,用户身份,ID,0,1*,输出:用户私钥,d,ID,18,基于身份的签名体制初始化（Setup）18,签名（Sign）,输入,:,系统参数,params,消息,M,M，,签名者的私钥,d,ID,.,输出,:签名,S,验证（Verify）,输入,:,系统参数,params,签名,S,，签名者公钥（身份）,ID,0,1*,消息,M,M.,输出,:“Accept”或者“Reject”.,基于身份的签名体制,19,签名（Sign）基于身份的签名体制19,Shamir提出了一个采用RSA算法的IBS算法。,初始化:,1.选取两个大素数p，q，计算它们的乘积n；选取与(n)互素的整数 e;选取一个单向函数h.,参数:n,e,h；主密钥:n 的因子.,提取私钥:,给定用户的 ID,PKG计算用户的私钥 g，满足 ge=ID mod n.,Shamir IBS Scheme,20,Shamir提出了一个采用RSA算法的IBS算法。Shami,签名:,A 用私钥 g 签署消息 m:,1.选取随机整数 r，计算t=re mod n,2.计算s=g*rh(t,m)mod n,Signature:=Zn Zn.,验证:,验证者收到签名 =，消息m和签名者的公钥(身份ID),验证下式是否成立,se=ID*t h(t,m)mod n.,Shamir IBS Scheme,21,签名:Shamir IBS Scheme21,Shamir IBS Scheme,效率,签名和验证分别需要,2 integer exponentiations,1 integer multiplication and,1 hash operation.,安全性：分解因子问题困难Integer Factorization Problem(IFP).,22,Shamir IBS Scheme效率22,初始化（Setup）,输入,:安全参数,t,输出,:,系统参数,params,和,主密钥,master-key,提取私钥（,Extract）,输入,:,系统参数,params,和,主密钥,master-key,用户身份,ID,0,1*,输出:用户私钥,d,ID,密钥协商（Key Agreement）,输入,:,系统参数,params,和,用户私钥,d,ID,输出：会话密钥K,基于身份的密钥协商体制,23,初始化（Setup）基于身份的密钥协商体制23,（基于Weil,对,和Tate 对）,初始化:,PKG 选取一个满足 p=3 mod 4且 p+1=c*r，其中c,r亦为素数；选取一个将0-1数据映射到椭圆曲线上点的hash函数H:0,1 G1.；选取一个随机数 s Fq 作为主密钥.,params:；master-key:s,提取私钥:,设用户 A 的身份是 ID,A,PKG 计算他的私钥,Q,A,=H(ID,A,).；S,A,=sQ,A,.,Scott IB Key Agreement,24,（基于Weil对 和Tate 对）Scott IB Key,密钥协商:,A 选取一个随机数 a r,计算 T,A,=e(s,A,Q,B,)a;,把 TA发送给 B.,2.B选取一个随机数 b r,计算 T,B,=e(s,B,Q,A,)b;把 TB发送给 A.,3.A 计算 K,AB,=T,B,a，同样地，B计算K,BA,=T,A,b,如果A和B正确执行协议，他们将计算出共享的密钥：,K,AB,=K,BA,=e(Q,A,Q,B,)sab,是否存在,中间人攻击,Scott IB Key Agreement,25,密钥协商:是否存在Scott IB Key Agreemen,Scott IB Key Agreement,B,A,e(sB,QA),b,e(sA,QB),a,e(Q,A,Q,B,),abs,e(Q,A,Q,B,),abs,26,Scott IB Key AgreementBAe(sB,Q,Scott IB Key Agreement,B,M,A,e(sB,QA),b,e(sA,QB),a,e(QA,QB),m,e(QA,QB),ma,e(QA,QB),asm,27,Scott IB Key AgreementBMAe(sB,Scott IB Key Agreement,B,M,A,e(sB,QA),b,e(sA,QB),a,e(P,QB),m,e(g,QB),sma,e(QA,QB),asm,M发送其它值,是否可行？,28,Scott IB Key AgreementBMAe(sB,Scott IB Key Agreement,B,M,A,求e(s,A,Q,B,),Q,A,P,求e(Q,A,Q,B,),s,Q,A,Q,B,P,Q,B,P,求e(s,B,Q,A,),sA,sB,K=e(Q,A,Q,B,),s,=e(g,g),sAB,29,Scott IB Key AgreementBMA求e(sA,效率（单个用户的计算复杂度）,1 pairing operation,1 map-to-point hash function(H),1 group ad