第2章信息加密技術(shù)基礎(chǔ)-課件

1、第二章信息加密技術(shù)基礎(chǔ) 引 言 信息加密是網(wǎng)絡(luò)安全體系中重要機(jī)制之一。信息加密的目的是為了保持信息的機(jī)密性，使用恰當(dāng)?shù)募用軜?biāo)準(zhǔn)將在計(jì)算機(jī)環(huán)境中增加安全性。信息加密通過使用一種編碼而使存儲(chǔ)或傳輸?shù)男畔⒆優(yōu)椴豢勺x的信息，解密是一個(gè)相反的過程。這些編碼就是將明文變成密文的加密算法或數(shù)學(xué)方法。引 言 (續(xù)) 加密編碼在Shannon的信息論中有針對(duì)性的闡述，數(shù)論及基礎(chǔ)代數(shù)是加密算法的理論基礎(chǔ)。要將一段信息加密或解密，你會(huì)要用到密鑰，它是一個(gè)很大的值。一般來說，密鑰越大，加密就越健壯。一般來說加密體制分為對(duì)稱密鑰加密和公用密鑰加密，對(duì)稱密鑰加密在密鑰方面有一定的缺陷，但執(zhí)行效率高；公用密鑰加密加密執(zhí)行效

2、率底，但保密性強(qiáng)，在報(bào)文和網(wǎng)絡(luò)方面對(duì)小量信息加密非常有效.2.1 信息加密理論基礎(chǔ) 信息安全的核心技術(shù)之一是加密技術(shù)，它涉及信息論、基礎(chǔ)數(shù)論和算法復(fù)雜性等多方面基礎(chǔ)知識(shí)。隨著計(jì)算機(jī)網(wǎng)絡(luò)不斷滲透到各個(gè)領(lǐng)域，加密技術(shù)的應(yīng)用也隨之?dāng)U大，應(yīng)用加密基礎(chǔ)理論知識(shí)，深入探索可靠可行的加密方法，應(yīng)用于數(shù)字簽名、身份鑒別等新技術(shù)中成為網(wǎng)絡(luò)安全研究重要的一個(gè)方面。加密的理論依據(jù) 密碼學(xué)問題就是隨機(jī)性的利用問題. 差不多每臺(tái)使用加密技術(shù)的計(jì)算機(jī)安全系統(tǒng)都需要隨機(jī)數(shù)，供密鑰、協(xié)議中的基礎(chǔ)參量等使用或者用做輔助信息或者初始化向量。這些系統(tǒng)的安全也經(jīng)常依賴于這些隨機(jī)數(shù)的隨機(jī)性及被保護(hù)程度。簡單的加密舉例 中秋日月 編碼

3、密鑰 密文編碼 詩 月明明日 010101 10 111111 明日月明 101010 000000 ？ 明日明日 101101 000111 日明月明 110010 011000 通過這個(gè)例子我們看到一個(gè)簡單的加密過程，原來的詩通過與密鑰的模二運(yùn)算實(shí)現(xiàn)了加密。2.1.1 信息編碼基礎(chǔ)知識(shí) 第二次世界大戰(zhàn)期間，美國為了提高信息儲(chǔ)存和傳遞的效率，發(fā)明了多種新的編碼方法，奠定了現(xiàn)代信息科學(xué)技術(shù)的基礎(chǔ)。Shannon還于1949年發(fā)表了“保密系統(tǒng)的通信理論”一文，奠定了現(xiàn)代密碼學(xué)基礎(chǔ)從而對(duì)加密過程中信息編碼有了明確的分析。在該文中他從信息論觀點(diǎn)，對(duì)信息系統(tǒng)的保密性問題作了全面而深刻的闡述。 1. 信

4、 息 熵 基 本 知 識(shí) 信息論中最重要的內(nèi)容，是如何認(rèn)識(shí)和使用信息熵來表現(xiàn)信息。 這里用Shannon最喜歡用的猜謎方法來說明信息熵的基本概念。假如有：“我們大_都喜_使_計(jì)_機(jī)來管_數(shù)_?！?不用很多努力，就可以猜出完整的句子:“我們大家都喜歡使用計(jì)算機(jī)來管理數(shù)據(jù)?！?Shannon在信息論中指出，能猜出來的字符不運(yùn)載信息，而不能猜出來的字符運(yùn)載信息。1. 信 息 熵 基 本 知 識(shí)(續(xù)) 空格所隱藏的字符屬于多余度字符，不用那些字符也能運(yùn)載該句子的全部信息，比如：“我_大_使_機(jī)來_數(shù)_?！本秃茈y猜出完整的句子，在信息傳遞的時(shí)候，也很難做檢錯(cuò)和抗錯(cuò)。因此，保留一定的多余度(或冗余度)是非

5、常重要的。 2. 信息量和信息熵基本定義(1) 信息熵（information entropy）是對(duì)信息狀態(tài)“無序”與“不確定”的度量（從本質(zhì)上講，熵不是對(duì)信息的度量，但信息的增加而使產(chǎn)生的熵減小，熵可以用來度量信息的增益）。 2. 信息量和信息熵基本定義(2) 定義：給定一離散集合X=xi; i=1,2,n，令xi出現(xiàn)的概率是 且 。事件xi包含的信息量 通常=2，此時(shí)相應(yīng)的信息量單位是bit。Shannon定義信息的數(shù)學(xué)期望為信息熵，即信源的平均信息量。 (2.1)2. 信息量和信息熵基本定義(3) 定義：將集合X中事件所包含的信息量統(tǒng)計(jì)平均，則平均值定義為集合X的熵.信息熵表征了信源整體

6、的統(tǒng)計(jì)特征，集合X的熵H（x）表示X中事件所包含的平均信息量，或總體的平均不確定性的量度。(2.2)2. 信息量和信息熵基本定義(4) 對(duì)某一特定的信源，其信息熵只有一個(gè)，因統(tǒng)計(jì)特性不同，其熵也不同。例如，兩個(gè)信源，其概率空間分別為：2. 信息量和信息熵基本定義(5) 則信息熵為： 可見， ,說明信源 比信源 的平均不確定性要大，即在事件發(fā)生之前，分析信源 ，由于事件 是等概率的，難以猜測哪一個(gè)事件會(huì)發(fā)生.2. 信息量和信息熵基本定義(6) 而信源 ，雖然也存在不確定性，但大致可以知道, 出現(xiàn)的可能性要大。正如兩場比賽，其中一場，雙方勢均力敵；而另一場雙方實(shí)力懸殊很大。當(dāng)然,人們希望看第一場，

7、因?yàn)閯儇?fù)難卜，一旦賽完，人們獲得信息量大。也可以這樣理解，信息熵 表征了變量 的隨機(jī)性。因此，熵反映了變量的隨機(jī)性，也是表征隨機(jī)變量統(tǒng)計(jì)特性的一個(gè)特征參數(shù)。3. 信息熵的基本性質(zhì)(1)對(duì)稱性 當(dāng)概率空間中 序任意互換時(shí)，熵函數(shù)的值不變，例如下面兩個(gè)信源空間:3. 信息熵的基本性質(zhì)(2) 其信息熵 .該性質(zhì)說明，熵只與隨機(jī)變量的總體結(jié)構(gòu)有關(guān)，與信源總體的統(tǒng)計(jì)特性有關(guān)，同時(shí)也說明所定義的熵有其局限性，它不能描述事件本身的主觀意義。3. 信息熵的基本性質(zhì)(3)確定性 如果信源的輸出只有一個(gè)狀態(tài)是必然的, 即 則信源的熵: 此性質(zhì)表明，信源的輸出雖有不同形態(tài)，但其中一種是必然的，意味著其他狀態(tài)不可能出

8、現(xiàn)。那么，這個(gè)信源是一個(gè)確知信源，其熵為零。 (2.3)3. 信息熵的基本性質(zhì)(4)非負(fù)性 即 。 因?yàn)殡S機(jī)變量 的所有取值的概率分布為 ，當(dāng)取對(duì)數(shù)的底大于時(shí)， ,而 ,則得到的熵是正值，只有當(dāng)隨機(jī)變量是一確知量時(shí)，熵才等于零。這種非負(fù)性對(duì)于離散信源的熵來說，這一性質(zhì)并不存在。 3. 信息熵的基本性質(zhì)(5)可加性 獨(dú)立信源 和 的聯(lián)合信源的熵等于它們各自的熵之和。 如果有兩個(gè)隨機(jī)變量 和 ， 它們彼此是統(tǒng)計(jì)獨(dú)立的，即 的概率分布為 ,而 的分布概率為 ,則聯(lián)合信源的熵: 可加性是熵函數(shù)的一個(gè)重要特性，正因?yàn)橛锌杉有?，所以可以證明熵函數(shù)的形式是唯一的。 3. 信息熵的基本性質(zhì)(6)極值性 信源各

