第6章保密通信的基本概念與方法6.1密碼體制6.2保密通信的數(shù)學理論6.3密碼破譯6.4Shannon保密理論

6.1密碼體制

在介紹密碼學的數(shù)學理論之前，我們先來介紹一下密碼體制。密碼體制是指設(shè)計一套加密運算和解密運算，使得明文加密密鑰經(jīng)過加密運算能得到密文，密文與解密密鑰經(jīng)過解密運算能得到明文。密碼體制的分類方法很多，通常人們習慣于從以下幾個角度對密碼體制進行劃分。

6.1.1換位與代替密碼體制

在加密/解密過程中，根據(jù)信息元素的位置和形態(tài)是否發(fā)生變化，可將密碼體制分為換位密碼體制和代替密碼體制。

1.換位密碼體制

在加密/解密過程中，信息元素只有位置上的變化，而形態(tài)不變，此種密碼體制稱為換位密碼體制。換位密碼體制的優(yōu)點是，可以打破明文消息中的某些固定結(jié)構(gòu)模式，使來自明文或密鑰的信息充分擴散到密文中，達到信息擴散的目的。但由于信息元素的形態(tài)在加密/解密過程中沒有變化，因此使得各信息元素出現(xiàn)的頻率在明文和密文中相同。密碼分析者通過對密文的統(tǒng)計分析就可能得到相應(yīng)明文的有關(guān)信息，甚至全部明文。

2.代替密碼體制

在加密/解密過程中，信息元素之間的位置排列關(guān)系沒有發(fā)生變化，而是形態(tài)發(fā)生了變化，此種密碼體制稱為代替密碼體制。代替密碼體制的優(yōu)點是，可以使明文和密鑰的信息混雜在一起，使人很難確定明文和密鑰是如何變成密文的。6.1.2序列與分組密碼體制

1.序列密碼體制

序列密碼體制是指將明文序列P與密鑰序列K按照序列的基本單位進行bit對bit的運算(如模二運算等)而形成密文的一種密碼體制。對于一個序列密碼，如果密鑰序列每隔n(n為正整數(shù))個bit以后重復，就稱之為周期序列密碼;反之，若密鑰不重復，則稱之為非周期序列密碼。序列密碼體制的特點是，加密及解密算法非常簡單，只是將明文序列與密鑰序列進行bit對bit的運算。密鑰是隨機的、不重復的，序列密碼體制的核心是密鑰序列生成算法的設(shè)計，即保密的核心是密鑰序列生成的方法。

2.分組密碼體制

分組密碼體制是指將明文序列P按nbit長度進行分組(最后一個分組不夠長度時，要填充為一個完整的分組)，所有的分組在相同的密鑰控制下分別進行加密變換而產(chǎn)生密文的一種密碼體制。

分組密碼體制的特點是，加密(或解密)算法非常復雜，它是分組密碼體制的核心，也就是說，分組密碼體制的關(guān)鍵是設(shè)計一個復雜而又高效的加密(或解密)算法。密鑰是相對固定的，對每一個分組的加密都使用固定長度、固定內(nèi)容的密鑰。6.1.3對稱與非對稱密鑰密碼體制

1.對稱密鑰密碼體制

對稱密鑰密碼體制又稱為單密鑰密碼體制或秘密密鑰體制。如果一個密碼體制的加密密鑰和解密密鑰相同，或者雖然不同，但是由其中的任意一個可以很容易地推導出另一個，則該密碼體制便稱為對稱密鑰密碼體制。如古典密碼體制均屬于對稱密鑰密碼體制。序列密碼以及分組密碼也都屬于對稱密鑰密碼體制。對稱密鑰密碼體制的典型代表是數(shù)據(jù)加密標準DES和高級數(shù)據(jù)加密標準AES。

2.非對稱密鑰密碼體制

