信息論與密碼學介紹

現(xiàn)代密碼學——

信息論與密碼學介紹計算機科學與技術學院信息論與密碼學信息論從一誕生就與密碼學結(jié)下了不解之緣。Shannon最早在1949年將信息論引入到密碼學中，提出了完善保密的體制；而完善保密體制要求密鑰和明文至少一樣長，使得完善保密在現(xiàn)實中難以實現(xiàn)。直到最近十幾年量子密碼的研究，又使得信息理論安全模型重新被推回到研究者的視野中，無條件安全密鑰協(xié)商成為研究熱點。信息論與密碼學之后，信息理論安全模型又引入到模糊提取中，即從生物特征等模糊保密數(shù)據(jù)中直接提取出密碼體制中所需要的密鑰。無條件安全密鑰協(xié)商和模糊提取有共同之處，都需要糾錯和從部分保密的數(shù)據(jù)中提取密鑰，因此信息論、糾錯碼、無條件認證碼等理論與技術的成熟為無條件安全密鑰協(xié)商和模糊提取的研究奠定了堅實的基礎。引言

信息論主要研究信息的測度、信道容量、信息率失真函數(shù)，與這三個概念相對應的香農(nóng)三定理以及信源和信道編碼.它是用概率論和數(shù)理統(tǒng)計方法，從量的方面來研究通信系統(tǒng)的信息如何獲取、加工、處理、傳輸和控制的一門科學。

通信系統(tǒng)模型信源：消息的來源編碼器：把消息變換成信號信道:傳遞信號的媒介,在物理線路上劃分的邏輯通道。譯碼器：把信道輸出的信號反變換信宿：信息的接受端噪聲：信道中的干擾一、如何度量信息二、信道容量三、信息率失真函數(shù)四、香農(nóng)三大編碼定理五、常用的編碼方法六、信息論與密碼體制的安全測度二、信道容量三、信息率失真函數(shù)四、香農(nóng)三大編碼定理五、常用的編碼方法六、信息論與密碼體制的安全測度一、如何度量信息

一、如何度量信息信息是由信源發(fā)出的，在研究度量信息之前，首先研究一下信源。信源隨機矢量離散信源連續(xù)信源單符號多符號隨機變量隨機過程單符號離散信源的數(shù)學模型為：

1、單符號的離散信源考慮有兩個隨機事件的離散信源數(shù)學模型為：自信息量聯(lián)合自信息量條件自信息量互信息量條件互信息量信息量對單個信息自信息量單位：比特(2為底)、奈特（e為底）、笛特/哈特（10為底）1提醒:不確定度表示含有多少信息，信息量表示隨機事件發(fā)生后可以得到多少信息。有聯(lián)合自信息量代表X與Y同時發(fā)生時的信息量2聯(lián)合自信息量條件自信息量

3自信息量、條件自信息量和聯(lián)合自信息量之間有如下關系式：

互信息量4信宿Y的數(shù)學模型為：信源發(fā)出消息ai,信宿收到bj,二者的比正好體現(xiàn)出其交互信息量.是，也是的已知條件。5條件互信息量信源整體的信息量如何度量？

平均互信息量信源熵聯(lián)合熵條件熵加權熵信源整體的信息量信源熵：各離散消息自信息量的數(shù)學期望，即信源的平均自信息量。還稱為信源的信息熵；香農(nóng)熵；無條件熵；熵函數(shù)；熵的單位：比特/符號。1信源熵信源熵和平均自信息量兩者在數(shù)值上是相等的，但含義并不相同。信源熵表征信源的平均不確定度，平均自信息量是消除信源不確定度所需要的信息的量度。信源一定，不管它是否輸出離散消息，只要這些離散消息具有一定的概率特性，必有信源的熵值，這熵值在總體平均的意義上才有意義，因而是一個確定值。

在離散信源的情況下，信源熵的值是有限的。而信息量只有當信源輸出離散消息并被接收后，才有意義。這就是給予接收者的信息度量。這值本身可以是隨機量，如前面所講的自信息量。也可以與接收者的情況有關。當信源輸出連續(xù)消息時,信息量的值可以是無窮大。

