資源描述：
《公鑰密碼算法RSA.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、第6講公鑰密碼算法《信息安全概論》課程幻燈片主要內容RSA公鑰密碼算法Diffie-Hellman密鑰交換協議EIGamal公鑰加密算法一、傳統加脫密方式分析加密的目的：(1)不讓竊聽者讀懂----信道上是密文!(2)收方能夠正常脫密----有脫密密鑰即可！發(fā)方收方密鑰破譯者不知道結論:(1)發(fā)方可以不具有脫密的能力！(2)加密密鑰可與脫密密鑰不同，可以公開一、傳統加脫密方式分析(續(xù))傳統加密的缺點：1.密鑰必須通過可靠信道在脫密前分發(fā)完畢!2.密鑰的分配、存儲與管理非常棘手！3.互不信任的收發(fā)雙方的抵賴與否認無法判決解決方案:加密密鑰公開,脫密密鑰保密--非對
2、稱的要求：由公開的密鑰在實際上求不出保密的密鑰發(fā)方收方密鑰絕對可靠的信道二、公鑰密碼體制的基本思想（Diffie-Hellman在1977年提出)密碼算法有一對密鑰：一個用于加密，稱為加密密鑰；另一個用于脫密，稱為脫密密鑰。加密密鑰是公開的，而脫密密鑰是保密的，且加密密鑰的公開不會危及脫密密鑰的安全。此時，加密消息不受限制(加密密鑰公開)，但只有能夠脫密者只有一個！二、公鑰密碼體制的基本思想此時，如果一個用戶使用秘密密鑰處理信息，其它用戶都可使用公開密鑰解讀處理過的信息。數字簽名該方法可實現數字簽名。識別簽名公開密鑰秘密密鑰難求出用作加密密鑰用作脫密密鑰用作簽名
3、密鑰用作簽名識別密鑰依賴于特殊的數學難題基于公鑰密碼的保密通信和數字簽名三、RSA密碼算法作者：R.Rivest；A.Shamir；L.Adlman（美國麻省理工學院）提出時間：1977年研制，1978發(fā)表。數學難題：大合數分解是計算上不可行的。大合數分解問題的困難性已知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