非對稱密鑰密碼體制又稱為雙密鑰密碼體制或公開密鑰密碼體制。如果一個密碼體制的加密/解密操作分別使用兩個不同的密鑰，并且不可能由加密密鑰推導出解密密鑰(或不可能由解密密鑰推導出加密密鑰)，則該密碼體制便稱為非對稱密鑰密碼體制。采用非對稱密鑰密碼體制的每個用戶都有一對相互關(guān)聯(lián)而又彼此不同的密鑰，使用其中的一個密鑰加密的數(shù)據(jù)，不能使用該項密鑰自身進行解密，而只能使用對應(yīng)的另外一個密鑰進行解密。在這一對密鑰中，其中有一個密鑰稱為公鑰，它可公開并通過公開的信道發(fā)給任何一位想與自己通信的另一方。另一個密鑰則必須由自己秘密保存，稱為私鑰，用于解密由公鑰加密的信息。非對稱密鑰密碼體制的典型代表是RSA公鑰密碼體制。

非對稱密鑰密碼體制的出現(xiàn)是現(xiàn)代密碼學研究的一項重大突破，它的主要優(yōu)點是可以適應(yīng)開放性的網(wǎng)絡(luò)環(huán)境，密鑰分發(fā)及管理問題相對簡單，可以方便、安全地實現(xiàn)加密、數(shù)字簽名和身份認證。

6.2保密通信的數(shù)學理論

6.2.1數(shù)論

顧名思義，數(shù)論是研究數(shù)的一門理論，它是研究整數(shù)性質(zhì)的一個數(shù)學分支。與幾何學一樣，數(shù)論既是最古老的數(shù)學分支，又是古往今來比較活躍的數(shù)學研究領(lǐng)域。在密碼學中，數(shù)論更多地用于密碼算法設(shè)計，尤其是20世紀70年代公鑰密碼體制的問世，進一步促進了數(shù)論在密碼編碼領(lǐng)域的應(yīng)用和拓展。下面簡要介紹在密碼研究中所涉及的幾個基本概念。

1.素數(shù)

在上小學的時候，我們就學過合數(shù)和素數(shù)的概念。下面給素數(shù)下一個具體的定義：一個大于1的整數(shù)，如果它的正因子只有1和它本身，這個數(shù)就稱為素數(shù)(或質(zhì)數(shù))，否則就稱為合數(shù)。比如2，3，5，7，11等都是素數(shù)，而4，6，8，9等就是合數(shù)。素數(shù)的個數(shù)是無限的，在公開密鑰密碼體制中為了安全起見必須使用大素數(shù)(如1024bit的素數(shù)甚至更長)。

素數(shù)、合數(shù)再加上1就構(gòu)成了所有的正整數(shù)。

在數(shù)論中還有一個重要的概念——互素?；ニ厥侵溉我鈨蓚€正整數(shù)a和b，當它們除了1之外沒有其它的公因子，即a和b的最大公因子為1，記為gcd(a，b)=1，則稱a和b互素。

2.模運算

我們知道，在整數(shù)范圍內(nèi)，任意兩個整數(shù)之和、之差、之積都還是整數(shù)，但是整數(shù)除以整數(shù)卻不一定是整數(shù)，比如素數(shù)與素數(shù)相除。也可以換一種說法，對任意的兩個整數(shù)a和b(a>b)，很有可能b就不是a的因子，即a=bq+r(r≠0)，r是a除以b的余數(shù)，a與b的關(guān)系也可以表示為(6-1)上述幾種記法的意思都是一樣的，都表示所謂的模運算。在密碼學特別是公鑰密碼體制中，往往需要求解模逆元。那么，什么是模逆元呢？求模逆元，即尋找一個x，使得(6-2)其中，a和n都是正整數(shù)，x稱為a的模n的逆元。上式也可寫作(6-3)例如，尋找一個x，使得(6-4)這個方程等價于尋找一組x和k，使得方程4x=7k+1(6-5)成立。其中x和k均為整數(shù)。求解模逆元問題很困難，有時有結(jié)果，有時沒有結(jié)果。例如，5模14的逆元是3，因為5×3=15，15≡1(mod14);而2模14則沒有逆元。

一般情況下，如果a和n是互素的，那么存在x，使得a－1≡x(modn)成立；而如果a和n不是互素的，那么不存在x，使得a－1≡x(modn)成立。如果n是一個素數(shù)，那么從1到n－1的每一個數(shù)與n都是互素的，在這個范圍內(nèi)恰好有一個逆元。