9、個(gè)狀態(tài)為零概率分布時(shí)，熵值最大，并且等于信源輸出狀態(tài)數(shù)，因?yàn)?當(dāng) 時(shí)， (2.5)例 題 例，信源有兩種狀態(tài)時(shí)，概率空間 其 與 關(guān)系如圖所示,，當(dāng) =1/2時(shí)熵有最大值；當(dāng)信源輸出是確定的，即 ，則 ，此時(shí)表明該信源不提供任何信息；反之，當(dāng)信源輸出為等概率發(fā)生時(shí)，即 時(shí)信源的熵達(dá)到最大值，等于1bit信息量。 信息熵函數(shù)曲線P(x)00.51明文H(x)4. 信息熵在信息加密編碼中的作用(1) 通過熵和信息量的概念，可計(jì)算加密系統(tǒng)中各部分的熵。令明文熵為 ，密鑰熵 ，密文熵 。這里M、K和C分別是明文、密鑰和密文空間，m、k、c分別是它們的字母集，l ,r和v分別是明文、密鑰、和密文的長度。

10、則明文和密文之間的互信息以及密鑰與密文之間的互信息分別是：(2.6)(2.7)4. 信息熵在信息加密編碼中的作用(2) 因?yàn)橹灰芪摹⒚荑€確定后，明文也就得到了，所以 ,故 定理：對(duì)任意加密系統(tǒng) 從該理論我們可以看出，密鑰熵越大，密文中所包含的明文信息量就越小。一個(gè)加密系統(tǒng)中，若其密文與明文之間的互信息 ，則密碼分析者無論截獲多大的密文，均不能得到有關(guān)明文的任何信息。這種加密系統(tǒng)稱為完善加密系統(tǒng)，或無條件加密系統(tǒng)。(2.8)4. 信息熵在信息加密編碼中的作用(3) 在對(duì)密文攻擊下，完善加密系統(tǒng)是安全的，但它不能保證在已知明文或選擇性明文攻擊下也是安全的。因此，完善保密系統(tǒng)存在的必要條件是 證明

11、：若 ，則由前一個(gè)定理可得， ，所以 的必要條件是 (2.9)2.1.2 數(shù)論基本術(shù)語數(shù)論是研究整數(shù)性質(zhì)的一個(gè)數(shù)學(xué)分支，同時(shí)也是加密技術(shù)的基礎(chǔ)學(xué)科之一。首先介紹一些數(shù)論的基本知識(shí).1. 整 數(shù)定義：設(shè) 。如果存在 使得 ，那么就說b 可以被a 整除，記為 ，且稱b是a的倍數(shù),a 是b的因數(shù)(或稱約數(shù)、除數(shù)、因子) 。 b不能被a整除可以記作dFa。由定義及乘法運(yùn)算的性質(zhì)，可推出整除關(guān)系具有以下性質(zhì)（注：符號(hào) 本身包含了條件 ）：（1） ；（2）如果 且 ，則 ；（3）設(shè) ,那么 與 等價(jià);（4）如果 且 ,則對(duì)所有的 ,有 ;（5）設(shè) ,如果 ,那么 ;2. 素 數(shù) 定義:設(shè)整數(shù) 。如果它除了

12、顯然因數(shù) 外沒有其他的因數(shù)，則p就稱為是素?cái)?shù)，也叫不可約數(shù)。若 ， 且a不是素?cái)?shù)，則a稱為合數(shù)。 關(guān)于素?cái)?shù)，有以下性質(zhì)：（1）如果p是素?cái)?shù)，且 ，則 或 ，即p至少整除a與b中的一個(gè)。（2）任何一個(gè)整數(shù) ，均可以分解成素?cái)?shù)冪之積：（3）若不計(jì)因數(shù)的順序，這個(gè)分解式是唯一的。其中 , 是兩兩互不相同的素?cái)?shù)， 是正整數(shù)。（4）素?cái)?shù)有無窮多個(gè)。（5）設(shè) 表示不大于 的素?cái)?shù)的數(shù)目，則 。3. 同 余 設(shè) ，如果 ，則稱a和b模n同余，記為 ，整數(shù)n稱為模數(shù)。由 于 等價(jià)于 ，所以 與 等價(jià)。因此，一般我們總假定 。如果 ，我們稱b是a對(duì)模n的最小非負(fù)剩余，有時(shí)也稱b為a對(duì)模n的余數(shù)。同余式的一些基本性

13、質(zhì)（1）反身性: ；（2）對(duì)稱性:如果 ，那么 ；（3）傳遞性:如果 ， ,那么 ；（4）如果 ， 那么 ； 。（5）如果 ， ，gcd ，(兩個(gè)不同時(shí)為0的整數(shù)a與b的最大公約數(shù)表示成gcd(a,b)那么 ，存在 ,當(dāng)且僅當(dāng)gcd 。一些關(guān)于同余的基本概念(1) 同余類 可用其中任一元素a(經(jīng)常取 )代替，記作 。于是 從 中分別取一個(gè)數(shù)作為代表構(gòu)成一個(gè)集合，稱為模n的一個(gè)完全剩余系， 記為 ，稱為模n的非負(fù)最小完全剩余系。 (2.11)一些關(guān)于同余的基本概念(2) 在模n的完全剩余系中，去掉那些與n不互素的數(shù)，剩下的部分稱為模n的簡化剩余系； 的簡化剩余系記為 ，讀為模n的非負(fù)最小簡化剩余

14、系。顯然, 中的元便是不超過n并與n互素的那些數(shù)，它們的個(gè)數(shù)等于歐拉函數(shù) 的值。（歐拉函數(shù)的定義為: 小于自然數(shù)N并與N互質(zhì)(除1以外無其它公因子)的自然數(shù)的個(gè)數(shù)用函數(shù) 表示,稱為歐拉函數(shù)。歐拉函數(shù)的具體性質(zhì)會(huì)在后面第6小節(jié)進(jìn)行闡述）4. 模 運(yùn) 算 給定正整數(shù)n，對(duì)任意a，若存在q，使得 則稱r是a關(guān)于模n的余數(shù)，記為 。 若 則稱整數(shù)a，b同余，記為 整數(shù)集中所有與數(shù)a同余的整數(shù)集合稱為a的同余類，記為 。模 運(yùn) 算 的 性 質(zhì)（1） 當(dāng)且僅當(dāng) 。（2） 當(dāng)且僅當(dāng) 。（3）如果 ， ，則 。 a模n的運(yùn)算給出了a對(duì)模n的余數(shù)。注意：模運(yùn)算的結(jié)果是從0到 的一個(gè)整數(shù)。模運(yùn)算就像普通的運(yùn)算一樣

15、，它是可交換，可結(jié)合，可分配的。而且，對(duì)每一個(gè)中間結(jié)果進(jìn)行模m運(yùn)算，其作用與先進(jìn)行全部運(yùn)算，然后再進(jìn)行模m運(yùn)算所得到結(jié)果是一樣的。5. 最大公約數(shù)與最小公倍數(shù) 設(shè) ， 是兩個(gè)整數(shù)，如果 且 ，那么就稱b是 和 的公約數(shù).一般的，設(shè) ，是K個(gè)整數(shù)，如果 那么就稱b是 的公約數(shù)。因?yàn)閷?duì)于任意一個(gè)不等于零的整數(shù)，它的因數(shù)是有限的。所以，任意一對(duì)整數(shù) ，其中一個(gè)不為零時(shí)，它們的公約數(shù)的個(gè)數(shù)也必定是有限的；同理，當(dāng) 中有一個(gè)不為零時(shí)，它們的公約數(shù)是有限的.這樣,我們引入最大公約數(shù)的概念。 定義: 設(shè) ， 是兩個(gè)整數(shù)，我們把 和 的公約數(shù)中最大的數(shù)稱為 和 的最大公約數(shù)，記為( , )或 當(dāng) 時(shí)，我們稱

