以演算法為代表的公鑰密碼體制

1. 在加密演算法中屬於公鑰密碼體制的是什麼

演算法介紹：
現有矩陣M，N和P，P=M*N。如果M（或N）的行列式為零，則由P和M（或P和N）計算N（或M）是一個多值問題，特別是M（或N）的秩越小，N（或M）的解越多。
由以上問題，假設Tom和Bob相互通信，現做如下約定：
1. 在正式通信之前，二人約定一個隨機奇異矩陣M。
2. Tom和Bob各自選取一個n*n的隨機矩陣作為他們的私有密鑰，設Tom的為A，Bob的為B。
3. 然後Tom計算矩陣Pa=A*M作為他的公鑰，Bob計算矩陣Pb=M*B作為他的公鑰。
4. 當Tom向Bob發送消息時，計算加密矩陣K=A*Pb,用K對消息加密後發送到Bob端，Bob收到消息後，計算解密矩陣K』= Pa*B，由以上代數關系可以看出，K= K』，也既加密和解密是逆過程，可以參照對稱加密標准AES。
5. Bob向Tom發送消息時，計算解密矩陣K= Pa*B，加密。Tom收到消息後計算解密矩陣K=A*Pb，原理同上。
演算法分析：
由以上介紹可容易看出，此演算法比RSA和ECC的加密效率要高4-6個數量級，且加密強度在增大n的基礎上，可獲得與以上兩演算法相當的加密強度。
該演算法仍在論證階段,歡迎此方面高手攜手參與或提出缺點.
email:[email protected]

2. 什麼是公鑰密碼演算法

20世紀70年代，美國學者Diffie和Hellman，以及以色列學者Merkle分別獨立地提出了一種全新的密碼體制的概念。Diffie和Hellman首先將這個概念公布在1976年美國國家計算機會議上，幾個月後，他們這篇開創性的論文《密碼學的新方向》發表在IEEE雜志資訊理論卷上，由於印刷原因，Merkle對這一領域的貢獻直到1978年才出版。他們所創造的新的密碼學理論，突破了傳統的密碼體制對稱密鑰的概念，豎起了近代密碼學的又一里程碑。

不同於以前採用相同的加密和解密密鑰的對稱密碼體制，Diffie和Hellman提出了採用雙鑰體制，即每個用戶都有一對選定的密鑰：一個是可以公開的，另一個則是秘密的。公開的密鑰可以像電話號碼一樣公布，因此稱為公鑰密碼體制或雙鑰體制。
公鑰密碼體制的主要特點是將加密和解密的能力分開，因而可以實現多個用戶的信息只能由一個用戶解讀；或只能由一個用戶加密消息而由多個用戶解讀，前者可以用於公共網路中實現保密通信，而後者可以用於認證系統中對消息進行數字簽名。
公開密鑰密碼的基本思想是將傳統密碼的密鑰一分為二，分為加密密鑰Ke和解密密鑰Kd，用加密密鑰Ke控制加密，用解密密鑰Kd控制解密。而且由計算復雜性確保加密密鑰Ke在計算上不能推導出解密密鑰Kd。這樣，即使將Ke公開也不會暴露Kd，也不會損害密碼的安全。於是便可以將Ke公開，而只對Kd保密。由於Ke是公開的，只有Kd是保密的，因此從根本上克服了傳統密碼在密鑰分配上的困難。

公開密鑰密碼滿足的條件
根據公開密鑰密碼的基本思想，可知一個公開密鑰密碼應當滿足下面三個條件：

1. 解密演算法D和加密演算法E互逆，即對所有明文M都有，D(E(M,Ke),Kd)=M。
2. 在計算上不能由Ke推導出Kd。
3. 演算法E和D都是高效的。

