网络信息安全第九章.ppt

* 现代密码学理论与实践-09 */32 确定两个素数p和q，选择e或d并计算另外一个 检验素数 随机选择一个奇数，如使用伪随机数产生器 随机选一个整数a n 完成随机素数性检验，如果n没有通过检验，则另选n 如果n通过了足够多次的检验，则接受n，否则另选 例：p = 5, q = 7, n = 35, φ(n)=24 选d = 11，则e = inv(11, 24) = 11，M = 2 C = me mod n = 211 mod 35 = 18 M = Cd mod n = 1811 mod 35 = 2 密钥的产生和检验素数 * 现代密码学理论与实践-09 */32 RSA的安全性 例：p = 53，q = 61，n = pq = 3233， φ(n)＝52x60 = 3120 令d = 791，则e = 71 令m = RE NA IS SA NC E 即m = 1704 1300 0818 1800 1302 0426 170471 mod 3233 = 3106，…， C = 3106 0100 0931 2691 1984 2927 RSA的安全性 有三种可能的对RSA的攻击方法 强行攻击：尝试所有可能的密钥 数学攻击：对两个素数乘积的因子分解(FAC问题) 计时攻击：依赖于解密算法的运行时间 RSA的安全性问题依赖于大合数的素因子分解，即factorization problem (FAC)，FAC的计算复杂性为T=exp((ln(n)ln(ln(n)))1/2)， 同DLP问题。 * 现代密码学理论与实践-09 */32 p和q应满足下列约束条件： P和q的长度应仅相差几位，p和q都应约在1075到10100之间 (p-1)和(q-1)都应有一个大的素因子 GCD(p-1, q-1)应该较小 另外，已经证明，若en且dn1/4，则d很容易确定 * 现代密码学理论与实践-09 */32 针对RSA的计时攻击 计时攻击 类似通过观察他人转动保险柜拨号盘的时间长短来猜测密码 可能的解决办法 不变的幂运行时间，可能会降低性能 在求幂运算中加入随机延时 隐蔽：在执行幂运算之前先将密文乘上一个随机数 RSA数据安全算法，用私钥实现操作M=Cd mod n的过程如下 产生0－n-1之间的秘密随机数r 计算C’=C(re) mod n, e是公开的指数 计算M’=(C’)d mod n 计算M=M’r -1 mod n, 其中r -1是r模n的乘法逆元，根据 redmod n=r，可以证明结论是正确的 * 现代密码学理论与实践-09 */32 几种不同复杂性的算法的代价 * Dr. Diffie is currently a Distinguished Engineer at Sun Microsystems and Professor Hellman is a Professor Emeritus of Electrical Engineering at Stanford University British Intelligent agency also discovered public key cryptography in early 1970’s, due to confidential reason, their work was no known to public until 1990’s. * Rivest: professor in MIT Shamir: a founder of a security company in Isreal Adleman: a professor in USC 现代密码学理论与实践-09 现代密码学理论与实践-09 * 现代密码学理论与实践-09 */32 网络信息安全 Chapter 9 Public-key Cryptography and RSA * 现代密码学理论与实践-09 */32 本章要点 非对称密码是一种密码体制，其加密算法和解密算法使用不同的密钥，一个是公钥，一个是私钥。非对称密码也称为公钥密码。 非对称密码用两个密钥中的一个以及加密算法将明文转换为密文，用另一个密钥以及解密算法从密文恢复出明文。 非对称密码可以用来必威体育官网网址、认证或者两者兼而有之。 应用最广泛的公钥密码体制是RSA，破解RSA的困难，是基于分解大合数的素因子的困难。 * 现代密码学理论与实践-09 */32 9.1 公开密钥密码体制的基本原理 对称密码体制的问题 加密能力与解密能力是捆绑在一起的 密钥更换、传递和交换需要可靠信道，密钥分发困难 如有N用户，则需要C=N (N-1)/