密码学中的算法设计(岳峰)

尚焕清

（浙江工业大学 软件工程1203班 201226630308 浙江 杭州 310023）

【摘 要】 密码学是一门历史悠久、实用性很强的学科。密码学最初是随着政治和军事需要的而逐步发展起来的。随着时代的进步，信息安全越来越重要，密码学也变得越来越精深，通过各种各样的算法策略，可以实现多种加密方案。这里通过密码学的基本知识引入一些典型的算法展现算法在密码学中的应用。

【关键词】密码学 算法设计 解密 加密 随机数

Algorithm Design In Cryptology

【Summary】

Cryptology is a discipline which have a strong practical and with a long history. Initially, Cryptology developed gradually with the needs of political and military. With the develop of era, information security becomes more and more important, Cryptology becomes more and more profound either, through a variety of algorithm strategy can achieve a variety of encryption scheme. This text will show you the algorithm in the application of Cryptology by introduce some typical basic knowledge of cryptology algorithms. 【keyword】

Cryptology Algorithm Design decrypt encrypt random number

1． 密码学概述

(1).密码学的发展 密码学的发展经历了几个主要的阶段，在有些文献中将其分为古典密码、近代密码和现

代密码。这里将密码学分为初级阶段(手工阶段)、中级阶段(机械阶段)和高级阶段(电子与计算机阶段)。

A. 初级阶段 在密码学初级阶段，密码学表现形式为手工密码，或者也可以称为艺术密码。这个阶段的密码主要服务于当时的军事和政治，密码的形式呈现多样化。加密和解密都依赖于密码设计者的创意或者智慧，而没有严格的理论推倒证明。比如意大利数学家卡丹(G.Cardan)发明的卡丹密码，又称网格式密码(grill cipher)，如图1(1)-1所示。

将密码融于一张写满字的纸张上，约定好密文的位置，顺序读取位置即可获取密文。

图1(1)-1

卡丹密码卡和读取位置

B.中级阶段

中级阶段，密码学已经开始走向成熟，一些专家学者开始对密码学进行定量的分析和理论的证明。同时，基于这些理论的各种机械形式的密码机相继出现。比如德国的Enigma、美国的Sigaba以及日本的Red和Purple等。这个时期依然主要服务于军事和政治。

C.高级阶段

在密码学的高级阶段，密码开始趋于民用。这离不开计算机以及现代通信技术的发展，同时各种私钥密码算法体系（例如DES算法、AES算法等）和公钥密码算法体系（例如RSA算法等）的出现也极大地促进了密码学应用的普及。这个时期，密码机开始走出机械化，普遍采用电子和计算机来实现。

同时，随着密码学的不断发展，现在的密码学以及不局限于传统的信息加密解密。目前，密码学已经开辟了数字签名、共享秘密等新的领域。

(2).密码学的基本概念

密码学是一门比较广泛的学问，往往涉及攻防两个方面。密码学就是在敌对双方不断“攻”和“防”的发展中走向成熟的。密码学的一个简单定义就是：

密码学 = 密码编制学 + 密码分析学。

其中，密码编制学就是研究好的密码系统，保护信息不被敌方或者任何无关的第三方获得。密码分析学则是研究攻破一个密码系统的途径，将隐蔽的信息恢复出其本来的面目。这样，通俗的说，密码学就是研究信息加密和破译密码的一门学问。

谈到密码学就要涉及密码系统。一个密码系统包含明文字母空间、密文字母空间、密钥空间和算法。而密码系统的两个基本单元就是算法和密钥。其中：

明文字母空间：要传递信息明文的取值范围。 密文字母空间：加密后密文字母的取值范围。 密钥：加密和解密过程中所用到的关键字。 密钥空间：密钥字母的取值范围

算法：一些规定了明文和密文之间变换方法的公式、法则或者程序。

一般来说，明文字母空间依赖于不同国家或系统需要设定为字母或汉字。密文字母空间依赖不同加密系统，一般也为汉字或字母等。密钥则是一串随机的二进制序列。算法则比较

丰富，有DES算法、AES算法、RSA算法等。

2． 柯克霍夫斯原则

密码学是一门攻防兼备的技术。目前还没有精确的从理论上度量一个密码系统保密能力的方法。到哪有一个基本原则就是破译者掌握的关于密码的系统的知识越多，成功破译的可能性越大。对密码系统的威胁性越大。根据破译者掌握的知识程度的攻击，可以大体分为如下几类：

第1等级攻击——仅知算法的攻击，对密钥一无所知。

第2等级攻击——已知密文的攻击，还能搜集到传递的密文信息。

