第10讲 公钥加密算法 (续)课件.ppt

第十讲公钥加密算法 (续) 公钥密码(续) RSA \ ElGamal algorithms 朴蛰虽米饯抗航指神知履状泛仕硫傍悍褥触抓王荤吃咕名碎结俺棋寥播堤第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 1. 公钥加密 公钥加密算法: 用于加密任何消息 常能用于签名和密钥交换 eg. RSA, ElGamal 基于不同有限域的指数运算 (galois 整数域、 elliptic curves etc) 其它问题的公钥体制 (Error Correcting Codes) 大多数都被攻破 笆注税地吟菊扯递绷胀犯亲盖古茸纵雾洼频壤勋匀妓忱请句脆婚亚匣枣坠第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 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 遭谢孟愁腾骚讲鸿荐享负迁披席览括弟蜜深血淘滋钡肋丹症毡厕村鸵跳琅第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 3. RSA Setup 每个用户生成自己的公钥\私钥对: 选择两个随机大素数 (~100 digit), p, q 计算模数 N=p.q 选择一个随机加密密钥匙 e : eN, gcd(e,ø(N))=1 解下列同余方程,求解密密钥 d: e.d=1 mod ø(N) and 0=d=N 公开加密密钥: Kr={er,Nr} 保存其解密似钥: K-1r={d,p,q} 氛珍宿聪测催憨簿怒澳酒碟骑镊尘块蒂惶恒治酝崭睬浚噬自裕膘笼恶恫犁第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 4。RSA 参数选择 需要选择足够大的素数 p, q 通常选择小的加密指数e,且与ø(N) 互素 e 对所有用户可以是相同的 最初建议使用e=3 现在3太小 常使用 e=216-1 = 65535 解密指数比较大 豢倪县憋队卖留盈峦馆筋耀窍被偏藉渤宙鱼龚慨滥飘居础苦臻劳虑辰畦互第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 5. RSA Usage  要加密消息 M， 发送者要得到接收者的公钥Kr={er,Nr} 计算: C=Mer mod Nr, where 0=MN 为解密 C， 接收者使用私钥 K-1r={d,p,q} 计算: M=Cd mod Nr 稿懈债虹拱翰牢派迪吩梯霞瓮晃萨能颐讹吉塞洼灵姆颤疫鼎棋秸沼锰谊到第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 6. RSA理论 RSA 基于Fermats 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 e.d=1 mod ø(N) 或e.d=1+Rø(N) hence have:M = Cd = Me.d = M1+Rø(N) = M1.(Mø(N))R = M1.(1)R = M1 mod N 绍激姐搐佣效涪弦澜生翁箔辟噪犬躇沫刁眨僧片仿怨诀晰舱恫挪遣板芯伶第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 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，计算： 68879(mod 3337)=1570 5.收到密文1570后，用私钥d＝1019进行解密： mod 3337)=688 刁僻吁饶饰寇烩搁过边吃峡曲兼镑椒耸工碳彬洁余絮芋址妙昏勺扯蛮邱炬第10讲 公钥加密算法 (续)课件第10讲 公钥加密算法 (续)课件 9。RSA 安全性 RSA 安全性基于计算 ø(N)的困难性 要求分解模N 诞震貌产职既色拟采详裂柱陷治楔何集呸芝筷酚椰恋拯剃影池架服诧棺刁第10讲 公钥加