应用密码学概要（一）

密码学在计算机领域是一个较难理解的主题，充满较多的概念、数学证明以及信息论等领域的知识要求，对于大多数工程师而言，从宏观角度上了解密码学，基本就能应付日常的使用。但通过研究学习发现，如果能对密码学底层的知识有足够的了解，能更深刻地理解密码学算法的底层原理，应付更复杂领域的密码学应用，做到知其然而知其所以然。本系列文章将尝试深入浅出地对密码学相关知识做一次总结，内容涵盖： 一次性密码本、DES与AES、分组加密及其模式与安全性探讨、流加密、Hash函数与消息验证(HMAC)以及HTTPS应用概要。本文将介绍一次性密码本、DES与AES，其他内容后续陆续更新。

（ 点击原文链接，可跳转blog阅读，获取更好的阅读体验）

异或(XOR)

文章的开篇，我们从最简单的异或说起。异或是一个二元判断操作，当两个输入相同时返回0，相异时返回0。常用符号”⊕”来表示。常见操作定义如下：

1⊕1=0

除了以上定义，异或操作还具有如下属性：

1. 顺序无关性：A⊕(B⊕C)=(A⊕B)⊕C

2. 可交换：A⊕B=B⊕A

3. 任何输入与自身异或，输出为0：A⊕A=0

4. 任何输入与0异或，其结果为其本身：1⊕0=1,0⊕0=0

而基于以上四个属性，我们可以推导地五条重要的属性：a⊕b⊕a=b

A⊕B⊕A=A⊕A⊕B(属性1)

以上定义，除对“0”和“1”的异或操作满足外，可以推广到任何多个位的操作。如对两个数字或两个字符串进行按位异或操作，也均满足以上定义。

#定义字符串按位异或的操作

一次性密码本(One-Time Pad)

基于以上关于异或的朴素定义，我们可以得到一个“坚不可摧”的加密方式，即：一次性密码本加密。

如上图所示，其中P代表明文(plaintext),C代表密文(ciphertext),K代表密钥(Key)。先通过对明文进行按位异或，将得到密文，完成加密。密文用相同的密钥进行按位异或，将得到明文信息，完成解密的操作。 从安全性上来看，攻击者知道密文C的情况下，可以证明其再没有K的信息时，他将不能获取任何关于明文的信息，但前提是：

• 密钥K必须完全随机

如果，密钥K不是完全随机产生，则无法证明其安全性。因为密钥不真随机的情况下，明文P与密文C可能存在一定的函数关系，而非完全独立，即使破解函数关系依旧非常困难，但是却不是可证明安全的。

• 密钥K不能复用

  另外一个前提是密钥不能复用。假设攻击者获取了两份明文P1、P2经用同一密钥K加密而得到的密文C1和C2，攻击者只需要将两份密钥进行异或操作，即可得到明文的的异或结果。推导如下：

	C1⊕C2=(P1⊕K)⊕(P2⊕K)

尽管得到的是P1、P2的异或结果，要独立分离出P1和P2的准确结果依旧困难，但要注意的是，两个明文的异或结果依旧会泄漏一些信息。如下面两张图片A、B进行异或，得到的结果几乎泄漏了所有信息。

密钥序列不能重用，这意味着每个明文的位都必须有一个密钥位与其对应，即密钥长度与明文长度要一样，这一点在工程实践上是没有意义的，这也是一次性密码本(OTP)在实际中很少使用的原因。

DES与AES

前文说到一次性密码本，它需要一个与明文长度一样长的随机生成的密钥来完成加密和解密，这种要求在工程实践上难度很大，接下来我们介绍两个可以用固定长度密钥对明文分组进行加密的算法。

DES

DES是一种用56位密钥对64位长的明文分组进行加密的方式。

DES是一种对称加密，加密和解密都使用相同的密钥。它采取迭代算法来进行加密，每一次加密过程都包含16轮操作，而每一轮的操作完全相同。只是每一轮的操作会使用不同的子密钥进行，子密钥由主密钥推导而来，上一轮的输出为下一轮的输入，整个迭代加密结构被称为 Feistel网络 ，Feistel网络结构如下：

