北京師范大學數(shù)學學院楊進goodskyfly@163.com網(wǎng)絡與信息安全

2025/2/21第1頁問題復雜性第2章信息安全數(shù)學基礎（計算復雜性）算法復雜性2025/2/21第2頁問題復雜性第2章信息安全數(shù)學基礎（計算復雜性）算法復雜性2025/2/21第3頁為何要學習計算復雜性？計算復雜性是研究密碼分析對于計算量需求和密碼分析困難程度，從而得出這些密碼技術和算法在現(xiàn)有可行條件下是否含有足夠安全性。學習計算復雜性，需要掌握兩個概念：問題算法計算復雜性2025/2/21第4頁問題（problem）

（問題）定義：即需要回答普通性提問:它通常含有若干個參數(shù)。對于一個問題進行描述應該包含兩方面內容：必須對問題全部給定參數(shù)給出普通性描述；必須描述該問題答案（或解）應該滿足性質。當問題全部參數(shù)都有了確定取值時，我們稱得到了該問題一個實例（instance）。2025/2/21第5頁算法（algorithm）

定義（算法）：即求解某個問題一系列詳細步驟（通常被了解為求解所需通用計算程序）。算法總是針對詳細問題而言，求解一個問題算法通常不止一個。當某個算法能夠回答一個問題任何實例時，我們稱該算法能夠回答這個問題。當一個問題最少有一個能夠回答該問題算法時，我們稱該問題可解（resolvable），不然稱該問題不可解（unresolvable）。2025/2/21第6頁算法（algorithm）（續(xù)）

相關算法幾點注釋：算法總有輸入和輸出算法輸入大小普通用輸入變量長度（單位為位）來表示普通來說，算法用某種編程語言來實現(xiàn)計算機程序普通來說，我們僅僅關注處理問題最有效算法2025/2/21第7頁問題與算法問題：怎樣求解兩個整數(shù)a和b最大條約數(shù)？參數(shù)：a和b問題實例：a＝20，b＝30算法：利用因子分解求a＝20和b＝30最大條約數(shù)a＝2×2×5b＝2×3×5所以a和b最大條約數(shù)是2×5＝102025/2/21第8頁算法復雜性

（算法復雜度）定義：即度量該算法所需計算能力，包含：時間復雜性T（timecomplexity）；空間復雜性S（spacecomplexity）；信道帶寬；數(shù)據(jù)總量；……2025/2/21第9頁算法復雜性（續(xù)）計算復雜性表示符號為“O”（稱為“大O”，即算法階號），表示計算復雜性數(shù)量級

好處：使算法復雜性度量與處理器運行速度和指令運行時間無關；明確地揭示了輸入數(shù)據(jù)長度對算法復雜性影響。

2025/2/21第10頁算法復雜性（續(xù)）算法常見復雜性分類（1）常數(shù)算法（constantAlgorithm）：假如運行時間是O(1)，即該算法復雜性不依賴于n。（2）線性算法（linearAlgorithm）：假如運行時間是O(n)。（3）多項式算法（polynomialAlgorithm）：假如運行時間是O(nm)，其中m是一個常數(shù)。含有多項式復雜性算法族被稱為多項式時間算法。（4）超多項式算法（superpolynomialAlgorithm）：假如運行時間是，其中c是一個常數(shù)，而s(n)是關于n大于常數(shù)而小于線性函數(shù)。（5）指數(shù)算法（exponentialAlgorithm）：假如運行時間是，其中t是大于1常數(shù)，f(n)是關于n多項式函數(shù)。2025/2/21第11頁算法復雜性（續(xù)）算法常見復雜性分類普通而言，常數(shù)算法、線性算法、多項式算法和超多項式算法統(tǒng)稱為多項式算法。所謂多項式，就是含有以下形式一個函數(shù)：其中，k和ck是常數(shù)，且ci稱≠0為。當k>0時，k稱為多項式次數(shù)，ci稱為多項式系數(shù)。

2025/2/21第12頁算法復雜性算法分類及其運行時間

算法類型復雜性運算次數(shù)n＝106時間多項式算法常數(shù)算法O(1)11微秒線性算法O(n)1061秒二次多項式算法O(n2)101211.6天三次多項式算法O(n3)101832,0指數(shù)算法O(2n)10301030103010算法復雜性（續(xù)）2025/2/21第13頁算法復雜性算法復雜度增加速度算法復雜性（續(xù)）亞指數(shù)指數(shù)多項式2025/2/21第14頁算法復雜性（續(xù)）研究問題內在復雜性，即在圖靈機上處理最難問題實例所需最小時間和空間條件。圖靈機是一個含有沒有限讀、寫存放帶有限狀態(tài)機，能夠被看成一個實際可用計算模型。2025/2/21第15頁問題復雜性第2章信息安全數(shù)學基礎（計算復雜性）算法復雜性2025/2/21第16頁問題復雜性