模運算又稱為時鐘算術(shù)。比如，Alice對她父親說，她晚上10：00就會到家，可是由于臨時有事她遲到了13個小時，那么她是幾點到家的呢？這就是模12運算，即

(10+13)mod12=23mod12=11mod12

(6-6)由于23和11的模12運算相等，因而上式又可以寫成

23≡11(mod12)

(6-7)

在數(shù)論中稱23與11模12同余。

聯(lián)立k個同余式(6-8)稱為同余方程組。在我國古代的《孫子算經(jīng)》中有這樣一個問題：“今有物不知其數(shù)，三三數(shù)之剩二、五五數(shù)之剩三、七七數(shù)之剩二，問物幾何？答曰二十三?！痹O(shè)所求之物數(shù)為x，那么用同余方程組表示出來就是：

(6-9)這就是歷史上著名的剩余問題，可以用以下定理來描述。

中國剩余定理設(shè)n1，n2…，nk是兩兩互素的正整數(shù)，即i≠j，gcd(ni，nj)=1，則對任意的整數(shù)b1，b2…，bk，以下同余方程組(6-10)在模n1，n2…，nk下有唯一解。這就是中國數(shù)學家大約在公元前100年發(fā)現(xiàn)的“中國剩余定理”。

3.因子分解

因子分解就是對合數(shù)的分解，當合數(shù)比較小時，分解容易。當數(shù)字逐漸增大時，我們就需要動筆算一算或者在計算機上運算了。當然，在實際應(yīng)用中，必須借助于有效的數(shù)學方法進行因子分解。數(shù)學家們在這方面已取得了許多進展，如試除法、數(shù)域篩選法、橢圓曲線法等。然而，對于很大的數(shù)(如1024bit以上的數(shù))進行因子分解，其所用的計算時間在目前條件下是一個天文數(shù)字。因子分解是數(shù)論中最古老的一個問題，這個問題在密碼體制中可以簡單地描述如下：

已知兩個大素數(shù)p和q，求其積n很容易；反之，知道n要求出p和q就很困難。第6章中提到的RSA公鑰密碼體制就是根據(jù)這一數(shù)學難題而設(shè)計的一種加密體制。目前，公鑰密碼有三種最為常用的體制：RSA公鑰密碼體制、EIGamal公鑰密碼體制和橢圓曲線公鑰密碼體制(ECC)。這三種體制分別運用了三個數(shù)學難題，即因子分解、離散對數(shù)和橢圓曲線離散對數(shù)問題。

4.離散對數(shù)

模運算用于指數(shù)計算時可以表示為

axmodn

(6-11)

稱之為模指數(shù)運算。模指數(shù)運算的逆問題就是找出一個數(shù)的離散對數(shù)，即求解x，使得

ax≡b(modn)

(6-12)

這是一個難題。

在公開密鑰密碼體制中，有一種EIGamal公鑰密碼體制，就是利用求離散對數(shù)的困難性而設(shè)計的一種密碼體制。使用該項體制時每一個用戶將計算:

y=αxmodp

(6-13)用戶將x作為自己的秘密密鑰嚴格保密，而y作為自己的公開密鑰。6.2.2信息熵與保密通信的本質(zhì)聯(lián)系

Shannon從概率統(tǒng)計的觀點出發(fā)研究信息的傳輸和保密問題，他將公共通信系統(tǒng)歸納為圖6-1(a)所示的原理圖，而將保密通信系統(tǒng)歸納為圖6-1(b)所示的原理圖。公共通信系統(tǒng)的目的是在信道有干擾的情況下，使接收的信號無差錯或差錯盡可能小。而保密通信系統(tǒng)的設(shè)計目的是使竊聽者即使在完全準確地收到了接收信號的情況下也無法恢復出原始消息。圖6-1公共通信系統(tǒng)與保密通信系統(tǒng)在保密通信中涉及三個要素，即明文、密鑰和密文，與它們分別對應(yīng)的集合就叫做明文空間、密鑰空間和密文空間。這三個空間之間有一定的聯(lián)系，比如密文空間的統(tǒng)計特性就是由明文和密鑰的統(tǒng)計特性共同決定的。因此，如果一種密碼體制被破譯，其本質(zhì)是密文中不同程度地泄漏了有關(guān)明文或密鑰的信息。