條件1是構成密碼的基本條件，是傳統密碼和公開密鑰密碼都必須具備的起碼條件。
條件2是公開密鑰密碼的安全條件，是公開密鑰密碼的安全基礎，而且這一條件是最難滿足的。目前尚不能從數學上證明一個公開密鑰密碼完全滿足這一條件，而只能證明它不滿足這一條件。
條件3是公開密鑰密碼的工程實用條件。因為只有演算法E和D都是高效的，密碼才能實用。否則，密碼只有理論意義，而不能實際應用。
滿足了以上三個條件，便可構成一個公開密鑰密碼，這個密碼可以確保數據的秘密性。然而還需要確保數據的真實性，則還需滿足第四個條件。
4.對於所有明文M都有E(D(M,Kd),Ke)=M。
條件4是公開密鑰密碼能夠確保數據真實性的基本條件。如果滿足了條件1、2、4，同樣可以構成一個公開密鑰密碼，這個密碼可以確保數據的真實性。
如果同時滿足以上四個條件，則公開密鑰密碼可以同時確保數據的秘密性和真實性。此時，對於所有的明文M都有D(E(M,Ke),Kd)= E(D(M,Kd),Ke)=M。
公開密鑰密碼從根本上克服了傳統密碼在密鑰分配上的困難，利用公開密鑰密碼進行保密通信需要成立一個密鑰管理機構（KMC），每個用戶將自己的姓名、地址和公開的加密密鑰等信息在KMC登記注冊，將公鑰記入共享的公開密鑰資料庫。KMC負責密鑰的管理，並對用戶是可信賴的。這樣，用戶利用公開密鑰密碼進行保密通信就像查電話號碼簿打電話一樣方便，再也不需要通信雙方預約密鑰，因此特別適合計算機網路應用，而且公開密鑰密碼實現數字簽名容易，所以特別受歡迎。
下圖是公鑰密碼體制的框圖，主要分為以下幾步：

1. 網路中要求接收消息的端系統，產生一對用來加密和解密的密鑰，如圖中的接收者B，產生一對密鑰PKB，SKB，其中PKB是公開鑰，SKB是秘密鑰。
2. 端系統B將加密密鑰（圖中的PKB）存儲在一個公開的寄存器或文件中，另一密鑰則被保密（圖中個SKB）。
3. A要想向B發送消息m，則使用B的公開鑰加密m，表示為 c=EPKB[m] 其中，c是密文，E是加密演算法。
4. B收到密文c後，用自己的秘密鑰SKB解密，表示為 m=DSKB[c] 其中，D是解密演算法。因為只有B知道SKB，所以其他人無法對c解密。

這就是公開密鑰的原理~

（轉載需向本人獲取許可權）

3. 公鑰密碼體制是什麼它的出現有何重要意義它與對稱密碼體制的異同有哪些

公開密鑰密碼體制是現代密碼學的最重要的發明和進展。公開密鑰密碼體制對信息發送與接收人的真實身份的驗證、對所發出/接收信息在事後的不可抵賴以及保障數據的完整性有著重要意義。

公鑰密碼體制與對稱密碼體制都是密碼體制中的一種。

公鑰密碼體制與對稱密碼體制的主要區別如下：

一、性質不同

1、公鑰密碼體制：是現代密碼學的最重要的發明和進展。

2、對稱密碼體制：是一種傳統密碼體制，也稱為私鑰密碼體制。

二、作用不同

1、公鑰密碼體制：努力使互聯網安全可靠，旨在解決DES演算法秘密密鑰的利用公開信道傳輸分發的難題。

2、對稱密碼體制：由於對稱加密系統僅能用於對數據進行加解密處理，提供數據的機密性，不能用於數字簽名。因而人們迫切需要尋找新的密碼體制。

三、特點不同

1、公鑰密碼體制：由於公鑰演算法不需要聯機密鑰伺服器，密鑰分配協議簡單，所以極大簡化了密鑰管理。除加密功能外，公鑰系統還可以提供數字簽名。

2、對稱密碼體制：計算開銷小，加密速度快，是用於信息加密的主要演算法。

4. 公鑰密碼體制和私鑰密碼體制各有什麼優缺點

常用密鑰，加密解密用同一個Key，安全性，防偽性，鑒權性都不好。
公鑰私鑰解決了以上的問題。

5. RSA演算法的基本含義

