现在密码学第2章信息保密技术(2)

第二章信息保密技术（2）2004年9月国际数据加密算法（IDEA）IDEA（InternationalDataEncryptionStandard）由瑞士联邦理工学院的XuejiaLai和JamesMassey于1990年提出，分组长度为64-bit，密钥长度为128-bit。能抵抗差分密码分析，目前还没有发现明显的安全漏洞，应用十分广泛。著名的电子邮件安全软件PGP就采用了IDEA进行数据加密。IDEA的混淆特性IDEA的混淆特性是经由混合下述三种操作而成的：以比特为单位的异或运算，用＋表示。定义在模（mod65536）的模加法运算，其操作数都可以表示成16位整数，用＋表示这个操作。定义在模＋1（mod65537）的模乘法运算。162162IDEA的混淆特性（续）由于上面3个操作，基于以下的“非兼容性“（Incompatible），当应用在IDEA时，可以充分发挥出混淆的特性。三种中的任意两个，都不满足“分配律”，例如运算⊙及＋，任意a，b，c∈，则有：a＋(b⊙c)≠（a＋b）⊙（a＋c）3个操作中的任意2个，都无法满足“结合律”。例如运算＋及＋，任意a，b，c∈，a＋(b＋c)≠（a＋b）＋（a＋c）因此在IDEA的设计中，使用了这三种操作混合组合来打乱数据。攻击者无法用化简的方式来分析密文与明文及密钥之间的关系。162F162FIDEA的扩散特性IDEA的扩散特性是建立在乘法/加法（MA）的基本结构上。该结构一共有4个16位的输入，两个16位的输出。其中的两个输入来源于明文，另两个输入是子密钥，源于128位加密密钥。Lai经过分析验证，数据经过8轮的MA处理，可以得到完整的扩散特性。MA基本结构F1F2⊙⊙G1G2Z5Z6子密钥（16位）明文输入（16位）明文输入（16位）子密钥（16位）输出（16位）输出（16位）（i）（i）＋＋IDEA算法描述IDEA是由8轮相似的运算和随后的一个输出变换组成64位的明文分组在每一轮中都是被分成4份，每份从16位为一单元来处理每一轮中6个子密钥×8＋输出变换4个子密钥＝52个子密钥每一轮的运算又分成两部分：第一部分即变换运算。利用加法及乘法运算将4份16位的子明文分组与4个子密钥混合，产生4份16位的输出。这4份输出又两两配对，以逻辑异或将数据混合，产生两份16位的输出。这两份输出，连同另外的两个子密钥成为第二部分的输入。第二部分即用以产生扩散特性的MA运算。MA运算生成两份16位输出。MA的输出再与变换运算的输出以异或作用生成4份16位的最后结果。这4份结果即成为下一轮运算的原始输入。子密钥的产生首先将128位加密密钥以16位为单位分成8组，其中前6组作为第一轮迭代运算的子密钥，后2组用于第二轮迭代运算的前2组子密钥。然后将128位密钥循环左移25位，再分为8组子密钥，其中前4组用于第二轮迭代运算，后4组用作第三轮迭代运算的前4组子密钥，依此直至产生全部52个子密钥。这52个子密钥的顺序为：Z1(1)，Z2(1)，…，Z6(1)；Z1(2)，Z2(2)，…，Z6(2)；…；Z1(8)，Z2(8)，…，Z6(8)；Z1(9)，Z2(9)，Z3(9)，Z4(9)，IDEA的解密本质上与加密过程唯一不同的是解密密钥子块Ki(r)是从加密密钥子块Zi(r)按下列方式计算出来的：其中表示的模（＋1）的乘法逆，亦即，表示的模的加法逆，亦即＋。8,,3,2))(,,,)((),,,(1)10(4)10(2)10(31)10(1)(4)(3)(2)(1rZZZZKKKKrrrrrrrr9,1))(,,,)((),,,(1)10(4)10(3)10(21)10(1)(4)(3)(2)(1rZZZZKKKKrrrrrrrr8,,2,1),(),()9(6)9(5)(6)(5rZZKKrrrr1Z16211ZZ⊙ZZ162162ZIDEA的设计理念IDEA的设计主要考虑是针对16位为单位的处理器。因此无论明文、密钥都是分成16位为一个单元进行处理。IDEA使用了三种简单的基本操作，因此在执行时可以达到非常快的操作。在33MHz386机器上运行，加密速度可以达到880kb/s。经过特殊设计的VLSI芯片，更可以达到55Mb/s的速度。IDEA采用三种非常简单的基本操作，混合运算，以达到混淆目的。而相对地，DES采用经过特殊设计的S-盒，而对这些S-盒的分析又不对外公开。相较之下，IDEA的安全性评估，较易被大家接受。IDEA的整体设计非常规律。MA运算器及变换运算器重复使用在系统上。因此非常适合VLSI实现。AES算法1997年4月15日，美国国家标准技术研究所（NIST）发起征集AES（AdvancedEncryptionStandard)的活动，目的是为响应公众日益增长的替换DES的要求，确定21世纪的数据加密标准。1997年9月12日正式公布了通告。通告要求AES比3DES快而且安全，分组长度为128-bit，密钥长度为128、192及256-bit。NIST原名为NBS（国家标准局），是美国商业部下属的一个机构，1988年改为现名。著名的DES加密算法即是由它们颁布的。1998年8月20日公布了符合基本要求的15个算法。1999年3月22日从中选出了5个。2000年4月25日对5个算法进行了讨论。2000年10月2日，NIST公布了最终的获胜者是Rijndael算法，比利时人设计。AES算法能有效地抵抗差分分析与线性攻击。但加密、解密过程不完全对称，使用了不同的代码和S-盒，所以实现起来占用资源相对多一些。AES算法-Rijndael算法数据块长度和密钥长度可以是128比特、192比特和256比特，其原型是Square算法。设计策略——宽轨迹策略（WideTrailStrategy）。宽轨迹策略针对差分分析和线性分析提出，其最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼进的偏差的界。AES算法-Rijndael算法（续）Rijndael采用的是代替/置换网络。每一轮由以下三层组成：线性混和层——确保多轮之上的高度扩散；非线性层——由16个S－盒并置而成，起到混淆的作用；密钥加层——子密钥简单地异或到中间状态上。S－盒选取的是有限域GF（28）中的乘法逆运算，它的差分均匀性和线性偏差都达到了最佳。AES算法-Rijndael算法（续）在加密之前，对数据块做预处理。首先，把数据块写成字的形式，每个字包含4个字节，每个字节包含8比特信息。其次，把字记为列的形式。这样数据块就可以记为以下的形式：其中，每列表示一个字每个表示一个8比特的字节，即),,,(,3,2,1,0jjjjjaaaaajia,)2(),1/(])[2(8,48GFaxxGFajij如用Nb表示一个数据块中字的个数，那么Nb＝4，6或8。类似地，用Nk表示密钥中字的个数，那么Nk＝4，6或8。例如，Nk＝6的密钥可以记为以下的形式：算法轮数Nr由Nb和Nk共同决定，具体值见下表NrNb=4Nb=6Nb＝8Nk＝4101214Nk＝6121214Nk＝8141414Rijndael算法加密过程字节代换行移变换列变换列变换行移变换字节代换行移变换字节代换子密钥（0）子密钥（1）最后一轮第Nr-1轮明文块密文块第一轮子密钥（Nr）子密钥（Nr-1）Rijndael算法加密过程（续）注1：字节代换（ByteSub）是作用在字节上的一种非线性字节变换。由以下两个变换合成。首先，把每个字节看作一个系数在{0,1}上的多项式，在有限域中取它相对于模多项式的乘法逆，其中，零多项式的乘法逆映射到自身。其次，再使用下式所定义的GF(2)域上的放射变换，作用在所求得的乘法逆上。)2(8GF1)(248xxxxxm011000111111100001111100001111100001111110001111110001111110001111110001)(1,,jijiaaByteSub其中是在中的乘法逆，记作：注2：行移变换在此变换的作用下，数据块的第0行保持不变，第1行循环左移位，第2行循环左移位，第3行循环左移位，其中移位值和与加密块长Nb有关。1,jia1,jiajia,)2(8GF))(),(),(),(()(,3,2,1,0jjjjjaByteSubaByteSubaByteSubaByteSubaByteSubNb移位值C1C2C3412361238134注3：列混合变换（MixColumn）式中看成环中的元素，乘法是在环中进行的。注意，因为与互素，所以有可逆元caaMixColumnjj)(ja)1/(])[2(48xxGF'02''01''01''03')'02','01','01','03('23xxxc)1/(])[2(48xxGFc14xc'0''09''0''0')'0','09','0,'0('23ExxDxBEDBd子密钥的生成加密和解密过程分别需要Nr＋1个子密钥步骤：1.主密钥的扩展2.子密钥的选取根据和两种不同的情况，采取不同的主密钥扩展方式。110Nkkkk6Nk6Nk主密钥的扩展对于当时，定义。当时：若，定义；若，令定义其中，Rotate(a,b,c,d)是左移位，即Rotate(a,b,c,d)＝（b,c,d,a）。6Nk1,,1,0Nkiiikw1)1(NrNbiNk0modNki1iNkiiwww0modNki)2(][81GFxiRCi)1/(])[2()'00','00','00'],[(][48xxGFiRCiRcon]/[))((1NkiRconwRotateByteSubwwiNkii对于当时，定义。当时：若且，定义若，令，定义若，定义这样，就得到了Nb(Nr+1)个字。第i个子密钥就是6Nk1,,1,0Nkiiikw1)1(NrNbiNk0modNki4modNki1iNkiiwww0modNki)2(][81GFxiRCi)1/(])[2()'00','00','00'],[(][48xxGFiRCiRcon]/[))((1NkiRconwRotateByteSubwwiNkii4modNki)(1iNkiiwByteSubww1)1(1iNbiNbiNbwwwjwRijndael解密算法结构与加密算法相同，其中的变换为加密算法变换的逆变换，且使用了一个稍有改变的密钥编制行移变换的逆是状态的后三行分别移动个字节，这样在i行j处的字节移到处。字节代换的逆是Rijndael的S-盒的逆作用到状态的每个字节，这可由如下得到：先进行仿射的逆变换，然后把字节的值用它的乘法逆代替。列混合变换的逆类似于列混合变换，状态的每一列都乘以一个固定的多项式：321,,CNbCNbCNbNbCNbjimod)()(xd'0''09''0''0')(23ExxDxBxd2.2.3分组密码的分析方法解密与密码分析解密是加密的逆过程，是指掌握密钥和密码算法的合法人员从密文恢复出明文的过程。密码分析则是指非法人员对密码的破译，而且破译以后不会告诉对方。共同点“解密（脱密）”和“密码分析（密码破译）”都是设法将密文还原成明文。不同点二者的前提是不同的，“解密（脱密）”掌握了密钥和密码体制，而密码分析（破译）则没有掌握密钥和密码体制分组密码的分析方法(续）根据攻击者掌握的信息，可将分组密码的攻击分为以下几类：唯