[密码学] 复杂性理论基础
文章目錄
- 復(fù)雜性理論基本概念
- 問題(problem)
- 算法
- 算法復(fù)雜性
- 算法分類
- 問題復(fù)雜性
- 圖靈機(jī)
- 圖靈機(jī)分類
- 問題復(fù)雜性
- P問題
- NP問題
- NP完全問題(NPC問題)
- 總結(jié)
- 密碼學(xué)復(fù)雜性理論假設(shè)
- 單向函數(shù)(OWF)
- 偽隨機(jī)生成器(PRG)
- 真隨機(jī)數(shù)生成
- 偽隨機(jī)數(shù)生成器(PRG)
- 構(gòu)造偽隨機(jī)生成器
- 測試偽隨機(jī)性的方法
- 單向函數(shù)與偽隨機(jī)生成器的關(guān)系
- 總結(jié)
復(fù)雜性理論基本概念
問題(problem)
??①需要回答的一般性提問
??②含有若干未定參數(shù)：
???如果給問題的所有參數(shù)指定了具體值，就得到該問題的一個實例。
算法
?①求解某一個問題的一系列具體步驟。
??例如：高斯消元法、歐幾里得算法
?②如果一個算法可以解決一個問題的任何一個實例，則這個算法可以解答這個問題。
?③如果針對一個問題，至少存在一個算法可解答這個問題，則這個問題是可解的(resolvable)；否則，是不可解的(unresolvable)。例如：停機(jī)問題、希爾伯特第十問題。
算法復(fù)雜性
?①一般由算法所需求的**最大時間(T)和存儲空間(S)**度量。
?②同一問題，不同規(guī)模，時間與空間上存在差異。
??時間與空間表示成實例的規(guī)模n的函數(shù)
?③符號"大O"(Big O)
?④用數(shù)量級度量復(fù)雜度的優(yōu)點：
??刻畫時間與空間的需求受輸入長度變化的影響；
??與所用處理系統(tǒng)無關(guān)
算法分類
?①多項式時間算法：O(n^t)：其中t為常數(shù)，n為輸入規(guī)模。
?②指數(shù)時間算法：O(t^h(n))：其中h(n)為多項式。
?③當(dāng)h(n)大于常數(shù)而低于線性函數(shù)時，稱為超多項式時間算法。
?④多項式時間算法可認(rèn)為是有效的。
問題復(fù)雜性
圖靈機(jī)
?①一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號。
?②一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當(dāng)前所指的格子上的符號，并能改變當(dāng)前格子上的符號。
?③一套控制規(guī)則TABLE。它根據(jù)當(dāng)前機(jī)器所處的狀態(tài)以及當(dāng)前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態(tài)寄存器的值，令機(jī)器進(jìn)入一個新的狀態(tài)。
?④一個狀態(tài)寄存器。它用來保存圖靈機(jī)當(dāng)前所處的狀態(tài)。圖靈機(jī)的所有可能狀態(tài)的數(shù)目是有限的，并且有一個特殊的狀態(tài)，稱為停機(jī)狀態(tài)。
圖靈機(jī)分類
?①確定型圖靈機(jī)(DTM)：每一步操作結(jié)果的唯一確定的；
?②非確定型圖靈機(jī)(NTM)：每一步的操作及結(jié)果不是唯一的，可能是多種選擇；
問題復(fù)雜性
?一個問題的復(fù)雜性由在圖靈機(jī)上解決此問題的最難的實例所需的最小的時間和空間決定。
P問題
?確定型圖靈機(jī)上可用多項式時間可解的問題，稱為易處理的。易處理問題的全體稱為確定性多項式時間可解類。
?補(bǔ)充：在確定型圖靈機(jī)上不能用多項式時間系統(tǒng)地解出的問題，稱為難處理的。
NP問題
?在非確定型圖靈機(jī)上可用多項式時間可解的問題，稱為非確定性多項式時間可解問題。
?①NP問題的全體稱為非確定性多項式時間可解類，記為NP。
?②求解過程：猜測、驗證
?③所謂可解指的是，若機(jī)器猜測一個解，可在多項式時間內(nèi)驗證其正確性。
例如：背包問題(子集合問題)、可滿足問題
NP完全問題(NPC問題)
?一個問題是NP完全的，如果NP中的任何一個問題都是可以在多項式時間內(nèi)轉(zhuǎn)化為該問題。
?①NP完全問題是NP中**"最難"的問題**
總結(jié)
P類問題：能在多項式時間內(nèi)可解的問題；
NP類問題：在多項式時間內(nèi)“可驗證”的問題。也就是說，不能判定這個問題到底有沒有解，而是猜出一個解來在多項式時間內(nèi)證明這個解是否正確。
NPC問題：存在這樣一個NP問題，所有的NP問題都可以約化成它。換句話說，只要解決了這個問題，那么所有的NP問題都解決了。
P問題屬于NP問題，但不等于
密碼學(xué)復(fù)雜性理論假設(shè)
單向函數(shù)(OWF)
偽隨機(jī)生成器(PRG)
隨機(jī)性：均勻、獨立、不可預(yù)測
真隨機(jī)數(shù)生成
?一般通過測量不可預(yù)測的物理過程實現(xiàn)：電離輻射的脈沖檢測
?缺點：效率低、成本高
偽隨機(jī)數(shù)生成器(PRG)
?確定性算法，輸入固定長度的真隨機(jī)數(shù)(種子)，輸出任意長度的字符串，且輸出字符串的分布與均勻分布計算上不可區(qū)分。但并不能增加熵。
構(gòu)造偽隨機(jī)生成器
利用流密碼、分組密碼、Hash函數(shù)、公鑰密碼等
測試偽隨機(jī)性的方法
?①統(tǒng)計測試(必要不充分條件)
??16項檢測：頻率測試、序列測試、游程測試、自相關(guān)測試等
?②可證明安全的偽隨機(jī)生成器：基于數(shù)學(xué)困難問題的構(gòu)造
??Blun-Micali偽隨機(jī)數(shù)生成器：
??安全性基于破譯RSA體制的困難性：
??二次剩余生成器：
單向函數(shù)與偽隨機(jī)生成器的關(guān)系
?①利用單向函數(shù)可構(gòu)造偽隨機(jī)生成器
?②利用**偽隨機(jī)函數(shù)(PRF)**構(gòu)造安全MAC
總結(jié)
總結(jié)
以上是生活随笔為你收集整理的[密码学] 复杂性理论基础的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [密码学] 流密码
- 下一篇： [Windows子系统] Ubuntu1