RSA公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種「由已知加密密鑰推導出解密密鑰在計算上是不可行的」密碼體制。
在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密演算法E和解密演算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據PK計算出SK。
正是基於這種理論，1978年出現了著名的RSA演算法，它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網路伺服器中注冊。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常採用傳統加密方法與公開密鑰加密方法相結合的方式，即信息採用改進的DES或IDEA對話密鑰加密，然後使用RSA密鑰加密對話密鑰和信息摘要。對方收到信息後，用不同的密鑰解密並可核對信息摘要。
RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現今的三十多年裡，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。
SET(Secure Electronic Transaction)協議中要求CA採用2048bits長的密鑰，其他實體使用1024比特的密鑰。RSA密鑰長度隨著保密級別提高，增加很快。下表列出了對同一安全級別所對應的密鑰長度。 保密級別 對稱密鑰長度（bit） RSA密鑰長度（bit） ECC密鑰長度（bit） 保密年限 80 80 1024 160 2010 112 112 2048 224 2030 128 128 3072 256 2040 192 192 7680 384 2080 256 256 15360 512 2120 這種演算法1978年就出現了，它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman。早在1973年，英國國家通信總局的數學家Clifford Cocks就發現了類似的演算法。但是他的發現被列為絕密，直到1998年才公諸於世。
RSA演算法是一種非對稱密碼演算法，所謂非對稱，就是指該演算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。
RSA的演算法涉及三個參數，n、e1、e2。
其中，n是兩個大質數p、q的積，n的二進製表示時所佔用的位數，就是所謂的密鑰長度。
e1和e2是一對相關的值，e1可以任意取，但要求e1與(p-1)*(q-1)互質；再選擇e2，要求(e2*e1)mod((p-1)*(q-1))=1。
（n，e1),(n，e2)就是密鑰對。其中(n，e1)為公鑰，(n，e2)為私鑰。
RSA加解密的演算法完全相同，設A為明文，B為密文，則：A=B^e2 mod n；B=A^e1 mod n；（公鑰加密體制中，一般用公鑰加密，私鑰解密）
e1和e2可以互換使用，即：
A=B^e1 mod n；B=A^e2 mod n;

6. 密碼體制的技術分類

密碼體制分為私用密鑰加密技術(對稱加密)和公開密鑰加密技術(非對稱加密)。
1、對稱密碼體制
對稱密碼體制是一種傳統密碼體制，也稱為私鑰密碼體制。在對稱加密系統中，加密和解密採用相同的密鑰。因為加解密密鑰相同，需要通信的雙方必須選擇和保存他們共同的密鑰，各方必須信任對方不會將密鑰泄密出去，這樣就可以實現數據的機密性和完整性。對於具有n個用戶的網路，需要n(n-1)/2個密鑰，在用戶群不是很大的情況下，對稱加密系統是有效的。但是對於大型網路，當用戶群很大，分布很廣時，密鑰的分配和保存就成了問題。對機密信息進行加密和驗證隨報文一起發送報文摘要(或散列值)來實現。比較典型的演算法有DES(Data Encryption Standard數據加密標准)演算法及其變形Triple DES(三重DES)，GDES(廣義DES)；歐洲的IDEA；日本的FEAL N、RC5等。DES標准由美國國家標准局提出,主要應用於銀行業的電子資金轉帳(EFT)領域。DES的密鑰長度為56bit。Triple DES使用兩個獨立的56bit密鑰對交換的信息進行3次加密，從而使其有效長度達到112bit。RC2和RC4方法是RSA數據安全公司的對稱加密專利演算法，它們採用可變密鑰長度的演算法。通過規定不同的密鑰長度,，C2和RC4能夠提高或降低安全的程度。對稱密碼演算法的優點是計算開銷小，加密速度快，是目前用於信息加密的主要演算法。它的局限性在於它存在著通信的貿易雙方之間確保密鑰安全交換的問題。此外，某一貿易方有幾個貿易關系，他就要維護幾個專用密鑰。它也沒法鑒別貿易發起方或貿易最終方，因為貿易的雙方的密鑰相同。另外，由於對稱加密系統僅能用於對數據進行加解密處理，提供數據的機密性，不能用於數字簽名。因而人們迫切需要尋找新的密碼體制。
2、非對稱密碼體制
非對稱密碼體制也叫公鑰加密技術，該技術就是針對私鑰密碼體制的缺陷被提出來的。在公鑰加密系統中，加密和解密是相對獨立的，加密和解密會使用兩把不同的密鑰，加密密鑰(公開密鑰)向公眾公開，誰都可以使用，解密密鑰(秘密密鑰)只有解密人自己知道，非法使用者根據公開的加密密鑰無法推算出解密密鑰，顧其可稱為公鑰密碼體制。如果一個人選擇並公布了他的公鑰，另外任何人都可以用這一公鑰來加密傳送給那個人的消息。私鑰是秘密保存的，只有私鑰的所有者才能利用私鑰對密文進行解密。公鑰密碼體制的演算法中最著名的代表是RSA系統，此外還有:背包密碼、McEliece密碼、Diffe_Hellman、Rabin、零知識證明、橢圓曲線、EIGamal演算法等。公鑰密鑰的密鑰管理比較簡單,並且可以方便的實現數字簽名和驗證。但演算法復雜,加密數據的速率較低。公鑰加密系統不存在對稱加密系統中密鑰的分配和保存問題，對於具有n個用戶的網路，僅需要2n個密鑰。公鑰加密系統除了用於數據加密外，還可用於數字簽名。公鑰加密系統可提供以下功能：A、機密性（Confidentiality）：保證非授權人員不能非法獲取信息，通過數據加密來實現；B、確認（Authentication）：保證對方屬於所聲稱的實體，通過數字簽名來實現；C、數據完整性（Data integrity）：保證信息內容不被篡改，入侵者不可能用假消息代替合法消息，通過數字簽名來實現；D、不可抵賴性（Nonrepudiation）：發送者不可能事後否認他發送過消息，消息的接受者可以向中立的第三方證實所指的發送者確實發出了消息，通過數字簽名來實現。可見公鑰加密系統滿足信息安全的所有主要目標。

