第8章分组密码课件.ppt

第8章 分组密码,第8章 分组密码,81 分组密码概述,定义8.1 一个分组密码是一种映射：记为E(X,K)或 称为明文空间，称为密文空间，为密钥空间。,81 分组密码概述定义8.1 一个分组密码是一种映射：,82 分组密码的设计原则,有关实用密码的两个一般设计原则是Shannon提出的混乱原则和扩散原则。混乱：人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐蔽明文数字统计特性。,82 分组密码的设计原则 有关实用密码的两个一般设计原则是,软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，比如8、16、32比特等。在软件实现中，按比特置换是难于实现的，因此我们应尽量避免使用它。子块上所进行的一些密码运算应该是一些易于软件实现的运算，最好是用一些标准处理器所具有的一些基本指令，比如加法、乘法和移位等。,软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进,硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用规则结构，因为密码应有一个标准的组件结构以便其能适应于用超大规模集成电路实现。,硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用,其他原则：简单性原则：包括规范的简单性和分析的简单性。必须能抗击所有已知的攻击，特别是差分攻击和线性攻击。可扩展性。要求能提供128、192、256比特的可变分组或密钥长。,其他原则：,83 分组密码的结构,83 分组密码的结构,Feistel网络与SP网络，它们的主要区别在于：SP结构每轮改变整个数据分组，而Feistel密码每轮只改变输入分组的一半。AES和DES分别是这两种结构的代表。Feistel网络（又称Feistel结构）可把任何轮函数转化为一个置换，它是由Horst Feistel在设计Lucifer分组密码时发明的，并因DES的使用而流行。“加解密相似”是 Feistel型密码的实现优点。SP网络（又称SP结构）是Feistel网络的一种推广，其结构清晰，S一般称为混淆层，主要起混淆作用。P一般称为扩散层，主要起扩散作用。SP网络与Feistel网络相比，可以得到更快速的扩散，不过SP网络的加解密通常不相似。有关这两种结构的特点，读者在了解了DES和AES算法之后再细细体会。,Feistel网络与SP网络，它们的主要区别在于：SP结构每,8.4 分组密码的安全性,8.4.1 安全需求 如果不知道密钥的知识，攻击者从密文恢复出明文是实际不可能的。用固定的k比特的秘密钥，加密T个明文，其中，最大化T后仍能达到一个可接受的安全性是现代分组密码追求的目标。几乎所有当代分组密码用更小的查表（代替盒或S盒）合并其他变换（线性变换）模仿这样一个大的随机查表。这种做法实际上是安全性和可接受的复杂性的一个折中。,8.4 分组密码的安全性 8.4.1 安全需求,8.4.2 安全模型,1）无条件安全性。2）多项式安全性。3）“可证明的安全性”。4）实际的安全性。5）历史的安全性。,8.4.2 安全模型 1）无条件安全性。,8.4.3 分组密码作为一个伪随机置换,伪随机意味：在多项式时间内，加密询问使得没有攻击者可以区分分组密码和一真实的随机置换；相应于选择明文攻击。超伪随机意味：在多项式时间内，加、解密询问使得没有攻击者可以区分分组密码和一真实的随机置换。相应于选择明、密文攻击。分组密码也可以与单向函数联系。,8.4.3 分组密码作为一个伪随机置换 伪随机意味：在多项式,8.4.4 攻击的分类,数据复杂度：实施一个攻击所需输入的数据量，用长为N的分组作单位。处理复杂度：执行一个攻击所花的时间，时间单位可取攻击者不得不亲自做的加密次数。存储复杂度：需要记忆的字，单位可取长为N的分组。,8.4.4 攻击的分类 数据复杂度：实施一个攻击所需输入的数,组密码的攻击方法目前有：穷举密钥搜索法、差分分析、截断差分分析、不可能差分分析、高阶差分分析、线性分析、差分线性分析，Boomerang攻击、相关密钥攻击、插值攻击、非双射攻击、Slide攻击、攻击。,组密码的攻击方法目前有：穷举密钥搜索法、差分分析、截断差分分,8.5 典型的分组密码算法DES,DES的历史1971 IBM，由Horst Feistel 领导的密码研究项目组研究出LUCIFER算法。并应用于商业领域。1973美国标准局征求标准，IBM提交结果，在1977年，被选为数据加密标准。,8.5 典型的分组密码算法DES DES的历史,8.5.1 DES的描述,DES利用56比特串长度的密钥K来加密长度为64位的明文，得到长度为64位的密文该算法分三个阶段实现：1.给定明文X，通过一个固定的初始置换IP来排列X中的位，得到X0。X0=IP（X）=L0R0其中L0由X0前32位组成，R0由X0的后32位组成。2.计算函数F的16次迭代,根据下述规则来计算LiRi(1=i=16）Li=Ri-1,Ri=Li-1 F(Ri-1,Ki)其中Ki是长为48位的子密钥。子密钥K1，K2，K16是作为密钥K（56位）的函数而计算出的。3.对比特串R16L16使用逆置换IP-1得到密文Y。Y=IP-1（R16L16）,8.5.1 DES的描述DES利用56比特串长度的密钥K,第8章分组密码课件,IP-初始置换,58,50,42,34,26,18,10,2,60,52,44,36,28,20,12,4,62,54,46,38,30,22,14,6,64,56,48,40,32,24,16,8,57,49,41,33,25,17,9,1,59,51,43,35,27,19,11,3,61,53,45,37,29,21,13,5,63,55,47,39,31,23,15,7,IP-初始置换58,50,42,34,26,18,PC1,57,49,41,33,25,17,9,C Half 1,58,50,42,34,26,18,10,2,59,51,43,35,27,19,11,3,60,52,44,36,63,55,47,39,31,23,15,D Half 7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4,PC157,49,41,33,25,17,9,S-box-1,0 1 2 3 4 5 6 7 8 9 a b c d e f COL S1 14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,S-box-10 1 2 3 4 5,DES一轮加密的简图,Li-1 Ri-1,F,+,Li Ri,Ki,DES一轮加密的简图 Li-1 Ri-1F+Li,对F函数的说明：（类比于S-DES）F（Ri-1,Ki）函数F以长度为32的比特串A=R（32bits）作第一个输入，以长度为48的比特串变元J=K(48bits)作为第二个输入。产生的输出为长度为32的位串。(1)对第一个变元A，由给定的扩展函数E，将其扩展成48位串，E（A）(2)计算E（A）+J，并把结果写成连续的8个6位串,B=b1b2b3b4b5b6b7b8(3)使用8个S盒，每个Sj是一个固定的416矩阵，它的元素取015的整数。给定长度为6个比特串，如Bj=b1b2b3b4b5b6计算Sj(Bj)如下：b1b6两个比特确定了Sj的行数,r(0=r=3);而b2b3b4b5四个比特确定了Sj的列数c（0=c=15）。最后Sj(Bj)的值为S-盒矩阵Sj中r行c列的元素（r,c）,得Cj=Sj(Bj)。(4)最后，P为固定置换。,对F函数的说明：（类比于S-DES）F（Ri-1,Ki）,DES 轮函数F（）,DES 轮函数F（）,DES中使用的其它特定函数：初始置换IP：见140页图4-4-3,从图中看出X的第58个比特是IP（X）的第一个比特；X的第50个比特是IP（X）的第二个比特逆置换IP-1；扩展函数E；置换函数P。从密钥K计算子密钥：实际上，K是长度为64的位串，其中56位是密钥，8位是奇偶校验位（为了检错），在密钥编排的计算中，这些校验位可略去。(1).给定64位的密钥K，放弃奇偶校验位（8，16，64）并根据固定置换PC-1（见144页图4-4-9）来排列K中剩下的位。我们写 PC-1(K)=C0D0其中C0由PC-1（K）的前28位组成；D0由后28位组成。,DES中使用的其它特定函数：初始置换IP：见140页图4-,(2)对1=i=16，计算Ci=LSi(Ci-1)Di=LSi(Di-1)LSi表示循环左移2或1个位置，取决于i的的值。i=1,2,9和16 时移1个位置，否则移2位置（143页表4-4-2）。Ki=PC-2(CiDi),PC-2为固定置（见145页图4-4-10)。注：一共16轮，每一轮使用K中48位组成一个48比特密钥。可算出16个表，第i个表中的元素可对应上第i轮密钥使用K中第几比特！如：第7轮的表7：K7取K中的比特情况：52 57 11 1 26 59 10 34 44 51 25 199 41 3 2 50 35 36 43 42 33 60 1828 7 14 29 47 46 22 5 15 63 61 394 31 13 38 53 62 55 20 23 37 30 6,(2)对1=i=16，计算Ci=LSi(Ci-1)D,轮密钥编排,K,PC-1,C0 D0,LS1,LS1,C1 D1,LS2,LS2,LS16,LS16,C16 D16,PC-2,PC-2,K1,K16,轮密钥编排KPC-1C0 D0LS1LS1,14,17,11,24,1,5,C half 3,28,15,6,21,10,(bits 1-28)23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,D half 30,40,51,45,33,48,(bits 29-56)44,49,39,56,34,53,46,42,50,36,29,32 C half provides bits to S1-S4,D half to S5-S8,PC2,14,17,11,24,1,5,DES加密的一个例子,取16进制明文X：0123456789ABCDEF密钥K为：133457799BBCDFF1去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000应用IP，我们得到：L0=11001100000000001100110011111111L1=R0=11110000101010101111000010101010然后进行16轮加密。最后对L16,R16使用IP-1得到密文：85E813540F0AB405,DES加密的一个例子取16进制明文X：012345678,8.5.2 DES的设计思想和特点,DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。S盒的设计准则：1.S盒不是它输入变量的线性函数2.改变S盒的一个输入位至少要引起两位的输出改变3.对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。,8.5.2 DES的设计思想和特点 DES的核心是S盒，除此,DES的弱点：1）存在一些弱密钥和半弱密钥。2）在DES的明文m，密文C与密钥k之间存在着互补的特性。,DES的弱点：,8.5.3 DES的工作方式（对其他分组密码也适用）,1.电子密文方式（ECB）,8.5.3 DES的工作方式（对其他分组密码也适用）1.,2.密文分组链接方式(CBC),2.密文分组链接方式(CBC),3.密文反馈方式（CFB）,3.密文反馈方式（CFB）,4.输出反馈模式（OFB）,4.输出反馈模式（OFB）,8.5.5 DES的安全性,对DES的批评主要集中在以下几点：DES的密钥长度（56位）可能太小。DES的迭代次数可能太少。S盒中可能有不安全因素。DES的一些关键部分不应当保密。,8.5.5 DES的安全性 对DES的批评主要集中在以下几,8.6 典型的分组密码的分析方法,1.穷尽密钥搜索（强力攻击）2.线性分析方法 3.差分分析方法 4.相关密钥密码分析 5.中间相遇攻击,8.6 典型的分组密码的分析方法 1.穷尽密钥搜索（强力攻,8.6.1 差分分析法,差分分析方法是一种选择明文攻击.基本思想是通过分析特定明文差分对相应密文差分影响来获得可能性最大的密钥。,8.6.1 差分分析法 差分分析方法是一种选择明文攻击.,8.6.1.1 差分分析的理论依据,定义8.6.1 设Sj是一个给定的S盒 是一对长度为6比特的串。称Sj的输入异或是 的输出异或是。定理8.6.1 设Ej和Ej是S盒Sj的两输入，Sj的输出异或是Cjt，记，则密钥比特Jj出现在集合 之中，即。,8.6.1.1 差分分析的理论依据 定义8.6.1 设S,8.6.1.2 差分分析的应用实例,例3 假定有下列的三对明文和密文，这里明文具有确定的异或，并且使用同一个密钥加密。为简单起见，使用16进制表示。,8.6.1.2 差分分析的应用实例 例3 假定有下列的三对,8.6.2 线性密码分析,是一种已知明文攻击 攻击者的目的是希望找到有效的线性表达式 使其成功的概率p1/2，且|p-1/2|最大。,8.6.2 线性密码分析 是一种已知明文攻击,在已知个明密文对时，线性攻击可实施如下：（1）对所有明文P和密文C，T表示（8.5.2.2）左边为0的次数。（2）若TN/2，那么当p1/2时，猜测Kk1kl=0；当p1/2时，猜测Kk1kl=1；当p1/2，猜测Kk1kl=0；当|p-1/2|充分小时，成功的概率为,在已知个明密文对时，线性攻击可实施如下：,8.7 美国高级数据加密标准AES,背景从各方面来看，DES已走到了它生命的尽头。其56比特密钥实在太小，虽然三重DES可以解决密钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。鉴于此，1997年4月15日美国国家标准和技术研究所（NIST）发起征集AES（AESAdvanced Encryption Standard）算法的活动，并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。,8.7 美国高级数据加密标准AES背景,要求该算法应比三重DES快而且至少还要一样的安全，它应当具有128比特分组长度和256比特分组密钥长度（不过必须支持128和192比特的密钥），此外，还应该具有较大的灵活性。,要求,871 AES的评估准则 1）安全性；2）代价，主要包括：许可要求，在各种平台上的计算效率（速度）和内存空间的需求；3）算法和实现特性，主要包括：灵活性、硬件和软件适应性、算法的简单性等。,871 AES的评估准则,1998年8月20日，NIST在第一阶段讨论（AES1）中宣布了由12个国家提出的15个候选算法，1999年3月开始的第二阶段讨论（AES2），1999年8月NIST选出5个算法候选:MARS、RC6、Rijndael、Serpent和Twofish。,1998年8月20日，NIST在第一阶段讨论,872 高级加密标准算法AESRijndael,最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界，由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。,872 高级加密标准算法AESRijndael 最,第8章分组密码课件,Rijndael算法的安全性能有效地抵抗目前已知的攻击方法的攻击。如：部分差分攻击、相关密钥攻击、插值攻击（Interpolation attack）等。对于Rijndael，最有效的攻击还是穷尽密钥搜索攻击。,Rijndael算法的安全性,先进分组密码的特点,可变密钥长度混合操作依赖数据的循环移位依赖于密钥的循环移位依赖密钥的S盒子冗长的密钥调度算法可变的F函数和可变的明文/密文长度可变的循环次数在每次循环中都对两半数据进行操作,先进分组密码的特点可变密钥长度,8.8 欧洲21世纪数据加密标准,NESSIE(New European Schemes for Signature,Integrity,and Encryption)是欧洲的信息社会技术（IST）委员会计划出资33亿欧元支持的一项工程数字签名、完整性和加密新欧洲方案。,8.8 欧洲21世纪数据加密标准 NESSIE(New E,64比特分组密码 MISTY1 128比特分组密码AES和Camellia 256比特分组密码 SHACAL-2,64比特分组密码 MISTY1,8.8.2 Camellia算法简介,1 加密过程,8.8.2 Camellia算法简介 1 加密过程,2 解密过程 3密钥方案,2 解密过程,8.8.2.2 Camellia组件,1 F函数2 FL和FL-1函数,8.8.2.2 Camellia组件1 F函数,3 P函数 4 S盒,3 P函数,8.8.2.3 安全性,高水平的安全性和多平台的有效性。12轮以上不存在线性偏差和差分特征概率大于的差分/线性特征。15轮以上不存在概率大于的差分和线性特征。,8.8.2.3 安全性 高水平的安全性和多平台的有效性。,特点：,Camellia被仔细地设计以便能击退所有已知的密码分析，设计者设想10年到20年安全期限。该密码非常适合软件、硬件实现，应用范围包括从低耗智能卡到高速网络系统。用汇编语言的优化实现在Pentium 800MHz加密速度超过每秒276M比特，比优化的DES实现快多了。另外，一个显著的特征是它的小的硬件设计。硬件设计包括密钥方案，加密和解密，只占用大约1.1万个门，这在目前现存的128比特分组密码中是最小的，极好地迎合了当前无线卡市场需求。,特点：Camellia被仔细地设计以便能击退所有已知的密码分,