第二章 传统加密技术 2.0密码学历史 2.1密码学基本概念 2.2 代换技术 2.3 置换技术 2.4 轮转机 2.5 隐写术.

Presentation on theme: "第二章 传统加密技术 2.0密码学历史 2.1密码学基本概念 2.2 代换技术 2.3 置换技术 2.4 轮转机 2.5 隐写术."— Presentation transcript:

1 第二章 传统加密技术 2.0密码学历史 2.1密码学基本概念 2.2 代换技术 2.3 置换技术 2.4 轮转机 2.5 隐写术

2 密码学的历史 　密码技术的出现可以追溯到远古时代，英文中密码学（Cryptography）一词来源于古希腊的Kryptos和Graphein，意思是密写。 自从人类社会有了战争就出现了密码（烽火戏诸侯、凯撒密码），但1949年以前的密码更多的是一门艺术，那时的密码专家常常靠直觉和经验来设计和分析密码，而不是靠严格的证明。 1949年，Shannon发表了题为“保密系统的通信原理”一文，开始了密码学的科学研究。近代密码技术已发展为一门和数学紧密相关的学科，即所谓的密码学。密码学发展成为一门系统的技术科学，除了和数学紧密相关而外，还涉及到通信、计算机、微电子学等多种技术门类，所应用的数学工具也从简单的代数发展到近代代数、信息论、数论、组合学、计算机复杂性等等多个领域。本书主要介绍密码学中的基本概念，常用的加密算法及密码的管理。

3 密码学的历史 《六韬》，又称《太公兵法》，传说作者为姜太公。 其中有两种军事通讯密码，一是阴符，二是阴书。
阴符是使用者事先制造一套尺寸不等、形状各异的“阴符”，共8种，每种都代表一定意义，只有通讯双方知道。它们是：大胜克敌符，长1尺；破阵离将符，长9寸；降城得邑符，长8寸；却敌极远符，长7寸；警众坚守符，长6寸；请粮益兵符，长5寸；败军亡将符，长4寸；失利亡士符，长3寸； 较之阴符，阴书进了一步。它应用“一合而再离，三发而一知”的方法。也就是说把一份完整的军事文书裁成3份，分写在3枚竹简上，派3个通讯员分别持这枚竹简出发，到达目的地后，3枚简合而为一，方知原意。中途即使其中一人或二人被捕，也不致失密。

4 密码学的历史 《武经总要》中，曾公亮收纳了当时军队中必用的40个军用短语编成密码本，另以没有重复字的五言律诗一首（正好为40字）作为解码“密钥”。这40个军用短语分别为：“1、请弓；2、请箭；3、请刀；4、请甲；5、请枪旗……37、将士叛；38、士卒病；39、将军病；40、战小胜”。当部将率部出征时，主将发给部将一本密码本，并约好用某一首五言诗作为解码“密钥”。 例如，双方事先约定以杜甫的《春望》为“密钥”。该诗全文为：“国破山河在，城春草木深。感时花溅泪，恨别鸟惊心。烽火连三月，家书抵万金。白头搔更短，浑欲不胜簪。”战斗进行中，如急需增拨弓、箭，统兵部将从密码本中查出“请弓”为1号短信，“请箭”为2号短语，然后再在《春望》一诗中找出其第1、2字分别为“国”和“破”。此将领即可拟一普通公文。公文中混编入“国”和“破”二个字，并在此二字上加盖自己印章。主将收到公文后，就可紧急调集弓和箭前去增援。

5 2.1密码学基本概念 密码学（cryptology)是研究密码系统或通信安全的一门科学。它主要包括两个分支，即密码编码学（cryptography）和密码分析学（cryptoanalytics） 。 密码编码学的主要目的是伪装信息，就是以给定的有意义的数据进行可逆的数学变换，将其变为表面上杂乱无章的数据，使得只有合法的接收者才能恢复有意义的数据，而其余任何人都不能（或很难）恢复原来的数据。 密码分析学的主要目的是研究加密消息的破译和消息的伪造。