7. 公鑰加密解密體系包括哪些

公鑰加密解密體系包括：

(1)明文空間M，它是全體明文的集合。

(2)密文空間C，它是全體密文的集合。

(3)密鑰空間K，它是全體密鑰的集合。其中每一個密鑰K均由加密密鑰和解密密鑰組成，即。

(4)加密演算法E，它是一族由M到C的加密變換，對於每一個具體的，則E就確定出一個具體的加密函數，把M加密成密文C。

(5)解密演算法D，它是一族由C到M的解密變換，對於每一個確定的，則D就確定出一個具體的解密函數。

公鑰加密體制是不對稱密鑰，優點是運算速度快，密鑰產生容易。

8. 公鑰密碼系統及RSA公鑰演算法

公鑰密碼系統及RSA公鑰演算法

本文簡單介紹了公開密鑰密碼系統的思想和特點，並具體介紹了RSA演算法的理論基礎，工作原理和具體實現過程，並通過一個簡單例子說明了該演算法是如何實現。在本文的最後，概括說明了RSA演算法目前存在的一些缺點和解決方法。

關鍵詞：公鑰密碼體制 ， 公鑰 ，私鑰 ，RSA

§1引言

隨著計算機聯網的逐步實現，Internet前景越來越美好，全球經濟發展正在進入信息經濟時代，知識經濟初見端倪。計算機信息的保密問題顯得越來越重要，無論是個人信息通信還是電子商務發展，都迫切需要保證Internet網上信息傳輸的安全，需要保證信息安全。信息安全技術是一門綜合學科，它涉及資訊理論、計算機科學和密碼學等多方面知識，它的主要任務是研究計算機系統和通信網路內信息的保護方法以實現系統內信息的安全、保密、真實和完整。其中，信息安全的核心是密碼技術。密碼技術是集數學、計算機科學、電子與通信等諸多學科於一身的交叉學科。它不僅能夠保證機密性信息的加密，而且能夠實現數字簽名、身份驗證、系統安全等功能。是現代化發展的重要科學之一。本文將對公鑰密碼系統及該系統中目前最廣泛流行的RSA演算法做一些簡單介紹。

§2公鑰密碼系統

要說明公鑰密碼系統，首先來了解一下不同的加密演算法：目前的加密演算法按密鑰方式可分為單鑰密碼演算法和公鑰密碼演算法。

2.1.單鑰密碼

又稱對稱式密碼，是一種比較傳統的加密方式，其加密運算、解密運算使用的是同樣的密鑰，信息的發送者和信息的接收者在進行信息的傳輸與處理時，必須共同持有該密碼（稱為對稱密碼）。因此，通信雙方都必須獲得這把鑰匙，並保持鑰匙的秘密。

單鑰密碼系統的安全性依賴於以下兩個因素：第一，加密演算法必須是足夠強的，僅僅基於密文本身去解密信息在實踐上是不可能的；第二，加密方法的安全性依賴於密鑰的秘密性，而不是演算法的秘密性，因此，我們沒有必要確保演算法的秘密性（事實上，現實中使用的很多單鑰密碼系統的演算法都是公開的），但是我們一定要保證密鑰的秘密性。

