第3讲公钥密码学

1、网络与信息安全技术网络与信息安全技术第三讲第三讲公钥密码公钥密码华中科技大学软件工程硕士课程华中科技大学软件工程硕士课程公钥密码学的历史 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,49

2、7,500 对传输信道安全性的要求！ 密钥必须通过某一信道协商传输，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高 数字签名问题！ 传统加密算法无法实现抗抵赖的需求公钥体制加密的框图公钥体制认证的框图公钥体制认证保密的框图公钥密码基于的数学难题 背包问题 大整数分解问题 ( RSA体制 ) 离散对数问题 有限域的乘法群上的离散对数问题 (ElGamal体制) 定义在有限域的椭圆曲线上的离散对数问题 (类比的ElGamal体制)公钥密码主要算法 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECCDiffie-Hellman密钥交

3、换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 解密:

4、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因此120

5、12222kkkbbbbbmaaaaaa 例: 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

6、, 并计算满足de1 mod (n)的d, 可由推广的Euclid算法完成.大素数产生 素数生成过程: 随机选择一个奇数n(如通过伪随机数发生器) 随机选择a, 使ad Euclid（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

7、(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

8、 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-16

9、45415-1645-9292951-9292914-45166114-4516-23741371-23741337-11938437-1193-1715501 椭圆曲线密码体制ECCy2=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所需的密钥量远比基于有限域上