DES和AES算法详解

DES

DES简介

数据加密标准（DES，Data Encryption Standard）是一种使用密钥加密的块密码，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。这个算法因为包含一些机密设计元素，相对短的密钥长度以及怀疑内含美国国家安全局（NSA）的后门而在开始时有争议，因此DES因此受到了强烈的学院派式的审查，并以此推动了现代的块密码及其密码分析的发展。

DES是一种分组密码，明文、密文和密钥的分组长度都是64位，并且都是面向二进制的密码算法。DES处理的明文分组长度为64位，密文分组长度也是64位，使用的密钥长度为56位（实现上函数要求一个64位的密钥作为输入，但其中用到的只有56位，另外8位可以用作奇偶校验位或者其他用途）。DES的解密过程和加密相似，解密时使用与加密同样的算法，不过子密钥的使用次序要反过来。DES的整个体制是公开的，系统的安全性完全靠密钥的保密。

DES算法概述

DES算法框图：

子密钥产生过程：

算法主要包括：
初始置换IP、16轮迭代的乘积变换、逆初始置换IP^-1以及16个子密钥产生器。

DES算法详解

密钥的产生

DES的乘积变换部分含有16轮非线性变换，每一轮变换都用一个48比特的子密钥，共需16个不同的48比特的子密钥。
一个64比特的外部密钥经过密钥产生器产生48比特的16个子密钥。
置换1：置换1的作用是将56比特密钥K’各位上的数按规定方式进行换位。置换后的56比特分别存到两个28比特的寄存器中。如图：

C0的各位依次为原密钥中的57,49,41,…,36位，D0的各位依次为原密钥中的63,55,…,4位。
循环左移寄存器：每个循环左移寄存器都有28比特，加密时，循环寄存器对C(i+1)、D(i+1)的内容是将循环寄存器对C(i)、D(i)的内容分别左移1至2位得到的。各级寄存器移位的比特数如表所示:

压缩置换：是从56位内容中选出48位，产生16轮加密的16子密钥。压缩置换表如表：

压缩置换表中的数字表示循环寄存器对（Ci、Di）的比特序号，他的读取顺序是从左到右，从上到下，即的第14,17,11,…位分别置换成Ci的第1,2,3,…位。

明文加密过程

初始置换IP：将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。
逆初始置换IP^-1： 将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。
IP和IP^-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8, x16…., x64变成为IP输出的一个字节。
初始置换表IP如下：

即将输入的第58位换到第一位，第50位换到第2位，…，依此类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左 32位，R0 是右32位，例：设置换前的输入值为D1D2D3……D64，则经过初始置换后的结果为：L0=D58D50…D8；R0= D57D49…D7。

逆初始置换表IP^-1:

具体置换图示如下：

乘积变换f：它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。
每次迭代时只对右边的32 bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。
在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。

选择扩展运算E：将输入的32 bit Ri-1扩展成48 bit的输出，令s表示E原输入数据比特的原下标，则E的输出是将原下标s0或1(mod 4)的各比特重复一次得到的，即对原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重复一次,实现数据扩展。将表中数据按行读出得到48 bit输出。

选择压缩运算S：将前面送来的48 bit数据自左至右分成8组，每组为6 bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出。

将前面送来的48比特数据从左至右分成8组，每组为6比特，然后并行送入8个S盒。8个S盒的工作原理都是一样，为一个非线性替换运算。每个S盒都是一个4行、16列的矩阵，每行都是0到15的数字，但每行的数字排列都不同。每个S盒有6位输入，4位输出，6位输入中的第1位和第6位数字组成的二进制数值决定置换矩阵的行数，其余4位数字所组成的二进制数值决定置换矩阵的列数，行数和列数交点的数字便是S盒的输出。

例：假设S1盒的输入110010, 因第1位和第6位数字组成的二进制数为10=(2)10，他对应S1行号为2的那一行，其余4位数字所组成的二进制数为1001=(9)10，对应S1列号为9的那一列，交点处的数是12，则S1的输出为1100。

置换运算P：对S1至S8盒输出的32 bit数据进行坐标置换，置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。

AES

AES简介

