复旦大学信息安全课件第3章现代加密算法
第第3章 现代加密算法章 现代加密算法分组密码的基本概念、设计原则和设计方法、运行模式等分组密码的基本概念、设计原则和设计方法、运行模式等（美国）商用数据加密标准即（美国）商用数据加密标准即DES算法、算法、SAFER算法和本世纪替代算法和本世纪替代DES算法的算法的Rijndael算法算法公钥密码体制以及重要的加密算法公钥密码体制以及重要的加密算法3.1 分组密码分组密码分组密码是将明文序列分成长为分组密码是将明文序列分成长为L的组的组m=(m0m1mL-1) ， 各 组 分 别 在 密 钥， 各 组 分 别 在 密 钥k=(k0,k1,ks)控制下变换成等长的输出序列即密文控制下变换成等长的输出序列即密文c=(c0c1cn-1)。在相同密钥下，分组密码对长为在相同密钥下，分组密码对长为L的输入明文组所进行的变换是等同的，的输入明文组所进行的变换是等同的，只需研究对任一组明文的变换规则。只需研究对任一组明文的变换规则。分组密码实质上是多字母代换密码的推广，所采用的分组密码实质上是多字母代换密码的推广，所采用的L较大。较大。3.1.1分组密码设计原则分组密码设计原则在分组密码中，明密文都采用在分组密码中，明密文都采用0,1序列。序列。把长为把长为L的的0,1字符串字符串m和和c表示成小于表示成小于2L的整数，即：的整数，即：m=(m0m1mL-1) 102Liiim=mc=(c0c1cL-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 ， 并 需 要， 并 需 要 23264bit=215MB存储，因此穷举攻击实际上是不可行的存储，因此穷举攻击实际上是不可行的2)密钥量要足够大，即置换子集中的元素足够多，尽可能消除弱密钥并使所有密密钥量要足够大，即置换子集中的元素足够多，尽可能消除弱密钥并使所有密钥同样好钥同样好。同时为了便于密钥管理同时为了便于密钥管理，密密3)由密钥确定的置换算法要足够复杂，实现明文与密文的扩散和混乱，没有简单的关系可循，并能抗差分攻击、线性攻击等已知的密码攻击方法。由密钥确定的置换算法要足够复杂，实现明文与密文的扩散和混乱，没有简单的关系可循，并能抗差分攻击、线性攻击等已知的密码攻击方法。4)设计的算法采用规则的模块结构，加密和解密运算简单，便于软件和硬件的实现。在主要以软件实现为手段的密码算法中，应选用以标准处理器进行运算的基本运算，而避免采用如逐位置换那种较难用软件实现的运算。在主要以硬件实现为手段的密码算法中，应使得加密和解密过程之间的差别仅在由密钥所生成的密钥表的不同，使得加密和解密可以用同一设计的算法采用规则的模块结构，加密和解密运算简单，便于软件和硬件的实现。在主要以软件实现为手段的密码算法中，应选用以标准处理器进行运算的基本运算，而避免采用如逐位置换那种较难用软件实现的运算。在主要以硬件实现为手段的密码算法中，应使得加密和解密过程之间的差别仅在由密钥所生成的密钥表的不同，使得加密和解密可以用同一器件实现器件实现在实际设计密码算法时，要实现上述各要求也不容易。在实际设计密码算法时，要实现上述各要求也不容易。为了便于实现，通常可将较简单且易实现的密码系统进行组合，构成比较复杂、密钥量大的密码系统。为了便于实现，通常可将较简单且易实现的密码系统进行组合，构成比较复杂、密钥量大的密码系统。Shannon提出了设计分组密码采用方法的建议：提出了设计分组密码采用方法的建议：(1) “概率加权和”方法，以一定的概率随机从一些简单密码系统中选择一个用于加密当前明文。设选用的密码系统有“概率加权和”方法，以一定的概率随机从一些简单密码系统中选择一个用于加密当前明文。设选用的密码系统有r个，用个，用E1,E2,En表示，被选用的概率是表示，被选用的概率是p1,p2,pr， 其 中， 其 中11riip。 概 率 和 系 统 可 表 示 成。 概 率 和 系 统 可 表 示 成C=p1E1+p2E2+prEr。(2)“乘积”方法，用两个密码算法乘积”方法，用两个密码算法E1和和E2对明文进行加密。先用对明文进行加密。先用E1对明文进行加密，然后再用对明文进行加密，然后再用E2对所得结果加密。对所得结果加密。(3)采用扩散和混乱方法。采用扩散和混乱方法。所谓扩散就是使每位明文和密钥的影响散布到尽可能多的输出密文中，以隐蔽明文的统计特性，防止对密钥逐段破译所谓扩散就是使每位明文和密钥的影响散布到尽可能多的输出密文中，以隐蔽明文的统计特性，防止对密钥逐段破译混乱就是使作用于明文的密钥与密文之间的关系复杂化，使明文与密文之间、密文与密钥之间的统计相关性极小化，以便抗统计分析攻击。混乱就是使作用于明文的密钥与密文之间的关系复杂化，使明文与密文之间、密文与密钥之间的统计相关性极小化，以便抗统计分析攻击。3.1.2 分组密码中的常用函数和分组密码中的常用函数和S盒设计盒设计在分组密码中，通常采用一些比较简单的函数，通过多次乘积、迭代强化为一个复杂的密码体制。在分组密码中，通常采用一些比较简单的函数，通过多次乘积、迭代强化为一个复杂的密码体制。1.常用基本代换常用基本代换代换是输入集代换是输入集A到输出到输出A上的双射变换上的双射变换fk:AA。其中其中k是控制输入变量，称为密钥。是控制输入变量，称为密钥。在密码学中称实现代换在密码学中称实现代换fk的系统为代换网络。的系统为代换网络。双射条件保证在给定双射条件保证在给定k下可从密文唯一恢复出原明文，不知道下可从密文唯一恢复出原明文，不知道k则恢复明文应是难的。则恢复明文应是难的。对于给定的代换网络，用对于给定的代换网络，用F表示在该系统中可以实现的代换表示在该系统中可以实现的代换fk全体：全体：F= fk|k K。K为密钥空间。为密钥空间。如果网络可以实现所有可能的如果网络可以实现所有可能的2n!个代换个代换， k m f c 图 代换网络(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代换代换：mc:c=m+1 mod2n(这里这里|x|表示将字符串转换为十进制数表示将字符串转换为十进制数)令令F = , 2, 2n-1, 2n=1，显然，显然|F |=2n类似可定义类似可定义 -1：mc:cm- -1 mod2nm+(2n-1)mod2n显然显然 -1中中= -1 =I(恒等变换恒等变换)。(3)线性变换线性变换T令令T是是GF(2)上的上的nn阶非奇阵，则阶非奇阵，则T定义了一个定义了一个GF(2n)上的变换，它将输入明文矢量上的变换，它将输入明文矢量m=(m0m1mn-1) 变 换 为 密 文 矢 量变 换 为 密 文 矢 量c=(c0c1cn-1)，即，即c=mT。令。令FT是所有是所有nn阶非奇阵组成的集合，则阶非奇阵组成的集合，则|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)上的上的nn阶非奇阵，阶非奇阵，b为为GF(2)上的上的n维矢量，则维矢量，则T：xy=xT+b为仿射变换。为仿射变换。令令F为所有仿射变换全体构成的集合。为所有仿射变换全体构成的集合。由于对任意给定的由于对任意给定的T可有可有2n个不同的个不同的b，因此仿射变换总数，因此仿射变换总数|F|=2n2n-1！。！。许多古典密码都可用上述基本代换来描述许多古典密码都可用上述基本代换来描述利用基本代换之积可以构成对称群利用基本代换之积可以构成对称群S(2n)中的所有元素。中的所有元素。在把基本代换进行组合时应避免线性性在把基本代换进行组合时应避免线性性二二元代换网络可用布尔函数来描述。令元代换网络可用布尔函数来描述。令n=3，为方，为方便便起见，规定输入和输出二元矢量的分量下标按递起见，规定输入和输出二元矢量的分量下标按递增增次序排列，即输入次序排列，即输入x=(x0,x1,x2)，y=(y0,y1,y2)。设设与代换网络相应的逻辑真值如表所示，则可写出与代换网络相应的逻辑真值如表所示，则可写出各各输出变量与输入变量的关系式输出变量与输入变量的关系式序号输入x0 x1 x2输出y0 y1 y2012345670 0 00 0 10 1 00 1 11 0 01 0 11 1 01111 1 00 1 00 0 01 0 11 1 10 0 10 1 1100)()()()(210210210210 xxxxxxxxxxxx)()()()(210210210210 xxxxxxxxxxxx)()()()(210210210210 xxxxxxxxxxxx2.轮函数轮函数在分组密码中，通常用一个函数在分组密码中，通常用一个函数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为密钥长。若对每个密钥为密钥
