简化算法设计及其在《密码学》教学中的应用

摘要：在《密码学》教学中，S-DES是简化算法的一个成功例子。本文根据S-DES的思路，对MD5等算法做了简化设计。教学实践证明，简化算法可以降低学习难度，提高学生学习兴趣，改善教学效果。

关键词：密码学；教学；算法；简化

中图分类号：TP309文献标识码：A文章编号：1009-3044(2007)12-21734-01

Design of Simplified Algorithm and It's Application in Cryptography Course Teaching

LI Yan-jun, OU Hai-wen, MAO Ming

(Beijing Electronic Science and Technology Institute，Beijing 100070, China)

Abstract:In the Cryptography course teaching, S-DES is a successful case of simplified algorithm. In this paper, according to the train of thought, we simplify and design the MD5 algorithm and others. The teaching practice proved it can reduce the study difficulty, raise the interest of students and improve teaching effect.

Key words:Cryptography course; teaching; algorithm; simplify

21世纪以来，随着计算机和网络进一步渗入人们的日常生活，网络中的安全问题越来越受到关注。于是随之产生了信息安全专业这一新兴学科，由于密码技术是信息安全中的关键和核心，《密码学》课程也就成为了信息安全专业课程建设中的重点。由于在各类教材中出现的密码算法一般都是国际上通用的一些算法，理论基础深厚，算法本身也比较繁琐，在教学中通常遇到教师讲得口干舌燥，学生听得昏昏欲睡，普遍反映密码学太高深，太难学了。如何让密码学更简单地被学生接受？笔者认为首先要解决的问题就是简化繁琐复杂的密码算法，去掉算法中重复的步骤，提取出算法的数学原理，然后用简单的流程图说明复杂的算法过程。

在这一方面，S-DES的设计是一个成功的例子，把64比特的明文输入缩小到8比特，16轮的加解密过程同样缩小了8倍。于是出现在学生面前的就不再是64比特明文经过16轮加密的算法，而是8比特明文经过2轮加密的算法，S-DES没有改变DES的算法原理，但是更简洁，也更容易被初学者接受。根据S-DES这个思路，我们对MD5等算法也做了简化，并进行了设计和实现。这里以MD5为例，将我们的工作做简要介绍。

1 MD5的简化

对简化MD5算法简要的叙述为：简化MD5以32位分组来处理输入的信息，且每一分组被划分为16个2bit位子分组，经过了一系列的处理后，算法的输出由四个2bit位分组组成，将这四个2bit位分组级联后将生成一个8bit位散列值。

它也可简单归纳为三句话：（1）输入：任意长度的报文；（2）输入分组长度：32 bit；（3）输出：8 bit 报文。

2 简化 MD5算法的设计

2.1 简化MD5算法的设计流程

由于设计的是8bit输出的简化MD5，所以定义的四个初始化链接变量都为2bit，分组采用的是32bit分组，这样才能保证输出为8bit，每轮压缩函数都能进行16次操作，而又不改变原来MD5的原理。简化MD5产生报文摘要的过程如图1所示。单个 32-bit 分组的简化 MD5 处理过程如图2所示。

T表为：

其中，a,b,c,d = 缓冲区的四个2bit的链接变量，以一个给定的次序排列。

g = 基本逻辑函数F,G,H,I之一。

X[k] = M[q×16 + k] = 在第q个32位数据块中的第k个2bit位。

T[i] = 表T中的第i个2bit位。

+ = 模 2的加。

来分别对应上面的四个压缩函数。

X[0..15]：保存当前32bit待处理输入分组的值。

X[k] = M[q×16 + k] = 在第q个32位数据块中的第k个2bit位。

每次循环(4)的每步(16)内，X[i]的使用顺序各不相同。

2.2 设计说明

简化MD5算法的设计，一般都认为是在原来输出的基础上，任意再选择几位输出，就认为是简化了，其实这是设计的一个误区。不过再应用MD5的时候可以这样做，因为这也是对MD5的一个应用。

在设计时要真正理解MD5的原理，比如从第二个分组开始就要考虑到链接变量的变化。它不再是简单的上一个压缩函数的输出，而是还要再加上原来的初始化变量。这一点容易在设计时被忽略。

简化MD5的设计完全不用考虑到算法的完全性。这一点在设计时容易对设计者产生误导，不利于设计者自由发挥。对于设计者只有走出这个误区，才能设计出自己满意的简化算法。

设计时尽量和MD5原理保持一致，因为这样会使自己在实现时变得简单许多。

3 结束语

如果把MD5算法比成黑匣子的话，那么简化MD5算法出现将会让这个黑匣子变得更加透明。算法本身是为教学设计的，所以它的主要作用还是教学方面，因此，我们对其他一些算法如AES、SHA1等算法也进行了简化和设计，并在实际的《密码学》教学中进行应用。

算法的简化可以让学生更容易接受，使其中的运算过程变得更加直观与形象。由于二者在原理上是相通的，理解了简化算法，也就相应理解了原算法。经过实际的教学检验，学生反映密码算法变得容易学了，学习《密码学》的兴趣和积极性明显提高，教学效果得到了较大改善。

参考文献：

[1]黄刚，于林. FLASH MX标准教程[M]. 北京:北京希望电子出版社,2002.

[2]颜金桫.KCL小土豆工作室[M].FLASH MX 2004ActionScript 2.0与RIA应用程序开发[M]. 北京:电子工业出版社,2005.

[3]陈鲁生，沈世镒. 现代密码学[M]. 北京:科学出版社,2002.

[4]毛明. 大众密码学[M]. 北京:高等教育出版社,2005.

[5]杨波. 现代密码学[M]. 北京:清华大学出版社,2003.

“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”