從單鑰密碼的這些特點我們容易看出它的主要問題有兩點：第一，密鑰量問題。在單鑰密碼系統中，每一對通信者就需要一對密鑰，當用戶增加時，必然會帶來密鑰量的成倍增長，因此在網路通信中，大量密鑰的產生﹑存放和分配將是一個難以解決的問題。第二，密鑰分發問題。單鑰密碼系統中，加密的安全性完全依賴於對密鑰的保護，但是由於通信雙方使用的是相同的密鑰，人們又不得不相互交流密鑰，所以為了保證安全，人們必須使用一些另外的安全信道來分發密鑰，例如用專門的信使來傳送密鑰，這種做法的代價是相當大的，甚至可以說是非常不現實的，尤其在計算機網路環境下，人們使用網路傳送加密的文件，卻需要另外的安全信道來分發密鑰，顯而易見，這是非常不智是甚至是荒謬可笑的。

2.2公鑰密碼

正因為單鑰密碼系統存在如此難以解決的缺點，發展一種新的﹑更有效﹑更先進的密碼體制顯得更為迫切和必要。在這種情況下，出現了一種新的公鑰密碼體制，它突破性地解決了困擾著無數科學家的密鑰分發問題，事實上，在這種體制中，人們甚至不用分發需要嚴格保密的密鑰，這次突破同時也被認為是密碼史上兩千年來自單碼替代密碼發明以後最偉大的成就。

這一全新的思想是本世紀70年代，美國斯坦福大學的兩名學者Diffie和Hellman提出的，該體制與單鑰密碼最大的不同是：

在公鑰密碼系統中，加密和解密使用的是不同的密鑰（相對於對稱密鑰，人們把它叫做非對稱密鑰），這兩個密鑰之間存在著相互依存關系：即用其中任一個密鑰加密的信息只能用另一個密鑰進行解密。這使得通信雙方無需事先交換密鑰就可進行保密通信。其中加密密鑰和演算法是對外公開的，人人都可以通過這個密鑰加密文件然後發給收信者，這個加密密鑰又稱為公鑰；而收信者收到加密文件後,它可以使用他的解密密鑰解密，這個密鑰是由他自己私人掌管的，並不需要分發，因此又成稱為私鑰，這就解決了密鑰分發的問題。

為了說明這一思想,我們可以考慮如下的類比：

兩個在不安全信道中通信的人，假設為Alice（收信者）和Bob（發信者），他們希望能夠安全的通信而不被他們的敵手Oscar破壞。Alice想到了一種辦法，她使用了一種鎖（相當於公鑰），這種鎖任何人只要輕輕一按就可以鎖上，但是只有Alice的鑰匙（相當於私鑰）才能夠打開。然後Alice對外發送無數把這樣的鎖，任何人比如Bob想給她寄信時，只需找到一個箱子，然後用一把Alice的鎖將其鎖上再寄給Alice，這時候任何人（包括Bob自己）除了擁有鑰匙的Alice，都不能再打開箱子，這樣即使Oscar能找到Alice的鎖，即使Oscar能在通信過程中截獲這個箱子，沒有Alice的鑰匙他也不可能打開箱子，而Alice的鑰匙並不需要分發，這樣Oscar也就無法得到這把「私人密鑰」。

從以上的介紹可以看出，公鑰密碼體制的思想並不復雜，而實現它的關鍵問題是如何確定公鑰和私鑰及加/解密的演算法，也就是說如何找到「Alice的鎖和鑰匙」的問題。我們假設在這種體制中, PK是公開信息，用作加密密鑰，而SK需要由用戶自己保密，用作解密密鑰。加密演算法E和解密演算法D也都是公開的。雖然SK與PK是成對出現，但卻不能根據PK計算出SK。它們須滿足條件：

①加密密鑰PK對明文X加密後，再用解密密鑰SK解密，即可恢復出明文，或寫為：DSK（EPK（X））=X

②加密密鑰不能用來解密，即DPK（EPK（X））≠X

③在計算機上可以容易地產生成對的PK和SK。

④從已知的PK實際上不可能推導出SK。

