复变函数论课件：第二章 对称加密和消息机密性

第二章对称加密和消息机密性讲授内容加密的基本概念对称加密的基本原理DES算法的基本原理分组密码的工作模式对称密码的密钥管理对称加密的应用

你所知道的密码学的应用军事电子商务（网上购物)网上银行（网上转账，资金查询，……)手机电子邮件……密码学是计算机安全的基础密码学计算机安全基本概念密码学(Cryptology):是研究信息系统安全保密的科学密码编码学(Cryptography):主要研究对信息进行编码,实现对信息的隐蔽密码分析学(Cryptanalytics):主要研究加密消息的破译基本术语明文（Plaintext）：需要加密的原始的消息和数据加密（Encryption）：用某种方法隐藏明文内容的过程密文（Ciphertext）：被加密后的明文解密（Decryption）：把密文转换成明文的过程加密和解密的过程密码体制的五个组成部分明文（Plaintext）：需要加密的原始的消息和数据，用作加密算法的输入。加密算法（EncryptionAlgorithm）：加密算法对明文进行变换，使明文变成不可理解的乱码。密钥（SecretKey）：加密操作和解密操作通常在密钥的控制下进行，密钥包括加密密钥和解密密钥密文（Ciphertext）：被加密的明文，表现出来是一系列不可理解的乱码，用作解密算法的输入。解密算法（DecryptionAlgorithm）：解密算法对密文进行变换，恢复出原来的明文。加密/解密的表示假设明文为P，密文为C，加密密钥为k1，解密密钥为k2加密表示为：C＝EK1（P)；EK1（P)表示使用密钥k1来加密P解密表示为：P＝DK2（C)；DK2（C)表示使用密钥k2来解密C加密通信的模型密码分类按密钥的数量

单密钥(对称密钥)与双密钥(公开密钥)按照加密和解密算法是否保密受限制的密码算法和基于密钥的密码算法按执行的操作

替换(substitution)与换位(permutation)按明文处理方式

流密码(streamcipher)与分组密码(blockcipher)密码算法的分类1按照密钥的特点分类：对称密码算法（symmetriccipher)：就是加密密钥和解密密钥相同，又称秘密密钥算法或单密钥算法，例如DES，Rijndael（AES)。对称密码算法的加密密钥和解密密钥必须保密。公开密钥算法（public-keycipher)

加密密钥和解密密钥不相同，从一个很难推出另一个。又称非对称密钥算法（asymmetriccipher)，例如RSA。公开密钥算法中的一个密钥可以公开让别人知道，所以又称公开密钥（publickey），简称公钥；而用另一个密钥必须保密,所以又称私人密钥（privatekey)

，简称私钥。对称密码算法和公开密钥密码算法对称密码算法加密密钥和解密密钥相同运算速度快非对称密码算法加密密钥和解密密钥不同运算速度慢对称加密算法的表示假设明文为P，密文为C，加密密钥和解密密钥为k加密表示为：C＝EK（P)；EK（P)表示使用密钥k来加密P解密表示为：P＝DK（C)；DK（C)表示使用密钥k来解密C密码算法的分类2按照算法是否保密分为:

