信息安全數(shù)學(xué)2017.2北京工業(yè)大學(xué)信息學(xué)部課程簡介為了解決信息通信系統(tǒng)信息的非授權(quán)訪問，密碼技術(shù)被廣泛的用于通信系統(tǒng)的各個層面?，F(xiàn)代密碼技術(shù)是以數(shù)學(xué)為基礎(chǔ)發(fā)展起來的，其中數(shù)論和代數(shù)結(jié)構(gòu)是解決現(xiàn)代密碼關(guān)鍵技術(shù)的理論基礎(chǔ)。而現(xiàn)有各學(xué)科教學(xué)體制中缺乏專門介紹密碼以及信息安全所涉及的數(shù)學(xué)知識的課程。因此，為了適應(yīng)信息技術(shù)發(fā)展的需求，將信息安全相關(guān)的數(shù)學(xué)作為一門獨立的基礎(chǔ)課程，為解決信息安全理論與實踐問題提供數(shù)學(xué)基礎(chǔ)。課程地位本課程為信息安全專業(yè)以及與通信相關(guān)的各專業(yè)的本科生奠定一定的數(shù)學(xué)基礎(chǔ)，提高他們認識、分析和解決信息安全問題的能力。本課程是學(xué)科基礎(chǔ)課，系統(tǒng)的介紹與信息安全理論與技術(shù)相關(guān)的數(shù)學(xué)知識以及一些常用的計算方法，并通過一些應(yīng)用實例使學(xué)生了解數(shù)學(xué)知識在信息安全中的應(yīng)用，同時通過這些實例幫助學(xué)生更好的理解抽象的數(shù)學(xué)知識，為進一步應(yīng)用數(shù)學(xué)知識解決信息安全領(lǐng)域的理論與實踐問題奠定扎實的數(shù)學(xué)基礎(chǔ)。緒論信息系統(tǒng)安全包含以下四個方面：設(shè)安備全：設(shè)備的穩(wěn)定性、可靠性、可用性數(shù)據(jù)安全：數(shù)據(jù)的秘密性、完整性、可用性內(nèi)容安全：信息內(nèi)容在政治上是健康的，符合國家法律法規(guī)、符合中華民族優(yōu)良的道德規(guī)范行為安全：行為的秘密性、行為的完整性、行為的可控性（以確保信息安全）信息安全的內(nèi)涵信息系統(tǒng)的硬件系統(tǒng)安全和操作系統(tǒng)安全是信息系統(tǒng)安全的基礎(chǔ)，密碼和網(wǎng)絡(luò)安全等技術(shù)是信息系統(tǒng)安全的關(guān)鍵技術(shù)。為了表述簡單直接將信息系統(tǒng)安全簡稱為信息安全。信息安全學(xué)科是研究信息獲取、信息存儲、信息傳輸和信息處理中的信息安全保障問題的一門新興學(xué)科。信息安全學(xué)科的性質(zhì)信息安全學(xué)科是綜合計算機、通信、電子、數(shù)學(xué)、物理、生物、管理、法律和教育等學(xué)科，并發(fā)展演繹而形成的交叉學(xué)科。信息安全學(xué)科已經(jīng)獨立，并形成了自己的理論、技術(shù)和應(yīng)用，正服務(wù)于信息社會。信息安全的主要研究方向密碼學(xué)網(wǎng)絡(luò)安全信息系統(tǒng)安全信息內(nèi)容安全信息對抗信息安全的理論基礎(chǔ)數(shù)學(xué)密碼學(xué)——代數(shù)、數(shù)論、概率統(tǒng)計。安全協(xié)議——邏輯學(xué)信息對抗——博弈論信息論、控制論和系統(tǒng)論計算理論：可計算理論和計算復(fù)雜性理論主要內(nèi)容及時間安排計算復(fù)雜性（6課時）因式分解困難問題及其所涉及的數(shù)論基礎(chǔ)（28課時）離散對數(shù)問題及其現(xiàn)代數(shù)學(xué)基礎(chǔ)（10課時）邏輯學(xué)基礎(chǔ)（6課時）量子力學(xué)基礎(chǔ)（2課時）總復(fù)習(xí)（2課時）閉卷考試：平時20%+試卷80%答疑：每周三下午2-4點，信西404A。第一講：計算復(fù)雜性計算復(fù)雜性的概念計算量的表示算法與計算量計算復(fù)雜性影響計算復(fù)雜性的因素計算復(fù)雜性的概念（1）

