密碼知識

談起密碼算法，有的人會覺得陌生，但一提起PGP，大多數網上朋友都很熟悉， 它是一個工具軟件，向認證中心注冊后就可以用它對文件進行加解密或數字簽名，PGP所采用的是RSA算法，以后我們會對它展開討論。密碼算法的目的是為了保護信息的保密性、完整性和安全性，簡單地說就是信息的防偽造與防竊取，這一點在網上付費系統(tǒng)中特別有意義。密碼學的鼻祖可以說是信息論的創(chuàng)始人香農，他提出了一些概念和基本理論，論證了只有一種密碼算法是理論上不可解的，那就是 One Time Padding，這種算法要求采用一個隨機的二進制序列作為密鑰，與待加密的二進制序列按位異或，其中密鑰的長度不小于待加密的二進制序列的長度，而且一個密鑰只能使用一次。其它算法都是理論上可解的。如DES算法，其密鑰實際長度是56比特，作2^56次窮舉，就肯定能找到加密使用的密鑰。所以采用的密碼算法做到事實上不可解就可以了，當一個密碼算法已知的破解算法的時間復雜度是指數級時，稱該算法為事實上不可解的。順便說
3 G* w5 T9 c8 c) G一下，據報道國外有人只用七個半小時成功破解了DES算法。密碼學在不斷發(fā)展變化之中，因為人類的計算能力也像摩爾定律提到的一樣飛速發(fā)展。作為第一部分，首先談一下密碼算法的概念。
3 w$ K2 O1 R) r8 c" f2 z
密碼算法可以看作是一個復雜的函數變換，C = F M, Key ),C代表密文，即加密后得到的字符序列，M代表明文即待加密的字符序列，Key表示密鑰，是秘密選定的一個字符序列。密碼學的一個原則是“一切秘密寓于密鑰之中”，算法可以公開。當加密完成后，可以將密文通過不安全渠道送給收信人，只有擁有解密密鑰的收信人可以對密文進行解密即反變換得到明文，密鑰的傳遞必須通過安全渠道。目前流行的密碼算法主要有DES，RSA，IDEA，DSA等，還有新近的Liu氏算法，是由華人劉尊全發(fā)明的。密碼算法可分為傳統(tǒng)密碼算法和現代密碼算法，傳統(tǒng)密碼算法的特點是加密和解密必須是同一密鑰，如DES和IDEA等；現代密碼算法將加密密鑰與解密密鑰區(qū)分開來，且由加密密鑰事實上求不出解密密鑰。這樣一個實體只需公開其加密密鑰(稱公鑰，解密密鑰稱私鑰)即可，實體之間就可以進行秘密通信，而不象傳統(tǒng)密碼算法似的在通信之前先得秘密傳遞密鑰，其中妙處一想便知。因此傳統(tǒng)密碼算法又稱對稱密碼算法(Symmetric Cryptographic Algorithms )，現代密碼算法稱非對稱密碼算法或公鑰密碼算法( Public-Key Cryptographic Algorithms )，是由Diffie 和Hellman首先在1976年的美國國家計算機會議上提出這一概念的。按照加密時對明文的處理方式，密碼算法又可分為分組密碼算法和序列密碼算法。分組密碼算法是把密文分成等長的組分別加密，序列密碼算法是一個比特一個比特地處理，用已知的密鑰隨機序列與明文按位異或。當然當分組長度為1時，二者混為一談。這些算法以后我們都會具體討論。
2 j( x* k! z, e. k
. y, t4 C. _5 u$ ^; ?5 b8 ZRSA算法

# t! f) {- V  A1 b  b　
( [9 e9 j1 Y$ a' o/ c1978年就出現了這種算法，它是第一個既能用于數據加密也能用于數字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。

RSA的安全性依賴于大數分解。公鑰和私鑰都是兩個大素數（ 大于 100個十進制位）的函數。據猜測，從一個密鑰和密文推斷出明文的難度等同于分解兩個大素數的積。

密鑰對的產生。選擇兩個大素數，p 和q 。計算：

n = p * q

然后隨機選擇加密密鑰e，要求 e 和 ( p - 1 ) * ( q - 1 ) 互質。最后，利用Euclid 算法計算解密密鑰d, 滿足

% f& y: `$ D* V9 Y0 Y4 S$ Qe * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

  m8 G. q% V+ ^( a其中n和d也要互質。數e和n是公鑰，d是私鑰。兩個素數p和q不再需要，應該丟棄，不要讓任何人知道。

5 n) A; Z2 C4 k2 r加密信息 m（二進制表示）時，首先把m分成等長數據塊 m1 ,m2,..., mi ，塊長s，其中 2^s <= n, s 盡可能的大。對應的密文是：
% h! p; C$ v2 K$ }
# k; }3 q- Q) }; l. ^" G' l& Uci = mi^e ( mod n ) ( a )
, {3 I% |% S8 y6 A5 t3 \
解密時作如下計算：
+ P$ V, G& @2 Y3 i- w! J# k
mi = ci^d ( mod n ) ( b )
, x, d7 _7 z& T
- x* G: o: e; x) ^8 I% k& m: }RSA 可用于數字簽名，方案是用 ( a ) 式簽名， ( b )式驗證。具體操作時考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運算。
" G" }: Q  N4 `* ~$ ]3 \1 a/ m
+ M/ Q& ^; a1 b" \* }4 eRSA 的安全性。
  ]- \1 s3 G: x+ fRSA的安全性依賴于大數分解，但是否等同于大數分解一直未能得到理論上的證明，因為沒有證明破解RSA就一定需要作大數分解。假設存在一種無須分解大數的算法，那它肯定可以修改成為大數分解算法。目前， RSA的一些變種算法已被證明等價于大數分解。不管怎樣，分解n是最顯然的攻擊方法?，F在，人們已能分解140多個十進制位的大素數。因此，模數n必須選大一些，因具體適用情況而定。
( x4 s) f: p/ Z( t1 \: Q
; Z: e4 f7 c) cRSA的速度。
由于進行的都是大數計算，使得RSA最快的情況也比DES慢上100倍，無論是軟件還是硬件實現。速度一直是RSA的缺陷。一般來說只用于少量數據加密。

  y6 l3 Q9 F# B& b6 hRSA的選擇密文攻擊。
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實體簽署。然后，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構：

( XM )^d = X^d *M^d mod n
, F* Q! _, W- U, K: J0 M
' R" W/ b2 }& V- E前面已經提到，這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征--每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way HashFunction
對文檔作HASH處理，或同時使用不同的簽名算法。在中提到了幾種不同類型的攻擊方法。 　　

RSA的公共模數攻擊。
* x: L6 d$ q* F+ F: k若系統(tǒng)中共有一個模數，只是不同的人擁有不同的e和d，系統(tǒng)將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。
- G  s2 u% E6 ^; n5 E2 i0 T0 \