6 密码系统的模型 图2-2 密码分析者 明文 密文 明文 消息源 接收者 加密 解密 密钥 密钥 密钥源 密钥源 安全通道

7 明文：原始可理解的消息或数据，作为算法的输入。
加密算法：加密算法对明文进行各种代换和变换。 密钥：密钥也是加密算法的输入。密钥独立于明文和算法。算法根据所用的特定密钥而产生不同的输出。算法所用的代换和变换也依靠密钥。 密文：作为算法的输出，看起来是完全随机而杂乱的消息。它依赖于明文和密钥。对于给定的消息，不同的密钥产生不同的密文，密文是数据的随机流，并且其意义是不可理解的。 解密算法：本质上是加密算法的逆运行。输入密文和密钥，输出原始明文。

8 传统密码的安全使用要满足如下两个要求： 1. 加密算法必须是足够强的。至少，我们希望这个算法在对手知道它并且能够得到一个或者多个密文时也不能破译密文或计算出密钥。这个要求通常用一种更强的形式表述为：即使对手拥有一定数量的密文和产生每个密文的明文，他也不能破译密文或发现密钥。 2. 发送者和接收者必须在某种安全的形式下获得密钥并且必须保证密钥安全。 一般来说，加密算法可以是公开的。对称密码的这些特点使其能够广泛应用。算法不需要保密这一事实使得制造商可以开发出低成本的芯片以实现数据加密算法。这些芯片能够广泛使用，许多产品里都有这种芯片。所以，采用对称密码，首要的安全问题是密钥的保密性。

9 明文X＝［X1,X2,…Xm］字母表为26个大写字母。目前，最常用的字母表为｛0,1｝
加密密钥为K＝[K1,K2…Kj]，密钥K的可能值的范围称密钥空间。 加密Y＝E(K, X)＝［Y1,Y2,…Yn］ 解密X=D(K, Y)= ［X1,X2,…Xn］ 一般假定攻击者知道加密（解密）算法，攻击者的兴趣在于X和K

10 2.1.1 密码编码学 密码编码学系统具有以下三个独立的特征：
1. 转换明文为密文的运算类型：所有的加密算法都基于两个原理：代换和置换，代换是将明文中的每个元素（如位、字母、位组或字组等）映射成另一个元素；置换是将明文中的元素重新排列。上述运算的基本要求是不允许有信息丢失（即所有的运算是可逆的）。大多数密码体制，也称为乘积密码系统，都使用了多层代换和置换。 2. 所用的密钥数：如果发送方和接收方使用相同的密钥，这种密码就称为对称密码、单密钥密码、秘密钥密码或传统密码。如果收发双方使用不同的密钥，这种密码就称为非对称密码、双钥或公钥密码。 3. 处理明文的方法：分组密码每次处理输入的一组元素，相应地输出一组元素。流密码则是连续地处理输入元素，每次输出一个元素。

11 2.1.2 密码分析学 攻击密码体制的典型目标是恢复使用的密钥，而不是仅仅恢复出单个密文对应的明文。攻击传统的密码体制有两种一般的方法：
● 密码分析学：密码分析学攻击依赖于算法的性质和明文的一般特征或某些明密文对。这种形式的攻击企图利用算法的特征来推导出特别的明文或使用的密钥。 ● 穷举攻击：攻击者对一条密文尝试所有可能的密钥，直到把它转化为可读的有意义的明文。平均而言，获得成功至少要尝试所有可能密钥的一半。 如果上述任意一种攻击能成功地推导出密钥，那么影响将是灾难性的：将会危及所有未来和过去使用该密钥加密的消息的安全。 我们首先考虑密码分析学，然后讨论穷举攻击。