計算復(fù)雜性理論（Computationalcomplexitytheory）是計算理論的一部分，研究計算問題時所需的資源，比如時間和空間，以及如何盡可能的節(jié)省這些資源。

計算復(fù)雜性理論所研究的資源中最常見的是時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少內(nèi)存）。其他資源亦可考慮，例如在并行計算中，需要多少并行處理器才能解決問題。計算復(fù)雜性的概念（2）時間復(fù)雜度是指在計算機科學(xué)與工程領(lǐng)域完成一個算法所需要的時間，是衡量一個算法優(yōu)劣的重要參數(shù)。時間復(fù)雜度越小，說明該算法效率越高，則該算法越有價值?？臻g復(fù)雜度是指計算機科學(xué)領(lǐng)域完成一個算法所需要占用的存儲空間，一般是輸入?yún)?shù)的函數(shù)。它是算法優(yōu)劣的重要度量指標，一般來說，空間復(fù)雜度越小，算法越好。我們假設(shè)有一個圖靈機來解決某一類語言的某一問題，設(shè)有X個字（word）屬于這個問題，把X放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數(shù)總和稱為空間。計算復(fù)雜性的概念（3）復(fù)雜度理論和可計算性理論不同，可計算性理論的重心在于問題能否解決，不管需要多少資源。而復(fù)雜性理論作為計算理論的分支，某種程度上被認為和算法理論是一種“矛”與“盾”的關(guān)系，即算法理論專注于設(shè)計有效的算法，而復(fù)雜性理論專注于理解為什么對于某類問題，不存在有效的算法。歷史回顧在20世紀50年代，Trahtenbrot和Rabin的論文被認為是該領(lǐng)域最早的文獻。而一般說來，被公認為奠定了計算復(fù)雜性領(lǐng)域基礎(chǔ)的是Hartmanis和Stearns的1960年代的論文Onthecomputationalcomplexityofalgorithms。在這篇論文中，作者引入了時間復(fù)雜性類TIME(f(n))的概念，并利用對角線法證明了時間層級定理（TimeHierarchyTheorem）。在此之后，許多研究者對復(fù)雜性理論作出了貢獻。期間重要的發(fā)現(xiàn)包括：對隨機算法的去隨機化（derandomization）的研究，對近似算法的不可近似性（hardnessofapproximation）的研究，以及交互式證明系統(tǒng)（Interactiveproofsystem）理論和零知識證明（Zero-knowledgeproof）等。特別的復(fù)雜性理論對近代密碼學(xué)的影響非常顯著，而最近，復(fù)雜性理論的研究者又進入了博弈論領(lǐng)域，并創(chuàng)立了“算法博弈論”（algorithmicgametheory）這一分支。計算模型和計算資源計算復(fù)雜性理論的研究對象是算法在執(zhí)行時所需的計算資源，而為了討論這一點，我們必須假設(shè)算法是在某個計算模型上運行的。常討論的計算模型包括圖靈機（Turingmachine）和電路（circuit），它們分別是一致性（uniform）和非一致性（non-uniform）計算模型的代表。而計算資源與計算模型是相關(guān)的，如對圖靈機我們一般討論的是時間、空間和隨機源，而對電路我們一般討論電路的大小。由邱奇-圖靈論題（Church-Turingthesis），所有的一致的計算模型與圖靈機在多項式時間意義下是等價的。而由于我們一般將多項式時間作為有效算法的標志，該論題使得我們可以僅僅關(guān)注圖靈機而忽略其它的計算模型。例1：可滿足性（Satisfiability）問題布爾變量集合布爾變量和稱為文字子句集合子句是一些文字的析?。ㄟ壿嫽颍┱嬷蒂x值給定U和C，是否存在滿足C的真值賦值？可滿足：C中所有的子句在t下為真計算復(fù)雜度：例2：貨郎擔(dān)問題

