3 数据加密标准

现代密码学概论7/29/202610:55AM1主讲人：潘森杉第3讲数据加密标准

·有关实用密码的两个一般设计原则是Shannon提出的混淆原则和扩散原则。混淆：人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的。扩散：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也应影响密文的许多位数字以便隐蔽明文数字统计特性。软硬件实现的设计原则：加密和解密可用同样的器件来实现。尽量使用规则结构，因为密码应有一个标准的组件结构以便其能适应于用超大规模集成电路实现。大多数分组密码都是乘积密码，通常伴随一系列置换与代换操作，常见的乘积密码是迭代密码。典型的迭代密码：明确定义一个轮函数和一个密钥编排方案，一个明文的加密将通过Nr轮类似过程。K——确定长度的随机二元密钥用K生成Nr个轮密钥(也叫子密钥)K1,K2,…,KNr，其列表(K1,K2,…,KNr)即为密钥编排方案，它是由K经过一个固定的、公开的算法生成。轮函数g以轮密钥Kr和当前状态wr-1作为它的两个输入，下一个状态定义为wr，初态w0被定义成明文x，密文y定义为经过Nr轮后的状态，即：加密：

w0

←

x

初态w1

←g(w0,K1)第1轮…………wNr-1

←g(wNr-2,KNr-1)第Nr-1轮wNr

←g(wNr-1,KNr)第Nr轮

y

←wNr

为解密，g在第二个变量固定的条件下必须是单射，即等价于存在g-1，g-1(g(w,k),k)=w解密：

wNr

←

y

wNr-1

←g-1(wNr,KNr)

………w1

←g(w2,K2)w0

←g(w1,K1)

x

←w0