12 密码分析学 基于密码分析者知道信息的多少，下表概括了密码攻击的几种类型。 惟密文攻击（加密算法，要解密的密文）
已知明文攻击（加密算法，要解密的密文，用同一密钥加密的一个或多个明密文对 选择明文攻击（加密算法，要解密的密文，分析者任意选择的明文，及对应的密文） 选择密文攻击（加密算法，要解密的密文，分析者有目的选择的一些密文，以及对应的明文） 选择文本攻击 （加密算法，要解密的密文，分析者任意选择的明文，及对应的密文，分析者有目的选择的一些密文，及对应的明文） 以上攻击强度依次增大。一般地，加密算法起码要能经受得住已知明文攻击才行。

13 密码分析学 无条件安全：如果一个密码体制满足条件：无论有多少可使用的密文，都不足以惟一地确定密文所对应的明文，则称该加密体制是无条件安全的。也就是说，无论花多少时间，攻击者都无法将密文解密，这仅仅因为他所需的信息不在密文里。除了一次一密（在以后的章节中将会讲到）之外，所有的加密算法都不是无条件安全的。 计算上安全：实用中，加密算法的使用者应挑选尽量满足以下标准的算法： ● 破译密码的代价超出密文信息的价值。 ● 破译密码的时间超出密文信息的有效生命期。 如果满足了上述两条标准，则加密体制是计算上安全的。

14 密码分析学 对称密码体制的所有分析方法都利用了这样一个事实，即明文的结构和模式在加密之后仍然保存了下来，并且在密文中能找到一些蛛丝马迹。
穷举攻击：试遍所有密钥直到有一个合法的密钥能够把密文还原成明文，这就是穷举攻击。 下表给出了不同密钥大小对应的解密所需时间。

15 2.2 代换技术 首先我们讨论一下所有加密技术都要用到的两个基本模块：代换和置换。
代换法是将明文字母替换成其他字母、数字或符号的方法当涉及字母时，本书约定：用小写字母表示明文，大写字母表示密文，斜体小写字母表示密钥。

16 2.2.1 Caesar密码 已知最早的代换密码是由Julius Caesar发明的Caesar密码。它非常简单，就是对字母表中的每个字母用它之后的第3个字母来代换。例如： meet me after the toga party PHHW PH DIWHU WKH WRJD SDUWB 注意字母表是循环的，即认为紧随字母Z之后的是字母A。 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 z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 如果把字母表编码为0~25的数字： 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 Z 那么，加密算法可以如下表达，对于每个明文字母p，代换成密文字母C：C = E(3, p) = (p + 3) mod 26

17 2.2.1 Caesar密码 一般化的恺撒加密算法为： C = E(k, p) = (p + k) mod 26
一般化的恺撒解密算法为： p = D(k, C) = (C - k) mod 26 如果已知某给定的密文是Caesar密码，那么穷举攻击是很容易实现的：只要简单地测试所有的25种可能的密钥。如图2.3的例子。

18 Caesar密码的三个重要特征使我们可以采用穷举攻击分析方法：
1. 已知加密和解密算法。 2. 需测试的密钥只有25个。 3. 明文所用的语言是已知的，且其意义易于识别。

19 2.2.2 单表代换密码 Caesar密码仅有25种可能的密钥，是远不够安全的。通过允许任意代换，密钥空间将会急剧增大。
如果密文行是26个字母的任意置换，那么就有26！或大于 4×1026种可能的密钥，这比DES的密钥空间要大10个数量级，应该可以抵挡穷举攻击了。这种方法称为单表代换密码。 对于这种加密方法，如何进行攻击呢？

20 根据语言的统计规律引入一种奇妙的分析算法：统计方法

21 2.2.2 单表代换密码 出现频率最高的密文字母很可能对应于出现频率最高的明文字母。
我们可以尝试着做一些代换，信息填入明文，看看是否像一个消息的轮廓。更系统一点的方法是寻找其他的规律。 统计双字母组合的频率是一个很有效的工具。由此可以得到一个类似于图2.5的双字母组合的相对频率图。最常用的一个字母组合是th。

