密码算法详解——AES

一时失言乱红尘 2022-10-02 11:57 272阅读 0赞

转载自：[https://www.cnblogs.com/luop/p/4334160.html][https_www.cnblogs.com_luop_p_4334160.html]

# 0 AES简介 #

我们知道数据加密标准（Data Encryption Standard: DES）的密钥长度是56比特，因此算法的理论安全强度是256。但二十世纪中后期正是计算机飞速发展的阶段，元器件制造工艺的进步使得计算机的处理能力越来越强，DES将不能提供足够的安全性。1997年1月2号，美国国家标准技术研究所（National Institute of Standards and Technology: NIST）宣布希望征集高级加密标准（Advanced Encryption Standard: AES）\[3\]，用以取代DES。AES得到了全世界很多密码工作者的响应，先后有很多人提交了自己设计的算法。最终有5个候选算法进入最后一轮：[Rijndael][]，[Serpent][]，[Twofish][]，[RC6][]和MARS，下图分别为其中的5位作者。最终经过安全性分析、软硬件性能评估等严格的步骤，Rijndael算法获胜。

![671127-20160524103729100-1928102316.jpg][]

Rijndael由比利时两位非常著名的密码学家[Joan Daemen][]和[Vincent Rijmen][]设计。Rijndael是一个分组密码算法族，其分组长度包括128比特、160比特、192比特、224比特、256比特，密钥长度也包括这五种长度，但是最终AES只选取了分组长度为128比特，密钥长度为128比特、192比特和256比特的三个版本。本文主要结合AES-128进行介绍，AES-196和AES-256的思路基本一样，只是密钥扩展算法的过程会稍有不同，加解密的轮数会适当增加，但加解密的操作都是一样的。另外，本文只对AES算法的各个模块、基本原理进行介绍，旨在加深对算法流程、密码算法实现的了解。在正式软件运用中并不推荐自己编写代码，很多开源项目如Linux，OPENSSL，SRTP等都有非常高效的实现。由于数学知识的缺陷，本文不介绍算法安全性分析相关的知识，有兴趣的读者可以自行阅读相关文献。

AES是一个分组密码，属于对称密码范畴，AES算法的模块在对称密码领域特别是分组密码领域常有使用。

# 1 算法流程 #

AES加密算法涉及4种操作：**字节替代**（SubBytes）、**行移位**（ShiftRows）、**列混淆**（MixColumns）和**轮密钥加**（AddRoundKey）。下图给出了AES加解密的流程，从图中可以看出：1）解密算法的每一步分别对应加密算法的逆操作，2）加解密所有操作的顺序正好是相反的。正是由于这几点（再加上加密算法与解密算法每步的操作互逆）保证了算法的正确性。加解密中每轮的密钥分别由种子密钥经过**密钥扩展算法**得到。算法中16字节的明文、密文和轮子密钥都以一个4x4的矩阵表示。

![130035028553414.png][]

## 1.1 字节替代 ##

字节代替的主要功能是通过S盒完成一个字节到另外一个字节的映射。S盒的详细构造方法可以参考文献\[4\]。这里直接给出构造好的结果，下图(a)为S盒，图(b)为S-1（S盒的逆）。S盒用于提供密码算法的**混淆性**。

![130038570278987.png][]

![130039158865217.png][]

S和S-1分别为16x16的矩阵，完成一个8比特输入到8比特输出的映射，输入的高4-bit对应的值作为行标，低4-bit对应的值作为列标。假设输入字节的值为a=a7a6a5a4a3a2a1a0，则输出值为S\[a7a6a5a4\]\[a3a2a1a0\]，S-1的变换也同理。

例如：字节00000000B替换后的值为（S\[0\]\[0\]=）63H，再通过S-1即可得到替换前的值，（S-1 \[6\]\[3\]=）00H。

## 1.2 行移位 ##

行移位是一个4x4的矩阵内部字节之间的置换，用于提供算法的**扩散性**。

1) 正向行移位

正向行移位用于加密，其原理图如下。其中：第一行保持不变，第二行循环左移8比特，第三行循环左移16比特，第四行循环左移24比特。

假设矩阵的名字为state，用公式表示如下：state’\[i\]\[j\] = state\[i\]\[(j+i)%4\];其中i、j属于\[0,3\]。

![130047023709062.png][]

2) 逆向行移位

逆向行移位即是相反的操作，即：第一行保持不变，第二行循环右移8比特，第三行循环右移16比特，第四行循环右移24比特。

用公式表示如下：state’\[i\]\[j\] = state\[i\]\[(4+j-i)%4\];其中i、j属于\[0,3\]。

## 1.3 列混淆 ##

列混淆：利用GF(28)域上算术特性的一个代替，同样用于提供算法的**扩散性**。

