基于C语言的“密码学实验”课程教学设计

王会勇，唐士杰

（1. 桂林电子科技大学 数学与计算科学学院，广西 桂林；2. 桂林电子科技大学 电子工程与自动化学院，广西 桂林）

一 引言

随着现代信息技术的发展，信息安全越来越受到重视，使得“密码学”成为很多工科高校信息安全专业的基础课程。但该课程的教学却一直存在一些困难，存在着“高不成低不就”的现象，即一方面，本课程的学习门槛较高；另一方面，学完本课程后，却常有很难用上所学知识的感觉。一个明显表现是信息安全专业的毕业生，无论是本科生还是研究生，都很难在毕业后直接就职于对口职业。究其原因，除课程本身内容丰富、应用要求高等原因之外，实践教学的设计困难、教学效果难以保障也是一个重要原因。

二 “密码学”课程教学的主要困难

从“密码学”课程的内容和教学现状来看，本课程的教学主要存在以下三方面困难。

（一） 密码学的学习门槛较高，且内容十分丰富，学习难度较大

首先，现代密码学的内容主要包含“密码学”的数学与计算机理论基础、“密码学”的理论主体和“密码学”应用三个方面[1]。其中，学习“密码学”所需的数学基础主要包含抽象代数、概率论和数论基础，但学习这些内容首先要求学生具备一些数学基础课程，如线性代数、离散数学、组合数学等，以及一些计算机基础课程，主要包括算法分析、数据结构、编程工具等。除此之外，密码学的学习中还有可能需要信息论和语言学等方面的知识。

其次，现代密码学的主要内容是对称密码与非对称密码，但这两部分内容都存在一些非常复杂、学习难度很高的部分，如对称密码中的DES、AES、SMS4加解密算法、一些HASH算法和非对称密码中的椭圆曲线密码、RSA密码等。即使对具备良好基础的初学者来说，这些内容都是有较大难度的。

另外，为取得良好的教学效果，本课程一般设置理论课和实验课两个部分。理论课程主要学习相关的数学基础、算法基础和密码学基础知识，实验课程的主要目标则是加深学生对理论知识的掌握和理解，并在理论知识与实用技能之间架起桥梁。因此，实验教学的设计在很大程度上决定了本课程的实际教学效果。但“密码学”实验课程的内容也非常丰富，既可以包含基础性内容，如古典密码、对称密码和非对称密码技术，也可以包含扩展应用型内容，如网络基础、漏洞扫描、密码破解、数据库入侵、Web 攻击、缓冲区溢出等。其中有些内容复杂度很高，用基础性工具编程实现的难度很大。

（二） 学生的数学基础与计算机基础薄弱，编程能力普遍不足

如前所述，学习“密码学”课程需要具备较多的数学与计算机基础知识。因此，国内大多数高等院校将本课程设置到本科三年级或四年级开设。但从实际情况来看，多数高校在本科生的一年级和二年级并没有开设“密码学”所需的群论、抽象代数、数论等基础课程，且即使开设了此类课程，很多学生也无法达到课程的考核要求。这就使得“密码学”课程的教学过程不得不预留大量时间来补充相关数学与计算机基础。另一方面，虽然国内大多数高校都为低年级学生开设了C语言等编程类课程，但学生的实际学习效果也很难达到能够编程实现某些较为复杂的密码学算法（如DES、AES等）的程度。

（三） 缺乏实验设备和工具

在设计密码学实验的内容时，通常有两种做法[2]。一种是要求学生用某种高级语言编程实现某些密码算法程序，另一种是要求学生利用实现了特定密码算法的软件工具对某些密码算法进行验证。

对于第一种做法，由于很多密码算法原理比较复杂，编程实现的工作量很大。解决这个问题的一个理想方法是由教师提供程序的主体架构，只要求学生添加少量的关键代码。但在目前，在大多数在线学习平台还很难看到此类程序资源，而让教师自己编写所有程序框架也存在很大困难。