22 2.2.2 单表代换密码 一种对策是对每个字母提供多种代换，就像一个读音可以代表多个单词的同音词一样，一个明文单元也可以变换成不同的密文单元。比如字母e可以替换成16，74，35和21等，循环或随机地选取其中一个即可。如果对每个明文元素（字母）分配的密文元素（如数字等）的个数与此明文元素（字母）的使用频率成一定比例关系，那么使用频率信息就完全被隐藏起来了。 然而，即使采用了同音词方法，明文中的每个元素也只对密文中的一个元素产生影响，多字母语法模式（比如双字母音节）仍然残留在密文中，这样就降低了密码分析者分析的难度。 有两种主要的方法可以减少代换密码里明文结构在密文中的残留度：一种是对明文中的多个字母一起加密，另一种是采用多表代换密码。每一种我们都会简单地提及。

23 Playfair密码 最著名的多表代换密码是Playfair密码，它把明文中的双字母音节作为一个单元并将其转换成密文的双字母音节。 这个密码实际上是由英国科学家Charles Wheatstone于1854年发明的，但是却挂着他的朋友Baron Playfair的名字。在英国的外事机构中，Baron Playfair在密码方面的成就是首屈一指的。 例如使用的密钥词是monarchy，建立下列矩阵。 M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z

24 对明文按如下规则一次加密两个字母： 1. 如果该字母对的两个字母是相同的，那么在它们之间加一个填充字母，比如x。例如balloon先把它变成ba lx lo on 这样四个字母对。 2. 落在矩阵同一行的明文字母对中的字母由其右边的字母来代换，每行中最右边的一个字母就用该行中最左边的第一个字母来代换，比如ar变成RM。 3. 落在矩阵同一列的明文字母对中的字母由其下面的字母来代换，每列中最下面的一个字母就用该列中最上面的第一个字母来代换，比如mu变成CM。 4. 其他的每组明文字母对中的字母按如下方式代换：该字母所在行为密文所在行，另一字母所在列为密文所在列。比如hs变成BP，ea变成IM（或JM）。

25 Playfair密码相对于简单的单表密码是一个巨大的进步。首先，因为有26个字母，故有26×26=676个字母对，因此对单个字母对进行判断要困难得多。而且，单个字母的相对频率比字母对的相对频率在统计规律上要好。这样利用频率分析字母对就更困难一些。 因为这些原因，Playfair密码在很长一段时间内被认为是牢不可破的。第一次世界大战中英军就使用它作为陆军的战时加密体制，并且在第二次世界大战中，美军及其他一些盟国军队仍在大量使用。

26 尽管Playfair密码被认为是较安全的，它仍然是相对容易攻破的，因为它的密文仍然完好地保留了明文语言的大部分结构特征。
图2.6显示了Playfair密码和其他一些密码加密的有效性。图2.6也表明了使用Playfair密码加密后文本的字母频率分布情况。 如果频率分布的信息完全被加密过程隐藏了，那么密文的频率曲线应该是一条水平线，惟密文密码分析由此下手将一无所获。图中所示表明Playfair密码虽然有比明文稍平坦的频率分布曲线，但是仍然透露了大量的信息给密码分析者。

27 Hill密码 另一个有趣的多表代换密码是Hill密码，它是1929年由数学家Lester Hill发明的。加密算法将m个连续的明文字母替换成m个密文字母，这是由m个线性方程决定的 。 例如m=3时，C=KP mod 26 c1 c2 c3 k11 k12 k13 k12 k22 k23 k31 k32 k33 p1 p2 p3 ＝ mod 26

28 解密则使用K的逆矩阵K -1： P＝ K -1 C＝K K -1 P＝P 同Playfair密码相比，Hill密码的优点是完全隐藏了单字母的频率特性。实际上，Hill用的矩阵越大所隐藏的频率信息越多。 尽管Hill密码足以抗惟密文攻击，但是它较易被已知明文攻击破解。对于一个m×m的Hill密码，假如我们有m个明密文对，每个长度都是m，那么可以得到m×m的明文矩阵X和密文矩阵Y，且有Y=KX。 若X可逆，则K=YX -1。若X不可逆，则找到一个可逆的X即可。

