第3讲公钥密码学资料课件

网络与信息安全技术网络与信息安全技术第三讲第三讲公钥密码公钥密码华中科技大学软件工程硕士课程华中科技大学软件工程硕士课程公钥密码学的历史76年Diffie和Hellman发表了“密码学的新方向”,奠定了公钥密码学的基础公钥技术是二十世纪最伟大的思想之一 改变了密钥分发的方式广泛用于数字签名和身份认证服务78年,RSA算法 对称算法的不足密钥管理量的困难！传统密钥管理:两两分别用一个密钥时,则n个用户需要C(n,2)=n(n-1)/2个密钥,当用户量增大时,密钥空间急剧增大,如:n=100 时,C(100,2)=4,995 n=5000时,C(5000,2)=12,497,500对传输信道安全性的要求！密钥必须通过某一信道协商传输，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高数字签名问题！传统加密算法无法实现抗抵赖的需求 公钥体制加密的框图 公钥体制认证的框图 公钥体制认证保密的框图 公钥密码基于的数学难题 背包问题 大整数分解问题(RSA体制)离散对数问题有限域的乘法群上的离散对数问题 (ElGamal体制)定义在有限域的椭圆曲线上的离散对数问题 (类比的ElGamal体制)公钥密码主要算法Diffie-Hellman密钥交换算法背包算法RSA算法EIGamal算法 椭圆曲线密码算法ECC Diffie-Hellman密钥交换RSA算法 1977年由Ron Rivest、Adi Shamir和Len Adleman发明,1978年公布;是一种分组加密算法;明文和密文在0n-1之间,n是一个正整数 应用最广泛的公钥密码算法;只在美国申请专利,且已于2000年9月到期;RSA算法 RSA密钥生成与使用产生密钥对选择两个大素数p,q,pq计算n=pq,(n)=(p-1)(q-1)选择整数e,使得gcd(e,(n)=1计算d e-1 mod(n)公钥:KU=e,n,私钥:KR=d,n使用:将明文划分成块,使得每个明文报文P长度m满足0mn加密:C=me mod n解密:m=Cd mod nRSA算法中的计算问题 如何计算ab mod n 密钥产生 如何计算ab mod n 中间结果非常大6677 mod 119,先求6677再取模,则中间结果就已远远超出了计算机允许的整数取值范围(a x b)mod n=(a mod n)x(b mod n)mod n 幂运算的效率求x16,直接计算的话需做15次乘法.然而如果重复对每个部分结果做平方运算即求x,x2,x4,x8,x16则只需4次乘法。求am可如下进行,其中a，m是正整数：将m表示为二进制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此例:19=124+023+022+121+120，所以a19=(a1)2a0)2a0)2a1)2a1从而可得以下快速指数算法：c=0;d=1；for i=k downto 0 d0 c=2c;d=(dd)mod n;if bi=1 then c=c+1;d=(da)mod nreturn d.d是中间结果,d的终值即为所求结果.c在这里的作用是表示指数的部分结果,其终值即为指数m c对计算结果无任何贡献,算法中完全可将之去掉密钥产生 如何找到足够大的素数p和q?选择e或d计算另外一个?选取满足1e(n)和gcd(n),e)=1的e,并计算满足de1 mod(n)的d,可由推广的Euclid算法完成.大素数产生素数生成过程:随机选择一个奇数n(如通过伪随机数发生器)随机选择a,使adEuclid（f,d）1.Xf;Yd；2.if Y=0 then return X=gcd(f,d)；3.R=X mod Y；4.X=Y；5.Y=R；6.goto 2。例4.2 求gcd(1970,1066)。1970=11066+904,gcd(1066,904)1066=1904+162,gcd(904,162)904=5162+94,gcd(162,94)162=194+68,gcd(94,68)94=168+26,gcd(68,26)68=226+16,gcd(26,16)26=116+10,gcd(16,10)16=110+6,gcd(10,6)10=16+4,gcd(6,4)6=14+2,gcd(4,2)4=22+0,gcd(2,0)因此gcd(1970,1066)=2。扩展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)的整数部分 (Y1,Y2,Y3)(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 例 求gcd(1769,550)。所以gcd(1769,550)=1，550-1 mod 1769=550。循环次数QX1X2X3Y1Y2Y3初值-1017690155013015501-3119241-3119-4137431-413745-1645415-1645-9292951-9292914-45166114-4516-23741371-23741337-11938437-1193-1715501 椭圆曲线密码体制ECC y2=x3+ax+b mod p 椭圆曲线(con.)引进一个0元素,并定义如下的加法运算:引进一个无穷点0(,)作为0元素 任何解点R(x,y)的逆就是R(x,-y)设P(x1,y1)和Q(x2,y2)是椭圆曲线上的两个点,则连接P(x1,y1)和Q(x2,y2)的直线与椭圆曲线的另一交点关于横轴的对称点即为 P(x1,y1)+Q(x2,y2)点 椭圆曲线上的离散对数问题椭圆曲线群上的离散对数问题考虑等式Q=kP，其中Q、P属于Ep(a,b)，kp已知k和P，计算Q，是容易的已知Q和P，计算k，是困难的 椭圆曲线密码体制的优点安全性高运算复杂度更高,因此椭圆曲线密码体制比基于有限域上的离散对数问题的公钥体制更安全.密钥量小在实现相同的安全性能条件下,ECC所需的密钥量远比基于有限域上的离散对数问题的公钥体制的密钥量小灵活性好GF(q)上的椭圆曲线可以通过更改曲线参数,得到不同的曲线,形成不同的循环群.因此椭圆曲线具有丰富的群结构和多选择性 ECC和RSA/DSA同等安全条件下的密钥长度RSA/DSA5127681024204821000ECC106132160211600人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。