rsa演算法公開密鑰

A. RSA公開密鑰體制進行運算的原理

RSA演算法
RSA演算法是R.Rivest、A.Shamir和L.Adleman於1977年在美國麻省理工學院開發，於1978年首次公布。RSA公鑰密碼演算法是目前網路上進行保密通信和數字簽名的最有效的安全演算法之一。RSA演算法的安全性基於數論中大素數分解的困難性，所以，RSA需採用足夠大的整數。因子分解越困難，密碼就越難以破譯，加密強度就越高。�0�2
演算法如下：
選兩個很大的素數p和q；
求出它們的積n = p * q，n叫做模；
選出一個數e，e<n且要求e與(p-1)(q-1)互質；
求出e的逆d，要求ed = 1 mod (p-1)(q-1)；
e和d分別叫做公開指數和私有指數。公鑰是數對（n,e）；
私鑰是d。
例如：
選取p=3, q=5，e=3,假定明文為M=7，應用RSA演算法進行加/解密。
解：(1)、n=p*q=15，
（p-1）*（q-1）=8；
(2)、 由ed= 1 mod （p-1）*（q-1）得
7*d=1 mod 8，計算出d =11。
(3)、則密文C為
C = Me mod n
= 73 mod 15
= 343 mod 15
= 13
(4)、復原明文M為：
M = Cd mod n
= 1311 mod 15
= 7

作業：
使用RSA公開密鑰體制進行運算：
1、 若p=5，q=11，求符合條件5個以上e。

e可為：1、3、7、9、11、13、17、19、21、23、27、29、
31、33、37、39、41、43、47、49、51、53

2、 設p=3，q=11，d=7，m=5，計算C。

c=me mod n=53 mod 33=26