圖靈機分為兩類：確定性圖靈機。非確定性圖靈機2025/2/21第17頁問題復雜性（續(xù)）確定性圖靈機。確定性圖靈機輸出結果只取決于輸入和初始狀態(tài)。所以，對于含有相同輸入和初始狀態(tài)，運行一個確定性圖靈機所得到結果是完全相同。非確定性圖靈機：能夠進行猜測。求解一個問題分兩個階段：猜測階段和驗證階段。2025/2/21第18頁圖靈機圖靈機包含一個有限狀態(tài)控制單元、k（≥1）條紙帶（Tape）和k個讀寫頭（Tapehead）。有限狀態(tài)控制單元控制每個讀寫頭訪問一條紙帶，并沿著紙帶左右移動圖靈機求解問題輸入是一個有限長度字符串，該輸入占據(jù)每條紙帶無限個單元最左邊有限個單元。讀寫頭對紙帶一次訪問稱之為一個正當移動（Move）。2025/2/21第19頁圖靈機（續(xù)）圖靈機求解問題時，被賦予一個初始狀態(tài)（InitialState），且一步一步地移動，從而完成對輸入掃描。假如圖靈機最終掃描了整個輸入串，且滿足了中止條件而停頓下來，則稱圖靈機識別了該輸入。不然，圖靈機在某一點沒有正當移動，所以會沒有識別輸入串而停頓下來，此時稱圖靈機無法識別該輸入。圖靈機所識別一個輸入，稱為一個可識別語言一個實例。2025/2/21第20頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第21頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第22頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第23頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第24頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第25頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第26頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第27頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第28頁圖靈機（續(xù)）比如：請設計一個圖靈機，用于證實某個非負整數(shù)是否能被3整除。2025/2/21第29頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1100)能被3整除。2025/2/21第30頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第31頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第32頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第33頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第34頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第35頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝12(二進制1011)能被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第36頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)不能被3整除。2025/2/21第37頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第38頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第39頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第40頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第41頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第42頁圖靈機（續(xù)）比如：請用DIV3圖靈機證實a＝13(二進制1101)被3整除。當前狀態(tài)紙帶上符號下一步移動下一個狀態(tài)q0（初態(tài)）01空右右響鈴或終止q0q1q101空右右輸出非整除信息q2q0q201空右右輸出非整除信息q1q22025/2/21第43頁問題復雜性

借助于圖靈機理論，問題復雜型實際上就是在圖靈機上處理最難問題實例所需要最小時間最小空間2025/2/21第44頁圖靈機（續(xù)）圖靈機M識別一個長度為n輸入串而移動步數(shù)稱為圖靈機時間復雜性，記為：當圖靈機M識別一個長度為n輸入串，其寫操作中讀寫頭所訪問紙帶單元數(shù)稱為圖靈機空間復雜性，記為：2025/2/21第45頁圖靈機（續(xù)）2025/2/21第46頁問題分類假如一個問題在確定性圖靈機上能夠在多項式時間內得處處理，則稱該問題時易處理（tractable）。也既是說，能夠用多項式時間處理問題稱之為易處理。不能夠在多項式時間內處理問題是難處理。因為伴隨輸入尺寸增加，求解這類問題需要時間快速變得很長，以至于不可能有效求解。難處理問題也被稱為是難解。2025/2/21第47頁P類問題易處理問題全體稱為“多項式時間可解類”，記為P類。復雜度類P包含全部能用多項式時間處理問題。上述定義表明，假如L是多項式時間內可識別語言，則確定性圖靈機能夠在多項式時間內，判定一個字符串是否屬于語言L。2025/2/21第48頁NP類問題有這么一類問題，即使不能夠用確定性圖靈機來有效求解，不過卻能夠用非確定性圖靈機在多項式時間內得處處理這類問題稱為“非確定性多項式時間可解問題”，簡稱NP問題。定義（NP類）NP類表示用非確定性圖靈機在多項式時間內能夠識別語言類。2025/2/21第49頁NP類問題（續(xù)）意義：能夠經(jīng)過非確定性多項式時間算法對許多對稱密鑰算法和全部公鑰算法進行攻擊。NP完全問題：指NP中任何一個問題都能夠經(jīng)過多項式時間轉化為該問題。NP完全問題全體被記為NPC。NP完全問題是NP問題中最難問題。

