第五章分组密码(51-53)

1、第五章第五章 分组密码分组密码l5.1 分组密码基本概念l5.2 数据加密标准DESl5.3 高级加密标准AESl5.4 国际数据加密算法IDEAl5.5 SMS4密码算法l5.6 分组密码的工作模式l5.7 分组密码分析技术5.1分组密码基本概念分组密码基本概念l分组密码是将明文消息划分成长为L（L的值通常为64或128）的分组Ml各个长为L的分组分别在密钥K的控制下变换成与明文组等长的一组密文C5.1分组密码基本概念分组密码基本概念l对于分组密码两个设计原则是扩散和混淆。l扩散原则：1)明文中的每一位影响密文中的许多位，这样可以隐蔽明文的统计特性；2)使得密钥的每一位影响密文的许多位分组密

2、码基本概念分组密码基本概念 l混淆原则：设计的密码算法应使得密钥和明文以及密文之间的依赖关系变得尽可能复杂。 l可以使用复杂的非线性代替变换来达到较好的混淆效果。l 扩散例子扩散例子分组密码的基本要求分组密码的基本要求分组密码的原理分组密码的原理乘积密码乘积密码l扩散和混混（淆）乱两种基本密码操作的组合变换(乘积密码)l现代分组密码都属于乘积密码，它们可分为：Feistel密码: 同时使用了可逆和不可逆的基本变换部件。非Feistel密码: 只使用了可逆的基本变换部件2022-2-247乘积密码的实现乘积密码的实现SPN网络网络lSPN网络是由多重多重S变换和变换和P变换变换组合成的变换网络l

3、基本操作是S变换变换(代换代换)和和P变换变换(置换置换)，前者称为S盒盒，后者称为P盒盒lS盒起到混乱作用，盒起到混乱作用，P盒起到扩散的作用盒起到扩散的作用2022-2-248乘积密码的实现乘积密码的实现SPN网络网络2022-2-249S变换起混淆的作用； P变换起扩散的作用SPN结构的性质结构的性质lSPN具有雪崩效应：雪崩效应：输入(明文或密钥)即使只有很小的变化，也会导致输出有很大的变化2022-2-24102022-2-24112022-2-2412Feistel网络网络2022-2-2413Feistel网络网络Feistel网络的结构特点定义 变换f称为对合变换（或称为自反变

