數(shù)學(xué)理論復(fù)雜性省公開(kāi)課一等獎(jiǎng)全國(guó)示范課微課金獎(jiǎng)?wù)n件

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

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

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

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

相關(guān)算法幾點(diǎn)注釋：算法總有輸入和輸出算法輸入大小普通用輸入變量長(zhǎng)度（單位為位）來(lái)表示普通來(lái)說(shuō)，算法用某種編程語(yǔ)言來(lái)實(shí)現(xiàn)計(jì)算機(jī)程序普通來(lái)說(shuō)，我們僅僅關(guān)注處理問(wèn)題最有效算法2025/2/21第7頁(yè)問(wèn)題與算法問(wèn)題：怎樣求解兩個(gè)整數(shù)a和b最大條約數(shù)？參數(shù)：a和b問(wèn)題實(shí)例：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頁(yè)算法復(fù)雜性

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

好處：使算法復(fù)雜性度量與處理器運(yùn)行速度和指令運(yùn)行時(shí)間無(wú)關(guān)；明確地揭示了輸入數(shù)據(jù)長(zhǎng)度對(duì)算法復(fù)雜性影響。

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

2025/2/21第12頁(yè)算法復(fù)雜性算法分類及其運(yùn)行時(shí)間

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

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

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

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

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

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

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

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