16、和 是互素的。 顯然最 大 公 約 數(shù) 的 性 質(zhì)（1）（2）若 | ,j=2,k ，則（3）任意的整數(shù)x, 有（4）對(duì)任意的整數(shù)x,有 （5）設(shè) , 是不都為零的整數(shù)，則一定存在一對(duì)整數(shù) , ，使得： 最 小 公 倍 數(shù) 的 概 念 設(shè) ， 是兩個(gè)均不等于零的整數(shù)，如果 且 ，那么 1 就稱為是 和 的公倍數(shù)，一般地，設(shè) 是k個(gè)均不等于零的整數(shù)。 如果 ，則稱 l是 的公倍數(shù)。公倍數(shù)的集合是無窮集合，但根據(jù)自然數(shù)的理論，存在最小的正的公倍數(shù)。我們把 和 的正的公倍數(shù)中最小的數(shù)稱為 和 的最小公倍數(shù)，記為 或6. 歐拉（Euler）函數(shù) 歐拉（Euler）函數(shù) 設(shè)n1,歐拉函數(shù) 表示在區(qū)間 中

17、與n互素的整數(shù)的個(gè)數(shù)。 歐拉函數(shù) 具有以下性質(zhì)： (1)如果p是素?cái)?shù)，則 ； (2)如果p是素?cái)?shù)， 。那么 ； (3)對(duì)于整數(shù) , 根據(jù)算術(shù)基本定理，n可以分解成惟一的形如 的分解式，則 (4)若 和 互素，則 。2.1.3 算法復(fù)雜性基礎(chǔ)知識(shí) 所謂問題，是指一個(gè)要求給出解釋的一般性提問，通常含有若干個(gè)未定參數(shù)或自由變量。它由兩個(gè)要素組成 ，第一個(gè)要素是描述所有的參數(shù)，也就是對(duì)所有未定參數(shù)的一般性描述;第二個(gè)要素是解答必須滿足的性質(zhì)。一個(gè)問題 可以看成是由無窮多個(gè)問題實(shí)例組成的一個(gè)類。1. 算 法 的 定 義 所謂算法是由明確指出操作的規(guī)則所組成的若干語句的集合，只要按照規(guī)則一步一步執(zhí)行一定數(shù)

18、目的語句，便可求出問題的答案。通常的計(jì)算機(jī)程序都可以看作是算法的表達(dá)形式，在問題的兩要素中，對(duì)算法而言，第一個(gè)要素就是“輸入”，第二個(gè)要素就是“輸出”。如果把問題P的任意一個(gè)實(shí)例作為算法A的輸入，A在有限步驟之內(nèi)總能輸出關(guān)于此實(shí)例的正確答案，我們就說算法A可解問題P。對(duì)于一個(gè)問題P，如果存在一個(gè)算法A可解問題P，我們稱問題P是算法可解的。2. 算 法 復(fù) 雜 性 算法的復(fù)雜性表征了算法在實(shí)際執(zhí)行時(shí)所需計(jì)算能力方面的信息 ， 通常它由該算法所要求的最大時(shí)間與存取空間來確定。 由于算法所需的時(shí)間和空間往往取決于問題實(shí)例的規(guī)模n (n表示了該實(shí)例的輸入數(shù)據(jù)長度)，同時(shí)，算法在用于相同規(guī)模n的不同實(shí)例

19、時(shí)。其時(shí)間和空間需求也可能會(huì)有很大差異，因此，實(shí)際中我們常常研究的是算法關(guān)于輸入規(guī)模 的所有實(shí)例的時(shí)間與空間需求的平均值。算 法 復(fù) 雜 性 的 構(gòu) 成 通常情況下，一個(gè)算法的計(jì)算復(fù)雜性由兩個(gè)變量度量：時(shí)間復(fù)雜性 和空間復(fù)雜性 。它們定義如下：（1）時(shí)間復(fù)雜性 ：以某特定的基本步驟為單元，完成計(jì)算過程所需的總單元數(shù)稱為算法的時(shí)間復(fù)雜性，或時(shí)間復(fù)雜度。n為輸入的規(guī)模或尺寸。（2）空間復(fù)雜性 :以某特定的基本存儲(chǔ)空間為單元，完成計(jì)算過程所用的存儲(chǔ)單元數(shù)，稱為算法的空間復(fù)雜性或空間復(fù)雜度。n是輸入的規(guī)?；虺叽纭Ｋ惴◤?fù)雜性的基本符號(hào)（1） 一個(gè)算法的計(jì)算復(fù)雜性用“O”符號(hào)表示其數(shù)量級(jí)?！癘”的意思是：

20、對(duì)于兩個(gè)任意的實(shí)值函數(shù)f和g，若記號(hào) ，則存在有一個(gè)值a，對(duì)充分大的n，有 。計(jì)算復(fù)雜性的數(shù)量級(jí)就是這種類型的函數(shù)，即當(dāng)n變大時(shí)增長得最快的函數(shù)，所有常數(shù)和較低階形式的函數(shù)可以忽略不計(jì)。算法復(fù)雜性的基本符號(hào)（2） 另一個(gè)符號(hào)是“o”。它的定義是： 當(dāng)且僅當(dāng) ，這意味著在 時(shí)， 比 可以忽略不計(jì)。 時(shí)間復(fù)雜度 有時(shí)也用工作因子W表示，這時(shí) 。如果一個(gè)算法的復(fù)雜性不依賴于n，那么它是常數(shù)級(jí)的用 表示之，而 表示復(fù)雜性隨n線性增長，因而是線性型算法。復(fù)雜性隨n線性增長的其他一些算法也稱為二次方或三次方等，所有這些算法都是多項(xiàng)式的，它們的時(shí)間復(fù)雜性是 。有多項(xiàng)式時(shí)間復(fù)雜性的算法稱為多項(xiàng)式時(shí)間算法或有效

21、算法。3. 問 題 的 復(fù) 雜 性 問題的復(fù)雜性是問題固有的性質(zhì)。問題的復(fù)雜性理論利用算法復(fù)雜性作為工具，將大量典型的問題按照求解的代價(jià)進(jìn)行分類。問題的復(fù)雜性由在圖靈機(jī)上解其最難實(shí)例所需的最小時(shí)間與空間決定，還可以理解為由解該問題的最有效的算法所需的時(shí)間與空間來度量。N P 問 題 在確定型圖靈機(jī)上可用多項(xiàng)式時(shí)間求解的問題，稱為易處理的問題。易處理的問題的全體稱為確定性多項(xiàng)式時(shí)間可解類，記為P類。在非確定性圖靈機(jī)上可用多項(xiàng)式時(shí)間求解的問題，稱為非確定性多項(xiàng)式時(shí)間可解問題，記為NP問題。NP問題的全體稱為非確定性多項(xiàng)式時(shí)間可解類，記為NP類。顯然， ，因?yàn)樵诖_定型圖靈機(jī)上多項(xiàng)式時(shí)間可解的任何問題

22、在非確定型圖靈機(jī)上也是多項(xiàng)式時(shí)間可解的。N P C 問 題 NP類中還有一類問題稱為NP完全類，記為NPC。所有的NP問題都可以通過多項(xiàng)式時(shí)間轉(zhuǎn)換為NPC中的問題。NPC是NP類中困難程度最大的一類問題,但NPC中的問題困難程度相當(dāng)，都可以多項(xiàng)式時(shí)間轉(zhuǎn)化為稱為可滿足性問題的NPC問題，此類NPC具有如下性質(zhì)，若其中的任何一個(gè)問題屬于P，則所有的NP問題都屬于P，且 ?，F(xiàn)在的密碼算法的安全性都是基于NPC問題的，破譯一個(gè)密碼相當(dāng)于求解一個(gè)NPC問題,如果 ，則破譯密碼就是一件很容易的事情.2.2 信息加密方式與標(biāo)準(zhǔn) 經(jīng)典的信息加密理論主要用于通信保密，而現(xiàn)代信息加密技術(shù)的應(yīng)用已深入到信息安全的各

