第2章传统加密技术.

第二章传统加密技术2.0Introduction2.1SymmetricCipherModel（对称密码模型）2.2SubstitutionTechniques（代换技术）2.3TranspositionTechniques（置换技术）2.4RotorMachines（轮转机）2.5Steganography（隐写术）2.0介绍几个概念：Plaintext(明文)–原始的消息Ciphertext(密文)–加密后的消息Encipher(Encrypt)(加密)-由明文到密文的变换过程Decipher(Decrypt)(解密)-从密文恢复出明文的过程密码学(Cryptology)-研究信息系统安全保密的科学Encryption、Decryptionalgorithm(加、解密算法)–对明文(密文）进行加密（解密）时采用的一组规则SecretKey(密钥)–对加密与解密过程进行控制的参数2.0介绍密码学发展历史密码技术的出现可以追溯到远古时代，英文中密码学（Cryptography）一词来源于古希腊的Kryptos和Graphein，意思是密写。自从人类社会有了战争就出现了密码（斯巴达木卷、中途岛密码战.....)，但1949年以前的密码更多的是一门艺术，那时的密码专家常常靠直觉和经验来设计和分析密码，而不是靠严格的证明。2.0介绍诞生于公元前五世纪的斯巴达木卷，被认为是最早的加密如发送方要发送如下信息:sendmoretroopstosouthernflankateightamtomorrow(明早八点向南翼增兵)于是将信息沿着木杖的方向写在缠绕在木杖的腰带上|S|E|N|D||M|O|R|E||T|R|O|O||P|S||T|O||S|O|U|T|H|E|R|N|||F|L|A|N|K||A|T||E|I|G|H||T||A|M||T|O|M|O|R|R|O|W||然后展开腰带.腰带上面的文字顺序就变成了下面的样子SPTESFNLADTAMONMKTOSOROAMEUTOTRTHERREIOORGWONH2.0介绍2.0介绍1918年，WilliamF.Friedman发表论文“TheIndexofCoincidenceandItsApplicationsincryptography)(“重合指数及其在密码学中的应用”)。1949年，ClaudeShannon（香农）的论文“TheCommunicationTheoryofSecrecySystems)(“保密系统的通信理论”)奠定了密码学的理论基础。20世纪70年代是密码学发展的重要时期，有两件重大事件发生。其一，1976年11月23日，DES（DataEncryptionStandard）算法被确认为联邦标准算法。1998年正式退役。其二，1976年11月，Diffie与Hellman发表了一篇题为“Newdirectionsincryptography”（密码学新方向）的论文，开辟了公开密钥学的新领域，成为现代密码学的一个里程碑。1978年，R.L.Rivest,A.Shamir和L.Adleman实现了RSA公钥密码体制，它成为公钥密码的杰出代表和事实标准，至今仍是当今网络安全的基石。2.0介绍密码体制：加密系统采用的基本工作方式，可以用数学符号来描述：S＝{P,C,K,E,D}其中，P-明文空间C-密文空间K-密钥空间E-加密变换D-解密变换k∈K，发方：P收方：Pk1（公共信道）加密EC=Ek1(P)解密DP=Dk2(C)（秘密信道）k2密钥源2.1对称密码模型2.1对称密码模型加密：C=Ek1(P)解密：P=Dk2(C)=Dk2(Ek1(P))加密算法：对明文进行加密时采用的一组规则。解密算法:对密文进行解密时采用的一组规则。当K1与K2完全相同时，即是我们通常所说的对称加密。（注：算法一般都是公开的）2.1.1密码编码学密码编码学——具备以下三个独立特征：转换明文为密文的运算类型：代换和置换。代换是将明文中的每个元素(位、字母、位组、字串)映射成另一个元素；置换是将明文中的元素重新排列。这些运算都要求不能有信息丢失、即所有运算是可逆的。所用的密钥数：发送方和接收方使用相同密钥，称为对称密码，否则，称为非对称密码。处理明文的方法：分组处理或流式处理。2.1.2密码分析密码分析——密码分析是攻击者为了窃取机密信息所做的事情攻击。密码体制的典型目标是恢复使用的密钥，而不是仅仅恢复出单个密文对应的明文。攻击传统的密码体制有两种一般的方法：密码分析学：这种攻击依赖于算法的性质和明文的一般特征或某些明密文对。这种形式的攻击企图利用算法的特征来推导出特别的明文或使用的密钥。2.1.2密码分析穷举法：就是对可能的密钥或明文的穷举。穷举密钥时，用可能密钥解密密文，直到得到有意义的明文，确定出正确的密钥和明文。穷举明文，就是将可能的明文加密，将所得密文与截取的密文对比，从而确定正确的明文。这一方法主要用于公钥体制和数字签名。阻止穷举的方法有：增加密钥的长度，在明文、密文中增加随机冗余信息等等。上述任何一种方法，如果攻击能成功地推导出密钥，那么影响将是灾难性的：将会危及所有未来和过去使用该密钥加密消息的安全。2.1.2密码分析根据密码分析者对明、密文掌握的程度，攻击主要可分为四种：惟密文攻击（加密算法，要解密的密文）已知明文攻击（加密算法，要解密的密文，用同一密钥加密的一个或多个明密文对）选择明文攻击（加密算法，要解密的密文，分析者任意选择的明文，及对应的密文）选择密文攻击（加密算法，要解密的密文，分析者有目的选择的一些密文，以及对应的明文）选择文本攻击（加密算法，要解密的密文，分析者任意选择的明文，及对应的密文，分析者有目的选择的一些密文，及对应的明文，即为选择明文和选择密文的结合）以上攻击威胁依次增大。一般地，加密算法起码要能经受得住已知明文攻击才行2.1.2密码分析理论上，除了一次一密的密码体制外，没有绝对安全的密码体制。所以，称一个密码体制是安全的，一般是指密码体制在计算上是安全的，即：破译密码的代价超出密文信息的价值；破译密码的时间超出密文信息的有效生命期。2.2代换技术（substitution）密码学的发展：加密算法的两个基本原理：Substitution代换：将明文中的每个元素映射成另一个元素。Permutation置换：将明文中的元素重新排列，明文中的字母保持不变。代换和置换1949年之前-古典密码学49～75年-现代常规密码76年之后-公钥密码学2.2代换技术（substitution）2.2.1Caesar密码有记载表明，在古罗马就已经使用采用代换技术的对称密码。据说有一位名叫JuliusCaesar的国王在作战时曾使用过一种密码技术（如今把这种密码技术称为“凯撒密码”技术）。2.2.1Caesar密码该密码技术的思路是这样的：将26个英文字母a，b，c，…依次排列，z后面再接排a，b，c，…取移位间隔为3，将每个字母（明字符）由与它间隔为3的字母来替代（密字符），由此构成了一张明字符和密字符的对照表，称为密码表,如下所示：abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC由密码表，取明文块M=network，相应的密文块C=QHWZRUN。2.2.1Caesar密码如果把字母表编码为0-25的数字(p27)，加密算法可以如下表达，对于每个明文字母p，代换成密文字母C：C=E(3,p)=(p+3)mod26注意到k(移位间隔)的取值可以在1至25之间变化，所以总共可以得到25个不同的密码表。以上介绍的是k=3的一种情况。如果取k=5，那么明文M=network加密后就变为密文C=SJYBTWP。2.2.1Caesar密码一般化的恺撒加密算法为：C=E(k,p)=(p+k)mod26一般化的恺撒解密算法为：p=D(k,C)=(C-k)mod262.2.1Caesar密码可见，同样的明文，如果k的取值不同，那么就会得到不同的密文。这个k就是这种密码技术的密钥。因为k的取值最多只有25种，所以这种密码技术在计算技术如此发达的今天已经不再安全。但从这种技术中我们可以了解它的加密思想，从而可以古为今用。2.2.1Caesar密码Caesar密码的三个重要特征使我们可以采用穷举攻击分析方法：1.已知加密和解密算法。2.需测试的密钥只有25个。3.明文所用的语言是已知的，且其意义易于识别。2.2.2单表代换密码Caesar密码仅有25种可能的密钥，是远不够安全的。通过允许26个字母任意代换，密钥空间将会急剧增大。如果密文行是26个字母的任意置换，那么就有26！种可能的密钥，这比DES的密钥空间要大10个数量级，应该可以抵挡穷举攻击了。这种方法称为单表代换密码。对于这种加密方法，如何进行攻击呢？根据语言的统计规律，采用统计方法在英语中，字母e是用得最多的，其次为t，0，a，h，I等。最常用的两字母组依次是:th，in，er，re及an。最常用的三字母组是:the，ing，and及ion。2.2.2单表代换密码先得有足够多的密文•几十个字母以上•明文得有明确的意义(古典算法时通常是这样的)统计密文中各个字母的出现概率结合明文的统计•猜测出现得最多密文字母对应明文字母e(或t、a)，最少的是z(或j)•猜测出现得最多密文字母双组是th•观察所谓的明文，并重试2.3.2.2单表代换密码单表代换密码容易被攻击，因为单字母替代不会改变字母的频率，所以原始文字的统计特征几乎被完整保留下来。有两种主要方法可以减少代换密码里明文结构在密文中的残留度：一种是对明文中的多个字母一起加密；另外一种是采用多表代换。2.2.3Playfair密码采用多字母一起加密最著名的密码体制是Playfair密码，将明文中的双字母组合作为一个单元对待，并将这些单元转换为密文的双字母组合。例如使用的密钥词是monarchy，建立右边所示矩阵：MONARCHYBDEFGI/JKLPQSTUVWXZ2.2.3Playfair密码其矩阵的构造如下：首先，从左到右、从上到下填入该密钥的字母，重复的字母只保留一个，其余去除;其次，按照字母表顺序将其余字母填入矩阵的剩余空间。字母I和J被算作一个字母，可以根据使用者的意愿在形成密文时确定用I或J。2.2.3Playfair密码Playfair算法根据下列规则每次对明文的两个字母进行加密，这两个字母构成一对：（1）一对明文字母如果是重复的则在这对明文字母之间插入一个填充字符，如x。例如balloon先把它变成balxloon这样四个字母对。(2)如果分割后的明文字母对在矩阵的同一行中都出现(不需要相邻)，那么分别用矩阵中其右侧的字母代替，行的最后一个字母由行的第一个字母代替。例如，ar加密为RM，ek加密为FE。2.3.2.3Playfair密码（3）如果分割后的明文字母对在矩阵的同一列中都出现，则分别用矩阵中其下方的字母代替，列的最后一个字母由列的第一个字母代替。如mu加密为CM（4）否则，明文对中的每一个字母将由与其同行，且与另一个字母同列的字母代替。例如hs加密为BP，ea加密为IM（或JM）2.2.3Playfair密码Playfair密码与单字母替代密码相比有明显的优势：其一，双字母有26*26=676种组合方式，识别各种双字母组合比单字母困难得多;其二，各种字母组的相对频率范围也更为广泛，使频率分析更加困难。因此，Playfair曾被认为是不可破译的，英国陆军在第一次世界大战中采用了它，二战中它仍被美国陆军和其他同盟国大量使用。2.2.3Playfair密码课堂练习：密钥为monarchy，把明文balloon通过Playfair密码体系加密后得到的密文是什么？2.2.5多表代换加密(维吉尼亚密码)改进简单的单表代换的另外一种方法是在明文消息中采用不同的单表代换。这种方法一般称之为多表代换密