分组密码体制

本科生学位课：现代密码学第三章分组密码体制主讲教师：董庆宽研究方向：密码学与信息安全Email：[e-mail]2/1493.1分组密码概述3.2数据加密标准DES3.3差分密码分析和线性密码分析3.4分组密码的运行模式3.5IDEA3.6AES－Rijndael本章提要3/1493.1分组密码概述分组密码(BlockCipher)：将明文消息分组，逐组加密；对称密码算法，属于代换密码将明文消息编码表示后的数字序列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为密钥空间，如图所示。加密算法明文分组密码框图解密算法明文x=(x0,x1,...,xn-1)x=(x0,x1,...,xn-1)y=(y0,y1,...,ym-1)密文密钥k=(k0,k1,...,kt-1)密钥k=(k0,k1,...,kt-1)4/149与流密码不同之处：(1)分组加密。在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。(2)无记忆性。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为m的数字序列的代换密码。算法的输入长度和输出长度通常取m=n(用于加密)若mn，则为有数据扩展的分组密码(用于认证)若mn，则为有数据压缩的分组密码(用于认证)在二元情况下，明文x和密文y均为二元数字序列它们的每个分量xi，yjGF(2)。本章将主要讨论二元情况。也是当前分组密码研究的主流。5/149分组密码的作用加密(适合软硬件实现)构成其它密码功能的基本模块1.构造伪随机数生成器。用于产生性能良好的随机数适合产生少量随机数2.构造流密码。速度比移位寄存器(适用硬件)慢得多，但软件实现方便采用适当的分组链接模式(CFB或OFB)可实现3.消息认证和数据完整性保护通过用于构造消息认证码(MAC)和杂凑函数等来实现6/149分组密码算法设计的研究发展概况（一）古典密码学阶段(1949年前)的分组密码的研究1）密码学的研究主要用于军用和专门的机构2）算法保密，出现了代换和置换的方法3）产生了乘积密码的思想指顺序地执行两个或多个基本密码系统，使最后结果的密码强度高于每个基本密码系统的强度，多轮加密(3.1.3节1段)4）基尔霍夫准则：早在1883年荷兰密码学家A.Kerckhoffs就在其《军事密码学》中提出如下密码设计准则：密码系统应该是计算安全的；密钥由通信双方事先约定好，并根据一定协议进行更换；密码系统应该易于使用；密码系统应该精确而有效；除了密钥，密码系统的所有细节都为对手所知。基尔霍夫还提出了一次一密的密码设计方法，直接促进了流密码研究7/149（二）近代密码学阶段(1949-1975)-分组密码的酝酿期1）计算机技术的发展，开始了密码学面向商业应用的设计2）Shannon的工作：1949年，C.E.Shannon(1916~2002)建立了保密系统的通信理论，50-70年代Shannon的工作起着决定性的指导作用。对密码理论的贡献主要有两点其一，用信息论刻划了密码学中的安全性提出了语言冗余度和“熵”的概念，论述了破译密码需要多少信息量定义了”计算安全”与”无条件安全”；前者与破译密码的价值有效性和时间有效性有关。后者是指无论破译者有多少密文也无法解出对应的明文，即使解出也无法验证结果的正确性(One-Time-Pad)其二，提出了密码设计中的扩散准则和混淆准则在一次一密无法实现的情况下，这两个准则是设计密码体制的最基本准则。Shannon的思想今天仍然是设计密码体制极其重要的指导准则3）Smith关于Lucifer密码的设计研究4）Feistel网络的密码结构8/149（三）现代密码学阶段－走向成熟1）密码学由专门应用转向商业应用美国数据加密标准DES(DataEncryptionStandard)是最重大的标志。它和公钥密码体制的提出是现代密码学的开端和密码学发展史上两个重要里程碑。是近代密码学研究重要结晶。2）DES加密算法的公开及其在商用数据加密中的广泛应用，激发了人们对密码学的研究兴趣，密码学进入了一个新的时期3）现代分组密码研究的发展早期的研究基本上是围绕DES进行的，推出了一些类似的算法，例如：LOKI，FEAL，GOST等。9/149进入20世纪90年代，人们对DES算法研究更加深入，特别是差分密码分析（differentialcryptanalysis）和线性密码分析（linearcryptanalysis）的提出，迫使人们不得不研究新的密码结构。IDEA密码打破了DES类密码的垄断局面随后出现了SQUARE、SHARK、SAFER-64等采用了结构非常清晰的代替—置换（SP）网络，从理论上给出了最大差分特征概率和最佳线性逼近优势的界，证明了密码对差分密码分析和线性密码分析的安全性。1997~2000年间美国高级加密标准AES的征集活动以及2000~2003年间欧洲NESSIE计划的实施，再次掀起了密码研究的新高潮，15个AES候选算法和24个NESSIE终选算法反映了当前密码设计的水平，也可以说是近几年研究成果的一个汇总。10/149目前对分组密码安全的讨论主要包括差分密码分析、线性密码分析和强力攻击等1990年Biham和Shamir差分密码分析方法以及1993年MitsuruMatsui线性密码分析方法的问世，都极大丰富了密码学的内容从理论上讲，差分密码分析和线性密码分析是目前攻击分组密码的最有效的方法，而从实际上说，强力攻击是攻击分组密码最可靠的方法。11/149分组密码领域有待继续研究和完善的理论和实际问题如何设计可证明安全的密码算法；如何加强现有算法及其工作模式的安全性；如何测试密码算法的安全性；如何设计安全的密码组件，例如S-盒、扩散层及密钥扩散算法等。分组密码没有非常有效的数学分析工具需要实践检验参考资料：《对称密码学》胡予濮，张玉清等著《密码分析学》冯登国12/149分组密码算法设计满足的要求：I.应用要求：实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有：运行速度存储量（程序的长度、数据分组长度、高速缓存大小）实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之间进行适当的折中选择13/149II.算法设计的要求分组密码设计在于找到一种算法，能在密钥控制下从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文数字组进行加密变换①分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。(明文相关性和统计特性)DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求232×64b=215MB＝32GB存贮，故现在采用穷举攻击已经可以实现(时间存储攻击)生日攻击：(请参考6.2.3节)随机选取n个人，至少有两个人生日相同的概率为P＝1－365×364×…×(365－n+1)/365n当n＝64时p＝0.997近乎于114/149②密钥量要足够大（即置换子集中的元素足够多）尽可能消除弱密钥并使所有密钥同等地好，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。DES采用56比特密钥，太短IDEA采用128比特密钥，够用据估计，在今后30～40年内采用80比特密钥是足够安全的③由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击如差分攻击和线性攻击有高的非线性阶数，实现复杂的密码变换使对手破译时除了用穷举法外，无其它捷径可循15/149④加密和解密运算简单，易于软件和硬件高速实现使用子块和简单的运算如将分组n划分为子段，每段长为8、16或者32在软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避免用软件难于实现的逐比特置换加解密算法应具有相似性为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现多轮迭代是乘积密码的特例，指同一基本加密结构的多次执行若以一个简单函数f，进行多次迭代，就称其为迭代密码。每次迭代称作一轮(Round)。相应函数f称作轮函数。每一轮输出都是前一轮输出的函数，即y(i)=f[y(i-1),k(i)]，其中k(i)是第i轮迭代用的子密钥，由秘密密钥k通过密钥生成算法产生。16/149⑤数据扩展一般无数据扩展，在采用同态置换和随机化加密技术时(如公钥密码)可引入数据扩展。⑥差错传播尽可能地小1比特的传输错误不会影响更多比特的正确解密要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法而后进行严格的安全性检验并且要易于实现。下面介绍设计分组密码时的一些常用方法。17/1493.1.1代换为使加密运算可逆(使解密运算可行)，明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换(与古典密码中代换表同义)即代换是输入集A到输出集合A上的双射变换：fk：AA式中，k是控制输入变量，即密钥密钥k决定了使用哪一个代换，是代换函数的一部分双射条件保证在给定k下可从密文惟一恢复明文如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值，则不同可逆变换的个数有2n!个。（2n的全排列）18/149代换网络：实现代换fk的运算网络称作代换网络(由多个运算组件组成)。常利用一些简单的基本代换，通过组合，实现较复杂的、元素个数较多的代换集，即代换网络19/149代换结构下图表示n=4的代换密码的一般结构4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。共有24！=16!种可能置换012345678910111213141501234567891011121314154比特输入4比特输出20/149加密映射和解密映射也可由代换表来定义，这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。表3-1对应的代换表明文密文明文密文密文明文密文明文0000111000010100001011010011000101000010010111110110101101111000100000111001101010100110101111001100010111011001111000001111011100001110000100110010010000111000010000010101110001101010011111111000011110011101101010011011011011001011110100101110000011110101加密代换解密代换21/149这种代换结构中分组长度不宜太小如果分组长度太小，如n=4，系统则等价于古典的代换密码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只是因为分组长度太小。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。22/149但分组长度很大的可逆代换结构是不实际的，会使