区块链技术背后的理论基石—组合数学（离散数学）初谈

“密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大一部分基石就是数学。学习和掌握一些数学知识是必要的，在此我主要分享一些有关于密码学的数学知识。”

区块链当中一个重要分支就是密码学。而密码学当中涉及到相当的数学知识，比如：数论、初等数学、代数学、组合数学以及概率论等。若没有一点数学基础的话，密码学的研究将是进行不通的。密码学和数学的关系可谓深之又深，甚至可以说信息安全的很大一部分基石就是数学（密码学是信息安全中的一部分）。学习和掌握一些数学知识是必要的，在此我主要分享一些有关于密码学的数学知识。

现代数学可以分为两大类：一类是研究连续对象的，如方程和分析学等等；另一类就是研究离散对象的数学，即离散数学（组合数学）。

有人称广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。

注：广义的组合数学就是离散数学；狭义的组合数学是离散数学除图论、代数结构、数理逻辑等的部分。

以上只是不同学者在叫法上的区别（在此不是我们关注的重点）。随着计算机科学的日益发展，组合数学的重要性越发突出，这很好理解，因为计算机科学的核心内容就是使用算法处理离散的数据（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）图论的应用

图论在计算机领域的应用广泛，例如利用哈密顿图求最短路径问题和旅行商最优问题，利用哈夫曼算法对指令系统优化以及提高通信效率等问题。在计算机体系结构中，指令系统的优化非常重要，因为可以提高整个计算机系统的性能，指令系统的优化方法很多，其中一种就是对指令的格式进行优化，是指用最短的位数来表示指令的操作码和地址码，使程序中的指令的平均字长最短，可以使用哈夫曼算法对指令的格式进行优化，利用哈夫曼算法可以构造出最优二叉树，而二叉树的权是最小的，即可以实现指令的平均字长最短。同样的原理利用哈夫曼算法构造最优二叉树可以解决通信中传输二进制数最优效率的问题。

组合数学（离散数学）在密码学及计算机科学领域的作用非常重要，密码学及计算机科学普遍采用离散数学中的一些概念、知识点和研究方法。离散数学不但为密码学和计算机科学提供必要的理论基础，还在计算机学科中有着广泛的应用（上述只是部分而非全部），随着研究的深入相信会有更多的应用出现。

通过学习组合数学（离散数学）的思想和方法将显著提高逻辑思维能力和创造性思维能力。作为严谨的科学技术工作者，我们有必要学习数学知识，因为其于密码学和计算机科学的重要性真的是不言而喻的。

原文作者：Mercina-zy

文章来源：

https://mp.weixin.qq.com/s?__biz=MzU5NTE2ODM2MQ==&mid=2247483833&idx=1&sn=e074d4127c2d63345a41af3c2f110580&chksm=fe775cbfc900d5a92c1132036b92aacec5762d4db2f6c8c30f21382810d941da93b26a3d5154&scene=21#wechat_redirect