信息安全导论课程-ch09-公钥密码学和RSA.ppt

* 一般用于传输会话密钥（和签名及鉴别） R、A、S 事实上，p q和私钥一起保留可以加快运算速度。（借助中国剩余定理） （不互素时仍成立） 97221 % 2003 = 1363 /rsalabs/challenges/ /wiki/RSA_number * 部分效果 RSA Laboratories sponsors the RSA Factoring Challenge number digits prize factored (references) RSA-100 100 ? Apr. 1991 RSA-110 110 ? Apr. 1992 RSA-120 120 ? Jun. 1993 RSA-129 129 $100 Apr. 1994 (Leutwyler 1994, Cipra 1995) RSA-130 130 ? Apr.?10, 1996 RSA-140 140 ? Feb.?2, 1999 (te Riele 1999a) RSA-150 150 withdrawn? Apr.?6, 2004 (Aoki 2004) RSA-155 155 ? Aug.?22, 1999 (te Riele 1999b, Peterson 1999) RSA-160 160 ? Apr.?1, 2003 (Bahr et al. 2003) RSA-576 174 $10k Dec.?3, 2003 (Franke 2003) RSA-640 193 20k open RSA-704 212 30k open RSA-768 232 50k open RSA-896 270 75k open RSA-1024 309 100k open RSA-1536 463 150k open RSA-2048 617 200k open The RSA challenges ended in 2007 The RSA challenges ended in 2007. RSA Laboratories stated: Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active. 因子分解所需的MIPS年 抵抗因子分解 N如果有特殊结构，则较易被分解，因此： N要尽量大，当前1024位应该是安全的 P和Q应该宽度接近，比如都约512位 P-1和Q-1应该都有大的素因子，比如强素数 Pollards p ? 1 integer factorization algorithm, gcd（p-1,q-1）应该比较小 共模攻击 假如一组用户，共用一个模n （e1, n），（e2, n） 从n, e1, e2, c1=m^e1, c2=m^e2计算m 用扩展欧氏算法找 r*e1 + s*e2 = 1 [r*e1 = 1 mod e2] 则 m = c1^r * c2^s = m^e1^r*m^e2^s = m^(r*e1 + s*e2)=m 教训 不要使用同一个模 计时攻击 Timing Attacks on Implementations of DH, RSA, DSS, and Other Systems，1994，Paul C. Kocher 攻击者可以统计执 行时间得到d的比 特取值 抵抗计时攻击 计算M=Cd mod N 取随机数rN 计算C’=Cre mod N 计算M’=C’d mod N 计算M=M’r-1 mod N = C’dr-1 mod N = (Cre)dr-1 mod N = Cd r(ed-1) mod N = Cd mod N 对RSA选择密文攻击 （选择密文意味着可以借用私钥） 利用抗计时攻击的思路， 可以用随机数r把C掩盖为C’， 然后把C’用私钥解密得到M’， 从M’乘以r-1，即得M 对RSA的主要支持和批评 形式简单，易于理解，研究深入，支持广泛 既能用来加密，又可签名 安全性的模糊（疑为等价于因子分解的难度） 随机素数产生并不容易 运算量大，速度受局限，尤其在嵌入式设备中 公钥发布 当要通信时向对方索要其公钥 需要额外的可信保障 扩散 通过可信的朋友之间的辗转交换，比如PGP中 公开的目录服务 目录的维护得由信得过的机构执行 每个用户在目录里有一项{身份信息，其公钥} 提