【文章內容簡介】 很大差異，因此，實際中我們常常研究的是算法關于輸入規(guī)模 的所有實例的時間與空間需求的平均值。 算 法 復 雜 性 的 構 成 通常情況下，一個算法的計算復雜性由兩個變量度量：時間復雜性 和空間復雜性 。它們定義如下： （ 1） 時間復雜性 ：以某特定的基本步驟為單元，完成計算過程所需的總單元數(shù)稱為算法的時間復雜性，或時間復雜度。 n為輸入的規(guī)?；虺叽纭? （ 2） 空間復雜性 :以某特定的基本存儲空間為單元，完成計算過程所用的存儲單元數(shù)，稱為算法的空間復雜性或空間復雜度。 n是輸入的規(guī)模或尺寸。 )(nT )(nS)(nT )(nS 算法復雜性的基本符號 （ 1） 一個算法的計算復雜性用? O?符號表示其數(shù)量級。? O?的意思是：對于兩個任意的實值函數(shù) f和 g，若記號 ，則存在有一個值 a，對充分大的 n，有 。計算復雜性的數(shù)量級就是這種類型的函數(shù)，即當 n變大時增長得最快的函數(shù)，所有常數(shù)和較低階形式的函數(shù)可以忽略不計。 ??? nngOnf )),(()( )()( ngaf ? 算法復雜性的基本符號 （ 2） 另一個符號是? o?。它的定義是： 當且僅當 ，這意味著在 時， 比 可以忽略不計。 時間復雜度 有時也用工作因子 W表示，這時 。如果一個算法的復雜性不依賴于 n，那么它是常數(shù)級的用 表示之，而 表示復雜性隨 n線性增長，因而是線性型算法。復雜性隨 n線性增長的其他一些算法也稱為二次方或三次方等，所有這些算法都是多項式的，它們的時間復雜性是 。有多項式時間復雜性的算法稱為多項式時間算法或有效算法。 ??? nngonf )),(()(l im ( ) / ( ) 0n f n g n?? ???)(nf )(ng ))(( ngo )(ngW ?)1(o)(o)()( lnonT ? 3. 問 題 的 復 雜 性 問題的復雜性是問題固有的性質。問題的復雜性理論利用算法復雜性作為工具，將大量典型的問題按照求解的代價進行分類。問題的復雜性由在圖靈機上解其最難實例所需的最小時間與空間決定，還可以理解為由解該問題的最有效的算法所需的時間與空間來度量。 N P 問 題 在確定型圖靈機上可用多項式時間求解的問題，稱為易處理的問題。易處理的問題的全體稱為確定性多項式時間可解類，記為 P類。在非確定性圖靈機上可用多項式時間求解的問題，稱為非確定性多項式時間可解問題，記為 NP問題 。 NP問題的全體稱為非確定性多項式時間可解類，記為NP類。顯然， ，因為在確定型圖靈機上多項式時間可解的任何問題在非確定型圖靈機上也是多項式時間可解的。 NPP ? N P C 問 題 NP類中還有一類問題稱為 NP完全類，記為 NPC。所有的 NP問題都可以通過多項式時間轉換為 NPC中的問題。 NPC是 NP類中困難程度最大的一類問題 ,但NPC中的問題困難程度相當，都可以多項式時間轉化為稱為可滿足性問題的 NPC問題，此類 NPC具有如下性質，若其中的任何一個問題屬于 P，則所有的 NP問題都屬于 P，且 。現(xiàn)在的密碼算法的安全性都是基于 NPC問題的，破譯一個密碼相當于求解一個NPC問題 ,如果 ，則破譯密碼就是一件很容易的事情 . NPP ? NPP ? 信息加密方式與標準 經(jīng)典的信息加密理論主要用于通信保密，而現(xiàn)代信息加密技術的應用已深入到信息安全的各個環(huán)節(jié)和對象，信息的加密方式和標準也有了深入廣泛的發(fā)展，特別是現(xiàn)代加密和信息隱藏技術的結合，實現(xiàn)信息隱蔽傳輸使人類對信息的加密技術有了新的認識和要求，下面介紹信息加密技術的基本概念、方式和標準。 信息加密基本概念 （ 1） 研究安全信息的加密技術和研究破解安全信息密碼的密碼分析技術的學科稱為 密碼學 。信息加密是通過使用一種編碼而使某些可讀的信息 (明文 )變?yōu)椴豢勺x的信息 (密文 )。這些編碼就是將明文變成密文的加密算法 (也稱為密碼 )或數(shù)學方法。密碼使用隱蔽語言、文字、圖象的特種符號，目標是接收數(shù)據(jù)作為輸入，產生密文作為輸出，以便數(shù)據(jù)的原始意義得以隱藏。在計算機通訊中，采用密碼（密鑰為參數(shù)）將信息隱蔽起來，再將隱蔽后的信息傳輸出去，使信息在傳輸過程中即使被竊取或載獲，也不能了解信息的內容，從而保證信息傳輸?shù)陌踩? 信息加密基本概念 （ 2） 通信兩端將信息編碼時，發(fā)送端使用簡單的信息加密；接收端收到傳來的信息后通過解密看到編碼前的信息，整個過程中加密或解密是由密鑰控制實現(xiàn)的。 密鑰 是用戶按照一種密碼體制隨機選取，它通常是一隨機字符串，是控制明文變換（加密）和密文變換（解密）的唯一參數(shù)。密鑰全體稱為密鑰空間。一般來說，密鑰越大，加密就越健壯。 加密系統(tǒng)的組成部分 如上所述，一個加密系統(tǒng)實際上是某種加密算法在密鑰控制下實現(xiàn)的從明文到密文的映射，它至少包括下面四個組成部分： （ 1）加密的報文，也稱明文； （ 2）加密后的報文，也稱密文； （ 3）加密解密設備或算法； （ 4）加密解密的密鑰； 一般情況下，密鑰由 K表示，明文由 m表示，加密算法由 ( ) 表示，解密算法由 ( ) 表示，； 則， ( ( m )) =m 2DK1EK 加密系統(tǒng)示意圖 一個完整的加密系統(tǒng)如下圖所示 : 信源 加密 解密 信宿 密文 明文 竊聽 干擾 明文 密鑰 K1 密鑰 K2 圖 加密系統(tǒng)示意圖 加密系統(tǒng)的安全規(guī)則 （ 1） 任何一個加密系統(tǒng)必須基本具備四個安全規(guī)則： （ 1）機密性 (confidentiality)：加密系統(tǒng)在信息的傳送中提供一個或一系列密鑰來把信息通過密碼運算譯成密文，使信息不會被非預期的人員所讀取，只有發(fā)送者和接收者應該知曉此信息的內容。 加密系統(tǒng)的安全規(guī)則 （ 2） （ 2）完整性 (integrity)：數(shù)據(jù)在傳送過程中不應被破壞，收到的信宿數(shù)據(jù)與信源數(shù)據(jù)是一致的。應該選取健壯的密碼和加密密鑰，以確保入侵者無法攻破密鑰或找出一個相同的加密算法，阻止入侵者會改變數(shù)據(jù)后對其重新加密。有時，數(shù)據(jù)完整性可以通過適當?shù)姆椒ㄔ谛畔⑦€未被完全修改時檢測到，如：密碼散列函數(shù)是單向密碼，它為明文產生惟一的?指紋?，當明文被攔截和讀取，要修改它將改變散列，致使有意向的接收者很容易看出散列之間的差異。 加密系統(tǒng)的安全規(guī)則 （ 3） （ 3）認證性 (authentication) ：加密系統(tǒng)應該提供數(shù)字簽名技術來使接收信息用戶驗證是誰發(fā)送的信息，確定信息是否被第三者篡改。只要密鑰還未泄露或與別人共享，發(fā)送者就不能否認他發(fā)送的數(shù)據(jù)。實際應用中，假如發(fā)送者和接收者都使用一個對稱密鑰，對于整體信息加密或計算機網(wǎng)絡上的鏈路級加密，在兩個路由器之間建立一個加密會話，以通過因特網(wǎng)發(fā)送加密信息。連接到網(wǎng)絡的計算機發(fā)送明文給路由器，明文被轉換為密文，然后通過因特網(wǎng)發(fā)送到另一端的路由器。在整個加密數(shù)據(jù)形成和傳遞過程中，加密方網(wǎng)絡內部和非加密方的任一節(jié)點都能插入信息，并在這一層次分析，但對于接收者這一節(jié)點來說你只能判定信息是否來自某個特定的網(wǎng)絡，而要確認信息的發(fā)送節(jié)點，這將使驗證機制變得很復雜。 加密系統(tǒng)的安全規(guī)則 （ 4） （ 4）非否定 (nonrepudiation)：加密系統(tǒng)除了應該驗證是誰發(fā)送的信息外，還要進一步驗證收到的信息是否來自可信的源端，實際上是通過必要的認證確認信息發(fā)送者是否可信?，F(xiàn)代健壯的驗證方法用加密算法來比較一些已知的信息段，如 PIN(個人識別號 )判斷源端是否可信。 非否定規(guī)則應屬于認證性規(guī)則中的一部分。一般來說，前三個規(guī)則一起被稱為 CIA 。從技術的角度來看，所有的加密都提供了私有性和完整性，其余的均由此衍生，這包括非否定和認證性規(guī)則。 信息加密方式 1. 信息加密方式分類 對存儲的文件和網(wǎng)絡中傳輸?shù)臄?shù)據(jù)包實施信息加密，其加密方式可以根據(jù)加密系統(tǒng)不同的特征劃分 ： （ 1） 按密鑰方式劃分 對稱式加密 ： 收發(fā)雙方使用相同密鑰。加密和解密使用同一密鑰。加密算法和解密算法在對稱式加密中是相同的，加密和解密使用同一密鑰 K表示。 非對稱式加密 ： 也稱公用密鑰加密，加密和解密使用不同密鑰。它通常有兩個密鑰，稱為?公鑰?和?私鑰?。它們兩個必需配對使用，否則不能打開加密文件。這里的?公鑰?是指可以對外公布的，?私鑰?則不對外公布，只有持有人知道。加密算法和解密算法在非對稱式加密中是不相同的； K1是加密密鑰 ,是公開的，稱為公鑰， K2是解密密鑰，稱為私鑰，則須保密。 2種不同方式的加密示意圖 明文 解密 密鑰 K2 明文 加密 密鑰 K2 K K 密文傳輸 圖 對稱式 加密示意圖 明文 解密 密鑰 K2 K1 K2 加密 密鑰 K2 明文 圖 非對稱式 加密示意圖 1. 信息加密方式分類 （ 2）按保密程度劃分 理論上保密的加密：無論獲取多少密文和有多大的計算能力，對于明文始終不能得到唯一解的加密方法。如：采用客觀隨機一次出來的密碼就屬于這種加密方式。 實際上保密的加密：從理論的角度是可以破解的，但在現(xiàn)有客觀條件下，無法通過計算來確定唯一解。 （ 3）按明文形態(tài)劃分 模擬信息加密：用來加密模擬信息。如：動態(tài)范圍之內，連續(xù)變化的語音信號的加密。 數(shù)字信息加密：用來加密數(shù)字信息。如：兩個離散電平構成 0、1二進制關系的電報信息的加密。 2. 數(shù) 字 簽 名 數(shù)字簽名是對原信息附上加密信息的過程，是一種身份認證技術，支持加密系統(tǒng)認證性和非否定；簽名者對發(fā)布的原信息的內容負責，不可否認。數(shù)字簽名采用非對稱式加密（也稱公鑰加密標準）對信息 m使用私鑰 K2加密，運算如下：S=DK2(m) 其中 S為簽名， D為解密算法；接收者收到發(fā)送者發(fā)來的 S和 m信息，同時從公開媒體找到了發(fā)送者的公鑰 K1, 發(fā)送者用 K2對 S進行如下運算： E K1 (S)= E K1 (DK2(m))= m , E為加密算法；收到的 m對應計算出來的 m，結果說明信息確實來源于發(fā)送者，第三方不可能知道私鑰 K2，無法篡改 S，發(fā)送者無法否認發(fā)送 m信息。在實際工作中，由于解密計算緩慢，為了提高簽名速度， m信息往往要經(jīng)過壓縮或散列處理或盡量取簡短信息，如公鑰數(shù)據(jù)等。 數(shù)字簽名工作流程圖 信息 m 密鑰 K2 私鑰 K 2 公鑰 K1 信息 m 密鑰 K2 解密算法 密鑰 K2 簽名 S 密鑰 K2 簽名 S 密鑰 K2 加密算法 密鑰 K2 圖 數(shù)字簽名工作流程圖 3. 網(wǎng) 絡 信 息 加 密 網(wǎng)絡信息加密的目的是保護網(wǎng)內的數(shù)據(jù)、文件、口令和控制信息，保護網(wǎng)上傳輸?shù)臄?shù)據(jù)。網(wǎng)絡加密常用的方式有鏈路加密和端點加密。 （ 1）鏈路加密 鏈路加密對鏈路層數(shù)據(jù)單元進行加密保護，其目的是保護網(wǎng)絡節(jié)點之間的鏈路信息安全。這種加密不但對節(jié)點之間之間傳輸?shù)臄?shù)據(jù)報文加密，還要把路由信息、校驗和控制信息包括數(shù)據(jù)鏈路層的幀頭、位填充和控制序列等都進行加密；當密文傳輸?shù)侥骋还?jié)點時，全部解密獲得鏈信息和明文，然后全部加密后發(fā)送往下一個節(jié)點；對于這種加密，加密設備的設計相對復雜，必須理解鏈路層協(xié)議和必要的協(xié)議轉換。 鏈路加密的優(yōu)缺點 鏈路加密非常有效，是因為幾乎任何有用消息都被加密保護。加密范圍包括用戶數(shù)據(jù)、路由信息和協(xié)議信息等。因此，攻擊者將不知道通信的發(fā)送和接受者的身份、不知道信息的內容、甚至不知道信息的長度以及通信持續(xù)的時間。而且，系統(tǒng)的安全性將不依賴任何傳輸管理技術。密鑰管理也相對簡單，僅僅是線路的兩端需要共同的密鑰。線路兩端可以獨立于網(wǎng)絡的其他部分更換密鑰。