⑤加密和解密的運算可以對調，即：EPK（DSK（X））=X

從上述條件可看出，公開密鑰密碼體制下，加密密鑰不等於解密密鑰。加密密鑰可對外公開，使任何用戶都可將傳送給此用戶的信息用公開密鑰加密發送，而該用戶唯一保存的私人密鑰是保密的，也只有它能將密文復原、解密。雖然解密密鑰理論上可由加密密鑰推算出來，但這種演算法設計在實際上是不可能的，或者雖然能夠推算出，但要花費很長的時間而成為不可行的。所以將加密密鑰公開也不會危害密鑰的安全。

這種體制思想是簡單的，但是，如何找到一個適合的演算法來實現這個系統卻是一個真正困擾密碼學家們的難題，因為既然Pk和SK是一對存在著相互關系的密鑰，那麼從其中一個推導出另一個就是很有可能的，如果敵手Oscar能夠從PK推導出SK，那麼這個系統就不再安全了。因此如何找到一個合適的演算法生成合適的Pk和SK，並且使得從PK不可能推導出SK，正是迫切需要密碼學家們解決的一道難題。這個難題甚至使得公鑰密碼系統的發展停滯了很長一段時間。

為了解決這個問題，密碼學家們考慮了數學上的陷門單向函數，下面，我們可以給出它的非正式定義：

Alice的公開加密函數應該是容易計算的，而計算其逆函數（即解密函數）應該是困難的（對於除Alice以外的人）。許多形式為Y=f（x）的函數，對於給定的自變數x值，很容易計算出函數Y的值；而由給定的Y值，在很多情況下依照函數關系f (x)計算x值十分困難。這樣容易計算但難於求逆的函數，通常稱為單向函數。在加密過程中，我們希望加密函數E為一個單項的單射函數，以便可以解密。雖然目前還沒有一個函數能被證明是單向的，但是有很多單射函數被認為是單向的。

例如，有如下一個函數被認為是單向的，假定n為兩個大素數p和q的乘積，b為一個正整數，那麼定義f：

f (x )= x b mod n

(如果gcd（b,φ（n））=1，那麼事實上這就是我們以下要說的RSA加密函數)

如果我們要構造一個公鑰密碼體制，僅給出一個單向的單射函數是不夠的。從Alice的觀點來看，並不需要E是單向的，因為它需要用有效的方式解密所收到的信息。因此，Alice應該擁有一個陷門，其中包含容易求出E的你函數的秘密信息。也就是說，Alice可以有效解密，因為它有額外的秘密知識，即SK，能夠提供給你解密函數D。因此，我們稱一個函數為一個陷門單向函數，如果它是一個單向函數，並在具有特定陷門的知識後容易求出其逆。

考慮上面的函數f (x) = xb mod n。我們能夠知道其逆函數f -1有類似的形式f (x ) = xa mod n，對於合適的取值a。陷門就是利用n的因子分解，有效的算出正確的指數a（對於給定的b）。

為方便起見，我們把特定的某類陷門單向函數計為?。那麼隨機選取一個函數f屬於?，作為公開加密函數；其逆函數f-1是秘密解密函數。那麼公鑰密碼體制就能夠實現了。

根據以上關於陷門單向函數的思想,學者們提出了許多種公鑰加密的方法，它們的安全性都是基於復雜的數學難題。根據所基於的數學難題，至少有以下三類系統目前被認為是安全和有效的：大整數因子分解系統(代表性的有RSA)、橢園曲線離散對數系統(ECC)和離散對數系統(代表性的有DSA)。

§3 RSA演算法

3.1簡介

當前最著名、應用最廣泛的公鑰系統RSA是在1978年，由美國麻省理工學院(MIT)的Rivest、Shamir和Adleman在題為《獲得數字簽名和公開鑰密碼系統的方法》的論文中提出的。它是一個基於數論的非對稱(公開鑰)密碼體制，是一種分組密碼體制。其名稱來自於三個發明者的姓名首字母。它的安全性是基於大整數素因子分解的困難性，而大整數因子分解問題是數學上的著名難題，至今沒有有效的方法予以解決，因此可以確保RSA演算法的安全性。RSA系統是公鑰系統的最具有典型意義的方法，大多數使用公鑰密碼進行加密和數字簽名的產品和標准使用的都是RSA演算法。

