第四章 传统密码学与典型算法

第4章对称密码体制与典型算法本章内容分组密码体制AES密码算法Camellia密码算法序列密码1第4章对称密码体制与典型算法教学要求了解对称密码体制的基本概念掌握分组密码的基本原理了解分组密码的操作模式掌握AES和Camellia密码算法了解序列密码的基本原理2密码体制概述密码体制对称密码体制非对称密码体制分组密码体制序列密码体制传统密码体制公钥密码体制加、解密密钥相同，保密加、解密密钥不同，一个保密，一个公开公钥密码体制也是分组密码体制3对称密码体制的数学模型44.1分组密码体制特点明文、密文组长度为n，密钥长度为t，密钥量为2t密文中的任一位数字与该组明文所有的数字均有关每组明文使用相同密钥加密本质是{0，1，…，2n-1}集合上的自映射或置换5一、分组密码算法的基本要求分组长度足够大防止明文穷举法奏效密钥量足够大

防止密钥穷举法奏效密码变换足够复杂使对手除了用穷举法破译外，无其它捷径可走，有效对抗统计破译法6问题与对策分组长度足够大：代换网络十分复杂，难以控制与实现对策

将分组划分为几个小段，分别设计这些小段的代换网络密钥量足够大：密码系统十分复杂，同样难以控制与实现对策

概率加权法：设计多个子系统，使用时随机抽取乘积密码法：设计多个子系统，对明文多次加密密码变换足够复杂：抗统计破译法的要求，难以简单实现

对策扩散法：将每1位明文和密钥数字的影响扩散到每1位密文数字混淆法：使密文与明文、密钥的统计特性复杂化揉面团乘积密码置乱主要实现扩散，非线性代换主要实现混淆7二、分组密码算法原理的典型结构

Feistel密码结构加密解密特点①采用多轮乘积密码迭代，实现扩散与混淆。②每轮仅改变一半数据，且运算结束时左、右各半数据交换位置。③用于改变数据的轮函数F通常包括代换和置乱操作。实现置乱的装置常称为P盒，实现代换的装置常称为S盒，它们分别实现扩散与混淆。④解密算法与加密算法本质上相同，仅仅是轮密钥颠倒顺序使用。⑤密码的安全性能取决于分组长度、密钥位数、迭代轮数、子密钥产生算法和轮函数F等参数。为了保障密码的安全性能，这些参数必须精心选择，精心设计。8SP网络Substitution代换，实现混淆Permutation换位，实现扩散迭代密码结构，实现乘积密码9SP网络的两种基本操作10DES的一般设计准则相关免疫性随机性雪崩效应特性完全性非线性11三、分组密码的操作模式电子密码本（ECB）模式密码分组链接（CBC）模式计数器（CRT）模式密码反馈（CFB）模式输出反馈（OFB）模式121、电码本（ECB）模式优、缺点操作简单速度快无差错传播单表代换不适合格式固定或变化比较少的长数据（如图象数据）加密132、密码分组链接(CBC)模式优、缺点操作较简单速度较快多表代换适用面广差错传播1组143、计数器（CTR）模式优点操作较简单速度较快多表代换适用面广无差错传播154、密码反馈（CFB）模式优、缺点多表代换适用面广操作复杂速度较慢差错传播大165、输出反馈（OFB）模式优、缺点多表代换适用面广无差错传播操作复杂速度较慢17四、典型的分组密码算法DES：数据加密标准算法IDEA：国际数据加密算法AES：高级加密标准算法Camellia：欧洲加密标准算法184.2AES密码算法荣代尔Advanced

Encryption

Standard1997年9月12日：美国NIST提出征集该算法的公告1998年8月20日：NIST召开了第一次候选大会，并公布了15个候选算法1999年3月22日：NIST从15个候选算法中公布了5个进入第二轮选择：MARS，RC6，Rijindael，SERPENT和Twofish2000年10月2日：以安全性、性能、大小、实现特性为标准而最终选定了Rijndael算法2001年：正式发布AES标准一、AES的诞生背景19202122Rijndael

算法是由两位比利时的密码专家发明的，它很快而且所需的内存不多，且算法非常可靠Rijndael

算法的设计策略是针对差分和线性分析提出来的，是一个分组迭代密码，具有可变的分组长度和密钥长度Rijndael