（Travelingsalesmanproblem)給定n個城市，任意兩個城市間有路相連，一個貨郎從一個城市出發(fā)，不重復(fù)的遍歷所有的城市并回到起點，求一條路程最短的路徑。加權(quán)完全圖，，，求Hamilton圈

，使得計算復(fù)雜度：用有限時間可以求解，但計算時間太長，成本太高優(yōu)化技術(shù)與方法計算量(1)＋,－,×,÷比較：≠，≤，≥，＜，＞5種基本演算都是用1step

可以實現(xiàn).實際上,×比＋多占用時間.「四舍五入」不算基本演算.

計算量(2)｛a1,a2,...,an｝：n個整數(shù)Q1.

求和（1）：

a1+a2+???+an.

n-1steps→O(n)算法.Q2.

求和（2）：

(1)2×a1+???+2×an,2n-1steps→O(n)算法.(2)2×(a1+???+an)

,nsteps→O(n)算法.計算量(3)Q3.

計算：a1b1+???+anbn.

2n-1steps.Q4.2個ｎ×ｎ階矩陣相乘.

n2(2n-1)steps（n2(n+n-1)）.計算量(4)Q5.｛a1,a2,...,an｝：n個整數(shù)

求其和為最大的部分集合.

所有的部分集合的和進行比較2n(n-1)+(2n-1)→O(n2n)算法.計算量的膨脹(1)10行×10列棋盤上米粒的數(shù)量（第1格內(nèi)放1粒米，以后每格順次增加1倍……)格序號米粒數(shù)重量(kg)112.0×10-592565.1×10-3181310722.6×10027671088641.3×10336343597383686.9×10545175921860444163.5×1085490071992547409921.8×10116346116860184273879049.2×10137223611832414348226068484.7×10168112089258196146291747061762.4×10202.4×108億噸計算量的膨脹(2)100MIPS(megainstructionspersecond)1秒間100萬回的計算＝1step用10-6秒光速3.0×1010cm/秒(10-6秒

行進300m)n101001,00010,000n10-5秒10-4秒10-3秒0.01秒n210-4秒0.01秒1秒100秒n30.001秒

1秒16.6分277時間2n0.001秒1014世紀10284世紀n!0.036秒10141世紀102551世紀宇齡：

宇宙的年齢1.5×108世紀（１５０億年）計算機速度增加的效果（1）10秒間的計算量？100MIPS10倍100倍1000倍

n1071081091010n23千1萬

3萬

10萬n3215462

1千

2千2n2327

30

33

n!101112131000倍?1step用10-9秒?

10-9秒光可以行進30cm計算機速度增加的效果（2）計算速度1秒可以求解問題的規(guī)模

O(2n)O(n)O(n2)O(n5)O(n10)100100100100100101200141115107103100031615812610710000100025115811010000031623982001131000000100006312511000001171000000031623100031610000001201000000001000001585398平行（并列）計算的場合0.5cm見方小碎片，覆蓋地球表面需要2.0×1019個.與100MIPS的單個計算機相比，能加速多少？n1001,000.2n1014世紀→0.85秒10284世紀→10263世紀n!10141世紀→10120世紀102551世紀→102530世紀問題與算法每個問題都可能有多個算法存在．每個算法的計算量（速度）都不同。例：贗品金幣問題：問題：9個外觀完全一樣的金幣.，有一個是假的（重量輕）．提問：用天秤來鑒別真?zhèn)?，天秤需要使用幾次？贋品金幣問題算法使用2次天秤,就可以鑒別出假幣.789１23456左邊軽右邊軽平衡１23中有偽幣789中有偽幣456中有偽幣左邊軽１32右邊軽平衡１32456789計算量的表示法:上界值表示法O記號：(BigONotation)定義:O(f(n))讀作orderf(n),或階f(n)即：g(n)=O(f(n))表示對于任意定數(shù)c和m，以及對所有n＞m，有下式成立：g(n)＜cf(n)計算量的表示法——例n２+1000n→O(n２)logn+n3+1000n2→O(n3)判斷：n!→O(nn)？10n2→

