资源描述：
《公钥密码算法RSA.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6讲公钥密码算法《信息安全概论》课程幻灯片主要内容RSA公钥密码算法Diffie-Hellman密钥交换协议EIGamal公钥加密算法一、传统加脱密方式分析加密的目的：(1)不让窃听者读懂----信道上是密文!(2)收方能够正常脱密----有脱密密钥即可！发方收方密钥破译者不知道结论:(1)发方可以不具有脱密的能力！(2)加密密钥可与脱密密钥不同，可以公开一、传统加脱密方式分析(续)传统加密的缺点：1.密钥必须通过可靠信道在脱密前分发完毕!2.密钥的分配、存储与管理非常棘手！3.互不信任的收发双方的抵赖与否认无法判决解决方案:加密密钥公开,脱密密钥保密--非对
2、称的要求：由公开的密钥在实际上求不出保密的密钥发方收方密钥绝对可靠的信道二、公钥密码体制的基本思想（Diffie-Hellman在1977年提出)密码算法有一对密钥：一个用于加密，称为加密密钥；另一个用于脱密，称为脱密密钥。加密密钥是公开的，而脱密密钥是保密的，且加密密钥的公开不会危及脱密密钥的安全。此时，加密消息不受限制(加密密钥公开)，但只有能够脱密者只有一个！二、公钥密码体制的基本思想此时，如果一个用户使用秘密密钥处理信息，其它用户都可使用公开密钥解读处理过的信息。数字签名该方法可实现数字签名。识别签名公开密钥秘密密钥难求出用作加密密钥用作脱密密钥用作签名
3、密钥用作签名识别密钥依赖于特殊的数学难题基于公钥密码的保密通信和数字签名三、RSA密码算法作者：R.Rivest；A.Shamir；L.Adlman（美国麻省理工学院）提出时间：1977年研制，1978发表。数学难题：大合数分解是计算上不可行的。大合数分解问题的困难性已知p和q，很容易计算出p×q＝？；但是，如果已知p×q＝n，由n计算p＝？和q＝？却是十分困难的。这就是因式分解问题。例如：345677×135317=46775974609计算46773080681=？×？困难！解决该问题的一种最直接的方法就是利用每个可能的p试除n（穷举p）。但当n很大时，该方
4、法的计算量太大。最多需试除次RSA密码算法：Step1用户Bob首先选取两个不同的大素数p,q,并计算出N＝pq和φ(N)＝(p-1)(q-1)。公开密钥：(e,N)秘密密钥：(d,N)明文空间和密文空间：Z/(N)＝{0,1,…,N-1}加密算法：Step2选加密密钥e:0＜e＜φ(N),使得e与(p-1)(q-1)互素。Step3求出满足0＜d＜φ(N)和edmodφ(N)＝1的dc＝memodNAliceBob秘密参数：p,q,φ(N),d最大的公因子是1ed被φ(N)除后所得的余数脱密算法：m＝cdmodN例:设RSA体制中p=3,q=11,取加密密钥e
5、=7因e=7与φ(N)＝20互素,故可解模方程得到d＝3。加密算法：c＝m7mod33脱密算法：m＝c3mod33(1)求脱密密钥d;(2)写出相应的加密算法和脱密算法解:此时N＝p×q＝33,且φ(N)＝(p-1)(q-1)即7dmod20＝1明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,n)=(3,33)＝(3-1)(11-1)＝20edmodφ(N)＝1故RSA体制为：加密实例:设RSA算法为:当明文m＝8时，密文为：明、密文空间:Z/(33)加密密钥：(e,n)=(7,33)脱密密钥：(d,n)=(3,33)加密算法：c＝m
6、7mod33脱密算法：m＝c3mod33c＝m7mod33＝87mod33＝221mod33＝(210)2×2mod33＝(1024)2×2mod33＝(1024mod33)2×2mod33＝[(31×33＋1)mod33]2×2mod33＝2mod33＝2对密文c＝2的脱密：m＝c3mod33＝8mod33＝8＝23mod33有关RSA公钥密码的几个问题（1）RSA的脱密算法为何正确？N＝pq和φ(N)＝(p-1)(q-1)公开密钥：(e,N)秘密密钥：(d,N)明文空间和密文空间：Z/(N)＝{0,1,…,N-1}加密算法：0＜e,d＜φ(N),使得e与(p
7、-1)(q-1)互素,且edmodφ(N)＝1c＝memodN脱密算法：m＝cdmodNcdmodN＝(memodN)dmodN＝medmodNm＝?问题：现证：当0≤x＜N时，有xedmodN＝xFermat小定理设p是素数，则任意非零整数m，都有xp-1modp＝1首先：由edmodφ(N)＝1和φ(N)＝(p-1)(q-1)存在整数k，使得ed＝k(p-1)(q-1)＋1xk(p-1)(q-1)modp＝1对所有整数x，都有xk(p-1)(q-1)＋1modp＝xmodp即：xedmodp＝xmodp对所有x都成立同理可证：xedmodq＝xmodp对所有
8、x都成立现证：medmo
