现代密码学第4章1：概述

1分组密码《现代密码学》第4章(1)2本章主要内容1、分组密码概述2、数据加密标准DES算法3、分组密码的运行模式4、差分密码分析与线性密码分析5、IDEA算法6、AES算法——Rijndael3在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（MAC）和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。第1节：分组密码概述4实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择。1分组密码概述5是一种单钥或对称算法通信实体双方使用相同的密钥加密和解密现代分组密码（由乘积密码构成）包括DES,Blowfish,IDEA,LOKI,RC5,Rijndael(AES)及其它一些算法1分组密码概述6在分组密码中，消息被分成许多块，每块都要被加密类似于许多字符被替换-（64-bitsormore）许多现代分组密码具有下列形式：1分组密码概述71分组密码概述8分组密码理论基础理想的方法是使用尽可能大的替换模块，但不实际，因为对每个64bit的模块，将需要264个实体的替换表，因此使用一些小的模块代替。使用乘积密码的思想这种概念由ShannonandFeistel提出9分组密码的设计原理可变密钥长度混合操作依赖数据的循环移位依赖于密钥的循环移位依赖密钥的S盒子冗长的密钥调度算法可变的F函数和可变的明文/密文长度可变的循环次数在每次循环中都对两半数据进行操作10Shannons保密系统理论ClaudeShannon对现代密码的重要工作：CEShannon,CommunicationTheoryofSecrecySystems,BellSystemTechnicalJournal,Vol28,Oct1949,pp656-715CEShannon,PredictionandEntropyofprintedEnglish,BellSystemTechnicalJournal,Vol30,Jan1951,pp50-64在上述文章中，提出了下列概念:“熵”的概念语言冗余度破译密码需要多少信息量定义了”计算安全”与”无条件安全”11即如果通过填加一些英语字母加密英文内容，是不安全的。因为英语有80%的冗余度，英语密文如果有60%的冗余度，就可以破解。Shannons保密系统理论12分组密码是将明文消息编码表示后的数字序列x0,x1,…,xi,…划分成长为n的组x=(x0,x1,…,xn-1)，各组（长为n的矢量）分别在密钥k=(k0,k1,…,kt-1)控制下变换成等长的输出数字序列y=(y0,y1,…,ym-1)（长为m的矢量），其加密函数E：Vn×K→Vm，Vn和Vm分别是n维和m维矢量空间，K为密钥空间，如图1所示。1分组密码概述13明文序列x1,x2,…,xi,…加密函数E:Vn×KVn这种密码实质上是字长为m的数字序列的代换密码。解密算法加密算法密钥k=(k0,k1,…,kt-1)密钥k=(k0,k1,…,kt-1)明文x=(x0,x1,…,xm-1)明文x=(x0,x1,…,xm-1)密文x=(y0,y1,…,ym-1)图1分组密码框图1分组密码概述14它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为n的数字序列的代换密码。1分组密码概述15通常取m=n。若mn，则为有数据扩展的分组密码；若mn，则为有数据压缩的分组密码。在二元情况下，x和y均为二元数字序列，它们的每个分量xi，yi∈GF(2)。本节将主要讨论二元情况。设计的算法应满足下述要求：1分组密码概述16分组密码是许多系统安全的一个重要组成部分。可用于构造拟随机数生成器流密码消息认证码(MAC)和杂凑函数消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分。分组密码概述17分组密码与序列密码比较，主要区别是在加密方式上：序列密码：kKGk=k0k1k2012mmm))()((001122kmkmkm分组密码概述18大多数实用分组密码的明文信号取自于F2、且满足：n=n’（即明文没有被扩展）。考察的一个分组密码体制，设K为密钥空间，n为分组长度，那么加密变换空间为：E={Ek|Ek:是一一映射,kK}。若将中点与其所对应的二进制数不加区别，则每个Ek(kK)可等同一个2n-置换。nnFF22),,,(110nxxxXnF22110)(ˆnxxxX分组密码概述19线性部分EnS2记为由所有2n-置换构成的所谓2n次对称群，那么一个好的分组密码的加密变换空间在中的位置应如下图所示：nS2nS2分组密码概述20应用中对于分组码的要求安全性运行速度存储量(程序的长度、数据分组长度、高速缓存大小)实现平台(硬、软件、芯片)运行模式21分组密码设计问题分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。22①分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求232×64b=215MB存贮，故采用穷举攻击是不现实的。1分组密码算法设计要求23②密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。DES采用56比特密钥，看来太短了，IDEA采用128比特密钥，据估计，在今后30～40年内采用80比特密钥是足够安全的。1分组密码算法设计要求24③由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。1分组密码算法设计要求25④加密和解密运算简单，易于软件和硬件高速实现。如将分组n化分为子段，每段长为8、16或者32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用以软件难于实现的逐比特置换。1分组密码算法设计要求26为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现。此外，差错传播和数据扩展要尽可能地小。1分组密码算法设计要求27⑤数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。⑥差错传播尽可能地小。1分组密码算法设计要求28软件实现的设计原则：使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，比如8、16或32比特等；在软件实现中，按比特操作（如置换）是难于实现的，因此应该尽量避免它。子块上所进行的密码运算应该是一些易于软件实现的运算，最好是用一些标准处理器所具有的那些基本指令，比如加法、乘法和移位等。1分组密码软件设计原则29加密和解密应具有相似性（最好只是在密钥的使用方式上存在不同，其余皆同）以便可以用同样的器件来实现。尽量使用规则结构，且应符合国际的统一标准，以便适合于用超大规模集成电路来实现。值得注意的是：分组密码常常以乘积密码的方式来设计。由合理选择的许多子密码（相继使用）构成的乘积密码既可实现良好的混乱、又可实现良好的扩散。1分组密码硬件设计原则30要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。下面介绍设计分组密码时的一些常用方法。1分组密码算法设计要求31如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。（1）代换1分组密码算法设计方法32图2表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。加密映射和解密映射可由代换表来定义，如表3.1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见33页表3.1）（1）代换33在Shannon1949的文章中，介绍了替换-置换网络的思想(S-P)networks这种思想形成了现代密码的基础S-Pnetwork替换-置换乘积密码的现代形式S-Pnetworks是基于下列两种最基本的密码运算（前面介绍过）：替换（Substitution）置换（Permutation）（1）代换34图2代换结构（1）代换35但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如n=4，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只是因为分组长度太小。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。（1）代换36然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表3.1为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要64比特。一般地，对n比特的代换结构，密钥的大小是n×2n比特。如对64比特的分组，密钥大小应是64×264=270≈1021比特，因此难以处理。（1）代换37实际中常将n分成较小的段，例如可选n=r·n0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大，称每个子代换为代换盒，简称为S盒。例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实现，每个S盒的输入端数仅为6比特，输出端数仅为4比特。（1）代换38代换网络代换是输入集A到输出A’上的双射变换：fk：AA＇式中，k是控制输入变量，在密码学中则为密钥。实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。39代换fk的集合：S={fkkK}K是密钥空间。如果网络可以实现所有可能的2n!个代换，则称其为全代换网络。全代换网络密钥个数必须满足条件：＃{k}2n!代换网络40密码设计中需要先定义代换集S，而后还需定义解密变换集，即逆代换网络S-1，它以密文y作为输入矢量，其输出为恢复的明文矢量x。要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密码体制的集合S中的元素个数都远小于2n!。代换网络41例:n=4代换结构0123456789101112131415012345678910111213141542明文密文明文密文00001101000101010010000100110110010010010101111101100010011100111000101010011000101010111011111011000111110101001110