信源熵與信息量的比較信源的平均不確定度消除不定度所需信息與信源是否輸出無關接收后才得到信息確定值一般為隨機量有限值可為無窮大

熵信息量總括起來，信源熵有三種物理含義：

信源熵H(X)表示信源輸出后，離散消息所提供的平均信息量。信源熵H(X)表示信源輸出前，信源的平均不確定度。信源熵H(X)反映了變量X的隨機性123條件熵2

H(X/Y)

表示輸出端在收到一個符號后，信源X的不確定度,若H(X/Y)0,表示信源X尚存不確定性，所以這個條件熵稱為信道疑義度，也是因為信道干擾造成了信息的損失，因此也稱損失熵.如果沒有損失,那么損失熵H(X/Y)=0,一般情況下不確定度H(X/Y)小于H(X)，說明經(jīng)過信道傳輸，總能消除一些信源的不確定性，從而獲得一些信息。

H(Y/X)

表示輸入端發(fā)出一個符號后，信宿Y的不確定度,若H(Y/X)0，表示信宿Y尚存的不確定性，這是因為信道噪聲造成的，因此稱噪聲熵.3聯(lián)合熵稱疑義度,或損失熵.稱噪聲熵.4加權熵香農(nóng)信息的局限：沒有考慮收信者的主觀特性和主觀意義,不考慮收信者主觀感受的不同，同一消息對任何收信者，所得信息量相同。設信源為:重量，即權重系數(shù)。構造重量空間加權熵定義信息的加權熵從某種程度上反映了人的主觀因素。5平均互信息量平均互信息量Y對X的也稱平均交互信息量或交互熵同理，X對Y的平均互信息：平均互信息的物理意義

平均互信息量是收到Y(jié)前、后關于X的不確定度減少的量，即由Y獲得的關于X的平均信息量。

H(X/Y)

表示輸出端在收到Y(jié)后，信源X的不確定度,說明經(jīng)過信道傳輸，總能消除一些信源的不確定性，從而獲得一些信息。則:

I(X;Y)=H(X)-H(X/Y)正好是經(jīng)過信道傳輸后，所消除的信源的不確定性，從而獲得的信息.先驗不確度后驗不確定度

表示發(fā)送X前、后，關于Y的平均不確定度減少的量。H(Y/X)正好是通信后，所消除的信宿Y的不確定性，從而獲得了一些信息.各種熵之間的關系H(X),H(Y)－信源熵，無條件熵H(X/Y)－疑義度，損失熵H(Y/X)－噪聲熵H(XY)－聯(lián)合熵I(X;Y)－平均互信息量，交互熵XYXYXYXYXY發(fā)出符號序列的無記憶信源也稱為多符號離散平穩(wěn)無記憶信源，它輸出的消息序列中各符號之間無相互依賴關系。亦稱為單符號離散平穩(wěn)無記憶信源的擴展信源。發(fā)出符號序列的有記憶信源是用信源發(fā)出的一個符號序列的整體概率，即N個符號的聯(lián)合概率來反映有記憶信源的特征。發(fā)出符號序列的馬爾可夫信源是用信源發(fā)出的符號序列中各個符號之間的條件概率來反映記憶特征。2、多符號離散平穩(wěn)信源平穩(wěn)信源如果各維聯(lián)合概率分布均與時間起點無關，即對兩個不同的時刻i和j，有這種各維聯(lián)合概率均與時間起點無關的完全平穩(wěn)信源稱為離散平穩(wěn)信源。則該信源的N次擴展信源為：設一個離散無記憶信源為：2.1單符號離散平穩(wěn)無記憶信源的擴展信源可證明序列信息的熵為：根據(jù)信息熵的定義，序列信息熵為：二維信源2.2發(fā)出符號序列的有記憶信源一般地不確定性降低N維信源平均符號熵：極限熵：平均符號熵：極限熵：可以證明對于一般信源，求出極限熵是很困難的，然而，一般來說，取N不大時就可以得到與極限熵非常接近的條件熵和平均符號熵，因此可以用條件熵和平均符號熵來近似極限熵2.3馬爾可夫信源