29 2.2.5多表代换密码(维吉尼亚密码） 改进简单的单表代换的方法是在明文消息中采用不同的单表代换。这种方法一般称之为多表代换密码。 此类算法中最著名且最简单的是Vigenère密码。 凯撒加密的进一步推广，明文的每个字母使用不同的凯撒加密。并且用另一种方式表达凯撒加密：a(+0),b(+1),… 例如取密钥为: deceptive 密钥: deceptivedeceptivedeceptive 明文: wearediscoveredsaveyourself 密文: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

30

31 2.2.5多表代换密码 这种密码的强度在于每个明文字母对应着多个密文字母，且每个密文字母使用惟一的密钥字母，因此字母出现的频率信息被隐藏了，不过并非所有的明文结构信息都隐藏了。例如，图2.6给出了9个密钥词的Vigenère密码频率分布特征。尽管它对于Playfair密码是一个较大的改进，却依然保留了许多频率信息。 如果认为是用Vigenère密码加密的，破译能否取得进展将取决于能否判定密钥词的长度。洞察到这个事实很重要：如果两个相同的明文序列之间的距离是密钥词长度的整数倍，那么产生的密文序列也是相同的。

32 在前面的例子里，“red”的两次出现相隔9个字母，在两种情况下，“r”都是用“e”加密，“e”都是用“p”加密，“d”都是用“t”加密，因此得到了两个相同的密文序列VTW。分析者只需发现重复序列VTW，而重复的VTW之间相隔9个字符，那么他就认为密钥词的长度是3或9。VTW的两次出现也可能是偶然的，而不一定是用相同密钥加密相同明文序列导致的。然而如果信息长度足够大，就会有大量重复的密文序列出现。 破解密码也依靠于另一个重要的观察。如果密钥词的长度是N，那么密码实际上包含了N个单表代换。例如，以DECEPTIVE作为密钥词，那么处在位置1，10，19，…的字母的加密实际上是单表密码。因此，我们可以用明文语言的频率特征对这样的单表密码分别进行攻击。

33 2.2.5多表代换密码 密钥词的周期性可以用与明文信息一样长的不重复密钥词来消除。Vigenère提出用一个所谓的“密钥自动生成系统”来将密钥词和明文自身连接来生成不重复的密钥词。例如： key: deceptivewearediscoveredsav plaintext: wearediscoveredsaveyourself ciphertext:ZICVTWQNGKZEIIGASXSTSLVVWLA 即使采用这个方案，它也是易受攻击的。因为密钥和明文具有相同频率的分布特征，所以我们可以应用统计学的方法。例如，用“e”加密“e”，由图2.5可以估计出其发生的概率为(0.127)2≈0.016，而用“t”加密“t”发生的概率大概只有它的一半，等等。密码分析者利用这些规律能够成功地进行分析虽然破译Vigenère密码的技术并不复杂 。

34 2.2.5多表代换密码 最终的反破译措施也许只有选择一个和明文毫无统计关系且和它一样长的密钥了。
1918年工程师Gilbert Vernam首先引入了这种体制，其运算基于二进制数据而非字母。 这种技术的本质在于构造密钥的方式。Vernam提出使用连续的磁带，其最终也将循环。所以事实上该体制是使用周期很大的循环密钥。尽管周期很长对于密码分析增添了相当大的难度，但是如果有足够的密文，使用已知或可能的明文序列，或者联合使用二者，该方案是可以被破解的。

35 2.2.6 一次一密 陆军情报军官Joseph Mauborgne提出了一种对Vernam密码的改进方案，从而达到了最完善的安全性。Mauborgne建议使用与消息一样长且无重复的随机密钥来加密消息，另外，密钥只对一个消息进行加解密，之后丢弃不用。每一条新消息都需要一个与其等长的新密钥。 这就是著名的一次一密，它是不可攻破的。它产生的随机输出与明文没有任何统计关系。因为密文不包含明文的任何信息，所以无法可破。

36 2.2.6 一次一密 因为给出任何长度与密文一样的明文，都存在着一个密钥产生这个明文。因此，如果你用穷举法搜索所有可能的密钥，就会得到大量可读、清楚的明文，但是没有办法确定哪一个才是真正所需的，因而这种密码是不可破的。 在实际中，一次一密提供完全的安全性存在两个基本难点： 1. 产生大规模随机密钥有实际困难。任何经常使用的系统都需要建立在某个规则基础上的数百万个随机字符，提供这样规模的真正随机字符是相当艰巨的任务。 2. 更令人担忧的是密钥的分配和保护。对每一条发送的消息，需要提供给发送方和接收方等长度的密钥。因此，存在庞大的密钥分配问题。 因为上面这些困难，一次一密实际很少使用，主要用于安全性要求很高的低带宽信道。

37 2.3置换技术 到现在为止，我们所讨论的都是将明文字母代换为密文字母。与之极不相同的一种加密方法是对明文进行置换，这种密码称为置换密码。
栅栏技术 以列优先的顺序写下明文，以行优先的顺序读出。 例如，用深度为2的栅栏技术加密信息“meet me after the toga party”，可写为： m e m a t r h t g p r y e t e f e t e o a a t 加密后的信息是： MEMATRHTGPRYETEFETEOAAT

38 一个更复杂的方案是把消息一行一行地写成矩形块，然后按列读出，但是把列的次序打乱。列的次序就是算法的密钥。例如：
Key: Plaintext: a t t a c k p o s t p o n e d u n t i l t w o a m x y z Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ 单纯的置换密码因为有着与原始明文相同的字母频率特征而易被识破。如同列变换所示，密码分析可以直接从将密文排列成矩阵入手，再来处理列的位置。双字母音节和三字母音节分析办法可以派上用场。 多重置换提高安全性

39 2.4 转轮机 刚才的例子表明用多步置换得到的算法对密码分析有很大的难度。这对代换密码也适用。我们先来介绍对多层加密原理有着重要应用的例子，轮转机密码系统。 在第二次世界大战中，德国(Enigma密码机)和日本(Purple密码机)都使用了基于转轮原理的密码机。盟军破译了这两种密码，对二战的结局产生了重要的影响。。 转轮机的基本原理如下图所示。

40

41 所以整个系统重复使用26×26×26=17 576个不同的代换字母表，如果用4个或5个转轮，周期数将分别为456 976和11 881 376。
今天，转轮机的意义在于它曾经给最为广泛使用的密码——数据加密标准DES指明了方向。

42 2.5 隐写术 隐写术不是严格意义上的加密，它的方法是隐藏某消息的存在。 常用的隐写术：
● 字符标记：选择一些印刷字母或打字机打出的文本，用铅笔在其上书写一遍。这些标记需要做得在一般场合下辨认不出，除非将纸张按某个角度对着亮光看。 ● 不可见墨水：有些物质用来书写后不留下可见痕迹，除非加热或加之以某种化学物质。 ● 针刺：在某些字母上刺上小的针孔，这一般是分辨不出来的，除非对着光线。 ● 打字机的色带校正：用黑色的色带在行之间打印。用这种色带打印后的东西只在强光下可见。

43 图像水印技术：例如，柯达CD格式的最大分辨率是2048×3072，其中每一个像素包含有24位的RGB颜色信息。改动这24位像素的最低一位对整个画质影响不大。结果是你可以在每一张数字快照中隐藏2.3兆字节的信息。有很多软件包就是采用诸如此类的办法来进行信息隐蔽的。 隐写术适用于如下的情况：通信双方宁愿内容丢失，也不愿他们进行秘密通信的事实被人发现。

44 作业和实验 思考题2.7 习题2.5，2.13，2.16，2.18，2.20 编程题2.22，图像中嵌入水印
作业和实验　 思考题2.7 习题2.5，2.13，2.16，2.18，2.20 编程题2.22，图像中嵌入水印 也可以两个同学一组，一个加密一个解密 可能论文题：中文与英文相比有何特点？中文加密有没有其他可能的加密算法？