【正文】 名速度， m信息往往要經(jīng)過壓縮或散列處理或盡量取簡短信息，如公鑰數(shù)據(jù)等。 2. 數(shù) 字 簽 名 數(shù)字簽名是對原信息附上加密信息的過程，是一種身份認證技術(shù)，支持加密系統(tǒng)認證性和非否定；簽名者對發(fā)布的原信息的內(nèi)容負責，不可否認。 數(shù)字信息加密：用來加密數(shù)字信息。 （ 3）按明文形態(tài)劃分 模擬信息加密：用來加密模擬信息。如：采用客觀隨機一次出來的密碼就屬于這種加密方式。加密算法和解密算法在非對稱式加密中是不相同的； K1是加密密鑰 ,是公開的，稱為公鑰， K2是解密密鑰，稱為私鑰，則須保密。它們兩個必需配對使用，否則不能打開加密文件。 非對稱式加密 ： 也稱公用密鑰加密，加密和解密使用不同密鑰。加密和解密使用同一密鑰。從技術(shù)的角度來看，所有的加密都提供了私有性和完整性，其余的均由此衍生，這包括非否定和認證性規(guī)則。 非否定規(guī)則應(yīng)屬于認證性規(guī)則中的一部分。 加密系統(tǒng)的安全規(guī)則 （ 4） （ 4）非否定 (nonrepudiation)：加密系統(tǒng)除了應(yīng)該驗證是誰發(fā)送的信息外，還要進一步驗證收到的信息是否來自可信的源端，實際上是通過必要的認證確認信息發(fā)送者是否可信。連接到網(wǎng)絡(luò)的計算機發(fā)送明文給路由器，明文被轉(zhuǎn)換為密文，然后通過因特網(wǎng)發(fā)送到另一端的路由器。只要密鑰還未泄露或與別人共享，發(fā)送者就不能否認他發(fā)送的數(shù)據(jù)。有時，數(shù)據(jù)完整性可以通過適當?shù)姆椒ㄔ谛畔⑦€未被完全修改時檢測到，如：密碼散列函數(shù)是單向密碼，它為明文產(chǎn)生惟一的?指紋?，當明文被攔截和讀取，要修改它將改變散列，致使有意向的接收者很容易看出散列之間的差異。 加密系統(tǒng)的安全規(guī)則 （ 2） （ 2）完整性 (integrity)：數(shù)據(jù)在傳送過程中不應(yīng)被破壞，收到的信宿數(shù)據(jù)與信源數(shù)據(jù)是一致的。一般來說，密鑰越大，加密就越健壯。 密鑰 是用戶按照一種密碼體制隨機選取，它通常是一隨機字符串，是控制明文變換（加密）和密文變換（解密）的唯一參數(shù)。在計算機通訊中，采用密碼（密鑰為參數(shù)）將信息隱蔽起來，再將隱蔽后的信息傳輸出去，使信息在傳輸過程中即使被竊取或載獲，也不能了解信息的內(nèi)容，從而保證信息傳輸?shù)陌踩＿@些編碼就是將明文變成密文的加密算法 (也稱為密碼 )或數(shù)學方法。 信息加密基本概念 （ 1） 研究安全信息的加密技術(shù)和研究破解安全信息密碼的密碼分析技術(shù)的學科稱為 密碼學 。 NPC是 NP類中困難程度最大的一類問題 ,但NPC中的問題困難程度相當，都可以多項式時間轉(zhuǎn)化為稱為可滿足性問題的 NPC問題，此類 NPC具有如下性質(zhì)，若其中的任何一個問題屬于 P，則所有的 NP問題都屬于 P，且 。 NPP ? N P C 問 題 NP類中還有一類問題稱為 NP完全類，記為 NPC。 NP問題的全體稱為非確定性多項式時間可解類，記為NP類。易處理的問題的全體稱為確定性多項式時間可解類，記為 P類。問題的復雜性由在圖靈機上解其最難實例所需的最小時間與空間決定，還可以理解為由解該問題的最有效的算法所需的時間與空間來度量。 ??? nngonf )),(()(l im ( ) / ( ) 0n f n g n?? ???)(nf )(ng ))(( ngo )(ngW ?)1(o)(o)()( lnonT ? 3. 問 題 的 復 雜 性 問題的復雜性是問題固有的性質(zhì)。復雜性隨 n線性增長的其他一些算法也稱為二次方或三次方等，所有這些算法都是多項式的，它們的時間復雜性是 。 時間復雜度 有時也用工作因子 W表示，這時 。 ??? nngOnf )),(()( )()( ngaf ? 算法復雜性的基本符號 （ 2） 另一個符號是? o?。? O?的意思是：對于兩個任意的實值函數(shù) f和 g，若記號 ，則存在有一個值 a，對充分大的 n，有 。 n是輸入的規(guī)模或尺寸。 n為輸入的規(guī)?；虺叽纭? 算 法 復 雜 性 的 構(gòu) 成 通常情況下，一個算法的計算復雜性由兩個變量度量：時間復雜性 和空間復雜性 。 由于算法所需的時間和空間往往取決于問題實例的規(guī)模 n (n表示了該實例的輸入數(shù)據(jù)長度 )，同時，算法在用于相同規(guī)模 n的不同實例時。對于一個問題 P，如果存在一個算法 A可解問題 P，我們稱問題 P是 算法可解 的。通常的計算機程序都可以看作是算法的表達形式，在問題的兩要素中，對算法而言，第一個要素就是?輸入?，第二個要素就是?輸出?。一個問題 可以看成是由無窮多個問題實例組成的一個類。它由兩個要素組成 ，第一個要素是描述所有的參數(shù)，也就是對所有未定參數(shù)的一般性描述 。那么 ； (3)對于整數(shù) , 根據(jù)算術(shù)基本定理， n可以分解成惟一的形如 的分解式，則 (4)若 和 互素，則 。我們把 和 的正的公倍數(shù)中最小的數(shù)稱為 和 的最小公倍數(shù)，記為 或 1a2 11a11a2a kaaa , 21 ? 1,1,1 21 kaaa ? kaa , 21 ?1a2a1a2 ],[ 21 aa ),( balcm 6. 歐拉 （ Euler） 函數(shù) 歐拉（ Euler）函數(shù) 設(shè) n≥1,歐拉函數(shù) 表示在區(qū)間 中與 n互素的整數(shù)的個數(shù)。 如果 ，則稱 l是 的公倍數(shù)。 定義 : 設(shè) ， 是兩個整數(shù)，我們把 和 的公約數(shù)中最大的數(shù)稱為 和 的最大公約數(shù)，記為 ( , )或 當 時，我們稱 和 是互素的。因為對于任意一個不等于零的整數(shù)，它的因數(shù)是有限的。而且，對每一個中間結(jié)果進行模 m運算，其作用與先進行全部運算，然后再進行模 m運算所得到結(jié)果是一樣的。注意：模運算的結(jié)果是從 0到 的一個整數(shù)。 （ 3）如果 ， ，則 。 )0( nrrqna ???? nar mod? )mod()mod( nbna ?( m od )a b n?? ?n 模 運 算 的 性 質(zhì) （ 1） 當且僅當 。歐拉函數(shù)的具體性質(zhì)會在后面第 6小節(jié)進行闡述） nZ*Z*n )(n? )(n? 4. 模 運 算 給定正整數(shù) n，對任意 a，若存在 q，使得 則稱 r是 a關(guān)于模 n的余數(shù)，記為 。顯然 , 中的元便是不超過 n并與 n互素的那些數(shù)，它們的個數(shù)等于歐拉函數(shù) 的值。于是 從 中分別取一個數(shù)作為代表構(gòu)成一個集合，稱為模 n的一個完全剩余系， 記為 ，稱為模 n的非負最小完全剩余系。 （ 5）如果 ， ， gcd ， (兩個不同時為 0的整數(shù) a與 b的最大公約數(shù)表示成 gcd(a,b))那么 ，存在 ,當且僅當 gcd 。如果 ，我們稱 b是 a對模 n的最小非負剩余，有時也稱 b為 a對模 n的余數(shù)。由 于 等價于 ，所以 與 等價。 （ 5）設(shè) 表示不大于 的素數(shù)的數(shù)目，則 。其中 , 是兩兩互不相同的素數(shù)， 是正整數(shù)。 關(guān)于素數(shù)，有以下性質(zhì)： （ 1）如果 p是素數(shù)，且 ，則 或 ，即 p至少整除 a與 b中的一個。如果它除了顯然因數(shù) 外沒有其他的因數(shù)，則 p就稱為是素數(shù)，也叫不可約數(shù)。 （ 5）設(shè) ,如果 ,那么 。由定義及乘法運算的性質(zhì)，可推出整除關(guān)系具有以下性質(zhì)（注：符號 本身包含了條件 ）： （ 1） ； （ 2）如果 且 ，則 ； （ 3）設(shè) ,那么 與 等價 。如果存在 使得 ，那么就說 b 可以被 a 整除，記為 ，且稱 b是 a的倍數(shù) ,a 是 b的因數(shù) (或稱約數(shù)、除數(shù)、因子 ) 。( ?vl cmI )()( lmHKH ? 數(shù)論基本術(shù)語 ? 數(shù)論是研究整數(shù)性質(zhì)的一個數(shù)學分支，同時也是加密技術(shù)的基礎(chǔ)學科之一。因此，完善保密系統(tǒng)存在的必要條件是 證明：若 ，則由前一個定理可得， ，所以 的必要條件是 )()( lmHKH ?() )()(lmHKH ? 0)。( KHmHcmI lvl ??() 0)。 0)),()( ?rvl kcmH )()),(。一個加密系統(tǒng)中，若其密文與明文之間的互信息 ，則密碼分析者無論截獲多大的密文，均不能得到有關(guān)明文的任何信息。(vllvl cmHmHcmI ?? )()()。這里 M、K和 C分別是明文、密鑰和密文空間， m、 k、c分別是它們的字母集， l ,r和 v分別是明文、密鑰、和密文的長度。 ?????? ?? )(1)P(x)](,[1121xPxxxPXi)(XH )xP )(xP 1)( 1 ?x 0)( ?XH 2/1)( 1 ?xP 信息熵函數(shù)曲線 P(x) 0 1 明文 H(x) 4. 信息熵在信息加密編碼中的作用 (1) 通過熵和信息量的概念，可計算加密系統(tǒng)中各部分的熵。 如果有兩個隨機變量 和 ， 它們彼此是統(tǒng)計獨立的，即 的概率分布為 ,而 的分布概率為 ,則聯(lián)合信源的熵 : 可加性是熵函數(shù)的一個重要特性，正因為有可加性，所以可以證明熵函數(shù)的形式是唯一的。這種非負性對于離散信源的熵來說，這一性質(zhì)并不存在。 ,0)()(,1)( 321 ???? ?xPxPxP 2( ) [ 1 l og 1 0 l og 0] 0niHX?? ? ? ? ? ??() 3. 信息熵的基本性質(zhì) (4) III. 非負性 即 。 )()( YHXH ? 3. 信息熵的基本性質(zhì) (3) II. 確定性 如果信源的輸出只有一個狀態(tài)是必然的 , 即 則信源的熵 : 此性質(zhì)表明，信源的輸出雖有不同形態(tài)，但其中一種是必然的，意味著其他狀態(tài)不可能出現(xiàn)。因此，熵反映了變量的隨機性，也是表征隨機變量統(tǒng)計特性的一個特征參數(shù)。當然 ,人們希望看第一場，因為勝負難卜，一旦賽完，人們獲得信息量大。例如，兩個信源，其概率空間分別為： 2. 信息量和信息熵基本定義 (5) 則信