受限制的（restricted)算法:算法的安全性基于对算法的保密。基于密钥（key-based)的算法:算法的安全性基于对密钥的保密。受限制的密码算法在现代密码学中，已经不再使用受限制的密码算法。原因如下：算法是要人掌握的。一旦人员变动，就要更换算法。算法的开发是非常复杂的。一旦算法泄密，重新开发需要一定的时间。不便于标准化：由于每个用户必须有自己唯一的加密算法，不可能采用统一的硬件和软件产品。不便于质量控制：用户自己开发算法，需要好的密码专家，否则对安全性难于保障。因此，现代密码学都采用基于密钥保密的安全策略。就是：将加密算法标准化（可以公开），只保护密钥。这样便于标准化和质量控制（可以由高水平的专家开发算法）；一个密钥泄密，只要换一个便可。Kerckhoffs假设一个密码系统应该在除了密钥保密以外的其他信息（包括明文的统计特性、加密/解密的算法、密钥空间及其统计特性等）都公开的情况下是安全的在设计一个密码系统时，目标是在Kerckhoffs假设的前提下实现安全，即密码系统的安全性不依赖加/解密算法的保密，而是依赖所使用的密钥的安全性。对称加密算法的安全应用条件对称加密算法在Kerckhoffs假设前提下要足够安全只有通信的双方知道加密和解密的密钥密码算法的分类3按照明文的处理方法：分组密码（blockcipher):将明文分成固定长度的分组，用同一密钥和算法对每一分组加密，输出也是固定长度的密文。对称密码算法DES,IDEA,RC6,Rijndael（AES）属于分组密码算法。流密码（streamcipher):又称序列密码，流密码每次加密一位或一字节的明文。流密码是手工和机械密码时代的主流密码算法的分类4按照从明文到密文转换的操作类型：替换密码（substitutioncipher):就是将明文中的每一个字符替换成密文中的另一个字符。接收者对密文做反向替换就可以恢复出明文。换位密码（permutationcipher):又称置换密码。明文和密文的字母保持相同，但在密文中字母的顺序被打乱了。替换密码举例1替换密码举例2Caesar密码加密的原理：把明文的字母用相应的字母表中随后的第三个字母替换abcdefghijklmnopqrstuvwxyzDEFGHIJKLMNOPQRSTUVWXYZABC例如:meetmeafterthetogapartyPHHWPHDIWHUWKHWRJDSDUWB替换密码举例2如果给字母表中每个字母分配一个数字abcdefghijklm0123456789101112nopqrstuvwxyZ13141516171819202122232425Caesar密码的加密和解密可以表示为:C=E(p)=(p+k)mod(26)p=D(C)=(C–k)mod(26)替换密码举例3单表代换密码（MonoalphabeticCipher）比Caesar密码复杂，密文对应的字母不仅仅是明文字母的简单移位，而是任意排列的字母明文字母:abcdefghijklmnopqrstuvwxyz密文字母:DKVQFIBJWPESCXHTMYAUOLRGZNPlaintext:ifwewishtoreplacelettersCiphertext:WIRFRWAJUHYFTSDVFSFUUFYA换位密码举例1明文：thiscryptosystemisnotsecure密文eruc,esto,nsim,etsy,sotp,yrcs,iht加密方法把明文顺序倒过来，然后截成固定长度的字母组作密文。换位密码举例2明文：meetmeafterthetogaparty加密的方法把明文按照斜纹的形式排列成一个矩阵，然后按一定的顺序选出矩阵中的各行的字母以形成密文。mematrhtgpryetefeteoaat密文MEMATRHTGPRYETEFETEOAAT换位密码举例3明文：thiscryptosystemisnotsecure加密的方法把明文按照一定的顺序排列成一个矩阵，然后按一定的顺序选出矩阵中各列的字母以形成密文。thiscryptosystemIsnotsecure密文tysnu,hptor,itete,soms,csie,rysc密码学的起源和发展三个阶段：1949年之前密码学是一门艺术1949～1975年密码学成为科学1976年以后密码学的新方向——公钥密码学密码学的起源和发展1949年之前:古典密码（classicalcryptography)密码学还不是科学,而是艺术出现一些密码算法和加密设备密码算法的基本手段(替换：substitution&换位：permutation)出现，针对的是字符简单的密码分析手段出现密码学的起源和发展1949～1975年:计算机使得基于复杂计算的密码成为可能1949年Shannon的“TheCommunicationTheoryofSecretSystems”1967年DavidKahn的《TheCodebreakers》1971-73年IBMWatson实验室的HorstFeistel等的几篇技术报告Smith,J.L.TheDesignofLucifer,ACryptographicDeviceforDataCommunication,1971Smith,J.L,etal.AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem,Aug.1972Feistel,H.CryptographyandComputerPrivacy,May1973数据的安全基于密钥而不是算法的保密密码学的起源和发展1976年以后:1976年Diffie&Hellman的“NewDirectionsinCryptography”提出了公开密钥密码算法。1977年Rivest,Shamir&Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法

