概率公開密鑰加密演算法

① 公鑰加密演算法/哈希演算法

公鑰加密演算法 也叫非對稱加密，它在加密和解密時使用的是不同的密鑰，具有這樣的特徵：

最常見的公鑰加密演算法是RSA公鑰加密演算法，也是簽名中普遍使用的演算法。其數學原理如下：

理論上 {n, e} 和 {n, d} 可以互換，任何一個都可以是公鑰或者私鑰，加密和解密的函數也可以互換。但實踐中，一般固定設置 e = 65537(0x10001) ，相當於公開的一個約定，這樣一來 {n, e} 就只能作為公鑰使用。

哈希演算法
也叫散列或者摘要演算法，對一段任意長度的數據，通過一定的映射和計算，得到一個固定長度的值，這個值就被稱為這段數據的哈希值(hash)。給定一個哈希演算法，它一定具有以下特徵：

常見的哈希演算法有: md5, sha1, sha256等，其中sha1長度為160bits，而sha256長度為256bits，二者相比，sha256的取值范圍更大，因此碰撞和破解的概率更低，也就相對更安全。

② 密鑰和加密演算法是個什麼關系

密鑰是一種參數（它是在明文轉換為密文或將密文轉換為明文的演算法中輸入的數據），加密演算法是明文轉換成密文的變換函數，同樣的密鑰可以用不同的加密演算法，得到的密文就不一樣了。

舉個很簡單的例子，比如凱撒密碼，就是將字母循環後移n位，這個n就是一個密鑰，循環後移的方法叫做演算法，雖然用的是相同的演算法，但是對明文用不同的密鑰加密的結果不一樣。

比如Run用Key=1（密鑰）的凱撒密碼，變成Svo，用Key=2（密鑰）加密就成了Twp，所以密鑰和演算法是明顯不同的，再比如現在公鑰密碼體系大多用的RSA演算法，但每個人的密鑰不一樣，密文才不同，一般來說，演算法是公開的，而密鑰是不公開的一個加密演算法正好包含兩個輸入參數，一個是明文，一個是密鑰。

(2)概率公開密鑰加密演算法擴展閱讀：

1，秘密密鑰演算法：

使用極其復雜的加密演算法，即使破譯者能夠對選擇的任意數量的明文進行加密，也無法找出破譯密文的方法。秘密密鑰的一個弱點是解密密鑰必須和加密密碼相同，這就產生了如何安全地分發密鑰的問題。

2，公開密鑰演算法：

滿足三個條件：第一個條件是指將解密演算法作用於密文後就可以獲得明文；第二個條件是指不可能從密文導出解密演算法；第三個條件是指破譯者即使能加密任意數量的選擇明文，也無法破譯密碼。如果滿足以上條件，則可以公開加密演算法。

③ 公開密鑰加密技術

