區塊鏈技術背後的理論基石—組合數學
公眾號回復「1」，拉你進區塊鏈技術討論微信群
作者：於中陽
來源：區塊鏈兄弟
本文約5000字+，閱讀（觀看）需要30分鐘
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。
區塊鏈當中一個重要分支就是密碼學。而密碼學當中涉及到相當的數學知識，比如：數論、初等數學、代數學、組合數學以及概率論等。若沒有一點數學基礎的話，密碼學的研究將是進行不通的。密碼學和數學的關係可謂深之又深，甚至可以說信息安全的很大一部分基石就是數學（密碼學是信息安全中的一部分）。學習和掌握一些數學知識是必要的，在此我主要分享一些有關於密碼學的數學知識。
組合數學（Combinatorial mathematics），又稱為離散數學。
現代數學可以分為兩大類：一類是研究連續對象的，如方程和分析學等等；另一類就是研究離散對象的數學，即離散數學（組合數學）。
有人稱廣義的組合數學就是離散數學，也有人認為離散數學是狹義的組合數學和圖論、代數結構、數理邏輯等的總稱。
註：廣義的組合數學就是離散數學；狹義的組合數學是離散數學除圖論、代數結構、數理邏輯等的部分。
以上只是不同學者在叫法上的區別（在此不是我們關注的重點）。隨著計算機科學的日益發展，組合數學的重要性越發突出，這很好理解，因為計算機科學的核心內容就是使用演算法處理離散的數據（010101）。
組合數學不僅在基礎數學的研究中佔有重要地位，其在別的的學科中也有重要的應用，如計算機科學、編碼和密碼學、物理等學科中均有重要應用。
可以不誇張的說，組合數學的發展奠定了本世紀的計算機革命的基礎。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程序，而程序就是演算法，在絕大多數情況下，計算機的演算法是針對離散的對象，而不是在做數值計算。確切地說，組合數學是計算機出現以後迅速發展起來的一門數學分支，主要研究離散對象的存在、計數以及構造等方面問題。由於計算機軟體的促進和需求，組合數學已成為一門既廣博又深奧的學科，其發展奠定了本世紀的計算機革命的基礎，並且改變了傳統數學中分析和代數占統治地位的局面。正是因為有了組合演算法才使人感到，計算機好像是有思維的。
體現在大學計算機及信息安全相關的課程設置中，離散數學是專業基礎課，不但為後續課程提供必須的理論基礎，而且可以培養學生的抽象思維能力和解決問題的能力。離散數學的教學內容與計算機硬體和軟體都有著密切的關係，具有鮮明的基礎特點，不僅是密碼學、數據結構、資料庫原理、數字邏輯、編譯原理、人工智慧、信息安全等課程的重要課程，同時以計算機導論和程序設計基礎作為離散數學的先導課程。
另外需要強調的是，密碼學實際是一個交叉學科，其和數學、計算機科學和資訊理論的聯繫最為緊密。
組合數學中的代數系統理論包括代數系統的基本概念、半群、與獨異帶你、群、環與域、格與布爾代數。代數系統與密碼學聯繫非常緊密，其為密碼學提供了非常重要的數學基礎，是其不可分割的一部分。
組合數學的應用—密碼學
組合數學是密碼學與計算機科學應用必不可少的理論和工具，其的應用是非常廣泛的。例如其數理邏輯在數學模型、計算機語義、人工智慧等方面的應用。集合論在資料庫技術中的應用。代數系統在信息安全中的密碼學方面的應用，圖論在信息檢索、網線布線、指令系統優化等方面的應用。
現對其中代數系統理論在密碼學中的應用，進行舉例說明。
凱撒密碼
在密碼學中，凱撒密碼是一種最簡單且最廣為熟知的一種加密技術，其是一種簡單的基於替換原理的加密技術。凱撒密碼將明文中的所有字母都在字母表上進行向後（或者向前）的偏移移動，當然這是有一個固定數目的，而這個固定數目是根據個人的選擇進行的。由此偏移，明文被替換稱密文。而上述的固定數目的偏移量，即是凱撒密碼中的加解密密鑰 K。比如，偏移量為3，字母A將被字母D替換，而其中的 K 為3，即密鑰是3。其它的字母加密以此類推即可。解密的時候倒推回去，即可。
在代數系統理論中，群是一種典型的代數系統，其具有封閉性、可結合性、含有單位元以及每個元素都具有逆元等性質。所以，可以說凱撒密碼從本質上說就是一個特殊的群，其是建立在26個字母之上，字母與密鑰進行運算的剩餘模群。通過對群理論的學習可以更助於理解凱撒密碼的本質。
公鑰密碼學
再比如公鑰密碼學中，費馬小定理和歐拉定理提供了數學上的安全性保障。通過對於費馬小定理的原理和正確性的理解可以更好的理解演算法的安全性，在實際應用中更好的應用。
橢圓曲線密碼
還有密碼學中的橢圓曲線密碼，其是基於橢圓曲線的一種公鑰密碼演算法。其密碼安全性是基於橢圓曲線離散對數的困難性之上的，是一個有限域上橢圓曲線的阿貝爾群，毫無疑問，代數系統理論中群和域的學習對於理解橢圓曲線密碼是有幫助的。
另外一些應用，棋盤密碼、希爾密碼、Walsh譜。
接下來，我們談一下離散數學與其它學科的關係。
1）離散數學與數據結構的關係
離散數學與數據結構的關係非常緊密，數據結構課程描述的的對象有四種，分別是線形結構、集合、樹形結構和圖結構，這些對象都是離散數學研究的內容。線形結構中的線形表、棧、隊列等都是根據數據元素之間關係的不同而建立的對象，離散數學中的關係就是研究有關元素之間的不同關係的內容；數據結構中的集合對象以及集合的各種運算都是離散數學中集合論研究的內容；離散數學中的樹和圖論的內容為數據結構中的樹形結構對象和圖結構對象的研究提供了很好的知識基礎。
2）離散數學與資料庫原理的關係
資料庫原理研究中的資料庫類型有一種是關係資料庫。關係資料庫中的關係演算和關係模型需要用到離散數學中的謂詞邏輯的知識；關係資料庫的邏輯結構是由行和列構成的二維表，表之間的連接操作需要用到離散數學中的笛卡兒積的知識，表數據的查詢、插入、刪除和修改等操作都需要用到離散數學中的關係代數理論和數理邏輯中的知識。
3）離散數學與數字邏輯的關係
數字邏輯為計算機硬體中的電路設計提供了重要理論，而離散數學中的數理邏輯部分為數字邏輯提供了重要的數學基礎。在離散數學中命題邏輯中的聯結詞運算可以解決電路設計中的由高低電平表示的各信號之間的運算以及二進位數的位運算等問題。
4）離散數學與編譯原理的關係
編譯原理和技術是軟體工程技術人員很重要的基礎知識，編譯程序是非常複雜的系統程序。其包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優化、目標代碼生成、依賴機器的代碼優化等7個階段。離散數學中的計算模型中的語言和文法、有限狀態機、語言的識別和圖靈機等知識點為編譯程序中的詞法分析和語法分析提供了理論基礎。
5）離散數學與人工智慧的關係
離散數學中數學推理和布爾代數章節中的知識為早期的人工智慧研究領域打下了良好的數學基礎。謂詞邏輯演算為人工智慧學科提供了一種重要的知識表示方法和推理方法。此外，模糊邏輯的概念也應用於人工智慧。
6）離散數學與信息安全、密碼學的關係
離散數學和信息安全與密碼學的應用也關係密切，離散數學中的代數系統和初等數論為密碼學提供了重要的數學基礎，例如凱撒密碼的本質就是使用了代數系統中的群的知識，初等數論中的歐拉定理和費馬小定理為著名的RSA公鑰密碼體系提供了最直接的數學基礎。
離散數學的應用
1）數理邏輯的應用
數理邏輯是用數學方法研究思維規律的一門學科，包括命題邏輯、謂詞邏輯和推理理論等知識點。命題邏輯中的聯結詞廣泛應用在大量信息的檢索、邏輯運算和位運算中。
比如，目前大部分網頁檢索引擎都支持布爾檢索，使用NOT、AND、OR等聯結詞進行檢索有助於快速找到特定主題的網頁；信息在計算機內都表示為0或1構成的位串，通過對位串的運算可以對信息進行處理，計算機字位的運算與邏輯中的聯結詞的運算規則是一致的，掌握了聯結詞的運算為計算機信息的處理提供了很好的知識基礎。
在計算機硬體設計中，使用了聯結詞完備集中的與非和或非，使用與非門和或非門設計邏輯線路，替代了之前的非門、與門和或門的組合，優化了邏輯線路。
謂詞邏輯可以表示關係模型中的關係操作。
推理理論可以應用到計算機語義的理解中，在推理理論中驗證某理論的邏輯正確性時首先需要將其形式化，這樣在邏輯推理時就直接使用邏輯規則進行推理而不需要理會其具體含義了，在計算機語義中，也可以將其形式化，藉助推理理論的方法進行計算機語義的理解。
2）集合論的應用
集合是由各種不同元素構成的，並用統一的方法來處理的對象，集合論包括集合代數、關係和函數等知識點。集合代數中的集合的性質和集合的運算主要是為其他學科提供數學基礎，現實世界中的數字、符號、圖像、語音、視頻等各種信息都可以作為數據存放到計算機進行處理，這些數據就構成集合。
關係是一種特殊的集合，它反映了研究對象之間的聯繫與性質，例如關係資料庫模型中，每個資料庫都是一個關係，在計算機程序中輸入和輸出就構成一個二元關係。
等價關係和偏序關係廣泛的存在於實際應用中，例如利用偏序的知識可以解決調度中的最優調度問題；在軟體工程的軟體測試方法中有一種等價類劃分的方法，即將所有待測試的數據構成的集合劃分為符合軟體需求規格和設計規定的有效等價類和不符合的無效等價類，因為每個等價類中只需要取一個數據代表其所在等價類的其他數據進行測試，所以大大提高了軟體測試的效率。函數的應用比較廣泛，例如在密碼學中的應用，公鑰系統中的原理是基於單向陷門函數，單向陷門函數滿足3個條件：
（1）對於屬於定義域的任意一個 x，可以很容易算出 F(x)=y
（2）對於幾乎所有屬於值域的任意一個 y ，則在計算上除非獲得陷門，否則不可能求出 x ，使得 x=F-1(y)
（3）若有一額外數據 z（稱為陷門），則可以很容易的求出 x=F-1(z) 。
單向陷門函數與單向函數的差異在於可逆與不可逆。若單向陷門函數存在，則任何單向陷門函數均可用來設計公開密鑰密碼系統。同時，若單向函數滿足交換性，則單向函數也可能用來設計公開密鑰密碼系統。
3）代數系統的應用
代數系統研究的是集合、該集合中元素的運算和一些特殊元素，其中群是一種特殊的代數系統，具有可結合、有單位元、每個元素都有逆元等性質。凱撒密碼系統的原理是將字母表的字母右移 n 個位置，n 即是密鑰（key）。
然後對字母表長 L 作模運算，加密形式為：c=(m+n)modl，解密形式為：m=(c-n)modl。其實凱撒密碼就是建立在26個字母之上，字母與密鑰 key 運算的剩餘模群。
橢圓曲線加密演算法是利用橢圓曲線離散對數問題，橢圓曲線離散對數問題定義如下：給定素數 p 和橢圓曲線 E，對 Q=kP ，在已知 P，Q 的情況下求出小於 p 的正整數 k ，由於已知 k 和 P 計算 Q 比較容易，而由 Q 和 P 計算 k 則比較困難，至今沒有有效的方法來解決這個問題，這正是該加密演算法的原理所在。
4）圖論的應用
圖論在計算機領域的應用廣泛，例如利用哈密頓圖求最短路徑問題和旅行商最優問題，利用哈夫曼演算法對指令系統優化以及提高通信效率等問題。在計算機體系結構中，指令系統的優化非常重要，因為可以提高整個計算機系統的性能，指令系統的優化方法很多，其中一種就是對指令的格式進行優化，是指用最短的位數來表示指令的操作碼和地址碼，使程序中的指令的平均字長最短，可以使用哈夫曼演算法對指令的格式進行優化，利用哈夫曼演算法可以構造出最優二叉樹，而二叉樹的權是最小的，即可以實現指令的平均字長最短。同樣的原理利用哈夫曼演算法構造最優二叉樹可以解決通信中傳輸二進位數最優效率的問題。
組合數學（離散數學）在密碼學及計算機科學領域的作用非常重要，密碼學及計算機科學普遍採用離散數學中的一些概念、知識點和研究方法。離散數學不但為密碼學和計算機科學提供必要的理論基礎，還在計算機學科中有著廣泛的應用（上述只是部分而非全部），隨著研究的深入相信會有更多的應用出現。
通過學習組合數學（離散數學）的思想和方法將顯著提高邏輯思維能力和創造性思維能力。作為嚴謹的科學技術工作者，我們有必要學習數學知識，因為其於密碼學和計算機科學的重要性真的是不言而喻的。
文章發布只為分享區塊鏈技術內容，版權歸原作者所有，觀點僅代表作者本人，絕不代表區塊鏈兄弟贊同其觀點或證實其描述。
TAG:區塊鏈兄弟 |