對于一般的有記憶平穩(wěn)多符號離散信源,要求極限熵相當困難,因此可以用條件熵和平均符號熵來近似極限熵.我們希望N不大時,條件熵和平均符號熵也很接近極限熵,馬爾可夫信源就是在這種背景下提出來的.

在很多信源的輸出序列中，符號之間的依賴關系是有限的，任何時刻信源符號發(fā)生的概率只與前邊已經(jīng)發(fā)出的若干個符號有關，而與更前面的符號無關。為了描述這類信源除了信源符號集外還要引入狀態(tài)集。這時，信源輸出消息符號還與信源所處的狀態(tài)有關。

若一個信源滿足下面兩個條件，則稱為馬爾可夫信源：（1）某一時刻信源輸出的符號的概率只與當前所處的狀態(tài)有關，而與以前的狀態(tài)無關；（2）信源的下一個狀態(tài)由當前狀態(tài)和下一刻的輸出唯一確定。特點：有限的相關符號組構成的序列1、有限記憶長度；

3、發(fā)出一個個符號，每發(fā)一個符號狀態(tài)要發(fā)生轉(zhuǎn)移。2、信源輸出不僅與符號集有關，而且與狀態(tài)有關；狀態(tài)具體地說，狀態(tài)是指與當前符號有關的前面m個隨機變量系列：的一個具體消息，記為：其中：每種狀態(tài)以一定概率發(fā)生,其數(shù)學模型為：有關,所以當信源處于某一狀態(tài)si時，若再發(fā)出一個符號akm+1后，所處的狀態(tài)就變了，轉(zhuǎn)移到另一狀態(tài)sj。所以sj只與si和akm+1有關,即任何時刻信源處在什么狀態(tài)完全由前一時刻的狀態(tài)和發(fā)出的符號決定。由于符號Xm+1只與前面m個隨機變量系列：由m階馬爾可夫信源的定義,并考慮其平穩(wěn)性，可以推導出還可以進一步證明:對于馬爾可夫信源,平均每發(fā)一個符號(不是一個消息)的信息量為:

平穩(wěn)信源（如果不平穩(wěn)則先把其變成分段平穩(wěn)的）21注意階馬爾可夫信源需滿足如下條件,H

就存在:元在，對并非在任何情況下都存mnH￥1馬爾可夫信源發(fā)出一個個符號，有限長度有記憶信源發(fā)出一組組符號；

一般有記憶信源用聯(lián)合概率描述符號間的關聯(lián)關系，馬爾可夫信源用條件概率（狀態(tài)轉(zhuǎn)移概率）來描述符號間的關聯(lián)關系；m階馬爾可夫與一般記憶長度為m的有記憶信源的區(qū)別：212馬爾可夫信源記憶長度雖然有限，但依賴關系延伸到無窮遠。長為m的有限記憶信源符號間的依賴關系僅限于每組內(nèi)，組與組之間沒有依賴關系；34若是有記憶平穩(wěn)信源,也可以用條件熵.3、連續(xù)信源連續(xù)信源可分為單變量連續(xù)信源和多變量連續(xù)信源；單變量連續(xù)信源可看作是取值連續(xù)的隨機變量；可用密度函數(shù)、聯(lián)合密度和條件密度描述。單變量連續(xù)信源的數(shù)學模型為：并滿足連續(xù)信源熵（相對熵）定義：

此熵稱為相對熵，與離散信源的絕對熵不同其他連續(xù)熵的定義：平均互信息量的定義：最大連續(xù)熵定理對離散信源來說，若信源呈等概率分布時，信源熵取得最大值。對連續(xù)信源來說，信源熵不一定取得最大值，須加一些限制條件。在不同的限制條件下，有不同的最大連續(xù)熵。三、信息率失真函數(shù)四、香農(nóng)三大編碼定理五、常用的幾種編碼方法六、信息論與密碼體制的安全測度一、如何度量信息二、信道容量信道，通俗地說，是指以傳輸媒質(zhì)為基礎的信號通路。信道的作用是傳輸信號。