23、個(gè)環(huán)節(jié)和對(duì)象，信息的加密方式和標(biāo)準(zhǔn)也有了深入廣泛的發(fā)展，特別是現(xiàn)代加密和信息隱藏技術(shù)的結(jié)合，實(shí)現(xiàn)信息隱蔽傳輸使人類對(duì)信息的加密技術(shù)有了新的認(rèn)識(shí)和要求，下面介紹信息加密技術(shù)的基本概念、方式和標(biāo)準(zhǔn)。2.2.1 信息加密基本概念（1） 研究安全信息的加密技術(shù)和研究破解安全信息密碼的密碼分析技術(shù)的學(xué)科稱為密碼學(xué)。信息加密是通過使用一種編碼而使某些可讀的信息(明文)變?yōu)椴豢勺x的信息(密文)。這些編碼就是將明文變成密文的加密算法(也稱為密碼)或數(shù)學(xué)方法。密碼使用隱蔽語言、文字、圖象的特種符號(hào)，目標(biāo)是接收數(shù)據(jù)作為輸入，產(chǎn)生密文作為輸出，以便數(shù)據(jù)的原始意義得以隱藏。在計(jì)算機(jī)通訊中，采用密碼（密鑰為參數(shù)）將信息

24、隱蔽起來，再將隱蔽后的信息傳輸出去，使信息在傳輸過程中即使被竊取或載獲，也不能了解信息的內(nèi)容，從而保證信息傳輸?shù)陌踩?.2.1 信息加密基本概念（2） 通信兩端將信息編碼時(shí)，發(fā)送端使用簡單的信息加密；接收端收到傳來的信息后通過解密看到編碼前的信息，整個(gè)過程中加密或解密是由密鑰控制實(shí)現(xiàn)的。密鑰是用戶按照一種密碼體制隨機(jī)選取，它通常是一隨機(jī)字符串，是控制明文變換（加密）和密文變換（解密）的唯一參數(shù)。密鑰全體稱為密鑰空間。一般來說，密鑰越大，加密就越健壯。加密系統(tǒng)的組成部分 如上所述，一個(gè)加密系統(tǒng)實(shí)際上是某種加密算法在密鑰控制下實(shí)現(xiàn)的從明文到密文的映射，它至少包括下面四個(gè)組成部分： （1）加密的報(bào)

25、文，也稱明文； （2）加密后的報(bào)文，也稱密文； （3）加密解密設(shè)備或算法； （4）加密解密的密鑰； 一般情況下，密鑰由K表示，明文由m表示，加密算法由 ( ) 表示，解密算法由 ( ) 表示，； 則， ( ( m ) =m 加密系統(tǒng)示意圖一個(gè)完整的加密系統(tǒng)如下圖所示:信源加密解密信宿密文明文竊聽干擾明文密鑰K1密鑰K2圖2.2 加密系統(tǒng)示意圖加密系統(tǒng)的安全規(guī)則（1） 任何一個(gè)加密系統(tǒng)必須基本具備四個(gè)安全規(guī)則： （1）機(jī)密性(confidentiality)：加密系統(tǒng)在信息的傳送中提供一個(gè)或一系列密鑰來把信息通過密碼運(yùn)算譯成密文，使信息不會(huì)被非預(yù)期的人員所讀取，只有發(fā)送者和接收者應(yīng)該知曉此信息的

26、內(nèi)容。加密系統(tǒng)的安全規(guī)則（2） （2）完整性(integrity)：數(shù)據(jù)在傳送過程中不應(yīng)被破壞，收到的信宿數(shù)據(jù)與信源數(shù)據(jù)是一致的。應(yīng)該選取健壯的密碼和加密密鑰，以確保入侵者無法攻破密鑰或找出一個(gè)相同的加密算法，阻止入侵者會(huì)改變數(shù)據(jù)后對(duì)其重新加密。有時(shí)，數(shù)據(jù)完整性可以通過適當(dāng)?shù)姆椒ㄔ谛畔⑦€未被完全修改時(shí)檢測到，如：密碼散列函數(shù)是單向密碼，它為明文產(chǎn)生惟一的“指紋”，當(dāng)明文被攔截和讀取，要修改它將改變散列，致使有意向的接收者很容易看出散列之間的差異。加密系統(tǒng)的安全規(guī)則（3） （3）認(rèn)證性(authentication) ：加密系統(tǒng)應(yīng)該提供數(shù)字簽名技術(shù)來使接收信息用戶驗(yàn)證是誰發(fā)送的信息，確定信息是否

27、被第三者篡改。只要密鑰還未泄露或與別人共享，發(fā)送者就不能否認(rèn)他發(fā)送的數(shù)據(jù)。實(shí)際應(yīng)用中，假如發(fā)送者和接收者都使用一個(gè)對(duì)稱密鑰，對(duì)于整體信息加密或計(jì)算機(jī)網(wǎng)絡(luò)上的鏈路級(jí)加密，在兩個(gè)路由器之間建立一個(gè)加密會(huì)話，以通過因特網(wǎng)發(fā)送加密信息。連接到網(wǎng)絡(luò)的計(jì)算機(jī)發(fā)送明文給路由器，明文被轉(zhuǎn)換為密文，然后通過因特網(wǎng)發(fā)送到另一端的路由器。在整個(gè)加密數(shù)據(jù)形成和傳遞過程中，加密方網(wǎng)絡(luò)內(nèi)部和非加密方的任一節(jié)點(diǎn)都能插入信息，并在這一層次分析，但對(duì)于接收者這一節(jié)點(diǎn)來說你只能判定信息是否來自某個(gè)特定的網(wǎng)絡(luò)，而要確認(rèn)信息的發(fā)送節(jié)點(diǎn)，這將使驗(yàn)證機(jī)制變得很復(fù)雜。加密系統(tǒng)的安全規(guī)則（4） （4）非否定(non-repudiation)

28、：加密系統(tǒng)除了應(yīng)該驗(yàn)證是誰發(fā)送的信息外，還要進(jìn)一步驗(yàn)證收到的信息是否來自可信的源端，實(shí)際上是通過必要的認(rèn)證確認(rèn)信息發(fā)送者是否可信?，F(xiàn)代健壯的驗(yàn)證方法用加密算法來比較一些已知的信息段，如PIN(個(gè)人識(shí)別號(hào))判斷源端是否可信。 非否定規(guī)則應(yīng)屬于認(rèn)證性規(guī)則中的一部分。一般來說，前三個(gè)規(guī)則一起被稱為CIA 。從技術(shù)的角度來看，所有的加密都提供了私有性和完整性，其余的均由此衍生，這包括非否定和認(rèn)證性規(guī)則。2.2.2 信息加密方式1. 信息加密方式分類 對(duì)存儲(chǔ)的文件和網(wǎng)絡(luò)中傳輸?shù)臄?shù)據(jù)包實(shí)施信息加密，其加密方式可以根據(jù)加密系統(tǒng)不同的特征劃分： （1）按密鑰方式劃分 對(duì)稱式加密：收發(fā)雙方使用相同密鑰。加密和解

29、密使用同一密鑰。加密算法和解密算法在對(duì)稱式加密中是相同的，加密和解密使用同一密鑰K表示。 非對(duì)稱式加密：也稱公用密鑰加密，加密和解密使用不同密鑰。它通常有兩個(gè)密鑰，稱為“公鑰”和“私鑰”。它們兩個(gè)必需配對(duì)使用，否則不能打開加密文件。這里的“公鑰”是指可以對(duì)外公布的，“私鑰”則不對(duì)外公布，只有持有人知道。加密算法和解密算法在非對(duì)稱式加密中是不相同的；K1是加密密鑰,是公開的，稱為公鑰，K2是解密密鑰，稱為私鑰，則須保密。2種不同方式的加密示意圖 明文解密密鑰K2明文 加密 密鑰K2KK密文傳輸圖2.2 對(duì)稱式加密示意圖明文 解密 密鑰K2K1K2加密 密鑰K2明文 圖2.3 非對(duì)稱式加密示意圖1

30、. 信息加密方式分類 （2）按保密程度劃分 理論上保密的加密：無論獲取多少密文和有多大的計(jì)算能力，對(duì)于明文始終不能得到唯一解的加密方法。如：采用客觀隨機(jī)一次出來的密碼就屬于這種加密方式。 實(shí)際上保密的加密：從理論的角度是可以破解的，但在現(xiàn)有客觀條件下，無法通過計(jì)算來確定唯一解。 （3）按明文形態(tài)劃分 模擬信息加密：用來加密模擬信息。如：動(dòng)態(tài)范圍之內(nèi)，連續(xù)變化的語音信號(hào)的加密。 數(shù)字信息加密：用來加密數(shù)字信息。如：兩個(gè)離散電平構(gòu)成0、1二進(jìn)制關(guān)系的電報(bào)信息的加密。2. 數(shù) 字 簽 名 數(shù)字簽名是對(duì)原信息附上加密信息的過程，是一種身份認(rèn)證技術(shù)，支持加密系統(tǒng)認(rèn)證性和非否定；簽名者對(duì)發(fā)布的原信息的內(nèi)容