第3等级攻击——已知明文的攻击，还能搜集到某些明文和密文的对应关系。 第4等级攻击——在前述基础上，还能有选择搜集到某些明文和密文的对应关系。 第5等级攻击——在前述基础上，还能像合法用户一样使用密码系统发送加密的信息。 第6等级攻击——在前述基础上，还能改变、截获或者重发信息。

越往后，破译能力越强，对密码系统的安全性破坏越大，但一个密码系统设计时，往往只需考虑经受1、2等级攻击即可。这一点，1883年由柯克霍夫斯（A.kerchoffs）提出，即密码系统中的算法即使被破译者所知，也应该无助于用来推导出明文或者密钥。因此，现在这一原则被称为柯克霍夫斯原则，并被广泛接受。

3． 经典密码学算法方案例举

经典密码学大致可以分为传统密码学和现代密码学两类。了解经典密码学可以加深对密 码体系的理解

传统密码学包括如下几种算法方案： 换位密码算法方案； 单表代替密码算法方案；

同音代替密码算法方案； 多表代替密码算法方案； 多字母组代替密码算法方案； 转轮密码机算法方案。

现代密码学大体有如下几类： 序列密码算法方案； 分组密码算法方案； 公钥密码算法方案。

4． 经典密码算法部分算法分析

(1).替换加密解密算法

A. 替换加密算法

替换加密算法的基本方法是这样的，首先给定一个密钥 n ,对应明文中的每一个字符的ASCII码都向后移动 n 而得到的相应的加密算法，按照这个思想编写算法：

char[] jiami(char[]str, int n) {

int i , len; char[]miwen;

len = str.length;

if((miwen = new char[len+1] == NULL)) {

cout<<”申请内存失败”<}

for( i = 0 ; i < len ; i ++) {

miwen[i] = (char)(str[i] + n); }

miwen[len] = ‘\\0’; return miwen; }

这里，输入参数str为明文字符数组，输入参数n为指定的加密密钥。程序严格遵循了前述算法。

B. 替换解密算法

替换解密密码算法的基本思想：首先给定一个密钥n，这个密钥必须和加密时的密钥一致，对应密文中的每一个字符的ASCII码都向前移动n而得到相应的明文。

char[] jiemi(char[]str, int n) {

int i , len; char[]mingwen;

len = str.length;

if((mingwen = new char[len+1] == NULL)) {

cout<<”申请内存失败”<}

for( i = 0 ; i < len ; i ++) {

mingwen[i] = (char)(str[i] - n); }

mingwen[len] = ‘\\0’; return mingwen; }

输入参数str为密文字数组，输入参数n为指定的加密密钥。

(2).换位加密解密算法

换位密码方法有很多种，有一种是基于二维数组移位的换位加密解密算法。二维数组移位的换位解密算法就是将明文字符串按照一个给定的顺序保存在二维数组中，然后按照另外一个顺序读出，便得到密文。执行相反的过程便可以恢复出明文。

例如，有一个字符串“Hello everyone！”，这里指定一个4×4的二维数组来保存该字符串，如图4(2)-1所示。明文的方向为按行存储，从列的方向便可以读出密文:

“Ho ene reley!lvo”

执行相反的过程便可以恢复出明文字符串。

A. 换位加密算法

基于二维数组移位的加密算法的操作步骤： (1) 给定一个二维数组的列数，也就是该二维

数组每行可以保存的字符个数。

图4(2)-1 二维数组换位加密解密方案

(2) 将明文字符串按行依次排行到该二维数组中。 (3) 按列读出该二维数组中的字符，这样便得到密文。

B. 换位解密算法

(1) 给定一个二维数组的列数，也就是该二维数组每行可以保存的字符个数。这个数应该和

加密算法中一致。

(2) 将密文字符串按列依次排列到改二维数组中。 (3) 按行读出该二维数组中的字符，这样便得到密文。

5.结束语

密码学是现代社会十分重要的学科，也是计算机算法的一个重要演练场。通过各种算法实现各种加密方案，可以使得我们的信息安全得到保障。但是科学发展的速度很快，很多今天热门的方案，过几天或许就被破解出来。所以使用算法不断地创新出新的加密方案是一个不会过时的主题。

【参考文献】

[1]王晓东，计算机算法设计与分析[M].北京：电子工业出版社，2012:1-4. [2]张素霞，基于数据结构的程序递归算法设计[J].硅谷，2012,7(12)：48,108. [3]赵志云、衡友跃，The Classic Algorithm Fundamental of Program Language Java[M].北京：中国铁道出版社，2012,5(1):350-369.