RSA演算法是第一個既能用於數據加密也能用於數字簽名的演算法，因此它為公用網路上信息的加密和鑒別提供了一種基本的方法。它通常是先生成一對RSA密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網路伺服器中注冊，人們用公鑰加密文件發送給個人，個人就可以用私鑰解密接受。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。

該演算法基於下面的兩個事實,這些事實保證了RSA演算法的安全有效性：

1)已有確定一個數是不是質數的快速演算法；

2)尚未找到確定一個合數的質因子的快速演算法。

3.2工作原理

1)任意選取兩個不同的大質數p和q，計算乘積r=p*q；

2)任意選取一個大整數e，e與(p-1)*(q-1)互質，整數e用做加密密鑰。注意：e的選取是很容易的，例如，所有大於p和q的質數都可用。

3)確定解密密鑰d：d * e = 1 molo（p - 1）*（q - 1） 根據e、p和q可以容易地計算出d。

4)公開整數r和e，但是不公開d；

5)將明文P (假設P是一個小於r的整數)加密為密文C，計算方法為：

C = Pe molo r

6)將密文C解密為明文P，計算方法為：

P = Cd molo r

然而只根據r和e（不是p和q）要計算出d是不可能的。因此，任何人都可對明文進行加密，但只有授權用戶（知道d）才可對密文解密。

3.3簡單實例

為了說明該演算法的工作過程,我們下面給出一個簡單例子,顯然我們在這只能取很小的數字，但是如上所述，為了保證安全，在實際應用上我們所用的數字要大的多得多。

例：選取p=3, q=5，則r=15，（p-1）*（q-1）=8。選取e=11（大於p和q的質數），通過d * 11 = 1 molo 8，計算出d =3。

假定明文為整數13。則密文C為

C = Pe molo r

= 1311 molo 15

= 1,792,160,394,037 molo 15

= 7

復原明文P為：

P = Cd molo r

= 73 molo 15

= 343 molo 15

= 13

因為e和d互逆，公開密鑰加密方法也允許採用這樣的方式對加密信息進行"簽名"，以便接收方能確定簽名不是偽造的。

假設A和B希望通過公開密鑰加密方法進行數據傳輸，A和B分別公開加密演算法和相應的密鑰，但不公開解密演算法和相應的密鑰。A和B的加密演算法分別是ECA和ECB，解密演算法分別是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。 若A要向B發送明文P，不是簡單地發送ECB（P），而是先對P施以其解密演算法DCA，再用加密演算法ECB對結果加密後發送出去。

密文C為：

C = ECB（DCA（P））

B收到C後，先後施以其解密演算法DCB和加密演算法ECA，得到明文P：

ECA（DCB（C））

= ECA（DCB（ECB（DCA（P））））

= ECA（DCA（P））/*DCB和ECB相互抵消*/

=

P          /*DCB和ECB相互抵消*/

這樣B就確定報文確實是從A發出的，因為只有當加密過程利用了DCA演算法，用ECA才能獲得P，只有A才知道DCA演算法，沒 有人，即使是B也不能偽造A的簽名。

3.4優缺點

3.4.1優點

RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。該演算法的加密密鑰和加密演算法分開，使得密鑰分配更為方便。它特別符合計算機網路環境。對於網上的大量用戶，可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進行保密通信，只需從公鑰簿上查出對方的加密密鑰，用它對所傳送的信息加密發出即可。對方收到信息後，用僅為自己所知的解密密鑰將信息脫密，了解報文的內容。由此可看出，RSA演算法解決了大量網路用戶密鑰管理的難題，這是公鑰密碼系統相對於對稱密碼系統最突出的優點。

3.4.2缺點

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

2)安全性, RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價，而且密碼學界多數人士傾向於因子分解不是NPC問題。目前，人們已能分解140多個十進制位的大素數，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：

( XM )d = Xd *Md mod n

前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特徵--每個人都能使用公鑰。但從演算法上無法解決這一問題，主要措施有兩條：一條是採用好的公鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way Hash Function對文檔作HASH處理，或同時使用不同的簽名演算法。除了利用公共模數，人們還嘗試一些利用解密指數或φ（n）等等攻擊.