汇聚了安全性能、效率、可实现性和灵活性等优点23破译时间宇宙年龄1011年24二、AES的算法结构采用Square结构10/12/14轮迭代251、AES的数据结构按列填充26基本运算字节代换SubBytes行移位ShiftRows列混合MixColumns轮密钥加AddRoundKeySquare结构（方形结构）有10/12/14轮迭代2、AES的算法结构最后1轮没有列混合27采用乘积密码迭代，实现扩散与混淆。每一轮都使用代换和混淆技术并行地处理整个数据分组。无论是加密还是解密，除了最后一轮少了列混合运算外，其它各轮都是按照相同顺序依次执行四种基本运算（解密时为四种基本运算的逆运算）。解密算法完全是加密算法的倒推，加、解密原理清晰，便于理解。和其它分组密码相同，轮密钥在解密时颠倒顺序使用。AES结构特点28利用S盒将中间态s中的每个字节非线性变换为另一个字节。实现每个字节数据中各位的混淆。

三、AES的基本运算1、字节代换运算SubBytes29S盒的构造方法第一步：将S盒的输入字节首先映射为它在有限域GF(28)中的乘法逆元，{00}映射为它自身。使用不可约多项式。任何非0元素都存在乘法逆元。30记S盒输入的乘法逆元记S盒输出对做仿射变换，得到S盒输出或其中ci为{63}的第i位：S盒的构造方法第二步：31S盒变换举例乘法逆元S盒变换仿射变换32S盒查找表S盒变换33三、AES的基本运算2、行移位运算ShiftRows中间态s中各行的循环左移第0行不移位第1行循环左移1个字节第2行循环左移2个字节第3行循环左移3个字节。行移位运算打乱了中间态s中各字节的位置关系，在功能上相当于置乱操作，可以实现扩散效果。34三、AES的基本运算3、列混合运算MixColumns实现中间态s中各列数据基于GF(28)域的变换。对每列数据起到良好的混淆作用。第i列变换：字节运算字运算35系数在GF(2)上的多项式运算1）加法“+”：字节的按位异或运算，即模2加

+

其中，＝＋，i＝0，1,…,7。（1）GF(28)域上的字节运算

362）乘法“•”类似普通多项式乘法，但系数运算要看作比特的乘法和异或运算，即看作{0,1}域上的运算。不可约多项式，元素才有乘法逆有限域上的多项式乘法①模多项式法计算字节乘法运算37例4-1

计算字节乘法运算。不便软硬件实现38对于GF(28)上模n次多项式m(x)乘法，有

Xn

modm(x)=m(x)-xn

GF(28)上x.a(x)模m(x)乘法②移位相加法计算字节乘法运算39x·a(x)模m(x)乘法的讨论相当于系数左移1位（右侧补0）相当于系数左移1位（右侧补0），再和1B异或乘以x2相当于在乘以x的基础上再乘以x。以此类推。*结论40例4-2用移位相加法，计算解：41例4-2用移位相加法，计算42课堂练习：用移位相加法计算

(10000011)•(01010111)(00000001)•(01010111)=(01010111)(00000010)•(01010111)=(10101110)(00000100)•(01010111)=(01011100)⊕(00011011)=(01000111)(00001000)•(01010111)=(10001110)(00010000)•(01010111)=(00011100)⊕(00011011)=(00000111)(00100000)•(01010111)=(00001110)(01000000)•(01010111)=(00011100)(10000000)•(01010111)=(00111000)(10000011)•(01010111)=[(00000001)+(00000010)+(10000000)]•(01010111)=(01010111)⊕(10101110)⊕(00111000)=(11000001)最高位是1，左移1位，异或1B最高位是1，左移1位，异或1B最高位是0，左移1位最高位是0，左移1位最高位是0，左移1位，最高位是0，左移1位最高位是0，左移1位43③表操作法计算字节乘法运算将GF(28)域上所有的非0元素{xy}表示为生成元{03}的幂，即{xy}={03}{XY}，并将{xy}与幂指数{XY}的对应关系制作成一张对数表:例：44例4-3证明域上的元素45例4-3证明域上的元素证：46③表操作法计算字节乘法运算将字节乘法变换为幂指数的加法。即若，则有：算术加注意：47③表操作法计算字节乘法运算例：将{xy}与幂指数{XY}的对应关系制作成一张对数表，从而根据{XY}查找到域上所有的非0元素{xy}：{03}{XY}={xy}。48例4-4利用表操作法，计算解：49例4-4利用表操作法，计算解：课堂练习查表法计算{7a}·{93}50查表求任意域元素的乘法逆元方法除了｛00｝外所有的域元素都有逆