4、换），如果其反变换还是f。（对任何x满足f(f(x)=x）我们看到，lFeistel网络的第（1）步是对合变换；lFeistel网络的第（2）步也是对合变换；lFeistel网络本身不是对合变换。Feistel网络的这种结构使它能够组合成安全强度高的分组密码算法。2022-2-2414Feistel网络网络Feistel网络能否直接用作分组密码算法？不能。l首先，明文(L(0), R(0)和密文(L(1), R(1)之间有一个明显的关系R(0)= L(1)，即密钥只覆盖了明文的一半 。l其次，设攻击者Eve获得了明文(L(0), R(0)和密文(L(1), R(1)。Eve知道R(1)=L(0

5、)+F(R(0), k)，即F(R(0), k)=R(1)+L(0)。在方程中， Eve仅仅不知道密钥k。如果函数F设计得不好，就可能在方程中解出密钥k，或猜测出密钥k。这就是说，算法的安全性完全依赖于函数F，安全性依靠过于单薄。2022-2-2415Feistel网络网络多轮迭代与轮函数：迭代型分组密码就是用简单的、安全性弱的加密算法进行多轮迭代以获得强的安全性。单轮加密算法称为轮函数，所用的密钥称为单轮子密钥。比如，把Feistel网络作为轮函数，将迭代型分组密码的加密算法构造如下：Feistel网络 Feistel网络 Feistel网络左右对换。则（1）克服了Feistel网络的安全性

6、缺陷；（2）分组密码是“加解密相似的”。5.2 数据加密标准数据加密标准DESl1973年5月15日,美国国家标准局NBS(National Bureau of Standards)开始公开征集标准加密算法，并公布了它的设计要求：l(1)算法必须提供高度的安全性；l(2)算法必须有详细的说明,并易于理解；l(3)算法的安全性取决于密钥，不依赖于算法；l(4)算法适用于所有用户；l(5)算法适用于不同应用场合；l(6)算法必须高效、经济；l(7)算法必须能被证实有效；l(8)算法必须是可出口的。2022-2-24175.2 数据加密标准数据加密标准DES美国国家标准局（NBS）于1977年公布了

7、由IBM公司研制的一种加密算法，并批准把它作为非机要部门使用的数据加密标准（Data Encryption Standard），简称DES。自从公布以来，它一直超越国界成为国际上商用保密通信和计算机通信的最常用的加密算法。当时规定DES的使用期为10年。后来美国政府宣布延长它的使用期，其原因大概有两条：一是DES尚未受到严重的威胁，二是一直没有新的数据加密标准问世。DES超期服役了很长时间，在国际通信保密的舞台上活跃了20年。2022-2-24185.2 数据加密标准数据加密标准DESDES扮演的突出角色首先，DES的结构闪烁着人类设计思想的精华，其优点和缺点被密码学界淋漓尽致地讨论，供后人借

8、鉴。举例如下： （1）DES 使用了S盒，而S盒现在已经是几乎所有分组密码算法不可缺少的部件。 （2）迭代分组密码是分组密码的主流设计。（3）DES 轮函数结构是Feistel网络，这种结构现在已经是轮函数的经典结构之一。2022-2-24195.2 数据加密标准数据加密标准DES（4）DES算法的第一个和最后一个部件没有密钥的参与，在已知明文攻击之下不起任何安全性作用。以后设计的分组密码都纠正了这个缺点。（5）DES的S盒设计细节始终没有公布，因此被人们怀疑设有陷门（即密码设计者为自己预留的破译通道）。这种不透明的设计显然会影响其商用前景。这一缺点引出了商用分组密码设计的一个准则“透明性”，

9、即密码的使用者能够确知该密码的安全强度。 2022-2-24205.2 数据加密标准数据加密标准DES其次，对DES的各种攻击方法纷纷被提出。穷举搜索仍然是对分组密码实用攻击的主角。但进入90年代后，基于数学分析的攻击方法逐渐兴起，如以色列密码专家Shamir等人提出了差分密码分析，日本密码学家Matsui等人提出了线性密码分析，这些数学攻击方法都首先被用于破译DES，并且可以说取得了局部的成功。(比如，有人在个人计算机上用差分密码分析方法，几分钟就破译了8轮DES（标准的DES算法为16轮迭代）。又比如，据称使用243个明文/密文对就可以由线性密码分析方法破译DES。243已经不是天文数字了

10、，据称数十台工作站协同工作，经过十多天就可完成。 )2022-2-24215.2 数据加密标准数据加密标准DESl为抵抗对DES的各种攻击，产生了强化版的三重DES。l三重DES的安全强度高于DES，但似乎不够简洁。l2000年5月，美国国家标准技术研究所（NIST）最终确定了DES的替代标准AES（Advanced Encryption Standard），才使DES基本上完成了自己的历史使命。 AES的算法名称是Rijndael。5.2.1 DES加密算法概述加密算法概述lDES的加密过程可简单描述为三个阶段： 2022-2-2423DESDES的计算部件的计算部件 初始置换初始置换IP与

11、其逆置换与其逆置换IP -1IP是对64比特课文进行位置重排。IP -1是IP的反变换。设 m=(m1, m2, , m64)；c=(c1, c2, , c64)；使得IP(m)=c，或者IP -1(c)=m。则c1= m58，c2= m50，c64= m7。2022-2-2424DESDES的计算部件的计算部件 下表详细给出IP(m)的下标序号与m的下标序号的对应关系，其中IP(m)的下标按顺序排列。7152331394755635132129374553613111927354351591917253341495781624324048566461422303846546241220283

12、64452602101826344250582022-2-2425DESDES的计算部件的计算部件 下表详细给出IP -1(c)的下标序号与c的下标序号的对应关系，其中IP -1(c)的下标按顺序排列。255717499411332658185010422342759195111433352860205212444362961215313455373062225414466383163235515477393264245616488402022-2-2426DESDES的计算部件的计算部件 扩充变换扩充变换E 扩充变换E的作用是将32比特的课文膨胀为48比特。设 m=(m1, m2, , m3

13、2)；c=(c1, c2, , c48)；使得E(m)=c。则c1= m32，c2= m1，c48= m1。下表详细给出E(m)的下标序号与m的下标序号的对应关系，其中E(m)的下标按顺序排列。（注意：下表的中间4列恰好是m的第1第32比特 ） 2022-2-2427DESDES的计算部件的计算部件 E：13231302928292827262524252423222120212019181716171615141312131211109898765454321322022-2-2428DESDES的计算部件的计算部件 8个个S盒盒S1、S2、S8 每个S盒Sj都是将6比特的课文缩减为4比特；

14、8个S盒总共将48比特的课文缩减为32比特。（请不要忘记S盒的作用是获得高度的非线性）设一个S盒的输入为6比特串m=(m1, m2, m3, m4, m5, m6)，输出为4比特串c=(c1, c2, c3, c4)。将比特串m1m6、m2m3m4m5、c1c2c3c4都用10进制数来表示，则在表中位于m1m6行m2m3m4m5列的数就是S盒的输出c1c2c3c4 。2022-2-2429S1 01234567891011121314150144131215118310612590710157414213110612119538241148136211151297310503151282491

15、75113141006132022-2-2430S20123456789101112131415015181461134972131205101313471528141201106911520147111041315812693215313810131542116712051492022-2-2431S30123456789101112131415010091463155113127114281137093461028514121115121364981530111212510147311013069874151431152122022-2-2432S401234567891011121314

16、15071314306910128511124151138115615034721211014921069012117131513145284331506101138945111272142022-2-2433S50123456789101112131415021241710116853151301491141121247131501510398624211110137815912563014311812711421361509104532022-2-2434S6012345678910111213141501211015926801334147511110154271295611314011

17、3829141552812370410113116343212951510111417608132022-2-2435S70123456789101112131415041121415081331297510611130117491101435122158621411131237141015680592361113814107950151423122022-2-2436S80123456789101112131415013284615111109314501271115138103741256110149227114191214206101315358321147410813151290356

18、112022-2-2437DESDES的计算部件的计算部件 我们发现，每一个S盒的每一行数字都是015的一个排列。换句话说，每一个S盒，当输入值m1m6固定时，输出值c1c2c3c4都是输入值m2m3m4m5的可逆函数。为什么要这样设计？为了使扩充变换E8个S盒（32比特 32比特）整体是一个可逆函数，必须使得8个S盒总体输出是8个S盒总体输入的第25、811、1417、2023、2629、3235、3841、4447比特的可逆函数。（回顾扩充变换E：扩充变换E的作用是将32比特的课文膨胀为48比特，且扩充变换后的第1、6、7、12、13、18、19、24、25、30、31、36、37、42、

19、43、48比特为扩充部分。 ）2022-2-2438DESDES的计算部件的计算部件 置换置换P：将32比特的课文改变位置顺序。见下表。25411226301319932732142482103118526231511728122921207162022-2-2439DESDES的计算部件的计算部件 32比特输入比特输入/32比特输出的钥控非线性函数比特输出的钥控非线性函数F钥控非线性函数记为Y=F(X, k)，其中X 32为比特输入， k为48比特密钥， Y为32比特输出。F是扩充变换E、群加密、 8个S盒、置换P的组合，具体的步骤如下。（1） X为32比特输入。（2）对X进行扩充变换E，得

20、到48比特课文U。（3）计算U+k= V，其中k是48比特密钥。（4）将V分为8段，分别进行8个S盒变换，得到32比特课文W。（5）对W进行置换P，得到32比特输出Y。2022-2-24402022-2-2441轮函数：轮函数：轮函数是Feistel网络，输入、输出均为64比特：2022-2-2442DES是迭代型分组密码，明文分组长度为64比特。加密算法步骤如下。u（1）对明文分组进行初始置换IP。u（2）进入16轮迭代，轮函数就是如前所述的Feistel网络，其中第m轮迭代所用的子密钥为k(m)， m=116；第16轮迭代是特殊的一轮，只进行“覆盖”，不进行“左右交换”。u（3）进行初始置

21、换IP的逆变换IP-1。2022-2-2444DESDES的用户密钥（密钥种子）是64比特长，而其中的第8、16、24、32、40、48、56、64比特是奇偶校验位。因此，真正有效的用户密钥（密钥种子）是56比特长。然而DES的加密密钥总长度是4816=766比特。因此， 56比特的用户密钥需要扩展为4816=768比特的加密密钥。密钥扩展算法描述如下。DES加密算法的密钥扩展算法需要用到两个缩减变换PC-1和PC-2，其中PC-1是将64比特长的串缩减为56比特；PC-2是将56比特长的串缩减为48比特。2022-2-2445 PC-1：412202851321293745536161422

22、303846546271523313947556336445260311192735435159210182634425058191725334149572022-2-2446PC-2：32293650424653345639494448334551403055473731524121320277168264121923102161528351241117142022-2-2447密钥扩展算法还需要用到循环左移变换LSj，j=116。其中LSj表示生成第j轮子密钥k(j)时的循环左移变换。这里规定：当j=1，2，9，16时，LSj为循环左移1位；当j=38或1015时，LSj为循环左移2位。每

23、一个循环左移变换的输入和输出都是28比特串。 2022-2-24482022-2-2449DES的解密的解密DES的解密算法与加密算法相同，也是IP16轮迭代（最后一轮是特殊轮）IP-1。仅仅各轮迭代所用的子密钥不同。若加密算法各轮迭代所用的子密钥为k(1)， k(2)， ，k(16)，则解密算法各轮迭代所用的子密钥为k(16)，k(15)， ，k(1)。2022-2-2451对对DES评价的现有结果评价的现有结果lDES简单快速，所使用的计算部件都是计算机的最常用操作。lDES是加解密相似的。lDES加密算法的第一个计算部件是IP，最后一个计算部件是IP-1，都没有密钥的参与。在已知明文攻击

24、之下， IP和IP-1都可以剥去，没有任何安全性功能。lDES的S盒的设计细节没有公开。lDES的用户密钥长度（有效长度）是56比特，对于越来越快速的穷举搜索攻击，安全强度似乎已经不够了。2022-2-2452l设DES的加密算法为y=DES(x, k)，其中k为密钥种子，则当x和k都取补时，函数值取补。l对于密钥种子k，如果DES-1(, k)=DES(, k)，则称k为一个弱密钥。根据DES的密钥扩展算法，不难看出有4个弱密钥：k=(0, , 0)；k=(1, , 1)；k=(0, , 0, 1, , 1)；k=(1, , 1, 0, , 0)。l如果有两个密钥种子k1和k2，使得DES(

25、, k1)=DES(, k2)，则称(k1, k2)为一个半弱密钥对。已经发现DES有12个半弱密钥对。 （以上三条说明，明文、密钥、密文之间存在一些简单的关系，随机性不足）2022-2-2453l研究表明，要使密文每个比特都是明文所有比特和密钥所有比特的复合函数，需要将DES的轮函数进行5轮以上的迭代。l人们用2检验证明，用随机密钥种子并8轮迭代，就能使明文和密文基本上不相关。从这一角度来看，DES算法的16轮迭代是足够了。2DESlMeet-in-the-middle attack!Effective key length is just 57 bits!EXDX1X2X256m1m2m2

26、56Try all possible keys= ?For key length n,total work is “only” 2n + 2n = 2n+1mm三重三重DES加密加密加密：C=Ek1Dk2Ek1 P解密：P =Dk1Ek2Dk1C三重三重DES加密加密 两个密钥的三重DES称为称为加密-解密-加密方案，简记为，简记为EDE(encrypt-decrypt-encrypt)。l此方案已在此方案已在ANSI X9.17和和ISO 8732标准中采用，并在保密增标准中采用，并在保密增强邮递强邮递(PEM)系统中得到利用。系统中得到利用。l破译它的穷举密钥搜索量为破译它的穷举密钥搜索量

27、为2112 51035量级，而用差分分析量级，而用差分分析破译也要超过破译也要超过1052量级。此方案仍有足够的安全性。量级。此方案仍有足够的安全性。l三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用2022-2-2463AES-分组密码分组密码Rijndael 高级加密标准高级加密标准AESl1997年4月5日：NIST发起征集AES(Advanced Encryption Standard)算法，要求具有128比特的分组长度，并支持128、192和256比特的密钥长度，且要求AES能在全世界范围内免费使用 l1998年8月20日：NIST召开了第一次AES候选会议

28、，并公布了15个AES候选算法。后来，NIST又筛选出5个AES候选算法 (MARS, RC6, Rijindael, SERPENT, Twofish)l2000年10月：NIST宣布由比利时的密码专家Joan Daemen博士和Vincent Rijmen博士开发的Rijndael算法做为AES的最终算法2022-2-24计算机科学与技术学院64AES的评估准则的评估准则l安全性安全性l评估准则中最重要因素，包括下述要点：l算法抗密码分析的强度l稳定的数学基础l算法输出的随机性l与其他候选算法比较的相对安全性l代价代价l主要包括：许可要求，在各种平台上的计算效率(速度)和内存空间的需求l算

29、法和实现特性算法和实现特性l主要包括：灵活性、硬件和软件适应性、算法的简单性等2022-2-24计算机科学与技术学院65AES的设计者的设计者lJoan Daemen（1965-） ：比利时密码学家。还参与设计设计了 MMB, Square, SHARK, NOEKEON, 3-Way, 和 BaseKing等分组密码l1988年， Daemen毕业于鲁汶大学(Katholieke Universiteit Leuven)土木工程系. 随后参加了COSIC研究小组并进行分组密码, 流密码和密码散列函数的设计和分析工作l1995年Daemen完成了他的PhD2022-2-24计算机科学与技术学院

30、66v Vincent Rijmen（1970-），比利时密码学家。也是hash函数WHIRLPOOL和分组密码Anubis，KHAZAD，Square，NOEKEON和SHARK的设计者之一v 1993年获得鲁汶大学电子工程专业学位v 1997年获得鲁汶大学ESAT/COSIC实验室的博士学位，并继续在实验室做博士后工作RIJNDAELRIJNDAEL的数学基础的数学基础有限域有限域GF(28)；系数在系数在GF(28)上的多项式上的多项式 。群的定义:u一些数字组成的集合 u一个加法运算，运算结果属于此集合（封闭性）u服从结合律。有单位元，逆元 u如果是可交换的，则成为abelian群环环

31、u环: uabelian 群，及一个乘法运算u满足结合律与加法的分配律u如果加法满足交换律, 则称交换环u例：整数 mod N （for any N ）域域u域：uabelian 加群uabelian 乘群 (ignoring 0) u环 u例： integers mod P （ P 为素数）Galois Galois 域域u如果 p是素数,则模运算modulo p 形成 Galois Field modulo p .记为： GF(p) u许多加密运算需要指数运算, GF(p) 中的指数运算ub = ae mod pu重复乘法运算ueg. 75 = 7.7.7.7.7 u计算指数的快速有效算法

32、u思想：重复平方运算u计算最终结果的乘法运算2022-2-2472分组密码分组密码Rijndael有限域有限域GF(28) GF(28)上的元素通常采用字节值来表示。但为了更方便地运算，此处对GF(28)上的元素采用传统的多项式表示法。由b7b6b5b4b3b2b1b0构成的一个字节b看成系数在0, 1中的多项式：b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0。在多项式表示中，GF(28)上两个元素的和仍然是一个次数不超过7的多项式，其系数是原来两个元素对应系数的模2加（比特异或）。要计算GF(28)上的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)

33、上两个元素的乘积就是这两个多项式的重模积。（次数模此8次不可约多项式，系数模2）。2022-2-2473分组密码分组密码Rijndael此8次不可约多项式称为模多项式。对于RIJNDAEL密码，模多项式确定为m(x)= x8+x4+x3+x+1 。模多项式的二进制表示为9比特100011011，十六进制表示为“11B” 。以下是一个乘法的例子： (x6+x4+x2+x+1)(x7+x+1)=x7+x6+1(mod2, mod m(x)；或者“01010111”“10000011”=“11000001” ；或者“57”“83”=“C1” 。举例举例(x6+x4+x2+x+1)(x7+x+1)=

34、x13+x11+x9+x8+x7+x7+x5+x3+x2+x+ x6+x4+x2+x+1 =x13+x11+x9+x8+x6+x5+x4 +x3+x+1(x13+x11+x9+x8+x6+x5+x4 +x3+1)mod m(x)= x7+x6+1100011011 10101101111001 100011011 100000011001 100011011 11000001(x6+x4+x2+x+1)(x7+x+1)= x7+x6+12022-2-2475分组密码分组密码Rijndael另外，对于uGF(28)，u0，计算u的乘法逆元v可直接采用GF(2)上多项式的欧几里德扩充算法得 u(x

35、)u(x)+m(x)h(x)=1(mod2)，或u(x)u(x)=1(mod2, modm(x)，其中u=u(x)，v=v(x)。所计算出的v就是u的乘法逆元，即u(x)v(x)=1或者uv=1。 2022-2-2476分组密码分组密码Rijndael系数在系数在GF(28)上的多项式上的多项式 4个字节的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对应系数相加；换句话说，多项式的加法就是4字节向量的逐比特异或。 多项式的乘法运算必须要取模M(x)=x4+1，这样使得次数小于4的多项式的乘积仍然是一个次数小于4的多项式。即(a3x3+a2x2+a1x+a0)(b3x

36、3+b2x2+b1x+b0)=c3x3+c2x2+c1x+c0 ，2022-2-2477分组密码分组密码Rijndael其中 c0=a0b0+a1b3+a2b2+a3b1；c1=a0b1+a1b0+a2b3+a3b2；c2=a0b2+a1b1+a2b0+a3b3；c3=a0b3+a1b2+a2b1+a3b0。注意所有的加法和乘法运算都是在域GF(28)中的。可以将上述计算表示为 321001233012230112303210aaaabbbbbbbbbbbbbbbbcccc2022-2-2478分组密码分组密码Rijndael定理定理 系数在GF(28)上的多项式b3x3+b2x2+b1x+b

37、0是模(x4+1)可逆的，当且仅当以下矩阵在GF(28)上可逆。0123301223011230bbbbbbbbbbbbbbbb2022-2-2479分组密码分组密码RijndaelRIJNDAELRIJNDAEL的设计标准的设计标准RIJNDAEL密码的设计力求满足以下密码的设计力求满足以下3条条标准：标准：l（1）抗所有已知的攻击。）抗所有已知的攻击。l（2）在多个平台上速度快，编码紧凑）在多个平台上速度快，编码紧凑。l（3）设计简单。）设计简单。2022-2-2480分组密码分组密码RijndaelRIJNDAELRIJNDAEL的算法说明的算法说明 RIJNDAEL的明文分组称为状态，

38、所有的操作都在状态之间进行。状态可以用以字节为元素的矩阵阵列图表示，该阵列有4行，列数记为Nb，Nb等于分组长度除以32。密钥种子（在原文中称为密码密钥Cipher Key）类似地用一个以字节为元素的矩阵阵列图表示，该阵列有4行，列数记为Nk，Nk等于分组长度除以32。2022-2-2481分组密码分组密码Rijndael下表就是Nb=6的状态和Nk=4的密钥种子。一个明文分组按a00a10a20a30a01a11a21a31的顺序影射到状态阵列中。同理，密钥种子按k00k10k20k30k01k11k21k31的顺序影射到密钥种子阵列中。 a00 a01a02a03a04a05a10a11a

39、12a13a14a15a20a21a22a23a24a25a30a31a32a33a34a35k00 k01k02k03k10k11k12k13k20k21k22k23k30k31k32k332022-2-2482分组密码分组密码Rijndael 轮函数轮函数 RIJNDAEL的轮函数由四个不同的计算部件所组成，分别是：l字节代替（ByteSub）；l行移位（ShiftRow）；l列混合（MixColumn）；l加密钥（AddRoundKey）。 1. 字节代替（字节代替（ByteSub） 是将状态阵列的每个字节做相同的变换，该变换由以下两个子变换所合成： 2022-2-2483（1）首先，将

40、字节看作GF(28)上的元素，映射到自己的乘法逆；0字节影射到它自身。 （2）其次，将字节看作GF(2)上的8维向量，做如下的（GF(2)上的；可逆的）仿射变换： 0110001111111000011111000011111000011111100011111100011111100011111100017654321076543210 xxxxxxxxyyyyyyyy2022-2-2484以上两个子变换所合成的字节代替采用一个8比特输入/8比特输出的S盒来实现。2. 行移位（行移位（SHiftRow） 是将状态阵列的各行进行循环移位，不同状态行的位移量不同。第0行不移动，第一行循环左移C1

41、个字节，第二行循环左移C2个字节，第三行循环左移C3个字节。位移量(C1, C2, C3)的选取与Nb有关，当Nb=4或6时一般取(C1, C2, C3)=(1, 2, 3)。 3. 列混合（列混合（MixColumn） 是将状态阵列的每个列视为系数在GF(28)上、次数小于4的多项式，被同一个固定的多项式c(x)进行模x4+1乘法。当然要求c(x)是模x4+1可逆的多项式，否则列混合变换就是不可逆的，因而会使不同的明文分组具有相同的对应密文分组。RIJNDAEL的设计者所给出的c(x)为（系数用16进制数表示）： 2022-2-2485c(x)=03x3+01x2+01x+02 c(x)是与

42、x4+1互素的，因此是模x4+1可逆的。由前面的讨论知，将状态阵列的每个列视为GF(28)上的4维向量，列混合运算可表示为GF(28)上的可逆线性变换：3210321002010103030201010103020101010302aaaabbbb2022-2-2486这个运算需要做GF(28)上的乘法。但由于所乘的因子是三个固定的元素02、03、01，所以这些乘法运算仍然是比较简单的（注意到乘法运算所使用的模多项式为m(x)= x8+x4+x3+x+1）。设一个字节为b=(b7b6b5b4b3b2b1b0)，则b01=b； b02=(b6b5b4b3b2b1b00)+(000b7b70b7b

43、7)； b03=b01+b02。（请注意，加法为取模2的加法，即逐比特异或）2022-2-24874. 加密钥（加密钥（AddRoundKey） 是将单轮子密钥阵列简单地与课文阵列进行比特异或。这里当然要求子密钥阵列与课文阵列是同阶的。 综上所述，组成RIJNDAEL轮函数的计算部件简洁快速，功能互补。轮函数的伪C代码如下：lRound (State, RoundKey)ll ByteSub (State)l ShiftRow (State)l MixColumn (State)l AddRoundKey (State, RoundKey)l AES的分组的分组lAES首先将明文按字节按字节分

44、成列组列组l状态状态(State)：密码运算的中间结果称为状态2022-2-2488a00a01a02a03a10a11a12a13a20a21a22a23a30a31a32a331. 字节代替（字节代替（ByteSub）l 2022-2-24计算机科学与技术学院892022-2-24902. 行移位（行移位（SHiftRow）2022-2-24913. 列混合（列混合（MixColumn）2022-2-24922022-2-24934. 加密钥（加密钥（AddRoundKey）2022-2-2494结尾轮是特殊轮，轮函数与前面各轮不同，将MixColumn这一步去掉。即为lFinalRoun

45、d (State, RoundKey)ll ByteSub (State)l ShiftRow (State)l AddRoundKey (State, RoundKey)l 在以上的伪C代码记法中， Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey 等函数都在指针State、RounKey所指向的阵列上进行运算。 2022-2-2495分组密码分组密码Rijndael迭代的轮数记为Nr，Nr与Nb和Nk有关，其中Nb是明文阵列的列数， Nk是密钥种子阵列的列数。下表给出了Nr与Nb和Nk的关系。 NrNb=4Nb=6Nb=8Nk=

46、4101214Nk=6121214Nk=8141414子密钥生成算法子密钥生成算法l包括两个部分：密钥扩展和轮密钥选取l密钥比特总数分组长度密钥比特总数分组长度(轮数轮数1)l分组长度=128和轮数=10时，轮密钥长度为128(101)1408比特lAES首先将种子密钥输入到一个4*4矩阵中，每列组成1个字2022-2-2496K K0 0K K4 4K K8 8K K1212K K1 1K K5 5K K9 9K K1313K K2 2K K6 6K K1010K K1414K K3 3K K7 7K K1111K K1515w0w0w1w1w2w2w3w3密钥扩展密钥扩展2022-2-24

47、97w4i-4w4i-4w4i-3w4i-3w4i-2w4i-2w4i-1w4i-1w4iw4iw4i+1w4i+1w4i+2w4i+2w4i+3w4i+3l TT函数函数l由3部分组成：字循环、字代替和轮常量异或2022-2-2498w4i-1SubBytesByteRote+RconT(w4i-1)+w4i-4w4i2022-2-2499函数ByteRote(a,b,c,d)= (b,c,d,a)，即是输入字的1字节循环 K0,0K0,1K0,2K0,3K1,0K1,1K1,2K1,3K2,0K2,1K2,2K2,3K3,0K3,1K3,2K3,3ByteRoteK0,0K0,1K0,2K

48、1,3K1,0K1,1K1,2K2,3K2,0K2,1K2,2K3,3K3,0K3,1K3,2K0,3轮常量轮常量Rcon的右边3个字节总是0，记为Rconj=(RCj,0,0,0)j12345678910RCj(16进制)01020408102040801B36lRCj的构造： RC1=0 x01; RCj=2*RCj-1; j=2,3,4,5,6,7,8,9,10l密钥的使用：2022-2-24100w0w1w2w3w4w5w6w7w8w9w10轮密钥轮密钥0轮密钥轮密钥1轮密钥轮密钥22022-2-24101针对Nk6，扩展算法为lKeyExpansion (byte Key4*Nk W

49、Nb*(Nr+1)ll For (j=0; j Nk; j+)l Wj=(Key4*j, Key4*j+1, Key4*j+2, Key4*j+3;l For (j=Nk; j6，扩展算法为lKeyExpansion (byte Key4*Nk WNb*(Nr+1)ll For (j=0; j Nk; j+)l Wj=(Key4*j, Key4*j+1, Key4*j+2, Key4*j+3;l For (j=Nk; jNb*(Nr+1); j+)l l temp=Wj-1;l if (j% Nk=0)l temp=SubByte (RotByte (temp)Rconj/Nk;l else

50、if (j% Nk=4)l temp=SubByte (temp);l Wj=Wj- Nktemp;l l 2022-2-24103解释：解释：j% Nk= 表示j除以 Nk的余数。SubByte(W)表示输出字的每一个字节都是用RIJNDAEL的S盒作用到输入字W的对应字节所得到的。RotByte (W)表示1字节的循环移位 。Rconj/Nk 为轮常数字，其值为（字节用16进制表示，同时理解为GF(28)上的元素）：lRcon1=(01, 00, 00, 00)lRconj=(02)j-1, 00, 00, 00); j=2, 3, 。表示逐比特异或。AES的等价解密的等价解密lAES的加

51、解密过程不相同加解密过程不相同，需要使用相应变换的逆变换，并且各个变换的使用顺序也不一样：l逆行移位l逆字节代换l轮密钥加l逆列混合l这使得这使得AES的加解密使用不同的软件和硬件模的加解密使用不同的软件和硬件模块块l能否使得加解密使用相同的顺序哪？能否使得加解密使用相同的顺序哪？2022-2-24104等价的解密过程等价的解密过程l交换逆行移位和逆字节代换交换逆行移位和逆字节代换l逆行移位影响字节的顺序，但不改变自己的内容，同时也不以自己的内容决定它的变换l逆字节代换影响自己的内容，但不改变字节的顺序，同时也不依赖字节的顺序来进行它的变换l因此，两个操作可以交换l交换轮密钥加和逆列混合交换轮

52、密钥加和逆列混合l轮密钥加和逆列混合都不改变矩阵中字节的顺序：2022-2-24105( )()iiss逆列混合（wj）=逆列混合逆列混合 wj例子例子l所以我们得到如下的等价变形：2022-2-241063,003,113,2233,33,03,13,23,3 0E0B0D09 090E0B0D0D090E0B 0B0D090E 0E0B0D090090E0B0D0D090E0B0B0D090ESW jSW jSW jW jSSSSS0123 E0B0D09 090E0B0D0D090E0B 0B0D090E W jW jW jW j轮密钥求逆轮密钥求逆等价操作等价操作2022-2-2410

53、7逆列混合逆列混合+AddRoundKey轮密钥加轮密钥加状态矩阵状态矩阵逆列混合逆列混合+AddRoundKey轮密钥加轮密钥加状态矩阵状态矩阵轮密钥轮密钥逆列混合逆列混合2022-2-24108分组密码分组密码RijndaelRIJNDAEL的的解密算法解密算法 RIJNDAEL不是加解密相似的。RIJNDAEL密码的设计显然忽视了解密算法的性能。其中的原因有两个：一是解密算法性能的重要性远不如加密算法性能；在分组密码的许多应用中，解密算法是不使用的，比如消息认证码（MAC）、消息加密的CFB模式或OFB模式等。二是忽视解密算法性能会使加密算法的性能设计更加容易。 Add Round Ke

54、yInverse mix colsAdd round keyInverse sub bytesInverse shift rowsAdd round keyMix ColumnsShift RowsAdd Round KeyInverse sub bytesInverse shift rowsInverse mix colsAdd round keyInverse sub bytesInverse shift rowsAdd round keySubstitute BytesAdd round keyShift RowsSubstitute BytesAdd round keySubstitu

55、te BytesShift RowsMix ColumnsExpand Key.w0,3w4,7w36,39w40,43PlaintextPlaintextCiphertextCiphertextRound 1Round 9Round 10Round 1Round 9Round 10国际数据加密标准国际数据加密标准IDEAl国际数据加密算法国际数据加密算法IDEA(International Data Encryption Algorithm):1990年由瑞士苏黎世联邦工业大学的来学嘉和James Messey提出，1992年最终完成l128位密钥加密64位明文分组，穷举分析需要1038次试

56、探，目前尚无有效破译方法l密码强度：l扰乱：密文以复杂交错的方式依赖明文和密钥l扩散：每个明文比特都应该影响每个密文比特2022-2-24计算机科学与技术学院110lIDEA设计思想：基于“相异代数群上的混合相异代数群上的混合运算运算” l通过连续使用三个“不相容”的群运算作用于两个16比特子块来获得l算法用硬件和软件实现都很容易，比DES在实现上快得多 l近年来提出的分组密码算法中的一个很成功的方案，已在PGP中采用2022-2-24计算机科学与技术学院111来学嘉来学嘉l来学嘉（来学嘉（1954-）国际著名密码学家。瑞士籍华人l1978-1982，西安电子科技大学本科；l1982-1984

57、，西安电子科技大学信息安全研究所硕士研究生；l1985到瑞士ETH Zurich, Signal and Information Processing Laboratory；1988-1992在该实验室攻读博士并取得博士学位l主要工作：密码学，IDEA密码的共同发明者(连同J.L. Massey 教授)。他的两位导师是著名密码学家肖国镇教授和瑞士ETH的Massey教授l1992年，博士论文“On the Design and Security of Block Ciphers”给出了 IDEA 密码算法l现任上海交通大学计算机科学与工程系教授2022-2-24计算机科学与技术学院112IDE

58、A的三种基本操作的三种基本操作lIDEA的基本操作是将两个16位的值映射成一个16位的值l异或，l整数模216(65536)加 l整数模216+1(65537)乘例如：0000000000000000 1000000000000000= 1000000000000001因为：216 x 215 mod (216+1) = 215 + 12022-2-24计算机科学与技术学院113三种运算的代数结构三种运算的代数结构三种运算都是交换群运算（Abel群运算）。运算 的单位元是(0000000000000000)。运算 的单位元是(0000000000000000)。运算 的单位元是(0000000

59、000000001)。关于群运算，任何非单位元的次数都是2。关于群运算，非单位元的次数有2，22，23，216。关于群运算，非单位元的次数有2，22，23，216。三种运算的密码学性质三种运算的密码学性质设z=xy。则z的一个比特仅仅依赖于x和y在相同位置上的比特值，毫无扩散能力。设z=x y。则z的一个比特依赖于x和y在相同位置及以下位置上的比特值，具有单向扩散能力。设z=x y。则z的一个比特依赖于x和y在所有位置上的比特值，具有双向扩散能力。与的结构差异很大； 与虽然具有同构关系，但这种同构关系却表现为一种“离散对数”的关系。将它们组合在一起使用，可以破坏任何一种群结构。IDEA加密加密

60、2022-2-24计算机科学与技术学院116 IDEA轮函数轮函数2022-2-24计算机科学与技术学院117X1X2X3X4Z1(i)+Y1Y2Y3Y4Z2(i)Z3(i)Z4(i)Z6(i)Z5(i)+在每轮中，4个子块分别和密钥的6个16比特子块及中间结果进行3种不同的群运算，即XOR、加运算和乘运算在两轮之间，第2和第3个子块进行交换在每一轮中，执行的过程如下在每一轮中，执行的过程如下(1) 输入子块X1和第1个子密钥块进行“乘”运算(2) 输入子块X2和第2个子密钥块进行“加”运算(3) 输入子块X3和第3个子密钥块进行“加”运算(4) 输入子块X4和第4个子密钥块进行“乘”运算(5) 将第