Ch9 公钥密码学与RSA.ppt

西安电子科技大学计算机学院 Chapter 9  公钥密码学与RSA 对称密码 只使用一个密钥 收发双方共享这个单一的密钥 密钥是对称的，双方是对等的 对称密码的不足 密钥管理问题 传统密钥管理：两两分别用一个密钥时，则n个用户需要C(n,2)=n(n-1)/2个密钥，当用户量增大时，密钥空间急剧增大。 密钥分配问题 密钥必须通过某一信道协商，对这个信道的安全性的要求比正常的传送消息的信道的安全性要高。 数字签名的问题 传统加密算法无法实现抗伪造和抵赖的需求 公钥密码的起源 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 Rivest, Shamir和Adleman在1978年提出RSA公钥算法 A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM. Vol.21.No.2. Feb. 1978, PP.120-126 James Ellis (UK CESG) 在1970年曾提出此概念 公钥密码体制 密码学发展历史中最伟大的一次革命 公钥/双钥/非对称密码都是指使用两个密钥： 公钥：可以公开的密钥，用于加密消息或验证签名 私钥：只能由接收者私存，用于解密消息或签名 两个密钥配对使用 公钥加密信息，私钥解密信息 私钥签名信息，公钥验证签名 参与方不对等，所以是非对称的 基于数学函数而非基于替换和置换 公钥密码体制的特点 公钥算法依赖于一个加密密钥和一个与之相关的不同的解密密钥，算法具有如下特点： 仅根据密码算法和加密密钥来确定解密密钥在计算上是不可行的。 有些算法（如RSA）还具有如下特点： 两个密钥中的任何一个都可用来加密，另一个用来解密。 对称密码和公钥密码 公钥密码体制：加密 加密： Y=EKUb(X) X=DKRb(Y) 公钥密码体制：认证 认证： Y=EKRa(X) X=DKUa(Y) 公钥密码体制：加密和认证 Z=EKUb [ EKRa(X) ] X=DKUa [ EKRb(Z) ] 公钥密码体制的应用 分为三类: 加密/解密 (提供必威体育官网网址性) 数字签名 (提供认证) 密钥交换 (会话密钥) 一些算法可用于上述三类，而有些只适用于其中一类或两类。 对公钥密码的要求 公钥密码算法依赖于: 仅仅知道算法和加密密钥，推导解密密钥计算上是不可行的 已知加解密密钥时，进行加解密运算计算上是容易的 对公钥密码的要求：书P189的6个条件 满足条件的算法中只有RSA和椭圆曲线密码体制为人们普遍接受 单向陷门函数 寻找合适的单向陷门函数是公钥密码体制应用的关键 单向陷门函数： 若k和X已知，则容易计算 Y = fk(X). 若k和Y已知，则容易计算X = fk-1(Y). 若Y已知但k未知，则计算出X = fk-1(Y)是不可行的. 单向陷门函数举例： 离散对数 大整数分解 背包问题 公开密钥密码分析 穷举攻击 解决方法：长密钥 ； 但加密/解密速度太慢 公开密钥加密应用： 密钥管理和数字签名 找到根据公钥计算私钥的方法 尚未在数学上证明对一特定公钥算法（包括RSA）该攻击方法不可行 穷举消息攻击 对要发送的消息附加随机数 常见的公钥密码算法 背包算法 McEliece算法 RSA算法 Rabin(RSA的变种算法) 基于离散对数难题的ElGamal算法 必威体育精装版的椭圆曲线算法 §9.2 RSA 1977年提出，1978年首次发表 自诞生日起就成为被广泛接受且被实现的通用公钥加密方法 是一种分组密码 安全性基于大数的素因子分解的困难性 补充：模运算（第4章） 设a是整数，n是正整数，定义a除以n所得的余数为a mod n，整数n称为模数。 如：11 mod 7＝4 如果(a mod n)=(b mod n)，则称两整数a和b模n同余，记为a≡b mod n 如：73 ≡4 mod 23 素数（第8章） 因子： 若a＝mb，其中a、m、b为整数，b≠0，则b是a的一个因子 最大公因子： 两个整数a、b的最大公因子记为c=gcd(a, b)，条件： ① c是a的因子也是b 的因子，即c是a、b的公因子 ② a和b的任一公因子，也是