AES加密算法即密码学中的高级加密标准（Advanced Encryption Standard，AES），又称Rijndael加密法，是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。

AES算法本质上是一种对称分组密码体制，采用代替/置换网络，每轮由三层组成：线性混合层确保多轮之上的高度扩散，非线性层由16个S盒并置起到混淆的作用，密钥加密层将子密钥异或到中间状态。AES是一个迭代分组密码，其分组长度和密钥长度都是可变的，只是为了满足AES的要求才限定处理的分组大小为128位，而密钥长度为128位、192位或256位，相应的迭代轮数N，为10轮、12轮、14轮。AES汇聚了安全性能、效率、可实现性、灵活性等优点。最大的优点是可以给出算法的最佳查分特征的概率，并分析算法抵抗查分密码分析及线性密码分析的能力。

AES算法概述

AES算法，基本变换包括SubBytes（字节替代）、ShiftRows（行移位）、MixColumns（列混淆）、AddRoundKey(轮密钥加）KeyExtension（密钥扩展）

AES算法中的加密、解密过程要经过多次数据变换操作，每一次变换操作会产生一个中间结果，称为状态(State)，算法的执行过程如下：

①：给定一个明文M，将State初始化为M，并进行AddRoundKey操作，将轮密钥与State异或。

②：对前Nr-1轮中的每一轮，用S盒进行一次SubBytes代替变换，对State做一次ShiftRows行移位操作，再对State做一次MixColumns列混淆操作，然后进行AddRoundKey操作。

③：按照顺序分别进行SubBytes、ShiftRows、AddRoundKey操作。

④：将最后的State中的内容定义为密文C。

AES的解密算法于加密不同，基本运算中除轮密钥加(AddRoundKey)不变之外，其余操作如SubBytes、ShiftRows、MixColumns都要求进行求逆变换。

AES算法详解

明文及密钥的组织排列方式(以明文分组为128bits为例组成的阵列)：

以明文分组（或密钥）为128bits、192bits 、256bits为例组成的阵列：

一些相关的的术语定义和表示：

状态（State）：密码运算的中间结果称为状态。
State的表示：状态用以字节为基本构成元素的矩阵阵列来表示，该阵列有4行，列数记为Nb。 Nb=分组长度（bits）÷ 32 Nb可以取的值为4，6，8，对应的分组长度为128， 192， 256 bits。
密码密钥（Cipher Key）的表示： Cipher Key类似地用一个4行的矩阵阵列来表示，列数记为Nk。 Nk=密钥长度（bits）÷32 Nk可以取的值为4，6，8，对应的密钥长度为128， 192， 256 bits。

轮数（Round）的不同取值：

ByteSubstitution(字节替代)

非线性的字节替代，单独处理每个字节：

求该字节在有限域GF(2⁸)上的乘法逆，”0”被映射为自身，即对于α∈GF(2⁸)，求β∈GF(2⁸)，

使得 α·β=β·α=1mod(x⁸+x⁴+x²+x+1)。

对上一步求得的乘法逆作仿射变换

y_i=x_i + x_(i+4)mod8 + x_(i+6)mod8 + x_(i+7)mod8 + c_i

(其中c_i是63₁₀即01100011₂的第i位），用矩阵表示为：

下面直接利用置换表完成替换：

void AES::SubBytes(unsigned char state[][4])
{
    int r,c;
    for(r=0; r<4; r++)
    {
        for(c=0; c<4; c++)
        {
            state[r][c] = Sbox[state[r][c]];
        }
    }
}

ShiftRows(行移位变换)

行移位变换完成基于行的循环位移操作，变换方法：

在ByteRotation变换中，状态阵列的后3行循环移位不同的偏移量。移位变换作用于行上，第0行不变，第1行循环移位C1字节，第2行循环移位C2字节，第3行循环移位C3字节。

偏移量C1、C2、C3与分组长度Nb有关，如下表所示：

void AES::ShiftRows(unsigned char state[][4])
{
    unsigned char t[4];
    int r,c;
    for(r=1; r<4; r++)
    {
        for(c=0; c<4; c++)
        {
            t[c] = state[r][(c+r)%4];
        }
        for(c=0; c<4; c++)
        {
            state[r][c] = t[c];
        }
    }
}

MixColumns(列混淆变换)

将状态的列看作是有限域GF(2⁸)上的多项式a(x)，与多项式c(x)=(03·x³ + 01·x² + 01·x + 02) · mod(x⁴ + 1)。

逐列混合，方法：

b(x) = (03·x³ + 01·x² + 01·x + 02) · a(x) mod(x⁴ + 1)

矩阵表示形式：

void AES::MixColumns(unsigned char state[][4])
{
    unsigned char t[4];
    int r,c;
    for(c=0; c< 4; c++)
    {
        for(r=0; r<4; r++)
        {
            t[r] = state[r][c];
        }
        for(r=0; r<4; r++)
        {
            state[r][c] = FFmul(0x02, t[r])
                        ^ FFmul(0x03, t[(r+1)%4])
                        ^ FFmul(0x01, t[(r+2)%4])
                        ^ FFmul(0x01, t[(r+3)%4]);
        }
    }
}
 
unsigned char AES::FFmul(unsigned char a, unsigned char b)
{
    unsigned char bw[4];
    unsigned char res=0;
    int i;
    bw[0] = b;
    for(i=1; i<4; i++)
    {
        bw[i] = bw[i-1]<<1;
        if(bw[i-1]&0x80)
        {
            bw[i]^=0x1b;
        }
    }
    for(i=0; i<4; i++)
    {
        if((a>>i)&0x01)
        {
            res ^= bw[i];
        }
    }
    return res;
}

其中FFmul为有限域GF(2⁸)上的乘法，标准算法应该是循环8次（b与a的每一位相乘，结果相加），但这里只用到最低2位，解密时用到的逆列混淆也只用了低4位，所以在这里高4位的运算是多余的，只计算低4位。

数学基础

AES的基础域是有限域 GF(2⁸)：
一个GF(2)上的8次既约多项式可生成一个 GF(2⁸)
GF(2⁸)的全体元素构成加法交换群，线性空间。
GF(2⁸)的非零元素构成乘法循环群。
GF(2⁸)中的元素有多种表示：
字节： GF（2⁸）={a7,a6,…a1,a0}
多项式形式： GF（2⁸）={a7x7+a6x6+…+a1x+a0}
指数形式：GF(2⁸)={0, 1… 254}
对数形式：GF(2⁸)={0, 1… 254}

GF(2⁸)的特征为 2 。

AES的GF(2⁸)表示：
AES采用的既约模多项式：
m(x)=x⁸+x⁴+x³+x+1
AES采用GF(2⁸)的多项式元素表示。
字节B＝b7b6b5b4b3b2b1b0可表示成GF(2)上的多项式：
b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x1+b0
例：字节57＝01010111的多项式表示：
01010111 x⁶+x⁴+x²+x+1

加法：两元素多项式的系数按位模 2加
例2：57＋83＝D4
(x6+x4+x2+x+1)⊕(x7+x+1)= x7+x6+x4+x2
乘法：两元素多项式相乘，模 m(x)
例3：57×83＝C1
(x6+x4+x2+x+1)×(x7+x+1)=x7+x6+1 mod m(x)
乘法单位元：字节01 多项式 1
乘法逆元：
设a(x)的逆元为b(x)，则 a(x)b(x)=1 mod m(x) 。
根据Euclid算法求出。

AddRoundKey(轮密钥加变换)

简单来说就是逐字节相加，有限域GF(28)上的加法是模2加法，即异或：

void AES::AddRoundKey(unsigned char state[][4], unsigned char k[][4])
{
    int r,c;
    for(c=0; c<4; c++)
    {
        for(r=0; r<4; r++)
        {
            state[r][c] ^= k[r][c];
        }
    }
}

KeyExpansion(密钥扩展)

密钥bit的总数＝分组长度×（轮数Round＋1）例如当分组长度为128bits和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408bits。
将密码密钥扩展成一个扩展密钥。
从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个4字节字，第二个轮密钥由接下来的Nb个4字节字组成，以此类推。

将输入的密钥扩展为11组128位密钥组，其中第0组为输入密钥本身

其后第n组第i列为第n-1组第i列与第n组第i-1列之和（模2加法，1<= i <=3）