分组密码课件

第8章分组密码第8章分组密码8．1分组密码概述定义8.1一个分组密码是一种映射： 记为E(X,K)或 称为明文空间，称为密文空间，为密钥空间。8．1分组密码概述定义8.1一个分组密码是一种映射：8．2分组密码的设计原则有关实用密码的两个一般设计原则是Shannon提出的混乱原则和扩散原则。混乱：人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐蔽明文数字统计特性。8．2分组密码的设计原则有关实用密码的两个一般设计原则是软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，比如8、16、32比特等。在软件实现中，按比特置换是难于实现的，因此我们应尽量避免使用它。子块上所进行的一些密码运算应该是一些易于软件实现的运算，最好是用一些标准处理器所具有的一些基本指令，比如加法、乘法和移位等。软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用规则结构，因为密码应有一个标准的组件结构以便其能适应于用超大规模集成电路实现。硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用其他原则：简单性原则：包括规范的简单性和分析的简单性。必须能抗击所有已知的攻击，特别是差分攻击和线性攻击。可扩展性。要求能提供128、192、256比特的可变分组或密钥长。其他原则：8．3分组密码的结构8．3分组密码的结构Feistel网络与SP网络，它们的主要区别在于：SP结构每轮改变整个数据分组，而Feistel密码每轮只改变输入分组的一半。AES和DES分别是这两种结构的代表。Feistel网络（又称Feistel结构）可把任何轮函数转化为一个置换，它是由HorstFeistel在设计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的历史1971IBM，由HorstFeistel领导的密码研究项目组研究出LUCIFER算法。并应用于商业领域。1973美国标准局征求标准，IBM提交结果，在1977年，被选为数据加密标准。8.5典型的分组密码算法——DESDES的历史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.1DES的描述

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,7IP-初始置换58,50,42,34,26,18,PC157,49,41,33,25,17,9,CHalf1,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,DHalf7,62,54,46,38,30,22,14,6,61,53,45,37,29,21,13,5,28,20,12,4PC157,49,41,33,25,17,9,S-box-10123456789abcdefCOL

S[1]

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-1012345DES一轮加密的简图

Li-1Ri-1F+LiRiKiDES一轮加密的简图Li-1Ri-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矩阵，它的元素取0~15的整数。给定长度为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中的比特情况：

52571112659103444512519

941325035364342336018

2871429474622515636139

4311338536255202337306(2)对1<=i<=16，计算

Ci=LSi(Ci-1)

D轮密钥编排KPC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16

…轮密钥编排KPC-1C0D0LS1LS114,17,11,24,1,5,Chalf3,28,15,6,21,10,(bits1-28)23,19,12,4,26,8,16,7,27,20,13,2,41,52,31,37,47,55,Dhalf30,40,51,45,33,48,(bits29-56)44,49,39,56,34,53,46,42,50,36,29,32ChalfprovidesbitstoS1-S4,DhalftoS5-S8

PC214,17,11,24,1,5,DES加密的一个例子

取16进制明文X：0123456789ABCDEF

密钥K为：133457799BBCDFF1

去掉奇偶校验位以二进制形式表示的密钥是00010010011010010101101111001001101101111011011111111000

应用IP，我们得到：

L0=11001100000000001100110011111111

L1=R0=11110000101010101111000010101010

然后进行16轮加密。

最后对L16,R16使用IP-1得到密文：85E813540F0AB405DES加密的一个例子

取16进制明文X：0123456788.5.2DES的设计思想和特点

DES的核心是S盒，除此之外的计算是属线性的。S盒作为该密码体制的非线性组件对安全性至关重要。S盒的设计准则：

1.S盒不是它输入变量的线性函数

2.改变S盒的一个输入位至少要引起两位的输出改变

3.对任何一个S盒，如果固定一个输入比特，其它输入变化时，输出数字中0和1的总数近于相等。8.5.2DES的设计思想和特点DES的核心是S盒，除此DES的弱点：1）存在一些弱密钥和半弱密钥。