第二种做法只要求学生对某些密码算法做验证，且目前已经有了一些工具，如西普信息安全实验平台、四川农业大学密码学实验课程学习平台[3]、CrypTool[4]等。但此类实验一方面可能需要付费购买实验平台，另一方面对学生的要求通常很低，即学生只需按部就班地操作，基本不需要理解相关密码算法的细节就可以完成任务，因此对学生理解算法帮助较小。

为解决上述困难，有的教师设计了分层教学模式，收到了良好的教学效果。在陆向艳等人[5]的教学设计中，第一层是展示层，即在理论课或实验课开始由教师向学生展示密码算法的原理与基本实现过程。第二层是验证层，包含两种模式：无需编写代码模式和需要编写代码模式。无需编写代码的模式主要针对某些复杂的教学内容，要求学生利用某种已有工具验证密码算法，而需要编写代码的模式则针对某些相对容易编码的内容，要求学生使用某种高级语言编程实现；第三层是应用层，教学目的是训练学生对密码算法综合应用和创新应用的能力，主要采用三种模式开展：课程设计、创新项目和学科竞赛。该教学模式的主要教学内容如表1所示。

表1 密码学实验课程分层教学内容

三 我们的设计

（一） 实验内容

在综合考虑学生实际情况和现有软硬件条件之后，我们将本校数学与计算科学学院信息与计算科学专业16课时的“密码学实验”课程的教学内容分为两类，分别为编程实现类内容和验证类内容。

编程实现类学习内容是教学重点，主要包含四个部分，分别为古典密码（移位密码、仿射密码[6]和 Vigenère密码）[7]、公钥密码（RSA密码和ElGamal密码）[8]、实用密码算法（主要包含伪随机数产生和中国剩余定理）、Diffie-Hellman密钥交换算法[9]。每个部分大约需要3~4学时。

选择上述内容作为编程实现内容的首要原因是上述内容属于密码学中的核心内容，其次是上述内容都较易用高级编程语言实现。另外，上述算法中的一些核心算法是可以反复使用的，如在RSA方案、ElGamal方案和中国剩余定理算法中，都需要用到求乘法模逆元的操作等。反复的使用能够进一步加深学生对这些关键算法的理解和掌握程度。

编程验证类学习内容主要包含对称密码DES算法、哈希函数和数字签名，要求学生在指定的学习平台（目前主要利用四川农业大学密码学实验课程学习平台）完成对指定密码算法的验证，并提交验证报告。此部分可要求学生在上课时间完成（大约需要2~3学时），也可要求学生利用课后时间完成。上述内容虽然也是密码学的基础核心内容，但编程实现的难度太大，故只要求学生完成验证任务。

（二） 实验设计

（1）古典密码学实验。基本目标是通过编程实现经典的代替密码和置换密码，为现代分组密码实验奠定基础。考虑到实现难度和课时限制，我们选择了移位密码、仿射密码和Vigenère密码作为主要实验内容。

移位密码的加密过程是将明文中的每个字母用其后面的第k个字母替代。由于其加解密过程非常直观、简单，因此适于作为学生实验的第一个案例。

仿射密码需引入两个参数α和β，且在解密时需求解有限域Zn上的乘法逆元α-1∈Zn。这可借助扩展欧几里得算法实现。但由于求乘法逆元的操作涉及到较为复杂的代数知识，故可将此内容放在下一次实验课。在本次实验中，由于n通常取为字母表中字母的个数，即n=26，且要求α与n互素，故可直接将Z26上所有与26互素的元素的乘法逆元列表给出，方面学生直接使用（表2）。

表2 Z26上与26互素的元素的乘法逆元表

Vigenère密码是一种多表代换密码，其本质是周期移位密码。Vigenère密码的密钥为一含有d个字母的有限字母序列。当d=1时，Vigenère密码就是移位密码。

由于完整实现该算法的难度较大，我们要求学生使用固定密钥“cat”，并取n=26，对明文“vigenere cipher”进行加密，并计算密文“xizgnxtevkpagr”，然后实现解密过程。