密碼學與其它學科一樣，有一個“從實踐到理論、再從理論回到實踐”的反復過程。對密碼學體制的理論保密性研究，從Shannon的觀點來看，有如下研究內(nèi)容：“當密碼分析者有無限的時間和人力可用于分析密文時，一個體制抵抗密碼分析的能力有多大？密文是否有一個唯一解？即使為求解它可能需要一個不切實際的工作量，為得到唯一解必須截獲多少電文？是否存在無論截獲多少電文其解也絕不唯一的密碼體制？是否存在敵人無論截獲多少電文也得不到任何信息的密碼體制？”Shannon用信息論的觀點回答了這些問題。

1.多余度D

多余度D在檢錯和糾錯技術(shù)中是很有用的。這是由于在信息的傳輸和處理過程中出錯是難免的，為了檢測錯誤和糾正錯誤，需要在原始信息中添加一些數(shù)據(jù)作為檢錯和糾錯使用，這樣做的目的對于通信的可靠性是大有好處的。

從密碼學的觀點來看，多余度對信息安全是不利的。Shannon指出：多余度為密碼分析奠定了基礎(chǔ)，這是Shannon對密碼學的巨大貢獻。事實上確實如此，多余度越小，破譯分析的困難就越大，這對于保密來說是十分有利的。

2.熵H(M)

從密碼學的角度來看，如果一個密碼系統(tǒng)的熵H(M)越大，則表示在該密碼系統(tǒng)中哪些密文對應(yīng)哪些明文的不確定程度就越大，即由密文分析出對應(yīng)明文的概率就越小，這樣

的密碼系統(tǒng)就越安全。

3.唯一解距離U

怎樣衡量破譯分析的難度呢？Shannon又定義了一個稱做“唯一解距離U”的量，其含義是當密碼分析者進行窮舉攻擊時，可能解密出唯一有意義的明文所需要的最少的密文量。

當密碼分析者所截獲的密文字符數(shù)大于唯一解距離時，這種密碼的破譯問題就存在一個解；而當所截獲的密文字符數(shù)少于唯一解距離時，就存在多個可能的解。

Shannon用信息論描述了被截獲的密文量和成功破譯的可能性之間的關(guān)系，他用一個數(shù)學公式來計算唯一解距離:(6-14)式中，U代表唯一解距離，H(K)代表密鑰的熵值，D代表明文語言的多余度。一般來說，明文語言的多余度越大，唯一解距離就越小，密碼分析者在唯密文攻擊的情況下就越容易求得正確的密鑰。因此，為提高密碼體制的安全性，應(yīng)盡量減小明文語言的多余度。6.2.3復雜度理

1.算法復雜度

在設(shè)計密碼算法時，一方面密碼設(shè)計者都希望自己設(shè)計的算法在進行正常的加密/解密運算時能有較快的速度并占用較小的空間，而另一方面他們都期望密碼破譯者在破譯該算法所產(chǎn)生的密文時具有無窮無盡的時間需求和無法滿足的空間需求。那么，如何做到這一點呢？回答是：利用算法復雜度理論去分析所設(shè)計的密碼算法。

算法復雜度是指運行一個算法所需的時間和空間的資源，常用兩個變量——時間復雜度T和空間復雜度S來度量，即運行一個算法所需的時間和所占用的空間是衡量一個算法復雜度的兩個主要指標。在密碼學發(fā)展的初期，無論是密碼編碼學，還是密碼分析學，都處于知其然而不知其所以然的狀態(tài)。一方面，密碼專家編制了各種各樣的密碼體制，一開始總是認為這些密碼體制是非常安全的，而事實上這些體制是不安全的，很快被破譯，其根本原因是，當時沒有一種數(shù)學理論來度量其算法的安全性。算法復雜度理論的出現(xiàn)解決了這一問題，它可以幫助密碼專家分析一個算法所具有的抗破譯能力，從而可以確定一個密碼算法的安全性。