2）在DES的明文m，密文C与密钥k之间存在着互补的特性。

DES的弱点：8.5.3DES的工作方式（对其他分组密码也适用）

1.电子密文方式（ECB）8.5.3DES的工作方式（对其他分组密码也适用）1.2.密文分组链接方式(CBC)2.密文分组链接方式(CBC)3.密文反馈方式（CFB）3.密文反馈方式（CFB）4.输出反馈模式（OFB）4.输出反馈模式（OFB）8.5.5DES的安全性对DES的批评主要集中在以下几点：DES的密钥长度（56位）可能太小。DES的迭代次数可能太少。S盒中可能有不安全因素。DES的一些关键部分不应当保密。8.5.5DES的安全性对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设S8.6.1.2差分分析的应用实例例3假定有下列的三对明文和密文，这里明文具有确定的异或，并且使用同一个密钥加密。为简单起见，使用16进制表示。8.6.1.2差分分析的应用实例例3假定有下列的三对8.6.2线性密码分析是一种已知明文攻击攻击者的目的是希望找到有效的线性表达式 使其成功的概率p≠1/2，且|p-1/2|最大。8.6.2线性密码分析是一种已知明文攻击在已知Ｎ个明密文对时，线性攻击可实施如下：（1）对所有明文P和密文C，T表示（8.5.2.2）左边为0的次数。（2）若T>N/2，那么当p>1/2时，猜测K[k1…kl]=0；当p<1/2时，猜测K[k1…kl]=1；否则，当p>1/2时，猜测K[k1…kl]=1；当p<1/2，猜测K[k1…kl]=0；当|p-1/2|充分小时，成功的概率为在已知Ｎ个明密文对时，线性攻击可实施如下：8.7美国高级数据加密标准——AES背景从各方面来看，DES已走到了它生命的尽头。其56比特密钥实在太小，虽然三重DES可以解决密钥长度的问题，但是DES的设计主要针对硬件实现，而今在许多领域，需要用软件方法来实现它，在这种情况下，它的效率相对较低。鉴于此，1997年4月15日美国国家标准和技术研究所（NIST）发起征集AES（AES—AdvancedEncryptionStandard）算法的活动，并成立了AES工作组。目的是为了确定一个非保密的、公开披露的、全球免费使用的加密算法，用于保护下一世纪政府的敏感信息。也希望能够成为保密和非保密部门公用的数据加密标准（DES）。8.7美国高级数据加密标准——AES背景要求该算法应比三重DES快而且至少还要一样的安全，它应当具有128比特分组长度和256比特分组密钥长度（不过必须支持128和192比特的密钥），此外，还应该具有较大的灵活性。要求8．7．1AES的评估准则

1）安全性；2）代价，主要包括：许可要求，在各种平台上的计算效率（速度）和内存空间的需求；3）算法和实现特性，主要包括：灵活性、硬件和软件适应性、算法的简单性等。8．7．1AES的评估准则1998年8月20日，NIST在第一阶段讨论（AES1）中宣布了由12个国家提出的15个候选算法，1999年3月开始的第二阶段讨论（AES2），1999年8月NIST选出5个算法候选:MARS、RC6、Rijndael、Serpent和Twofish。1998年8月20日，NIST在第一阶段讨论8．7．2高级加密标准算法AES——Rijndael最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界，由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。8．7．2高级加密标准算法AES——Rijndael最第8章分组密码课件Rijndael算法的安全性 能有效地抵抗目前已知的攻击方法的攻击。如：部分差分攻击、相关密钥攻击、插值攻击（Interpolationattack）等。对于Rijndael，最有效的攻击还是穷尽密钥搜索攻击。

Rijndael算法的安全性先进分组密码的特点可变密钥长度混合操作依赖数据的循环移位依赖于密钥的循环移位依赖