O(n3)？logn→

O(n)？思考：O()?優(yōu)化問題的規(guī)模表示優(yōu)化問題大小的參數(shù)例如：旅行商問題：都市的個數(shù);背包問題：物品的個數(shù)注：參數(shù)的個數(shù)并不僅限于1個InputSize多項式時間算法與指數(shù)時間算法指數(shù)時間算法=用問題規(guī)模的指數(shù)函數(shù)來表示計算時間的算法非有效算法的代名詞多項式時間算法=能用問題規(guī)模的多項式函數(shù)來表示計算時間的算法高效率算法的代名詞多項式時間算法的計算時間問題規(guī)模計算時間1020304050100100010000100MIPS(millioninstructionspersecond)計算機的情形指數(shù)時間算法的計算時間100MIPS(millioninstructionspersecond)計算機的情形問題規(guī)模計算時間10203040501001宙齢=150億年指數(shù)災(zāi)難：計算量的指數(shù)增長指數(shù)災(zāi)難能否避免？SAT問題，貨郎擔(dān)問題，背包問題，圖著色問題，最長路徑問題，……是否對于每個問題都有好的算法？什么是好的算法？什么是算法？算法的定義為實現(xiàn)某個任務(wù)而構(gòu)成的簡單指令集有窮的計算良過程通過有限多次運算可以決定的過程正確直觀，非形式算法的定義希爾伯特第十問題（1900）設(shè)計一個算法來判斷多項式是否有整數(shù)根算法：通過有限多次運算可以決定的過程AlanTuring&AlonzoChurch（1936）圖靈機程序算法：圖靈機程序形式化的，精確的圖靈機（TuringMachine)帶子可讀可寫無限長的帶子讀寫頭可左移右移

有限狀態(tài)控制器1111110000000BBB1…………圖靈機（TuringMachine)TM運行由確定:當(dāng)前狀態(tài)為q，所讀字符為s

，讀寫頭不變，，，讀寫頭左移一格，s不變，，讀寫頭右移一格，s不變，無定義，則停機Church-Turing論題：凡是可計算的過程都可用圖靈機實現(xiàn)；旅行商問題的計算量（1）n個都市訪問的可能的巡回路線：n!的Stirling近似公式BigOh記法

的定數(shù)倍的大小可以忽略≈旅行商問題的計算量（2）根據(jù)Stirling公式以及O（）表示法O（nn）排序問題的計算量（1）：排序問題：S=｛a1,a2,...,an｝，n個整數(shù)列，按數(shù)值大小排列dataS輸入

需O(n)時間；可能的排列種類數(shù)n!種；算法中每一個比較,都增加2倍的情形數(shù)2分樹的高度（比較的次數(shù)）,

log2(n!)=O(nlog

n)x＞y?yesnon!種可能的排列排序問題計算量（2）總計算時間的復(fù)雜性：O(nlog

n)dataS輸入時間(或賦值時間)：O(n)

比較時間：O(nlog

n)上位取整計算量的確定例：背包問題的貪婪算法（greedyalgorithm）的計算量確定計算量的確定計算量的確定計算量的確定計算量的確定計算量的確定計算量的確定計算的復(fù)雜度時間復(fù)雜度：