公钥密码使得发送端和接收端无密钥传输的保密通信成为可能！密码学的起源和发展1976年以后:对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现“过渡性”的“postDES”算法IDEA,RCx,CAST等90年代对称密钥密码进一步成熟，Rijndael,RC6,MARS,Twofish,Serpent等出现

2001年Rijndael成为DES的替代者密码算法的安全性绝对安全（Unconditionallysecure）

无论破译者有多少密文,他也无法解出对应的明文,即使他解出了,他也无法验证结果的正确性.计算安全（Computationallysecure）

破译的代价超出信息本身的价值;破译的时间超出了信息的有效期.密码学的两个分支密码编码（Cryptography）：构造安全的密码体制，使攻击者不能获得明文或者密钥。密码分析（Cryptanalysis）：试图发现明文或者密钥的过程。密码分析分类1穷举攻击：密码分析者用试遍所有密钥的方法来破译密码。对抗的方法：增加密钥的数量或者增加加密（解密）算法的复杂性。统计分析攻击：密码分析者通过分析明文和密文的统计规律来破译密码。对抗的方法：设法使明文的统计特性不带入密文。数学分析攻击：密码分析者通过数学分析的方法来破译密码。对抗的方法：设计具有坚实数学基础和足够复杂的密码系统。穷举攻击尝试所有的密钥直至成功，是最基本的攻击方式对抗的方法：增加密钥的数量或者增加加密（解密）算法的复杂性。统计分析攻击举例统计分析攻击举例假设存在如下密文：

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ攻击分析

计算明文中相关字母的频率（见下表）

P和Z出现的频率最高，猜测P和Z是e和t

ZW组合出现的频率高，猜测ZW是th，ZWP是theP13.33Z11.67S8.33U8.33O7.50M6.67H5.83D5.00E5.00V4.17X4.17F3.33W3.33Q2.50T2.50A1.67B1.67G1.67…统计分析攻击举例不断根据英文字母的统计规律和密文中字母的统计规律进行猜测和尝试，最后获得明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow.密码分析分类2仅有密文：攻击者只拥有密文已知明文：攻击者拥有明文和相应的密文选择明文：攻击者获得对加密装置的暂时访问，能够选择明文并提交给加密装置获得相应的密文选择密文：攻击者获得对加密装置的暂时访问，能够选择密文并提交给加密装置获得相应的明文选择正文：选择明文和选择密文的组合Feistel分组密码结构由IBM的Feistel于1973年提出几乎所有的对称加密算法都基于这种结构实现Feistel

结构图加密:

Li=Ri-1;Ri=Li-1F(Ri-1,Ki)解密:

Ri-1=Li

Li-1=RiF(Ri-1,Ki)=RiF(Li,Ki)Feistel结构定义Feistel