31、負(fù)責(zé)，不可否認(rèn)。數(shù)字簽名采用非對(duì)稱式加密（也稱公鑰加密標(biāo)準(zhǔn)）對(duì)信息m使用私鑰K2加密，運(yùn)算如下：S=DK2(m) 其中S為簽名，D為解密算法；接收者收到發(fā)送者發(fā)來的S和m信息，同時(shí)從公開媒體找到了發(fā)送者的公鑰K1, 發(fā)送者用K2對(duì)S進(jìn)行如下運(yùn)算：E K1 (S)= E K1 (DK2(m)= m , E為加密算法；收到的m對(duì)應(yīng)計(jì)算出來的m，結(jié)果說明信息確實(shí)來源于發(fā)送者，第三方不可能知道私鑰K2，無法篡改S，發(fā)送者無法否認(rèn)發(fā)送m信息。在實(shí)際工作中，由于解密計(jì)算緩慢，為了提高簽名速度，m信息往往要經(jīng)過壓縮或散列處理或盡量取簡短信息，如公鑰數(shù)據(jù)等。數(shù)字簽名工作流程圖 信息m密鑰K2私鑰K 2公鑰K1

32、信息m 密鑰K2解密算法密鑰K2簽名S密鑰K2簽名S密鑰K2加密算法密鑰K2圖2.4 數(shù)字簽名工作流程圖3. 網(wǎng) 絡(luò) 信 息 加 密 網(wǎng)絡(luò)信息加密的目的是保護(hù)網(wǎng)內(nèi)的數(shù)據(jù)、文件、口令和控制信息，保護(hù)網(wǎng)上傳輸?shù)臄?shù)據(jù)。網(wǎng)絡(luò)加密常用的方式有鏈路加密和端點(diǎn)加密。 （1）鏈路加密 鏈路加密對(duì)鏈路層數(shù)據(jù)單元進(jìn)行加密保護(hù)，其目的是保護(hù)網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈路信息安全。這種加密不但對(duì)節(jié)點(diǎn)之間之間傳輸?shù)臄?shù)據(jù)報(bào)文加密，還要把路由信息、校驗(yàn)和控制信息包括數(shù)據(jù)鏈路層的幀頭、位填充和控制序列等都進(jìn)行加密；當(dāng)密文傳輸?shù)侥骋还?jié)點(diǎn)時(shí)，全部解密獲得鏈信息和明文，然后全部加密后發(fā)送往下一個(gè)節(jié)點(diǎn)；對(duì)于這種加密，加密設(shè)備的設(shè)計(jì)相對(duì)復(fù)雜，必須

33、理解鏈路層協(xié)議和必要的協(xié)議轉(zhuǎn)換。鏈路加密的優(yōu)缺點(diǎn) 鏈路加密非常有效，是因?yàn)閹缀跞魏斡杏孟⒍急患用鼙Ｗo(hù)。加密范圍包括用戶數(shù)據(jù)、路由信息和協(xié)議信息等。因此，攻擊者將不知道通信的發(fā)送和接受者的身份、不知道信息的內(nèi)容、甚至不知道信息的長度以及通信持續(xù)的時(shí)間。而且，系統(tǒng)的安全性將不依賴任何傳輸管理技術(shù)。密鑰管理也相對(duì)簡單，僅僅是線路的兩端需要共同的密鑰。線路兩端可以獨(dú)立于網(wǎng)絡(luò)的其他部分更換密鑰。 鏈路加密的缺點(diǎn)是：整個(gè)連接中的每段連接都需要加密保護(hù)。對(duì)于包含不同體系機(jī)構(gòu)子網(wǎng)絡(luò)的較大型網(wǎng)絡(luò)，加密設(shè)備、策略管理、密鑰量等方面的開銷都是巨大的。另外，在每個(gè)加密節(jié)點(diǎn)，都存在加密的空白段：明文信息，這是及其危險(xiǎn)

34、的，特別是對(duì)于跨越不同安全域的網(wǎng)絡(luò)。后來，為解決節(jié)點(diǎn)中數(shù)據(jù)是明文的缺點(diǎn)，在節(jié)點(diǎn)內(nèi)增加了加解裝置，避免了節(jié)點(diǎn)明文，這種加密方式稱為節(jié)點(diǎn)加密；但和鏈鏈加密一樣，同樣依靠公共網(wǎng)絡(luò)節(jié)點(diǎn)資源的配合，開銷依然很大。端 點(diǎn) 加 密 端點(diǎn)加密的是對(duì)源端用戶到目的端用戶的數(shù)據(jù)提供加密保護(hù)。既將加密模塊置于網(wǎng)絡(luò)以上的加密方式。端點(diǎn)加密中，數(shù)據(jù)從加密的端節(jié)點(diǎn)，一直到對(duì)應(yīng)的解密節(jié)點(diǎn)，數(shù)據(jù)在整個(gè)傳輸過程中都保持密文形式，從而克服了鏈路加密出現(xiàn)加密空白段（中間節(jié)點(diǎn)明文信息）的問題。由于加密和解密只發(fā)生在兩個(gè)端節(jié)點(diǎn)，因此對(duì)中間節(jié)點(diǎn)是透明的。這樣大大減少了安裝設(shè)備的開銷（特別是中間節(jié)點(diǎn)設(shè)備開銷），以及復(fù)雜的策略管理和密鑰管理

35、所引起的麻煩。由于加密范圍往往集中在高層協(xié)議數(shù)據(jù)，還極易為不同流量提供QoS服務(wù)，實(shí)現(xiàn)按特定流量進(jìn)行加密和不同強(qiáng)度的加密。從而有利于提高系統(tǒng)的效能，優(yōu)化系統(tǒng)的性能。端點(diǎn)加密的缺點(diǎn) 端點(diǎn)加密的缺點(diǎn)是：由于通信環(huán)境往往比較復(fù)雜，要在跨越網(wǎng)絡(luò)的兩個(gè)端用戶之間成功地完成密鑰的建立是需要付出性能代價(jià)的。其次，端點(diǎn)加密不能保護(hù)數(shù)據(jù)傳輸過程中的某些信息，如路由信息、協(xié)議信息等，一個(gè)訓(xùn)練有素的攻擊者可以借助這些信息發(fā)動(dòng)某些流量分析攻擊。另外，端點(diǎn)加密設(shè)備（模塊）的實(shí)現(xiàn)十分復(fù)雜，要求設(shè)備必須理解服務(wù)的提供層的協(xié)議，并且成功調(diào)用這些服務(wù)，然后在設(shè)備中對(duì)對(duì)應(yīng)的數(shù)據(jù)進(jìn)行密碼處理，并且將處理后的數(shù)據(jù)傳送給上層協(xié)議。如果

36、加密設(shè)備不能為上層協(xié)議提供良好的服務(wù)接口，則將對(duì)通信的性能產(chǎn)生較大的影響。 2.2.3 數(shù)據(jù)加密標(biāo)準(zhǔn)1. 對(duì)稱密鑰加密DES DES(data encryption standard)是1976年由美國國家標(biāo)準(zhǔn)局頒布的一種加密算法，屬于對(duì)稱密鑰加密算法體制，早期被公認(rèn)為較好的加密算法，經(jīng)過長期嚴(yán)驗(yàn)證后，被國際標(biāo)準(zhǔn)化組織接受作為國際標(biāo)準(zhǔn)。DES自它應(yīng)用20多年來，不斷經(jīng)受了許多科學(xué)家破譯，同時(shí)也成為密碼界研究的重點(diǎn)。DES對(duì)稱密鑰加密算法廣泛的應(yīng)用在民用密碼領(lǐng)域，為全球貿(mào)易、金融等非官方部門提供了可靠的通信安全保障。DES的相關(guān)知識(shí) DES主要采用替換和移位的加密方法用56位密鑰對(duì)64位二進(jìn)制數(shù)

