计算机安全%20%20公钥密码体系ppt课件.ppt

公钥密码体系 计算机安全与保密 对称算法的不足 密钥必须通过某一信道协商 对这个信道的安全性的要求比正常的传送消息的信道的安全性要高 公钥密码背景 公钥密码体制的特点 加密密钥与解密密钥在本质上是不同的 即已知一个密钥并不能轻易地求出另一个密钥 不需要增加分发密钥的额外信道 公钥密码体制的要求 产生一对密钥是计算可行的已知公钥和明文 产生密文是计算可行的接收方利用私钥来解密密文是计算可行的对于攻击者 利用公钥来推断私钥是计算不可行的已知公钥和密文 恢复明文是计算不可行的 可选 加密和解密的顺序可交换 公钥密码的安全性依赖于从已知的公钥 加密算法和密文中无法求出明文或秘钥 Diffie和Hellman提出了一种陷门单向函数概念 为建立公钥密码体制找到了一种途径 单向函数 函数f若满足下列条件 对任意给定的x 容易计算f X y 对任意给定的y 求出x使得f x y是困难的 求离散对数问题y gxmodp若给出p g y求x称为求离散对数问题因子分解问题n pq若给定n 求p q称为因子分解问题背包问题给定一个有限个自然数序列集合B b1 b2 bn 及二进制数序列x x1 x2 xn S x1b1 x2b2 xnbn给定B S 求x序列 称为求背包问题 单向陷门函数 单向陷门函数是满足下列条件的函数f 给定x 计算y f x 是容易的 给定y 计算x使x f 1 y 是不可行的 存在陷门t 已知t时 对给定的任何y 若相应的原象x存在 则计算x是容易的 通过陷门单向函数建立公钥密码 f x 是单向陷门函数 陷门为t 那么设计公钥密码系统时f x 作为公钥 陷门t作为私钥 任何人都可将明文m利用公钥f x 加密得到密文y f m 而任何人不知道私钥即陷门 由密文y都无法求出m 因为f x 是单向的 但拥有私钥 便可容易求出m RSA公钥密码体制 1 1977年由Rivest Shamir和Adleman发明并于1978年公布 2 明文和密文在0 n 1之间 n是一个正整数3 应用最广泛的公钥密码算法4 只在美国申请专利 且已于2000年9月到期 欧拉函数 欧拉函数 欧拉函数 欧拉函数 欧拉函数 RSA密码体制的描述密钥生成算法 每个用户执行以下操作随机生成两个不同大素数p q 计算n pq n p 1 q 1 随机选取整数e 1 e n 满足 e n 1 利用扩展欧基里德算法求出满足ed 1mod n 的整数d 公开 n e 保密 p q n d 其中e就是加密密钥 而d就是解密密钥 n称为模数 例如取p 7 q 17 则n pq 7 17 119 n 7 1 17 1 6 16 96任取e 5 则d 77 注意5 77 385 1mod96 RSA加解密 若B要利用A的公钥进行加密 则B执行获得A可信的公钥 n e 把消息按分组的方式表示为区间 0 n 1 之间的整数m 计算c Ee m memodn 将密文c发送给A 解密 为从c中恢复明文m A利用解密密钥d 计算m cdmodn 例如在上面的例子中 假设m 19 则c 195 19 192 2 19 3612 19 42mod119 304 66mod119因此密文为c 66 对于密文c 66 其解密过程如下m 6677 662 38 66mod119 7238 66mod119 4738 66mod119 6719 66mod119 672 9 67 66mod119 869 19mod119 862 4 86 19mod119 184 87mod119 18 87mod119 19mod119 解密的正确性 费马小定理 若 a n 1 则a n 1modn推论1 若n pq p q都是素数 k是任意整数 则m n 1 m p 1 q 1 1 mmodn推论 mk p 1 q 1 1 mmodn由于ed 1mod n 则存在整数k 满足ed 1 k n 1 k p 1 q 1 因此cd med mk p 1 q 1 1 mmodn所以解密成功 加密函数E x xemodn是一个单向函数 所以对攻击的人来说求逆计算不可行 而A能解密的陷门是由分解n pq 知 n p 1 q 1 从而用欧氏算法解出解密私钥d 所以如果能够分解n 那么就可以完成解密 RSA体制的陷门单向函数 RSA的安全性 RSA的安全性是基于大整数的因子分解的困难性猜想 攻破RSA与分解n是多项式等价的 然而 这个猜想至今没有给出可信的证明 素因子p q应当是强素数 p是强素数 存在大素数p1 p1 p 1 同时r1 r2是大素数 r1 p1 1 r2 p1 1 选择强素数的目的是因为选择的p q如果p 1 q 1的素因子都很小 则n pq存在p 1或p 1分解法 2 因子p q的差必须足够大 如果p q比较接近 则由p q的平均值可得 再利用 可得 进而求出p q 的加解密密钥不能太小 存在低指数攻击已经证明了当d的二进制长度小于模数n长度的1 4时 可以利用连分数法在多项式时间内求解n 如果解密指数d被泄露 则就可以分解出n 因此就必须重新选取n 而不能只是重新选取e d RSA的实现 可供选择的大素数是否多随机选择大素数是否容易模幂运算能否快速实现 模幂运算 模幂运算 模幂运算 平方和乘算法 平方和乘算法的复杂度 执行次数至少要k次模乘 最多需要 次模乘 素数分布 素数判定 确定性素数判定 判定结果一定正确概率性素数判定 判定结果在某个概率上是正确的 概率性素数判定算法内部使用了一个随机数 在复杂度理论中也称此类算法为随机算法 Miller Rabin素数判定算法 强伪素数判定算法 输入n b输出n是以b为其的强伪素数 输出true 否则输出false Miller Rabin素数判定算法 Prime test n b rand iftest n b falsereturnfalse 输出n不是素数returntrue 输出n是素数 Miller Rabin素数判定算法正确概率 Miller Rabi