1) 正向列混淆

正向列混淆的原理图如下：

![130052373249725.png][]

根据矩阵的乘法可知，在列混淆的过程中，每个字节对应的值只与该列的4个值有关系。此处的乘法和加法都是定义在GF(28)上的，需要注意如下几点：

1) 将某个字节所对应的值乘以2，其结果就是将该值的二进制位左移一位，如果原始值的最高位为1，则还需要将移位后的结果异或00011011；\[1\]

**　　　　　　**英文原文描述如下：In particular, multiplication of a value by x (i.e., by \{02\}) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (0001 1011) if the leftmost bit of the original value (prior to the shift) is 1.

2) 乘法对加法满足分配率，例如：07·S0,0=(01⊕02⊕04)·S0,0= S0,0⊕(02·S0,0)(04·S0,0)

3) 此处的矩阵乘法与一般意义上矩阵的乘法有所不同，各个值在相加时使用的是模28加法（异或运算）。

下面举一个例子，假设某一列的值如下图，运算过程如下：

![130102368866430.png][]

![130105054177539.png][]

在计算02与C9的乘积时，由于C9对应最左边的比特为1，因此需要将C9左移一位后的值与(0001 1011)求异或。同理可以求出另外几个值。

2) 逆向列混淆

逆向列混淆的原理图如下：

![130108397307413.png][]

由于：

![130110187306459.png][]

说明两个矩阵互逆，经过一次逆向列混淆后即可恢复原文。

## 1.4 轮密钥加 ##

这个操作相对简单，其依据的原理是“任何数和自身的异或结果为0”。加密过程中，每轮的输入与轮子密钥异或一次；因此，解密时再异或上该轮的轮子密钥即可恢复。

## 1.5 密钥扩展算法 ##

密钥扩展的原理图如下：

![130112236057708.png][]

密钥扩展过程说明：

1)  将种子密钥按图(a)的格式排列，其中k0、k1、……、k15依次表示种子密钥的一个字节；排列后用4个32比特的字表示，分别记为w\[0\]、w\[1\]、w\[2\]、w\[3\]；

2)  按照如下方式，依次求解w\[j\]，其中j是整数并且属于\[4,43\]；

3)  若j%4=0,则w\[j\]=w\[j-4\]⊕g(w\[j-1\]),否则w\[j\]=w\[j-4\]⊕w\[j-1\]；

函数g的流程说明：

a)  将w循环左移8比特；

b)  分别对每个字节做S盒置换；

c)  与32比特的常量（RC\[j/4\],0,0,0）进行异或，RC是一个一维数组，其值如下。（RC的值只需要有10个，而此处用了11个，实际上RC\[0\]在运算中没有用到，增加RC\[0\]是为了便于程序中用数组表示。由于j的最小取值是4，j/4的最小取值则是1，因此不会产生错误。）

RC = \{0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1B, 0x36\}

## 1.6 小结 ##

密码算法要求是可逆的，这样解密算法才能正确的恢复明文。拿AES来说，在密钥固定的情况下，明文和密文在整个输入空间是一一对应的。因此算法的各个部件也都是可逆的，再将各个部件的操作顺序设计成可逆的，密文就能正确的解密了。

# 2 源码 #

自己写了一份[AES-128][]的实现代码，放在Github上；另外一份[AES][]代码实现了3种密钥长度的算法，和标准文档完全保存一致，没有做任何优化，有兴趣可以看看。

AES中列混淆部分设计有限域乘法操作，在运行中需要消耗较多的时间。现在的计算平台都拥有丰富的软件资源(RAM、Flash等)，因此AES的软件实现一般都会采用**查表**的方式，将字节替代、行移位、列混淆合在一起查表，大概消耗8-10K字节的存储空间，但效率非常之高。

在硬件上，为了减少实现面积，可以通过对解密的操作进行适当调换，这样解密操作可以复用加密的电路。

# 3 扩展 #

SIMD \[10\]：单指令流多数据流指令，最常用的包括SSE、SSE2、AVX、AVX512 \[5\] 等，现在很多Intel和AMD的处理器都支持。SIMD操作能够很大地提高效率，一些项目中都有用到，比如libsodium \[6\]（A modern and easy-to-use crypto library）、FastMemcpy \[7\] （Speed-up over 50% in average vs traditional memcpy in gcc 4.9 or vc2012 ）、hamming\_weight \[8\] （C library to compute the Hamming weight of arrays）等。

AES-NI \[9\]：AES硬件指令，能够很快地实现AES加解密，大部分Intel处理器、AMD处理器支持。

# 4 参考文献 #

\[1\] William Stallings著；王张宜等译. 密码编码学与网络安全——原理与实践（第五版）\[M\]. 北京：电子工业出版社，2012.1.