信道對于信息率的容納并不是無限制的，它不僅與物理信道本身的特性有關，還與信道輸入信號的統(tǒng)計特性有關，它有一個極限值，即信道容量，信道容量是有關信道的一個很重要的物理量。下面只介紹如何定義信道容量。

二、信道容量信道的數(shù)學模型和分類P(Y/X)xY信道的數(shù)學模型：{X

P(Y/X)Y}信道的輸入為一個隨機變量X，相應的輸出為隨機變量為Y。對于一個離散信道應有三個參數(shù)：輸入符號集：X={x1，x2，…，xn}輸出符號集：Y={y1，y2，…，ym}信道轉(zhuǎn)移概率：P(Y/X)={p(y1/x1),p(y2/x1),…,p(ym/x1),…,p(y1/xn),…,p(ym/xn)}信道容量的定義

對于固定信道，總存在某種輸入概率分布，使信道所能傳送的信息率R=I（X;Y）達到最大值，定義這個最大值為信道容量，記為C。使I(X;Y)達到信道容量的分布為最佳分布。單位時間信道容量

若信道平均傳輸一符號需t秒種，則單位時間的信道容量為:

信道容量是完全描述信道特性的參量，是信道能夠傳送的最大信息量。三、信息率失真函數(shù)一、如何度量信息二、信道容量四、香農(nóng)三大編碼定理五、常用的幾種編碼方法六、信息論與密碼體制的安全測度

實際通信系統(tǒng)允許一定的失真存在,有時也沒必要要求完全無失真?zhèn)鬏敗?/p>

因此,在實際通信系統(tǒng)中,在保真度準則下,允許信源輸出有一定的失真存在。也就是說,允許壓縮信源輸出的信息率。

那么在允許一定程度失真的條件下，能夠把信源信息壓縮到什么程度，就是我們要講的信息失真率函數(shù)。三、信息率失真函數(shù)1、失真函數(shù)信源信源編碼信道編碼信道信道譯碼信源譯碼信宿干擾根據(jù)信道編碼定理，我們可以把信道編碼、信道和信道解碼等價成是一個沒有任何干擾的廣義信道，這樣收信者收到消息后，所產(chǎn)生的失真只是由信源編碼帶來的。我們也可以把信源編碼和信源譯碼等價成一個信道。我們稱此信道為試驗信道。信源信宿試驗信道現(xiàn)在我們要研究在給定允許失真的條件下，是否可以設計一種信源編碼使信息傳輸率為最低。為此，我們首先討論失真的測度。設離散信源概率分布為

稱為單個符號的失真度（或稱失真函數(shù)）.經(jīng)信道傳輸后輸出序列為:

對任一指定一個非負數(shù)

失真函數(shù)用來表征信源發(fā)出一個符號ai，而在接收端再現(xiàn)成符號bj所引起的誤差或失真。d越小表示失真越小，等于0表示沒有失真。可以將所有的失真函數(shù)排列成矩陣的形式：我們稱它為失真矩陣。1常用失真函數(shù)漢明失真稱為2稱平方誤差失真函數(shù).稱絕對值誤差失真測度

由于ai和bj都是隨機變量，所以失真函數(shù)d(ai，bj)也是隨機變量，限失真時的失真值，只能用它的數(shù)學期望或統(tǒng)計平均值，因此將失真函數(shù)的數(shù)學期望稱為平均失真度，記為

平均失真度平均失真是對在給定信源分布p(x)條件下，通過有擾信道傳輸而引起失真的統(tǒng)計平均度量。

若平均失真度不大于我們所允許的失真D(預先給定的某一限定值)，我們稱此為保真度準則。凡滿足保真度準則的這些試驗信道稱為D失真許可的試驗信道。把所有D失真許可的試驗信道組成一個集合，用符號BD表示。為D失真許可的

試驗信道平均失真由信源分布p(ai)、假想信道的轉(zhuǎn)移概率p(bj/ai)和失真函數(shù)d(ai,bj)決定，若p(ai)和d(ai,bj)已定，則調(diào)整使1、D允許試驗信道

2、信息率失真函數(shù)R(D)