計算量:計算各基本操作的實行回數(shù)（timecomplexity）空間復(fù)雜度各計算時點內(nèi)存中保持數(shù)據(jù)個數(shù)的最大值（spacecomplexity）兩者的總稱：計算的復(fù)雜度計算復(fù)雜度的影響因素探索空間1---解的近似度、滿意度例：0—10之間的整數(shù)解：1-9共9個可行解（一維）0—10之間的實數(shù)解：精確到小數(shù)點后6位共有107個可行解（一維）；107n個可行解（n維）探索空間2---解空間大小例：桌子上有6根火柴，要求構(gòu)建出4個三角形。計算復(fù)雜度的影響因素探索策略的選取計算復(fù)雜度的影響因素問題本身P問題NP問題（NP-hard，NP困難問題）NP完全問題

P類 （Polynomial) 判定問題：只有肯定和否定兩種答案優(yōu)化問題可以化作判定問題處理P類具有多項式時間算法的判定問題形成的計算復(fù)雜性類猜測TSP（Travelingsalesmanproblem)不屬于P（J.Edmonds1965）

Pclassproblem:能用多項式時間算法求解的問題的集合稱為P（polynomial）問題某一個問題屬于P問題的証明某一個問題不屬于P問題的証明如能夠找到一個多項式時間算法

（簡単）不存在？沒找到？（困難）優(yōu)化問題的分類（1）NP類(NondeterministicPolynomial)NP問題：在非確定型圖靈機上多項式時間可解的問題在確定型圖靈機上多項式時間可驗證的問題P類包含于NP類中NP類問題在確定圖靈機上指數(shù)時間可解非確定型圖靈機和確定型圖靈機的計算能力相當(dāng)優(yōu)化問題的分類（2）

NPclassproblem:尚未確信能否用多項式時間算法求解的問題的集合稱為NP（non-deterministicpolynomial）問題某一個問題不屬于NP問題的証明某一個問題屬于NP問題的証明如能夠找到一個多項式時間算法

（簡単）可以歸結(jié)為某一類既知的NP類問題（現(xiàn)階段7類））優(yōu)化問題的分類（3）（根據(jù)算法）

NP-completeproblem:集合NP中的問題=NP問題如果某個NP問題能夠求解，則因所有NP問題都可以經(jīng)過歸結(jié)，轉(zhuǎn)化為該問題，從而可以求解所有NP問題。這樣的NP問題=NP完全問題——集合NP中的最難的問題=

NP完全問題計算難度比較的標準難易是比較而言的多項式時間歸約（Karp歸約1972)定義問題A多項式時間內(nèi)轉(zhuǎn)化為問題B的特殊情況，則稱A可多項式歸約于B，記為轉(zhuǎn)化時間為多項式對于A的輸入I的回答與其對應(yīng)的B的輸入f(I)一致NP完全與NP-hardNP完全問題：NP-hard問題：NP完全問題第一個NP完全問題（Cook定理1971）可滿足性問題是NP完全問題六個NP完全問題（Karp1972)3SAT，3DM，VC，團，HC，劃分更多的NP完全問題1979年：300多個1998年：2000多個P、NP、NP完全的包容關(guān)系NPNP完全旅行商問題背包問題。。。P最短路問題線性規(guī)劃問題。。。NP=PNP完全大多數(shù)研究者認可的包容關(guān)系這種可能性也存在（現(xiàn)階段無法證明）懸賞$100萬求證NP完全問題第一個NP完全問題（Cook定理1971）可滿足性問題是NP完全問題六個NP完全問題（Karp1972)3SAT，3DM，VC，團，HC，劃分更多的NP完全問題1979年：300多個1998年：2000多個現(xiàn)在的估計如果，則指數(shù)災(zāi)難無法避免P=?NP（P-NP問題）P=NPPNPCNP如何處理NP完全問題

實際的問題不會消失油井勘探問題移動通訊中的頻率分配問題并行計算以硬件設(shè)備換取時間存在著很多種并行計算模型理想模型PRAM可多項式時間解NP完全問題實際中效果不好處理器數(shù)目是受限的現(xiàn)實的代價：通訊，同步，……分布式計算算法的研究隨機算法判定問題：以較大概率得到正確輸出輸出正確，但計算時間不定優(yōu)化問題：輸出解的性能不穩(wěn)定