size_t ex_gcd(size_t a, size_t b, size_t *x, size_t *y)
{
size_t d = 0, t = 0;
if (b == 0) {
x = 1, y = 0;
return a;
}
d = ex_gcd(b, a % b, x, y), t = x;
*x = *y;
*y = t - a / b * (*x);
return d;
}
了解了扩展欧几里得，我们来看它与乘法逆元的关系。
逆元：a 关于 模b 的逆元 整数d 满足 $ad \mod b ≡ 1$
扩展欧几里得：求方程$ax+by=GCD(a,b)$ 的一组解
size_t ex_gcd_inv(size_t a, size_t b)
{
size_t x = 0, y = 0;
ex_gcd(a, b, &x, &y);
return x;
}
// The SubBytes Function Substitutes the values in the
// state matrix with values in an S-box.
static void sub_bytes(state_t* state)
{
uint8_t i, j;
for (i = 0; i < 4; ++i) {
for (j = 0; j < 4; ++j) {
(*state)[j][i] = get_sbox_value((*state)[j][i]);
}
}
}
// The ShiftRows() function shifts the rows in the state to the left.
// Each row is shifted with different offset.
// Offset = Row number. So the first row is not shifted.
static void shift_rows(state_t* state)
{
uint8_t temp = 0;
// Rotate first row 1 columns to left
temp = (*state)[0][1];
(*state)[0][1] = (*state)[1][1];
(*state)[1][1] = (*state)[2][1];
(*state)[2][1] = (*state)[3][1];
(*state)[3][1] = temp;
// Rotate second row 2 columns to left
temp = (*state)[0][2];
(*state)[0][2] = (*state)[2][2];
(*state)[2][2] = temp;
temp = (*state)[1][2];
(*state)[1][2] = (*state)[3][2];
(*state)[3][2] = temp;
// Rotate third row 3 columns to left
temp = (*state)[0][3];
(*state)[0][3] = (*state)[3][3];
(*state)[3][3] = (*state)[2][3];
(*state)[2][3] = (*state)[1][3];
(*state)[1][3] = temp;
}
int32_t aes_enc_cfb128(struct aes_ctx* ctx, uint8_t* buf, size_t buf_len)
{
int32_t ret = 0;
size_t i;
uint8_t *iv = NULL;
if (0 == buf_len) {
goto finish;
}
if (NULL == ctx || NULL == buf) {
printf("[error] : ctx or buf pointer is NULL\n");
ret = -1;
goto finish;
}
iv = ctx->iv;
for (i = 0; i < buf_len; i += AES_BLOCKLEN) {
aes(iv, ctx->round_key);
xor_with_iv(buf, iv);
iv = buf;
buf += AES_BLOCKLEN;
}
/* store Iv in ctx for next call */
memcpy(ctx->iv, iv, AES_BLOCKLEN);
finish:
return ret;
}
int32_t aes_dec_cfb128(struct aes_ctx* ctx, uint8_t* buf, size_t buf_len)
{
int32_t ret = 0;
size_t i;
uint8_t *iv = NULL;
uint8_t store_next_iv[AES_BLOCKLEN] = {0};
if (0 == buf_len) {
goto finish;
}
if (NULL == ctx || NULL == buf) {
printf("[error] : ctx or buf pointer is NULL\n");
ret = -1;
goto finish;
}
for (i = 0; i < buf_len; i += AES_BLOCKLEN) {
memcpy(store_next_iv, buf, AES_BLOCKLEN);
aes_inv((state_t *)iv, ctx->round_key);
xor_with_iv(buf, ctx->iv);
memcpy(ctx->iv, store_next_iv, AES_BLOCKLEN);
buf += AES_BLOCKLEN;
}
finish:
return ret;
}
3.4 CTR
/* Symmetrical operation: same function for encrypting as for decrypting. Note any IV/nonce should never be reused with the same key */
int32_t aes_enc_ctr(struct aes_ctx* ctx, uint8_t* buf, size_t buf_len)
{
uint8_t buffer[AES_BLOCKLEN];
size_t i;
int32_t bi;
for (i = 0, bi = AES_BLOCKLEN; i < buf_len; ++i, ++bi) {
if (bi == AES_BLOCKLEN) { /* we need to regen xor compliment in buffer */
memcpy(buffer, ctx->iv, AES_BLOCKLEN);
aes((state_t*)buffer, ctx->round_key);
/* Increment Iv and handle overflow */
for (bi = (AES_BLOCKLEN - 1); bi >= 0; --bi) {
/* inc will overflow */
if (ctx->iv[bi] == 255) {
ctx->iv[bi] = 0;
continue;
}
ctx->iv[bi] += 1;
break;
}
bi = 0;
}
buf[i] = (buf[i] ^ buffer[bi]);
}
}
int32_t aes_dec_ctr(struct aes_ctx* ctx, uint8_t* buf, size_t buf_len)
{
return aes_enc_ctr(ctx, buf, buf_len);
}
3.1_Security_对称密钥算法之AES
进阶加密标准（英语：Advanced Encryption Standard，缩写：AES），又称Rijndael加密法（荷兰语发音： [ˈrɛindaːl]，音似英文的“Rhine doll”），是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，进阶加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。现在，进阶加密标准已然成为对称金钥加密中最流行的演算法之一。
本节继承3.0_Security_对称密钥算法加解密通用实现，来介绍AES主算法。本文包括：
1. 相关数学知识
本节介绍AES中所用到的数学知识，这些算法的C语言实现在https://github.com/carloscn/cryptography/blob/master/lib/carlos/math_utils.c 定义。
1.0 素域
1.0.1 素数
素数也称谓质数，只能被1和本身整除的，密码学中经常用到素数。这里有一个快速判断素数的方法：
1.0.2 伽罗瓦域
我们所有的计算都是在有限域中进行计算的。有限域有时也称伽罗瓦域，它指的是由有限个元素组成的集合，在这个集合内可以执行加、减、乘和逆运算。而在密码编码学中，我们只研究拥有有限个元素的域，也就是有限域。域中包含元素的个数称为域的阶。只有当m是一个素数幂时，即m=p^n(其中n为正整数是p的次数，p为素数)，阶为m的域才存在。p称为这个有限域的特征。
也就是说，有限域中元素的个数可以是11(p=11是一个素数,n=1)、可以是81(p=3是一个素数，n=4)、也可以是256(p=2是一个素数，n=8).....但有限域的中不可能拥有12个元素，因为12=2·2·3，因此12也不是一个素数幂。
有限域中最直观的例子就是阶为素数的域，即n=1的域。域GF(p)的元素可以用整数0、1、...、p-1l来表示。域的两种操作就是模整数加法和整数乘法模p。加上p是一个素数，整数环Z表示为GF(p)，也成为拥有素数个元素的素数域或者伽罗瓦域。GF(p)中所有的非零元素都存在逆元，GF(p)内所有的运算都是模p实现的。
素域内的算数运算规则如下：
注：GF(2)是一个非常重要的素域，也是存在的最小的有限域，由于GF(2)的加法，即模2加法与异或(XOR)门等价，GF(2)的乘法与逻辑与(AND)门等价，所以GF(2)对AES非常重要。
1.0.3 扩展域
如果有限域的阶不是素数，则这样的有限域内的加法和乘法运算就不能用模整数加法和整数乘法模p表示。而且m>1的域被称为扩展域，为了处理扩展域，我们就要使用不同的符号表示扩展域内的元素，使用不同的规则执行扩展域内元素的算术运算。
在扩展域GF(2^m)中，元素并不是用整数表示的，而是用系数为域GF(2)中元素的多项式表示。这个多项式最大的度(幂)为m-1，所以每个元素共有m个系数，在AES算法使用的域GF(2^8)中，每个元素A∈GF(2^8)都可以表示为：
$$ A(x) = a_7x^7 + a_6x^6 + ... + a_1x, a_i \in GF(2) = 0,1
$$
注意：在域GF(2^8)中这样的多项式共有256个，这256个多项式组成的集合就是扩展域GF(2^8)。每个多项式都可以按一个8位项链的数值形式存储：
$$ A = (a_7, a_6, a_5, a_4, a_3, a_2, a_1, a_0) $$
像x^7、x^6等因子都无需存储，因为从位的位置就可以清楚地判断出每个系数对应的幂。
扩展域GF(2^m)内的加减法
在AES算法中的密钥加法层中就使用了这部分的知识，但是不是很明显，因为我们通常把扩展域中的加法当作异或运算进行处理了，因为在扩展域中的加减法处理都是在底层域GF(2)内完成的，与按位异或运算等价。假设$A(x), B(x) \in GF(2^m)$，计算两个元素之和的方法就是：
$$ C(x) = A(x) + B(x) = \sum_{i=0}^{m-1}C_ix^i, c_i \equiv (a_i + b_i) \% 2
$$
而两个元素之差的计算公式就是：
$$ C(x) = A(x) - B(x) = \sum_{i=0}^{m-1}C_ix^i, c_i \equiv (a_i - b_i) \% 2 \equiv (a_i + b_i) \% 2
$$
在减法运算中减号之所以变成加号，这就和二进制减法的性质有关了
扩展域GF(2^m)内的乘法
扩展域的乘法主要运用在AES算法的列混淆层(Mix Column)中，也是列混淆层中最重要的操作。我们项要将扩展域中的两个元素用多项式形式展开，然后使用标准的多项式乘法规则将两个多项式相乘：
在多项式乘法中C(x)的度会大于m-1，因此需要对此进行化简，而化简的基本思想与素域内乘法情况相似：在素域GF(p)中，将两个整数相乘得到的结果除以一个素数，化简后的结果就是最后的余数。而在扩展域中进行的操作就是：将两个多项式相乘的结果除以一个不可约多项式，最后的结果就是最后的余数。(这里的不可约多项式大致可以看作一个素数)
举例：
1.1 欧几里得算法 Euclid's algorithm
欧几里得算法（英语：Euclidean algorithm），又称 辗转相除法，是求最大公约数的算法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。还有另一种秋两数的最大公约数的方法：更相减损法。
举例： 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：
至此，最大公约数为1。
使用C语言实现欧几里得算法：
1.2 乘法逆元[^1]
数学上的乘法逆元就是指直观的倒数，即 a 的逆元是 1/a，也即与 a 相乘得 1 的数。ax=1，则x是a的乘法逆元。
这里我们讨论关于取模运算的乘法逆元，即对于整数 a，与 a 互质的数 b 作为模数，当整数 x 满足
(ax) mod (b) ≡ 1时，称 x 为 a 关于模 b 的逆元，代码表示就是a * x % b == 1，求x的值。求逆元通常有三种算法：扩展欧几里得、费马小定理、递推求逆元。 （只介绍前两个）
1.2.1 扩展欧几里得
扩展欧几里得算法是用于解决形如$ax+by=d$（a, b, d是整常数，x, y是整数）的不定方程的求整数解的问题的一种方法。它同样因为易于理解以及简单而被广泛使用。它的使用并不是广泛的，它需要先满足 $ax+by=gcd(a,b)=d$ 这一条件（贝祖等式）才能够用于求整数解。
扩展欧几里得算法主要应用是求乘法的逆元，乘法逆元在公钥密码学中占有着举足轻重的地位。
扩展欧几里得算法则是求：
$$ ax+by=GCD(a,b) $$
了解了扩展欧几里得，我们来看它与乘法逆元的关系。
时间复杂度：大约
O(logn)（斐波那契复杂度）。适用范围：存在逆元即可求，适用于个数不多但模数b很大的时候，最常用、安全的求逆元方式。1.2.2 费马小定理 Fermat's little theorem
费马小定理：对于整数 a 与质数 b ，若 a 与 b 互质，则有：
$$ a^{b-1} \mod b ≡ 1 $$
快速幂求模
求
x ^ n % MOD，n很大时需要用折半的思想。如下所示求2^15：可以看到，两两结合的时候，如果数字个数是奇数就会有“零头”，把零头存入
ret，最终结果就是256 x 2 x 4 x 16。上文费马小定理的式子等价于：
$$ a \times a^{b-2} \mod b ≡ 1 $$
显然 $a^{b-2}$就是 $a$ 模 $b$ 的逆元。求逆元，就用 $b-2$ 和 $b$ 代替 快速幂取模中的
n和mod：时间复杂度：大约
O(log b)。适用范围：一般在模数b是质数的时候。2. AES加解密原理^2
大多數AES計算是在一個特別的有限域完成的。
AES加密过程是在一个4×4的位元组矩阵上运作，这个矩阵又称为“体（state）”，其初值就是一个明文区块（矩阵中一个元素大小就是明文区块中的一个Byte）。（Rijndael加密法因支援更大的区块，其矩阵的“列数（Row number）”可视情况增加）加密时，各轮AES加密回圈（除最后一轮外）均包含4个步骤：
2.1 AES算法步骤
2.1.1 AddRoundKey步骤
AddRoundKey步骤，回合密钥将会与原矩阵合并。在每次的加密回圈中，都会由主密钥产生一把回合金钥（透过Rijndael密钥生成方案产生），这把密钥大小会跟原矩阵一样，以与原矩阵中每个对应的位元组作异或（⊕）加法。在AddRoundKey步骤中，将每个状态中的位元组与该回合密钥做异或（⊕）：
2.1.2 SubBytes步骤
在SubBytes步骤中，矩阵中的各字节透过一个8位元的S-box进行转换。这个步骤提供了加密法非线性的变换能力。S-box与${GF(2^{8})}$上的乘法反元素有关，已知具有良好的非线性特性。为了避免简单代数性质的攻击，S-box结合了乘法反元素及一个可逆的仿射变换矩阵建构而成。此外在建构S-box时，刻意避开了不动点与反不动点，即以S-box替换字节的结果会相当于错排的结果。Rijndael S-box条目有针对S-box的详细描述。
2.1.3 ShiftRows步骤
ShiftRows描述矩阵的行操作。在此步骤中，每一行都向左循环位移某个偏移量。在AES中（区块大小128位元），第一行维持不变，第二行里的每个位元组都向左循环移动一格。同理，第三行及第四行向左循环位移的偏移量就分别是2和3。128位元和192位元的区块在此步骤的循环位移的模式相同。经过ShiftRows之后，矩阵中每一竖列，都是由输入矩阵中的每个不同列中的元素组成。Rijndael演算法的版本中，偏移量和AES有少许不同；对于长度256位元的区块，第一行仍然维持不变，第二行、第三行、第四行的偏移量分别是1位元组、2位元组、3位元组。除此之外，ShiftRows操作步骤在Rijndael和AES中完全相同。
2.1.4 MixColumns步骤
在MixColumns步骤，每一列的四个位元组透过线性变换互相结合。每一列的四个元素分别当作${ 1,x,x^{2},x^{3}}!$的係数，合併即为${GF(2^{8})}!$GF(2^{8})中的一个多项式，接著将此多项式和一个固定的多项式${c(x)=3x^{3}+x^{2}+x+2}$在模${x^{4}+1}!$下相乘。此步骤亦可视为Rijndael有限域之下的矩阵乘法。MixColumns函数接受4个位元组的输入，输出4个位元组，每一个输入的位元组都会对输出的四个位元组造成影响。因此ShiftRows和MixColumns两步骤为这个密码系统提供了扩散性。
3. 对称加密模式的AES实现
AES在对称加密里面是主算法，但是模式是通用的。本节主要介绍AES如何套到对称加密的模式里。为了研究AES的算法过程，我们自己参考和编写整理了AES逻辑，我们把AES的主算法抽象出接口来，
void aes(state_t* state, const uint8_t* round_key)在https://github.com/carloscn/cryptography/blob/master/lib/carlos/aes.c 中定义。接口void aes_inv(state_t* state, const uint8_t* round_key)是解密过程。针对于加密模式的实现，我们放在https://github.com/carloscn/cryptography/blob/master/lib/carlos/aes_cipher.c 中，里面调用aes的接口实现对称加密。
3.1 ECB
ECB结构简单，直接调用aes加密即可完成：
3.2 CBC
为了克服ECB的弱点，最简单的应对方法是对明文组做一些预处理，CBC模式在加密运算前将当前明文组与上一组的密文输出做异或运算，如此一来加密算法每次的输入就与明文分组没有固定关系。与ECB模式一样，CBC也要求待处理数据长度为16的倍数。
3.3 CFB
首先看加密过程，加密函数的输入是128位的移位寄存器，第一组输入为初始向量IV。加密函数输出最左边的s位与明文第一个s位分段内容异或得到第一个密文单元；移位寄存器左移s位，随后将密文单元填入移位寄存器最右边s位产生下一组加密函数的输入数据，直至所有明文单元被加密完。
3.4 CTR
4. 算法库
mbedtls提供了aes库函数，aes底层实现可以参考： https://github.com/Mbed-TLS/mbedtls/blob/development/library/aes.c
至于使用可以参考： https://mbed-tls.readthedocs.io/en/latest/kb/how-to/encrypt-with-aes-cbc/
我们也提供了一些AES和openssl evp接口的使用方法： https://github.com/carloscn/cryptography/blob/master/modules/sym/src/mbedtls_sca.c
https://github.com/carloscn/cryptography/blob/master/modules/sym/src/openssl_sca.c
5. 总结
结合上一篇3.0_Security_对称密钥算法加解密，这两篇文章算是把AES基本的理论知识点梳理了一遍。在实际工程应用中还存在着很多新内容和优化项，例如MixColumns可以构建GF(256)上的乘法表来加快加解密速度，如果不打算使用ECB与CBC模式，还能够将这张乘法表缩减一半的内容；还有存储设备上的数据加密会倾向使用XTS模式（如android fbe选择了AES-256-XTS），不需要额外存储iv，加解密都可以并行计算，一个分组损坏不影响后续内容；Android的fde如何处理DEK, KEK，如何应用安全性更强的Scrypt算法以抵抗彩虹表等等。Linux, Andriod系统安全中内核提供的安全加固方案也非常成熟，而掌握对称密码的基本原理，浏览过相关知识发展的过程，再回过头去研究这些内容的设计与实现也会更加得心应手。
6. Ref
[^1]:zhihu - 乘法逆元