64位的明文在完成初始转换后，会被分割成L0与R0左右两部分，每部分长度为32位，右半部分与生成的子密钥作为参数传入f函数，f函数的输出与左部分异或后作为下一轮的右半部分，而右半部分将直接复制到下一轮的左半部分。即：

R1=f(R0,K1)⊕L0

可见DES的 每一轮只对输入内容的左半部分加密，右半部分只是简单复制到下一轮 。

初始置换：

关于初始转换，本身对加密安全性没有任何影响，其只是对输入内容进行按位的位置变变换，如将第1位放置30位，30位放到20位等，逆转换即为复位。为什么要这么做？目前没有得到可解释的理由。

f函数：

由上面流程可知，DES中，f函数在安全性上扮演着非常重要的角色。f函数包括以下几步处理：

1. 位扩充

   位扩充是指将32位的输入扩展为48位，使用查表的方式进行扩充，也称为 E-盒转换 。具体转换方式如下图所示。 

需要注意的是，E-盒为算法内的静态定义，每一次加密过程都用同一E-盒的定义进行扩充。从上图的扩充过程可知，32个输入位经过扩充后变为48位，其中正好有16个位出现了两次，如图中1号位、4号位、5号位等。但是E-盒保证了 任意一个输入位都不会再同一个6位的输出分组中出现两次 ，如1号位出现在第一个6位分组和最后一个6位分组，4号位出现在第一个6位分组和第二个6位分组，这样做可以保证一半的输入位会影响两个不同的输出位置，而为什么以6个位作为分组单位？这与第三步的S-盒替换有关。

1. 与子密钥K进行异或操作，这一步很简单，输入和子密钥长度都是48，按位异或即可。

2. S-盒替换

   经过前面两步，输入已经转换为48位，而最终的输出需要转换为32位，这是通过S-盒转换来完成的，它通过查表的方式将6位的输入映射为4位的输出。DES中定义了8个S-盒，每个S-盒包含2^6=64个4位的值（十进制：0-15），这64个值分为4行*16列的表格进行存储。按以下方式读取S-盒：

• 第一个6位分组读S-盒1、依次，第8个分组读S-盒8

• 每个6位分组的最高位盒最低位决定要读的行，中间四个位决定要读取的列

如下图，第五个6位分组的读取方式：

S-盒转换给DES算法带来了唯一的非线性转换，即满足：S(A)⊕S(B)!=S(A⊕B)，它是DES加密过程中最重要的部分。

子密钥编排

DES的输入主密钥是64位的固定长度，而其中每第8个位为前面7个位的奇校验位，设置奇偶校验位除了能在密钥传输过程中用于检验密钥传输错误外，校验位的存在并没有增加密钥空间，对于增强加密安全性没有帮助。而密钥完整性校验，可以由更高级的办法进行，所以可以认为校验位的设置是一个比较过时的设计。

由于8位校验码的存在，所以DES其实是一个56位的主密钥加密，56位的主密钥在每一轮的加密过程中均会生成子密钥ki，而每一轮子密钥ki的长度固定是48位。子密钥生成算法如下图所示：

子密钥生成的算法里值得注意的是移位计算，移位计算会在左右两半部分同时进行，16轮密钥移动的位数正好为28位(左、右两半部分的长度)，由此可得到移位前和16轮移位后的密钥后，结果是一样的。这为后续解密过程生成字密钥提供了可逆支持。

解密

DES的解密的重点是， 解密算法与加密算法完全一致 ，这主要由密钥编排与Feistel网络的可逆性决定的。下面分别探讨密钥编排与Feistel网络的可逆性问题。

密钥编排可逆性

由上面子密钥的移位计算我们得到了移位前和16轮移位后的密钥完全一致，即C0=D16,D0=D16。而第16轮的，密钥由（C16,D16）进行PC-2转换得来。即：

k16=PC-2(C16,D16)

代入：C0=D16,D0=D16，得：

k16=PC-2(C0,D0)

(C0,D0)是由主密钥k进行PC-1转换而得来，所以：

k16=PC-2(PC-1(k))

即主密钥进行PC-1再进行PC-2，得到第16轮密钥k16。