37、據(jù)塊進(jìn)行加密，加密每次可對(duì)64位的輸入數(shù)據(jù)進(jìn)行16輪編碼，經(jīng)過一系列替換和移位后，原始的64位輸入數(shù)據(jù)轉(zhuǎn)換成了完全不同的64位輸出數(shù)據(jù)。DES算法運(yùn)算速度快，生成密鑰容易，適合于在當(dāng)前大多數(shù)計(jì)算機(jī)上用軟件方法和專用芯片上實(shí)現(xiàn)。但DES密鑰太短（56位），密鑰健壯性不夠好，降低保密強(qiáng)度；同時(shí)，DES安全性完全依賴于對(duì)密鑰的保護(hù)，在網(wǎng)絡(luò)環(huán)境下使用，分發(fā)密鑰的信道必須具備有力的可靠性才能保證機(jī)密性和完整性。 DES算法還有一些變形，如：三重DES和廣義DES等。目前，DES應(yīng)用領(lǐng)域主要包括：計(jì)算機(jī)網(wǎng)絡(luò)通信中的數(shù)據(jù)保護(hù)（只限于民用敏感信息）；電子資金加密傳送；保護(hù)用戶存儲(chǔ)文件，防止了未授權(quán)用戶竊密；計(jì)

38、算機(jī)用戶識(shí)別等。2. Clipper加密芯片標(biāo)準(zhǔn) 這種數(shù)據(jù)加密標(biāo)準(zhǔn)對(duì)用戶只提供加密芯片（Clipper）和硬件設(shè)備，它的密碼算法不公開，密鑰量比DES多1000多萬倍，是美國國家保密局（NSA）在1993年正式使用的新的商用數(shù)據(jù)加密標(biāo)準(zhǔn)，目的是取代DES，提高密碼算法的安全性，主要用于通信交換系統(tǒng)中電話、傳真和計(jì)算機(jī)通信信息的安全保護(hù)。為確保更可靠的安全性，加密設(shè)備的制作方法按照Clipper芯片由一個(gè)公司制造裸片，再由另一公司編程嚴(yán)格規(guī)定來實(shí)施。 Clipper芯片主要特點(diǎn)是充分利用高的運(yùn)算能力的設(shè)備資源加大密鑰量，從而用于計(jì)算機(jī)通信網(wǎng)上的信息加密，如：政府和軍事通信網(wǎng)中數(shù)據(jù)加密芯片的研究不

39、斷換代使它還實(shí)現(xiàn)了數(shù)字簽名標(biāo)準(zhǔn)和保密的哈希函數(shù)標(biāo)準(zhǔn)以及用純?cè)肼曉串a(chǎn)生隨機(jī)數(shù)據(jù)的算法等。3. 國際數(shù)據(jù)加密標(biāo)準(zhǔn) 這種算法是在DES算法的基礎(chǔ)上發(fā)展的。與 DES相同，國際數(shù)據(jù)加密算法IDEA（international data encryption algorithm）也是針對(duì)數(shù)據(jù)塊加密；它采用128位密鑰，設(shè)計(jì)了一系列加密輪次，每輪加密都使用從完整的加密密鑰中生成的一個(gè)子密鑰，基于這種算法，采用軟件實(shí)現(xiàn)和采用硬件實(shí)現(xiàn)同樣快速，非常適合于對(duì)大量的明文信息的快速加密。它在1990年正式公布并在以后得到了增強(qiáng)。傳統(tǒng)加密方法的缺點(diǎn) 在網(wǎng)絡(luò)通信中，傳統(tǒng)的對(duì)稱加密方法是發(fā)送者加密、接收者解密使用同樣的密

40、鑰，這種方法雖然有運(yùn)算快的特點(diǎn)，隨著用戶的增加，大量密鑰的分配是一個(gè)難以解決的問題。例如，若系統(tǒng)中有n個(gè)用戶，其中每兩個(gè)用戶之間需要建立密碼通信，則系統(tǒng)中每個(gè)用戶須掌握(n-1)/2個(gè)密鑰，而系統(tǒng)中所需的密鑰總數(shù)為n*(n-1)/2 個(gè)。對(duì)10個(gè)用戶，每個(gè)用戶必須有9個(gè)密鑰，系統(tǒng)中密鑰的總數(shù)為45個(gè)。對(duì)100個(gè)用戶，每個(gè)用戶必須有99個(gè)密鑰，系統(tǒng)中密鑰的總數(shù)為4950個(gè)。這還僅考慮用戶之間的通信只使用一種會(huì)話密鑰的情況。如此龐大數(shù)量的密鑰生成、管理、分發(fā)確實(shí)是一個(gè)難處理的問題。因此，對(duì)稱加密方法所帶來的密鑰的弱的健壯性和密鑰管理的復(fù)雜性局限了它的發(fā)展。4. 公開密鑰加密標(biāo)準(zhǔn) 早在20世紀(jì)70年

41、代，美國斯坦福大學(xué)的兩名學(xué)者迪菲和赫爾曼提出了一種加密方法公開密鑰加密方法，解決了傳統(tǒng)加密體系的密匙分配復(fù)雜的缺點(diǎn)。 公開密鑰加密方法是非對(duì)稱加密方式，該技術(shù)采用不同的加密密鑰和解密密鑰對(duì)信息加密和解密，每個(gè)用戶有一個(gè)對(duì)外公開的加密算法E和對(duì)外保密的解密算法D，它們須滿足條件： （1）D是E的逆，即DE（X）=X。 （2）E和D容易計(jì)算。 （3）如果由E出發(fā)求解D十分困難。公鑰及私鑰的概念 若加密密鑰可對(duì)外公開，稱為公鑰；一個(gè)用戶向另一用戶傳送信息，首先通過開放途徑(如BBS)的獲得另一用戶的公開密鑰，對(duì)明文加密后發(fā)送，而另一用戶唯一保存的解密密鑰是保密的，稱為私鑰，另一用戶通過安全的方法驗(yàn)證

42、信源可靠后，私鑰將密文復(fù)原、解密。理論上解密密鑰可由加密密鑰推算出來，但這種算法設(shè)計(jì)在實(shí)際上是不可能的，或者雖然能夠推算出，但要花費(fèi)很長的時(shí)間和代價(jià)，所以，將加密密鑰公開不會(huì)危害密鑰的安全。RSA 算 法 著名的RSA正是基于這種理論，算法以發(fā)明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman.這種算法為公用網(wǎng)絡(luò)上信息的加密和鑒別提供了一種基本的方法。為提高保密強(qiáng)度，RSA密鑰至少為500位長，一般推薦使用1024位，這就使加密的計(jì)算量很大。同時(shí)，為減少計(jì)算量，在傳送信息時(shí)，常采用傳統(tǒng)對(duì)稱加密方法與RSA公開密鑰加密方法相結(jié)合的方式，信息明文加密采用

43、改進(jìn)的DES或IDEA加密方法，使用RSA用于加密密鑰和信息摘要。對(duì)方收到信息后，用各自相關(guān)的密鑰解密并可核對(duì)信息。但是RSA并不能替代DES等對(duì)稱算法，RSA的密鑰長，加密速度慢，而采用DES等對(duì)稱算法加密速度快，適合加密較長的報(bào)文，彌補(bǔ)了RSA的缺點(diǎn)。美國的保密增強(qiáng)郵件系統(tǒng)（PEM）就是采用了RSA 和DES結(jié)合的方法，目前已成為E-MAIL保密通信標(biāo)準(zhǔn)。5. 量子加密方法 量子加密與公鑰加密標(biāo)準(zhǔn)同期出現(xiàn)，適用于網(wǎng)絡(luò)上加 密普通寬帶數(shù)據(jù)信道所傳送的信息，工作原理是兩端用戶各自產(chǎn)生一個(gè)私有的隨機(jī)數(shù)字符串，兩個(gè)用戶向?qū)Ψ降慕邮苎b置發(fā)送代表數(shù)字字符串的單個(gè)量子序列（光脈沖），接受裝置從兩個(gè)字符串

