密码学 对称密码学复习课件.ppt

对称密码学复习,本章内容,密码学概述古典密码对称分组密码序列密码随机数的生成,一、密码学概述,密码学研究内容：密码体制：对称密码体制、公钥密码体制杂凑（Hash）函数与消息认证数字签名与身份识别密钥分配与密钥管理各类密码协议：如密钥分发、秘密共享、零知识证明单向函数与伪随机序列生成器密码学提供的功能：机密性、完整性、鉴别、抗抵赖性；,一、密码学概述,教学目标：（1）掌握密码学的基本概念、基本原理、基本思想与基本方法。（2）掌握国内外典型密码算法和密码学的应用技术。（3）具备典型密码的软件开发能力和密码应用能力。,一、密码学概述,基本概念：密码学被分类成密码编码学（Cryptography）和密码分析学(Cryptanalytics)；加密通信模型；密码体制的定义；密码体制的分类；常见的密码分析类型；几种密码算法的安全性的含义；,二、古典密码,C.D.Shannon：采用扩散、混淆和乘积的方法设计密码：混淆（Confusion）：使密文和明文、密钥的统计特性之间的关系复杂化，如非线性因素；扩散（Diffussion）：将每一位明文和密钥的影响扩大到尽可能多的密文位中，以便隐藏明文的统计特性和防止对密钥进行逐段破译，使密文中每一位由明文中多位产生。乘积和迭代：多重加密方法混合使用 对一个加密函数多次迭代古典密码学的两种基本技术：代替（substitution）、置换(permutation）,二、古典密码,典型算法举例：数据安全基于算法保密 1、代换密码：弄明白典型算法的设计，仅要求进行简单的安全性分析单字母代换密码：单表代换密码：移位密码：密钥空间仅为26；仿射密码：e(x)=(ax+b)mod m,密钥空间为广义的单表代换密码：26!易受字母统计频率分析攻击；多表代换密码：维吉尼亚密码、Hill密码、转子机 多字母代换密码：Playfair密码 2、置换密码：弄清置换表的含义；,二、古典密码,多表代换密码：非周期多表代换密码：一次一密、量子密码；周期多表代换密码：维吉尼亚（Vigenere)密码、转子机、Hill密码 维吉尼亚密码密钥空间为：26m，但仍然保留了字符频率统计特性；,二、古典密码,Hill密码：完全隐藏了明文的统计信息，但是线性变换的安全性很脆弱，易受已知明文攻击；,二、古典密码,多字母代换密码：Playfair密码Playfair有2626=676种字母对组合，字符出现概率一定程度上被均匀化，基于字母频率的攻击比较困难，被广泛应用了很多年，但依然保留了相当的结构信息。对于替换密码举例，弄明白典型算法的设计，仅要求进行简单的安全性分析,二、古典密码,2、置换密码：弄清置换表的含义；,三、对称分组密码,对称分组密码的概述 DES+双重DES与3DES AES+相关数学基础分组密码工作模式,三、对称分组密码,3.1 对称分组密码的概述分组密码体制的定义分组密码的安全性、复杂度的概念仅要求了解；分组密码的设计原则：分组长度、密钥长度、混淆和扩散、易实现；典型迭代密码定义理解典型迭代密码分析：穷尽密钥搜索、线性分析法、差分分析法、相关密钥密码分析、中间相遇攻击典型密码结构：Feistel结构、SP结构（代换置换网络）,Feistel结构：DES,14,SP结构（代换置换网络）AES,整个分组P置换,第二次轮密钥加,三、对称分组密码,每种典型算法了解产生、特点及应用情况掌握加解密算法掌握密钥生成算法掌握算法的实现中的问题及编程实现：填充方式、工作模式；了解算法的安全性,三、对称分组密码,3.2 DES1、DES的基本参数、特点及应用：对称分组密码，明文、密钥、密文长度都为64位，面向二进制；2、DES的加解密算法:DES加解密结构DES一轮变换S盒3、DES的密钥生成算法4、DES算法的安全性：了解雪崩效应、密钥长度的争论、差分分析、线性分析、弱密钥和半弱密钥。5、双重DES和3DES,DES加密算法的数学描述：,DES解密算法的数学描述：,DES加密-轮的过程,22,S盒代换操作,Box S1,例如,S1(101010)=6=0110；S1(110011)=11=1011注：行列数均从0开始,0123,DES密钥编排算法,24,三、对称分组密码,双重DES:很难抵挡中间相遇攻击3DES:密钥足够长,兼容性好,目前广泛应用,速度较慢双密钥的3DES：ISO8732，ANSI X9.17三密钥的3DES：PGP，S/MIME,三、对称分组密码,3.3 AES1、AES相关数学基础2、AES的基本参数：AES具有128比特的分组长度，并支持128、192和256比特的密钥长度；SP网络；基本轮函数加迭代，轮数可变；数学基础好；简单快速；3、AES加解密算法：状态4、AES密钥生成算法5、AES的安全性及实现问题，了解,三、对称分组密码,1、AES相关数学基础数论：整除性：因子，素数，最大公因子，互素整数分解，求解最大公因子的方法，Euclid算法模运算：概念、模加法、模乘法、单位元、加法逆元、乘法逆元、运算性质、推广的Euclid算法求乘法逆元的方法有限域：概念、特殊的域中元素的表示及其运算有限域GF(p):加法，乘法，逆元，系数在Zp中的多项式加法和乘法运算GF(28)：加法、乘法、X乘一个字节：有限域GF(28)中的一个元素一个字：系数在GF(28)中并且次数小于4的多项式,有限域GF(28),AES的理论基础定义在GF(28),其基本运算有三种：加法、乘法和x乘；AES的GF(28)表示AES采用GF(28)的多项式元素表示：将b7b6b5b4b3b2b1b0构成的字节看成系数在0,1中的多项式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0加法：两元素多项式的系数按位模2加；乘法：两元素多项式相乘，模m(x)AES采用的既约模多项式为：乘法逆元：a(x)b(x)=1modm(x)根据推广的Euclid算法求出X乘xTime：用x乘以GF(28)的元素若b7=0,则字节左移一位补0；若b7 0,则左移一位补0后，与1B异或；,系数在GF(28)中的多项式,字：系数在GF(28)中并且次数小于4的多项式例：57 83 4A D1 57x3+83x2+4Ax+D1,三种基本运算：字加法、字乘法、字x乘法字加法：对应项系数按位模2加字乘法：多项式乘积再模m(x)=x4+1AES选定一个固定的可逆多项式做乘法；字X乘法：相当于字节循环移位；,三、对称分组密码,2、AES的加解密算法结构：SP网络，虽然加解密算法不同，但是加解密结构相同；几个基本变换及逆变换,AES加密算法流程,AES解密算法流程,2、AES的加解密算法:几个基本变换及逆变换：标准轮变换：Round(State,RoundKey)ByteSub(State);S盒变换 ShiftRow(State);行移位变换 MixColumn(State);列混淆变换 AddRoundKey(State,RoundKey)轮密钥加变换 标准逆轮变换Inv_Round(State,Inv_RoundKey)Inv_ByteSub(State);逆S盒变换 Inv_ShiftRow(State);逆行移位变换 Inv_MixColumn(State);逆列混淆变换 AddRoundKey(State,Inv_RoundKey)逆轮密钥加变换,三、对称分组密码,2、AES的加解密算法几个基本变换及逆变换的定义：S盒（即SubBytes操作）：非线性变换，矩阵定义特点；行移位；逆变换时位移量Nb-C1列混淆.,三、对称分组密码,35,2、AES的密钥生成算法 加密密钥生成算法密钥扩展：扩展密钥的比特数等于分组长度乘以轮数加1特定位置的扩展密钥计算方法不同,轮数不同稍不同；轮密钥选择:,三、对称分组密码,2、AES的密钥生成算法 加密密钥生成算法密钥扩展：扩展密钥的比特数等于分组长度乘以轮数加1特定位置的扩展密钥计算方法不同,轮数不同稍不同；轮密钥选择:,Nb=6且Nk=4时的密钥扩展与轮密钥选取,三、对称分组密码,2、AES的密钥生成算法解密密钥生成算法中解密的密钥扩展与加密的密钥扩展算法稍有不同；解密密钥生成算法定义如下：加密算法的密钥扩展；把InvMixColumn应用到除第一和最后一轮外是所有 轮密钥上；轮密钥选择:,三、对称分组密码,3.4 分组密码工作模式：了解采用工作模式的目的和原则，掌握几种常用模式采用工作模式的目的 掩盖数据模式：相同明文、密钥相同，则密文相同；使算法适应具体应用；工作模式对于DES、AES、3DES等任何分组密码都适用；在很多标准中都有规定：如：NIST(SP800-38A)、FIPS PUB 74和81、ANSI X3.106、ISO9732、ISO/IEC 97116等；,三、对称分组密码,3.4 分组密码工作模式设计的一般原则密码模式通常是基本密码、一些反馈、和一些简单运算的组合。运算是简单的，因为安全性依赖于基本密码，而不依赖模式。强调一点，密码模式不会损害算法的安全性。效率是另一个值得考虑的事情。运算模式将不会明显地降低基本密码的效率。第三个考虑事情是容错。一些应用需要并行加密或解密，而其它一些则需要能够尽可能多的进行预处理。无论怎样，在丢失或增加比特的密文流中，解密过程能够从比特错误中恢复是很重要的,三、对称分组密码,3.5 分组密码工作模式常用的有五种加密模式：设计方法、特点和应用场所、错误传播电码本模式ECB（Electronic Code Book）密文分组链接模式CBC（Cipher Block Chaining）密文反馈模式CFB（Ciphertext Feedback）输出反馈模式OFB（Output Feedback）计数器模式CRT（Counter Mode）短块加密：填充技术、密文挪用技术、序列加密,分组密码工作模式,电码本模式 ECB,电码本模式 ECB 特点,简单和有效 可以并行实现 不能隐藏明文的模式信息相同明文相同密文同样信息多次出现造成泄漏改变一个明文块，只引起相应的密文块的改变，而其他密文块不变。对明文的主动攻击是可能的，信息块可被替换、重排、删除、重放；误差传递：密文块损坏仅对应明文块损坏 适合于传输短信息,密文分组链接模式CBC,密文分组链接模式 CBC 特点,没有已知的并行实现算法 能隐藏明文的模式信息需要共同的初始化向量IV相同明文不同密文初始化向量IV可以用来改变第一块，应该唯一，但不必须改变一个明文块,则相应的密文块及其后的所有密文块将会改变.对明文的主动攻击是不容易的，信息块不容易被替换、重排、删除、重放这个特性意味着CBC模式适用于鉴别的目的，即：这些模式能用来产生消息鉴别码（MAC），MAC附在明文块序列的后面，用来保护消息的完整性。误差传递：密文块损坏两明文块损坏安全性好于ECB适合于传输长度大于64位的报文，还可以进行用户鉴别,是大多系统的标准如SSL、IPSec,密文反馈模式CFB加密示意图,46,密文反馈模式CFB解密示意图,47,密文反馈模式 CFB 特点,分组密码流密码没有已知的并行实现算法隐藏了明文模式需要共同的移位寄存器初始值IV对于不同的消息，IV必须唯一改变一个明文块，则相应的密文块及其后的所有密文块将会改变，这个特性意味着CFB模式适用于鉴别的目的；误差传递：一个单元损坏影响多个单元,1+Nb/j适用于面向数据流的通用传输，认证,输出反馈模式OFB加密示意图,49,输出反馈模式OFB解密示意图,50,输出反馈模式 OFB 特点,分组密码流密码没有已知的并行实现算法 隐藏了明文模式需要共同的移位寄存器初始值IV对不同的消息，IV必须唯一改变一个明文块，只引起相应的密文块的改变，而其他密文块不变。对明文的主动攻击是可能的，信息块可被替换、重排、删除、重放；有些情况下这可能是一个好的特性。例如，OFB模式通常用来加密卫星传输。误差传递：一个单元损坏只影响对应单元安全性较CFB差适用于噪声信道上的数据流的传输（如：卫星通信）,5、计数器模式CTR,52,计数器模式 CTR 特点,使用一个与明文分组等长的计数器，每个明文组，计数器的值必须不同。面向分组的通用传输，适用高速需求可以并行处理；可以预处理：由于加解密算法不依赖于明（密）文，在存储条件允许以及安全保障的条件下，可以预先将要使用的异或值计算出来，以供随后使用；随机存取：对于链接模式,必须加密Ci-1后才能加密Ci,CTR模式可以任意的加密一个组块,有些应用中,可能无需加密或解密所有的组块,只需要解密其中的一个.简单：只要实现加密算法，不需要解密算法，当加密算法与解密算法相差较大时，这个模式有较大优势；可证明安全：已经能够证明CTR模式至少与前面的模式同样的安全；,短块加密,分组密码一次只能对一个固定长度的明文（密文）块进行加解密；称长度小于分组长度的数据块为短块；必须采用合适的技术解决短块加密问题填充技术：ANSI X.923、ISO 10126、PKCS7、ISO/IEC 7816-4等密文挪用技术序列加密,密文挪用技术：不增加密文长度，但控制复杂,密文挪用法也需要指示挪用位数的指示符；负责收信者不知道挪用了多少位，从而不能正确解密;密文挪用加密短块的优点是：不引起数据的扩展;缺点是：解密时要先解密Cn，还原挪用后再解密Cn-1，从而使控制复杂.,密文挪用技术：不增加密文长度，但控制复杂,四、序列密码,1、序列密码的基本概念2、线性移位寄存器序列密码3、非线性序列密码4、RC4,四、序列密码,1、序列密码的基本概念：基本思想：分类：同步序列密码，自同步序列密码二元同步流密码体制模型流密码对密钥流的要求密钥流产生器的通常构建方法；LFSR+非线性组合函数,四、序列密码,2、线性移位寄存器序列密码线性移位寄存器：GF(2)上LFSR的结构反馈函数输出序列的求法,线性反馈移位寄存器,GF(2)上的n级线性反馈移位寄存器：LFSR的状态：LFSR的反馈函数：LFSR输出序列的性质完全由其反馈函数决定；一般总是假定Cn=1,n级LFSR输出序列的周期与状态 周期相等，也小于等于 2n-1。,四、序列密码,4、RC4基本特点:面向字节的密钥大小可变（1256字节）的序列密码；密码序列独立于明文代码少,速度快目前应用最广的商密级序列密码基于非线性数据表变换;RC4算法：S表初始化；只有当S表初始化完成后，才能计算产生密钥字符，才能进行加解密，否则将是不安全的；S表一旦完成初始化，输入密钥就不再被使用密钥流的产生；每生成一个字节的密钥k值，S中的元素个体就被重新置换一次,五、随机数生成,1、随机数的应用和特点了解随机数的应用：随机数的特点：随机性及不可预测性的概念及判定2、伪随机数的产生A、特意构造的算法：线性同余发生器：定义及参数选取BBS发生器：了解密码上安全的伪随机比特产生器 B、基于现存密码算法的算法：对称分组密码：理解几种伪随机数产生器的设计（循环加密、分组密码工作模式OFB，ANSI X9.17）；非对称分组密码Hash函数和消息认证,期中考试安排,时间：第8周上星期三，上午8:00-10:00地点：东校区东区一教DQ216开卷，可以带计算器,专题研究报告,分组：自由组合，每组不超过4人，明确分工选题：与密码学相关题目成果：提交3-5页的研究报告，准备5分钟报告ppt专题报告时间：12月23日上课时间,