算法思维在密码学教学中的应用

Agorithm Thinking Appication of Cryptography Teaching

Tian Youiang1 Wang Xuemei2

（1. Coege of Science， Guizhou University， Guiyang GuiZhou，550025， China； 2. Guiyang Vocationa and Technica Coege， Guiyang GuiZhou，550081， China）

密码学是信息安全类专业的重要专业基础课程，在很多学校，它也是数学、计算机、通信等相关专业的专业选修课程。密码学技术是信息安全的核心和关键，是数学在信息安全中的重要应用，特别是初等数论、抽象代数等抽象数学知识在保密通信领域的应用。密码学课程是理论性和应用性相结合的课程，充分体现了数学在具体应用领域的特殊作用和核心地位。密码学课程的教学主要围绕基本安全特性，如保密性、认证性、完整性、不可否认性、可用性等，论述各种密码原语，主要包括传统密码体制、序列密码、分组密码、公钥密码、签名与认证、密钥管理和密码协议、密码技术应用等密码算法的基本概念、发展历程、数学原理、算法设计思想和应用场景等。

算法可以说是计算机认识世界的基础和桥梁，是计算机和网络技术各个发展阶段不可或缺的最基本技术之一。算法可以描述为一序列的计算步骤，用它来将输入数据转换成输出结果。其方法主要涉及递推法、递归法、穷举法、贪心算法、分冶法、动态规划法、迭代法、分支界定法、回溯法等。这些方法和原理已经渗透到我们社会生活的方法面面。无论是我们在天上飞、还是在地上跑，或许是在办工作旁工作，无时无刻算法都在影响和规划着我们的一切。同时也给我们的生活和工作带来前所未有的深刻改变。

该文从算法思维的角度分析密码学课程教学。主要从形式化算法的概念探究分析密码学课程中的基本概念；应用程序设计中模块化设计思想，深入分析密码体制，特别是按照各个模块的功能作用，分析密码算法的设计思想和理念，组合分析密码学教学中密码协议的设计原理和方法。让学生进一步理解和掌握密码学课程的相关概念和原理。

1 密码学的数学基础渗透着算法思维

密码学的数学基础课程通常包括概率论、初等数论、抽象代数等。这些课程具有鲜明的算法特性，特别是初等数论和抽象代数更是如此。

在密码学教学课程中，需要使用很多抽象的数学概念，比如群、环、域、因式分解、同余、中国剩余定理、二次剩余、传统教学仍然停留在课堂讲解概念、定理分析证明、课后布置作业的等模式上。在学生听完课后，对其抽象概念只能囫囵吞枣，基本不甚理解其真正的应用背景和意义所在。学生仅能做到对抽象数学概念的死记硬背，在做题过程中生搬硬套，流于固定形式和套路，基本不能做到深入理解、灵活掌握和自如运用，给进一步学习密码学课程的深层次理解造成一定难度。可见，在教学过程中只是让学生通过做作业等常规方式来理解这些结论，必然不会起到较佳的效果。

因此，在密码学的数学基础的学习过程中，有必要结合这些知识的特点，用算法的思维方式，模块化的分析方法，给出初等数论、抽象代数中相关概念中的算法思想，通过算法程序化的思维，庖丁解牛的方式，按照其功能模块，深入解剖其内涵，同时从理论的角度剖析其应用外延，必将使学生更加深入地理解其概念和算法原理。从密码应用的高度提高抽象数学教学的趣味性。

2 应用形式化算法模式剖析密码学概念 密码学是在研究如何保密传送信息的过程中发展起来的，简单地说，密码学就是研究在敌对环境下如何实现保密的安全通信问题。它随着密码编码和密码分析这对“矛”和“盾”的长期永不停止的斗争中发展壮大起来的。随着先进科学技术的应用而成为一门融合多学科综合发展的尖端科学技术。目前，在国内外众多高校的本科生均开设了密码学课程。因密码学的军事用途而使得密码学本身带有一定的神秘性，而在日常生活、工作的方方面面均用到秘密技术。由于密码学数学基础的抽象性，使得对密码学的基本概念、原理的学习和理解，存在一定的难度。特别是对单向函数、陷门置换，公钥密码等，非常不符合我们传统的数学思维模式，这给学生的学习和老师的教学均带来一定的难度。在对密码学的这些概念的理解过程中，必须让学生用“转个弯”的方式，从算法形式化的模式去剖析，增强教学过程中这些知识理解的效果。

在计算机科学、安全协议等领域，算法的形式化方法是一种基于数学符合化描述技术，它适合于相关系统的描述、开发和验证。人们将形式化方法用于这些计算机领域，其目的是为了进一步安全可靠的分析这些系统的相关性能，期望以一种较为科学的方式提高所设计算法、系统的可靠性和鲁棒性。这里我们主要用算法形式化的模式去剖析密码学基本概念教学中的一些问题，特别是在公钥密码系统下的基本概念分析和理解。