3、若p=3，q=17，e=3，明文為「leach」(設a~z的
編號為0~25），求密文C。

字元l、e、a、c、h對應編號分別為：11、4、0、2、7；
c1=113 mod 51=5=F ；c2=43 mod 51=13=N
c3=03 mod 51=0=A ； c4=23 mod 51=8=I
c5=73 mod 51=37=L
即，密文C為：FNAIL

B. 什麼是RSA公鑰密碼

RSA公鑰密碼
RSA公鑰密碼是1977年由Ron Rivest、Adi Shamirh和LenAdleman在MIT(美國麻省理工學院〉開發的,1978年首次公布[RIVE78]。它是目前最有影響的公鑰加密演算法,它能夠抵抗到目前為止已知的所有密碼攻擊。目前它已被ISO推薦為公鑰數據加密標准。RSA演算法基於一個十分簡單的數論事實:將兩個大素數相乘十分容易,但是想分解它們的乘積卻極端困難,因此可以將乘積公開作為加密密鑰。

RSA的演算法結構相當簡單,整個演算法可以描述如下:

(1)選取兩個大素數p和q(保密)；

(2)計算n=pq(公開),γ=(p一1〉(q-1)(保密)；

(3)隨機選取整數e(公開,加密密鑰),使得ed(ear)=1

(4)計算d(保密,私人密鑰),使得ed≡1(mod r),即d=e-1(mod r);

（5)加密:c=me mod n

(6)解密:m=cd mod n。

利用RSA對被加密的信息m (長度小於log2n的整數)進行加密得到相應的密文c=me mod n;解密演算法則是計算m=cd modn RSA的優點是不需要密鑰分配,但缺點是速度慢。RSA公鑰密碼 RSA 公鑰 密碼

C. 已知RSA演算法中，素數p=5,q=7,模數n=35,公開密鑰e=5,密文c=10，求明文

密鑰d=5

明文m=c的d次方mod n

m=100000mod35

=5

或

解密密鑰：{d，n}={d，35}，

密文：C=10，

選擇兩個素數：p=5,q=7，則n=35=5*7。

計算φ(p-1)(q-1)=(5-)(7-1)=24，在[0，23]中選擇一個和24互素的數，本題選e=5，得5*d=l mod 24，解出d。不難得出，d=5，因為e×d = 5×5 = 25 = 1*24+1=1 mod 24。

因為：m=Cd(mod n)

所以，m=Cd(mod n)=5。

(3)rsa演算法公開密鑰擴展閱讀：

當公鑰e取較小的值，雖然會使加密變得易於實現，速度有所提高，但這樣做也是不安全的。最簡單的辦法就是e和d都取較大的值。

因為密鑰的產生受素數產生技術的限制，所以也有它的局限性。

（1）密鑰的產生受素數產生技術的限制，因而難以做到一次一密。

（2）分組長度太大，為保證安全性，n至少也要600比特以上，使運算代價很高，尤其是速度較慢，比對稱密碼演算法慢幾個數量級；隨著大整數素因數分解演算法的改進和計算機計算能力的提高，對n的長度在不斷增加，不利於實現數據格式的標准化。

D. 為什麼rsa演算法中即使公開公鑰，也能保證私鑰的安全

什麼是非對稱加密？所謂的非對稱加密，就是指加密和解密使用不同的密鑰的一類加密演算法。這類加密演算法通常有兩個密鑰A和B，使用密鑰A加密數據得到的密文，只有密鑰B可以進行解密操作（即使密鑰A也無法解密），相反，使用了密鑰B加密數據得到的密文，只有密鑰A可以解密。這兩個密鑰分別稱為私鑰和公鑰，顧名思義，私鑰就是你個人保留，不能公開的密鑰，而公鑰則是公開給加解密操作的另一方的。根據不同用途，對數據進行加密所使用的密鑰也不相同（有時用公鑰加密，私鑰解密；有時相反用私鑰加密，公鑰解密）。非對稱加密的代表演算法是RSA演算法。

E. des演算法與rsa演算法區別

1、性質不同：RSA公開密鑰密碼體制是一種使用不同的加密密鑰與解密密鑰。DES演算法為密碼體制中的對稱密碼體制，是1972年美國IBM公司研製的對稱密碼體制加密演算法。

2、特點不同：密鑰事實上是56位參與DES運算分組後的明文組和56位的密鑰按位替代或交換的方法形成密文組的加密方法。RSA演算法是由已知加密密鑰推導出解密密鑰在計算上是不可行的密碼體制。

3、密鑰數字不同：RSA允許選擇公鑰的大小。512位的密鑰被視為不安全的；768位的密鑰不用擔心受到除了國家安全管理（NSA）外的其他事物的危害，1024位的密鑰幾乎是安全的。DES演算法把64位的明文輸入塊變為64位的密文輸出塊，所使用的密鑰也是64位。

(5)rsa演算法公開密鑰擴展閱讀：

注意事項：

當改變明文的前8位元組時，只會影響密文的前8位元組，密文後8位元組不變。因此，在應用3DES演算法對線路傳輸數據加密過程中，若想保證密文的整體變化，要保證每塊明文數據都是變化的。

使用者在設置密鑰的時候應注意，密鑰的前後8位元組不要完全一樣，否則就變為了DES演算法，安全強度就會下降（用戶可根據Cn=Ek3(Dk2(Ek1(Mn)))公式自行推導）。需要特別留意的是，密鑰每位元組中的最後一位是檢驗位，不會參與到加密運算中。

F. 密鑰密碼體系的公開密鑰演算法RSA

公開密鑰演算法是在1976年由當時在美國斯坦福大學的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發明的（論文New Direction in Cryptography）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同開發的,分別取自三名數學家的名字的第一個字母來構成的。
1976年提出的公開密鑰密碼體制思想不同於傳統的對稱密鑰密碼體制，它要求密鑰成對出現，一個為加密密鑰(e)，另一個為解密密鑰(d)，且不可能從其中一個推導出另一個。自1976年以來，已經提出了多種公開密鑰密碼演算法，其中許多是不安全的， 一些認為是安全的演算法又有許多是不實用的，它們要麼是密鑰太大，要麼密文擴展十分嚴重。多數密碼演算法的安全基礎是基於一些數學難題， 這些難題專家們認為在短期內不可能得到解決。因為一些問題(如因子分解問題)至今已有數千年的歷史了。
公鑰加密演算法也稱非對稱密鑰演算法，用兩對密鑰：一個公共密鑰和一個專用密鑰。用戶要保障專用密鑰的安全；公共密鑰則可以發布出去。公共密鑰與專用密鑰是有緊密關系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由於公鑰演算法不需要聯機密鑰伺服器，密鑰分配協議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統還可以提供數字簽名。
公鑰加密演算法中使用最廣的是RSA。RSA使用兩個密鑰，一個公共密鑰，一個專用密鑰。如用其中一個加密，則可用另一個解密，密鑰長度從40到2048bit可變，加密時也把明文分成塊，塊的大小可變，但不能超過密鑰的長度，RSA演算法把每一塊明文轉化為與密鑰長度相同的密文塊。密鑰越長，加密效果越好，但加密解密的開銷也大，所以要在安全與性能之間折衷考慮，一般64位是較合適的。RSA的一個比較知名的應用是SSL，在美國和加拿大SSL用128位RSA演算法，由於出口限制，在其它地區（包括中國）通用的則是40位版本。
RSA演算法研製的最初理念與目標是努力使互聯網安全可靠，旨在解決DES演算法秘密密鑰的利用公開信道傳輸分發的難題。而實際結果不但很好地解決了這個難題；還可利用RSA來完成對電文的數字簽名以抗對電文的否認與抵賴；同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完性。 公用密鑰的優點就在於，也許你並不認識某一實體，但只要你的伺服器認為該實體的CA是可靠的，就可以進行安全通信，而這正是Web商務這樣的業務所要求的。例如信用卡購物。服務方對自己的資源可根據客戶CA的發行機構的可靠程度來授權。目前國內外尚沒有可以被廣泛信賴的CA。美國Natescape公司的產品支持公用密鑰，但把Natescape公司作為CA。由外國公司充當CA在我國是一件不可想像的事情。
公共密鑰方案較保密密鑰方案處理速度慢，因此，通常把公共密鑰與專用密鑰技術結合起來實現最佳性能。即用公共密鑰技術在通信雙方之間傳送專用密鑰，而用專用密鑰來對實際傳輸的數據加密解密。另外，公鑰加密也用來對專用密鑰進行加密。
在這些安全實用的演算法中，有些適用於密鑰分配，有些可作為加密演算法，還有些僅用於數字簽名。多數演算法需要大數運算，所以實現速度很慢，不能用於快的數據加密。以下將介紹典型的公開密鑰密碼演算法-RSA。
RSA演算法很好的完成對電文的數字簽名以抗對數據的否認與抵賴；利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。目前為止，很多種加密技術採用了RSA演算法，比如PGP（PrettyGoodPrivacy）加密系統，它是一個工具軟體，向認證中心注冊後就可以用它對文件進行加解密或數字簽名，PGP所採用的就是RSA演算法。由此可以看出RSA有很好的應用。

G. 公開密鑰密碼體系的演算法

公開密鑰演算法是在1976年由當時在美國斯坦福大學的迪菲（Diffie）和赫爾曼(Hellman)兩人首先發明的（論文New Direction in Cryptography）。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同開發的,分別取自三名數學家的名字的第一個字母來構成的。
1976年提出的公開密鑰密碼體制思想不同於傳統的對稱密鑰密碼體制，它要求密鑰成對出現，一個為加密密鑰(e)，另一個為解密密鑰(d)，且不可能從其中一個推導出另一個。自1976年以來，已經提出了多種公開密鑰密碼演算法，其中許多是不安全的， 一些認為是安全的演算法又有許多是不實用的，它們要麼是密鑰太大，要麼密文擴展十分嚴重。多數密碼演算法的安全基礎是基於一些數學難題， 這些難題專家們認為在短期內不可能得到解決。因為一些問題(如因子分解問題)至今已有數千年的歷史了。
公鑰加密演算法也稱非對稱密鑰演算法，用兩對密鑰：一個公共密鑰和一個專用密鑰。用戶要保障專用密鑰的安全；公共密鑰則可以發布出去。公共密鑰與專用密鑰是有緊密關系的，用公共密鑰加密的信息只能用專用密鑰解密，反之亦然。由於公鑰演算法不需要聯機密鑰伺服器，密鑰分配協議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統還可以提供數字簽名。 公鑰加密演算法中使用最廣的是RSA。RSA使用兩個密鑰，一個公共密鑰，一個專用密鑰。如用其中一個加密，則可用另一個解密，密鑰長度從40到2048bit可變，加密時也把明文分成塊，塊的大小可變，但不能超過密鑰的長度，RSA演算法把每一塊明文轉化為與密鑰長度相同的密文塊。密鑰越長，加密效果越好，但加密解密的開銷也大，所以要在安全與性能之間折衷考慮，一般64位是較合適的。RSA的一個比較知名的應用是SSL，在美國和加拿大SSL用128位RSA演算法，由於出口限制，在其它地區（包括中國）通用的則是40位版本。
RSA演算法研製的最初理念與目標是努力使互聯網安全可靠，旨在解決DES演算法秘密密鑰的利用公開信道傳輸分發的難題。而實際結果不但很好地解決了這個難題；還可利用RSA來完成對電文的數字簽名以抗對電文的否認與抵賴；同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。 通常信息安全的目標可以概括為解決信息的以下問題：
保密性(Confidentiality)保證信息不泄露給未經授權的任何人。
完整性（Integrity）防止信息被未經授權的人篡改。
可用性（Availability）保證信息和信息系統確實為授權者所用。
可控性（Controllability）對信息和信息系統實施安全監控，防止非法利用信息和信息系統。
密碼是實現一種變換，利用密碼變換保護信息秘密是密碼的最原始的能力，然而，隨著信息和信息技術發展起來的現代密碼學，不僅被用於解決信息的保密性，而且也用於解決信息的完整性、可用性和可控性。可以說，密碼是解決信息安全的最有效手段，密碼技術是解決信息安全的核心技術。
公用密鑰的優點就在於，也許你並不認識某一實體，但只要你的伺服器認為該實體的CA是可靠的，就可以進行安全通信，而這正是Web商務這樣的業務所要求的。例如信用卡購物。服務方對自己的資源可根據客戶CA的發行機構的可靠程度來授權。目前國內外尚沒有可以被廣泛信賴的CA。美國Natescape公司的產品支持公用密鑰，但把Natescape公司作為CA。由外國公司充當CA在中國是一件不可想像的事情。
公共密鑰方案較保密密鑰方案處理速度慢，因此，通常把公共密鑰與專用密鑰技術結合起來實現最佳性能。即用公共密鑰技術在通信雙方之間傳送專用密鑰，而用專用密鑰來對實際傳輸的數據加密解密。另外，公鑰加密也用來對專用密鑰進行加密。
在這些安全實用的演算法中，有些適用於密鑰分配，有些可作為加密演算法，還有些僅用於數字簽名。多數演算法需要大數運算，所以實現速度很慢，不能用於快的數據加密。以下將介紹典型的公開密鑰密碼演算法-RSA。
RSA演算法很好的完成對電文的數字簽名以抗對數據的否認與抵賴；利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。目前為止，很多種加密技術採用了RSA演算法，比如PGP（PrettyGoodPrivacy）加密系統，它是一個工具軟體，向認證中心注冊後就可以用它對文件進行加解密或數字簽名，PGP所採用的就是RSA演算法。由此可以看出RSA有很好的應用。

H. 在一個使用RSA的公開密鑰系統中，你截獲了發給一個其公開密鑰是e=5,n=35的用戶的密文C=10。明文M是什麼

解密密鑰：{d，n}={d，35}，

密文：C=10，

選擇兩個素數：p=5,q=7，則n=35=5*7。

計算φ(p-1)(q-1)=(5-1)(7-1)=24，在[0，23]中選擇一個和24互素的數，本題選e=5，得5*d=l mod 24，解出d。不難得出，d=5，因為e×d = 5×5 = 25 = 1*24+1=1 mod 24。

因為：M=Cd(mod n)

所以，M=Cd(mod n)=5。

(8)rsa演算法公開密鑰擴展閱讀：

RSA的演算法涉及三個參數，n、e1、e2。其中，n是兩個大質數p、q的積，n的二進製表示時所佔用的位數，就是所謂的密鑰長度。e1和e2是一對相關的值，e1可以任意取。

RSA的缺點主要有：

1、產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。

2、分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。

目前，SET(Secure Electronic Transaction)協議中要求CA採用2048比特長的密鑰，其他實體使用1024比特的密鑰。

I. RSA公開密鑰體制進行運算的原理

演算法如下：選兩個很大的素數p和q；求出它們的積n = p * q，n叫做模；選出一個數e，e<n且要求e與(p-1)(q-1)互質；求出e的逆d，要求ed = 1 mod (p-1)(q-1)；e和d分別叫做公開指數和私有指數。公鑰是數對（n,e）； 私鑰是d。例如： 選取p=3, q=5，e=3,假定明文為M=7，應用RSA演算法進行加/解密。 解：
(1)、n=p*q=15， （p-1）*（q-1）=8；
(2)、 由ed= 1 mod （p-1）*（q-1）得 7*d=1 mod 8，計算得d=11。
(3)、則密文C為 C = Me mod n= 73 mod 15 = 343 mod 15= 13
(4)、復原明文M為： M = Cd mod n = 1311 mod 15 = 7
作業： 使用RSA公開密鑰體制進行運算： 1、 若p=5，q=11，求符合條件5個以上e。 e可為：1、3、7、9、11、13、17、19、21、23、27、29、 31、33、37、39、41、43、47、49、51、53 2、 設p=3，q=11，d=7，m=5，計算C。 c=me mod n=53 mod 33=26 3、若p=3，q=17，e=3，明文為「leach」(設a~z的 編號為0~25），求密文C。 字元l、e、a、c、h對應編號分別為：11、4、0、2、7； c1=113 mod 51=5=F ；c2=43 mod 51=13=N c3=03 mod 51=0=A ； c4=23 mod 51=8=I c5=73 mod 51=37=L 即，密文C為：FNAIL