《网络信息安全技术(第二版)第2章密码技术课件.ppt》由会员分享，可在线阅读，更多相关《网络信息安全技术(第二版)第2章密码技术课件.ppt（179页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 密码技术基础 第2章 密码技术2.1 密码技术的基本概念密码技术的基本概念 2.2 古典密码体制古典密码体制 2.3 对称密码体系对称密码体系 2.4 公钥（非对称）密码体制公钥（非对称）密码体制 2.5 椭圆曲线密码体制椭圆曲线密码体制 第2章 密码技术基础 2.1 密码技术的基本概念密码技术的基本概念 密码方法可以隐藏和保护需要保密的信息，使未授权者不能获得该信息。加密技术是对传输过程中的数据进行保护的重要方法，也是对存储在媒体上的数据内容加以保护的一种有效手段。加密已经成为实现网络安全的一种有效又必不可少的技术手段。传统加密体制的整个过程如图2.1所示。此图是加密/解密的一个基本
2、原理图，需要加密的信息称为明文（Plaintext），这个明文信息由一个加密函数变换成密文(Ciphertext)，这个函数以一个密钥（Key）作为参数，所以可以用c=E（m，ke）来表达这个加密过程。第2章 密码技术基础 图2.1 传统加密体制的基本过程第2章 密码技术基础 解密过程基本类似，用一个解密函数和解密密钥对密文进行变换，成为明文，即m=D（c，kd），所以有m=D（E（m，ke），kd）。如果ke=kd，那么这种加密体制称为单钥或对称密码体制(One-Key or Symmetric Cryptosystem)。如果kekd，那么这种加密体制称为双钥或非对称密码体制(Two-Ke
3、y or Asymmetric Cryptosystem)。这是1976年由Diffie和Hellman等人所开创的新体制。第2章 密码技术基础 第2章 密码技术基础 2.2 古典加密技术古典加密技术2.2.1 置换密码置换密码 置换密码亦称换位密码。置换只不过是一个简单的换位。每个置换都可以用一个置换矩阵来Ek表示。每个置换都有一个与之对应的逆置换Dk。置换密码的特点是仅有一个发送方和接收方知道的加密置换（用于加密）及对应的逆置换（用于解密）。它是对明文L长字母组中的字母位置进行重新排列，而每个字母本身并不改变。第2章 密码技术基础 令明文m=m1,m2,mL。令置换矩阵所决定的置换为，则加
4、密置换 c=Ek(m)=(c1,c2,cL)=m(1),m(2),m(L)解密置换 例，置换密码。第2章 密码技术基础 最后一段长不足5，加添一个字母x。将各段的字母序号按下述置换矩阵进行换位：得到密文如下:STIEH EMSLP STSOP EITLB SRPNA TOIIS IOPCN SHXRE 第2章 密码技术基础 第2章 密码技术基础 2.2.2 代换密码代换密码 令表示明文字母表，内有q个“字母”或“字符”。设其顺序号为：0,1,q-1，可以将映射为一个整数集Zq=0,1,2,q-1，在加密时常将明文信息划分为长为L的信息单元，称为明文组。以m表示，如m=(m0,m1,mL),mi
5、Zq 第2章 密码技术基础 令表示明文字母表，内有q个“字母”或“字符”。设其顺序号为：0,1,:,q-1，可以将映射为一个整数集Z-q=0,1,2,:,q-1，密文组为c=(c1,c2,cL-1),ciZq，代换密码的加密变换是由明文空间到密文空间的映射。f:mc,m,c 假定函数f是一对一的映射，那么，给定密文c，有且仅有一个对应的明文组m，即对于f存在逆映射f-1，使f-1(c)=f-1f(m)=m加密变换通常是在密钥控制下进行的，即c=f(m,k)=Ek(m)第2章 密码技术基础 第2章 密码技术基础 1）位移代换密码 位移代换密码是最简单的一种代换密码，其加密变换为Ek(i)=(i+
6、k)j mod q 0i,jq,0kq 密钥空间元素个数为q，其中有一恒等变换，k=0，解密变换为D(j)=Eq-k(j)j+q-k(i+k)-ki mod q 例如，凯撒密码变换是对英文26个字母进行位移代换的密码，即将每一字母向前推移k位。若q=26，如选择密钥k=5，则有下述变换:明文：a b c d e f g h i j k l m n o p q r s t u v w x y z 密文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 第2章 密码技术基础 第2章 密码技术基础 2)乘数密码乘数密码的加密变换为Ek(i)=i*
7、kj mod q 0jq这种密码也称采样密码，是将明文字母表按序号每隔k位取出一个字母排列而成密文（字母表首尾相连）。显然，当(k,q)=1，即k与q互素时才是一一对应的。若q为素数，则有q-2个可用密钥。第2章 密码技术基础 例如，英文字母表q=26，选k=9，则由明文密文字母对应表明文：a b c d e f g h i j k l m n o p q r s t u v w x y z密文：A J S B K T C L U D M V E N W F O X G P Y H Q Z I R 于是对明文：Multiplicativer cipher 有密文：EYVPUFVUSAPUHK
8、SUFLKX。第2章 密码技术基础 第2章 密码技术基础 2 多表代换密码多表代换密码 多表代换密码是一系列（两个以上）代换表依次对明文信息的字母进行代换的加密方法。令明文字母表为Zq，令=(1,2,)为代换序列，明文字母序列为m=m1,m2,则相应的密文字母序列为c=Ek(m)=(m)=1(m),2(m),，若为非周期的无限序列，则相应的密码为非周期多表代换密码，否则，为周期多表代换密码。维吉尼亚是法国的密码专家，以他的名字命名的维吉尼亚密码加密算法是多表密码的典型代表。方法如下：第2章 密码技术基础 设密钥k=k1,k2,kn，明文m=m1,m2,mn，加密变换为 Ek(m)=c1,c2,
9、cn 其中 cimi+ki mod q i=1,2,n 例如，令q=26，明文m=polyalphabetic cipher，k=RADIO，即周期为5。首先将m分解成长为5的序列:polya lphab eticc ipher每一段用密钥 k=RADIO加密得密文：c=GOOGO CPKTP NTLKQ ZPKMF 第2章 密码技术基础 表2.1是维吉尼亚代换方阵，利用它可进行加密和解密。利用密钥k=RADIO对明文polya加密得GOOGO,第一个G是在r行p列上，第二个O是在a行o列上，第三个O是在d行l列上，以此类推。解密时p是r行含G的列，同理o是a行含O的列。以此可以推出全部密文，
10、从而恢复明文。第2章 密码技术基础 表表2.1 维吉尼亚密码代换方阵维吉尼亚密码代换方阵 第2章 密码技术基础 表表2.1 维吉尼亚密码代换方阵维吉尼亚密码代换方阵 第2章 密码技术基础 第2章 密码技术基础 流密码的安全性很大程度取决于生成的伪随机序列的好坏，对流密码技术的攻击主要来自于代数和概率统计的方法，目前出现了一些采用两种攻击手段相结合的密码攻击，对流密码的安全性形成了严重的挑战。流密码的实际计算过程是采用加密函数将输入的明文流序列和密钥流序列变换成密文流输出。明文按一定长度分组后被表示成一个序列（称为明文流），序列中的一项称为一个明文字。加密时，先由主密钥产生一个密钥流序列，该密钥
11、流序列的每一项和明文字具有相同的比特长度，称为一个密钥字。然后依次把明文流和密钥流中的对应项输入加密函数，产生相应的密文字，由密文字构成密文流输出。即 第2章 密码技术基础 设明文流为 m=m1m2mi 密钥流为 k=k1k2ki则加密算法为 解密算法为 第2章 密码技术基础 流密码与另一种对称密钥分组密码技术相比，主要具有以下优点：流密码运算速度非常快，算法在硬件实现时不需要复杂的硬件电路，非常适合于硬件实施；流密码错误扩展小，同步容易，并且加解密可以在缓冲较小的情况下顺利地串行化完成；流密码由于面向不同分组采用不同密钥，可以较好地隐藏明文的统计特征，安全程度较高。流密码体系主要由密钥流生成
12、器和加（解）密器几个部分组成。密钥流生成器用来生成作为密钥的伪随机序列，在加密过程中用作密钥流。加（解）密器完成对文本消息的实际加（解）密运算操作。流密码通常依据密钥流是否独立于明文流进行分类，可以分为同步流密码和自同步流密码两种类型。第2章 密码技术基础 第2章 密码技术基础 同步流密码无法抵御主动攻击者对密文字符进行的插入、删除或重放操作，此时会立即破坏系统的同步性，从而造成消息无法被解密器检测出来。同步流密码必须采用其他附加的技术为数据提供源认证并保证数据的完整性，这主要因为一个主动攻击者可能有针对性地对密文信息中的某些字符进行篡改，并明确地知道这些改动对明文会造成的影响。第2章 密码技
13、术基础 2自同步流密码自同步流密码自同步流密码也叫异步流密码，是指密钥流的产生受到明文流和密文流影响的流密码。通常，自同步流密码系统中第i个密钥字的生成不仅仅由主密钥独立决定，还要受到前面已经产生的若干个密文的影响。第2章 密码技术基础 第2章 密码技术基础 自同步流密码同样需要采用一些附加的技术来为数据提供源认证并保证其完整性。虽然在遭到攻击时，自同步流密码可以自动恢复大部分消息的解密，但是无法检测主动攻击者发起的对加密文字的插入、删除、重放等攻击，主动攻击者对密文字符的任何改动都可能引发一些密文字的解密出错，造成与明文不一致。与同步流密码相比，自同步流密码明文的统计学特征被扩散到了密文中，
14、在防御利用明文冗余度而发起的攻击方面要强于同步流密码，具备了明文统计扩散的特性。第2章 密码技术基础 3密钥流生成器密钥流生成器目前，密钥流生成器大都是基于移位寄存器实现的，主要是因为移位寄存器结构简单、易于实现且运行速度快，这种基于移位寄存器的密钥流序列通常被称为移位寄存器序列。密钥流生成器通常是由线性移位寄存器（LFSR）和一个非线性组合函数（即布尔函数）组合构成的。线性移位寄存器的理论早已比较成熟，其中的m序列移位寄存器具有良好的伪随机性，所以线性移位寄存器部分的设计相对容易。这样，密钥流生成器的重点与难点就集中在了非线性组合部分的设计与实现上。在二元情况下，非线性组合部分可用一个布尔函
15、数来实现，于是密钥流生成器的研究就归结为对布尔函数的研究。第2章 密码技术基础 密钥流生成器设计中，除了安全性以外，还要考虑密钥的易分配、易保管、便于实现和更换以及计算速度。任何密码系统设计要求的安全性越高则设计越复杂，在实际的设计中，这几项要求需要作一定的折中处理。密钥流生成器生成的密码流安全性有一定的限制，当密码流是完全随机序列时安全保密性能最好，而实际使用的密钥流序列都是密钥流生成器按一定算法生成的伪随机序列，所以并不是真正完善的保密系统。但采用有效算法使生成器所产生的密钥流序列尽可能具有随机序列的关键特征，可以提高系统的安全强度。通常，流密码的密钥流应具有如下特征：第2章 密码技术基础
16、（1）序列必须具有极大的周期，由于随机序列是非周期的，而按任何算法产生的序列必然是周期的或终归周期的，因此尽可能大的序列周期会增加序列被破解的难度，提高安全性；（2）序列必须具有良好的统计分布特性，即满足或部分满足Golomb的三个随机性假设，尽量避免统计攻击；第2章 密码技术基础（3）密钥流生成器应具有很高的线性复杂度，不能用级数较小的线性移位寄存器近似代替，防止生成方法被攻破；（4）密钥流生成器的算法结构和相关信息不能用统计方法在有限条件下计算得到，以尽可能保护密码系统的有效性。这些要求是序列密码的安全性的必要非充分条件。随着新的攻击方法的出现以及设计密钥流生成器的方法变化，还会对密钥流的
17、特性提出新的要求。第2章 密码技术基础 4线性反馈移位寄存器线性反馈移位寄存器生成一个具有良好特征的密钥流序列的常见方法有：线性移位寄存器LFSR、非线性移位寄存器NLFSR、有限自动机、线性同余等方法和混沌密码序列技术。这些方法的总体思路都是通过一个种子密钥（有限长）产生具有足够长周期的、随机性良好的序列。移位寄存器的周期是指输出的密钥序列从开始到再次重复时的长度。只要密钥序列的生成方法和种子密钥相同，就会产生完全相同的密钥流。第2章 密码技术基础 反馈移位寄存器（FeedbackShiftRegister）一般由移位寄存器和反馈函数（FeedbackFunction）两部分构成。移位寄存器
18、是位序列，具有n位长的移位寄存器称为n位移位寄存器。移位寄存器通常按位输出最低有效位，它通过所有位都右移一位实现一位输出，寄存器最左边一位的值可根据当前其他位的值计算得到。线性移位寄存器（LinearFeedbackShiftRegister，LFSR）是最简单的反馈移位寄存器。寄存器的反馈函数是寄存器中某些位值的简单异或，形成反馈函数的多个位叫做抽头序列，也称为Fibonacci配置。第2章 密码技术基础 2.3.2分组密码分组密码分组密码加密是在密钥的控制之下，将定长的明文块转换成等长密文的技术。分组密码使用同一密钥通过逆向变换来实现解密。当前的许多分组密码采用64位分组大小，但为了提高安
19、全性，这一长度可能会增加。明文信息通常是较长的文档或消息块，大小要比特定的加密分组大得多，在加密时会进行分组并且使用不同的技术或操作方式。加密的主要方法有：电子编码本（ECB）、密码分组链接（CBC）、密码反馈（CFB）或输出反馈（OFB）。ECB使用同一个密钥简单地将每个明文块一个接一个地进行加密；在CBC方式中，每个明文块在加密前先与前一密文块进行“异或”运算，从而增加了复杂程度，可以使某些攻击更难以实施；输出反馈（OFB）方式类似CFB方式，但是进行“异或”的量是独立生成的。CBC方法受到广泛使用，例如DES（qv）实现中就采用了该方法。第2章 密码技术基础 迭代的分组密码是那些在加密过
20、程有多次循环的密码，因此提高了安全性。在每个循环中，可以通过使用特殊的函数从初始密钥派生出的子密钥来进行适当的变换。该附加的计算需求必然会影响加密的速度，因此在安全性需要和执行速度之间存在着一种平衡。天下没有免费的午餐，密码技术也是如此；与其他地方一样，应用适当方法的技巧中有一部分是源于对需要进行的权衡以及如何理解该方法与需求平衡的关系。分组密码的主流算法包括DES、IDEA、SAFER、Blowfish和Skipjack，其中Skipjack算法是“美国国家安全局（USNationalSecurityAgency，NSA）”限制器芯片中使用的算法。第2章 密码技术基础 国际数据加密算法IDE
21、A（InternationalDataEncryptionAlgorithm）是由两位研究员XuejiaLai和JamesL.Massey在苏黎世的ETH开发的，一家瑞士公司AscomSystec拥有专利权。IDEA是作为迭代的分组密码实现的，使用128位的密钥和8个循环。这比DES提供了更多的安全性，但是在选择用于IDEA的密钥时，应该排除那些称为“弱密钥”的密钥。DES只有4个弱密钥和12个次弱密钥，而IDEA中的弱密钥数相当可观，有251个。但是，如果密钥的总数非常大，达到了2128个，那么仍有277个安全密钥可供选择。第2章 密码技术基础 2.3.3数据加密标准（数据加密标准（DES）
22、数据加密标准（DataEncryptionStandard，DES）是IBM的研究成果，是数据加密算法（DataEncryptionAlgorithm，DEA）的规范描述，在1997年被美国政府正式采纳。DES算法是使用最广泛的密钥系统之一，在各个领域特别是在金融领域数据安全保护中广泛应用，比如银行的自动取款机（AutomatedTellerMachine，ATM）的数据加密都使用DES。最初版本的DES是嵌入硬件中的，但随着应用范围的扩大也采用软件方式。第2章 密码技术基础 DES算法使用了56位的密钥以及附加的8位奇偶校验位，形成的分组大小最大为64位。DES算法采用一个迭代的分组密码，实
23、现中使用Feistel技术，首先将待加密的文本块分成两半，使用子密钥对其中一半文本应用循环功能，然后将输出与另一半进行“异或”运算；接着交换这两部分文本，这一过程会继续下去。DES使用了16个循环，但最后一个循环不进行交换。第2章 密码技术基础 设明文m是0和1组成的长度为64位的符号串，密钥K也是64位的0和1组成的符号串，即 m=m1m2 mi m64,mi=0或1K=K1K2 Ki K64,Ki=0或1其中，密钥K只有56位有效，K8,K16,K24,K64是奇偶校验位，在算法中不起作用。加密过程为 DES(m)=IP-1。T16。T15 T2。T1。IP(m)式中：IP是初始置换；IP
24、-1是IP的逆置换。第2章 密码技术基础 设m=m1m2m64,则IP置换为 设m=m1m2m64,则IP-1置换为 第2章 密码技术基础 表表2.2 初初 始始 置置 换换 表表2.3 逆逆 置置 换换 第2章 密码技术基础 （1）DES的加密过程。将DES的加密过程用图2.2表示。初始化换位IP，是将输入的二进制明文块T变换成T0=IP(T),然后T0经过16次函数f的迭代，最后通过逆初始换位IP-1得到64位的二进制密文输出。两次相邻的迭代之间的关系是 Li=Ri-1 Ri=Li-1f(Ri-1,Ki)其中，表示按位做不进位的加法运算，即10=01=1,0 0=11=0,ki表示48位的
25、子密钥。第2章 密码技术基础 图 2.2 DES加密过程第2章 密码技术基础 （1）函数f(Ri-1,ki)的结构如图2.3所示。图2.3中E是位选择表（见表2.3），它将Ri-1扩展成48位二进制块E(Ri=1)然后对E(Ri=1)和ki进行操作，并将结果分成8个6 bit二进制块B1,B2,B8，此处B1,B2,B8=kiE(Ri-1)，每个6位子块Bi都是选择（代换）函数Si的输入，其输出是一个4位的二进制块，把这些子块合并成32位二进制块后，用置换表P(如表2.4)将它变成P(S1(B1),S2(B2),S8(B8)这就是函数f(Ri-1,ki)的输出。每个Si将一个6位块Bi=b1,
26、b2,b6转换成一个4位块(如表2.5），与b1,b6对应的整数确定表中的行号，与b2,b3,b4,b5相对应的整数确定表中的列号，Si(Bi)的值就是位于该行和该列的整数的4位二进制表示形式。第2章 密码技术基础 图 2.3 DES中间变换过程 第2章 密码技术基础 表表 2.4 位选择表位选择表 第2章 密码技术基础 表表 2.5 换位表换位表 第2章 密码技术基础 表表2.6 选择（替代选择（替代)函数函数S 第2章 密码技术基础 表表2.6 选择（替代选择（替代)函数函数S 第2章 密码技术基础 表表2.6 选择（替代选择（替代)函数函数S 第2章 密码技术基础 密钥ki是由初始密钥推
27、导得到的，初始密钥k是一个64位的二进制块，其中8位是奇偶校验位，分别位于第8、16、64位。子密钥换位函数PC-1 把这些奇偶校验去掉，并把剩下的56位进行换位，如表（2.3）。换位后的结果PC-1(k)被分成两半C和D，各有28位，令Ci和Di分别表示推导ki时所用的C和D的值，变换公式如下 Ci=LS(Ci-1)Di=LS(Di-1)第2章 密码技术基础 式中，LS是循环左移位变换，其中LS1,LS2,LS9,LS16是循环左移一位变换，其余的LSi是循环左移两位变换。C0,D0是C和D的初始值。最后，通过子密钥变换函数PC2（参见表2.5）得出 ki=PC-2(Ci,Di)解密算法和加
28、密算法相同，但是它使用的子密钥顺序是相反的。第一次是用k16,第2次迭代用k15,最后一次用k1，这是因为最终换位IP-1是初始换位IP的逆变换且 Ri-1=Li Li-1=Rif(Li,ki)DES代换使得输出成为输入的非线性函数，换位扩展了输出对输入的依赖性。第2章 密码技术基础 表表2.7子密钥换位函数子密钥换位函数PC-1 Y YX X0123456789abcdef0637c777bf26b6fc53001672bfed7ab761ca82c97dfa5947f0add4a2af9ca472c02b7fd9326363ff7cc34a5e5f171d83115304c723c3189
29、6059a071280e2eb27b275409832c1a1b6e5aa0523bd6b329e32f84553d100ed20fcb15b6acbbe394a4c58cf6d0efaafb434d338545f9027f503c9fa8751a3408f929d38f5bcb6da2110fff3d28cd0c13ec5f974417c4a77e3d645d1973960814fdc222a908846eeb814de5e0bdbae0323a0a4906245cc2d3ac629195e479be7c8376d8dd54ea96c56f4ea657aae08cba78252e1ca6b4
30、c6e8dd741f4bbd8b8ad703eb5664803f60e613557b986c11d9eee1f8981169d98e949b1e87e9ce5528dff8ca1890dbfe6426841992d0fb054bb16第2章 密码技术基础 表表2.8子密钥换位函数子密钥换位函数PC-2 第2章 密码技术基础 (2)IDEA 国 际 数 据 加 密 算 法 IDEA（International Data Encryption Algorithm）是由两位研究员 Xuejia Lai 和 James L.Massey 在苏黎世的 ETH公司开发的，一家瑞士Ascom systec
31、公司拥有专利权。IDEA 是作为迭代的分组密码实现的，使用 128 位的密钥和 8 个循环。这比 DES 提供了更多的安全性，但是在选择用于 IDEA 的密钥时，应该排除那些称为“弱密钥”的密钥。DES 只有四个弱密钥和 12 个次弱密钥，而 IDEA 中的弱密钥数相当可观，有251个。但是，如果密钥的总数非常大，达到2128个，那么仍有277个密钥可供选择。第2章 密码技术基础 2.3.4高级加密标准高级加密标准(AES)1.AES算法的概念算法的概念AES算法的输入和输出都是长度为128bit的序列串，序列中每个位的值为0或1。这些序列在算法中称为数据分组(block)，序列包含的位(bi
32、t)数也称为分组长度。AES算法使用128bit、192bit或256bit长度的密钥。算法不支持其他的输入、输出长度和密钥长度。第2章 密码技术基础 1）字节）字节(byte)AES算法中的基本运算单位是字节(byte)，即作为一个整体的8bit二进制序列。算法的输入数据、输出数据和密钥都以字节为单位，明文、密钥和密文数据串被分割成一系列8个连续比特的分组，并形成字节数组。假设一个8字节的分组b是由字节序列b7,b6,b5,b4,b3,b2,b1,b0所组成的，则可将bi看做一个7次多项式b(x)的系数，即b(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0
33、式中，bi0,1。第2章 密码技术基础 例如，01010111表示成多项式为 x6+x4+x2+x+1 也可以使用十六进制符号来表示字节值，将每4bit表示成一个符号便于记忆。例如，01010111=57。第2章 密码技术基础 2）字节数组输入序列按字节划分，表示形式如下：第2章 密码技术基础 3）状态（State）AES算法的运算都是在一个二维字节数组上完成的，这个数组称为状态。当输入的明文序列转换成字节数组后，进一步将一维的字节数组内容转换为二维排列，就形成了状态矩阵。一个状态矩阵由四行组成，每一行包括Nb个字节，Nb的值等于分组长度除以32。状态矩阵用s表示，每一个字节的位置由行号r(范
34、围是0r4)和列号c(范围是0cNb)惟一确定，记为sr,c或sr,c。在AES标准中状态矩阵参数Nb=4，即0c4。第2章 密码技术基础 第2章 密码技术基础 图2.4AES加解密状态矩阵运算 第2章 密码技术基础 式中：0r4；0cNb。在加密和解密的完成阶段，状态矩阵采用以下规则转换，结果存储在输出数组out中：其中，0r4,0cNb。第2章 密码技术基础 4）状态矩阵列数组）状态矩阵列数组状态矩阵中每一列的4个字节是一个32位长的字，行号r是这个字中每个字节的索引，因此状态矩阵可以看做32位字(列)长的一维数组，列号c是该数组的列索引。由此上例中的状态可以看做4个字组成的数组，表示如下
35、：第2章 密码技术基础 2.有限域基本数学运算有限域基本数学运算AES算法的基本思想是基于置换和代替变换的演算方法。其中，置换是对数据的重新排列，而代替则是用数据替换另一个。AES算法中的所有字节按照每4位表示成有限域GF（28）中的一个元素。这个有限域元素可以进行加减法和乘法运算，但是这些运算不同于代数中使用的运算。下面介绍有限域相关算法的基本数学概念。第2章 密码技术基础 1）加减法在有限域中，多项式的加法运算定义为两个元素对应多项式相同位置指数项相应系数的“加法”。简单地说，有限域GF（28）的加法是按位进行异或XOR运算(记为)，即模2加，110，101，000。多项式减法与多项式加法
36、的规则相同。例如：以多项式表示加法的计算过程如下：第2章 密码技术基础 例：第2章 密码技术基础 3）乘以）乘以x在有限域GF(28)中，二元多项式乘以x，即乘以2；若将一多项式b(x)乘上x，其结果可以表示为 将上述结果模m(x)即可得到xb(x)的结果。如果得到的结果序列中b7=0，则不会出现结果溢出问题，将该结果整体左移一位并在最末位补0，就得到模运算后的形式；如果结果中b7=1，就需要左移一位后再模多项式m(x)。第2章 密码技术基础 有限域的乘x(即00000010或02)运算可通过字节级别的左移和与1b进行有条件的按位异或来实现，该操作记为x02或b=xtime(a)。x的高次幂乘
37、法可以通过多次重复使用xtime()来完成，计算的中间结果相加，可以实现任意常数的乘法。利用此特性，可将有限域乘法运算转换为有限域加法运算。例如：5713=FE5702=xtime(57)=AE5704=xtime(AE)=475708=xtime(47)=8E5710=xtime(8E)=075713=57010210=57AE07=FE 第2章 密码技术基础 4）系数在GF（28）域的特殊多项式运算给定字符向量转换为系数在有限域GF（28）中的多项式a(x)=a3x3+a2x2+a1x+a0，它可以用a0,a1,a2,a3形式表示。该多项式与有限域元素定义中使用的多项式操作不同，此处的系数
38、本身就是有限域元素，即是字节(byte)而不是比特(bit)，系数本身可以用另一个有限域多项式表示。特殊的四项多项式的乘法可使用不同的模多项式M(x)=x4+1。系数在有限域GF(28)中的多项式运算主要有乘法和乘以x两种。第2章 密码技术基础 (1)给定多项式b(x)=b3x3+b2x2+b1x+b0，计算a(x)与b(x)相乘。令，即 其向量表示为 第2章 密码技术基础 第2章 密码技术基础 由于多项式M(x)=x4+1在GF(28)下可能不是可约多项式，因此如果任意给定一个四次多项式，在模M(x)下不一定存在一个对应的乘法反多项式。在AES算法中，采用一个乘法反多项式的固定多项式来解决这
39、个问题，算法使用的四次多项式a(x)及反多项式a-1(x)有a(x)a-1(x)=1mod(x4+1)关系。第2章 密码技术基础 3.AES加密加密原始的Rijndael加密算法是分组长度可变、密钥长度也可变的分组密码形式，但AES算法经过修改已经有所不同，只支持几种特定的长度。在AES算法中规定了输入分组、输出分组、状态长度都是128位，即对应的Nb=4，该值反应了状态中32bit字的个数；密钥k的长度只能是128位、192位或256位。不同密钥长度对应的Nk=4、6或8，反映了密钥中32位字的个数(列数)。对于AES算法，算法的轮数Nr依赖于密钥长度，当Nk=4时，Nr10；当Nk=6时，
40、Nr12；当Nk=8时，Nr14。与Rijndael标准相比较，可以使用的密钥长度、分组长度、轮数的组合如表2.9所示。第2章 密码技术基础 表表2.9AES密钥长度、分组长度、轮数的组合表密钥长度、分组长度、轮数的组合表 第2章 密码技术基础 数据加密过程首先将输入信息复制到状态矩阵中，然后将密钥k0和待加密信息按位相与，完成初始轮子密钥的加密过程。然后将所有要加密的数据分组都使用轮函数F进行迭代计算，计算过程中使用的子密钥是由密钥扩展函数产生的，用来生成子密钥的初始密钥是主密钥。AES算法中函数F要进行Nr次迭代，根据密钥长度不同，轮函数执行次数Nr值可能是10、12或14。每轮计算包含4
41、个步骤，最后一轮包含3个步骤。AES的总体结构如图2.5所示。第2章 密码技术基础 图2.5AES迭代 第2章 密码技术基础 图2.5中待加密的数据序列被按组划分成一个字节阵列，每次加密操作针对字节进行。运算流程中轮函数分4层。第一层是由16个S-盒并置而成的非线性层，起到数据混淆的作用。第二和第三层是线性混合层，阵列行被移位，列被混叠，确保多轮计算中数据的高度扩散。在第四层，使用子密钥字节，对阵列中的每个字节进行异或操作，在本轮中不需要进行列的混叠。最后的状态矩阵被复制并转换输出。轮函数使用密钥扩展算法实现参数化，密钥编排是由密钥扩展得到的4比特字节的数组组成。第2章 密码技术基础 AES加
42、密的具体过程为首先初始化，产生初始密码，通过拷贝16字节的输入数组到44字节状态矩阵中，将一个分组长度的输入序列转化为状态矩阵，同时使用主密钥生成子密钥用于数据加密；状态矩阵通过与子密钥按位与运算完成初始变换；加密算法中预备阶段的处理步骤称为轮密钥加变换（AddRoundKey）。轮密钥加变换用密钥调度表中的前四行对状态矩阵逐个字节进行异或（XOR）操作，并用轮密钥表wc,r异或输入状态矩阵Stater,c。AES算法的主循环对状态矩阵执行四个不同的变换和替代操作，分别是字节替换变换（SubBytes）、行位移变换（ShiftRows）、列混叠变换（MixColumns）和轮密钥加变换（Add
43、RoundKey），最终循环Nr次得到密文输出。如图2.6所示。第2章 密码技术基础 图2.6AES加密过程 第2章 密码技术基础 下面讲述AES算法中的主要变换和替代计算方法。1）字节替换变换（SubBytes）字节替换变换是一个非线性可逆变换，针对状态矩阵中的每个字节利用替代表(S盒)进行运算，表示为SubBytes(State)，也称仿射变换。字节替换变换采用可逆的S盒，计算过程主要由两个变换复合而成。两个变换的内容如下：（1）选取有限域GF(28)上的乘法逆运算，其中，元素00映射到它自身。第2章 密码技术基础（2）应用如下算法完成一有限域GF(28)上的仿射变换：第2章 密码技术基础
44、 首先，将字节数据看成GF(28)上的元素，进行模m(x)运算映射到自己的乘法逆，0映射到自身；其次，作GF（28）的仿射变换，该变换过程可逆。预先将GF（28）上的每个元素通过查表作SubBytes变换，形成S盒。AES算法中的S盒与DES算法不同，AES的S盒具有一定的代数结构，而DES算法中是人为指定构造的。S盒的仿射变换以矩阵的形式可表示为 第2章 密码技术基础 S盒的仿射变换SubBytes()在状态矩阵上的变换功能如图2.7所示。图2.7S盒的单字节仿射变换第2章 密码技术基础 实际运算时，此函数可以通过查表快速获得对应变换值，替代变换的替代值如表2.10所示。例如b1,1=53，
45、查替代值表，找到第5列第3行，对应数值为ed，表示经过字节替代变换后，b1,1=ed。第2章 密码技术基础 表表2.10S盒中字节盒中字节x,y的替代值（十六进制格式）的替代值（十六进制格式）第2章 密码技术基础 2）行位移变换（）行位移变换（ShiftRows）行位移变换(ShiftRows)是在状态矩阵的行上进行的。状态阵列的后3行分别以ci位移大小循环移位。其中，第0行c0=0，即保持不变；第1行循环移位c1字节；第2行循环移位c2字节;第3行循环移位c3字节。运算结果是将行中的字节移向较低位，最低位的字节循环移动至行的最高位,如图2.8所示。128位状态矩阵的ShiftRows行位移变
46、换操作如图2.9所示。第2章 密码技术基础 图2.8ShiftRows对状态矩阵的行操作 第2章 密码技术基础 图2.9128位状态矩阵的ShiftRows行位移变换操作 第2章 密码技术基础 表表2.11不同分组长度的行位移变换偏移量不同分组长度的行位移变换偏移量 第2章 密码技术基础 3）列混叠变换（）列混叠变换（MixColumn）列混叠变换(MixColumns)在状态矩阵上，按照每一列分别进行运算，并将每一列看做有限域四次多项式，即将状态的列看做GF（28）上的多项式a(x)与多项式c(x)相乘，计算结果对固定多项式M(x)=x4+1取模。多项式c(x)表示为 其中,系数是用十六进制
47、表示的，并且c(x)与x4+1互质。第2章 密码技术基础 第2章 密码技术基础 写成矩阵表示形式为 第2章 密码技术基础 图2.10 列混叠变换MixColumns 第2章 密码技术基础 4)轮密钥加变换(AddRoundKey)在轮密钥加变换中，用轮密钥与状态矩阵按比特进行异或（XOR）操作。轮密钥是通过主密钥生成的子密钥，为了便于计算，轮密钥的长度等于分组长度，每一个轮密钥由Nb个字组成。轮密钥加变换过程如图2.11所示。第2章 密码技术基础 图2.11轮密钥加变换 第2章 密码技术基础 5）密钥扩展算法迭代计算过程中使用的轮密钥（子密钥）ki，是利用第i-1轮的轮密钥和密钥k0用密钥扩展
48、函数计算生成的。通过密钥扩展计算总共生成Nb(Nr+1)个密钥字。该算法需要使用Nb个字组成的初始集合，Nr轮中的每一轮计算需要Nb个字的密钥。密钥编排结果由一个4bit字的线性数组组成，记为wi，其中0iNb(Nr+1)，主密钥生成(Nr+1)Nb个字的轮密钥数组。密钥扩展函数原理如图2.12所示。第2章 密码技术基础 图2.12Nk=4的密钥扩展函数原理 第2章 密码技术基础 图2.12中16个字节的密钥划分为4组处理，每组包括4个字节。最后一组的4个字节由函数S进行替换处理（这个S函数和用F函数进行迭代处理时的S函数是一样的）。最初4个字节的结果和系数相加，系数的值是预先定义的，并且与轮
49、数有关。最终把得到的4个字节的结果和第i-1轮密钥的4个字节按位相加得到ki，再与第i-1轮密钥的4个字节按位相加，如此类推完成计算。第2章 密码技术基础 4.AES解密解密AES的解密算法与加密算法不同，是加密过程的逆运算。解密算法中各个变换的操作顺序与加密算法不同，但是加密和解密算法中的密钥编排形式是一致的。AES算法的若干性质保证了可以构造一个等价的解密算法，解密时各个变换的操作顺序与加密时相反(由逆变换取代原来的变换)。解密算法中使用的变换依次为列混叠(InvMixColumns)变换、逆行位移变换(InvShiftRows)、逆字节替换变换(InvSubBytes)和轮密钥加变换(A
50、ddRoundKey)，变换作用在密文序列对应的状态矩阵上。具体的解密过程如图2.13所示。第2章 密码技术基础 图2.13AES解密过程 第2章 密码技术基础 2.4公钥（非对称）密码体制公钥（非对称）密码体制 2.4.1公钥密码体制的基本概念公钥密码体制的基本概念公钥体制下，一个用户可以将自己设计的加密公钥和加密算法对外公布，而只保留解密用的私钥。任何人都可以获取这个用户的加密公钥和加密算法，并向该用户发送加密过的信息，该用户接收后可以使用私钥还原消息。在这个公钥加解密的过程中，会涉及到公私密钥对、数字证书以及电子签证机关等主要内容。第2章 密码技术基础 1.密钥对密钥对在基于公钥体系的安