44、中取出相匹配的比特值組成了密鑰。實(shí)現(xiàn)了會(huì)話或交換密鑰的傳遞。由于這種方法依賴的是量子力學(xué)定律，傳輸?shù)墓饬孔邮菬o法被竊聽的；如果有人進(jìn)行竊聽，就會(huì)對(duì)通信系統(tǒng)造成干擾，對(duì)通信系統(tǒng)的量子狀態(tài)造成不可挽回的變化，通信雙方就會(huì)得知有人進(jìn)行竊聽，從而結(jié)束通信，重新生成密鑰。這種加密技術(shù)不久的將來應(yīng)該有應(yīng)用和發(fā)展，但是如何實(shí)現(xiàn)數(shù)字簽名有待于研究。2.3 公鑰信息加密算法 隨著密碼技術(shù)的發(fā)展，Diffie和Hellman在IEEE提出提出了公鑰密碼系統(tǒng)，即加密密鑰和 解密密鑰不是同一把密鑰?，F(xiàn)在公鑰密碼系統(tǒng)被廣泛的應(yīng)用，其中RSA加密算法，Diffie-Hellman算法，ElGamal加密算法，橢圓曲線加密

45、算法被廣泛研究和應(yīng)用。2.3.1 RSA加密算法 RSA的安全性依賴于大數(shù)分解。公鑰及私鑰都是兩個(gè)大素?cái)?shù)（大于100個(gè)十進(jìn)制位）的函數(shù)，從一個(gè)密鑰和密文推斷出明文的難度等同于分解兩個(gè)大素?cái)?shù)的積。算法如下： .生成密鑰 （1）秘密的選取兩個(gè)大數(shù)p,q （2）計(jì)算 , ,這 指的是Euler函數(shù) （3）選取整數(shù)e，滿足 且 。 （4）計(jì)算d,滿足 。即d是e關(guān)于模 乘的逆元，（乘法逆元 ：設(shè) ，如果存在 ， 滿足 ，則稱x是a的模n乘法逆元，記為 (mod n) ）由e的定義，d唯一。 （5）輸出公鑰 ,私鑰 。具體加密解密操作 加密操作 選定 ,把明文分成長度為k的組塊。對(duì)每個(gè)明文分組M , M

46、在0到(n-1)之間。加密操作為： 解密操作 得到密文分組C，解密操作為： (2.14) (2.15)RSA算法的局限性（1）（1）有限的安全性 RSA是一種分組密碼算法，它的安全是基于數(shù)論中大的整數(shù)n分解為兩個(gè)素?cái)?shù)之積的難解性。目前，RSA的一些變種算法已被證明等價(jià)于大數(shù)分解。同樣，分解n也是最顯然的攻擊方法?，F(xiàn)在，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)。因此，適用具體情況而定，模數(shù)n必須選盡可能大。同時(shí)要注意，如果系統(tǒng)中共享一個(gè)模數(shù)，不同的人擁有不同的公鑰e1和e2，這些公鑰共模而且互質(zhì)，假如普遍的情況是同一信息用不同的公鑰加密，那么該信息無需私鑰就可得到恢復(fù)。即設(shè)P為信息明文，C1和C2

47、為密文，公共模數(shù)是n，則： C1 = Pe1 mod n ；C2 = Pe2 mod n 密碼分析者知道n、e1、e2、C1和C2，就能得到P。解決辦法只有一個(gè)，那就是不要共享模數(shù)n。RSA算法的局限性（2） （2）運(yùn)算速度慢 RSA算法進(jìn)行的都是大數(shù)計(jì)算，使得其最快的情況也比DES慢上100倍，無論是軟件實(shí)現(xiàn)還是硬件實(shí)現(xiàn)。速度一直是RSA算法的缺陷。一般來說RSA算法只用于少量數(shù)據(jù)加密。有一種提高RSA速度的建議是使公鑰e取較小的值，這樣會(huì)使加密變得易于實(shí)現(xiàn)，速度有所提高。但這樣作是不安全的，公鑰e和私鑰d還是都取較大的值為好。但是，RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理

48、解和操作。經(jīng)歷了各種攻擊的考驗(yàn)和最廣泛的研究，從提出到現(xiàn)在已近二十年，逐漸為人們認(rèn)為是目前最適用的公鑰算法之一。2.3.2 Diffie-Hellman算法 Diffie和Hellman在1976年公開發(fā)表的第一個(gè)公鑰密碼算法定義了公鑰密碼學(xué)。論文中提出一個(gè)密鑰交換系統(tǒng)，讓網(wǎng)絡(luò)互不相見的兩個(gè)通信體，可以共享一把鑰匙，用以證明公開密鑰的概念的可行性。這個(gè)算法本身基于計(jì)算對(duì)數(shù)難度，其目的是實(shí)現(xiàn)兩個(gè)用戶之間安全地交換密鑰以便于后續(xù)的數(shù)據(jù)加密。Diffie-Hellman密鑰交換算法在現(xiàn)在的許多商用產(chǎn)品中使用。Diffie-Hellman算法描述 算法描述如下： 給定公開素?cái)?shù)q和q的本原根r。即r1,

49、2,3,4,(q-1),且 1,2,3,4,(q-1) mod q, mod q, mod q, mod q則對(duì)b1,2,3,4,(q-1),可以唯一的指數(shù)i，使得b= mod q。 用戶A, B交換密鑰的方法如下： （1）用戶A選擇一個(gè)隨機(jī)數(shù) ,計(jì)算 ,A將 秘密保存而將 公開。 （2）用戶B選擇一個(gè)隨機(jī)數(shù) ,計(jì)算 ,B將 秘密保存而將 公開。 （3）A將 送給B，B將 送給A,（A并不知道 ,B并不知道 ） （4）用戶A計(jì)算密鑰： ； （5）用戶B計(jì)算密鑰： ； 2.3.3 ElGamal加密算法 EIGamal體制是T.EIGamal在1985年發(fā)表的“A public-key cryp

50、tosystem and a signatures scheme based on discrete logarithms”(一個(gè)基于離散對(duì)數(shù)的共鑰密碼體制和數(shù)學(xué)簽名方案)論文中提出的公開密匙密碼體制。 下面給出的EIGamal體制在論文中用于數(shù)據(jù)加密的算法。采用EIGamal公開密匙密碼體制的密碼系統(tǒng)中，所有的用戶都共享一個(gè)素?cái)?shù)P 以及一個(gè)Z的生成元g,明文空間P=Z,密文空間 ,選定0ap,計(jì)算 秘密密鑰：a 公開密鑰：bElGamal加密解密算法 加密算法：設(shè)明文為m,0mp,隨機(jī)的選取正整數(shù)k,0kp,gcd(k,p-1)=1,計(jì)算密文對(duì)y1, y2： 密文 。 解密算法： 可見，EI

51、Gamal體制的密文不是唯一的，這是一種非確定性加密方式。顯然增加了系統(tǒng)的安全性，但是，代價(jià)是密文膨脹了兩倍。2.3.4 橢圓曲線加密算法定義 定義：橢圓曲線指的是由韋爾斯特拉斯方程所確定的平面曲線 。 其中，系數(shù)（i =1，2，6）定義在基域K上 （K可以是有理數(shù)域、實(shí)數(shù)域、復(fù)數(shù)域，還可以是有限域，橢圓曲線密碼體制中用到的橢圓曲線都定義在有限域上）橢圓曲線加密算法相關(guān)知識(shí) 1985年，Koblitz和Miller相互獨(dú)立地開發(fā)提出了在密碼學(xué)中應(yīng)用橢圓曲線（Eliptical Curve）構(gòu)造公開密鑰密碼體制的思想。這一算法一出現(xiàn)便受到關(guān)注，由于基于橢圓曲線的公開密鑰密碼體制開銷?。ㄋ璧挠?jì)算

52、量小）、安全性高等優(yōu)點(diǎn)，隨著橢圓曲線的公開密鑰密碼體制極大的發(fā)展，它將替代RSA成為通用的公鑰密碼算法。實(shí)踐表明，在 32位的PC機(jī)上和16位微處理器上運(yùn)行橢圓曲線密碼算法，其中16位微處理器上的數(shù)字簽名不足500ms。因此，應(yīng)用橢圓曲線的數(shù)字簽名可以很容易地在小的有限資源的設(shè)備中使用。1. 有限域上的橢圓曲線算法的提出 設(shè)K表示一個(gè)有限域，E是域K上的橢圓曲線，則E是一個(gè)點(diǎn)的集合：E/K = ( x, y ) | y2+ a1xy + a3y = x3 + a2x2 + a4x + a6, a1, a3, a2, a4, a6 x, y K O 其中O表示無窮遠(yuǎn)點(diǎn)。在E上定義+運(yùn)算，P +

