第4章公开密钥密码1115.ppt

第4章 公开密钥密码 4.1 公钥密码概述 公开密钥算法中用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内），所以加密密钥能够公开，每个人都能用加密密钥加密信息，但只有解密密钥的拥有者才能解密信息。 在公开密钥算法系统中，加密密钥叫做公开密钥（简称公钥），解密密钥叫做秘密密钥（私有密钥，简称私钥）。 公开密钥算法主要用于加密/解密、数字签名、密钥交换。 讨论议题 为什么要设计公钥密码算法 密钥分配 公钥密码体制概述及其应用 公钥密码算法的实现 Diffie-Hellman密钥交换算法 背包算法 RSA算法 EIGamal算法 椭圆曲线密码算法ECC 1. 为什么要设计公钥密码体制 密钥分配（Key Distribution） 必威体育官网网址通信双方需共享密钥 共享密钥要经常更换 A选择密钥并手工传递给B 第三方C选择密钥分别手工传递给A,B 用A,B原有共享密钥传送新密钥 与A,B分别有共享密钥的第三方C传送新密钥给A和/或B N个用户集需要N(N-1)/2个共享密钥 密钥分发中心(Key Distribution Center) 密钥分发中心（KDC） 每个用户与KDC有共享密钥(Master Key) N个用户,KDC只需分发N个Master Key 两个用户间通信用会话密钥(Session Key) 用户必须信任KDC KDC能解密用户间通信的内容 起源 公钥密码又称为双钥密码和非对称密码，是1976年由Diffie和Hellman在其“密码学新方向”一文中提出的，见划时代的文献： W.Diffie and M.E.Hellman, New Directrions in Cryptography, IEEE Transaction on Information Theory, V.IT-22.No.6, Nov 1976, PP.644-654 RSA公钥算法是由Rivest,Shamir和Adleman在1978年提出来的, 见 Communitions of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126 公开密钥密码的重要特性 加密与解密由不同的密钥完成 加密: m?c: c = EK(m) 解密: c?m: m = DB(c) = DB(EK(m)) 知道加密算法,从加密密钥得到解密密钥在计算上是不可行的 两个密钥中任何一个都可以用作加密而另一个用作解密(不是必须的) m = DB(EK(m)) = EK(DB(m)) 2. 公钥密码体制的应用概述 公钥加密算法 传统加密过程 公钥加密算法 公钥密码算法 基于公开密钥的加密过程 基于公开密钥的认证过程 3. 公钥密码算法 基本思想和要求 涉及到各方：发送方、接收方、攻击者 涉及到数据：公钥、私钥、明文、密文 公钥算法的条件： 产生一对密钥是计算可行的 已知公钥和明文，产生密文是计算可行的 接收方利用私钥来解密密文是计算可行的 对于攻击者，利用公钥来推断私钥是计算不可行的 已知公钥和密文，恢复明文是计算不可行的 (可选)加密和解密的顺序可交换 一、背包问题 背包问题： 已知一长度为B的背包，及长度分别为a1,a2,...,an的n个物品。假定这些物品的半径和背包相同，若从这n个物品中选出若干个正好装满这个背包。现在反过来问：究竟是哪些物品？ 背包问题数学描述 背包问题求解 超递增序列背包问题求解方法 超递增序列背包问题求解方法 Merkle－Hellman背包公钥算法 Merkle－Hellman背包公钥算法 Merkle－Hellman背包公钥算法 问题： 如何解密？ 对公钥密码算法的误解 公开密钥算法比对称密钥密码算法更安全？ 任何一种算法都依赖于密钥长度、破译密码的工作量，从抗分析角度，没有一方更优越 公开密钥算法使对称密钥成为过时了的技术？ 公开密钥很慢，只能用在密钥管理和数字签名，对称密钥密码算法将长期存在 使用公开密钥加密，密钥分配变得非常简单？ 事实上的密钥分配既不简单，也不有效 4.2 基于大整数分解的公开密钥密码体系 一、大整数分解问题：已知整数n，n是两个素数的乘积，即n=q*p，求解p与q的值。 大整数分解是计算上的难题，目前还不存在一般性的有效解决算法。 RSA就是基于大整数分解问题的公开密钥密码体制代表算法 运算： （1）模数运算（2）模多项式运算 进一步运算:指数运算,逆运算 数论是理解公钥算法的基础 对整数 b!=0 及 a , 如果存在整数 m 使得 a=mb,称 b 整除 a, 也称b是a的因子 记作 b|a 例 1,2,3,4,6,8,12,24 整除