欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载
     

    四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt

    • 资源ID:3188477       资源大小:620.01KB        全文页数:76页
    • 资源格式: PPT        下载积分:8
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要8
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt

    1,四、公开密钥密码 阳振坤 yzkicst.pku.edu.cn 计算机科学技术研究所 http:/www.icst.pku.edu.cn/cryptocourse/,密码算法与应用基础,2,信息安全引论 对称密钥密码 对称密钥密码应用基础 公开密钥密码 数字签名与Hash函数 公开密钥密码应用基础 密钥交换与密钥管理,内容提要,3,信息安全的基本内容,保密性(Confidentiality) 真实性(Authentication) 完整性(Integrity) 不可否认性(Nonrepudiation) ,4,公开密钥密码,基本思想 数学基础 RSA算法 基于离散对数的算法 基于椭圆曲线的算法 密钥分发 总结 ,5,基本思想,加密与解密由不同的密钥完成 加密: XY: Y = EKU(X) 解密: YX: X = DKR(Y) = DKR(EKU(X) 从解密密钥得到加密密钥在计算上是不可行的 加密与解密的顺序没有限制(不是必须的) X = DKR(EKU(X) = EKU(DKR(X) 若X=Y且映射E: XY是映上的,则成立 EKU(X) = EKU(DKR(EKU(X) 若X=Y且为有限集合(例如分组密码),则E: XY是映上的,从而成立,6,用公钥密码实现保密,用户拥有自己的密钥对(KU,KR) 公钥KU公开,私钥KR保密 AB: Y=EKUb(X) B: DKRb(Y)= DKRb(EKUb(X)=X,7,用公钥密码实现认证,条件: 加密与解密的顺序没有限制 认证: AALL: Y=DKRa(X) ALL: EKUa(Y)=EKUa(DKRa(X)=X 认证+保密: AB: Z= EKUb(DKRa(X) B: EKUa(DKRb(Z)=X,8,公钥密钥的应用范畴,加密/解密 数字签名(身份认证) 密钥交换,9,公钥密钥算法必须满足的条件,密钥对的生成在计算上是可行的 用公钥加密明文在计算上是可行的 用私钥解密密文在计算上是可行的 从公钥获得私钥在计算上是不可行的 从公钥和密文来获得明文在计算上是不可行的 加密与解密的顺序没有限制(不是必须的) X = DKR(EKU(X) = EKU(DKR(X),10,One-way trapdoor function,对称密钥密码: Y = FK(X) easy if X & K are known X = FK-1(Y) easy if Y & K are known X = FK-1(Y) infeasible if only Y is known 公开密钥密码: Y = FK(X) easy if X & K are known X = FK-1(Y) easy if Y & K are known Where, K and K are related keys. X = FK-1(Y) infeasible if Y & K are known but K is unknown.,11,公钥密码分析,强制破译 通过公钥得到私钥 破译公钥加密的对称密钥 ,12,数学基础,素数,最大公约数(gcd),互素 模运算: a = qn + r, 0rn (a mod n) = r 同余: ab mod n iff (a mod n)=(b mod n) (a mod n)(b mod n) mod n = (ab) mod n (a mod n)(b mod n) mod n = (ab) mod n If (ab)(ac) mod n and a is relatively prime to n, then bc mod n (ab)(ac) mod n n|(ab-ac) n|(a(b-c) n|(b-c) bc mod n,13,Fermat定理,Fermat定理: p素数,a是整数且不能被p整除,则: ap-1 1 mod p 证明: 考虑集合1,2,p-1,对每个数乘以a,得到集合a mod p,2a mod p,(p-1)a mod p,对于p,后者两两不同且都在1与p-1之间,因此两个集合相同,于是: (p-1)! = 12(p-1) (a mod p)(2a mod p)(p-1)a mod p) mod p a2a(p-1)a mod p ap-1(p-1)! mod p 注意到(p-1)!与p互素,因此定理成立. 推论: p素数,a是任意整数,则: ap a mod p,14,Euler数,Euler数(n)定义为小于n且与n互素的正整数个数 p是素数,(p)=p-1 若n的因子分解为n=Piai, ai0,Pi互不相同,则 (n)= Piai(1-1/Pi) 若gcd(m,n)=1,则(mn)=(m)(n),特别地,若pq且都是素数, (pq)=(p-1)(q-1) Euler定理: 若a与n为互素的正整数,则: a(n) 1 mod n,15,Euler定理,a(n) 1 mod n 证明: R=x1,x2,x(n)为所有小于n且与n互素的正整数,考虑集合 S=(ax1mod n), (ax2mod n), (ax(n) mod n) (aximod n)与n互素 (aximod n)两两不等: (aximod n) = (axjmod n) ximod n = xjmod n S有(n)个元素 故S也是所有小于n且与n互素的正整数,因此S=R,从而 xi=(aximod n)(axi) mod n (a(n) xi) mod n 注意到xi 与n互素,从而得到结论.,16,Euler定理推论,推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 证明:若m=0或n,结论是显然的;若m与n互素,注意到(n)=(p-1)(q-1),由Euler定理可得到结论;否则m必定是p或者q的倍数,不妨设m=sp,则0sq为正整数,m与q互素,由Euler定理得到: m(q) 1 mod q (m(q)k(p) 1 mod q mk(p-1)(q-1) = tq+1 t是整数 等式两边乘以m=sp,得到: mk(p-1)(q-1)+1 = (tq+1)sp = tspq+sp m mod n,17,中国剩余定理(1),中国剩余定理: m1,m2,mk是两两互素的整数, a1,a2,ak是任意整数,M=mi,那么方程组 xai mod mi, 1im 关于模M有唯一解: x aiMi(Mi-1 mod mi) mod M , Mi=M/mi 证明: m1,m2,mk两两互素因此gcd(Mi,mi)=1 Mi-1 mod mi存在 正确性: Mi定义 Mi0 mod mj, 任给ij,18,中国剩余定理(2), x aiMi(Mi-1 mod mi) mod mj ajMj(Mj-1 mod mj) mod mj aj mod mj 正确性 唯一性: 假如x,y都是解x y mod mi,对任意i mi|(x-y),对任意i (mi) |(x-y),对任意j (m1,m2,mk两两互素) M|(x-y) x y mod M 唯一性 ,19,(axi mod n)与n互素,a与n为互素的正整数,x1,x2,x(n)为所有小于n且与n互素的正整数. S=(ax1mod n), (ax2mod n), (ax(n) mod n) 反证法: 若某个(aximod n)与n不互素,则存在素数p使得 p|n且p|(aximod n) 令r=(aximod n),则axi=tn+r,t是整数 p|n,p|r p|(axi) p|a或者p|xi 这说明a或者xi与n有共因子p,与假设a和xi都与n互素相矛盾. ,20,RSA算法简介,由Ron Rivest,Adi Shamir & Len Adlemen于1977年发布 属于分组密码 明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法 只在美国申请专利且已于2000年9月到期 NSA声称在60年代中期发现了公钥算法 英国的Clifford Cocks在1973年发表了与RSA几乎一样的算法,21,RSA算法描述,分组大小为k, 2k n 2k+1 加密: C = Me mod n 解密: M = Cd mod n = Med mod n 公钥: KU=e,n, 私钥: KR=d,n 上述算法需要满足以下条件: 能够找到e,d,n,使得Med mod n = M, 对所有Mn 计算Me和Cd相对容易 从e和n得到d是在计算上不可行的,22,RSA密钥生成原理,令n=pq, pq都是素数,(n)=(p-1)(q-1)是n的Euler数 Euler定理推论: 若n=pq, pq都是素数, k是任意整数,则 mk(p-1)(q-1)+1 m mod n, 对任意0mn 只要选择e,d, 满足ed=k(n)+1,即 ed 1 mod (n) d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n,23,RSA密钥生成与使用,选择两个大素数p,q, pq 计算n=pq,(n)=(p-1)(q-1) 选择整数e,使得gcd(e,(n)=1 (两个随机数互素概率0.6) 计算d e-1 mod (n) 公钥: KU=e,n, 私钥: KR=d,n 加密: C = Me mod n 解密: M = Cd mod n ,24,提高RSA解密速度: 结论1,解密: M = Cd mod n需作大数的幂运算,速度慢 结论1: 若pq都是素数,n=pq,则同余方程 x xp mod p x xq mod q 对模n有唯一解 x=(xp-xq)(q-1mod p)q+xq 证明: pq是素数 gcd(p,q)=1 q-1mod p存在. 唯一性由中国剩余定理保证. 验证解: 令r=q-1mod p,则r是整数, rq1 mod p x=(xp-xq)rq+xq 对于q, x=(xp-xq)r)q+xqxq mod q 对于p, x=(xp-xq)(rq)+xq(xp-xq)+xqxp mod p,25,提高RSA解密速度: 结论2,结论2: p素数,a是任意整数,则 ak (a mod p)k mod (p-1) mod p, k是任意整数 证明: 若a 0 mod p, 结论是显然的.否则, 令k=t(p-1)+r, t,r是整数, r=k mod (p-1), 那么 ak = at(p-1)+r at(p-1)ar mod p ar mod p (Fermat定理: ap-1 1 mod p) (a mod p)r mod p (a mod p)k mod (p-1) mod p,26,提高RSA解密速度: 方法,解密: M = Cd mod n, n = pq, pq都是素数 假如得到了 Mp M mod p Mq M mod q 就得到了M=(Mp-Mq)(q-1mod p)q+Mq mod n 由于M=Cd mod n,因此 Mp=Cd mod p = (C mod p)d mod (p-1) mod p Mq=Cd mod q = (C mod q)d mod (q-1) mod q 由于C mod p与C mod q要比C小, d mod (p-1)与d mod (q-1)也比d小,故解密速度会提高(48倍).,27,提高RSA加密速度?(1),同样的方法可以用于RSA的加密 加密: C = Me mod n, n = pq, pq都是素数 假如得到了 Cp C mod p Cq C mod q 就得到了C=(Cp-Cq)(q-1mod p)q+Cq mod n 由于C=Me,从而 Cp=Me mod p = (M mod p)e mod (p-1) mod p Cq=Me mod q = (M mod q)e mod (q-1) mod q 加密速度是否会提高?,28,提高RSA加密速度?(2),加密: C = Me mod n, n = pq, pq都是素数 M0,1,2,2k-10,1,2,n-1, 其中2kn2k+1 定义上,加密E: 0,1,2,n-10,1,2,n-1 实际上,加密E: 0,1,2,2k-10,1,2,n-1 解密映射的定义域总是0,1,2,n-1 M在较小的空间上,C在较大的空间上 e一般可以选择比d小 加密: Cp=Me mod p = (M mod p)e mod (p-1) mod p 解密: Mp=Cd mod p = (C mod p)d mod (p-1) mod p 同样的方法对加密速度的提高不如对解密速度的提高显著,29,RSA的安全性,强制破解 基于数学的攻击 基于运算时间的攻击 ,30,RSA加密解密计算量,加密: C = Me mod n 解密: M = Cd mod n 幂运算位数增长快 幂运算速度慢并且e,d都是很大的数 (a mod n)(b mod n) mod n = (ab) mod n 计算xm,其中m=2s,只需要计算s次,即计算: xmi,mi=2i,i=0,1,s,31,计算幂,计算d=am, m=bkbk-1b0(二进制表示) d1 for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod n return d ,32,Euclid算法,gcd(a,b)=gcd(b, a+kb) a,b,k为任意整数 gcd(a,b)=gcd(b, a mod b) a0,b0 Eclid(d,f): 求最大共约数,假定df Xf, Yd if Y = 0 then return X X X mod Y XY goto 上述的循环最多进行多少次? 2log2(max(f,d),33,扩展Euclid算法,ExtEclid(d,f):求最大共约数或模逆, 假定df (X1,X2,X3)(1,0,f), (Y1,Y2,Y3)(0,1,d) if Y3 = 0 then return X3, no inverse if Y3 = 1 then return 1, inverse is Y2 Q (X3/Y3)的整数部分 (X1,X2,X3)(X1-QY1, X2-QY2, X3-QY3) (X1,X2,X3) (Y1,Y2,Y3) goto fX1+dX2=X3, fY1+dY2=Y3 若Y3=1,则 fY1+dY2=1 dY2=(-Y1)f+1 dY2 1 mod f Y2 = d-1 mod f ,34,素数模的平方剩余解,直接判断一个整数是否为素数是困难的 命题: 如果p是素数,则方程 x2 1 mod p 只有平凡解x 1 mod p. 证明: x2 1 mod p p|(x2-1) p|(x+1)(x-1) p|(x+1),或者p|(x-1) x+1=kp,或者x-1=jp, k,j是整数 x=kp-1,或者x=jp+1 x 1 mod p, 或者x -1 mod p,35,Miller-Rabin素数测试算法,Miller-Rabin算法用来测试一个整数是否是素数 WITNESS(a,n) 设bkbk-1b0是(n-1)的二进制表示 d1 for ik downto 0 do xd d(dd) mod n /x2 1 mod n if(d=1 & x1&xn-1) return TRUE if(bi=1) then d(da) /d=an-1 if(d1) return TRUE /Fermat定理 else return FALSE Miller-Rabin是概率测试(一次概率约0.5) ,36,素数生成,素数生成过程: 随机选择一个奇数n(如通过伪随机数发生器) 随机选择a, 使an 进行素数测试(例如用Miller-Rabin算法),若n没有通过测试,抛弃n,转到 如果通过了足够次数的测试,认为n是素数,否则转到. 素数定理: (N)N/ln(N), (N)为不超过N的素数个数. 随机整数N是素数的概率是1/ln(N) ,37,基于数学的攻击,公钥: KU=e,n, 私钥: KR=d,n, n=pq 分解n=pq (n)=(p-1)(q-1) d=e-1 mod (n) 不求出p,q,直接求(n) d=e-1 mod (n) 不求出(n),直接计算d 已知的方法至少跟因子分解一样难度 尚未发现多项式时间的因子分解算法 因子分解的算法已经取得了长足进步 如果en并且dn,则d容易被得到.目前已知最好的结果是=0.292 措施: 选择足够大的n(1024位以上),并且使得e,d之间相差不太大,也不太小,38,同模攻击,如果A,B使用同样模n的RSA算法(e1,d1,n),(e2,d2,n),C把信息M用A,B的公钥分别加密并传给它们: Y1 = Md1: A Y2 = Md2: B 假如gcd(d1,d2)=1,则窃听者能获得明文.做法是: 找到整数a1,a2,使得: a1d1+a2d2=1 (gcd(d1,d2)=1) 不妨假定a10,那么: M = (Y11)-a1Y2a2 mod n (Y11)-a1Y2a2= (Md1)1)-a1(Md2)a2 =Md1a1+a2d2 措施: 避免在不同用户之间共享模.,39,其他攻击,RSA的同态性质: EK(m1m2)=EK(m1)EK(m2) 措施: 加密前对信息处理,如通过hash或者单向函数 如果(p-1)或者(q-1)只有小的素数因子,则n容易被分解,n被分解的计算量与(p-1)或者(q-1)的最大素因子成某种正比. 措施: 找到p1q1,使得p1,q1,2p1+1,2q1+1都是素数,然后选择p=2p1+1,q=2q1+1(安全素数). ,40,基于运算时间的攻击,基于加密程序运行时间的攻击 计算d=am, m=bkbk-1b0(二进制表示) d1 for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod n return d 若bi=1, 执行d(da) mod n,否则不执行. 有少数的a,d, 上述模乘速度很慢 从左到右逐个确定bi,41,基于运算时间攻击的特征与防备,特征: 一种全新的攻击手段 选择明文的攻击 适用于攻击其他公钥算法 防备:计算d=am, m=bkbk-1b0(二进制表示) for ik downto 0 do d(dd) mod n if bi = 1 then d(da) mod n return d Constant exponentiation time Random delay Blinding,42,RSA Blinding,RSA blinding: 选择一个随机数r,使得gcd(r,n)=1,0rn 加密: C=(Mr)e mod n C = CD mod n D=(r-1)e, r-1是r关于mod n的乘法逆 解密: M= Cd mod n 代价: 每个块增加两个乘法,210%的性能损失 其他解决措施(初始化向量) ,43,因子分解算法改进,Special number field sieve速度更快 ,44,Montre Carlo模型,YES-BIASED型Montre Carlo算法:一个YES的回答总是正确的,一个NO的回答则可能是正确,也可能是错误的.称一个YES-BIASED算法具有错误概率,是指它回答NO时出错的几率至多是 NO-BIASED型Montre Carlo算法 Miller-Rabin属于YES-BIASED型Montre Carlo算法,其出错概率是0.5 ,45,密钥分发,分发公钥 Public announcement Publicly available directory Public-key authority Public key certificates 利用公钥分发对称密钥 Simple secret key distribution Secret key distribution with confidentiality and auhtentication Hybrid scheme ,46,Public announcement,直接把公钥散发出去 使用PGP并且把公钥附上 能被假冒 ,47,Publicly available directory,需要可信任的中央授权机构 授权机构维护着动态name,public key列表 用户在授权机构注册其public key(安全通道) 用户可以替换其public key 授权机构定期发布或更新整个目录 用户可在网络上直接访问公共目录(安全通道),48,Public-key publication,若成功修改了公共目录,则攻击者可假冒用户 ,49,Public-key authority,需要可信任的中央授权机构 每个用户知道授权机构的公钥 AAuth: (IDA,IDB,T1) AuthA: EKRauth(KUb,T1) AB: EKUb(IDA,N1) BAuth: (IDB,IDA,T2) AuthB: EKRauth(KUa,T2) BA: EKUa(N1,N2) AB: EKUb(N2),50,Public-key Distribution Scenario,若成功修改了公共目录,则攻击者可假冒用户 授权中心易成为性能及安全瓶颈 ,51,Public-key certificates,任何人可以阅读证书以确定证书拥有者的姓名和公钥 任何人可以验证证书是由授权机构发出而非伪造的 只有授权机构才可以发行和更新证书 任何人可以验证证书的时效性(非失效证书) CA=EKRauth(T,IDA,KUa),52,Exchange of public-key certificates,泄漏私钥等价于丢失证书 证书的时间作为有效期 ,53,Simple secret key distribution,Merkle的建议: A生成KUa,KRa, AB: (IDA,KUa) B生成随机密钥Ks, BA: EKUa(Ks) A解密EKUa(Ks)得到Ks: DKRa(EKUa(Ks) A丢弃KUa,KRa,B丢弃KUa 通讯前不需存在密钥,通讯后也不存在密钥 能抵抗偷听,不能抵抗主动攻击(中间人攻击),54,Merkle协议的中间人攻击,A生成KUa,KRa, AB: (IDA,KUa) E截获,生成KUe,KRe冒充AB: (IDA,KUe) B生成随机密钥Ks, BA: EKUe(Ks) E截获,解密后再用EKUa加密KsA: EKUa(Ks) A丢弃KUa,KRa,B丢弃KUa E获得了Ks,故以后只需进行窃听. A,B并不知晓它们被攻击了 ,55,Secret key distribution with confidentiality and authentication,假定A和B已经获得了双方的公钥: AB: EKUb(IDA,N1) BA: EKUa(N1 ,N2) AB: EKUb(N2) AB: Y=EKUb(EKRa(Ks) B解密Y获得会话密钥Ks=DKUa(DKRb(Y),56,Secret key distribution with confidentiality and authentication: Map,57,Hybrid Scheme,在IBM大型主机上使用 仍然使用KDC KDC与每个用户都拥有公钥,私钥对 KDC与每个用户共享主密钥(对称密钥密码) 会话密钥的分发由主密钥完成 主密钥更新由公钥完成 Performance Backward compatibility ,58,原根(primitive root),Euler定理表明,对两个互素的整数a,n, a(n) 1 mod n 因此存在最小正整数m(n) (m|(n),使得 am 1 mod n 若对某个a,m=(n),则称a是n的一个原根(primitive root).只有为2,4,p,2p的数才有原根,其中p是奇素数. 对于素数p,若a是p的一个原根,则: a,a1,a2,ap-1 关于p两两不同余,从而构成了p的非0剩余类,即与1,2,(p-1)关于模p等价.,59,离散对数,若a是素数p的一个原根,则对任意整数b, b0 mod p,存在唯一的整数i, 1i(p-1),使得: bai mod p i称为b以a为基模p的指数(离散对数),记作inda,p(b).容易知道: inda,p(xy)= inda,p(x)+inda,p(y) mod (p) inda,p(xr)= rinda,p(x) mod (p) 离散对数的计算: ygx mod p 已知g,x,p,计算y是容易的 已知y,g,p,计算x是困难的,60,Diffie-Hellman密钥交换,双方选择素数q以及q的一个原根r A选择Xq,计算XA=rXmod p, AB: XA B选择Yq,计算YB=rYmod p, BA: YB A计算: (YB)X(rY)XrXYmod p B计算: (XA)Y(rX)YrXYmod p 双方获得一个共享密钥(rXYmod p) 素数q以及q的原根r可由一方选择后发给对方 不能抵抗replay攻击 对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,61,Diffie-Hellman密钥交换的攻击,双方选择素数q以及q的一个原根r(假定E知道) A选择Xq,计算XA=rXmod p, AB: XA E截获XA,选Z,计算ZE=rZmod p,冒充AB:ZE B选择Yq,计算YB=rYmod p, BA: YB E截获YB,冒充BA: ZE A计算: (ZE)X(rZ)XrZXmod p B计算: (ZE)Y(rZ)YrYZmod p E计算: (XA)ZrXZmod p, (YB)ZrYZmod p E无法计算出rXYmod p E永远必须实时截获并冒充转发,否则会被发现.,62,ElGamal加密算法,选择: 一个素数p,p的一个原根r,一个整数a,令s=ra,公开p,r,s,保密a. 对于明文信息x, 加密: 秘密选择随机数k, 计算(rk mod p,xsk mod p)作为密文 解密: (xsk)(rk)a)-1 xrakr-ak x mod p 信息有扩张 ,63,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出 y2+axy+by=x3+cx2+dx+e 曲线上的点连同无穷远点O的集合 加法:若曲线三点在一条直线上,则其和为零 倍数:一个点的两倍是它的切线与曲线的另一个交点,64,椭圆曲线密码示意图,65,有限域上椭圆曲线,有限域上椭圆曲线 y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p y2+xyx3+ax2+b mod 2m 加法公式: P=(x1,y1), Q=(x2,y2) 若x1=x2且y1=-y2,则P+Q=O,否则 P+Q=(x3,y3) x3=2-x1-x2 y3=(x1-x3)-y1 其中, =(y2-y1)/(x2-x1), 如果PQ =(3x12+a)/2y1, 如果P=Q,66,Ep(a,b),椭圆曲线上的整数点在上述运算下成为一个交换群(Abelian群),记作Ep(a,b).关于|Ep(a,b)|,有如下不等式: p+1-2p1/2 |Ep(a,b)| p+1+2p1/2 该不等式表明: |Ep(a,b)| p G是Ep(a,b)的一个元素,使得nG=O的最小正整数n称为元素G的阶.,67,椭圆曲线密钥交换,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数 A选择Xn,计算PA=XG, AB: PA B选择Yn,计算PB=YG, BA: PB A计算: X(PB)=XYG B计算: Y(PA)=YXG=XYG 双方获得了一个共享会话密钥(XYG) 不能抵抗replay攻击 对中间人攻击的抵抗力远好于“Simple secret key distribution(Merkle的建议)”,68,椭圆曲线密钥交换的攻击,双方选择Ep(a,b)以及Ep(a,b)的一个元素G,使得G的阶n是一个大素数 A选择Xn,计算PA=XG, AB: PA E截获PA,选Z,计算PE=ZG,冒充AB:PE B选择Yn,计算PB=YG, BA: PB E截获PB,冒充BA: PE A计算: XZE = XZG B计算: YZE = YZG E计算: ZPA=ZXG, ZPB =ZYG E无法计算出XYG E永远必须实时截获并冒充转发,否则会被发现.,69,椭圆曲线加密解密,选择Ep(a,b)的元素G,使得G的阶n是一个大素数,秘密选择整数r.计算P=rG,公开(p,a,b,G,P),保密r. 加密M: 选择随机数k,C=kG,M+kP) 如果k使得kG或者kP为O,则要重新选择k. 解密C: (M+kP)-r(kG)=M+krG-rkG=M 加密信息有扩张,70,椭圆曲线密码的安全性,难点: 从P和kP获得k 对椭圆曲线研究的时间短 椭圆曲线要求密钥长度短,速度快 对比: ECC RSA,71,公开密钥密码总结,三类算法: RSA, ElGamal, ECC RSA 基础: IFP(Integer Factorization Problem) 加密、解密、密钥交换、数字签名 使用最广泛 ElGamal 基础: DLP(Discrete Logarithm Problem) 加密、解密、密钥交换、数字签名,72,公开密钥密码总结,ECC 基础: ECDLP(Elliptic Curve Discrete Logarithm Problem) 加密、解密、密钥交换、数字签名 密钥短,速度快 正在开始广泛应用 公钥算法加密解密速度慢 误区:公开密钥密码算法更安全 公开密钥密码使对称密钥密码过时了 公钥的分发是简单和一目了然的,73,Euler公式证明(1),注意到当n是素数时,(n)=n-1,所以只要说明,对任意素数p和任意正整数n: (np)=p(n), 若p整除n (np)=(p-1)(n), 若p不整除n 证明:把集合1,2,n分成两子集X=x1,x2,x(n)和Y=y1,y2,yn-(n),X为所有与n互素的数,Y为其余.记Xk=kn+x1, kn+x2, kn+x(n) , Yk=kn+y1, kn+y2, kn+yn-(n), 0kp, 显然全部的Xk,Yk的并集构成1,2,np. 由Y的定义, Y与n有大于1的公因子,从而所有Yk与(np)有大于1的共因子.,74,Euler公式证明(2),若p整除n,由于X与n互素,容易知道Xk与n互素,故 (np)=p|X|=p(n) 若p不整除n,若Xk中一个元素kn+xi与(np)有大于1公因子,设q是其一个素数公因子,则q|n或者q=p,假如是前者,则q|n, q|(kn+xi) q|xi,从而n与xi有公因子q,这与X的定义矛盾,因此q=p,这表明若某个Xk中的某个元素kn+xi与(np)有大于1公因子,则该公因子只能是p. 注意到不超过(np)的所有p的倍数是px1, px2, , px(n)和py1, py2, pyn-(n).,75,Euler公式证明(3),由于n与yj不互素,故存在素数q,使得q|n,q|yj,又由于p不整除n qp.由于xi与n互素,所以q不能整除xi,也不能整除pxi pxikn+yj (pxi不含因子q,而kn和yj含因子q) pyi kn+xj (xi不含因子q,而kn和pyj含因子q) 这说明任一pxi (1i(n)位于某个Xk中,任一pyi (1in-(n)位于某个Yk中,故全部Xk中与n有公因子p的数是px1, px2, px(n),故 (np)=p|X|-(n)=(p-1)(n) 公式得证. ,76,实习作业之二,实现Rijndael,具体要求与第一次作业相同,差别: 算法是Rijndael(而不是DES) 十一月七日前以email提交电子文档 Email地址: li_binicst.pku.edu.cn 参见网址: http:/www.icst.pku.edu.cn/cryptocourse/,

    注意事项

    本文(四公开密钥密码阳振坤yzkicstpkueducn计算机科学技术.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开