k15由(C15,D15)进行PC-2转换而来，而(C15,D15)由(C16,C16)向右移位(移2位，记R2)而得到,即：

k15=PC-2(C15,D15)

同理可计算k1、k2…k14,只是向右移位的位数有所差异，第一轮不移位，第2、9、16轮右移一位，其他轮右移两位。

Feistel网络的可逆性

Feistel网络的一个重要特性是 第一轮解密的结果是第16轮加密的逆，并可一次类推，第二轮的解密结果是第15轮加密的逆，直至最后一轮解密结果即为明文。 通过对比DES加密的第一轮和最后一轮:

由第16轮加密过程可知，密文结果为第16轮加密后左右交换与逆初始转换后而来，所以，对密文进行初始转换(IP)，即可得第16轮左右交换后的结果,因为初始转换与逆初始转换相互抵消，所以第一轮解密结果(DL0,DR0)为：

(DL0,DR0)=IP(C)=(R16,L16)

而L16由R15平移而来，所以：

DL0=R16

接着计算下一轮加密结果(DL1,DR1)

同理，DL1由DR0平移而来，所以

DL1=DR0=R15

根据算法计算DR1，

DR1=DL0⊕f(DR0,k16)= R16⊕f(L16,k16)

上式中，R15与f(R15,k16)进行了两次异或，由异或属性5(见上文， 这一点非常重要，这一点的存在使得f函数的可逆性不是必须的，因为f函数里的S-盒变化是非线性不可逆的 )，得：

DR1=L15

以上推导即证明了第一轮解密后得到的记过与最后一轮加密前的结果是相等的，即第一轮解密的结果是最后一轮加密的逆。同理可推：

