文档介绍：第十讲公钥加密算法(续) ?公钥密码(续)? RSA \ ElGamal algorithms ?目标: 掌握公钥加密算法 RSA 、 ElGamal 的原理掌握 RSA 、 ElGamal 的密钥生成算法 1. 公钥加密?公钥加密算法: 用于加密任何消息?常能用于签名和密钥交换? eg . RSA, ElGamal ?基于不同有限域的指数运算( galois 整数域、 elliptic curves etc) ?其它问题的公钥体制(Error Correcting Codes) ?大多数都被攻破? NTRU 2. RSA ( Rivest , Shamir , Adleman ) ?使用最广泛的公钥加密算法? Rivest , Shamir & Adleman (RSA) in 1977 ? R L Rivest , A Shamir , L Adleman , "On Digital Signatures and Public Key Cryptosystems", Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978 ? 3. RSA Setup ?每个用户生成自己的公钥\私钥对: ?选择两个随机大素数(~100 digit), p, q ?计算模数 N= ?选择一个随机加密密钥匙 e : e<N, gcd(e, ? (N ))=1 ?解下列同余方程,求解密密钥 d : ? =1 mod ? (N) and 0<=d<=N ?公开加密密钥: K={e,N} ?保存其解密似钥: ?K -1 ={d,p,q} 4。 RSA 参数选择?需要选择足够大的素数 p, q ?通常选择小的加密指数 e,且与? (N) 互素?e对所有用户可以是相同的?最初建议使用 e=3 ?现在 3太小?常使用 e=2 16 -1 = 65535 ?解密指数比较大 5. RSA Usage ?要加密消息 M,发送者要得到接收者的公钥 K={e,N} ?计算: C=M e mod N , where 0<=M<N ?为解密 C,接收者使用私钥?K -1 ={d,p,q} ?计算: M= C d mod N 6. RSA 理论? RSA 基于 Fermat's Theorem: ? if N = pq where p, q are primes, then: X ? (N) = 1 mod N ? for all x not divisible by p or q, ie gcd(x, ? (N ))=1 ? where ? (N)=(p-1)(q-1) ?但在 RSA 中, e & d 是特殊选择的? ie =1 mod ? (N) 或 =1+R ? (N) ? hence have: M = C d = M = M 1+R ? (N) = M 1 .(M ? (N)) R = M 1 .(1) R = M 1 mod N ? 8。 RSA 举例例子: 1. 选素数 p=47 和q=71,得 N=3337, ? (N)=46 ×70=3220 ; 2. 选择 e=79 ,求得私钥 d=e -1? 1019(mod 3220 )。 3. 公开 N=3337 和 e=79. 4. 现要发送明文 688 ,计算: 688 79 (mod 3337)=1570 1570 后,用私钥 d=1019 进行解密: 1570 1019 ( mod 3337)=688 9。 RSA 安全性? RSA 安全性基于计算? (N) 的困难性?要求分解模 N