第四章分组密码

2020/3/291第四章分组密码一、分组密码概述二、分组密码运行模式三、DES四、AES五、分组密码的分析2020/3/292一、分组密码概述2020/3/293分组密码概述分组密码是许多系统安全的一个重要组成部分。可用于构造拟随机数生成器流密码消息认证码(MAC)和杂凑函数消息认证技术、数据完整性机构、实体认证协议以及单钥数字签字体制的核心组成部分。2020/3/294应用中对于分组码的要求安全性运行速度存储量(程序的长度、数据分组长度、高速缓存大小)实现平台(硬、软件、芯片)运行模式2020/3/295分组密码概述明文序列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)2020/3/296分组密码概述通常取n=m。若nm，则为有数据扩展的分组密码。若nm，则为有数据压缩的分组密码。2020/3/297分组密码设计问题分组密码的设计问题在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文的数字组进行加密变换。2020/3/298分组密码算法应满足的要求分组长度n要足够大：防止明文穷举攻击法奏效。密钥量要足够大：尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。由密钥确定置换的算法要足够复杂：充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击。2020/3/299分组密码算法应满足的要求加密和解密运算简单：易于软件和硬件高速实现。数据扩展：一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能地小。2020/3/2910代换网络代换是输入集A到输出A’上的双射变换：fk：AA＇式中，k是控制输入变量，在密码学中则为密钥。实现代换fk的网络称作代换网络。双射条件保证在给定k下可从密文惟一地恢复出原明文。2020/3/2911代换网络代换fk的集合：S={fkkK}K是密钥空间。如果网络可以实现所有可能的2n!个代换，则称其为全代换网络。全代换网络密钥个数必须满足条件：＃{k}2n!2020/3/2912代换网络密码设计中需要先定义代换集S，而后还需定义解密变换集，即逆代换网络S-1，它以密文y作为输入矢量，其输出为恢复的明文矢量x。要实现全代换网络并不容易。因此实用中常常利用一些简单的基本代换，通过组合实现较复杂的、元素个数较多的代换集。实用密码体制的集合S中的元素个数都远小于2n!。2020/3/2913代换盒(S盒)在密码设计中，可选n=rn0，其中r和n0都为正整数，将设计n个变量的代换网络化为设计r个较小的子代换网络，而每个子代换网络只有n0个输入变量。称每个子代换网络为代换盒(SubstitutionBox)S盒x5x4x3x2x1x0y3y2y1y0DES的S盒2020/3/2914DES的S1-盒的输入和输出关系x5x0x5x4x3x2x1x010101100列号0123456789101112131415行号01441312151183106125907101574142131106121195382411481362111512973105031512824917511214100613(y3,y2,y1,y0)=(0,0,1,0)2020/3/2915扩散和混淆扩散将明文的统计特性散布到密文中。实现的方式是使明文的每一位影响密文中多位的值。2020/3/2916S盒的设计准则迄今为止，有关方面未曾完全公开有关DES的S盒的设计准则。Branstead等曾披露过下述准则：P1S盒的输出都不是其输入的线性或仿射函数。P2改变S盒的一个输入比特，其输出至少有两比特产生变化，即近一半产生变化。P3当S盒的任一输入位保持不变，其它5位输入变化时(共有25=32种情况)，输出数字中的0和1的总数近于相等。这三点使DES的S盒能够实现较好的混淆。2020/3/2917S盒的组合问题:如何将几个S盒组合起来构成一个n值较大的组。将几个S盒的输入端并行，并通过坐标置换(P-盒)将各S盒输出比特次序打乱，再送到下一级各S盒的输入端，起到了Shannon所谓的“扩散”作用。S盒提供非线性变换，将来自上一级不同的S盒的输出进行“混淆”。经过P-盒的扩散作用使1均匀地分散到整个输出矢量中，从而保证了输出密文统计上的均匀性，这就是Shannon的乘积密码的作用。2020/3/2918Feistel网络将nbit明文分成为左右各半、长为n/2bit的段，以L和R表示。然后进行多轮迭代，其第i轮迭代的输出为前轮输出的函数Li=Ri-1Ri=Li-1f(Ri-1,Ki)式中，Ki是第i轮用的子密钥，f是任意密码轮函数。称这种分组密码算法为Feistel网络（FeistelNetwork），它保证加密和解密可采用同一算法实施2020/3/2919迭代分组密码若以一个简单函数f，进行多次迭代，就称其为迭代密码。每次迭代称作一轮(Round)。相应函数f称作轮函数。每一轮输出都是前一轮输出的函数，即y(i)=f[y(i-1),k(i)]，其中k(i)是第i轮迭代用的子密钥，由秘密密钥k通过密钥生成算法产生。子密钥产生器kk(1)k(2)k(r)y(0)=xy(1)y(2)y(r-1)y(r)=y2020/3/2920对合密码(InvolutionCipher)加密函数f(x,k)，实现F2n×F2tF2n的映射。其中，n是分组长，t是密钥长。若对每个密钥取值都有f[f(x,k)，k]=x，即f(x,k)2=I(恒等置换)则称其为对合密码，以fI表示。2020/3/2921I型迭代分组密码以对合密码函数构造的多轮迭代分组密码。E[x,k]=fI[fI[fI[fI[x,k(1)]，k(2)]，k(r-1)]，k(r)]D[y,k]=fI[fI[fI[fI[y,k(r)]，k(r-1)]，k(2)]，k(1)]缺点：对任意偶数轮变换，若对所有i选择k(2i-1)=k(2i)，则加密的变换等价于恒等变换，在实用中需要避免这类密钥选择。2020/3/2922对合置换和II型迭代分组密码对合置换令P是对x的置换，即P：F2nF2n，若对所有xGF(2n)，有P[P[x]]=x，即PP=I(恒等置换)，以PI表示。II型迭代分组密码每轮采用对合密码函数和对合置换级连，即F[x,k]＝PI[fI[x,k]]并选解密子密钥与加密子密钥逆序，则加密解密可用同一器件完成。DES、FEAL和LOKI等都属此类。2020/3/2923III型迭代分组密码群密码：若密钥与明文、密文取自同一空间GF(2n)，且y=xk式中，是群运算，则称其为群密码。显然x可通过k的逆元求得x=yk-1令xk为一群密码，令fI(x,kB)为一对合密码，以F[x,k]＝fI(xkA,kB)为迭代函数，可以III型多轮迭代分组密码。在最后一轮中，另外加了一次群密码运算，用以保证整个加、解密的对合性。2020/3/2924III型迭代分组密码轮函数FFy(1)y(r-1)(a)加密xfI···fIykA(1)kB(1)kA(r)kB(r)kA(r+1)FFyfI···fIx(b)解密kA(r+1))-1kB(r)(kA(r))-1kB(1)(kA)-12020/3/2925IV型迭代分组密码在III型密码的轮函数基础上，再增加一个对合置换PI，构成IV型迭代分组密码的轮函数F[x,k]＝PI[fI[xkA,kB]]2020/3/2926IV型迭代分组密码轮函数Fy(1)y(r-1)FxfIPI···fIPIPIykA(1)kB(1)kA(r)kB(r)kA(r+1)(a)加密FFyfIPI···fIx(b)解密(kA(r+1))-1kB(r)PI[kA(r)]-1PI[kA(2)]-1kB(1)(kA(1))-12020/3/2927二、分组码的运行模式2020/3/2928主要工作模式即使有了安全的分组密码算法，也需要采用适当的工作模式来隐蔽明文的统计特性、数据的格式等，以提高整体的安全性，降低删除、重放、插入和伪造成功的机会。电子码本(ECB)密码反馈链接(CBC)密码反馈(CFB)输出反馈(OFB)。2020/3/2929电码本ECB模式直接利用加密算法分别对分组数据组加密。在给定的密钥下同一明文组总产生同样的密文组。这会暴露明文数据的格式和统计特征。明文数据都有固定的格式，需要以协议的形式定义，重要的数据常常在同一位置上出现，使密码分析者可以对其进行统计分析、重传和代换攻击。2020/3/2930电码本ECB模式xykDESyxkDES-12020/3/2931密码分组链接CBC模式每个明文组xi加密之前，先与反馈至输入端的前一组密文yi-1按位模2求和后，再送至加密算法加密各密文组yi不仅与当前明文组xi有关，而且通过反馈作用还与以前的明文组x1,x2,…,xi-1，有关2020/3/2932密码分组链接CBC模式初始矢量IV(InitialVector)：第一组明文xi加密时尚无反馈密文，为此需要在寄存器中预先置入一个。收发双方必须选用同一IV。实际上，IV的完整性要比其保密性更为重要。在CBC模式下，最好是每发一个消息，都改变IV，比如将其值加一。2020/3/2933密码分组链接CBC模式CBC模式xiyikDESyix’kDES-1++64bit存储64bit存储yi-12020/3/2934填充(Padding)给定加密消息的长度是随机的，按64bit分组时，最后一组消息长度可能不足64bit。可以填充一些数字，通常用最后1字节作为填充指示符（PI）。它所表示的十进制数字就是填充占有的字节数。数据尾部、填充字符和填充指示符一起作为一组进行加密。数据填充PI2020/3/2935CBC的错误传播1.明文有一组中有错，会使以后的密文组都受影响，但经解密后的恢复结果，除原有误的一组外，其后各组明文都正确地恢复。2.若在传送过程中，某组密文组yi出错时，则该组恢复的明文x’i和下一组恢复数据x’i+1出错。再后面的组将不会受yi中错误比特的影响。2020/3/2936k-比特密码反馈CFB模式若待加密消息必须按字符(如电传电报)或按比特处理时，可采用CFB模式。CFB实际上是将加密算法DES作为一个密钥流产生器，当k＝1时就退化为前面讨论的流密码了。CFB与CBC的区别是反馈的密文长度为k，且不是直接与明文相加，而是反馈至密钥产生器。2020/3/2937k-比特密码反馈CFB模式CFB模式++xixiyiyikkXi64bitXi64bitYi64bitYi64bitDESDES-1选最左边k位选最左边k位kbitkbityi-Lyi-2yi-12020/3/2938k-比特密码反馈CFB模式CFB的优点它特别适于用户数据格式的需要。能隐蔽明文数据图样，也能检测出对手对于密文的篡改。CFB的缺点对信道错误较敏感，且会造成错误传播。CFB也需要一个初始矢量，并要和密钥同时进行更换。2020/3/2939输出反馈OFB模式将分组密码算法作为一个密钥流产生器，其输出的k-bit密钥直接反馈至分组密码的输入端，同时这k-bit密钥和输入的k-bit明文段进行对应位模2相加。克服了CBC和CFB的错误传播所带来的问题。对于密文被篡改难以进行检测不具有自同步能力，要求系统要保持严格的同步2020/3/2940输出反馈OFB模式OFB模式+xiyik64bit64bitDES选最左边k位ki64bit寄存器kbitkbit+xiyik64