加密

《网络信息安全》中国科学技术大学肖明军[e-mail]2第二章数据加密技术基础•教学目的：熟悉并掌握以下内容：密码理论、现代加密技术及其应用、网络加密技术。•重点与难点：重点分析DES算法、RSA算法、MD5算法原理和应用。同时分析密钥交换技术、密码分析与攻击的方法和网络加密技术。难点是密钥管理与交换技术3第二章数据加密技术基础•本节学习目标：了解加密技术的发展及其相关知识掌握加密技术的原理最基本的加密算法对称加密算法原理非对称加密算法原理4导入新课•加密技术是保护网络信息安全的核心技术之一，是结合数学、计算机科学、电子与通讯等诸多学科于一身的交叉学科。•在计算机网络通信中，给网络双方通信的信息加密是保证网络信息安全的重要措施之一，起着其他安全技术无法替代的作用。5为什么要使用加密技术•因特网的飞速发展，一方面提供快捷的通信方式给众多的商家带来无限的商机；另一方面网络的不安全因素又使广大用户受到威胁。•为了网络信息的安全，人们选择了数据加密和身份认证。•人们对机密文件进行加密，防止他人随便阅读。•加密技术使网络信息安全得到了提高。62.1密码学的历史•古代加密手法（手工阶段）古代加密方法大约起源于公元前440年出现在古希腊战争中的隐写术。当时为了安全传送军事情报，奴隶主剃光奴隶的头发，将情报写在奴隶的光头上，待头发长长后将奴隶送到另一个部落，再次剃光头发，原有的信息复现出来，从而实现这两个部落之间的秘密通信。密码学用于通信的另一个记录是斯巴达人于公元前400年应用Scytale加密工具在军官间传递秘密信息。Scytale实际上是一个锥形指挥棒，周围环绕一张羊皮纸，将要保密的信息写在羊皮纸上。解下羊皮纸，上面的消息杂乱无章、无法理解，但将它绕在另一个同等尺寸的棒子上后，就能看到原始的消息。我国古代有以藏头诗、藏尾诗、漏格诗及绘画等形式来将真实意思隐藏在诗文或画卷中特定位置的记载，使人难以发现隐藏其中的“话外之音”。72.1密码学的历史•古典密码（机械阶段）古典密码的加密方法一般是文字置换，使用手工或机械变换的方式实现。古典密码系统已经初步体现出近代密码系统的雏形，它比古代加密方法复杂，其变化较小。古典密码的代表密码体制主要有：单表代替密码、多表代替密码及转轮密码。Caesar密码就是一种典型的单表加密体制；多表代替密码有Vigenere密码、Hill密码；著名的Enigma密码就是第二次世界大战中使用的转轮密码。82.1密码学的历史传输密文的发明地是古希腊，一个叫AeneasTacticus的希腊人在《论要塞的防护》一书中对此做了最早的论述。公元前2世纪，一个叫Polybius的希腊人设计了一种将字母编码成符号对的方法，他使用了一个称为Polybius的校验表，这个表中包含许多后来在加密系统中非常常见的成分，如代替与换位。Polybius校验表由一个5X5的网格组成，网格中包含26个英文字母，其中I和J在同一格中。每一个字母被转换成两个数字，第一个是字母所在的行数，第二个是字母所在的列数。如字母B就对应着12。使用这种密码可以将明文“message”置换为密文“32154343112215”。92.1密码学的历史古罗马：Caesar密码CaesarwasagreatsoldierABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC密码本Fdhvduzdvdjuhdwvroglhu明文密文CAESAR密码：c=（m+3）Mod26102.1密码学的历史1834年，伦敦大家的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也是密码通信能够采用在线加密技术提供了前提条件。1914年第一次世界大战爆发，德俄相互宣战。在交战过程中，德军破译了俄军第一军经给第二军的电文，从中得知，第一军的给养已经中断。根据这一重要情报，德军在这次战役中取得了全胜。这说明当时交战双方已开展了密码战，又说明战争刺激了密码的发展。1920年，美国电报电话公司的弗纳姆发明了弗纳姆密码。原理是利用电传打字机的五单位码与密钥字母进行模2相加。如若信息码（明文）为11010，密钥码为11101，则模2相加得00111即为密文码。接收时，将密文码再与密钥码模2相加得信息码（明文）11010。112.1密码学的历史•转轮密码机ENIGMA，由ArthurScherbius于1918年发明，使得英军从1942年2月到12月都没能解读出德国潜艇发出的信号。4轮ENIGMA在1944年装备德国海军•英国的TYPEX打字密码机，是德国3轮ENIGMA的改进型密码机。它在英国通信中使用广泛，且在破译密钥后帮助破解德国信号122.1密码学的历史•现代密码前面介绍了古典密码和近代密码，事实上还称不上是一门科学。直到1949年香农发表了一篇题为“保密系统的通信理论”的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。该文利用数学方法对信息源、密钥源、接收和截获的密文进行了数学描述和定量分析，提出了通用的秘密钥密码体制模型。主要特点把算法和密钥分开密码算法可以公开，密钥保密密码系统的安全性在于保持密钥的保密性132.2密码学的基本概念1.密码学的概念密码学这个词是从两个意为“秘密书写”的希腊字演化而来的，它是一门隐匿消息的艺术和科学。密码学包括密码编码学和密码分析学两部分，这两部分相互对立，但也相互促进，相辅相成。密码编码学研究的是通过编码技术来改变被保护信息的形式，使得编码后的信息除指定接收者之外的其他人都不可理解密码分析学研究的是如何攻破一个密码系统，恢复被隐藏起来的信息的本来面目数学定义：密码系统是一个5元组（E，D，M，K，C），M是明文集，K是密钥集，C是密文集，E：MKC是加密函数集，D：CKM是解密函数集。142.2密码学的基本概念2.保密通信模型)(mEceK发送方接收方加密算法E解密算法D加密：解密：不安全信道密码分析（Cryptanalysis）明文m密文c明文m加密密钥Ke解密密钥Kd)(cDmdK152.2密码学的基本概念3.基本术语明文（plaintext）：即原始的或未加密的信息、报文（message）。密文（ciphertext）：指明文经过加密后得到的信息。加密（encrypt,encryption）：指通过编码将信息从一个可理解的明文形式变换成一个错乱的、不可理解的密文形式的过程。解密（decrypt,decryption）：将密文还原成明文的过程。密码算法（Algorithm）、密码（Cipher）：加密和解密变换的规则（数学函数），有加密算法和解密算法。c=E(m),m=D(c),D(E(m))=m密钥（Key）:密码算法中的一个变量c=EKe(m),m=DKd(c),DKd(EKe(m))=m密码编码（Cryptography）：通过信息编码使信息保密。密码分析（Cryptanalysis）：用分析方法解密信息。16密文：0110解密：密钥：0101明文：0011•已知明文、密文，怎样求得密钥？C=PKP=CK异或运算（不带进位加法）：明文:0011加密：密钥:0101密文：0110K=CP一个简单的加密算法—异或172.3密码分析•在未知密钥的前提下，从密文恢复出明文、或者推导出密钥，对密码进行分析的尝试。•攻击方法分类（根据已知信息量的多少）唯密文攻击（Ciphertextonly）分析者有一些消息的密文，都是用同一算法加密的。分析者的目标是恢复尽量多的明文或者推算出密钥。已知明文攻击（KnownPlaintext）已知明文攻击：密码分析者不仅可以得到一些消息的密文，而且也知道这些消息的明文。分析者的任务是得到加密的密钥或者得到一个算法，该算法可以解密用同样的密钥加密的消息。182.3密码分析选择明文攻击（ChosenPlaintext）选择明文攻击：分析者不仅知道一些消息的明文和密文，而且可以选择被加密的明文。这比已知明文攻击更加有效。分析者的任务是得到加密的密钥或者得到一个算法，该算法可以解密用同样的密钥加密的消息。选择密文攻击（ChosenCiphertext）选择密文攻击：密码分析者能选择不同的被加密的密文，并可以得到对应的解密的明文，密码分析者的任务是推出密钥。主要针对公钥算法。选择密钥攻击（ChosenKey）选择密钥攻击：并不表示密码分析者能够选择密钥，只表示密码分析者具有不同密钥之间关系的有关知识。192.3密码分析•Successindealingwithunknownciphersismeasuredbythesefourthingsintheordernamed,perseverance,carefulmethodsofanalysis,intuition,luck.Theabilityatleasttoreadthelanguageoftheoriginaltextisverydesirablebutnotessential.ParkerHitt‘‘军事密码破译指南’’的开场白•毅力、审慎的分析方法、直觉、运气202.3密码分析•密码算法的安全性破解算法的代价大于加密数据本身的价值破解算法的时间超过了信息的生命期KeySize（bits）NumberofAlternativeKeysTimerequiredat106Decryption/µs32232=4.3x1094.3milliseconds56256=7.2x101620hours1282128=3.4x10385.4x1018years1682168=3.7x10505.9x1030yearsAverageTimeRequiredforExhaustiveKeySearch212.4古典密码系统•古典密码主要可以分为：换位密码（TranspositionCipher）替代密码（SubstitutionCipher）代替密码与换位密码的组合222.4古典密码系统•换位密码也称为排列组合密码，它无需对明文字母作任何变换，只需对明文字母的顺序按照密钥的规律相应的排行组合后输出，然后形成密文。232.4古典密码系统美国南北战争CANYOUUNDERSTAND输入方向输出方向明文：Canyouunderstand密文：codtaueanurnynsd242.4古典密码系统矩阵换位法NETWORKSECURITY明文：NETWORKSECUIRTY密文：EWNTRSOKCREUTIY密钥：Key=（34，f）加密函数：解密函数：加密fEWNTRSOKCREUTIY解密f-124134321f314243211f252.4古典密码系统•替代密码在替代密码中，用一组密文字母来代替一组明文字母，但保持明文字母位置不变。262.4古典密码系统恺撒密码CaesarwasagreatsoldierABCDEFGHIJKLMNOPQRSTUVWXYZDEFGHIJKLMNOPQRSTUVWXYZABC密码本Fdhvduzdvdjuhdwvroglhu明文密文恺撒密码：c=（m+3）Mod26恺撒密码为经典的单表替代密码。单表替代即简单替代或称为单字母替代，明文字母表中的一个字符对应密文字母表中的一个字符。这是所有加密中最简单的方法。272.4古典密码系统恺撒密码很容易受到利用统计特性的唯密文攻击。统计方法假定明文语言具有特定的统计特性，并且检查密文的统计特性是否符合这些假定。这些假设一起被称为语言模型。包括单字母模型、双字母模型、Markov模型和单词模型等等。如下表为英语中字母频率表：a0.080b0.015c0.030d0.040e0.130f0.020g0.015h0.060i0.065j0.065k0.005l0.035m0.030n0.070o0.080p0.02