我们知道，在公钥密码系统中，人们都会自然的想到RSA密码算法，在诸多老师和大学本科生的心目中想到的只是基于大整数分解困难问题的RSA是如何设计的，没有深刻的去理解这个密码体制形式化定义和形式化描述。下面就以公钥加密算法的讲解为例给以说明。

在现代密码学体系中，公钥密码是最能体现当代密码学思想的科学性之一。在1976年美国斯坦福大学的Diffie和Heman两人提出了公开密钥密码的新思想后，不仅其加密算法可以公开，甚至加密用的密钥（主要是公钥）也可以公开而不降低信息的保密程度，也一定程度上解决了之前密码体制的密钥管理问题。那么，在公钥密码体制的讲解过程中，重点给学生交代清楚其形式化定义。

这里以讲解RSA公钥加密算法为例。首先，详细论述公钥加密体制的形式化定义；其次，分析RSA的哪一部分是实现公钥加密的哪一部分功能；再次，分析算法中可能存在的安全漏洞；最后，给出一个具体的数字实例。具体地，一个公钥解密体制，从算法的角度，可以被形式化为一个三元组（K，E，D）。其中K代表的是密钥生成算法，其形式化功能就是生成一对匹配的公、私钥对，为后续算法E、D加解密做准备，K可以是概率算法；E是加密算法，其功能模块就是实现消息的加密，该算法也可以是概率算法；D是解密算法，改算法的功能是实现相应密文的解密操作。然后给出RSA实现各个功能的具体方法，包括RSA的密钥生成算法、加密算法和解密算法三个部分；接下来，形式化定义相应的功能模块，详细分析可能出现的安全问题，攻击者可能掌握的资源，明确指出RSA加密算法的安全性的数学基础；最后用一个数字实例说明算法的教学效果，增强学生对该算法的理解。

可见，应用算法形式化模式分析讲解公钥密码体制及具体的实例，能进一步厘清公钥密码算法的思路，让学生理解RSA加密体制的算法流程和安全性能之关键所在，符合当代大学生在学习过程中分析、解决问题的思维模式，能在教学过程中起到事半功倍的教学效果。该算法形式化方法模式也可以应用到密码学课程的其他知识的教学过程中。

3 应用模块化思想分析密码体制的设计

本节讨论应用算法的模块化思想分析密码体制的设计。在密码学的分组密码体制的教学过程中，根据密码体制的功能进行分块，讲解清楚各个分块的设计原则和目标，给出相应模块的实现方法；最后给出各个功能模块的组合，分析其安全功能没有因为这些功能的组合而降低。让学生清楚该部分内容的架构和“全貌”，能系统的理清密码体制设计的方法和规则，同时做到对知识点的类推和举一反三的效果。下面以分组密码的教学为例。

根据如上分析，在讲授分组密码设计时，可以分三个层面进行论述。首先，根据分组密码的安全需求，论述分组密码需要具有的安全性质。其次，根据这些安全性质，利用算法模块化思想，按照其性质的实现功能，给出相应的功能分块。最后，根据不同的实现方法，给出相应实现算法。

我们知道，对分组密码的主要威胁是已知明文攻击，因分组密码的密钥z被重复使用，即多次一密。为抵抗该类攻击，要求在设计密码时，要求分组密码具有：（1）混淆性：所设计的密码应使得明文、密文、密钥之间的依赖关系相当复杂，以至于这种依赖关系对密码分析者来说是无法利用的。（2）扩散性：所设计的密码应使得密钥的每一个比特影响密文的每一个比特，以防止对密钥进行逐段破译；明文的每一个比特影响密文的每一个比特，以便最充分地隐蔽明文。（3）具有较高的非线性度。根据这些安全性要求，利用模块化设计思想，其分组密码可模块化为计算部件、计算部件的组合、SPN（即替换/置换网络）及多轮迭代与轮函数。不同的模块实现不同的安全性质，同时保证各部件之间的功能不是抵消关系，而是叠加关系，使得其安全性能只会增加，而不是相互抵消。最后，给出具体的分组密码算法，详细分析其具体实现过程，如DES、IDEA、AES等。

可见，应用算法的模块化思想，阐述分组密码体制设计，能做到有的放矢去寻找相应的数学模型实现相应的功能，也给这些密码算法的形式化描述和分析带来诸多便利之处。同时也能让学生充分理解分组密码体制设计的微妙之处及精髓，调动学生的学习热情和积极性，培养学生的密码设计和分析的能力。

4 结语

该文应用算法思维模式讨论大学密码学的教学问题。首先，阐述密码学的相关数学基础课程中无不渗透着算法的思想，特别是在数论、抽象代数中更是如此。其次，应用算法形式化方法和模式讨论公钥密码体制的教学，以提高学生理解公钥密码体制的基本概念及安全性。最后，基于算法设计的模块化设计思想，以分组密码体制设计为例，分析论述这部分的教学方法，让教师和学生在学习和教学中都能够做到有的放矢，以此提高密码学教学过程中学生学习的接收能力。

[1]李云清.算法形式化推导及其在软件重用中的应用[J]. 计算机工程.2003(9) :.