2.問題復雜度

現(xiàn)實生活中有各種各樣的問題，有的問題容易求解，有的問題不容易求解。我們把現(xiàn)實可求解的問題稱為P類問題，將現(xiàn)實很難求解的問題稱為NP類問題，而將最難求解的問題稱為NPC類問題，如旅行者問題和三方匹配問題等。NPC問題目前還沒有有效的求解算法。有人建議利用問題復雜度來設(shè)計密碼系統(tǒng)，他們認為NPC問題是非常合適的對象。NPC問題很多，如果將陷門藏匿于這些問題中，可設(shè)計出一種既安全又實用的密碼系統(tǒng)，對密碼破譯者來說是一大挑戰(zhàn)。因為，當陷門被巧妙地放入所設(shè)計的密碼系統(tǒng)中時，對密碼破譯者而言，欲求解這些NPC問題，在有效時間內(nèi)是無法完成的，但對于知道這些陷門的人，卻可以利用簡便的途徑求解。

6.3密碼破譯

6.3.1密碼破譯概述

密碼分析俗稱密碼破譯，是指在密碼通信過程中，非授權(quán)者在不知道解密密鑰和通信者所采用的密碼體制細節(jié)的條件下對密文進行分析，試圖得到明文或密鑰的過程。研究密碼破譯規(guī)律的科學稱為密碼分析學或破譯學。密碼編碼學和破譯學的關(guān)系是對立統(tǒng)一的辯證關(guān)系，它們既相互依存又相互對立，共處于密碼學這一統(tǒng)一體中。沒有密碼編碼，也就不會產(chǎn)生密碼破譯。而沒有密碼破譯，密碼編碼技術(shù)的發(fā)展和提高也就無從談起，二者互為存在的條件。因此，要想設(shè)計出保密的、實用的密碼體制，就必須掌握密碼破譯的原理與方法；要想破譯取得成功，也必須依靠堅實的密碼編碼理論和技術(shù)。

另外，我們還需區(qū)別兩個概念：解密和密碼破譯。解密和密碼破譯都是設(shè)法將密文還原成明文的過程，解密是加密的逆過程，是指掌握密鑰和密碼算法的合法人員從密文中恢復出明文的過程，而密碼破譯則是指非授權(quán)人員在不掌握密鑰和密碼算法的情況下對密碼進行的分析和破譯工作。6.3.2密碼破譯規(guī)律

1.密碼規(guī)律

不同的密碼體制具有不同的密碼規(guī)律，密碼破譯利用的規(guī)律是具體的。例如，對于單表代替密碼和單置換換位密碼，其密碼規(guī)律比較明顯，易于識別和利用；而一次一密代替密碼和一次一密換位密碼的規(guī)律比較隱蔽，難于識別和利用，等等。此外，一個設(shè)計比較好的密碼體制，由于使用不當也會使密碼形成易于被破譯者所利用的規(guī)律。

2.文字規(guī)律

電報是由語言組成的，而任何一種語言的結(jié)構(gòu)都是有語法規(guī)律的。由于這些規(guī)律是公開的，它可以為密碼分析者充分利用，成為假設(shè)和反證的重要依據(jù)。文字規(guī)律的表現(xiàn)形式很多，概括起來主要有字母統(tǒng)計規(guī)律和電報公文格式兩個方面。字母統(tǒng)計規(guī)律如表6-1所示。

3.情況規(guī)律

密碼電報一般要反映當時當?shù)氐那闆r，盡管其內(nèi)容是秘密的，但其客觀情況往往有一定的公開性，只要對周圍情況進行調(diào)查研究，就有可能判斷該電報屬于哪方面的內(nèi)容，如戰(zhàn)爭、外交和重大事件等。另外，客觀情況有其相對的穩(wěn)定性，在一定的時間內(nèi)不會有大的變化等。充分利用這些情況規(guī)律，有助于破譯的成功。6.3.3密碼破譯方式

1.唯密文攻擊

