信息安全导论密码基础非对称密码.ppt

1 密码基础 非对称密码 又称公钥密码 信息安全导论 模块4 密码基础 2 对称密码体制使用中存在的问题 密钥分配问题 通信双方要进行加密通信 需要通过秘密的安全信道协商加密密钥 而这种安全信道可能很难实现密钥管理问题 在有多个用户的网络中 任何两个用户之间都需要有共享的秘密钥 当网络中的用户n很大时 需要管理的密钥数目非常大n n 1 2 3 对称加密示意图 注意 注意 4 公钥密码体制 1976年 W Diffie和M E Hellman发表了 密码学的新方向 一文 提出了公钥密码学 Public keycryptography 的思想 在公钥密码体制 Public keycryptosystem 中加密密钥和解密密钥是不同的 加密密钥可以公开传播而不会危及密码体制的安全性 通信的一方利用某种数学方法可以产生一个密钥对 一个称为公钥 Public key 另外一个称为私钥 Private key 该密钥对中的公钥与私钥是不同的 但又是相互对应的 并且由公钥不能推导出对应的私钥 选择某种算法 可以公开 能做到 用公钥加密的数据只有使用与该公钥配对的私钥才能解密 5 公钥密码体制 公钥密码体制 非对称 包括两个密钥 公钥 可以被任何人知道 用于加密私钥 只有消息的接收者知道 用于解密加密者或其他人不能解密从公钥无法导出私钥是密码学几千年历史中最有意义的结果 6 公钥密码的特点由私钥及其他密码信息容易计算出公开密钥由公钥及算法描述 计算私钥是困难的因此 公钥可以发布给其他人 7 注意 注意 非对称加密示意图 8 公钥密码的核心是使用一种特殊的函数 单项陷门函数 从一个方向求值是容易的 但逆向计算很困难定义 设f是一个函数 如果对于任意给定的x 计算y 使得y f x 是容易计算的 但对于任意给定的y 计算x是难解的 即求f的逆函数是难解的 则称f是一个单向函数 9 定义 设f是一个函数 t是与f有关的一个参数 对于任意给定的x 计算y 使得y f x 是容易的 如果当不知道参数t时 计算f的逆函数是难解的但当知道参数t时 计算f的逆函数是容易的则称f是一个单向陷门函数 参数t称为陷门 10 公钥密码中 加密函数就是一个单向陷门函数 只有解密者知道陷门 可以容易地进行解密 而不知道陷门的人则无法有效解密 11 典型的公钥密码算法1 背包算法 背包系统是1978年Merkle和Hellman基于求解背包问题的难解性提出的一个公钥密码系统背包问题 12 13 14 例 15 16 加解密运算 17 18 例 19 20 发送方 加密 21 接收方 解密 22 典型的公钥密码算法2 RSA RSA是Rivest Shamire和Adleman于1978年在美国麻省理工学院研制的其安全性建立在 大数分解和素性检测 这一数论难题基础上将两个大素数相乘是容易计算的将该乘积分解成两个大素数因子是困难的 计算上不可行 23 1 密钥的产生 选两个互异的大素数p和q 计算n p q n p 1 q 1 其中 n 是n的欧拉函数值 选一整数e 满足1 e n 且gcd n e 1 计算d 满足d e 1mod n 即d是e在模 n 下的乘法逆元 因e与 n 互素 由模运算可知 它的乘法逆元一定存在 以 e n 为公开钥 d p q 为秘密钥 RSA算法 24 2 加密加密时首先将明文比特串分组 使得每个分组对应的十进制数小于n 即分组长度小于log2n 然后对每个明文m 作加密运算 c memodn RSA算法 25 3 解密对密文分组的解密运算为 m cdmodn证明RSA算法中解密过程的正确性 证明过程用到数论中的知识cdmodn medmodn m RSA算法 26 例 选p 7 q 17 求得n p q 119 n p 1 q 1 96 取e 5 满足1 e n 且gcd n e 1 计算满足d e 1mod96且小于96的d 因为77 5 385 4 96 1 所以d为77 因此公开钥为 5 119 秘密钥为 77 7 17 设明文m 19 则由加密过程得密文为c 195mod119 2476099mod119 66 解密过程为m 6677mod119 19 RSA算法 27 1 RSA的加密与解密过程RSA的加密 解密过程都为求一个整数的整数次幂 再取模 如果按其含义直接计算 则中间结果非常大 有可能超出计算机所允许的整数取值范围 如上例中解密运算6677mod119 先求6677再取模 则中间结果就已远远超出了计算机允许的整数取值范围 而用模运算的性质 a b modn amodn bmodn modn就可减小中间结果 RSA中的计算问题 28 2 模指数运算的快速算法例如求x16 直接计算的话需做15次乘法 然而如果重复对每个部分结果做平方运算即求x x2 x4 x8 x16则只需4次乘法 求am可如下进行 其中a m是正整数 将m表示为二进制形式bkbk 1 b0 即m bk2k bk 12k 1 b12 b0因此 RSA中的计算问题 29 例 求a1919 1 24 0 23 0 22 1 21 1 20所以a19 a1 2a0 2a0 2a1 2a1 RSA中的计算问题 30 3 乘法逆元的求法 欧几里德算法 整数e 满足1 e n 且gcd n e 1计算d 满足d e 1mod n 即d是e在模 n 下的乘法逆元 因e与 n 互素 它的乘法逆元一定存在 RSA中的计算问题 31 RSA中的计算问题 32 RSA中的计算问题 33 RSA中的计算问题 34 前例 则1 96 5 19 5 19 5 77mod96 5 77 1mod96 则5的乘法逆元在mod96下为77 35 例 36 37 验证 17 17 289 3 96 1 1mod96 38 RSA的安全性是基于分解大整数困难的假定如果RSA的模数n被成功地分解为p q 则获得 n p 1 q 1 从而攻击者能够从公钥e解出d 即d e 1mod n 攻击成功 RSA算法的安全性 39 随着人类计算能力的不断提高 原来被认为是不可能分解的大数已被成功分解 例如RSA 129 即n为129位十进制数 大约428个比特 已在网络上通过分布式计算历时8个月于1994年4月被成功分解 RSA 130已于1996年4月被成功分解 RSA算法的安全性 40 商用安全要求n的长度在1024 2048比特p和q的长度相差不能太多p 1和q 1都应该包含大的素数因子p 1和q 1的最大公因子要尽可能小 41 典型的公钥密码算法3 ElGamal算法 ElGamal公钥密码体制是由T ElGamal于1985年提出的可用于数据加密 也可用于数字签名安全性依赖于有限域上计算离散对数的难题 42 ElGamal算法 43 特点 44 安全性分析 其安全性是建立在有限域上求离散对数难解问题的基础上有限域上的离散对数问题 45 46 ElGamal中参数选择的安全性要求 素数p至少应为150位以上的十进制数p 1至少应该有一个大的素数因子 47 公钥密码的特点 计算量大 运算速度慢主要用于密钥协商数据加密主要用对称密码 48 对称密码算法 加 解密速度快 但密钥分发问题严重非对称密码算法 加 解密速度较慢 但密钥分发问题易于解决为解决每次传送更换密钥的问题 结合对称加密技术和非对称密钥加密技术的优点 产生了电子信封技术 用来传输数据 49 加密技术的使用 50 小结 典型的非对称密码 RSA 对称密码 非对称密码各自特点如何用 51 作业 背包算法的练习 n 8 两位同学一组 班内序号 1 2 3 4 班内序号为奇数的同学 每人设计一个背包公钥密码系统 给出公开钥 保留秘密钥班内序号为偶数的同学 每人用你同伴的公开钥加密一个明文信息 将密文交给该同学 由该同学解密每组同学提交一个算法报告 算法的设计过程 公开钥 秘密钥 明文 密文 加解密运算过程等 52 作业 RSA算法的练习 选择两个大于30的素数p q 两位同学一组