线性密码分析假设能在明文比特子集与最后一轮即将进行代换的输入状态比特子集之间找到一个概率线性关系。即存在一个比特子集，使其中元素的异或表现出非随机的分布（如该异或值以偏离1/2的概率取0）攻击者有用同一未知K加密的明-密文对对每个明密文对，用所有可能的候选密钥对最后一轮解密y，对每个候选密钥，计算包含在线性关系式中的相关状态比特的异或值，然后确定上述的线性关系是否成立，若成立，相应计数器上加1，最后，计数频率离明密文对数的一半最远的候选密钥含有那些比特的正确值。明文密文分组长为n，密钥分组长为m，分别记为：P[1],…,P[n];C[1],…,C[n];K[1],…,K[m]定义A[i,j,…,k]=A[i]⊕A[j]⊕…⊕A[k]线性密码分析的目标：找出如下形式的有效线性方程：P[i1,i2,…,ia]⊕C[j1,j2,…,jb]=K[k1,k2,…,kc]如果方程成立概率p≠1/2，则称为有效的线性逼近如果|p-1/2|是最大的，则称为最有效的线性逼近N—明文数，T是使得方程左边为0的明文数T>N/2：K[k1,k2,…,kc]=0(p>1/2)or1(p<1/2)T<N/2：K[k1,k2,…,kc]=0(p<1/2)or1(p>1/2)从而可得关于密钥比特的一个线性方程，对不同的明密文重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。差分密码分析同线性密码分析的主要区别：包含将两个输入的异或与其相对应的两个输出的异或相比较。选择明文攻击：假设攻击者有大量的四元组(x,x*,y,y*)，x’=x⊕x*为固定值对每个四元组，应用所有可能的候选密钥对该密码的最后一轮进行解密；对每一个候选密钥，计算某些状态比特的值，并确定它们的异或是否有一个确定的值（即对给定输入异或值的最可能取的值）；如果是，就把对应的计数器加1；最后，希望具有最高频率的候选密钥含有真正密钥那些比特的取值。差分密码分析最早由Murphy发表于1990年。是一种强有力的密码分析方法，但它对DES并不十分凑效。根据设计DES的IBM小组成员所述，在1974年就知道了差分分析，设计S盒和置换P时充分考虑了抗差分攻击。针对于DES的线性密码分析由Matsui发表于1993年，需要243个明文就可以找出DES的密钥，而差分分析需247个选择明文。迄今为止，几乎没有其他研究组做工作来验证线性分析方法。数据加密标准(DES)DES概述1977年1月，美国国家标准局公布了DES，它是用于非保密数据(与国家安全无关的信息)的算法。该算法在世界范围内得到广泛应用，一个主要的例子就是银行的资金转帐它本来被批准用5年，此后经住了时间的考验，又批准了3个5年使用期是第一个并且也是最重要的现代对称加密算法。1011/10/1510:571111/10/1510:57DES介绍DES是分组密码，其中的消息被分成定长的数据分组，每一分组称为M或者C中的一个消息在DES中，M=C={0,1}64,K={0,1}56DES的运算可描述为三步：步骤一、将输入分组进行固定的“初始置换”IP：其中，L0,R0分别称为左右半分组，都是32bit。IP是固定的函数，是公开的，输入密钥不是它的参数，或者说，这个初始置换无明显的密码意义1211/10/1510:57步骤二、将下面的运算迭代16轮，i=1,…,16其中，ki成为轮密钥，是56bit输入密钥的一个48bit的子串，f称为“S盒函数(S-box)”，S表示代换，上述运算的特点是交换左右两半分组，就是说，一轮的左半分组输入是上一轮的右半分组输出，其目的是获得很大程度的信息扩散，本质是获得Shannon的混合特性。“S盒函数”f通过两个子运算实现了下面两个性质：消息分布所需的随机性：ki与Ri-1逐比特相加获得消息分布所需的非线性：S盒中包含8个代换盒(代换密码一般是非线性的仿射和移位是线性中的子类）11/10/1510:5713步骤三、将16轮迭代后得到的结果(L16,R16)输入到IP的逆置换来消除初始置换的影响，这一步的输出就是DES的输出，可表示为：说明：加密和解密都用这三个步骤，仅有的不同就是如果加密算法中使用的密钥是：那么解密中使用的轮密钥就应当是：这种排列轮密钥的方法成为“密钥表”，记为：思考题：请证明DES密码能满足Dk(Ek(m))=mIP－1的输入使得16轮迭代的两个半分组又进行了一次交换Feistel型密码Li=Ri-1Ri=Li-1⊕f(Ri-1,Ki)可逆：Li-1=Ri⊕f(Li,Ki)=(Li-1⊕f(Ri-1,Ki))⊕f(Li,Ki)Ri-1=LiLi-1Ri-1LiRifKiDES的结构DES描述图157/29/202610:55AM初始置换IP

在迭代运算之前，需要将输入的64位明文进行初始置换IP。进行初始置换后，明文的次序被打乱，如原来放在第58位的数据置换后放在第1位。58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157轮函数f(A,J)的描述

A为32比特串，J为48比特串，输出f(A,J)为32比特串A根据一个固定扩展函数E扩展成一个长为48比特串E(A)计算E(A)⊕J，并将所得结果分成8个长为6的比特串，记为B=B1B2…B8使用8个S盒S1,…,S8.每个Si为6进4出，用4×16矩阵描述。对Bj=b1…b6，计算Sj(Bj):b1b6对应Sj

的行，b2b3b4b5对应Sj的列，对应二进制表示Cj=Sj(Bj),将长为32比特的C=C1C2…C8通过固定置换P：

P(C)=f(A,J)轮函数加密流程图187/29/202610:55AM扩展置换

扩展置换将前一轮迭代的结果Ri−1作为输入，根据扩展函数E将32位的比特输入扩展为48位。

扩展函数E将32位的明文每4位为分成一组，共有8组,每个分组由4位扩展为6位。扩展方法为：每个分组的4位作为6位输出分组的中间4位，6位输出分组中的第1位和第6位分别由相邻的两个4位小分组的最外面两位扩散进入到本分组产生，其中第1个小分组的左侧相邻分组为最后一个小分组。将8个小分组扩展后的结果列成一张表，就构成了E置换的扩展置换表：3212345456789891011121312131415161716171819202120212223242524252627282928293031321012345678910111213141501231441312151183106125907015741421311061211954841148136211151297310501512824917511314100613S101231518146113497213120510313471528141201106911501471110413158126932151381013154211671205149S201231009146315511312711428137093461028514121115113649815301112125101471101306987415143115212S30123

7131430691012851112415138115615034721211014910690121171315131452843150610113894511127214S4S盒0123

2124171011685315130149141121247131501510398642111101378159125630141181271142136150910453S501231211015926801334147511101542712956113140113891415528123704101131164321295151011141760813S60123

4112141508133129751061130117491101435122158614111312371410156805926111381410795015142312S701231328461511110931450127115138103741256110149271141912142061013153582114741081315129035611S8S盒P盒变换

P盒变换是将S盒输出的32位比特串根据固定的置换P（也称P盒）置换到相应的位置。1672021291228171152326518311028241432273919133062211425密钥扩展方案给定一个64比特密钥K，删除8个校验比特(8,16,24,32,40,48,56,64)，并利用一个固定的置换PC-1置换K的剩下56比特，记PC-1(K)=C0D0,对每个i(0≤i≤16):Ci=LSi(Ci-1)Di=LSi(Di-1)Ki=PC-2(CiDi)其中：如果i＝1，2，9，16，LSi表示循环左移1位，否则LSi表示循环左移2位

PC-2是另一个置换(并非置换，56选48)PC-1置换表57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124PC-2置换表1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932DES子密钥的产生

KPC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16…DES子密钥的产生

KPC-1C0D0LS1LS1C1D1LS2LS2LS16LS16C16D16PC-2PC-2K1K16…DES的核心作用：在S盒函数F里，正是F实现了明文消息在密文消息空间上的随机非线性分布差分攻击(DifferentialCryptanalysis),通过利用两个明文消息间的线性差分和两个密文消息间的线性差分来攻击密码。Feistel密码(DES)中的S盒不必是可逆的，对任意的f(Ri-1,ki)都可以运行加密解密。2711/10/1510:57DES的分析对DES的S盒、迭代次数、密钥长度等设计准则的争议

DES的S盒、迭代次数、密钥长度都被设计成固定的参数，而且S盒的设计标准是保密的，至今未公布。人们担心如果在算法中嵌入了陷门，可使NSA(NationalSecurityAgency)使用一个简单的方法就能对消息解密。

1976年，NSA公布了6条S盒的设计准则。但是，S盒的设计准则还没有完全公开。DES存在着一些弱密钥

生成子密钥时，将种子密钥（去除了奇偶校验位后）分成两个部分，如果某个密钥K，使得这两个部分的每一部分的所有位都是0或1，这时由它产生的16个子密钥相同，由此：

DESK(x)=DESK-1(x)即由密钥K确定的加密变换和解密变换一致，这时我们称密钥K为一个弱密钥。（至少4个）

DES中还存在半弱密钥这些密钥把明文加密成相同的密文，即存在一个不同于K的密钥K’使DESK

(m)＝DESK’(m)。（至少12个）相对于总数为256

＝72057594037927936的密钥空间，弱密钥与半弱密钥所占的比例实在太小了。如果随机地选择密钥，那么选中这些弱密钥中的一个的概率可以忽略不计。而且可以在密钥产生进行检查，保证不使用弱密钥作为DES的密钥。DES的56位密钥无法抵抗穷举工具

DES的密钥只有56位，密钥量仅为256≈1017就目前的计算设备的计算能力而言，DES不能抵抗对密钥的穷举攻击。1998,耗资250000美元密钥搜索机，56小时找到DES的密钥1999，100000台计算机，22小时15分找到DES的密钥多重DES

多重DES就是使用多个密钥利用DES算法对明文进行多次加密，使用多重DES可以增加密钥量，从而大大提高抵抗密钥的穷索攻击的能力。EK1DK2

EK3PCDK3EK2DK1CP三重DES加密与解密过程计算机的运算速度也在不断攀升，2016年，国家并行计算机工程技术研究中心研制的“神威·太湖之光”(见右图)已取代了国防科学技术大学研制的“天河二号”，成为全球最快超级计算机，其浮点运算速度达每秒9.3亿亿次。分组密码的工作模式3211/10/1510:57分组密码将消息作为数据分组来处理，通常消息(一个消息串)的长度大于分组密码的消息分组长度，长的消息被分成一系列连续排列的消息分组，密码一次处理一个分组，因此确定密码算法后，分组加密可以有多个工作模式。1977年DES颁布。1980年底美国针对DES的应用制定了四种基本工作模式：电码本模式（ECB模式,ElectronicCodeBook）密码分组链接模式（CBC模式,CipherBlockChaining）密码反馈模式（CFB模式,CipherFeedback）输出反馈模式（OFB模式,OutputFeedback）分组密码的工作模式还有计数模式（CTR模式,Counter）计数密码分组链接模式（CCM模式）电码本模式(ECB,ElectronicCodeBook)在ECB模式下，直接用分组密码算法来进行消息的加密和解密。一个明文分组被加密成一个密文分组，相同的明文分组加密成相同的密文分组。

加密：yi＝Ek(xi)i＝1,2,…,

yi-1

yi

yi+1EkEkEkxi-1xixi+1解密：xi＝Dk(yi)i＝1,2,…,yi-1yiyi+1DkDkDkxi-1xixi+1ECB模式的优点是可以并行运算，速度快，易于标准化。ECB模式的缺点是分组加密不能隐蔽数据模式，即相同的明文蕴含着相同的密文组；不能抵抗分组重放、插入、删除等攻击。用途：传送短数据（如一个加密密钥）密码分组链接模式(CBC,cipherblockchaining)在该模式下，每个明文块xi首先与前一个密文块yi－1作异或操作，然后再用密钥k进行加密。每一分组的加密都依赖于前面所有的分组。在处理第一个分组时要与一个初始向量（IV）进行异或运算。IV不需要保密，它可以明文的形式与密文一起传送。加密：y1＝Ek(x1

IV)，yi＝Ek(xi

yi－1)i＝2,3,4,…,Nx1Eky1x2Eky2xnEkynIV....解密：m1＝Dk(y1)

IV，xi＝Dk(yi)

yi－1i＝2,3,4,…,Ny1Dkx1y2Dkx2ynDkxnIV....CBC模式的优点：引入了随机的初始向量，如果加密算法E是伪随机的，则输出具有一定的随机性，避免了ECB的缺点，隐蔽了明文的数据模式，在一定程度上能防止数据篡改。可用于产生消息认证码。CBC模式的缺点： 如果明文分组中的一位出错，将影响该分组的密文及其以后的所有密文分组。如果密文分组中的一位出现错误，将会影响到错误分组后的第二个分组的明文，其它的分组不受影响； 但是如果密文序列中丢失1位，那么所有