唯密文攻擊是指密碼破譯者除了擁有截獲的密文以及對密碼體制和密文信息的一般了解外，沒有其它可以利用的信息用于破譯密碼，即僅被限于對所用語言的統(tǒng)計特性的了解和對某些可能字的了解。在這種情況下進行密碼破譯是最困難的，經(jīng)不起這種攻擊的密碼體制被認為是完全不保密的。

2.已知明文攻擊

已知明文攻擊是指破譯者不僅掌握了相當數(shù)量的密文，還有一些已知的明文—密文對(通過某種手段得到的)可供利用?，F(xiàn)代密碼體制不僅要經(jīng)受得住唯密文攻擊，而且要經(jīng)受得住已知明文攻擊。

3.選擇明文攻擊

選擇明文攻擊是指密碼破譯者不僅能夠獲得一定數(shù)量的明文—密文對，還可以用他選擇的任何明文，在同一未知密鑰的情況下能加密得到相應(yīng)的密文。

4.選擇密文攻擊

選擇密文攻擊是指密碼破譯者能選擇不同的被加密的密文，并可得到對應(yīng)的解密的明文，據(jù)此破譯密鑰及其它密文。6.3.4密碼破譯方法

1.窮舉法

窮舉法是指對截獲的密文依次用各種可能的密鑰進行破譯嘗試，直到得到有意義的明文為止；或?qū)⒚荑€固定，對所有可能的明文加密，直到結(jié)果與截獲的密報一致為止。此法又稱為完全試湊法。

只要有足夠多的計算時間和存儲容量，理論上講窮舉法總是可以成功的，但實際應(yīng)用中，只要密碼體制設(shè)計得比較安全，窮舉法往往是不行的。

2.分析法

分析法主要有確定性分析法和統(tǒng)計分析法兩大類。確定性分析法是利用一個或幾個已知量，如密文-明文對等，用數(shù)學關(guān)系式表示出所求的未知量。已知量和未知量的關(guān)系視加密和解密的算法而定，尋求這種關(guān)系是確定性分析法的關(guān)鍵所在。統(tǒng)計分析法是指利用明文的已知統(tǒng)計規(guī)律進行破譯，密碼破譯者通過對截獲的密文進行統(tǒng)計分析，總結(jié)出統(tǒng)計規(guī)律，并與明文的統(tǒng)計規(guī)律進行對比，從中分析明文和密文之間的對應(yīng)關(guān)系或密碼變換信息。6.3.5密碼破譯步驟

密碼破譯步驟分為整理分類、統(tǒng)計分析、假設(shè)和反證三步。整理分類是指將截獲的大量密文進行整理分類，并將同一密碼體制加密的密文識別出來，歸為同一類。由于不同密碼體制的密碼規(guī)律不同，因此不可能做到將不同的密碼體制的密文放在一起進行破譯。統(tǒng)計分析是利用計算機對截獲的大量密文進行單字母、雙字母和三字母等各種統(tǒng)計。這些統(tǒng)計應(yīng)盡可能詳細，并力求發(fā)現(xiàn)不隨機的現(xiàn)象，經(jīng)過分析，以確定密碼編制的方法，從而暴露出密碼規(guī)律。假設(shè)和反證的方法在于，一個密碼體制之所以能被破譯，其主要原因是明文與密文之間、密文與明文之間存在著關(guān)聯(lián)性、可比較性和可反證性。

6.4Shannon保密理論

6.4.1理論保密體制

Shannon通過對保密性理論的研究，提出了理論上不可破譯的密碼體制有完全保密與理想保密兩種體制，即無論密碼分析者有多少時間和人力資料，無論其能截獲多大的密文量，他都破譯不了這兩種密碼體制，當然其前提條件是密碼分析僅有截獲的密文。

所謂完全保密體制，是指在這種密碼體制中明文數(shù)、密鑰數(shù)和密文數(shù)相等，即將每個明文變換成每個密文都恰好有一個密鑰，所有的密鑰都是等可能的。在完全保密體制下，沒有給密碼分析任何額外的可用于破譯的信息。因此，密碼分析者無法破譯這種體制。所謂理想保密體制，是指唯一解距離U趨于無