由于互信息取決于信源分布和信道轉(zhuǎn)移概率分布，當p(ai)一定時，互信息I是關于p(bj/ai)的下凸函數(shù)，存在極小值。因而在上述允許信道PD中，可以尋找一種信道p(bj/ai)使給定的信源p(ai)經(jīng)過此信道傳輸后，互信息I(X；Y)達到最小。該最小的互信息就稱為信息率失真函數(shù)R(D)，即

R(D)的物理意義：對于給定的信源，在滿足保真度準則下，必須傳送的最小信息量,它既反映了用戶容忍程度,也反映了信息率允許壓縮的最小值,R(D)越大,越難壓縮,反之可壓縮率就大.對于固定的信源分布，平均互信息量I(X;Y)是信道轉(zhuǎn)移概率

的下凸函數(shù)。也就是說:存在一個信道使某一特定信源經(jīng)過此信道傳輸時，信道的平均互信息達到極小值.連續(xù)信源的信息率失真函數(shù)定義下確界定義PD為滿足保真度準則:設平均互信息:的試驗信道集合.則連續(xù)信源的信息失真函數(shù)定義為:三、信息率失真函數(shù)一、如何度量信息二、信道容量四、香農(nóng)三大編碼定理五、常用的編碼方法六、信息論與密碼體制的安全測度香農(nóng)第一定理

如果編碼后的信源序列信息傳輸速率不小于信源的熵，那么一定存在一種無失真信源編碼方法；否則，不存在這樣的一種無失真信源編碼方法。香農(nóng)第二定理如果信息傳輸速率小于信道容量，那么總可以找到一種編碼方式，使得當編碼序列足夠長時傳輸差錯任意??；否則，不存在使差錯任意小的信道編碼方式。信道容量如堤壩的承受量，香農(nóng)第二定理就好比說：超過這個承受量就不能保證安全運行，低于這個承受量就能在發(fā)生較小事故的情況下運行。香農(nóng)第三定理對于任意的失真度，只要碼字足夠長，那么總可以找到一種編碼方法，使編碼后每個信源符號的信息傳輸率，而碼的平均失真度。香農(nóng)三大定理是信息論的基礎理論。香農(nóng)三大定理是存在性定理，雖然并沒有提供具體的編碼實現(xiàn)方法，但為通信信息的研究指明了方向。三、信息率失真函數(shù)一、如何度量信息二、信道容量四、香農(nóng)三大編碼定理五、常用的編碼方法六、信息論與密碼體制的安全測度五、常用的編碼方法對于離散信道編碼，有香農(nóng)編碼、費諾編碼、赫夫曼編碼、游程編碼等，對于連續(xù)信道編碼有LBG算法、預測編碼等。對于信源編碼，有分組碼、卷積碼。常用的有漢明碼、循環(huán)碼，都屬于線性分組碼。給兩個概率最小的符號各分配一個碼位，將其概率相加后合并作為一個新的符號，與剩下的符號一起，再重新排隊給縮減信源中概率最小的符號各分配一個碼元重復步驟2、3直至概率和為1243將信源符號按概率由大到小順序排隊1赫夫曼編碼設有一單符號離散無記憶信源試對該信源編Huffman碼。信源符號概率縮減信源碼字碼長0.250120.251020.21120.1500130.10000040.05000141

00.151

00.31

0111111111111

0

011.00.450.55Huffman編碼如下:進行赫夫曼編碼時，為得到碼方差最小的碼，應使合并的信源符號位于縮減信源序列盡可能高的位置上，以減少再次合并的次數(shù)，充分利用短碼。

三、信息率失真函數(shù)一、如何度量信息二、信道容量四、香農(nóng)三大編碼定理五、常用的編碼方法六、信息論與密碼體制的安全測度熵的密碼意義：

如果H(M)=0,則表示該信息不含任何不確定性，因此，該信息或該事件百分之百會發(fā)生。從通信的角度看，既然該信息百分之百會發(fā)生，意義就不大，沒有必要再發(fā)送。反之，如果H(M)很大，則表示信息的不確定性很大，從而收方收到該信息時，其信息量就相當大（重要）了。