信息安全基础5.ppt

5 公开密钥算法 概述 RSA算法 其他公开密钥算法 公开密钥数字签名算法 身份验证体制 密钥交换算法 5.1 概述 成对密钥的思想：一个加密密钥和一个解密密钥，而从其中一个密钥推导出另外一个是不能的。 混合密码系统：对称算法用于加密消息，公开密钥算法用于加密密钥。 5.2 RSA算法 第一个成熟的公开密钥算法，可以用作加密和数字签名 算法描述： RSA的安全性基于大整数的因数分解的困难性 首先随机选择两个大素数p和q，计算n = pq 然后随机选择加密密钥e，满足e与(p-1)(q-1)互素。用扩展的Euclid算法计算解密密钥d，使得ed ? 1 mod (p-1)(q-1) 公开密钥：e和n 秘密密钥：d 加密：C = Me mod n 解密：M = Cd mod n 例：已知 n=3337, e=79， M=6882326879666683 求 C=？ 解：n=pq=3337=47*71 p=47 q=71 (p-1)(q-1)=46*70=3220 d=e-1 mod 3220= 79-1 mod 3220=1019 将明文3位一组，m1=688, m2=232, m3=687, m4=966, m5=668, m6=003 加密： c1= m1e mod n=68879 mod 3337=1570 同理： c2=2756， c3=2091， c4=2276， c5=2423， c6=158 C=15702756209122762423158 解密 ： m1= c1d mod n=mod 3337=688 RSA算法用于数字签名：(见148页 7.1.6) 数字签名：手写签名来证明文件的原作者，或至少证明签名者同意文件的内容 签名的特性： 可信性：文件的接收者应该相信签名者慎重签署了该文件； 不可伪造性：能够证明是签名者本人，而不是别人慎重签署了该文件； 不可重用性：签名应该作为文件的一部分，任何人不能将该签名移动到别的文件上去； 不可更改性：任何人不能对签名后的文件内容进行更改； 不可否认性：签名及文件是客观存在的，签名者不能事后否认他签署过该文件。 RSA签名： S = Md mod n M:要签名的消息 验证签名： M = Se mod n e:公开密钥 d:秘密密钥 5.3 ElGamal公开密钥算法 ElGamal：安全性基于有限域内计算离散对数的困难性。 数字签名 加密 ElGamal 产生密钥： 一个素数p和两个随机数g，x，使g和x都小于p。 计算y = gx mod p 公开密钥：y, g和p，g和p由一群用户共享 秘密密钥：x ElGamal签名 产生签名： 选择一个随机数k，使k与p-1互素。 计算a = gk mod p 用扩展的Euclid算法求b，使M = (xa+kb) mod (p-1) 数字签名为a和b，k要保密。 验证签名：确认是否有yaab mod p = gM mod p 例：选择p=11,g=2,秘密密钥x=8,M=5 则 y=gx mod p=28 mod 11=3 公开密钥为：y=3,g=2,p=11 产生签名：选择一个随机数k=9 gcd(k,p-1)=gcd(9,10)=1 互素 计算：a=gk mod p=29 mod 11=6 用扩展Euclid算法求b: M=(xa+kb) mod (p-1) 5=(6*8+9b) mod 10 5=8+9b mod 10 7=9b mod 10 b=7*9-1 mod 10=7*9 mod 10=3 签名为：a=6,b=3 验证签名： 确认yaab mod p=gM mod p是否相等 yaab mod p= 3663 mod 11=10 gM mod p=25 mod 11=10 等式成立 ElGamal加密 加密M： 选择随机数k，使k与p-1互素 计算a = gk mod p, b = ykM mod p, a和b为密文 解密：计算M = b/ax mod