密碼知識(shí)

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

$ ]% Z+ `) E. ARSA算法

& n4 i4 L- v1 v' z5 m　
& D# {/ S" [! I+ X; h2 c3 Z$ H0 G1978年就出現(xiàn)了這種算法，它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名的算法。它易于理解和操作，也很流行。算法的名字以發(fā)明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理論上的證明。
! |! M7 q9 X2 C- }& m- l. D
8 \; P7 h) m1 K5 |( ]8 |RSA的安全性依賴(lài)于大數(shù)分解。公鑰和私鑰都是兩個(gè)大素?cái)?shù)（ 大于 100個(gè)十進(jìn)制位）的函數(shù)。據(jù)猜測(cè)，從一個(gè)密鑰和密文推斷出明文的難度等同于分解兩個(gè)大素?cái)?shù)的積。
6 g% a, z4 t6 Y% |
0 L5 N7 ]. f( _9 e: e; h密鑰對(duì)的產(chǎn)生。選擇兩個(gè)大素?cái)?shù)，p 和q 。計(jì)算：

8 C" W( w& t' O  In = p * q

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

e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )

其中n和d也要互質(zhì)。數(shù)e和n是公鑰，d是私鑰。兩個(gè)素?cái)?shù)p和q不再需要，應(yīng)該丟棄，不要讓任何人知道。
) b% X6 K6 K9 ]7 K% K- l1 r
( u/ s; p! O2 ]4 F7 M* k0 Y3 r1 H加密信息 m（二進(jìn)制表示）時(shí)，首先把m分成等長(zhǎng)數(shù)據(jù)塊 m1 ,m2,..., mi ，塊長(zhǎng)s，其中 2^s <= n, s 盡可能的大。對(duì)應(yīng)的密文是：

$ e0 q" f$ j5 `" j9 D& p/ n: Cci = mi^e ( mod n ) ( a )

9 L8 L0 t, ~  `: w解密時(shí)作如下計(jì)算：
* b+ M, C6 }$ s1 U$ |
/ i- p  ~$ _) i# ^% g  D8 ymi = ci^d ( mod n ) ( b )
- g6 R% b9 u$ b+ h  }
RSA 可用于數(shù)字簽名，方案是用 ( a ) 式簽名， ( b )式驗(yàn)證。具體操作時(shí)考慮到安全性和 m信息量較大等因素，一般是先作 HASH 運(yùn)算。

RSA 的安全性。
9 Y4 N2 a( u, s* q- B: _* j* MRSA的安全性依賴(lài)于大數(shù)分解，但是否等同于大數(shù)分解一直未能得到理論上的證明，因?yàn)闆](méi)有證明破解RSA就一定需要作大數(shù)分解。假設(shè)存在一種無(wú)須分解大數(shù)的算法，那它肯定可以修改成為大數(shù)分解算法。目前， RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。不管怎樣，分解n是最顯然的攻擊方法。現(xiàn)在，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，模數(shù)n必須選大一些，因具體適用情況而定。
! v. f3 d' k8 c1 Z$ P8 d
RSA的速度。
由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上100倍，無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來(lái)說(shuō)只用于少量數(shù)據(jù)加密。
$ n, `9 V. q% S8 N: O7 R6 b- j
RSA的選擇密文攻擊。
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過(guò)計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：

( XM )^d = X^d *M^d mod n
" V0 c* K# ?' N* M1 b5 M2 s
8 n; W9 i; l5 Y  I2 [. ~# N前面已經(jīng)提到，這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無(wú)法解決這一問(wèn)題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密，不對(duì)自己一無(wú)所知的信息簽名；另一條是決不對(duì)陌生人送來(lái)的隨機(jī)文檔簽名，簽名時(shí)首先使用One-Way HashFunction
對(duì)文檔作HASH處理，或同時(shí)使用不同的簽名算法。在中提到了幾種不同類(lèi)型的攻擊方法。 　　

RSA的公共模數(shù)攻擊。
若系統(tǒng)中共有一個(gè)模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那末該信息無(wú)需私鑰就可得到恢復(fù)。
! T$ O- a! W* f- T4 @# x+ T$ O