1、第七章 加密编码,学习得来终觉浅，绝知此事要自悟,Logo,绪论,Contents,1,密码学概述,2,加密编码中的信息论分析,3,古典密码及近代密码,4,现代密码学,5,Logo,密码学其他分支简介,Contents,6,网络通信加密方式,7,密码学理论及应用展望,8,思考题与习题,9,Logo,绪论,信息的传输过程中容易被对手截获，为了对信息进行保密，就需要采用加密编码。加密编码在不断发展、扩展的过程中形成了一门新的学问密码学，它涉及到两部分内容：密码编码和密码分析（破译）。密码学是一个扩展的概念 对密码学存在的误解,Logo,初次接触密码学的人可能会存在的误解：,以为学了密码学就可以破解
2、qq、邮箱密码之类的，其实这类的密码和密码学的一些情况下是两码事，一些密码都没有采用密码技术，而且破解密码的手法也比较简单学习了密码学即可用于破解银行的密码，而实际上破解银行的密码一般利用的不是高深的密码学知识，相反，它可能用各种木马，窃取密码。,Logo,6,1.完整性(Integrity),2.可用性(Availability),3.真实性(Authenticity）,除了通过加密实现机密性(Confidentiality)以外，经过逐步的发展，还可以实现以下安全需求：,4.责任追究性(Accountability）,5.公平性,现代的密码学,7.1 密码学概述,7.1.1 基本专业术语7
3、.1.2 加密编码算法分类7.1.3 密码分析及其分类7.1.4 密码系统的安全性及其分类7.1.5 加密编码的发展历程,明文（Plaintext）：待伪装或加密的消息（Message）。密文(Ciphertext)：对明文施加某种伪装或变换后的输出，也可认为是不可直接理解的字符或比特集，密文常用c表示。解密(decryption)算法则是其相反的过程：由密文转换回明文；加解密包含了这两种算法，一般加密即同时指称加密(encrypt或encipher)与解密(decrypt或decipher)的技术。密码算法(Cryptography Algorithm)，也简称密码（Cipher），通常是指
4、加、解密过程所使用的信息变换规则，是用于信息加密和解密的数学函数。密钥（Secret Key或者Key）：密码算法中的一个可变参数，通常是一组满足一定条件的随机序列。密码系统(Cryptosystem)：是加解密参与的各个要素构成的系统。,8,7.1.1 基本专业术语,密码学的作用：,鉴别：消息的接收者应该能够确认消息的来源（人、设备等）；入侵者不可能伪装成他人发送伪冒信息。完整性：消息的接收者应该能够验证在传送过程中消息没有被修改；入侵者不可能用假冒、篡改的消息代替发送者合法消息。抗抵赖：发送者事后不可能虚假地否认他发送的消息。,10,类似于通信系统的模型，香农也建立了保密系统的模型，如下图
5、7-1所示：,7.1.2 加密编码算法分类,图7-1 保密系统模型,11,EK（M）=C DK（C）=M（7-1）（7-2）这些函数具有下面的特性（见图7-2）：DK（EK（M）=M.,加密和解密运算都使用密钥（即运算都依赖于密钥，并用K作为下标表示），这样，加/解密函数现在变成：,图7-2 使用一个密钥的加/解密,12,有些算法使用不同的加密密钥和解密密钥（见图7-3），也就是说加密密钥K1与相应的解密密钥K2不同，在这种情况下：EK1（M）=C DK2（C）=M（7-3）（7-4）DK2（EK1（M）=M,图7-3 使用两个密钥的加/解密,对称加密算法（对称密码算法）有时又叫传统密码（加密
6、）算法、单钥密码（加密）算法、秘密密钥密码（加密）算法，就是加密密钥能够从解密密钥中推算出来，反过来也成立。,13,基于密钥的算法通常有两类：对称加密算法和公开密钥加密算法。,对称算法的加密和解密表示为：EK（M）=CDK（C）=M,14,公开密钥算法（也叫非对称算法、双钥算法）是这样设计的：用作加密的密钥不同于用作解密的密钥，而且解密密钥不能根据加密密钥计算出来（至少在合理假定的长时间内）。用公开密钥K加密表示为EK（M）=C.虽然公开密钥和私人密钥是不同的，但用相应的私人密钥解密可表示为：DK（C）=M有时消息用私人密钥加密而用公开密钥解密，这用于数字签名，尽管可能产生混淆，但这些运算可分
7、别表示为：EK（M）=CDK（C）=M,公开密钥算法,密码编码学的主要目的是保持明文（或密钥，或明文和密钥）的秘密以防止偷听者（也叫对手、攻击者、截取者、入侵者、敌手或干脆称为敌人）知晓。这里假设偷听者完全能够接获收发者之间的通信。密码分析学是在不知道密钥的情况下。恢复出明文的科学。成功的密码分析能恢复出消息的明文或密钥。密码分析也可以发现密码体制的弱点，最终得到上述结果（密钥通过非密码分析方式的丢失叫做泄露。）,15,7.1.3 密码分析及其分类,(1)唯密文攻击（又称唯密文分析）。密码分析者有一些消息的密文，这些消息都用同一加密算法加密。已知：C1=EK（P1），C2=EK（P2），Ci=
8、EK（Pi）推导出：P1，P2，Pi；K或者找出一个算法从Ci+1=EK（Pi+1）推出Pi+1。,16,常用的密码分析（攻击）有四类，当然，每一类都假设密码分析者知道所用的加密算法的全部知识：,(2)已知明文攻击。密码分析者不仅可得到一些消息的密文，而且也知道这些消息的明文。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），Pi，Ci=Ek（Pi），推导出：密钥k，或从Ci+1=Ek（Pi+1）推出Pi+1的算法。,（3）选择明文攻击。分析者不仅可得到一些消息的密文和相应的明文，而且他们也可选择被加密的明文。已知：P1，C1=Ek（P1），P2，C2=Ek（P2），Pi，Ci=Ek（
9、Pi）其中P1，P2，Pi是由密码分析者选择的。,17,（4）自适应选择明文攻击。这是选择明文攻击的特殊情况。密码分析者不仅能选择被加密的明文，而且也能基于以前加密的结果修正这个选择。,（5）选择密文攻击。密码分析者能选择不同的被加密的密文，并可得到对应的解密的明文，例如密码分析者存取一个防窜改的自动解密盒，密码分析者的任务是推出密钥。已知：C1，P1=Dk（C1），C2，P2=Dk（C2），Ci，Pi=Dk（Ci），推导出：k。,（6）选择密钥攻击。这种攻击并不表示密码分析者能够选择密钥，它只表示密码分析者具有不同密钥之间的关系的有关知识。这种方法有点奇特和晦涩，不是很实际。,18,（7）软
10、磨硬泡(Rubber-hose)攻击。密码分析者威胁、勒索，或者折磨某人，直到他给出密钥为止。行贿有时称为购买密钥攻击。这些是非常有效的攻击，并且经常是破译算法的最好途径。,全部破译。密码分析者找出密钥K，这样DK（C）=P。全盘推导。密码分析者找到一个代替算法A，在不知道密钥K的情况下，等价于DK（C）=P。实例（或局部）推导。密码分析者从截获的密文中找出明文。信息推导。密码分析者获得一些有关密钥或明文的信息。这些信息可能是密钥的几个比特、有关明文格式的信息等等。,19,Lars Knudsen把破译算法分为不同的类别，安全性的递减顺序为：,一个密码系统的安全性（security,safet
11、y）主要与两个方面的因素有关：（1）一个是所使用密码算法本身的保密强度。（2）另外一个方面就是密码算法之外的不安全因素。因此，密码算法的保密强度并不等价于密码系统整体的安全性。,20,7.1.4 密码系统的安全性及其分类,（1）无条件安全性（unconditional security）（2）计算安全性（computational security）（3）可证明安全性(provable security),21,评估密码系统安全性主要有三种方法：,（1）破译该密码系统的实际计算量（包括计算时间或费用）十分巨大，以至于在实际上是无法实现的。（2）破译该密码系统所需要的计算时间超过被加密信息有用的
12、生命周期。例如，战争中发起战斗攻击的作战命令只需要在战斗打响前需要保密；重要新闻消息在公开报道前需要保密的时间往往也只有几个小时。（3）破译该密码系统的费用超过被加密信息本身的价值。如果一个密码系统能够满足以上准则之一，就可以认为是满足实际安全性的。,22,密码系统要达到计算安全性（实际安全性），就要满足以下准则：,数据复杂性（Data Complexity）。用作攻击输入所需的数据量。处理复杂性（Processing Complexity）。完成攻击所需要的时间，这个经常叫做工作因素。存储需求（Storage Requirement）。进行攻击所需要的存储量。作为一个法则，攻击的复杂性取这三
13、个因数的最小化，有些攻击包括这三种复杂性的折中：存储需求越大，攻击可能越快。,23,不同方式衡量攻击方法的复杂性：,第一阶段：1949年之前，密码学还不是科学而是艺术，密码算法的设计者都是凭借自己的直观设计密码算法。第二阶段：19491975年，密码学成为科学，以1949年Shannon的“The Communication Theory of Secret Systems”为标志。第三阶段：1976年以后，出现了密码学的新方向,24,7.1.5 加密编码的发展历程,香农对信息的定义是：信息是消除不确定性的东西，对于加密而言，在让接受者获取信息的同时，希望对手能够获取的信息尽量少，这意味着一个
14、密码系统，对于对手的不确定性应该越大越好，可见密码系统的安全性问题可以转化为信息论中熵、条件熵、平均互信息量的问题。一个一般的密码系统，其加密解密可以表示为：EK（M）=CDK（C）=M对于对手，一般已知密文C，欲增强密码系统的不确定性，则可以增加K的不确定性，或者说从互信息量的角度，通过C获取的关于M（或者K）的互信息量要小；从另外一个角度，C作为条件时，K和M的不确定性大。,25,7.2 加密编码中的信息论分析,在密码学中有两种疑义度：1）对于给定密文C，密钥K的疑义度可表示为 H(K|C)=p(ki,cj)log2p(ki|cj)（7-5）2）对于给定密文C，明文M的疑义度可表示为 H(
15、M|C)=p(mi,cj)log2p(mi|cj),26,7.2.1 加密编码中的熵概念,27,破译者的任务是从截获的密文中提取有关明文的信息或从密文中提取有关密钥的信息I(M；C)H(M)H(M/C)I(K；C)H(K)H(K/C)H(M/C)和H(K/C)越大，破译者从密文能够提取出有关明文和密钥的信息就越小。对于合法的接收者，在已知密钥和密文条件下提取明文信息：H(M/C,K)0 I(M；CK)H(M)H(M/C,K)H(M),疑义度,28,因为 H(K/C)H(M/K,C)H(M/C)H(K/M,C)（M和K交换）H(M/C)（熵值H(K/M,C)总是大于等于零）H(M/C,K)0，上
16、式得 H(K/C)H(M/C)即已知密文后，密钥的疑义度总是大于等于明文的疑义度。我们可以这样来理解，由于可能存在多种密钥把一个明文消息M加密成相同的密文消息C，即满足的K值不止一个。但用同一个密钥对不同明文加密而得到相同的密文则较困难,无法解密。,疑义度,29,又因为 H(K)H(K/C)H(M/C)，则 上式说明，保密系统的密钥量越少，密钥熵H(K)就越小，其密文中含有的关于明文的信息量I(M;C)就越大。至于破译者能否有效地提取出来，则是另外的问题了。作为系统设计者，自然要选择有足够多的密钥量才行。,疑义度,30,在破译密码时，有时候我们会尝试用一个一个的密钥尝试加密所有的明文，看得到的
17、明文是否有意义，这样就可以在一定的程度上判断密钥是否是正确的。一个密码系统，就是需要让对手看来有更大的自由度，这样他们就无法确定明文。可以认为明文冗余度对于密码系统自由度的销噬。,7.2.2 密码系统的自由度,香农给出的唯一解距离的计算公式：（7-12）U为唯一解距离，H（K）为密码体制的熵，D为语言冗余度。根据以上方法得出的唯一解距离都很短。你认为信息论中的冗余度与在这里的冗余度一样吗？在此距离下是有唯一解吗？,31,7.2.3 唯一解距离与理想保密,32,7.2.4 完善保密与一次一密体制,香农定义了完善保密（完全保密，Perfect Secrecy）：对一个密码体制而言，如果对所有明文空
18、间中的任一明文x和密文空间中的任一密文y，都有，即截获密文后，明文的概率分布不发生改变，则称该密码体制具有完善保密性(Perfect secrecy)。或称该密码体制是完全保密的。根据密文与明文长度相等是否获得关于明文信息？,33,7.2.5 具有误导功能的低密钥可信度加密算法,如何让错误密钥得到的明文也有意义？选择题的扩充一次一密的改进,34,7.2.6 多重不确定的密码体制,现有密码系统中只有密钥是不确定的密码分析有哪些确定的条件，算法可以让这些条件不确定？是否可以让算法、加密重数等信息也不确定？,世界上最早的一种密码产生于公元前两世纪。是由一位希腊人提出的，人们称之为棋盘密码，原因为该密
19、码将26个字母放在55的方格里，i,j放在一个格子里，具体情况如下图7-4所示：,35,7.3 古典密码及近代密码 7.3.1 常见古典密码,图7-4 棋盘密码,古代密码多数可以通过字母频率攻击来破解，以恺撒密码为例，即使在不知道移位所对应的数字是3的情况下（因为可以是其它数字，而要破解的关键就是要找到这个数字），可以通过检查字母出现的频率来推测，比如：原文：p a n d a s o f t w a r e 密码：s d q g d v r i w z d u h,36,7.3.2 古典密码的分析,在这里，“d”出现的次数最多，由于英语中最常出现的两个字母是“a”和“e”，于是可以分别进行检
20、验。在“e”的情况下，“d”在“e”的后面第25位，然后用25来检验其它字母，出现如下情况：密码：s d q g d v r i w z d u h 向后25位译码：t e r h e w s j x a e v i这个字母序列没有丝毫意义，所以这次尝试不成功。然后再用3来试验，可以得到如下结果：密码：s d q g d v r i w z d u h向后3位译码：p a n d a s o f t w a r e,37,1834年，伦敦大家的实验物理学教授惠斯顿发明了电机，这是通信向机械化、电气化跃进的开始，也是密码通信能够采用在线加密技术提供了前提条件。对于分组密码，分组长度是固定的，如何
21、对任意长度的明文进行处理才能保证通过密文唯一地得到明文？,38,7.3.3 近代密码,前面两章介绍了古典密码和近代密码，它们的研究还称不上是一门科学。直到1949年香农发表了一篇题为“保密系统的通信理论”的著名论文，该文首先将信息论引入了密码，从而把已有数千年历史的密码学推向了科学的轨道，奠定了密码学的理论基础。,39,7.4 现代密码学,有利于对密码算法的安全性进行公开测试评估；防止密码算法设计者在算法中隐藏后门；易于实现密码算法的标准化；有利于使用密码算法产品的规模化生产，实现低成本和高性能。,40,对于商用密码系统而言，将密码算法公开的优点包括：,系统的保密性不依赖于对加密体制或算法的保
22、密，而仅依赖于密钥的安全性。满足实际安全性，使破译者取得密文后在有效时间和成本范围内，确定密钥或相应明文在计算上是不可行的。加密和解密算法应适用于明文空间、密钥空间中的所有元素。如果不能适应，应该进行相应的处理，比如填充。加密和解密算法能快速有效地计算，密码系统易于实现和使用。,41,一个提供机密性服务的密码系统是实际可用的，必须满足的基本要求：,7.4.1 对称加密算法,对称加密算法分为分组密码和流密码算法。目前世界上较为通用的分组加密算法有AES、IDEA和DES，流密码算法有RC4，A5。这类加密算法的计算速度非常快，因此被广泛应用于对大量数据的加密过程。,1.AES算法Rijndael
23、之所为能当选AES，主要是因为：(1)运算速度快，软硬件实现都表现出非常好的性能；(2)对内存的需求非常低，很适合于受限制的环境下；(3)算法可靠，使用非线性结构S盒，有足够的安全性；(4)该算法能有效抵抗差分分析和线性分析攻击；(5)Rijndael是一个分组迭代密码，被设计成128、192、256比特三种密钥长度，可用于加密长度128、192、256比特的分组，相应的轮数为10、12、14，分组长度和密钥长度设计灵活。,43,扩展密钥是从密钥矩阵变换而来，之所以称之为“扩展”是因为在AES的加密过程中，要对数据进行Nr+1次密钥加运算（包括一次初始密钥加运算），每次加密的密钥都不一样，我们
24、将这Nr+1次密钥加运算过程中用到的所有的密钥的集合叫做扩展密钥。迭代的轮数Nr是变化的，取值是根据Nb和Nk的值确定的，AES算法中给出了它们之间如下的对照表：,44,在进行加密之初，首先要生成每一轮加密的子密钥（轮密钥），而实际上原始密钥（种子密钥）是远远不够的，所以它通过密钥扩展来生成足够的轮密钥。,45,例如：如果Nb=6，Nk=4那么我们的加密过程应该进行Nr+1=13次，那么也就有13个扩展密钥。由于这些密钥要和state_matirx矩阵做异或运算，所以每个扩展密钥必须转化为一个和state_matirx矩阵同维数的加密矩阵才可以进行每个元素一对一的运算。由Nb和Nr的值，我们可
25、以计算出扩展密钥的整体“长度”，这个长度的单位为4个字节。如下公式可以给出：Nb*（Nr+1）；例如Nb=6，Nr=12则“长度”为78；,表7-1 Nr取值表,中间的迭代轮和结尾轮有一定的共同之处，下面介绍中间迭代轮包含4个步骤：,字节代换（SubBytes）透过一个非线性的替换函数，用查找表的方式把每个字节整体替换成对应的字节，也就是说这是一个8bit的S盒，这个变化具有很好的非线性性。行移位（ShiftRows）将矩阵中的每个横列进行左循环移位移位。,列混合（MixColumns）为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节，它是GF(28)上乘法运算，其
26、中所乘的因子是3个固定的数01，03，01。轮密钥加（AddRoundKey）：矩阵中的每一个字节都与该轮对应的轮密钥（round key）做XOR运算；每个轮密钥（子密钥）由密钥（又称加密密钥、种子密钥）通过密钥生成方案（key schedule）扩展产生。,迭代轮的4个步骤：,考虑到查表比计算更快，时间复杂度低，但是是以空间复杂度为代价的，AES加密算法的查表优化：使用32或更多bit寻址的系统，可以事先对所有可能的输入建立对应表，利用查表来实作SubBytes，ShiftRows和MixColumns步骤以达到加速的效果。这么做需要产生4个表，每个表都有256个格子，一个格子记载32bi
27、t的输出；约占去4KB(4096字节)内存空间，即每个表占去1KB的内存空间。如此一来，在每个加密循环中，只需要查16次表，作12次32bit的XOR运算，以及AddRoundKey步骤中4次32bitXOR运算。,用128bit的密钥（循环次数为10），那么每次加密的分组长为128bit的例子来说明算法，128bit有16个字节，每次加密一个128bit的分组，每次从明文中按顺序取出16个字节假设为a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14a15，这16个字节在进行变换前先放到一个44的矩阵中，形成状态（state）。如下图7-5所示：,图7-5 状态图,首先进行
28、一个初始的密钥加运算。接着进行开始第一次循环的第一个变换：SubByte。字节变换,图7-6 字节代换查表过程示意图,表中的S12为一个字节，可以用两个十六进制（XY）16来表示，S12=（53）16，下表是根据XY来建立的对应SubByte输出值的表。,接着是ShiftRows步骤：将状态中的各行进行循环移位，第1行（对应行值为0）不移动，第2行左循环移位1字节，以此类推，S为移动后的字节位置。,图7-7 行移位示意图,MixColumns步骤：,S0c(02S0c)(03S1c)S2cS3c，但这个结果可能会超出一个字节的存储范围，所以实际上还要对结果进行处理。,接着是AddRoundKe
29、y步骤：将密钥编排得到的对应轮的轮密钥与前面的结果进行异或运算。,图7-8 密钥加示意图,分组密码的工作模式主要有：电子密码本模式ECB、密码分组链接模式CBC、密码反馈模式CFB、输出反馈模式OFB、计数器模式CTR、密文挪用模式CTS等等。,(1)电子密码本模式ECB优点为1.简单；2.有利于并行计算；3.误差不会被传送；缺点：1.不能隐藏明文的模式；2.可能对明文进行主动攻击；,(2)密码分组链接模式CBC,优点：1.不容易主动攻击，安全性好于ECB，适合传输长度长的报文，是SSL、IPSec的标准。缺点：1.不利于并行计算；2.误差传递；3.需要初始化向量IV。,(3)密码反馈模式CF
30、B,优点：1.隐藏了明文模式;2.分组密码转化为流模式，无需填充处理；3.可以及时加密传送小于分组的数据;缺点：1.不利于并行计算;2.误差传送：一个明文单元损坏影响多个单元;3.唯一的IV;,(4)输出反馈模式OFB,优点：1.隐藏了明文模式;2.分组密码转化为流模式;3.可以及时加密传送小于分组的数据;缺点：1.不利于并行计算;2.对明文的主动攻击是可能的;3.误差传送：一个明文单元损坏影响多个单元;,RSA工作原理,任意选取两个不同的大质数p和q，计算乘积n=p*q；任意选取一个大整数e，e与(p-1)*(q-1)互质，整数e用做加密密钥。注意：e的选取是很容易的，例如，所有大于p和q的
31、质数都可用。确定解密密钥d：d*e1 mod（p-1）*（q-1）根据e、p和q可以容易地计算出d。公开整数n和e，但是不公开d；将明文P(假设P是一个小于r的整数)加密为密文C，计算方法为：CPe mod n 将密文C解密为明文P，计算方法为：PCd mod n,(5)计数器模式CTR,图7-12 CTR的模式,7.4.2 公开密钥加密算法,定理7-1 欧拉定理：若n,a为正整数，且n,a互素，则a(n)1(mod n)（7-15）其中(n)称为欧拉函数，欧拉定理实际上是费马小定理的推广。可以利用它来简化幂的模运算。,7.4.3 hash函数,hash函数也称杂凑函数（算法）、散列函数、哈希
32、算法，就是把任意长的输入消息串变化成固定长的输出串的一种函数。这个输出串称为该消息的杂凑值。一般用于产生消息摘要，密钥加密等。,一个安全的杂凑函数应该至少满足以下几个条件：,输入长度是任意的，这是因为明文的长度一般是任意的;输出长度是固定的，并且要足够长以保障安全性，根据目前的计算技术应至少取128bits长，以便抵抗生日攻击;对每一个给定的输入M，计算输出即杂凑值Hash（M）是很容易的；,已知杂凑值Hash（M）反推X，使得Hash（M）=Hash（X）在计算上是不可能的（其中X不一定等于M）；给定杂凑函数的描述，找到两个不同的输入消息M1和M2杂凑到同一个值（即Hash（M1）=Hash
33、（M2）是计算上不可行的hash值的每一bit都与M的每一bit相关，并有高度敏感性。,一个安全的杂凑函数应该至少满足以下几个条件：,7.5 密码学其他分支简介,在密码学中，有许多方案、协议、应用或算法，具有许多特别的功能，它们不一定是关于保密性、认证性的，这些方案虽然有些复杂，我们没有必要一一掌握，但是，有必要了解它们的概念，当需要运用的时候，按照相应的关键词、名称去查阅相关的文献资料即可。,7.5.1 特殊数字签名,盲签名（blind signature）代理签名（Agent Signature Scheme）群签名（group signature、又称团体签名）不可抵赖的数字签名（undeniable signature）指定的确认者签名（designated confirmer signature，指定证实人签名）一次性签名(One-Time Signature),7.5.2 零知
