蓝狮娱乐-蓝狮注册登录站

AES算法实现与优化

日期:2024-07-08 21:28 / 作者:佚名

高级加密标准(英语:Advanced Encryption Standard,缩写:AES),又称Rijndael加密法(荷兰语发音: [?r?inda?l],音似英文的“Rhine doll”),是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES,已经被多方分析且广为全世界所使用。经过五年的甄选流程,高级加密标准由美国国家标准与技术研究院(NIST)于2001年11月26日发布于FIPS PUB 197,并在2002年5月26日成为有效的标准。现在,高级加密标准已然成为对称密钥加密中最流行的算法之一。

该算法为比利时密码学家Joan Daemen和Vincent Rijmen所设计,结合两位作者的名字,以Rijndael为名投稿高级加密标准的甄选流程。

密钥长度 128、192、156bit
分组长度 128bit
结构 置换排列网络
重复回数 10、12、14等(视密钥长度而定)

关系密码攻击可以破解9个加密循环/256比特(密钥)的AES。另外选择明文攻击可以破解8个加密循环,192或256比特(密钥)的AES,或7个加密循环、128位(密钥)的AES。

严格地说,AES和Rijndael加密法并不完全一样(虽然在实际应用中两者可以互换),因为Rijndael加密法可以支持更大范围的区块和密钥长度:AES的区块长度固定为128比特,密钥长度则可以是128,192或256比特;而Rijndael使用的密钥和区块长度均可以是128,192或256比特。加密过程中使用的密钥是由Rijndael密钥生成方案产生。

大多数AES计算是在一个特别的有限域完成的。

AES加密过程是在一个4×4的字节矩阵上运作,这个矩阵又称为“体(state)”,其初值就是一个明文区块(矩阵中一个元素大小就是明文区块中的一个Byte)。(Rijndael加密法因支持更大的区块,其矩阵的“列数(Row number)”可视情况增加)加密时,各轮AES加密循环(除最后一轮外)均包含4个步骤:

  1. —矩阵中的每一个字节都与该次轮密钥(round key)做XOR运算;每个子密钥由密钥生成方案产生。
  2. —透过一个非线性的替换函数,用查找表的方式把每个字节替换成对应的字节。
  3. —将矩阵中的每个横列进行循环式移位
  4. —为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每内联的四个字节。最后一个加密循环中省略步骤,而以另一个取代。

代码流程图如下图:

img

对应的c语言代码如下:


解谜操作与加密操作相反,

步骤,回合密钥将会与原矩阵合并。在每次的加密循环中,都会由主密钥产生一把回合密钥(通过Rijndael密钥生成方案产生),密钥大小会跟原矩阵一样,与原矩阵中每个对应的字节作XOR操作。

img

对应的c代码如下:



在步骤中,矩阵中的各字节通过一个8位的 S-box 进行转换。这个步骤提供了加密法非线性的变换能力。S-box 与 $GF(2^8)$ 上的乘法逆元有关,已知具有良好的非线性特性。为了避免简单代数性质的攻击,S-box结合了乘法逆元及一个可逆的仿射变换矩阵建构而成。此外在建构S-box时,刻意避开了不动点反不动点,即以S-box替换字节的结果会相当于错排的结果。

img

对应的c代码:


AES算法的 S-box



描述矩阵的列操作。在此步骤中,每一列都向左循环位移某个偏移量。在AES中(区块大小128位),第一列维持不变,第二列里的每个字节都向左循环移动一格。同理,第三列及第四列向左循环位移的偏移量就分别是2和3。128位和192比特的区块在此步骤的循环位移的模式相同。经过之后,矩阵中每一竖行,都是由输入矩阵中的每个不同行中的元素组成。Rijndael算法的版本中,偏移量和AES有少许不同;对于长度256比特的区块,第一列仍然维持不变,第二列、第三列、第四列的偏移量分别是1字节、2字节、3字节。除此之外,操作步骤在Rijndael和AES中完全相同。

img

对应的c代码:



在步骤,每一列的四个字节通过线性变换互相结合。每一列的四个元素分别当作${\displaystyle 1,x,x{2},x{3}}$ 的系数,合并即为 ${\displaystyle GF(2^{8})}$ 中的一个多项式,接着将此多项式和一个固定的多项式 ${\displaystyle c(x)=3x{3}+x+x+2}$ 在模 ${\displaystyle x^{4}+1}$ 下相乘。此步骤亦可视为Rijndael有限域之下的矩阵乘法。函数接受4个字节的输入,输出4个字节,每一个输入的字节都会对输出的四个字节造成影响。因此和两步骤为这个密码系统提供了扩散性