談起密碼演算法，有的人會覺得陌生，但一提起PGP，大多數網上朋友都很熟悉，它是一個工具軟體，向認證中心注冊後就可以用它對文件進行加解密或數字簽名，PGP所採用的是RSA演算法，以後我們會對它展開討論。密碼演算法的目的是為了保護信息的保密性、完整性和安全性，簡單地說就是信息的防偽造與防竊取，這一點在網上付費系統中特別有意義。密碼學的鼻祖可以說是資訊理論的創始人香農，他提出了一些概念和基本理論，論證了只有一種密碼演算法是理論上不可解的，那就是 One Time Padding，這種演算法要求採用一個隨機的二進制序列作為密鑰，與待加密的二進制序列按位異或，其中密鑰的長度不小於待加密的二進制序列的長度，而且一個密鑰只能使用一次。其它演算法都是理論上可解的。如DES演算法，其密鑰實際長度是56比特，作2^56次窮舉，就肯定能找到加密使用的密鑰。所以採用的密碼演算法做到事實上不可解就可以了，當一個密碼演算法已知的破解演算法的時間復雜度是指數級時，稱該演算法為事實上不可解的。順便說一下，據報道國外有人只用七個半小時成功破解了DES演算法。密碼學在不斷發展變化之中，因為人類的計算能力也像摩爾定律提到的一樣飛速發展。作為第一部分，首先談一下密碼演算法的概念。
密碼演算法可以看作是一個復雜的函數變換，C = F M, Key ),C代表密文，即加密後得到的字元序列，M代表明文即待加密的字元序列，Key表示密鑰，是秘密選定的一個字元序列。密碼學的一個原則是「一切秘密寓於密鑰之中」，演算法可以公開。當加密完成後，可以將密文通過不安全渠道送給收信人，只有擁有解密密鑰的收信人可以對密文進行解密即反變換得到明文，密鑰的傳遞必須通過安全渠道。目前流行的密碼演算法主要有DESRSA，IDEA，DSA等，還有新近的Liu氏演算法，是由華人劉尊全發明的。密碼演算法可分為傳統密碼演算法和現代密碼演算法，傳統密碼演算法的特點是加密和解密必須是同一密鑰，如DES和IDEA等；現代密碼演算法將加密密鑰與解密密鑰區分開來，且由加密密鑰事實上求不出解密密鑰。這樣一個實體只需公開其加密密鑰(稱公鑰，解密密鑰稱私鑰)即可，實體之間就可以進行秘密通信，而不象傳統密碼演算法似的在通信之前先得秘密傳遞密鑰，其中妙處一想便知。因此傳統密碼演算法又稱對稱密碼演算法(Symmetric Cryptographic Algorithms )，現代密碼演算法稱非對稱密碼演算法或公鑰密碼演算法( Public-Key Cryptographic Algorithms )，是由Diffie 和Hellman首先在1976年的美國國家計算機會議上提出這一概念的。按照加密時對明文的處理方式，密碼演算法又可分為分組密碼演算法和序列密碼演算法。分組密碼演算法是把密文分成等長的組分別加密，序列密碼演算法是一個比特一個比特地處理，用已知的密鑰隨機序列與明文按位異或。當然當分組長度為1時，二者混為一談。這些演算法以後我們都會具體討論。
RSA演算法
1978年就出現了這種演算法，它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。
RSA的安全性依賴於大數分解。公鑰和私鑰都是兩個大素數（ 大於 100個十進制位）的函數。據猜測，從一個密鑰和密文推斷出明文的難度等同於分解兩個大素數的積。
密鑰對的產生。選擇兩個大素數，p 和q 。計算：
n = p * q
然後隨機選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互質。最後，利用Euclid 演算法計算解密密鑰d, 滿足
e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )
其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。
加密信息 m（二進製表示）時，首先把m分成等長數據塊 m1 ,m2,..., mi ，塊長s，其中 2^s <= n, s 盡可能的大。對應的密文是：
ci = mi^e ( mod n ) ( a )
解密時作如下計算：
mi = ci^d ( mod n ) ( b )
RSA 可用於數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運算。
RSA 的安全性。
RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數分解。假設存在一種無須分解大數的演算法，那它肯定可以修改成為大數分解演算法。目前， RSA的一些變種演算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解140多個十進制位的大素數。因此，模數n必須選大一些，因具體適用情況而定。
RSA的速度。
由於進行的都是大數計算，使得RSA最快的情況也比DES慢上100倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。
RSA的選擇密文攻擊。
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：
( XM )^d = X^d *M^d mod n
前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特徵--每個人都能使用公鑰。但從演算法上無法解決這一問題，主要措施有兩條：一條是採用好的公鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way Hash Function對文檔作HASH處理，或同時使用不同的簽名演算法。在中提到了幾種不同類型的攻擊方法。
RSA的公共模數攻擊。
若系統中共有一個模數，只是不同的人擁有不同的e和d，系統將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。設P為信息明文，兩個加密密鑰為e1和e2，公共模數是n，則：
C1 = P^e1 mod n
C2 = P^e2 mod n
密碼分析者知道n、e1、e2、C1和C2，就能得到P。
因為e1和e2互質，故用Euclidean演算法能找到r和s，滿足：
r * e1 + s * e2 = 1
假設r為負數，需再用Euclidean演算法計算C1^(-1)，則
( C1^(-1) )^(-r) * C2^s = P mod n
另外，還有其它幾種利用公共模數攻擊的方法。總之，如果知道給定模數的一對e和d，一是有利於攻擊者分解模數，一是有利於攻擊者計算出其它成對的e』和d』，而無需分解模數。解決辦法只有一個，那就是不要共享模數n。
RSA的小指數攻擊。 有一種提高RSA速度的建議是使公鑰e取較小的值，這樣會使加密變得易於實現，速度有所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。
RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數人士傾向於因子分解不是NPC問題。
RSA的缺點主要有：A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。目前，SET(Secure Electronic Transaction)協議中要求CA採用2048比特長的密鑰，其他實體使用1024比特的密鑰。
DSS/DSA演算法
Digital Signature Algorithm
(DSA)是Schnorr和ElGamal簽名演算法的變種，被美國NIST作為DSS(Digital SignatureStandard)。演算法中應用了下述參數：
p：L bits長的素數。L是64的倍數，范圍是512到1024；
q：p - 1的160bits的素因子；
g：g = h^((p-1)/q) mod p，h滿足h < p - 1, h^((p-1)/q) mod p > 1；
x：x < q，x為私鑰 ；
y：y = g^x mod p ，( p, q, g, y )為公鑰；
H( x )：One-Way Hash函數。DSS中選用SHA( Secure Hash Algorithm )。
p, q,
g可由一組用戶共享，但在實際應用中，使用公共模數可能會帶來一定的威脅。簽名及驗證協議如下：
1. P產生隨機數k，k < q；
2. P計算 r = ( g^k mod p ) mod q
s = ( k^(-1) (H(m) + xr)) mod q
簽名結果是( m, r, s )。
3. 驗證時計算 w = s^(-1)mod q
u1 = ( H( m ) * w ) mod q
u2 = ( r * w ) mod q
v = (( g^u1 * y^u2 ) mod p ) mod q
若v = r，則認為簽名有效。
DSA是基於整數有限域離散對數難題的，其安全性與RSA相比差不多。DSA的一個重要特點是兩個素數公開，這樣，當使用別人的p和q時，即使不知道私鑰，你也能確認它們是否是隨機產生的，還是作了手腳。RSA演算法卻作不到

④ 密鑰密碼體系的公開密鑰演算法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有很好的應用。

⑤ 公開密鑰密碼體系的產生

1. 選擇兩個大素數，p 和q ，計算出n=qp，n稱為RSA演算法的模數。p，q 必須保密，一般要求p，q為安全素數，n的長度大於1024bit ，這主要是因為RSA演算法的安全性依賴於因子分解大數問題。
2. 計算n的歐拉數
φ(n)=(p-1)(q-1)
φ(n)定義為不超過n並與n互質的數的個數。
3. 然後隨機選擇加密密鑰e，從[0,φ(n)-1]中選擇一個與φ(n)互質的數e作為公開的加密指數。
4. 最後，利用Euclid 演算法計算解密密鑰d, 滿足de≡1(mod φ(n))。其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。
5.得到所需要公開密鑰和秘密密鑰：
公開密鑰（即加密密鑰） PK=（e，n）
秘密密鑰（即解密密鑰） SK=（d，n）