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

1、1基于身份的密码体制基于身份的密码体制现代密码学现代密码学第十一章第十一章2精品课程网站测试精品课程网站测试nhttp:/n用户名：student1,student9n密码1111113作业作业n5月31日之前，作业提交 作业提交名单查询n6月10日之前，作业补交，之后提交作业不再记录4上节主要内容上节主要内容n身份鉴别的定义n口令认证协议n挑战应答协议n对身份识别协议的攻击和对策5本讲主要内容本讲主要内容n基于身份的密码系统（IBC）的提出n基于身份的加密体制（IBE）的定义nBoneh-Franklin IBE方案n基于身份的签名体制（IBS）的定义nShamir IBS方案n基于身份的密

2、钥协商（IBKA）的定义nScott IBS方案nIBC的应用n公开问题6基于身份的密码体制基于身份的密码体制nIBC是一种非对称密码体系，与以往公钥密码系统的不同在于任意的字符串可以作为用户的公钥，例如每个人的身份标识，email地址，电话号码等。n不需要CA系统将用户的身份和用户的公钥绑定。7基于基于IBC的安全电子邮件系统的安全电子邮件系统使用公钥加密邮件使用公钥加密邮件“”我是我是“”私钥私钥master-keyCA/PKG基于身份的密码体制基于身份的密码体制是否可以像PKI系统，由用户自己生成私钥？8基于身份的密码体制基于身份的密码体制n私钥生成（PKG）系统的PKG中心拥有一对主密

3、钥（master key），它公布主密钥中的公钥，自己保存私钥；PKG中心输入自己的私钥和用户的公钥，得到用户的公钥，并安全传回给用户；用户输入这个私钥和PKG中心的公钥，检查收到的私钥是否正确。9基于身份的加密体制基于身份的加密体制n1984年以色列科学家Shamir提出了基于身份的密码系统的概念（IBC）。n2001年，D.Boneh和M.Franklin,R.Sakai,K.Ohgishi 和 M.Kasahara利用椭圆曲线上的双线性对设计了基于身份的加密算法。n2001年C.Cocks利用平方剩余难题设计了基于身份的加密算法。nD.Boneh和M.Franklin提出的IBC(BF-

4、IBC)的安全性可以证明并且有较好的效率，所以引起了极大的反响。10基于身份的加密体制基于身份的加密体制n初始化初始化n输入:安全参数 tn输出:系统参数系统参数params和主密钥主密钥master-key n提取私钥提取私钥n输入:系统参数系统参数params和主密钥主密钥master-key 用户身份 ID0,1*n输出:用户私钥dID11基于身份的加密体制基于身份的加密体制n加密加密n输入:系统参数系统参数params,明文MM，明文接收者公钥（身份）ID0,1*,n输出:密文Cn解密解密n输入:系统参数系统参数params,密文C C，接收者私钥dID,n输出:明文M12双线性映射双

5、线性映射e:G1 G1 G2nG1 和 G2 是阶为p的循环群n双线性映射n任给 x,y G1 和任意整数 a,b Zpe(ax,by)=e(x,y)ab n非退化性（Non-Degenerate）n存在 x,y G1 使得 e(x,y)1G2 n可计算性（Computable）n对于任意给定的 x,y G1，计算 e(x,y)是容易的13安全性假设安全性假设nBilinear Diffie-Hellman 问题(BDHP)阶为q的循环群G1,G2,群上的双线性映射en给定G1上的一个生成元 g 和其上的任意三个元素 ag,bg,cg G1，其中 a,b,c Zp,计算 e(g,g)abcn安

6、全性假设:BDHP 是困难的14Boneh-Franklin IBE SchemeBoneh-Franklin IBE Schemen初始化初始化(t)n用 t 生成一个素数 qn生成阶为q的循环群 G1,G2,及一个双线性映射e:G1G1 G2n任意选取一个生成元 gG1n选取一个随机数 sZq*令 P=sgn选取两个密码学hash函数:H1:0,1*G1*和 H2:G2 0,1n15n初始化初始化(t)nM=0,1nnC=G1*0,1nnparams=q,G1,G2,e,n,g,P,H1,H2nmaster-key=sn私钥生成私钥生成(ID)ndID=s H1(ID)Boneh-Fran