img

对应c代码:



Rijndael的作者曾经为该算法提供了一个[主页](IAIK Krypto Group - AES Lounge (archive.org))。

现在这个主页的内容已经扩充了许多内容:

包括一些分析AES安全性的论文、AES硬件实现、高速AES实现、低代价AES实现、软件实现、侧信道分析、出错分析、AES扩展指令集等等内容。

image-20211024154921442

可以看到AES加密速率从2001年的1.82Gbits/sec发展到2005年21.54Gbits/sec以及70Gbits/sec,发展非常迅速,大多都是使用FPGA在硬件算法实现层面进行的优化。

image-20211024155238941

在侧信道分析部分可以看到经典的论文,比如AES高阶掩码,功率分析等等。有机会可以看一看。

在软件中实现AES时应该小心,特别是围绕侧通道攻击。

对较短的块进行加密只能通过填充源字节(通常使用空字节)来实现。

分组密码有五种工作体制:

  1. 电码本模式(Electronic Codebook Book (ECB));
  2. 2.密码分组链接模式(Cipher Block Chaining (CBC));
  3. 计算器模式(Counter (CTR));
  4. 密码反馈模式(Cipher FeedBack (CFB));
  5. 输出反馈模式(Output FeedBack (OFB))

电码本模式(Electronic Codebook Book (ECB)

这种模式是将整个明文分成若干段相同的小段,然后对每一小段进行加密。

img

这个方法很简单,但是不安全,因为保留了明文的结构信息。

对应的c代码实现:


密码分组链接模式(Cipher Block Chaining (CBC))

这种模式是先将明文切分成若干小段,然后每一小段与初始块或者上一段的密文段进行异或运算后,再与密钥进行加密。

img

对应c实现:


计算器模式(Counter CTR)

计算器模式不常见,在CTR模式中, 有一个自增的算子,这个算子用密钥加密之后的输出和明文异或的结果得到密文,相当于一次一密。这种加密方式简单快速,安全可靠,而且可以并行加密,但是在计算器不能维持很长的情况下,密钥只能使用一次。CTR的示意图如下所示:

img

对应的c代码:


其他两种比较复杂,不再详细说明、也没有写相应的代码。

使用32或更多比特寻址的系统,可以事先对所有可能的输入创建对应表,利用查表来实现,和步骤以达到加速的效果。这么做需要产生4个表,每个表都有256个格子,一个格子记载32位的输出;约占去4KB(4096字节)存储器空间,即每个表占去1KB的存储器空间。如此一来,在每个加密循环中,只需要查16次表,作12次32位XOR运算,以及AddRoundKey步骤中4次32位XOR运算。若使用的平台存储器空间不足4KB,也可以利用循环交换的方式一次查一个256格32位的表。参考文章:Efficient Software Implementation of AES on 32-Bit Platforms | SpringerLink

使用一种面向字节的方法,即从字节的角度分析,可以将, , 三个步骤合为一个操作。参考资料中也给出了相应的论文和实现。

不使用查找表时的优化

这种优化面向嵌入式设备,因为设备内存通常不足4KB。实际上这种优化目前已经有人完成、并且将所有的查找表替换为了实时计算。参考资料7中有详细的描述。

仅仅使用 Sbox 查找表的优化

这项工作在2003年由Bertoni等人完成,它们在低内存嵌入式设备中仅仅使用Sbox和InvSbox的情况下对AES算法进行了优化。详细内容见参考资料9,11。

算法的关键是使用了明文矩阵的转置

image-20211024213845946

这个操作非常简单,但是有一些非常有趣的结果。

结果是 , , 与之前的操作时类似的,但是通过这个转置运算可以被极大地加速。

在旧的 中,操作是这样的,实际上是 $GF(2^8)$ 上的矩阵乘法:

image-20211024214201918

每一列代价为4次乘法,4次XOR加法,3次移位操作。

总代价为 16次 $GF(2^8)$ 乘法,16次加法,12次移位以及一个中间变量。

新的 操作:

image-20211024220127249

区别在于以行来处理state数组而不是按列处理。

新的 需要16次乘法和16次XOR运算,不需要其他操作。

解密与加密类似,详细内容查看参考资料9和11。

面向字节、全查表加密优化

理论上来讲这种方法的速度最快(如果将上面的优化结合起来应该会更快,由于时间限制,不能写出完整的代码),但是并不安全,优化的核心是将运算过程用查表的方式实现,以下是用到的几个查询表:

Sbox && InvSbox

分别是Sbox和Sbox的逆


Xtime2Sbox && Xtime3Sbox

Xtime2Sbox这个表是Xtime2和Sbox的组合,即Xtime2[Sbox[]],Xtime3Sbox同理,在加密过程中用来做有限域中的乘法,在上面的算法说明中有解释。


Xtime2 && Xtime9 && XtimeB && XtimeD && XtimeE

在解密时使用,用于有限域乘法,是加密多项式的乘法逆元。


优化加密函数

在这个角度上,加密函数可以写为:


操作的查表实现:


的查表实现:


这个函数将 三个函数结合在一起,其中XtimeXSbox[]等于XtimeX[Sbox[]]。

操作与前面的算法是一致的:


解密函数优化

与加密类似,解密也采用查表实现。


实现:


实现:


查表存在的问题

然而,实际实现中应避免使用这样的对应表,否则可能因为产生缓存命中与否的差别而使侧信道攻击成为可能。

利用AES-NI指令进行优化

这一部分详细资料在参考资料12,即Intel AES-NI白皮书。

利用硬件指令的优化是软件实现的降维打击,可以做到 $1.3 cycles/sec$,甚至可以做到 $0.36cycles/sec$。

Crypo++官方benchmark例程中,CTR模式AES速度轻松达到 $4400Mb/sec$ 。在参考资料中给出了crypo++的源代码,试着阅读之后,由于时间关系还是放弃了分析。

下面是基本没有优化的使用AES-NI实现的AES算法,首先是加密函数:


解密函数:


优化结果

仅仅使用 Sbox 查找表的优化

以CPU周期数为计量单位,仅仅使用Sbox加解密时,测试的结果如下:

image-20211024221234626 image-20211024221423677

与 Gladman 给出的算法的对比:

image-20211024221310923

可以看到算法在解密方面提升很大。

面向字节、全查表优化结果

image-20211024223721606

经过五次运行测试,取平均值最终得到的结果如下:

加密时间(CPU cycle) 解密时间(CPU cycle)
73 111
image-20211024224338858

测试的CPU为 ,主频2400MHz。

加密速率 $ES=cpu_{fre}/t_{encrypt}=2400 * 10^6/73=32.88 * 10^6bytes/sec$

解密速率 $DS=cpu_{fre}/t_{decrypt}=2400*106/111=21.62*106bytes/sec$

使用AES-NI指令优化结果

image-20211025002558748

6.04452s内完成了789949975次AES操作。

加密速率 $ES=789949975/6.04452*16bytes/sec=1994.15Mb/s$

通过读取随机文件得到的结果:

用 命令生成随机文件。

这里读取随机文件大小为16MB,速率为 ,但是使用 函数测量会导致结果不准确,然而使用 汇编指令出现了一些问题。可能由于解密速率过大,导致 函数两次返回值相同。

所以将设置文件大小为168MB,再次运行:

加密速率为 $3902.44Mb/s$

解密速率为 $2711.86Mb/s$

多次运行,加密速率最高达到 $4705.88Mb/s$

image-20211025102716683

多次运行,解密速率最高达到 $4102.56Mb/s$

image-20211025102511008

  1. AES implementations - Wikipedia
  2. Advanced Encryption Standard - Wikipedia
  3. Cryptography - 256 bit ciphers (embeddedsw.net)
  4. The Rijndael Page (archive.org)
  5. kokke/tiny-AES-c: Small portable AES128/192/256 in C (github.com)
  6. AES五种加密模式(CBC、ECB、CTR、OCF、CFB) - 月之星狼 - 博客园 (cnblogs.com)
  7. A byte-oriented AES-256 implementation - Literatecode
  8. High-Speed Area-Efficient Implementation of AES Algorithm on Reconfigurable Platform | IntechOpen
  9. Efficient Software Implementation of AES on 32-Bit Platforms | SpringerLink
  10. Google Code Archive - Long-term storage for Google Code Project Hosting.
  11. Microsoft PowerPoint - Bertoni (iacr.org)
  12. Efficient AES Implementations on Westmere (intel.com)
  13. AES-NI Performance Analyzed; Limited To 32nm Core i5 CPUs | Tom's Hardware (tomshardware.com)
  14. Release Crypto++ 8.6 release · weidai11/cryptopp (github.com)

平台注册入口