下载文档原格式
密码学教师：袁征2012年2月28日第二章古典密码及其破译序言古典密码是密码学的渊源，这些密码大都简单，可用手工或机械实现加解密，现在很少采用。
然而研究古典密码的原理，对理解、构造、分析现代密码都是十分有益的。
本章共分两节：第一节古典密码第二节古典密码的破译1、古典密码概述用你的经验如何设计一个密码算法？1、古典密码概述古典密码的形式很多，归纳起来有下面三种：类型一、代替密码体制类型二、移位密码体制类型三、乘积密码体制1、古典密码概述1. 用密码体制的概念，分析方格密码有什么特点？2. 能不能改进这个密码算法？1、古典密码概述1. 用密码体制的概念，分析单置换移位密码体制有什么特点？2. 能不能改进这个密码算法？1、古典密码概述1. 能不能把方格密码与单置换移位密码体制结合起来？2、基本数学知识1. 回顾学过的同余的概念、性质？2. 密码学中的运算基本上都是同余模运算。
例如：“凯撒密码”，它的原理是将26个英文字母分别用它后面的第3个英文字母代替，若分别以0~25表示英文字母a~z，用m表示“明文”，c表示密文，凯撒密码的加密算法是：E：c=m+3 (mod26) ，如下所示：A B C D E F G H I J K L M N O P Q R S T U V W X Y ZD E F G H I J K L M N O P Q R S T U V W X Y Z A B C2、基本数学知识1. 7≡2(mod 5) ，2包含了整数中的什么数？二、剩余类环1.剩余类：所有模m和r(0≤r<m)同余的整数组成一个剩余类[r]。
例a：所有模5和2同余的整数组成一个剩余类[2]，该剩余类中的元素有无穷多个：2、7、12、17、22…例b：模5的剩余类有[0]、[1]、[2]、[3]、[4] 。
练习：模26的剩余类有那些？2. 欧拉函数：剩余类[r]中与m互素的同余类的数目用Φ(m)表示，称Φ(m)是m的欧拉函数。
古典加密的两种基本方法
古典加密是一种早期的加密方法，它使用简单的替换或置换来实现加密和解密。
其中，替换是指将明文中的每个字符用密钥中相应的字符进行替换，而置换则是将明文中的每个字符轮流替换为密钥中相应的字符。
下面是两种基本的古典加密方法:
1. 恺撒密码：恺撒密码是一种基于替换的古典加密方法，它使用一个固定的密钥对明文进行加密，密钥通常为 3 个或 4 个字母。
加密时，将明文中的每个字符用密钥中相应的字符进行替换，例如，如果密钥为“ABC”,则恺撒密码加密后的文本为“DE”。
恺撒密码的优点是简单易用，但容易被破解。
2. 棋盘密码：棋盘密码是一种基于置换的古典加密方法，它使用一个固定的密钥对明文进行加密，密钥通常为一个矩形网格，其中每个元素都是一个字母。
加密时，将明文中的每个字符轮流替换为密钥中相应的字符，例如，如果密钥为“ABC”,则棋盘密码加密后的文本为“DE”。
棋盘密码的优点是加密强度较高，但需要较大的密钥空间，因此需要更复杂的算法来实现。
密码技术专题（二）—古典密码体制∙1、密码体制的概念o明文信源o密文o密钥与加密运算o密码体制∙2、古典密码体制的发展o古典加密方法o代替密码o换位密码o转轮密码∙3、几种典型的古典密码体制o CAESAR体制o双字的Playfair体制o维吉尼亚体制o Hill体制我们已经知道，一个密码体制由明文信源、密文、密钥与加密运算这四个基本要素构成，下面我们将进一步给出它们的数学模型。
1、明文信源直观地讲，明文信源就是明文字母表或者明文字母。
比如所有的英文字母、全部的中文字符就是典型的明文字母表。
准确一点，明文信源还应当包含明文字母的概率分布。
如果用X表示明文字母表，则它的元素x∈X则就是明文字母。
在明文字母表中，不同的明文字母出现的频率往往是不同的，比如在26个英文字母中，一般来说字母“e”的频率最高；而在汉字中，可能是“的”字频率最高。
所以，一个明文信源记为S=[X,p(x)]，其中X为明文字母表，p(x)为明文字母x∈X 出现的概率，而且p(x)满足如下条件：对任何x∈X，p(x)≥0，且∑p(x)=1。
2、密文密文由密文字母表Y和密文字母y∈Y组成，密文字母表一般是指密文可能使用的全部字母的集合，而y∈Y是它的元素。
密文字母表可以与明文字母表相同，也可以不同。
3、密钥与加密运算密钥用来从密码体制的一组加密运算中选择一个加密运算（或者称为加密步），密钥允许你按照以前制定的规则改变加密，比如每天，或每份报之后，或者每个字符之后。
通常，密钥的组织和编排须利于它们允许通过简单的规则产生单独的加密步。
加密方法的组合复杂度取决于在此方法下密钥的数量。
如果用K表示密钥空间，也就是选择加密步的参数集合，k∈K则称为一个密钥。
加密步就是明文字母表X到密文字母表Y的一个映射：E：X→Y，对每个x∈X。
由于加密步并不是单一的，而是一族运算，因此我们就可以记为Ek=Ek(x)，其中x∈X，k∈K。
除特殊的编码方法外，如多名码或多音码，对于每个k∈K，Ek(x)都是X到Y的1-1映射。
实验一古典密码算法实验一古典密码算法实验名称：古典密码算法实验类型: 设计性实验学时：4适用对象: 信息安全一、实验目的学习常见的古典密码学算法，通过编程实现替代密码算法和置换密码算法，加深对古典密码体制的了解，为深入学习密码学奠定基础。
二、实验要求分析替代密码算法和置换密码算法的功能需求，详细设计实现替代密码算法和置换密码算法的数据结构和流程，给出测试用例和测试步骤，得出测试和结论。
替代密码算法和置换密码算法的实现程序必须提供加密和解密两个接口：int encrypt()和int decrypt()。
当加密或者解密成功时返回CRYPT_OK，失败时返回CRYPT_ERROR。
三、实验原理古典密码算法曾被广泛应用，大都比较简单，使用手工和机械操作来实现加密和解密。
它的主要应用对象是文字信息，利用密码算法实现文字信息的加密和解密。
下面介绍两种常见的具有代表性的古典密码算法，以帮助读者对密码算法建立一个初步的印象。
1.替代密码替代密码的原理是使用替代法进行加密，就是将明文由其它的字母、数字或符合所代替后形成密文。
这里每个明文字母对应的密文字母可能是一个，也可能是多个。
接收者对密文进行逆向替换即可得到明文。
替代密码有五种表现形式：○1单表代替即简单替代密码或者称为单字母代替，明文字母表中的一个字符对应密文字母表中的一个字符。
这是所有加密中最简单的方法。
○2多名码代替就是将明文字母表中的字符映射为密文字母表中的多个字符。
多名码简单代替早在1401年就由DuchyMantua公司使用。
在英文中，元音字母出现频率最高，降低对应密文字母出现频率的一种方法就是使用多名码，如e可能被密文5、13或25替代。
○3多音码代替就是将多个明文字符代替为一个密文字符。
比如将字母“i” 和“j”对应为“K”，“v”和“w”代替为“L”最古老的这种多字母加密始见于1563年由波他的《密写评价》（De furtiois literarum notis）一书。
实验二两种基本古典密码设计与实现
091234 谢锦仪一、实验目的：
该实验为验证性实验。
通过本实验，使学生对于两种基本的古典密码编码方法（“代替”与“移位”）产生深刻的感性认识，体验清楚二者之间的本质差异，为理解和掌握现代密码的相应知识打下良好基础。
二、实验内容：
1．设计一个周期3的多表代换并予以实现，要求：第一个表有密钥字法产生(密钥字自拟)，第二个表由洗牌法产生（注意，字母a~z与数字0~25一一对应，洗牌法即相当于实验一的方法1（n=25）），第三个表由公式法产生（数学公式自拟，注意它须是Z26上的一个一一变换）。
2．设计一个周期5的16-置换移位密码并予以实现，要求：5个16-置换至少有一个是由实验一（n=15）提供的两个方法以为、自行设计的其它方法产生。
三、实验要求：
1. 上述两个古典密码的编程实现，须能对下面一段明文进行正确加密（对代
替密码，空格和标点符号保持不动；对移位密码，空格和标点符号也移位）：
Q is a symmetric block cipher. It is defined for a block size of 128 bits. It allows arbitrary length passwords. The design is fairly conservative. It consists of a simple substitution-permutation network. In this paper we present the cipher, its design criteria and our analysis. The design is based on both Rjindael and Serpent. It uses an 8-bit s-box from Rjindael with the linear mixing layers replaced with two Serpent style bit-slice s-boxes and a linear permutation. The combination of methods eliminates the high level structure inherent in Rjindaelwhile having better speed and avalanche characteristics than Serpent. Speedis improved over Serpent. This version 2.00 contains better analysis, editorialchanges, and an improved key scheduling algorithm. The number ofrecommended rounds is also increased.
2. 抓图显示密文（附页），不能出现明显错误。
四、实验步骤：
1、实验思路
对于代替密码，难点是大小写的转化和保持加密后大小写的不变。
这里利用了专门的字符处理函数库ctype。
用Tolower函数将大写转化为小写，然后转化为数字。
这样才能容易的实现代替加密的过程。
在密钥字算法的实现中，利用字符串处理函数的功能，在拼接比较后，录入到choicewords中，最后进入keytab，作为密钥的一部分。
洗牌法我用的是实验一自己设计的方法，很简单就融入了这个程序之中。
移位密码：由于老师要求用一种全新的产生全排列的方法，我于是想到了RSA公钥体制。
这里面RSA算法是密码学三大算法之一(RSA、MD5、DES)，是一种不对称密码算法。
说如果满足条件：D是素数，N是两个素数(P,Q)之积，(D * E) mod ((P-1) * (Q-1))=1，那么存在Ｃ与Ａ（范围从２到Ｎ－１）一一对应，且Ｃ＝(A EXP D)mod N。
Ａ是一个有顺序的数，Ｃ就是一个看似无规律的伪随机数。
Mod运算表示求模，例如7Mod3=1。
意思是７除以３余１。
类似地8 Mod 3=2,9 Mod 3=0。
EXP表示前面数的后面数次方，其中还有两个附加条件：1,Ｐ和Ｑ不能一样。
2,e<(Ｐ-1)(Ｑ-1)且e与（Ｐ-1）(Ｑ-1)的最大公因数为１。
具体实现的时候，我把1随机安插进去，就成了一个随机全排列了。
具体的代码见附录。
而在利用时间种子产生随机数的函数中，为了避免重复，我在数组b录入元素后，令数组a对应的为0，然后再a不为0时录入b，十分简单。
而将三种方法合并为密钥表的做法与代替的例子类似，这里就不说了。
在最后输出的时候有一个与代替密码不一样的问题：虽然都是由几组密钥组成的keytab，但是黛米可以不分组变换，而移位的密钥表是16*5，不分组变换效果很差。
所以在输出的时候利用i<16时，(i-1)/16为0这一性质，实现了分组变换输出。
2、实验过程
这些代码中很多都在做一个工作：去掉重复的元素，将无重复的存入数组进行后续处理。
根据不同的情况，也使用不同的方法：先存入另一数组，比较后存入处理数组；或者存入一个初始值进处理数组，然后每录入一个就比较一次。
这两种方法显然后一种是更好的，但有时确实又需要辅助数组，这就需要视具体情况而定。
五、实验结果：
1、代替密码
2、移位密码
六、实验体会：
这次的实验由于有老师提供的参考代码，困难程度并不像代码的长度那般惊人。
代替密码的ctype函数库是一个重点，我们开始都犹豫大写的明文加密后如何保持大写不变，另设一组变换时行不通的。
如将大写字母与另外26个数字相对应，那么就要准备两张keytab，而且程序的复杂度会增加很多。
但是利用了isupper函数后这个就简单了，至于公式法，密钥字法和洗牌法，有实验一的思考结果在，都是不难的。
移位密码开始不知道怎么做，不过在上网查过资料之后找到了一种较好的伪随机产生方法。
这次实验还是有一定的难度，但是有老师给的代码，所以不用花太多的时间来编写程序，大大降低了实验难度。
以后的实验应该会越来越难，应该做好预习工作。
七、思考题：
“代替表”与“置换”的不动点、逆等是否一致？
答：不一致。
代替是约定明文集合到另一集合的关系，不一定是原集合，而移位是在明文集合中进行随机排列然后得到的密文。
两者的不动点、逆，只有在统一集合变换时菜可能一致。