（2）公钥密码实验。实验目标是编写RSA算法和ElGamal算法的简单加解密程序。

由于此实验需要用到乘法逆元，首先需要学生实现乘法逆元的求解过程。这个内容需要实现4个子算法，分别是素数判定算法（此算法在以前的C语言程序设计课程中学习过）、最大公约数算法（使用扩展欧几里得算法）、求乘法模逆元算法和整数幂模算法。

在实验中，为减小实现难度，我们对多项设置做了简化。首先，只要求学生使用较小的参数（如两个素数分别取为3和5，并令n=3×5）。其次，为减小难度，要求学生采用简单映射实现字符到整数的转换（表3）。另外，为简化实现过程，我们没有考虑实用RSA算法所需的填充、分割、通信等算法，只考虑了加解密过程。

表3 字符与整数的转换算法表

在ElGamal算法的实现过程中，需要介绍素数的原根和循环群的生成元的寻找方法。

（3）实用密码算法。本次实验重点是实现一些常用的密码学算法。实验内容主要包括伪随机数产生和中国剩余定理。

伪随机数的产生算法主要要求学生使用C语言中的srand()函数实现，并使用time函数获得系统时间作为srand()函数的种子。中国剩余定理的实现过程则要求学生求解如下一次同余方程组，其中m1，m2，L，mk两两互素。

上述方程组的求解步骤如下：

①判断m1，m2，L，mk是否两两互素。若不满足，输出“不能直接利用中国剩余定理”。

②计算M=m1·m2·L·mk。

⑥判断上述结果是否大于M，若是，将其减去M的若干倍。

⑦输出最终结果。

（4）Diffie-Hellman密钥交换。本次实验的主要目标是理解Diffie-Hellman算法的实现原理，用C语言编程实现Diffie-Hellman密钥协商过程。

该算法的实现过程需要用到欧拉函数计算算法、排序算法（如冒泡排序）、整数幂模算法、求本原根算法、素性判定算法和随机数生成算法。因此，本算法综合性较高，实现难度较大。这也是我们将本算法作为最后一个实验的原因。

首先介绍该算法的基本实现原理与步骤。其次，要求学生采用一些较小的参数模拟实现该算法，如：

对部分心有余力的学生，可要求其在完成基本算法的实现后，额外考虑中间人攻击的模拟实现过程。

（三） 实验过程与结果

对于编程实现类教学内容，我们要求学生利用C语言或其他高级语言编程实现，但推荐使用C语言。这是因为一方面学生已经在前期统一学习了“C语言程序设计”课程，使用C语言能够帮助学生进一步掌握该语言。另一方面，在对某些较复杂的算法任务做简化之后，使用C语言实现的难度并不会很高，是可以接受的。

例如，在所有实验中，我们不要求学生设计可视化输入输出界面；在某些密码算法中，只要求学生使用较小参数完成设计。如在RSA算法和ElGamal算法的实现中，只要求学生使用较小的素数实现算法即可。这种做法极大地降低了使用C语言编程的难度，又可以让学生真正理解所学算法的实现方法。从实验过程来看，几乎所有学生都采用了C语言作为编程工具，并成功完成了编程任务。图2是其中一个学生对“中国剩余定理”的实现代码与运行结果截图。

图2 对中国剩余的定理的实现代码与结果

四 结语

“密码学实验”课程的设计一直是一个比较困难的问题。我们结合本校实际情况与相关文献的经验，设计了一个可行的基于C语言的授课方案。按照我们的方案，学生能够在有限的课时内编程实现课程中的关键密码算法，从而深刻理解并掌握这些内容。对于一些较为复杂的程序，学生也能够通过既有工具验证算法的实际效果，从而在一定程度上掌握这些算法。

为进一步提升学生对某些较复杂算法的验证效果，我们正在设计基于一些在线编程平台（如EduCoder[10]）的测试框架，使得学生能够通过编辑部分关键代码完成整个算法。