\[2\] Daemen J, Rijmen V. AES proposal: Rijndael\[J\]. 1998.

\[3\] Advanced Encryption Standard, [https://en.wikipedia.org/wiki/Advanced\_Encryption\_Standard][https_en.wikipedia.org_wiki_Advanced_Encryption_Standard], 2017年3月获取.

\[4\] Joan Daemen and Vincent Rijmen, The Design of Rijndael, AES - The Advanced Encryption Standard, Springer-Verlag 2002 (238 pp.)

\[5\] SSE, SSE2, AVX, AVX512等, [https://software.intel.com/sites/landingpage/IntrinsicsGuide/][https_software.intel.com_sites_landingpage_IntrinsicsGuide], 2017年6月获取.

\[6\] Libsodium, [https://github.com/jedisct1/libsodium][https_github.com_jedisct1_libsodium], 2017年6月获取.

\[7\] FastMemcpy, [https://github.com/skywind3000/FastMemcpy][https_github.com_skywind3000_FastMemcpy], 2017年6月获取.

\[8\] Hamming\_weight, [https://github.com/CountOnes/hamming\_weight][https_github.com_CountOnes_hamming_weight], 2017年6月获取.

\[9\] AES-NI, [https://en.wikipedia.org/wiki/AES\_instruction\_set][https_en.wikipedia.org_wiki_AES_instruction_set], 2017年6月获取.

\[10\] SIMD, [https://en.wikipedia.org/wiki/SIMD][https_en.wikipedia.org_wiki_SIMD], 2017年6月获取.

# **更新说明** #

**2017.11.19**

a) 完善了评选指标的说明；

**2017.06.03**

**   ** a) 列混淆中加法是模28，不是模2；

b) 增加了SIMD和AES-NI的介绍；

**2017.03.15**

a) 增加了Rijndael和AES的区别；b) 增加了参考文献；c) 提到AES查表的实现；d) 循环移位不以字节为单位，统一改成比特；

e) 修复了Rijndael算法链接的错误；f) 更正了错别字;

[https_www.cnblogs.com_luop_p_4334160.html]: https://www.cnblogs.com/luop/p/4334160.html
[Rijndael]: http://csrc.nist.gov/archive/aes/rijndael/Rijndael-ammended.pdf
[Serpent]: http://cryptosoft.net/docs/Serpent.pdf
[Twofish]: https://www.schneier.com/academic/paperfiles/paper-twofish-paper.pdf
[RC6]: https://people.csail.mit.edu/rivest/pubs/RRSY98.pdf
[671127-20160524103729100-1928102316.jpg]: /images/20220112/c187206133e94e7bae9fac9917f7c6d7.png
[Joan Daemen]: https://en.wikipedia.org/wiki/Joan_Daemen
[Vincent Rijmen]: https://en.wikipedia.org/wiki/Vincent_Rijmen
[130035028553414.png]: /images/20220112/029178bf8c194c598dbb68fae6d2ec66.png
[130038570278987.png]: /images/20220112/cb5e403667714b22bd384f43dc8d51f9.png
[130039158865217.png]: /images/20220112/e2115571f9584ae08ffc3b0cecb6e1fd.png
[130047023709062.png]: /images/20220112/726eac2fb3b54863908dfdbafa4bf54a.png
[130052373249725.png]: /images/20220112/c1868894fc054ab695a666e2562cffd8.png
[130102368866430.png]: /images/20220112/1fd3c1ab054d4942bc8d61961baa6df3.png
[130105054177539.png]: /images/20220112/f9558f441fd14744aaa514adfcbf0c12.png
[130108397307413.png]: /images/20220112/37b906f2a1e642baaed3f3fe5585af7e.png
[130110187306459.png]: /images/20220112/017bac8694ae4ba5850718e35061c1b8.png
[130112236057708.png]: /images/20220112/9ca8fbeec5b6467aa67b587924b4e611.png
[AES-128]: https://github.com/openluopworld/aes_128
[AES]: https://github.com/dhuertas/AES/blob/master/aes.c
[https_en.wikipedia.org_wiki_Advanced_Encryption_Standard]: https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
[https_software.intel.com_sites_landingpage_IntrinsicsGuide]: https://software.intel.com/sites/landingpage/IntrinsicsGuide/
[https_github.com_jedisct1_libsodium]: https://github.com/jedisct1/libsodium
[https_github.com_skywind3000_FastMemcpy]: https://github.com/skywind3000/FastMemcpy
[https_github.com_CountOnes_hamming_weight]: https://github.com/CountOnes/hamming_weight
[https_en.wikipedia.org_wiki_AES_instruction_set]: https://en.wikipedia.org/wiki/AES_instruction_set
[https_en.wikipedia.org_wiki_SIMD]: https://en.wikipedia.org/wiki/SIMD