定義2.3.3（NP完全類）假如任意:

是非確定性多項式時間完全（NP完全）都能夠多項式規(guī)約到語言，則稱:2025/2/21第50頁NP類問題（續(xù)）NP中任何一個問題都能夠經(jīng)過多項式時間轉化為該問題。NP完全問題全體被記為NPC。NP完全問題是NP問題中最難問題。2025/2/21第51頁算法復雜性算法時間復雜度度量方法圖靈機處理問題所移動步數(shù)（該時間稱之為算法運行時間）該度量方法缺點：沒有考慮每一步詳細操作比如：加法和乘法計算開銷是不一樣為此，引入算法“按位”計算復雜度度量方法：考慮操作假如按位進行所需要執(zhí)行“步數(shù)”2025/2/21第52頁算法復雜性（續(xù)）2025/2/21第53頁算法復雜性（續(xù)）2025/2/21第54頁算法復雜性（續(xù)）2025/2/21第55頁算法復雜性-普通代數(shù)運算2025/2/21第56頁算法復雜性-模運算2025/2/21第57頁算法復雜性-有限域2025/2/21第58頁算法復雜性（續(xù)）2025/2/21第59頁算法復雜性（續(xù)）2025/2/21第60頁算法復雜性（續(xù)）2025/2/21第61頁算法復雜性（續(xù)）2025/2/21第62頁算法復雜性（續(xù)）2025/2/21第63頁算法復雜性（續(xù)）2025/2/21第64頁算法復雜性（續(xù)）2025/2/21第65頁算法復雜性（續(xù)）2025/2/21第66頁算法復雜性（續(xù)）假如將模運算視為基本運算單位（即一次模運算花費一個時間單位），則算法時間復雜度為2max(|a|,|b|)。

2025/2/21第67頁算法復雜性（續(xù)）2025/2/21第68頁算法復雜性（續(xù)）2025/2/21第69頁計算復雜性在信息安全中應用

在信息安全中，極難界定一個密碼體制是否是安全。在經(jīng)典密碼學中，安全性判定是基于信息論。信息論關注是密文當中到底包含多少關于明文信息。密文中關于明文信息量越大，密碼體制就越不安全。而只有當密文中不包含關于明文信息時，密碼體制才是絕對安全。香農證實過這種完美安全性只有當密鑰跟明文長度相等時，才能到達。這種安全性限制下密碼體制，其應用是非常困難。2025/2/21第70頁計算復雜性在信息安全中應用（續(xù)）

在當代密碼學當中，對安全性判定是基于計算復雜性。密文中是否包含明文信息，這個問題對安全性來說并不主要。關鍵是有沒有有效方法將密文中關于明文信息提取出來。換句話說，基于計算復雜性密碼學所關心不是密碼分析者是否有可能破譯算法（實際上，除了一次一密外，全部密碼體制都是有可能被破譯），而是關心密碼分析者是否含有對應資源和時間來破譯算法。2025/2/21第71頁計算復雜性在信息安全中應用（續(xù)）比如:假如一個密碼算法破譯只是一個P類問題，這個算法當然會被認為是不安全。一個需要宇宙年紀那么長時間才能破譯算法，當然有理由認為是安全。2025/2/21第72頁計算復雜性在信息安全中應用（續(xù)）基于復雜性理論當代密碼學將NP≠P作為一個必要條件，加密算法中，擁有正確加密/解密密鑰用戶進行加密/解密是易處理問題，而對于密碼攻擊者或分析者，從密文中提取明文或不用正確密鑰結構正當密文應該是一個難解問題。而很多加密算法是基于NP完全問題，即這類型算法中，分析和破譯是一個NP完全問題。我們稱之為NP≠P猜測。2025/2/21第73頁計算復雜性在信息安全中應用（續(xù)）假如NP＝P，則分析和破譯加密算法是一個多項式時間問題，即易處理問題。那么這些加密算法將失去其安全性。所以，假如這個猜測不正確，現(xiàn)在密碼學將失去其一個至關主要理論基礎。2025/2/21第74頁計算復雜性在信息安全中應用（續(xù)）另首先，即使NP≠P猜測成立，基于NP完全問題難解性密碼算法也不一定是安全。比如：基于NP完全著名背包問題破解就是一個反例。這是因為即使一個問題只有能夠忽略少數(shù)