DL(i)=R(16-i）

即： 第i轮的解密结果，为第(16-i)轮的加密的逆 ，由此可知：最后一轮的解密结果即为(R0,L0),(R0,L0)进行左右变化和逆初始转换后即得到明文。

DES的安全性

说到DES的安全性，我们得先看看DES算法历史。

(来源：wiki)

由上述历史中可知，IBM和NSA共同设计了DES，但是对于密钥长度问题众说纷纭，到底是谁，为什么选择了56位的密钥没有定论。而 56位位的密钥长度正是DES被认为不安全的主要原因 ，也就是说DES的不安全性不在其算法设计上，而在于其密钥长度过短，暴力破解的代价较小。

AES

从上述关于DES历史的引用中可以看出，DES的算法是IBM和NSA采取对外保密的方式进行设计的，许多关于算法设计上的选择原由，一直到后面才公开。而AES采取了完全相反的方式。1997年，NIST(美国国家标准与技术研究院)向社会公开征集新的高级密码标准(AES),并经过多轮评估竞选者提交的方案，最终于2001年确认宣布两位比利时密码学家设计的Rijndael方案成为新的高级密码标准。

AES在方案征集前确认了一下必须满足的要求：

• 分组加密，分组块大小固定为128位（关于分组加密的更多内容，见后文）。

• 支持三种密钥长度:128位、192位、256位。

• 不同于DES可以在硬件上可以高效实现，在软件上实现也应该可以高效。

Rijndael基本满足以上要求，主要区别是Rijndael的分组大小和密钥长度都可以为128、192和256，而AES只要求分组大小为128。即：

AES(Rijndael，下文所提AES均为Rijndael加密算法)算法加密过程如下图所示：

与DES一样，AES也采取多轮加密的方式，但是AES的加密轮数不是固定的，与密钥长度相关， 128位长的密钥加密轮数是10轮，192位的密钥加密轮数是12轮，256位的密钥加密轮数是14轮 。但是AES不具有Feistel网络结构，即加密解密的算法是不一样的，其中每一步都必须可以求逆运算来解密。同时AES每轮爹地啊，会加密整个分组(128位),而DES只加密分组的一半，即32位。

AES的每一轮需要经过字节代换层、扩散层(ShiftRows&MixColumns)、密钥加法层三层操作，但最后一层不会进行MixColumns的操作，在第一轮开始前需要也需要进行一次密钥加法层的操作。

密钥加法层

AES的密钥加法层很简单，子密钥生成器每一轮都会根据主密钥编排生成一个128位的子密钥。 子密钥与当前状态的数据进行异或即为密钥加法层的输出。 由此可见，无论前文的DES，还是AES，密钥在加密算法中都只与加密内容进行异或运算，并不会有其他复杂的算法。

字节代换层

与DES类似， AES在字节代换层，提供了非线性变换的S-盒子替换，提供了AES加密过程的唯一非线性元素。 但AES的S-盒是一个双向映射，这是解密操作所需要的。AES的S-盒是一个256位*8位的固定项对应表，AES每8位进行查表后替换。S-盒如下图所示：

查表举例: 

扩散层

在加密过程中设置扩散层是位了将一个明文位变化的影响扩散到多个密文的位置，以达到隐藏明文统计属性的目的。在AES中的扩散层主要两个操作:ShitRows(行移位)、MixColumns(列混淆)，这两个操作均为线性操作，即满足:OP(A)+OP(B)=OP(A+B)。

ShiftRows操作

在进行ShiftRows操作之前，需要将进行操作的输入分组划分为一个矩阵4*4的矩阵，矩阵中每个元素长度为一个字节(8bit，即128=4*4*8)，然后对矩阵的每一行进行位移。具体算法如下所示：

MixColumns操作

MixColumn操作采取对ShiftRows后的矩阵的与一个固定矩阵进行相乘(矩阵相乘)后得到。

子密钥编排

AES的子密钥编排，以原始主密钥(长度为128位、192位或156位)为输入，输出固定长度为128位，子密钥的个数等于加密轮数加1，因为在第一轮加密前需要进行一次密钥加法层的操作。即： 128位的主密钥，加密轮数是10轮，共生成11个子密钥，192位的主密钥，加密轮数是12轮，共生成13个子密钥，256位的主密钥，加密轮数是14轮，共生成15个子密钥。

以128位主密钥生成为例，流程如下：

128位主密钥的AES需要11个子密钥，用元素长度为44的32位的数组来存储，表示为W0…W43，数组中的每一个元素经过如图中所示计算过程来生成，最终每4个元素组成一个子密钥，子密钥长度也正好为128位。即：

K0=(W0,W1,W2,W3)

与之类似，192位主密钥的AES需要的13个字密钥用W0…W51的52个元素来存储，256位主密钥的AES需要的15个字密钥用W0…W59的60个元素来存储，也是每4个元素组成一个128位的子密钥。

由上述可知，不同的主密钥长度，只是影响了加密轮数，而每一轮参与加密的子密钥长度是一致的，都是128位。

从实现上来并不约束是一次性将所有元素全部计算好，还是每一轮计算4个元素来组成子密钥，因为这是可行的，因为每一轮子密钥只后向依赖前一轮子密钥的4个元素。

解密

前文说到，由于AES不是Feistel网络，因此所有层里的操作必须支持完全逆操作。即字节代换层、ShiftRows层和MixColumns层都必须支持逆操作，同时子密钥编排也需要支持逆操作。

密钥加法层逆向

由于密钥加法层只是将输入内容与子密钥进行异或，所以求逆运算只要将计算后的内容再与该轮子密钥进行一次异或，即可得原来的输入。 因为P⊕K⊕K=A。

字节代换层逆向

字节代换层的逆计算也很简单，因为字节代换层使用S-盒支持反向查找。反向S-盒如下表：

ShiftRows层逆向

因为ShiftRows只是简单的向右移位，所逆运算只要相反地左移相应的位即可。

MixColumns层逆向

MixColumns操作是将输入矩阵与一个固定矩阵进行相乘而得到，而根据矩阵运算法则，将结果乘以该固定矩阵的逆矩阵即可还原得到输入内容。

子密钥编排的可逆性

前文说到，AES的每一步计算都是可以进行逆计算的，在每一轮的逆计算过程中，都需要使用与对应轮的子密钥参与解密，只是顺序相反，即第一轮解密需要最后一轮加密的密钥，依次，最后一轮解密需要第一轮加密的密钥。由此可知，只需要在解密前重新按密钥编排算法将所有轮次的子密钥计算得到，在解密时获取相应轮次的密钥即可。只是由于需要先计算好所有轮次的子密钥，而不能像加密那样动态地计算子密钥。