[理学]04、公钥密码体制.ppt

4.5 ElGamal加密算法 ElGamal加密算法例： 例：设P = 2579，r = 2，a = 765，s = 2765 mod 2579 = 949 若Alice想传递消息x = 1299给Bob Alice首先选择一个随机数k，设k = 853 计算y1 = 2853 mod 2579 = 435 y2 = 1299 * 949853 mod 2579 = 2396 当Bob收到密文y＝(435，2396)后，计算 x=2396 * (435765 )-1mod 2579 ＝1299 4.6 小结 小结： 公钥算法的思想。 Diffie-Hellman密钥协商协议 RSA算法的数学原理。 基础：IFP(Integer Factorization Problem) 加/解密、密钥交换、数字签名 使用最广泛 ElGamal 基础: DLP(Discrete Logarithm Problem) 加/解密、密钥交换、数字签名 4.6 小结 公钥算法和对称钥算法区别(1) ： 对称加密的优点 速度快，处理量大，适用于对应用数据的直接加密。 加密密钥长度相对较短,如40比特～256比特。 可构造各种加密体制，如产生伪随机数，HASH函数等。 对称加密的缺点 密钥在双方都要一致、必威体育官网网址，传递较难。 大型网络中密钥量大，难以管理，一般需要TTP（KDC）。 密钥需要经常更换。 4.6 小结 公钥算法和对称钥算法区别(1) ： 公钥加密的优点 只有秘密钥必威体育官网网址，公开钥公开。 密钥生命周期相对较长。 许多公钥方案可以产生数字签名机制。 在大型网络上，所需的密钥相对较少。 公钥加密的缺点 速度慢，处理量少，适用于密钥交换。 密钥长度相对较长。 安全性没有得到理论证明。 4.6 小结 误区： 公开密钥密码算法更安全： 安全程度基于密钥长度和计算工作量。二者并不比对方优越。公开钥算法天生具有更大的危险性。 公钥的分发是简单和一目了然的。 对称密钥算法密钥分配是比较复杂，但是公开钥算法存在如何保证一个问题，即如何确认一个公开钥与其拥有者的对应问题。 公开密钥密码使对称密钥密码过时了 公开钥算法因速度问题更适合密钥交换。 实际应用是公开钥算法和对称钥算法的结合。 公钥算法用于签名和认证； 用公钥算法传输会话密钥； 用会话密钥/对称算法加密批量(bulk)数据 4.2.2 Diffie-Hellman算法 Diffie-Hellman算法例： 密钥交换基于素数q = 97和97的一个原根，在这里是a = 5。A和B分别选择秘密密钥Xa = 36和Xb = 58。每人计算其公开密钥如下： Ya = 536 = 50 mod 97 Yb = 558 = 44 mod 97 在他们交换了公开密钥以后，每人计算共享的秘密密钥如下： A : K = (Yb)Xa mod 97 = 4436 = 75 mod 97 B : K = (Ya)Xb mod 97 = 5058 = 75 mod 97 从{50，44}出发，攻击者要计算出75很不容易 4.2.2 Diffie-Hellman算法 Diffie-Hellman密钥交换的攻击： 中间人攻击 1 双方选择素数p以及p的一个原根a(假定O知道) 2 A选择Xap，计算Ya=aXa mod p，A?B: Ya 3 O截获Ya，选Xo,计算Yo=aXo mod p，冒充A?B:Yo 4 B选择Xbp，计算Yb=aXb mod p，B?A: Yb 5 O截获Yb,冒充B?A:Yo 6 A计算: (Yo)Xa ? (aXo)Xa ? aXoXa mod p 7 B计算: (Yo)Xb ? (aXo)Xb ? aXoXb mod p 8 O计算: (Ya)Xo?aXaXo mod p, (Yb)Xo?aXbXo mod p O无法计算出aXaXb mod p ，O永远必须实时截获并冒充转发 4.2.2 Diffie-Hellman算法 Diffie-Hellman密钥交换的攻击： 中间人攻击图示 A B K = aXaXo O K = aXbXo 4.3 背包算法 背包问题： 背包问题描述：给定重量分别为a1，a2，…，an的n个物品，装入一个背包中，要求重量等于一个给定值，那么究竟是那些物品？ 0-1背包问题： 给定一个正整数S和一个背包向量A=(a1,…,an)，其中ai是正整数，求满足方程S = ∑aixi的二进制向量X = (x1,…,xn)。 4.3 背包算法 背包问题用于公钥密码学： 做法：明文为X，S为密文 奥妙在于有两类背包，一类可以在线性时间内求解，另一类则不能 把易解的背包问题修改成难解的背包问题 公开密钥使用难解的背包问题 私钥使用易解的背包问题 4.3 背包算法 易