7、klin IBE SchemeBoneh-Franklin IBE Scheme16n加密加密(M)n选取随机数 rZq*nR=rg,M H2(e(H1(ID),P)r)n解密解密(C=(U,V)nV H2(e(dID,U)n正确性证明正确性证明 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-Franklin IBE SchemeBoneh-Franklin IBE Scheme17Boneh-Franklin IBE SchemeBoneh-Franklin IBE

8、Schemen效率 加密：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.n效率解密：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,18基于身份的签名体制基于身份的

9、签名体制n初始化（初始化（Setup）n输入:安全参数 tn输出:系统参数系统参数params和主密钥主密钥master-key n提取私钥（提取私钥（Extract）n输入:系统参数系统参数params和主密钥主密钥master-key 用户身份 ID0,1*n输出:用户私钥dID19n签名（签名（Sign）n输入:系统参数系统参数params,消息MM，签名者的私钥dID.n输出:签名S n验证（验证（Verify）n输入:系统参数系统参数params,签名S，签名者公钥（身份）ID0,1*,消息MM.n输出:“Accept”或者“Reject”.基于身份的签名体制基于身份的签名体制20S

10、hamir提出了一个采用RSA算法的IBS算法。n初始化初始化:1.选取两个大素数p，q，计算它们的乘积n；选取与(n)互素的整数 e;选取一个单向函数h.参数:n,e,h；主密钥:n 的因子.n提取私钥提取私钥:给定用户的 ID,PKG计算用户的私钥 g，满足 ge=ID mod n.Shamir IBS SchemeShamir IBS Scheme21n签名签名:A 用私钥 g 签署消息 m:1.选取随机整数 r，计算t=re mod n 2.计算s=g*rh(t,m)mod nnSignature:=Zn Zn.n验证验证:验证者收到签名 =，消息m和签名者的公钥(身份ID),验证下式

11、是否成立 se=ID*t h(t,m)mod n.Shamir IBS SchemeShamir IBS Scheme22Shamir IBS SchemeShamir IBS Schemen效率签名和验证分别需要 2 integer exponentiations,1 integer multiplication and 1 hash operation.n安全性：分解因子问题困难Integer Factorization Problem(IFP).23n初始化（初始化（Setup）n输入:安全参数 tn输出:系统参数系统参数params和主密钥主密钥master-key n提取私钥（提取私

12、钥（Extract）n输入:系统参数系统参数params和主密钥主密钥master-key 用户身份 ID0,1*n输出:用户私钥dIDn密钥协商（密钥协商（Key Agreement）n输入:系统参数系统参数params和用户私钥用户私钥dIDn输出：会话密钥K基于身份的密钥协商体制基于身份的密钥协商体制24（基于Weil对对 和Tate 对）n初始化:PKG 选取一个满足 p=3 mod 4且 p+1=c*r，其中c,r亦为素数；选取一个将0-1数据映射到椭圆曲线上点的hash函数H:0,1 G1.；选取一个随机数 s Fq 作为主密钥.params:；master-key:sn提取私钥:

13、设用户 A 的身份是 IDA,PKG 计算他的私钥 QA=H(IDA).；SA=sQA.Scott IB Key AgreementScott IB Key Agreement25n密钥协商密钥协商:A 选取一个随机数 a r,计算 TA=e(sA,QB)a;把 TA发送给 B.2.B选取一个随机数 b r,计算 TB=e(sB,QA)b;把 TB发送给 A.3.A 计算 KAB=TBa，同样地，B计算KBA=TAb如果A和B正确执行协议，他们将计算出共享的密钥：KAB=KBA=e(QA,QB)sab是否存在中间人攻击Scott IB Key AgreementScott IB Key Agr

14、eement26Scott IB Key AgreementScott IB Key AgreementBAe(sB,QA)be(sA,QB)ae(QA,QB)abse(QA,QB)abs27Scott IB Key AgreementScott IB Key AgreementBMAe(sB,QA)be(sA,QB)ae(QA,QB)me(QA,QB)mae(QA,QB)asm28Scott IB Key AgreementScott IB Key AgreementBMAe(sB,QA)be(sA,QB)ae(P,QB)me(g,QB)smae(QA,QB)asmM发送其它值是否可行？29

15、Scott IB Key AgreementScott IB Key AgreementBMA求e(sA,QB)QA,P求e(QA,QB)sQA,QB,PQB,P求e(sB,QA)sAsBK=e(QA,QB)s =e(g,g)sAB30n效率（单个用户的计算复杂度）1 pairing operation,1 map-to-point hash function(H),1 group addition in G1 2 group exponentiations in G2.n安全性：基于BDHP的困难性.Scott IB Key AgreementScott IB Key Agreement31

16、n多方密钥协商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的应用的应用nBoneh和Franklin的团队的努力,IBE 被应用于 Debian GNU/Linux.nShamus Software 也开发了包含 BF-IBE 的密码文库，称为“MIRACL”source code is available athttp:/crypto.stanford.edu/ibe

17、/download.htmlStanford 和Shamus图书馆开发使用 C/C+.似乎还没有Java implementation of IBE33IBC的应用的应用n现实应用中，Voltage Security 开发了包含IBE的 email 系统，它为Outlook,pine,hotmail,and Yahoo提供插件.nHewlett Packard Lab(布里斯托尔Bristol,UK)的研究员开发健康保健信息系统使用了IBE 系统.34IBC的应用的应用nIEEE P1363.3的基于标识的密码技术工作组正在进行相关算法的标准化工作。nISO/IEC已经标准化了两个基于身份的签

18、名算法。n2007年，国家密码局组织了国家标识密码体系IBC标准规范(Identity-Based Cryptograph)的编写和评审工作。由五位院士和来自党政军、科研院所的密码专家组成了评审组，对该标准规范在安全性、可靠性、实用性和创新性等方面进行了多次严格审查,2007年12月16日国家IBC标准正式通过了评审。35公开问题公开问题n密钥托管问题.所有IBC密码方案都有“密钥托管”的弱点。在IBE 和IBS方案中,用户的私钥是由PKG用他的主密钥来计算发布.因此，PKG拥有用户的私钥，可以解读相关的密文，冒充用户签名。n对策：Boneh 和 Franklin提出利用 Shamir 提出的

19、秘密共享技术分散单个PKG的权利n缺点：增加系统负担是否有更好的方法？36公开问题公开问题n密钥撤销问题.在基于身份的密码系统中，公钥是用户的身份信息，但是用户的私钥泄露时该公钥/私钥对将不能再使用（或者按策略需要定期更新密钥对），是否更换用户的身份（如电子邮箱等）？n对策Boneh 和Franklin 建议用户在身份信息后缀上密钥的生存期，如 |June,2004 作为真正的公钥，这样公钥可以定期撤销更换。PKI需要用CRL来公布撤销的公钥，用户在加密或者签名验证时首先要检查用户的公钥是否已经被撤销？37公开问题公开问题n效率问题：目前的IBE系统有两种实现方式，一种是基于双线性对（Weil

20、 pairing 和Tate pairing），如BFIBE；另一种是基于因子分解（二次剩余），如COCK的方案。第一种方案简单，但是双线性对的计算复杂度较高；第二种的数学问题较容易计算，但是方案一般效率低。38本节要点回顾本节要点回顾n基于身份的密码系统定义nIBE 定义及BF方案nIBS定义及shamir方案39思考：下列加密算法是否正确思考：下列加密算法是否正确n初始化初始化(t)n随机选取两个 t t比特素数 p,qn公开参数为公开参数为n=pqn=pq,和一个和一个hash函数函数H(*)nPKG中心的私钥为中心的私钥为p,qn私钥提取私钥提取(n,H(n,H,p p,q,ID)q,ID)=d dIDIDnd dIDID *H(ID)=1 H(ID)=1 mod(p-1)(q-1)(p-1)(q-1)n加密：加密：E(n,H(n,H(*),ID,),ID,MM)=M=MH(ID)H(ID)mod nn解密：解密：D(n,H(n,H(*),d,dIDID,C C)=C)=Cd dIDID mod n n40THE END！