第三章分组密码课件

1、第三章第三章 分组密码分组密码分组密码分组密码(Block Cipher)，一类对称密码算法：，一类对称密码算法：将明文消息分组，逐组加密；将明文消息分组，逐组加密；将明文消息编码表示后的数字序列将明文消息编码表示后的数字序列x0,x1,xi,划分成长为划分成长为n的组的组x=(x0,x1,xn-1) （长为（长为n的矢量）的矢量）各组分别在密钥各组分别在密钥k=(k0,k1,kt-1) K 控制下变换成输出序列控制下变换成输出序列y=(y0,y1,ym-1) Vm (长为长为m的矢量）的矢量）其加密函数其加密函数E：VnKVm，K为密钥空间为密钥空间分组密码实质上是字长为分组密码实质上是字长

2、为m的数字序列的代换密码的数字序列的代换密码1/nV算法的输入长度和输出长度算法的输入长度和输出长度1.通常取通常取m=n (用于加密用于加密)2.若若mn，则为有数据扩展，则为有数据扩展(mn)/压缩压缩(mN/2，则令，则令Kk1,k2,kc如果如果TN/2，则令，则令 Kk1,k2,kc从而可得关于密钥比特的一个线性方程。从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于密钥的一组线性方程，从对不同的明文密文对重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。而确定出密钥比特。 Pi1,i2,ia Cj1,j2,jb=Kk1,k2,kc Ai,j,k

3、=Ai Aj Ak22/ 2/1, 12/1, 0pp 2/1, 12/1, 0pp如果方程成立的概率大于1/2，则由于使得左边为0的明文数T大于总明文数的一半，在所有方程成立的情况中，左边得0的可能性更大，所以此时令右边取0。反之方程不成立的概率大于一半，则左边1多，右边取1 差分密码分析选择明文攻击差分密码分析选择明文攻击差分密码分析是迄今已知的攻击迭代密码最有效的方法之一差分密码分析是迄今已知的攻击迭代密码最有效的方法之一其基本思想是：其基本思想是： 通过分析通过分析明文对明文对的的差值差值对对密文对密文对的的差值差值的的影响来恢复某些密钥比特。影响来恢复某些密钥比特。 对分组长度为对分

4、组长度为n的的r轮迭代密码，两个轮迭代密码，两个n比特串比特串Yi和和Yi*的差的差分定义为分定义为YiYi(Yi*)1。其中表示。其中表示n比特串集上的一个特比特串集上的一个特定群运算，定群运算，(Yi*)1表示表示 Yi*在此群中的逆元。在此群中的逆元。在在DES的差分分的差分分析中差分的计算析中差分的计算选择选择YiYi*，因为，因为运算的单位元是运算的单位元是0元元由加密对可得差分序列：由加密对可得差分序列：Y0,Y1,Yr其中其中Y0和和Y0*是明文对，是明文对，Yi和和Yi* (1ir)是第是第i轮的输出，它轮的输出，它们同时也是第们同时也是第i+1轮的输入。第轮的输入。第i轮的子

5、密钥记为轮的子密钥记为Ki，F是轮是轮函数，且函数，且Yi=F(Yi-1,Ki)。23/ 差分密码分析选择明文攻击差分密码分析选择明文攻击定义定义4-1：r-轮特征轮特征(r-round characteristic)是一个差分序列：是一个差分序列：0,1,r其中其中0是明文对是明文对Y0和和Y0*的差分，的差分，i(1ir)是第是第i轮输出轮输出Yi和和Yi*的差分的差分r-轮特征轮特征=0,1,r的概率是指在明文的概率是指在明文Y0和子密钥和子密钥K1,Kr独立、均匀独立、均匀随机时，明文对随机时，明文对Y0和和Y0*的差分为的差分为0的条件下，第的条件下，第i(1ir)轮输出轮输出Yi和

6、和Yi*的差分为的差分为i的概率。的概率。共有共有r个概率值个概率值定义定义4-2：在：在r-轮特征轮特征=0,1,r中，定义中，定义 pi=P(F(Y)=i|Y=i-1)即即pi表示在输入差分为表示在输入差分为i-1的条件下，轮函数的条件下，轮函数F的输出差分为的输出差分为i的概率。的概率。（转移概率）（转移概率） r-轮特征轮特征=0,1,r的概率近似看作的概率近似看作 。24/riip1差分密码分析选择明文攻击差分密码分析选择明文攻击对对r-轮迭代密码的差分密码分析过程可综述为如下步骤：轮迭代密码的差分密码分析过程可综述为如下步骤： 找出一个找出一个(r-1)-轮特征轮特征(r-1)=

7、0 0, , 1 1, r-1-1，使得它的概率达到最大或几使得它的概率达到最大或几乎最大。（乎最大。（通过统计分析或者数学推导的方法通过统计分析或者数学推导的方法） 均匀随机地选择明文均匀随机地选择明文Y0并计算并计算Y0*，使得使得Y0和和Y0*的差分为的差分为 0 0，找出找出Y0和和Y0*在实际密钥加密下所得的密文在实际密钥加密下所得的密文Yr和和Yr*。若若最后一轮的子密钥最后一轮的子密钥Kr（或（或Kr的部分比特）有的部分比特）有2m个可能值个可能值Krj(1j2m)，设置相应的，设置相应的2m个计数器个计数器j(1j2m)。用每个用每个Krj解密密文解密密文Yr和和Yr*，得到，

8、得到Yr-1和和Yr-1*，如果，如果Yr-1和和Yr-1*的的差分是差分是r-1，则给相应的计数器，则给相应的计数器j加加1。 重复步骤，直到一个或几个计数器的值明显高于其他计数重复步骤，直到一个或几个计数器的值明显高于其他计数器的值，输出它们所对应的子密钥（或部分比特）。器的值，输出它们所对应的子密钥（或部分比特）。25/ Feistel 密码结构密码结构 Feistel密码结构（一种特殊的密码结构（一种特殊的SPN结构）结构）早期，很多成功的分组密码的结构从本质上说都是基于一个称为早期，很多成功的分组密码的结构从本质上说都是基于一个称为Feistel网络的结构网络的结构加解密相似加解密相

9、似是是Feistel型密码的一个实现优点，但它对于密码的型密码的一个实现优点，但它对于密码的扩散似扩散似乎有些慢乎有些慢，例如需要两轮才能改变输入的每一个比特。不过在实用中，例如需要两轮才能改变输入的每一个比特。不过在实用中似乎并不会形成较大的影响，只要轮数足够多。似乎并不会形成较大的影响，只要轮数足够多。Feistel提出利用乘积密码可获得简单代换密码提出利用乘积密码可获得简单代换密码多轮迭代多轮迭代每一轮变换实际上是一种每一轮变换实际上是一种SPNFeistel还提出了实现代换和置换的方法还提出了实现代换和置换的方法 其思想实际上是其思想实际上是Shannon提出的提出的利用乘积密码实现混

10、淆和扩散思想的具体利用乘积密码实现混淆和扩散思想的具体应用应用26/ Feistel 密码结构密码结构27/1Feistel 加密结构lHorst Feistel在70年代初设计了这样的结构，我们现在叫做Feistel cipher l每组明文分成左右两半L0和R0l其第i轮迭代的输入为前一轮输出的函数：lLiRi1lRiLi1F(Ri1, Ki)lKi是第i 轮用的子密钥，各轮不同，由密钥K产生l最后一轮完成后再左右交换Feistel 密码结构密码结构Feistel网络的实现与以下参数和特性有关：网络的实现与以下参数和特性有关： 分组大小分组大小 分组越大则安全性越高，但加密速度就越慢。分组

11、密码设计中最为普分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是遍使用的分组大小是64比特。当前多使用比特。当前多使用128比特以上比特以上 密钥大小密钥大小密钥越长则安全性越高，但加密速度就越慢。现在普遍认为密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或比特或更短的密钥长度是不安全的，通常使用更短的密钥长度是不安全的，通常使用128比特的密钥长度。比特的密钥长度。 轮数轮数 单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为型地，轮数取为16。 子密钥产生算法：子

12、密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。该算法的复杂性越大，则密码分析的困难性就越大。 轮函数轮函数 ：轮函数的复杂性越大，密码分析的困难性也越大。：轮函数的复杂性越大，密码分析的困难性也越大。28/ Feistel 密码结构密码结构在设计在设计Feistel网络时，还有以下两个方面需要考虑网络时，还有以下两个方面需要考虑 快速的软件实现快速的软件实现在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键时算法的执行速度是考虑的关键 算法容易分析算法容易分析如果算法能被无疑义地

13、解释清楚，就可容易地分析算法抵抗攻击的能力，如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法有助于设计高强度的算法2. Feistel 解密结构解密结构Feistel解密过程本质上和加密过程是一样的，使加解密可用同一算法解密过程本质上和加密过程是一样的，使加解密可用同一算法,算法算法使用密文作为输入使用密文作为输入，但，但使用子密钥使用子密钥Ki的次序与加密过程相反的次序与加密过程相反，即第，即第1轮使用轮使用Kn，第，第2轮使用轮使用Kn-1，最后一轮使用，最后一轮使用K1。29/ Feistel 密码结构密码结构加密过程由上而下加密过程由上而下解密过程

14、由下而上解密过程由下而上图中右边标出了解密过图中右边标出了解密过程中每一轮的中间值与程中每一轮的中间值与左边加密过程中间值的左边加密过程中间值的对应关系对应关系即加密过程第即加密过程第i轮的输轮的输出是出是LEiREi（表示表示链接）链接）解密过程第解密过程第17-i轮相轮相应的输入是应的输入是RDiLDi最后一轮输出密文是最后一轮输出密文是RE16LE1630/数据加密标准数据加密标准DESDES的产生的产生美国国家标准局美国国家标准局1973年开始研究除国防部外的其它部门的计算机系统年开始研究除国防部外的其它部门的计算机系统的数据加密标准的数据加密标准于于1973年年5月月15日和日和19

15、74年年8月月27日先后两次向公众发出了征求加密算日先后两次向公众发出了征求加密算法的公告。加密算法要达到的目的（通常称为法的公告。加密算法要达到的目的（通常称为DES 密码算法要求）主密码算法要求）主要为以下四点：要为以下四点： （1）提供高质量的数据保护提供高质量的数据保护，防止数据未经授权的泄露和未被察觉的，防止数据未经授权的泄露和未被察觉的修改；修改； （2）计算安全性计算安全性：具有相当高的复杂性，使得破译的开销超过可能获：具有相当高的复杂性，使得破译的开销超过可能获得的利益，同时又要便于理解和掌握；得的利益，同时又要便于理解和掌握； （3）基尔霍夫准则基尔霍夫准则：DES密码体制的

16、安全性应该不依赖于算法的保密，密码体制的安全性应该不依赖于算法的保密，其安全性仅以加密密钥的保密为基础；其安全性仅以加密密钥的保密为基础； （4）可行性可行性：实现经济，运行有效，并且适用于多种完全不同的应用。：实现经济，运行有效，并且适用于多种完全不同的应用。 31/数据加密标准数据加密标准DESDES在在1975年年3月月17日首次被公布在联邦记录中日首次被公布在联邦记录中经过大量的公开讨论后，经过大量的公开讨论后，1977年年1月月15日美国政府颁布：日美国政府颁布：采采纳美国纳美国IBM公司设计的方案公司设计的方案作为作为非机密数据非机密数据的正式数据加密的正式数据加密标准（标准（DE

17、S, Data Encryption Standard），），DES被正式批被正式批准并作为美国联邦信息处理标准，即准并作为美国联邦信息处理标准，即FIPS-46，同年，同年7月月15日开始生效。日开始生效。它的分组长度为它的分组长度为64比特，密钥长度为比特，密钥长度为56比特，是早期的称比特，是早期的称作作Lucifer密码的一种发展和修改。密码的一种发展和修改。DES是迄今为止世界上最为广泛使用和流行的一种分组密是迄今为止世界上最为广泛使用和流行的一种分组密码算法，码算法，1996年以后，主要是年以后，主要是3DES32/ DES算法描述算法描述加密：加密：明文分组明文分组64bit初始

18、置换初始置换IP16轮的轮的Feistel结构结构初始逆置换初始逆置换IP-1是是IP的逆的逆密钥编排密钥编排密钥密钥56比特，每比特，每7bit加加1个个奇偶校验位，总计奇偶校验位，总计64比特比特置换函数置换函数PC-1左循环移位再置换函数左循环移位再置换函数PC-2输出本轮子密钥输出本轮子密钥迭代迭代16轮轮33/ DES算法描述算法描述1. 初始置换初始置换表表3-2(a)和和3-2(b)分别给出了初始置换和逆初始置换的定义，这两个置换分别给出了初始置换和逆初始置换的定义，这两个置换是互逆的。是互逆的。64比特的明文比特的明文M以以8比特为一行，共比特为一行，共8行，以行顺序编号行，以

19、行顺序编号由表由表3-2(a)得得X=IP(M)，由，由3-2(b)得得 YIP-1(X)=IP-1(IP(M)=M34/ DES算法描述算法描述2. 轮结构轮结构64比特的轮输入分为左右两半，右半部分是本轮子密钥产生过程比特的轮输入分为左右两半，右半部分是本轮子密钥产生过程35/和Feistel网络一样，每轮变换可由以下公式表示：lLiRi1 lRiLi1 F(Ri1, Ki)l其中轮密钥Ki为48比特。 DES算法描述算法描述函数函数F(R,K)的计算过程的计算过程如上图所示，轮输入的右半部分如上图所示，轮输入的右半部分R为为32比特，比特，R首先被扩展成首先被扩展成48比特，比特，扩展过

20、程由表扩展过程由表3.2(c)定义，其定义，其中将中将R的的16个比特各重复一次个比特各重复一次。36/扩展后的48比特再与子密钥Ki异或，然后再通过8个S盒，产生32比特的输出。该输出再经过一个由表3.2(d)定义的置换P，产生的结果即为函数F(R,K)的输出。 DES算法描述算法描述扩展置换扩展置换E和置换和置换P37/ DES算法描述算法描述代换盒，简称代换盒，简称S盒，盒，substitution boxSF中的代换由中的代换由8个个S盒组成，每个盒组成，每个S盒的输入长为盒的输入长为6比特、输出长为比特、输出长为4比特，比特，其变换关系由表其变换关系由表3.3定义，每个定义，每个S盒

21、给出了盒给出了4个代换（由一个表的个代换（由一个表的4行给行给出）。出）。DES的的S盒定义盒定义38/ DES算法描述算法描述对每个盒对每个盒Si其其6比特输入中，比特输入中，第第1个和第个和第6个比特个比特形成一个形成一个2位二进制数，用来选择位二进制数，用来选择Si的的4个代换中的一个个代换中的一个中间中间4位用来选择列位用来选择列。行和列选定后，得到其交叉位。行和列选定后，得到其交叉位置的十进制数，将这个数表示为置的十进制数，将这个数表示为4位二进制数即得这一位二进制数即得这一S盒的输出。盒的输出。例如，例如，S1 的输入为的输入为011001则行选为则行选为01（即第（即第1行），列

22、选为行），列选为1100（即第（即第12列）列）行列交叉位置的数为行列交叉位置的数为9，其，其4位二进制表示为位二进制表示为1001，所以，所以S1的输出为的输出为1001。S盒作为该密码体制的唯一非线性组件对安全性至关重要盒作为该密码体制的唯一非线性组件对安全性至关重要S-盒的设计准则还没有完全公开，一些密码学家怀疑美国盒的设计准则还没有完全公开，一些密码学家怀疑美国NSA(the National Security Agency)设计设计S-盒时隐藏了陷门盒时隐藏了陷门，即万能钥匙，即万能钥匙39/ DES算法描述算法描述3密钥的产生密钥的产生实际上，实际上，K是长度为是长度为64的位串，

23、的位串，其中其中56位是密钥，位是密钥，8位是奇偶校位是奇偶校验位（为了检错），在密钥编验位（为了检错），在密钥编排的计算中，这些校验位可略排的计算中，这些校验位可略去。去。DES密钥编排算法结构图密钥编排算法结构图LSi表示循环左移一个或两个位表示循环左移一个或两个位置置其中其中i为为1，2，9，16循环移循环移1位，位，其余循环移两位其余循环移两位40/ DES算法描述算法描述综述加密过程综述加密过程：(1) 给定给定64位的密钥位的密钥K，放弃奇偶校验位（，放弃奇偶校验位（8，16，64）形成连续的）形成连续的56比特的密钥，对输入分组进行固定的比特的密钥，对输入分组进行固定的“初始置换

24、初始置换”IP,我们可以将这个我们可以将这个初始置换写为初始置换写为 , 称为称为“左右半分左右半分组组”32bits(2)再看再看DES加密算法框图，进行加密算法框图，进行16轮迭代轮迭代 ： ， ， 输入算法的输入算法的56比特密钥首先经过一个置换运算比特密钥首先经过一个置换运算PC-1，该置换由表，该置换由表3.4(a)给出得到给出得到48比特的子串，比特的子串， 称为布尔函数，它的特点是交换两半分组。称为布尔函数，它的特点是交换两半分组。在第在第i 轮分别对轮分别对 进行左循环移位，所移位数由表进行左循环移位，所移位数由表3.4(c)给出。给出。移位后的结果作为求下一轮子密钥的输入，同

25、时也作为置换选择移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择2 PC-2的输入。通过置换选择的输入。通过置换选择2产生的产生的48比特的比特的Ki，即为本轮的子密钥，作为，即为本轮的子密钥，作为函数函数F(Ri-1,Ki)的输入。其中置换选择的输入。其中置换选择2由表由表3.4(b)定义定义（3）DES算法的输出，我们将最后一步写为算法的输出，我们将最后一步写为: 注意注意 的输入：在输入之前，的输入：在输入之前，16轮迭代输出的两个半分组又进行了轮迭代输出的两个半分组又进行了一次交换。一次交换。输入分组IPRL00,00RL 和16, 2 , 1i1iiRLiiiikRfLR,1

26、1称为轮密钥ikf1 - i1 - iRL ，16161,LRIP输出分组1IP DES算法描述算法描述DES密钥编排中使用的表（表密钥编排中使用的表（表3-4） (a) 置换选择置换选择1 (b) 置换选择置换选择2 (c) 左循环移位位数左循环移位位数 42/ DES算法描述算法描述4解密解密l和和Feistel密码一样，密码一样，DES的解密和加密算法使用同一算法，但的解密和加密算法使用同一算法，但子密钥子密钥使用的顺序相反使用的顺序相反解密时子密钥的产生有两种方式：解密时子密钥的产生有两种方式：l1）是先由）是先由K产生产生16个子密钥，个子密钥，再逆续使用再逆续使用l2）反序产生。）

27、反序产生。(在前面讲过的密钥扩展过程中若改在前面讲过的密钥扩展过程中若改LSi为为l则也就可以依次产生这逆序的子密钥。则也就可以依次产生这逆序的子密钥。43/其它,21692110iiRSi115161621,kkkkkk 例例 在加密密钥在加密密钥 下，将明文消息下，将明文消息 加密为密文消息加密为密文消息 。让我们通过让我们通过DES算法来确认解密函数的正确运算，也就是算法来确认解密函数的正确运算，也就是在在 下，下， 的解密就输出的解密就输出 。 解：解：解密算法首先输入密文解密算法首先输入密文 作为作为“输入分组输入分组”，即即 但是因为但是因为c是实际上是加密算法中最后一是实际上是加

28、密算法中最后一步的步的“输出分组输出分组”，即：，即： 在第一轮中，我们有在第一轮中，我们有 这两个式子的右边，这两个式子的右边， 应该用应该用 来代替，来代替， 应该用应该用kmckcmc cIPRL00,161600,LRRL1161600011601,;kLfRLRfLRLRL16L15R16R161515,kRfL 其中其中 ，因此，上面两个式子实际上是下面的两个，因此，上面两个式子实际上是下面的两个 所以，所以，在第一轮解密以后在第一轮解密以后，我们得到，我们得到因此，因此，在第二轮开始在第二轮开始，两个半分组是，两个半分组是 .在随后的在随后的15轮中，使用同样的验证，我们将获得轮

29、中，使用同样的验证，我们将获得在在16轮迭代得到的两个最后的半分组轮迭代得到的两个最后的半分组 被交换为被交换为 然后输入到然后输入到 来消除来消除IP在式中的影响。在式中的影响。解密函数的输出确实是最初的明文分组解密函数的输出确实是最初的明文分组m.161kk 1516151515151151,;LkRfLRfLRRL151511,LRRL1515,LR001616141422,LRRLLRRL1616,RL001616,LRRL1IPDES的安全性问题的安全性问题完全依赖于所用的密钥，即算法是公开的完全依赖于所用的密钥，即算法是公开的DES的设计特色：的设计特色： 在在DES算法中函数是最

30、基本的关键环节，其中算法中函数是最基本的关键环节，其中 （1）用）用S盒实现小块的非线性变换，达到混乱目的盒实现小块的非线性变换，达到混乱目的 （2）用置换）用置换p实现大块的非线性变换，达到扩散目的实现大块的非线性变换，达到扩散目的 （3）置换）置换p的设计是每层的设计是每层s盒的盒的4bit输出进入到下一输出进入到下一 层的层的4个不同个不同S盒盒 DES的安全性包括：的安全性包括：取反特性取反特性，弱密钥和半弱密钥弱密钥和半弱密钥，密钥密钥与密文和明文的关系，与密文和明文的关系，DES评估与穷搜索破译评估与穷搜索破译3.6 高级加密标准高级加密标准AES 由于由于DES要花费比较大的软硬

31、件代价，效率不尽如人意，况且要花费比较大的软硬件代价，效率不尽如人意，况且DES密密钥较短不能抵抗群搜索攻击，于是更好的标准钥较短不能抵抗群搜索攻击，于是更好的标准AES走向了前台。走向了前台。 2000年年10月月2日日NIST宣布宣布Rijndael作为新的作为新的AES。至此，经过。至此，经过3年多的讨论，年多的讨论，Rijndael终终于脱颖而出。于脱颖而出。 2006年，年，AES已然成为了对称密钥加密中重要的国际标准之一已然成为了对称密钥加密中重要的国际标准之一AES的应用产品：有移动硬盘，的应用产品：有移动硬盘，USB无线网卡，加密锁，指纹加密无线网卡，加密锁，指纹加密U盘，盘，

32、 指纹加密防护盾等。指纹加密防护盾等。 47/ Rijndael的数学基础和设计思想的数学基础和设计思想1. 有限域有限域GF(28)有限域中的元素可以用多种不同的方式表示。有限域中的元素可以用多种不同的方式表示。对于任意对于任意素数素数的方幂，都的方幂，都有惟一的一个有限域有惟一的一个有限域，因此因此GF(28)的所有表示是同构的的所有表示是同构的，但不同的表示但不同的表示方法会影响到方法会影响到GF(28)上运算的复杂度上运算的复杂度本算法采用传统的多项式表示法：本算法采用传统的多项式表示法：将将b7b6b5b4b3b2b1b0构成的字节构成的字节b看成系数在看成系数在GF(2)=0,1中

33、的多项式中的多项式 b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：例如： 十六进制数十六进制数57对应的二进制为对应的二进制为01010111，看成一个字节，对应的多项，看成一个字节，对应的多项式为式为x6+x4+x2+x+148/ Rijndael的数学基础和设计思想的数学基础和设计思想AES的理论基础定义在的理论基础定义在GF(28) ,其基本的运算有三种，其基本的运算有三种，分别为加分别为加法，乘法和法，乘法和x乘。乘。加法：加法：在多项式表示中，在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过上两个元素的和仍然是一个次数不超过7的多项的多项

34、式，其系数等于两个元素对应系数的模式，其系数等于两个元素对应系数的模2加（比特异或）。加（比特异或）。例如：例如： 57+83=D4，用多项式表示为，用多项式表示为(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2 (mod m(x)用二进制表示为用二进制表示为 01010111+10000011=11010100由于每个元素的加法逆元等于自己，所以减法和加法相同。由于每个元素的加法逆元等于自己，所以减法和加法相同。49/ Rijndael的数学基础和设计思想的数学基础和设计思想乘法：乘法：要计算要计算GF(28)上的乘法，必须先确定一个上的乘法，必须先确定一个GF(2)上

35、的上的8次不可次不可约多项式，约多项式，GF(28)上两个元素的乘积就是这两个多项式的模上两个元素的乘积就是这两个多项式的模乘，在乘，在Rijndael密码中，这个密码中，这个8次不可约多项式确定为次不可约多项式确定为 m(x)=x8+x4+x3+x+1它的十六进制表示为它的十六进制表示为11B。二进制为。二进制为100011011例如，例如，5783=C1可表示为以下的多项式乘法：可表示为以下的多项式乘法：(x6+x4+x2+x+1)(x7+x+1)=x7+x6+1(mod m(x)乘法运算虽然不是标准的按字节的运算，但也是比较简单的计乘法运算虽然不是标准的按字节的运算，但也是比较简单的计算

36、部件。算部件。50/ Rijndael的数学基础和设计思想的数学基础和设计思想以上定义的以上定义的乘法满足交换律乘法满足交换律，且，且有单位元有单位元01。逆元逆元，对任何次数小于，对任何次数小于8的多项式的多项式b(x)，可用推广的欧几里得算，可用推广的欧几里得算法得法得b(x)a(x)+m(x)c(x)=1即即a(x)b(x)=1 mod m(x)，因此，因此a(x)是是b(x)的乘法逆元。的乘法逆元。再者，再者，乘法还满足分配律乘法还满足分配律：a(x)(b(x)+c(x)=a(x)b(x)+a(x)c(x)所以，所以，256个字节值构成的集合，在以上定义的加法和乘法运算个字节值构成的集

37、合，在以上定义的加法和乘法运算下，有有限域下，有有限域GF(28)的结构的结构非非0元的乘法满足元的乘法满足Abel群，加法满足群，加法满足Abel群，群，,满足分配率满足分配率51/ Rijndael的数学基础和设计思想的数学基础和设计思想X乘乘GF(28)上还定义了一个运算，称之为上还定义了一个运算，称之为x乘法，其定义为乘法，其定义为xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x)如果如果b7=0，求模结果不变，否则为乘积结果减去，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与，即求乘积结果与m(x)的异或。的异或。

38、由此得出由此得出x（十六进制数（十六进制数02）乘乘b(x)可以可以先对先对b(x)在字节内左移一位在字节内左移一位（最后（最后一位补一位补0），），若若b7=1，则再与，则再与1B（其二进制为（其二进制为00011011）做逐比特异或做逐比特异或来来实现，实现，该运算记为该运算记为b=xtime(a)。在专用芯片中，在专用芯片中，xtime只需只需4个异或。个异或。x的幂乘运算可以重复应用的幂乘运算可以重复应用xtime来实现。而任来实现。而任意常数乘法可以通过对中间结果相加实现。意常数乘法可以通过对中间结果相加实现。例如，例如，5708可按如下方式实现：可按如下方式实现： 5702=xti

39、me(57)=AE；5704=xtime(AE)=47；5708=xtime(47)=8E；52/ Rijndael的数学基础和设计思想的数学基础和设计思想2. 系数在系数在GF(28)上的多项式上的多项式4个字节构成的向量个字节构成的向量可以表示为可以表示为系数在系数在GF(28)上的次数小于上的次数小于4的多项式，的多项式，多项式的多项式的加法加法就是对应系数相加，即就是对应系数相加，即4字节向量的逐比特异或字节向量的逐比特异或规定多项式的规定多项式的乘法运算必须要取模乘法运算必须要取模M(x)=x4+1，这样使得次数小于，这样使得次数小于4的多项的多项式的乘积仍然是一个次数小于式的乘积仍

40、然是一个次数小于4的多项式，将多项式的模乘运算记为的多项式，将多项式的模乘运算记为 设设a(x)=a3x3+a2x2+a1x+a0，b(x)=b3x3+b2x2+b1x+b0 c(x)=c3x3+c2x2+c1x+c0，c(x)=a(x)b(x) mod (x4+1) 而而xj mod (x4+1)=xj mod 4，所以，所以c0=a0b0 a3b1 a2b2 a1b3c1=a1b0 a0b1 a3b2 a2b3c2=a2b0 a1b1 a0b2 a3b3c3=a3b0 a2b1 a1b2 a0b353/ Rijndael的数学基础和设计思想的数学基础和设计思想可将上述计算表示为可将上述计算

41、表示为 注意到注意到M(x)不是不是GF(28)上的不可约多项式（甚至也不是上的不可约多项式（甚至也不是GF(2)上的不可约上的不可约多项式），因此非零多项式的这种乘法不是群运算。多项式），因此非零多项式的这种乘法不是群运算。不过在不过在Rijndael密码中，对多项式密码中，对多项式b(x)，这种乘法运算只限于乘一个固定，这种乘法运算只限于乘一个固定的有逆元的多项式的有逆元的多项式a(x)=a3x3+a2x2+a1x+a0。定理定理1 系数在系数在GF(28)上的多项式上的多项式a3x3+a2x2+a1x+a0是模是模x4+1可逆可逆的，当且仅当以下矩阵在的，当且仅当以下矩阵在GF(28)上

42、可逆。上可逆。54/3210cccc0123301223011230aaaaaaaaaaaaaaaa3210bbbb0123301223011230aaaaaaaaaaaaaaaa55/证明：证明：a3x3+a2x2+a1x+a0是模是模x4+1可逆的，当且仅当存在多项式可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0，使得，使得(a3x3+a2x2+a1x+a0)( h3x3+h2x2+h1x+h0)=1 mod(x4+1)因此有因此有(a3x3+a2x2+a1x+a0)( h2x3+h1x2+h0 x+h3)=x mod(x4+1) (a3x3+a2x2+a1x+a0)( h1x

43、3+h0 x2+h3x+h2)=x2 mod(x4+1)(a3x3+a2x2+a1x+a0)( h0 x3+h3x2+h2x+h1)=x3 mod(x4+1)；将以上关系写成矩阵形式即得将以上关系写成矩阵形式即得 = c(x)=xb(x)定义为定义为x与与b(x)的模的模x4+1乘法，即乘法，即c(x)=xb(x)=b2x3+b1x2+b0 x+b3。其矩阵表示中，除。其矩阵表示中，除a1=01外，其他所有外，其他所有ai=00，即，即 因此因此x（或（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位的幂）模乘多项式相当于对字节构成的向量进行字节循环移位012330122301123

44、0aaaaaaaaaaaaaaaa0123301223011230hhhhhhhhhhhhhhhh10000100001000013210cccc000100000000010000000001010000003210bbbbRijndael算法的特点算法的特点 1.AES的加解密算法、密钥生成算法都是以的加解密算法、密钥生成算法都是以State为为 输入输入 2.加密时，首先进行加密时，首先进行“轮密钥加轮密钥加”算法，然后重复算法，然后重复9轮基轮基本密码模块的迭代算法，每一轮有字节代换，行移位、列混本密码模块的迭代算法，每一轮有字节代换，行移位、列混淆和轮密钥加淆和轮密钥加 四个算法；最

45、后进行第四个算法；最后进行第10轮运算，它与前面轮运算，它与前面9轮比一样的地方，就是少了列混淆算法。轮比一样的地方，就是少了列混淆算法。 3.解密时，是执行加密的逆过程，但要注意在解密时，字解密时，是执行加密的逆过程，但要注意在解密时，字节代换、行移位和列混淆三种运算是执行逆过程，算法设计节代换、行移位和列混淆三种运算是执行逆过程，算法设计完全不一样，只有轮密钥加算法和加密一样完全不一样，只有轮密钥加算法和加密一样 2.轮函数轮函数Rijndael的轮函数由的轮函数由4个不同的计算部件组成，分别是：个不同的计算部件组成，分别是：字节代换（字节代换（ByteSub）、行移位（）、行移位（Shi

46、ftRow）列混合（列混合（MixColumn）、密钥加（）、密钥加（AddRoundKey）(1) 字节代换（字节代换（ByteSub）字节代换是非线性变换，独立地对状态的每个字节进行。代换表（即字节代换是非线性变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到：盒）是可逆的，由以下两个变换的合成得到： 首先，将字节看作首先，将字节看作GF(28)上的元素，上的元素，映射到自己的乘法逆元，映射到自己的乘法逆元，00映射到自己。映射到自己。 其次，对字节做如下的（其次，对字节做如下的（GF(2)上的，可逆的）仿射变换：上的，可逆的）仿射变换： 上述上述S-盒

47、对状态的所有字节所做的变换记为盒对状态的所有字节所做的变换记为ByteSub (State)57/ 111101110011000110001100111011111000110011101111111101110011000176543210yyyyyyyy 0110001176543210 xxxxxxxx整个变换做成整个变换做成256字节的代换字节的代换表，运算时查表即可表，运算时查表即可 算法说明算法说明图图3.19是字节代换示意图。是字节代换示意图。ByteSub的逆变换的逆变换由代换表的逆表做字节代换，可通过如下两由代换表的逆表做字节代换，可通过如下两步实现步实现: 首先进行仿射变

48、换的逆变换首先进行仿射变换的逆变换再求每一字节在再求每一字节在GF(28)上逆元上逆元58/S盒盒aijbij 算法说明算法说明(2) 行移位（行移位（ShiftRow）行移位是将状态阵列的各行进行循环移位，不同状态行的位移行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。量不同。第第0行不移动行不移动第第1行循环左移行循环左移C1个字节个字节第第2行循环左移行循环左移C2个字节个字节第第3行循环左移行循环左移C3个字节个字节位移量位移量C1、C2、C3的取值与的取值与Nb有关，由表有关，由表3.10给出。给出。 表3.1059/ 算法说明算法说明按指定的位移量对状态的行进行的行移

49、位运算记为按指定的位移量对状态的行进行的行移位运算记为ShiftRow(State)图图3.20是行移位示意图。是行移位示意图。ShiftRow的逆变换的逆变换是对状态阵列的后是对状态阵列的后3列分别以位移量列分别以位移量Nb-C1、Nb-C2、Nb-C3进行循环移位。进行循环移位。60/左移左移0位位左移左移1位位左移左移2位位左移左移3位位算法说明算法说明（3）列混合（）列混合（MixColumn）在列混合变换中，在列混合变换中，将状态阵列的每个列视为将状态阵列的每个列视为GF(28)上的多项式，再与一上的多项式，再与一个固定的多项式个固定的多项式c(x)进行模进行模x4+1乘法乘法。当然要求。当然要求c(x)是模是模x4+1可逆的可逆的多项多项式，否则列混合变换就是不可逆的，因而会使不同的输入分组对应的输式，否则列混合变换就是不可逆的，因而会使不同的输入分组对应的输出分组可能相同。出分组可能相同。Rijndael的设计者给出的的设计者给出的c(x)为为（系数用十六进制数表（系数用十