chap密钥管理以及其他公钥体制

,公钥密码,10.1 Diffie-Hellman密钥交换算法,Diffie和Hellman在其里程碑意义的文章中，虽然给出了密码的思想，但是没有给出真正意义上的公钥密码实例，也既没能找出一个真正带陷门的单向函数然而，他们给出单向函数的实例，并且基于此提出Diffie-Hellman密钥交换算法,Diffie-Hellman密钥交换,允许两个用户可以安全地交换一个秘密信息，用于后续的通讯过程算法的安全性依赖于计算离散对数的难度素数p的原始根定义：如果a是素数p的原始根，则数a mod p, a2 mod p, , ap-1 mod p是不同的并且包含1到p-1的整数的某种排列。对任意的整数b，我们可以找到唯一的幂i满足b=ai mod p 0=i=(p-1)i 在离散对数算法中称为以a为基的指数 mod p。记为inda,p(b),Diffie-Hellman密钥交换协议描述,Alice和Bob协商好一个大素数p，和大的整数g，1p和g无须保密，可为网络上的所有用户共享 。,Diffie-Hellman密钥交换协议描述,当Alice和Bob要进行保密通信时，他们可以按如下步骤来做： (1) Alice选取大的随机数x，并计算 X = gx(mod P) (2) Bob选取大的随机数x，并计算 X = gx (mod P) (3) Alice将X传送给Bob；Bob将X 传送给Alice (4) Alice计算K= (X )X(mod P); Bob计算K =（X) X (mod P), 易见，K = K =g xx (mod P)由(4)知，Alice和Bob已获得了相同的秘密值K双方以K作为加解密钥以传统对称密钥算法进行保密通信,Generate randomXa pCalculateYa=aXa mod p,Generate randomXb pCalculateYb=aXb mod p,User A,User B,Ya,Yb,CalculateK=(Yb)Xa mod p,CalculateK=(Ya)Xb mod p,Diffie-Hellman Key Exchange,交换示例 为了计算简单，使用很小数字。设P=47和47的一个原元，a=3。A选择秘密密钥XA=8，B选择秘密密钥XB=10，各自计算其公开密钥。（1）双方各自计算用户A计算： YA=3 8mod 47=6561 mod 47=28 mod 47用户B计算： YB=3 10mod 47= 59049 mod 47=17 mod 47（2）交换YA和YB；（3）交换密钥后，A、B分别计算共享的秘密会话密钥KA、KB：用户A计算： KA=YB XA mod 47=178 mod 47=4 mod 47用户B计算： KB=YA XB mod 47=2810 mod 47=4 mod 47 A和B双方独立地决定采用4作为会话密钥。,Alice和Bob首先商议好p的值，本例假设为p=2579，则本原元为a=2。 假设Alice要发送消息x=1299给Bob，则 1）Bob选择随机数r=765作为自己的私钥，计算q=2r mod p=2756 mod 2579=949，作为公钥给Alice； 2）Alice选择随机数k=853，计算y=2k mod p=2853 mod 2579=435，作为公钥给Bob； 3）Alice计算密文e=x*q%k mod p=1299*949853 mod 2579=2396，并传递给Bob； 4）Bob接收到密文后，计算x=e*(yr)(-1) mod p=2396*(435765)(-1) mod 2579=1299，从而得到原文。,Diffie-Hellman安全性,离散对数的计算:ygx mod p已知g,x,p,计算y是容易的已知y,g,p,计算x是困难的,Diffie-Hellman密钥交换的攻击,replay攻击,中间人攻击图示,Diffie-Hellman密钥交换的攻击,中间人攻击1 双方选择素数p以及p的一个原根a(假定O知道)2 A选择Xap,计算Ya=aXa mod p, AB: Ya3 O截获Ya,选Xo,计算Yo=aXo mod p,冒充AB:Yo4 B选择Xbp,计算Yb=aXb mod p, BA: Yb5 O截获Yb,冒充BA:Yo6 A计算: (Xo)Xa(aXo)XaaXoXa mod p7 B计算: (Xo)Xb(aXo)XXbaXoXb mod p8 O计算: (Ya)XoaXaXo mod p, (Yb)XoaXbXo mod pO无法计算出aXaXb mod pO永远必须实时截获并冒充转发,否则会被发现,防范措施1，使用共享的对称密钥加密DH交换；2，使用公钥加密DH交换；3，使用私钥签名DH交换；,Taher Elgamal在1984和1985年间提出了一种基于离散对数问题的公钥密码体系，其类似于Diffie-Hellman的密钥协商协议。,10.2 ElGamal密码体系,2017/12/24,14,2017/12/24,15,ElGamal举例-加密,Alice选择XA=5； 计算 Alice的私钥为5；公钥为 假如Bob想将值M=17发送，则作如下计算： (1) Bob选择 k = 6 (2) 计算 (3) 计算 Bob发送密文（11, 5）,ElGamal举例-解密,Alice选择 在GF(19) 中 计算,安全性,对于给定的参数，破解ElGamal相当于解Diffie-Hellman问题。实际上，ElGamal可以被看成是Diffie-Hellman密钥的一种变形，基于这个原因，ElGamal的安全性依赖于Zp*上的离散对数问题;在加密过程中，对不同的消息m都应选取不同的随机数k，否则的话，攻击者可以很容易攻击ElGamal公钥体系。,攻击举例-k,如果k用于多个分块，利用信息的分块m1，攻击者计算,于是,若M1已知，很容易计算M2,2017/12/24,20,10.3 椭圆曲线密码学,略,2017/12/24,21,同等安全强度下密钥大小的比较,2017/12/24,22,小 结,公钥的分配 用公钥实现传统密码体制中秘密钥的分配 Diffie-Hellman密钥交换协议 ElGamal密码体系 椭圆曲线密码学（略）,2017/12/24,23,作业,习题 ：10.1 10.2,10.3 椭圆曲线密码学,在2005年2月16日，NSA宣布决定采用椭圆曲线密码的战略作为美国政府标准的一部分，用来保护敏感但不保密的信息。NSA推荐了一组被称为Suit B的算法，包括用来密钥交换的Menezes-Qu-Vanstone椭圆曲线和Diffie-Hellman椭圆曲线，用来数字签名的椭圆曲线数字签名算法。这一组中也包括AES和SHA。,椭圆曲线密码介绍,1985年Miller,Koblitz 独立提出y2+axy+by=x3+cx2+dx+e曲线上的点连同无穷远点O的集合(定义见下页）运算定义：若曲线三点在一条直线上,则其和为OO用作加法的单位：O = -O; P+O = P一条竖直线交X轴两点P1、P2，则P1+P2+O=O，于是P1 = -P2如果两个点Q和R的X轴不同，则画一连线，得到第三点P1，则Q+R+P1=O，即Q+R=-P12倍，一个点Q的两倍是，找到它的切线与曲线的另一个交点S，于是Q+Q=2Q=-S,(1) 无穷远元素（无穷远点，无穷远直线） 平面上任意两相异直线的位置关系有相交和平行两种。引入无穷远点，是两种不同关系统一。 ABL1， L2L1，直线AP由AB起绕A点依逆时针方向转动，P为AP与L1的交点。,L2,L1,P,B,A,P,Q,Q=BAP /2 AP L2可设想L1上有一点P，它为L2和L1的交点，称之为无穷远点。直线L1上的无穷远点只能有一个。（因为过A点只能有一条平行于L1的直线L2，而两直线的交点只能有一个。）结论：1*. 平面上一组相互平行的直线，有公共的无穷远点。（为与无穷远点相区别，把原来平面上的点叫做平常点）2* .平面上任何相交的两直线L1,L2有不同的无穷远点。原因：若否，则L1和L2有公共的无穷远点P，则过两相异点A和P 有相异两直线，与公理相矛盾。,椭圆曲线密码示意图,有限域上椭圆曲线,有限域上椭圆曲线y2x3+ax+b mod p p是奇素数,且4a3+27b20 mod p针对所有的0= x p，可以求出有效的y，得到曲线上的点(x,y)，其中x,y p。记为Ep(a,b)Ep(a,b)中也包括O加法公式:P+O=P如果P=(x,y)，则P+(x,-y)=O，(x,-y)点是P的负点，记为-P。而且(x,-y)也在Ep(a,b)中如果P=(x1,y1)，Q=(x2,y2)，则 P+Q=(x3,y3)为x3=2-x1-x2 (mod p)y3=(x1-x3)-y1 (mod p)其中，如果PQ，则 = (y2-y1)/(x2-x1) 如果P=Q，则 = (3x12+a)/(2y1),椭圆曲线用于加密,找到一个难题：考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的选择Ep(a,b)的元素G,使得G的阶n是一个大素数G的阶是指满足nG=O的最小n值秘密选择整数r，计算P=rG，然后公开(p,a,b,G,P)，P为公钥保密r加密M：先把消息M变换成为Ep(a,b)中一个点Pm然后，选择随机数k，计算密文Cm=kG,Pm+kP)如果k使得kG或者kP为O，则要重新选择k.解密Cm: (Pm+kP)-r(kG)=Pm+krG-rkG=Pm加密信息有扩张,椭圆曲线密码的安全性,难点: 从P和kP