如果，则可表示为：51例4-5求{95}的乘法逆{95}-1查对数表：{95}={03}{16}乘法逆元：{95}-1={03}{ff}-{16}={03}{e9}查反对数表：{03}{e9}＝{8a}

故{95}的乘法逆为{8a}验算{95}-1{95}={8a}{95}={03}{e9}{03}{16}={03}{ff}={01}对数表反对数表52（2）字运算—系数在GF(28)域上的运算1）字加法运算逐字节按位模2加法运算。例：53（2）字运算—系数在GF(28)域上的运算2）字乘法运算模不可约多项式f(x)=x4+1的乘法运算。根据可得形式与前面列混合式子相同！54列混合运算举例例4-6计算，其中解：55列混合运算举例例4-6计算，其中解：56列混合运算举例例4-6计算，其中解：57列混合运算举例例4-6计算，其中解：584、轮密钥加运算AddRoundKey密钥扩展后面介绍实现中间态与密钥字的按列异或运算。59四、AES的解密运算AES的解密算法完全由加密算法倒推而来。与加密算法相比，主要的不同之处有两点。四种基本运算用它们的逆运算取代。轮密钥颠倒顺序使用。此处仅介绍逆字节代换运算invSubBytes、逆行移位运算invShiftRows和逆列混合运算invMixColumns等三种逆运算。601、逆字节代换运算InvSubBytesinvSubBytes的输入字节。invSubBytes输出字节的乘法逆元。才是invSubBytes的输出字节。61逆S盒查找表例：逆字节代换622、逆行移位运算InvShiftRows图4-17逆行移位运算invShiftRows与行移位方向相反：第0行不变；第1行循环右移1个字节；第2行循环右移2个字节；第3行循环右移3个字节。633、逆列混和运算InvMixColumns64五、密钥扩展ExpandKey作用根据种子密钥（也称主密钥）k扩展出每轮迭代所需要的4个密钥字。

种子密钥k128比特：迭代10轮，需44个密钥字192比特：迭代12轮，需52个密钥字256比特：迭代14轮，需60个密钥字651、128比特密钥扩展w43661、128比特密钥扩展扩展过程直接用种子密钥k按列填充构成前4个密钥字。当且时，密钥字按下式扩展构成：。当且时，密钥字按照下式扩展构成：密钥字循环左移一个字节字节代换轮常数67轮常数轮常数Rconj的高字节总是前一个轮常数高字节的2倍模m(x)的结果{80}*2={100}=x8

=x8modm(x)=x4+x3+x+1={1b}m(x)=x8+x4+x3+x+1682、128比特密钥扩展举例例4-8假设128比特种子密钥k为：2b7e151628aed2a6abf7158809cf4f3c试列表给出AES的密钥扩展过程及结果。69加密密钥k

2b7e151628aed2a6abf7158809cf4f3c输入明文m3243f6a8885a308d313198a2e0370734六、AES加、解密实例输出密文c3902dc1925dc116a8409850b1dfb9732解密参见教材7021世纪欧洲NESSIE(NewEuropeanSchemesforSignatures，Integrity，andEncryption)密码工程确定的分组密码算法Feistel结构密码算法在21世纪的典型代表外观参数与AES相同安全性能和实现特性与AES算法大致相当知名度和影响力目前还不及AES算法4.3Camellia密码算法71紧随AES之后，保持欧洲工业界在密码学研究领域的领先地位2000年元旦启动NESSIE，同年3月公开征集2000年11月，征集到17个分组密码算法2001年9月，从中筛选出7个算法2003年2月，选定日本电报电话公司（NTT）的ShihoMoriai和日本三菱电子公司（MEC）的MitsuruMatsui两位密码学家联合设计的Camellia算法AES算法同时列为欧洲NESSIE标准算法一、Camellia的诞生背景721、Camellia算法的符号及含义二、Camellia的算法结构732、Camellia的算法结构预白化后白化典型的Feistel密码结构打乱算法的规律性加密结构128比特密钥2轮FL/FL-1和18轮Feistel叠代742、Camellia