53、Q = R，R是過P、Q的直線與曲線的另一交點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)， 當(dāng)P = Q時(shí)R是P點(diǎn)的切線與曲線的另一交點(diǎn)關(guān)于x軸的對(duì)稱點(diǎn)。這樣，( E, + )構(gòu)成可換群 ( Abel群)，O是加法單位元(零元)。橢圓曲線離散對(duì)數(shù)問題定義如下：給定定義在K上的橢圓曲線E，一個(gè)n階的點(diǎn)PE/K，和點(diǎn)QE/ K，如果存在l，確定整數(shù)l, 0, l ,n - 1, Q = lP。 我們知道，RSA是基于因子分解，其算法的核心就是如何尋找大數(shù)的因子分解，但大數(shù)的因子分解是比因子分解難得多的問題。橢圓曲線上的加法: P + Q = R 是橢圓曲線上一點(diǎn)的2倍: P + P = R. 基于該難題，1985年N.Ko

54、blitz和Miller提出將橢圓曲線用于密碼算法，分別利用有限域上橢圓曲線的點(diǎn)構(gòu)成的群實(shí)現(xiàn)了離散對(duì)數(shù)密碼算法。2. 橢圓曲線上的密碼算法 橢圓曲線加密系統(tǒng)由很多依賴于橢圓曲線離散對(duì)數(shù)算法問題的加密系統(tǒng)組成: （1）知E(Fn)對(duì)點(diǎn)的“ ”運(yùn)算形成一個(gè)Abel群，設(shè)pE(Fn)，若p的周期很大，即使p p p= (共有 t個(gè)p相加)成立的最小正整數(shù) t，希望t 很大(t = p的周期，表示為(p)=t)，并且對(duì)QE(Fq)，定有某個(gè)正整數(shù)m使Q=mp=p p(共有m個(gè)p相加)定義m=n Q (m為以n為底Q的對(duì)數(shù))橢圓曲線上的點(diǎn)形成的群E(Fn)，相關(guān)它的離散對(duì)數(shù)問題是難處理的。建立橢圓曲線密

55、碼體制 選取基域Fn，F(xiàn)n的橢圓曲線具體給定為確定的形式。 在E(Fn)中選一個(gè)周期很大的點(diǎn)，如選了一個(gè)點(diǎn)P=(xn, yn)，它的周期為一個(gè)大的素?cái)?shù)n，記 (P)=n(素?cái)?shù))。注意：在這個(gè)密碼體制中，具體的曲線及點(diǎn)P和它的n都 是公開信息。密碼體制的形式采用EIGamal體制，是完全類比過來。建立橢圓曲線密碼的方法 使用者執(zhí)行了下列計(jì)算： a) 在區(qū)間1,n-1中隨機(jī)選取一個(gè)整數(shù)d； b) 計(jì)算點(diǎn)Q:=dP (d個(gè)P相 ) ； c) 使用者公開自己的公開密鑰(E(Fn), p, n, Q)； d) 使用者的私鑰為整數(shù)d ； 發(fā)送者要發(fā)送消息m給使用者，執(zhí)行： a) 查找使用者的公鑰(E(Fn

56、), p, n, Q), b) 將m表示成一個(gè)域元素mFn， c) 在區(qū)間1，n-1內(nèi)選取一個(gè)隨機(jī)數(shù)k, d) 依據(jù)使用者的公鑰計(jì)算點(diǎn) (x1, y1):=kP (k個(gè)P相 )， e) 計(jì)算點(diǎn)(x2，y2):=kQ,如果x2 =0,則回到第c步計(jì)算C:=mx2； f) 傳送加密數(shù)據(jù)(x1,y1,C)給使用者； 使用者收到發(fā)送者的密文(x ,y ,C)后，執(zhí)行解密過程： a)使用私鑰d，計(jì)算點(diǎn)(x2，y2):=d(x1, y1)，再計(jì)算Fn中 ， b)通過計(jì)算m:=C ，恢復(fù)出明文數(shù)據(jù)m。2.4 信息加密產(chǎn)品簡介 信息加密產(chǎn)品隨著加密技術(shù)的應(yīng)用和發(fā)展出現(xiàn)了良好的商業(yè)化趨勢，比較常用的信息加密軟件

57、有PGP和CryptoAPI，作為開放的軟件工具，它們的使用為深入開展信息加密技術(shù)的研究提供了幫助。下面分別介紹PGP和CryptoAPI。 2.4.1 PGP加密軟件簡介 PGP(prettygoodprivacy)是一個(gè)對(duì)郵件和傳輸?shù)奈膿踹M(jìn)行加密的軟件，可以用來對(duì)郵件和文擋保密以防止非授權(quán)者閱讀，讓你可以安全地和你從未見過的人們通信。PGP軟件綜合了目前健壯的加密方法和加密系統(tǒng)認(rèn)證性方面的新手段，功能強(qiáng)大有很快的速度，是一種比較實(shí)用和安全的加密工具。PGP軟件創(chuàng)始人是美國的PhilZimmermann，由于許多版本不受密碼出口管制，源代碼也是免費(fèi)的，獲取比較方便。1. PGP采用的加密標(biāo)準(zhǔn)

58、 PGP用的是公匙加密和傳統(tǒng)加密的雜合算法，這種算法創(chuàng)造性在于他把公匙加密體系的方便和傳統(tǒng)加密體系的高速度結(jié)合起來，充分利用多個(gè)算法各自的優(yōu)點(diǎn)應(yīng)用于明文加密和密匙認(rèn)證管理機(jī)制中，形成了整個(gè)加密系統(tǒng)巧妙的設(shè)計(jì)。PGP實(shí)際上用來對(duì)明文加密采用了IDEA的傳統(tǒng)加密算法。IDEA的加（解）密速度比公匙加密算法如RSA快得多，但主要缺點(diǎn)就是密匙的傳遞渠道解決不了安全性問題，不適合網(wǎng)絡(luò)環(huán)境加密需要。因此，PGP每次加密都可以隨機(jī)生成密匙用IDEA算法對(duì)明文加密，然后在用密匙的傳遞中用公匙加密算法，一般是使用不適合加密大量數(shù)據(jù)的RSA或Diffie-Hellman算法對(duì)該密匙加密來保證傳遞渠道的安全性，這樣

59、收件人同樣是用RSA或Diffie-Hellman解密出這個(gè)隨機(jī)密匙，再用IDEA解密出明文。 PGP加密方法示意圖 解密 密鑰K2明文密鑰K 加密 密鑰K2明文加密密鑰K2發(fā)送者接收者IDEA加密密文接收者的公鑰K1公鑰加密密文解密密鑰K2接收者的私鑰K2密鑰K圖4.1PGP加密方法示意圖2. PGP的密匙管理（1） 在PGP中如果IDEA密匙是通過網(wǎng)絡(luò)傳送而不加密，網(wǎng)絡(luò)黑客們就會(huì)“監(jiān)聽”而獲取密匙，整個(gè)傳輸肯定危險(xiǎn)，因此，必須通過必要可靠的密匙管理來保證信息發(fā)送和接收的安全性。一個(gè)成熟的加密系統(tǒng)必然要有一個(gè)成熟的密匙管理機(jī)制配套，公匙加密體系可以解決傳統(tǒng)加密體系的密匙分配難保密的缺點(diǎn)，PG

60、P中應(yīng)用RSA或Diffie-Hellman算法實(shí)施密匙分配。2. PGP的密匙管理（2） 但是，分配過程中首先要獲取對(duì)方公匙，如果公匙被篡改，所獲得的公匙成了偽造的，密匙分配就會(huì)傳遞給篡改者，篡改者可以用自己的私匙解密獲得密匙。這可能是公匙密碼體系中最大的漏洞和安全性問題，你必須確信你拿到的公匙屬于它看上去屬于的那個(gè)人。防止這種情況出現(xiàn)的最好辦法是避免讓任何其他人有機(jī)會(huì)篡改公匙，比如直接從要接收信息的人手中得到公匙，然而當(dāng)在千里之外或無法見到時(shí)，這是很困難的。2. PGP的密匙管理（3） 解決這個(gè)問題一般方法是數(shù)字簽名，直接認(rèn)證你的信息接收者的公匙，防止篡改公匙；而PGP則在此基礎(chǔ)上發(fā)展了一