复旦信息安全课件第3章现代加密算法

第3章现代加密算法分组密码的基本概念、设计原则和设计方法、运行模式等（美国）商用数据加密标准即DES算法、SAFER算法和本世纪替代DES算法的Rijndael算法公钥密码体制以及重要的加密算法3.1分组密码分组密码是将明文序列分成长为L的组m=(m0m1…mL-1)，各组分别在密钥k=(k0,k1,…ks)控制下变换成等长的输出序列即密文c=(c0c1…cn-1)。在相同密钥下，分组密码对长为L的输入明文组所进行的变换是等同的，只需研究对任一组明文的变换规则。分组密码实质上是多字母代换密码的推广，所采用的L较大。3.1.1分组密码设计原则在分组密码中，明密文都采用{0,1}序列。把长为L的{0,1}字符串m和c表示成小于2L的整数，即：m=(m0m1…mL-1)102Liiim=‖m‖c=(c0c1…cL-1)102Liiic=‖c‖分组密码就是将ǁmǁ{0,1,…,2L-1}映射为ǁcǁ{0,1,…,2L-1}，即是{0,1,…,2L-1}到自身的置换。置换的选择由密钥k决定。所有可能的置换构成一个对称群S(2L)其中元素个数或密钥数为2L！。实际使用中的分组密码所用的置换都是上述置换集中的一个很小的子集。设计分组密码的关键是设法找到一种算法，使得在密钥控制下，能从一个足够大且足够好的置换子集中，简单而迅速地选出一个置换，用来对当前输入的明文数字组进行加密变换。分组密码的设计应满足如下要求：1)分组长度L应足够大，使分组代换字母表中的元素个数2L足够大，防止明文穷举攻击。例如若采用L=64的分组，在生日攻击下用232分组密文成功概率为0.5，并需要232×64bit=215MB存储，因此穷举攻击实际上是不可行的2)密钥量要足够大，即置换子集中的元素足够多，尽可能消除弱密钥并使所有密钥同样好。同时为了便于密钥管理，密3)由密钥确定的置换算法要足够复杂，实现明文与密文的扩散和混乱，没有简单的关系可循，并能抗差分攻击、线性攻击等已知的密码攻击方法。4)设计的算法采用规则的模块结构，加密和解密运算简单，便于软件和硬件的实现。在主要以软件实现为手段的密码算法中，应选用以标准处理器进行运算的基本运算，而避免采用如逐位置换那种较难用软件实现的运算。在主要以硬件实现为手段的密码算法中，应使得加密和解密过程之间的差别仅在由密钥所生成的密钥表的不同，使得加密和解密可以用同一器件实现在实际设计密码算法时，要实现上述各要求也不容易。为了便于实现，通常可将较简单且易实现的密码系统进行组合，构成比较复杂、密钥量大的密码系统。Shannon提出了设计分组密码采用方法的建议：(1)“概率加权和”方法，以一定的概率随机从一些简单密码系统中选择一个用于加密当前明文。设选用的密码系统有r个，用E1,E2,…,En表示，被选用的概率是p1,p2,…,pr，其中11riip。概率和系统可表示成C=p1E1+p2E2+…+prEr。(2)“乘积”方法，用两个密码算法E1和E2对明文进行加密。先用E1对明文进行加密，然后再用E2对所得结果加密。(3)采用扩散和混乱方法。所谓扩散就是使每位明文和密钥的影响散布到尽可能多的输出密文中，以隐蔽明文的统计特性，防止对密钥逐段破译混乱就是使作用于明文的密钥与密文之间的关系复杂化，使明文与密文之间、密文与密钥之间的统计相关性极小化，以便抗统计分析攻击。3.1.2分组密码中的常用函数和S盒设计在分组密码中，通常采用一些比较简单的函数，通过多次乘积、迭代强化为一个复杂的密码体制。1.常用基本代换代换是输入集A到输出A'上的双射变换fk:A→A'。其中k是控制输入变量，称为密钥。在密码学中称实现代换fk的系统为代换网络。双射条件保证在给定k下可从密文唯一恢复出原明文，不知道k则恢复明文应是难的。对于给定的代换网络，用F表示在该系统中可以实现的代换fk全体：F={fk|kK}。K为密钥空间。如果网络可以实现所有可能的2n!个代换，kmfc图代换网络(1)循环移位代换循环移位代换分为左循环移位代换和右循环移位代换。：(m0,m1,…,mn-1)→(m1,m2,…,mn-1,m0)：(m0,m1,…,mn-1)→(mn-1,m0,…,mn-2)令F为左循环移位代换全体构成的集合，F为右循环移位代换全体构成的集合，则|F|=|F|=n，并且和互为逆代换，即·=·=I(恒等变换)。(2)模2n加1代换：m→c:ǁcǁ=ǁmǁ+1mod2n(这里||x||表示将字符串转换为十进制数)令F={,2,…2n-1,2n=1}，显然|F|=2n类似可定义-1：m→c:ǁcǁ≡ǁmǁ-1mod2n≡ǁmǁ+(2n-1)mod2n显然·-1中=-1·=I(恒等变换)。(3)线性变换T令T是GF(2)上的n×n阶非奇阵，则T定义了一个GF(2n)上的变换，它将输入明文矢量m=(m0m1…mn-1)变换为密文矢量c=(c0c1…cn-1)，即c=mT。令FT是所有n×n阶非奇阵组成的集合，则|FT|=2n-1！(4)换位代换1||||||||||||1||||1||||||||)(jxjxxjyjxyjyjxyxj且若且若且若j将{0,1,…,2n}中第j个和第j+1个元素交换位置。2n个元素中的任意代换均可由该基本换位代换j的积实现(5)坐标置换坐标置换就是对x=(x0,x1,…,xn-1)的各分量进行置换。设为整数集{0,1,…,n-1}中元素的置换，则有：x=(x0,x1,…,xn-1)→y=(x(0),x(1),…,x(n-1))线性变换的特例，即限定T为每行每列只有一个非零向量的非奇置换阵。令F为所有坐标置换组成的集合，则|F|=n!。(6)仿射变换设T是GF(2)上的n×n阶非奇阵，b为GF(2)上的n维矢量，则δT：x→y=xT+b为仿射变换。令Fδ为所有仿射变换全体构成的集合。由于对任意给定的T可有2n个不同的b，因此仿射变换总数|Fδ|=2n·2n-1！。许多古典密码都可用上述基本代换来描述利用基本代换之积可以构成对称群S(2n)中的所有元素。在把基本代换进行组合时应避免线性性二元代换网络可用布尔函数来描述。令n=3，为方便起见，规定输入和输出二元矢量的分量下标按递增次序排列，即输入x=(x0,x1,x2)，y=(y0,y1,y2)。设与代换网络相应的逻辑真值如表所示，则可写出各输出变量与输入变量的关系式序号输入x0x1x2输出y0y1y201234567000001010011100101110111110010000101111001011100)()()()(210210210210xxxxxxxxxxxx)()()()(210210210210xxxxxxxxxxxx)()()()(210210210210xxxxxxxxxxxx2.轮函数在分组密码中，通常用一个函数f进行多次迭代，每次迭代就称为一轮，而函数f就称为轮函数。每一轮的输入都是前一轮的输出，即y(i)=f(y(i-1),k(i))，其中k(i)是第i轮迭代用的子密钥，它由密钥k通过子密钥生成算法产生。研究表明，一个好的轮函数，可使破译复杂性随迭代次数r指数地增大。1)对合密码函数设f(x,k)为GF(2n)×GF(2t)→GF(2n)的映射，其中n是分组长，t为密钥长。若对每个密钥k都有f(f(x,k),k)=x，即f(x,k)2=I，则称f为对合密码函数，用fI表示。由fI构造的多轮分组密码称为I型迭代分组密码。用fI在子密钥k(1),…,k(r)控制下对明文m进行r轮迭代运算，得到密文c；而用fI在逆序子密钥k(r),…,k(1)控制下对密文c进行r轮迭代运算，就得到明文m。前r轮运算就称为加密运算E(m,k)，后r轮运算就称为解密运算D(c,k)。这种构造密码方法有一个明显的缺陷，即对任意偶数轮变换，若对所有i选择k(2i-1)=k(2i)，则加密的变换等价于恒等变换在实际使用时必须避免选择这类密钥(2)对合置换设P是GF(2n)→GF(2n)的置换，若对所有xGF(2n)，有P(P(x))=x，即PP=I，就称为对合置换，用PI表示。如果每轮都采用对合密码函数fI和对合置换PI的复合，即E(x,k)=PI(fI(x,k))，并选解密子密钥与加密子密钥逆序称这类轮函数构造的多轮分组密码为Ⅱ型迭代分组密码。(3)群密码若密钥与明文、密文取自同一空间GF(2n)，为群运算，定义c=mk，称为群密码。c可通过k的逆元求m=ck-1。令mk为一群密码，fI(x,k)为对合密码函数，构造轮函数F(m,k)=fI(mkA,kB)，用它进行多次迭代，由此即得新的多轮分组迭代密码。为保证整个加、解密的对合性，在迭代的昀后一轮增加一次群密码运算，即：y(1)=fI(m)1(Ak,)1(Bk),…,y(r-1)=fI(y(r-2))1(rAk,)1(rBk)，y(r)=fI(y(r-1))(rAk,)(rBk))1(rAk称这样的密码为Ⅲ型迭代分组密码。(4)Ⅳ型迭代分组密码在上述轮函数基础上，如果再加一个对合置换PI，即构成新的轮函数F(m,k)=PI(fI(mkA,kB))，用它进行多次迭代，由此又得新的多轮分组迭代密码。为了保证整个加、解密的对合性，在迭代的昀后一轮增加一次群密码运算和对合置换，即：y(1)=PI(fI(m)1(Ak,)1(Bk)),…,y(r-1)=PI(fI(y(r-2))1(rAk,)1(rBk))，y(r)=PI(PI(fI(y(r-1))(rAk,)(rBk)))1(rAk))称这样的密码为Ⅳ型迭代分组密码。S盒设计在许多分组密码都属于迭代分组密码，而其核心是轮函数，而轮函数的基础是对合函数fI的选择以与其他代换的有机结合。组密码的非线性性通常主要依赖fI中的代换网络的线性性。于在密码设计时常选择较大的n(n为分组的长度)，达式中合取式个数随n指数级增大而难以实际应用n划分成较小的段。如选n=r·n0，这里r和n0们都是整数。设计n个变量的代换网络变为设计r个较小的子代网络，而每个子代换网络只有n0个输入变量，而n0般不会太大。S盒的强度和运行速度在很大程度上决定了分组密码的强度和运行速度，故S盒的设计是迭代分组密码成功和实用的关键。S盒设计经验表明，实现代换所需昀小的合取项数目可作为排除安全性差的盒函数指标或直观依据，对S盒提出的安全要求越高，其逻辑表达式中的合取式数目就越大。DES算法的n0=6，因此其合取式昀多可达26=64项。昀小项越多，实现也就越复杂。为了便于实现通常应对逻辑表达式化简一个好的S盒，其布尔函数应满足以下一些基本条件：(1)平衡性：函数f:Z2nZ2m,n≥m，当输入取遍所有可能值，如果每个输出y=f(x)出现次数相等，称f满足平衡准则。(2)严格雪崩准则(SAC)：所谓雪崩效应是指改变输入1bit，则输出将有一半的输出将改变。函数f:Z2nZ2,当输入任一位取补，其输出位将以1/2概率取补，则称f满足严格雪崩准则。如果对于函数f，其输入x任意i位(1≤i≤k)取补时，其输出y=f(x)将以1/2概率取补，则称f满足k阶严格雪崩准则。(3)非线性性：函数f:Z2nZ2，若对常数，f(x)=ax，则称f为线性函数，而f(x)=axb即为仿射函数(为常数)。对函数f=(f1,f2,…,fm):(其中fi:，i=1,2,…,m)定义非线性度为：NLf=})(|{|min2,,bxwxcfZxnwcb|，其中nZw2，)}0,,0,0{(2mZc，w·x表示GF(2)上w与x的点积，且)()(1xfcxfciimi(c=(c1,c2,…cm))。在密码线性分析中，关键就是S-盒的线性逼近。(4)线性结构：函数f:Z2nZ2，它的线性结构定义为矢量aZ2