3)速度太慢,由於RSA的分組長度太大，為保證安全性，n至少也要600 bitx以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。目前，SET(Secure Electronic Transaction)協議中要求CA採用2048比特長的密鑰，其他實體使用1024比特的密鑰。為了速度問題,目前人們廣泛使用單,公鑰密碼結合使用的方法,優缺點互補:單鑰密碼加密速度快,人們用它來加密較長的文件,然後用RSA來給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發問題。

§4結束語

目前，日益激增的電子商務和其它網際網路應用需求使公鑰體系得以普及，這些需求量主要包括對伺服器資源的訪問控制和對電子商務交易的保護，以及權利保護、個人隱私、無線交易和內容完整性（如保證新聞報道或股票行情的真實性）等方面。公鑰技術發展到今天，在市場上明顯的發展趨勢就是PKI與操作系統的集成，PKI是「Public

Key Infrastructure」的縮寫，意為「公鑰基礎設施」。公鑰體制廣泛地用於CA認證、數字簽名和密鑰交換等領域。

公鑰加密演算法中使用最廣的是RSA。RSA演算法研製的最初理念與目標是努力使互聯網安全可靠，旨在解決DES演算法秘密密鑰的利用公開信道傳輸分發的難題。而實際結果不但很好地解決了這個難題；還可利用RSA來完成對電文的數字簽名以抗對電文的否認與抵賴；同時還可以利用數字簽名較容易地發現攻擊者對電文的非法篡改，以保護數據信息的完整性。目前為止，很多種加密技術採用了RSA演算法，該演算法也已經在互聯網的許多方面得以廣泛應用，包括在安全介面層（SSL）標准（該標準是網路瀏覽器建立安全的互聯網連接時必須用到的）方面的應用。此外，RSA加密系統還可應用於智能IC卡和網路安全產品。

但目前RSA演算法的專利期限即將結束，取而代之的是基於橢圓曲線的密碼方案（ECC演算法）。較之於RSA演算法，ECC有其相對優點，這使得ECC的特性更適合當今電子商務需要快速反應的發展潮流。此外，一種全新的量子密碼也正在發展中。

至於在實際應用中應該採用何種加密演算法則要結合具體應用環境和系統，不能簡單地根據其加密強度來做出判斷。因為除了加密演算法本身之外，密鑰合理分配、加密效率與現有系統的結合性以及投入產出分析都應在實際環境中具體考慮。加密技術隨著網路的發展更新，將有更安全更易於實現的演算法不斷產生，為信息安全提供更有力的保障。今後，加密技術會何去何從，我們將拭目以待。

參考文獻：

[1] Douglas R.Stinson.《密碼學原理與實踐》.北京:電子工業出版社,2003,2:131-132

[2]西蒙.辛格.《密碼故事》.海口:海南出版社,2001,1:271-272

[3]嬴政天下.加密演算法之RSA演算法.http://soft.winzheng.com/infoView/Article_296.htm，2003

[4]加密與數字簽名.http://www.njt.cn/yumdq/dzsw/a2.htm

[5]黑客中級教程系列之十.http://www.qqorg.i-p.com/jiaocheng/10.html

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

公開密鑰演算法是在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有很好的應用。

10. 對稱密鑰體制與公鑰密鑰體制的特點各自是什麼各有何優缺點

對稱密鑰體制是加密密鑰與解密密鑰密碼相同，兩個參與者共享同一個密鑰。

公鑰密碼體制是使用不同的加密密鑰和解密密鑰，加密密鑰是公開信息，而解密密鑰需要保密。

公鑰密碼體制有很多良好的特性，它不僅可以用來加密，還可以很方便的用於鑒別和數字簽名。但公鑰密碼演算法比對稱密鑰密碼演算法要慢好幾個數量級。

對稱密鑰體制的加解密速度快且安全強度高，但密鑰難管理和傳送，不適於在網路中單獨使用。

密鑰的產生

1、選擇兩個大素數，p和q。

2、計算：n = p * q (p，q分別為兩個互異的大素數，p，q必須保密，一般要求p，q為安全素數，n的長度大於512bit，這主要是因為RSA演算法的安全性依賴於因子分解大數問題）。有歐拉函數(n)=(p-1)(q-1)。

3、然後隨機選擇加密密鑰e，要求e和( p - 1 ) * ( q - 1 )互質。

4、最後，利用Euclid演算法計算解密密鑰d,滿足de≡1(modφ（n))。其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。