的加密和解密分组大小：分组越大安全性越高，但性能下降，广泛采用64位的分组密钥位数：密钥越大安全性越高，但性能下降，广泛采用64位的密钥，但现在已经不够用，增加到128位处理的步数，典型16步子钥产生算法。算法越复杂，就增加密码分析的难度每一步的子函数。函数越复杂，就增加密码分析的难度快速软件实现，包括加密和解密算法结构简单，易于分析，便于掌握算法的安全性Feistel分组加密算法的特点DES(数据加密标准）

DES是第一个得到广泛应用的密码算法DES是一种分组密码算法，输入的明文分组为64位，密钥为56位，生成的密文分组为64位DES是一种对称密码算法，采用了Feistel网络结构DES的历史

1973年5月15日,NBS开始公开征集标准加密算法,并公布了它的设计要求:算法必须提供高度的安全性算法必须有详细的说明,并易于理解算法的安全性取决于密钥,不依赖于算法算法适用于不同应用场合算法必须高效、经济DES的历史（续）

1974年8月27日,NBS开始第二次征集,IBM提交了算法LUCIFER，该算法由IBM的工程师在1971~1972年研制1975年3月17日,NBS公开了全部细节1976年,NBS指派了两个小组进行评价1976年11月23日，采纳为联邦标准，批准用于非军事场合的各种政府机构1977年1月15日,“数据加密标准”FIPSPUB46发布1998年12月以后，DES不再作为联邦加密标准DES算法的基本结构初始置换（IP）逆初始置换（IP-1）DES每轮变换

Li=Ri-1Ri=Li-1F(Ri-1,Ki)F函数Expansion:3248S-box:64Permutation扩展/置换表（E表）S盒的结构S盒（S-box）S盒（S-box）（续）S盒（S-box）（续）对每个S盒，6比特输入中的第1和第6比特组成的二进制数对应的十进制数用来确定行，中间4位二进制数对应的十进制数用来确定列，相应行、列位置的十进制数的4位二进制数表示作为输出。例如S1盒的输入为011001，则行数和列数的二进制表示分别是01和1100，即第1行和第12列，S1盒的第1行和第12列的十进制数为9，用4位二进制数表示为1001，所以S1盒的输出为1001。置换表（P表）子密钥的产生置换选择1置换选择2和循环左移次数DES的雪崩效应雪崩效应是指明文或者密钥的微小变化将对密文产生很大的影响。特别地，明文或密钥的某一位发生变化将会导致密文的很多位发生变化。雪崩效应是任何好的密码算法必须具备的一个性质。DES的雪崩效应较强DES的安全性分析差分密码分析

线性密码分析

密钥短穷举破译字典攻击DES:差分密码分析破解DES:247个选择明文(255个已知明文)DES对差分密码分析的抵抗力很强DES:线性密码分析破解DES:243个已知明文DES对线性密码分析的抵抗力稍弱DES:穷举破译DES密钥长度:56位,256≈1017计算机能力为100MIPS次(108)/秒,1万台计算机协同工作一天，计算能力为:

108*10000*24*3600≈10171017/1017=1天DES:穷举破译（续）在CRYPTO’93上，Session和Wiener给出了一个非常详细的密钥搜索机器的设计方案，这个机器基于并行运算的密钥搜索芯片，所以16次加密能同时完成。此芯片每秒能测试5000万个密钥，用5760个芯片组成的系统需要花费10万美元，它平均用1.5天左右就可找到DES密钥。DES:穷举破译（续）1997年1月28日，美国的RSA数据安全公司在RSA安全年会上公布了一项“秘密密钥挑战”竞赛，其中包括悬赏1万美元破译密钥长度为56比特的DES。美国克罗拉多洲的程序员Verser从1997年2月18日起，用了96天时间，在Internet上数万名志愿者的协同工作下，成功地找到了DES的密钥，赢得了悬赏的1万美元。DES:穷举破译（续）1998年7月电子前沿基金会（EFF）使用一台25万美元的电脑在56小时内破译了56比特密钥的DES。1999年1月RSA数据安全会议期间，电子前沿基金会用22小时15分钟就宣告破解了一个DES的密钥。对称加密算法的演化三重DES三重DES简称3DES使用3个密钥并且执行三次DES算法，按照加密－解密－加密的顺序执行获得密文：C=EK3(DK2(EK1(P)))解密时使用这些密钥反向执行相同的操作，使用3个密钥并且执行三次DES算法，按照解密－加密－解密的顺序执行获得明文：

P=DK1(EK2(DK3(C)))假设P为明文，C为密文，Ek（X）表示使用密钥k加密X，Dk（Y）表示使用密钥k解密Y三重DES三重DES3DES的有效密钥长度是：56×3＝168位3DES可以简化使用两个密钥，即k1=k3，这样所提供的密钥长度是：56×2=112位AES背景介绍1997年4月15日，（美国）国家标准技术研究所（NIST）发起征集高级加密标准（AdvancedEncryptionStandard）AES的活动，活动目的是确定一个非保密的、可以公开技术细节的、全球免费使用的分组密码算法，作为新的数据加密标准。对AES的基本要求是：比三重DES快、至少与三重DES一样安全、数据分组长度为128比特、密钥长度为128/192/256比特AES背景介绍1998年8月12日，在首届AES会议上指定了15个候选算法。1999年3月22日第二次AES会议上，将候选名单减少为5个，这5个算法是RC6，Rijndael，SERPENT，Twofish和MARS。2000年4月13日，第三次AES会议上，对这5个候选算法的各种分析结果进行了讨论。2000年10月2日，NIST宣布了获胜者—Rijndael算法，2001年11月出版了最终标准FIPSPUB197。Rijindael算法之所以最后当选，是因为它集安全性、效率及灵活性于一体。AES

的加密和解密AES的特点不属于Feistel结构加密、解密相似但不对称分组长度一般为128位密钥长度支持128/192/256位密钥有较好的数学理论作为基础结构简单、速度快AES的数据结构字节替换（SubstituteBytes）字节替换举例行移位（ShiftRows）列混合(MixColumns)列混合(MixColumns)轮密钥加（AddRoundKey）其他的对称加密算法IDEABlowfishRC5RC4IDEA算法90年首次出现，91年修订，92公布细节，希望取代DES128位密钥，64位分组在PGP中使用BLOWFISH算法作者为BruceSchneierBLOWFISH算法特点采用了Feistel结构，16步快速：18时钟周期一个字节，速度快紧凑：消耗不到5k内存简单：结构简单，易于实现和判定算法强度安全性可变：通过选择不同的密钥长度来实现不同的安全级别子密钥产生过程复杂目前尚未有效的攻击方法RC5加密算法作者为RonRivest（RSA算法的设计者之一）算法特点适合硬件和软件实现速度快能够适应不同字长的处理器灵活的安全性：可变的循环次数，可变长的密钥简单对内存要求低RC4RC4是流密码RC4加密：Ci=MiXORStreamKeyi解密：Mi=CiXORStreamKeyi分组密码的工作模式电子密码本模式（ElectronicCodeBook，ECB）先把明文分成长度固定的分组用同样的密钥分别独立地处理每个分组密码分组链接模式（CipherBlockChaining，CBC）用前面明文分组的加密结果和当前的明文分组进行异或第一个明文分组和初始向量（IV）进行异或电子密码本模式（ECB）PlainPlain

Text

Textt

CipCiphe

r

Texher

TBlockCipherBlockCipherBlockCipherBlockCipherECB的特点简单和有效可以并行实现相同明文→相同密文，同样信息多次出现造成泄漏，故不能隐藏明文的模式信息信息块可被替换、删除、重放误差传递：一个密文块损坏→仅对应明文块损坏密码分组链接模式（CBC）PlainPlain

Text

Textt

CipCiphe

r

Texher

TBlockCipherIVBlockCipherBlockCipherBlockCipherCBC示意图CBC特点

没有已知的并行实现算法能隐藏明文的模式信息

需要共同的初始化向量IV

相同明文

→

不同密文

初始化向量IV可以用来改变第一块对明文的主动攻击是不容易的信息块不容易被替换、删除、重放误差传递：密文块损坏→两明文块损坏安全性好于ECBECB和CBC的比较CFB加密示意图CFB解密示意图CFB特点分组密码－>流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一误差传递：一个单元损坏影响多个单元加密/解密的位置链路加密和端到端加密加密/解密设备的位置链路加密（LinkEcryption）所传输的数据和数据包头都是加密的信息在每个路由器要被解密和重新加密保护用户数据和通讯信息每个路由器都需要加解密设施每个路由器都可能成为脆弱点在较低的网络层次上实现加密/解密设备的位置端到端加密（end－to－end加密）源主机加密数据目的主机解密数据只加密要传输的数据，而数据包头是明文通信方式不安全在较高的网络层次上实现可以采用链路加密和端到端加密的结合来获得更好的安全性密钥的管理所有的密码技术都依赖于密钥密钥的管理本身是一个很复杂的课题，而且是保证安全性的关键密钥管理方法因所使用的密码体制（对称密码体制和公钥密码体制）而异。密钥的生存期所有的密钥都有生存期:授权使用该密钥的周期原因拥有大量的密文有助于密码分析,一个密钥使用得太多了，会给攻击者增大收集密文的机会假定一个密钥的安全受到