AES加密算法和RSA加密算法

引用

AES加密算法原理
AES加密算法的C++实现
密码算法详解——AES(高级加密算法)

1. 前言

本文针对加密算法进行部分介绍，主要包括两种算法，分别为AES加密算法和RSA加密算法。
加密算法分为单向加密和双向加密。
单向加密包括MD5，SHA加密算法等等。单向加密算法是不可逆的，也就是无法将加密后的数据恢复成原始数据，除非采取碰撞攻击和穷举的方式。像是银行账户密码的存储，一般采用的就是单向加密的方式。
双向加密是可逆的，存在密文的密钥，持有密文的一方可以根据密钥解密得到原始明文，一般用于发送方和接收方都能通过密钥获取明文的情况。双向加密包括对称加密和非对称加密。对称加密包括DES加密，AES加密等等，本文档介绍的主要是AES加密。而非对称加密包括RSA加密，ECC加密。

2. AES算法

AES加密算法（Advanced Encryption Standard）：是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES。

图1 AES加密算法的流程

AES加密主要包括两个步骤：密钥扩展和明文加密。
密钥扩展：将输入的密钥（16字节、24字节和32字节）进行扩展，根据密钥长度的不同，得到扩展后的密钥进行加密的轮数也不相同。

图2 密钥扩展算法

密钥扩展过程说明（密钥为16字节）：
　　　　1) 将初始密钥以列为主，转化为4个32 bits的字，分别记为w[0…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的流程说明：
　　　　4) 将w循环左移一个字节；
　　　　5) 分别对每个字节按S盒进行映射；
　　　　6) 与32 bits的轮常量Rcon[j]进行异或。
轮常量（Rcon）是一个字，最右边三个字节总为0。因此字与Rcon相异或，其结果只是与该字最左的那个字节相异或。每轮的轮常量不同，定位为Rcon[j] = (RC[j], 0, 0, 0)。（RC是一维数组）
RC生成函数：RC[1] = 1, RC[j] = 2 * RC[j – 1]。
因为16字节密钥的只进行10轮的扩展，所以最后生成的RC[j]的值按16进制表示为：

图3 RC值

十轮的密钥扩展后，就能生成44个字大小的扩展密钥。扩展后的密钥将用于AES对明文的加密过程。

明文加密：
从图1可以看到，无论是AES的加密和解密过程，都涉及到四个主要的步骤：字节代替、行移位、列混淆和轮密钥加。以下对这四个过程进行详细说明。
① 字节代替：将输入状态的每个字节使用S盒上对应的字节进行替换
输入状态：是一个4×4的数组，数组内每个元素由输入的明文分组组成，按照列进行排序，比如输入的明文数据为193de3bea0f4e22b9ac68d2ae9f84808，则输入状态为

图4 输入状态矩阵

S盒是16×16个字节组成的矩阵，行列的索引值分别从0开始，到十六进制的F结束，每个字节的范围为（00-FF）。

图5 S盒

进行字节代替的时候，把状态中的每个字节分为高4位和低4位。高4位作为行值，低4位作为列值，以这些行列值作为索引从S盒的对应位置取出元素作为输出，如下图所示：

图6 S盒替换

S盒的构造方式如下：
（1） 按字节值得升序逐行初始化S盒。在行y列x的字节值是{yx}。
（2） 把S盒中的每个字节映射为它在有限域GF中的逆;{00}映射为它自身{00}。
（3） 把S盒中的每个字节的8个构成位记为(b7, b6, b5, b4, b3, b2, b1)。对S盒的每个字节的每个位做如下的变换：

图7 S-box盒生成公式

ci指的是值为{63}的字节c的第i位。
解密过程逆字节代替使用的是逆S盒，构造方式为

图8 逆S-box盒生成公式

字节d={05}。

② 行移位：状态的第一行保持不变。第二行循环左移一个字节，第三行左移两个字节，第四行循环左移三个字节。

图9 正向行移位

逆向行移位将状态中后三行执行相反方向的移位操作，如第二行向右循环移动一个字节，其他行类似。
③ 列混淆：将每列中的每个字节映射为一个新值，新值由该列中的4个字节通过函数变换得到。

图10 正向列混淆

要注意，图示的矩阵的乘法和加法都是定义在GF(2^8)上的。
逆向列混淆原理如下：

图11 逆向列混淆

④ 轮密钥加：将当前分组和扩展密钥的一部分进行按位异或。
扩展密钥通过图2的扩展密钥算法已经求出来了，所以这一步的步骤就是将分组与一部分扩展密钥按位异或操作。

图12 轮密钥加

轮密钥加后的分组再进行一次轮密钥加就能恢复原值，原理如下：

所以，只要经过密钥扩展和明文加密，就能将明文加密成密文，进行解密的时候，只需要进行逆向变换即可。

图1中还需要注意，明文输入到输入状态后，需要进行一轮的轮密钥加，对输入状态进行初始化。前9轮的加密过程，都需要进行字节替代、行移位、列混淆和轮密钥加，但是第10轮则不再需要进行列混淆。

进行解密的时候，需要进行逆向字节替代，逆向行移位、逆向列混淆和轮密钥加。

3.RSA公钥加密算法

RSA公钥加密算法是一种非对称加密算法，在1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。算法RSA也是采用了他们姓氏开头组成。
RSA算法较AES加密算法较为简单，其计算流程主要如下：

图13 RSA流程

RSA算法的正确性可以由以下证明：

图14 RSA正确性验证

4.参考文献

[1] William Stallings著；唐明等译. 密码编码学与网络安全——原理与实践（第六版）[M]. 北京：电子工业出版社，2015.3.