【密码算法 之二】对称加密算法 AES（Advanced Encryption Standard）浅析

1. 概述

  AES的全称是 Advanced Encryption Standard，意思就是“高级加密标准”。它的出现主要是用于取代其前任DES算法的，因为我们都知道EDS算法的秘钥长度实际为56bit，因此算法的理论安全强度为2的56次方，但是随着计算能力的大幅提高，虽然出现了3DES的加密方法，但由于它的加密时间是DES算法的3倍多，64bit的分组大小相对较小，所以还是不能满足人们对安全性的要求。
  于是1997年1月2号，美国国家标准技术研究（NIST）所宣布希望征集高级加密标准，用以取代DES。AES也得到了全世界很多密码工作者的响应，先后有很多人提交了自己设计的算法。最终有5个候选算法进入最后一轮：Rijndael，Serpent，Twofish，RC6和MARS。最终经过安全性分析、软硬件性能评估等严格的步骤，Rijndael算法获胜。最终将Rijndael算法确定为AES。
  AES算法是由美国的一个标准化机构—NIST（National Institube of Standards and Technology,国家标准技术研究所）选定的，它是美国的国家标准，即联邦信息处理标准（FIPS）（FIPS-197）。虽然AES是美国的标准，但同DES一样，它也是一个世界性的标准。
  Rijndael的真正作者是比利时密码学家 Joan Daemen 与 Vincent Rijmen。Rijndael 的分组长度和秘钥长度分别以32比特位单位在128bit~256bit的范围内进行选择。不过在AES规格中，分组长度固定为128比特，秘钥长度只有128、192和256比特。
  严格意义上说：AES 是 Rijndael 的一个子集，两者不能完全画等号。

特别注意：AES的分组长度为128bit（即16字节），秘钥长度有128bit、192bit、256bit三种形式，分别记为AES-128、AES-192、AES-256

。

2. 原理分析

  AES算法主要有四种操作处理，分别是**密钥加法层(也叫轮密钥加，英文Add Round Key)、字节代换层(SubByte)、行位移层(Shift Rows)、列混淆层(Mix Column)**。而明文x和密钥k都是由16个字节组成的数据(当然密钥还支持192位和256位的长度，这里暂时不分组这两种情况)，它是按照字节的先后顺序从上到下、从左到右进行排列的。而加密出的密文读取顺序也是按照这个顺序读取的，相当于将数组还原成字符串的模样了。
  AES算法在处理的轮数上只有最后一轮操作与前面的轮处理上有些许不同(最后一轮只是少了列混淆处理)，在轮处理开始前还单独进行了一次轮密钥加的处理。

2.1 加密流程

  加密流程如下图所示：

2.1.1 秘钥加法层

  在密钥加法层中有两个输入的参数，分别是明文（或者上一轮的输出Y[i-1]）和轮密钥k[i]（其中 i 为轮数），而且这两个输入都是128位的。秘钥加法层只需要将两个输入的数据进行按字节

异或

操作就会得到运算的结果。
  下图中，明文（或者上一轮的输出Y[i-1]）记为P，轮密钥k[i]记为K。

相关代码

staticvoidAddRoundKey(u64 *state,const u64 *w){
    state[0]^= w[0];
    state[1]^= w[1];}

2.1.2 字节代换层

  字节代换层的主要功能就是让输入的数据通过

S_box表

完成从一个字节到另一个字节的映射。这个表示通过一定的规则计算出来的，但是我们可以将其认为成一个固定的表即可（因为OpenSSL中也是将其按照”固定表“的形式利用的）。
  S_box表分为S盒和逆S盒两个表，其中S盒是用作加密字节替换的，逆S盒用作解密字节替换的。

S盒

逆S盒

字节转换示意图

相关代码

//S盒constunsignedchar S_Table[256]={0x63,0x7C,0x77,0x7B,0xF2,0x6B,0x6F,0xC5,0x30,0x01,0x67,0x2B,0xFE,0xD7,0xAB,0x76,0xCA,0x82,0xC9,0x7D,0xFA,0x59,0x47,0xF0,0xAD,0xD4,0xA2,0xAF,0x9C,0xA4,0x72,0xC0,0xB7,0xFD,0x93,0x26,0x36,0x3F,0xF7,0xCC,0x34,0xA5,0xE5,0xF1,0x71,0xD8,0x31,0x15,0x04,0xC7,0x23,0xC3,0x18,0x96,0x05,0x9A,0x07,0x12,0x80,0xE2,0xEB,0x27,0xB2,0x75,0x09,0x83,0x2C,0x1A,0x1B,0x6E,0x5A,0xA0,0x52,0x3B,0xD6,0xB3,0x29,0xE3,0x2F,0x84,0x53,0xD1,0x00,0xED,0x20,0xFC,0xB1,0x5B,0x6A,0xCB,0xBE,0x39,0x4A,0x4C,0x58,0xCF,0xD0,0xEF,0xAA,0xFB,0x43,0x4D,0x33,0x85,0x45,0xF9,0x02,0x7F,0x50,0x3C,0x9F,0xA8,0x51,0xA3,0x40,0x8F,0x92,0x9D,0x38,0xF5,0xBC,0xB6,0xDA,0x21,0x10,0xFF,0xF3,0xD2,0xCD,0x0C,0x13,0xEC,0x5F,0x97,0x44,0x17,0xC4,0xA7,0x7E,0x3D,0x64,0x5D,0x19,0x73,0x60,0x81,0x4F,0xDC,0x22,0x2A,0x90,0x88,0x46,0xEE,0xB8,0x14,0xDE,0x5E,0x0B,0xDB,0xE0,0x32,0x3A,0x0A,0x49,0x06,0x24,0x5C,0xC2,0xD3,0xAC,0x62,0x91,0x95,0xE4,0x79,0xE7,0xC8,0x37,0x6D,0x8D,0xD5,0x4E,0xA9,0x6C,0x56,0xF4,0xEA,0x65,0x7A,0xAE,0x08,0xBA,0x78,0x25,0x2E,0x1C,0xA6,0xB4,0xC6,0xE8,0xDD,0x74,0x1F,0x4B,0xBD,0x8B,0x8A,0x70,0x3E,0xB5,0x66,0x48,0x03,0xF6,0x0E,0x61,0x35,0x57,0xB9,0x86,0xC1,0x1D,0x9E,0xE1,0xF8,0x98,0x11,0x69,0xD9,0x8E,0x94,0x9B,0x1E,0x87,0xE9,0xCE,0x55,0x28,0xDF,0x8C,0xA1,0x89,0x0D,0xBF,0xE6,0x42,0x68,0x41,0x99,0x2D,0x0F,0xB0,0x54,0xBB,0x16};//字节代换intSubBytes_S(unsignedchar*PlainArray){int ret =0;for(int i =0; i <256; i++){
        PlainArray[i]= S_Table[PlainArray[i]];}return ret;}

2.1.3 行位移 – ShiftRows

  行位移操作最为简单，它是用来将输入数据作为一个4·4的字节矩阵进行处理的，然后将这个矩阵的字节进行位置上的置换。ShiftRows子层属于AES手动的扩散层，目的是将单个位上的变换扩散到影响整个状态当，从而达到雪崩效应。在加密时行位移处理与解密时的处理相反，我们这里将解密时的处理称作逆行位移。它之所以称作行位移，是因为它只在4·4矩阵的行间进行操作，每行4字节的数据。在加密时，保持矩阵的第一行不变，第二行向左移动8Bit(一个字节)、第三行向左移动2个字节、第四行向左移动3个字节。而在解密时恰恰相反，依然保持第一行不变，将第二行向右移动一个字节、第三行右移2个字节、第四行右移3个字节。
行移位示意图

相关代码

staticvoidShiftRows(u64 *state){unsignedchar s[4];unsignedchar*s0;int r;

    s0 =(unsignedchar*)state;for(r =0; r <4; r++){
        s[0]= s0[0*4+ r];
        s[1]= s0[1*4+ r];
        s[2]= s0[2*4+ r];
        s[3]= s0[3*4+ r];
        s0[0*4+ r]= s[(r+0)%4];
        s0[1*4+ r]= s[(r+1)%4];
        s0[2*4+ r]= s[(r+2)%4];
        s0[3*4+ r]= s[(r+3)%4];}}

2.1.4 列混淆

  这一步操作是将4字节的数据作为一个整体，进行比特运算，得到另外的4字节数据，这一步是相当复杂的异步，涉及到很多的知识点，我们这里仅将OpenSSL中实现的软算法代码贴过来，仅供参考。

typedefunion{unsignedchar b[8];
    u32 w[2];
    u64 d;} uni;staticvoidXtimeLong(u64 *w){
    u64 a, b;

    a =*w;
    b = a &0x8080808080808080uLL;
    a ^= b;
    b -= b >>7;
    b &=0x1B1B1B1B1B1B1B1BuLL;
    b ^= a <<1;*w = b;}staticvoidMixColumns(u64 *state){
    uni s1;
    uni s;int c;for(c =0; c <2; c++){
        s1.d = state[c];
        s.d = s1.d;
        s.d ^=((s.d &0xFFFF0000FFFF0000uLL)>>16)|((s.d &0x0000FFFF0000FFFFuLL)<<16);
        s.d ^=((s.d &0xFF00FF00FF00FF00uLL)>>8)|((s.d &0x00FF00FF00FF00FFuLL)<<8);
        s.d ^= s1.d;XtimeLong(&s1.d);
        s.d ^= s1.d;
        s.b[0]^= s1.b[1];
        s.b[1]^= s1.b[2];
        s.b[2]^= s1.b[3];
        s.b[3]^= s1.b[0];
        s.b[4]^= s1.b[5];
        s.b[5]^= s1.b[6];
        s.b[6]^= s1.b[7];
        s.b[7]^= s1.b[4];
        state[c]= s.d;}}

2.2 解密流程

  解密流程如下图所示：

2.2.1 秘钥加法层

  这个流程与2.1.1章节是一致的，不再累述。

2.2.2 逆字节代换层

  这个流程与2.1.1章节是一致的，不再累述，仅贴上示例代码。

constunsignedchar InvS_Table[256]={0x52,0x09,0x6A,0xD5,0x30,0x36,0xA5,0x38,0xBF,0x40,0xA3,0x9E,0x81,0xF3,0xD7,0xFB,0x7C,0xE3,0x39,0x82,0x9B,0x2F,0xFF,0x87,0x34,0x8E,0x43,0x44,0xC4,0xDE,0xE9,0xCB,0x54,0x7B,0x94,0x32,0xA6,0xC2,0x23,0x3D,0xEE,0x4C,0x95,0x0B,0x42,0xFA,0xC3,0x4E,0x08,0x2E,0xA1,0x66,0x28,0xD9,0x24,0xB2,0x76,0x5B,0xA2,0x49,0x6D,0x8B,0xD1,0x25,0x72,0xF8,0xF6,0x64,0x86,0x68,0x98,0x16,0xD4,0xA4,0x5C,0xCC,0x5D,0x65,0xB6,0x92,0x6C,0x70,0x48,0x50,0xFD,0xED,0xB9,0xDA,0x5E,0x15,0x46,0x57,0xA7,0x8D,0x9D,0x84,0x90,0xD8,0xAB,0x00,0x8C,0xBC,0xD3,0x0A,0xF7,0xE4,0x58,0x05,0xB8,0xB3,0x45,0x06,0xD0,0x2C,0x1E,0x8F,0xCA,0x3F,0x0F,0x02,0xC1,0xAF,0xBD,0x03,0x01,0x13,0x8A,0x6B,0x3A,0x91,0x11,0x41,0x4F,0x67,0xDC,0xEA,0x97,0xF2,0xCF,0xCE,0xF0,0xB4,0xE6,0x73,0x96,0xAC,0x74,0x22,0xE7,0xAD,0x35,0x85,0xE2,0xF9,0x37,0xE8,0x1C,0x75,0xDF,0x6E,0x47,0xF1,0x1A,0x71,0x1D,0x29,0xC5,0x89,0x6F,0xB7,0x62,0x0E,0xAA,0x18,0xBE,0x1B,0xFC,0x56,0x3E,0x4B,0xC6,0xD2,0x79,0x20,0x9A,0xDB,0xC0,0xFE,0x78,0xCD,0x5A,0xF4,0x1F,0xDD,0xA8,0x33,0x88,0x07,0xC7,0x31,0xB1,0x12,0x10,0x59,0x27,0x80,0xEC,0x5F,0x60,0x51,0x7F,0xA9,0x19,0xB5,0x4A,0x0D,0x2D,0xE5,0x7A,0x9F,0x93,0xC9,0x9C,0xEF,0xA0,0xE0,0x3B,0x4D,0xAE,0x2A,0xF5,0xB0,0xC8,0xEB,0xBB,0x3C,0x83,0x53,0x99,0x61,0x17,0x2B,0x04,0x7E,0xBA,0x77,0xD6,0x26,0xE1,0x69,0x14,0x63,0x55,0x21,0x0C,0x7D};//逆字节代换intSubBytes_InvS(unsignedchar*CipherArray){int ret =0;for(int i =0; i <256; i++){
        CipherArray[i]= InvS_Table[CipherArray[i]];}return ret;}

2.2.3 逆行移位层

  这个流程与2.1.3章节是一致的，参考代码如下：

staticvoidInvMixColumns(u64 *state){
    uni s1;
    uni s;int c;for(c =0; c <2; c++){
        s1.d = state[c];
        s.d = s1.d;
        s.d ^=((s.d &0xFFFF0000FFFF0000uLL)>>16)|((s.d &0x0000FFFF0000FFFFuLL)<<16);
        s.d ^=((s.d &0xFF00FF00FF00FF00uLL)>>8)|((s.d &0x00FF00FF00FF00FFuLL)<<8);
        s.d ^= s1.d;XtimeLong(&s1.d);
        s.d ^= s1.d;
        s.b[0]^= s1.b[1];
        s.b[1]^= s1.b[2];
        s.b[2]^= s1.b[3];
        s.b[3]^= s1.b[0];
        s.b[4]^= s1.b[5];
        s.b[5]^= s1.b[6];
        s.b[6]^= s1.b[7];
        s.b[7]^= s1.b[4];XtimeLong(&s1.d);
        s1.d ^=((s1.d &0xFFFF0000FFFF0000uLL)>>16)|((s1.d &0x0000FFFF0000FFFFuLL)<<16);
        s.d ^= s1.d;XtimeLong(&s1.d);
        s1.d ^=((s1.d &0xFF00FF00FF00FF00uLL)>>8)|((s1.d &0x00FF00FF00FF00FFuLL)<<8);
        s.d ^= s1.d;
        state[c]= s.d;}}

2.2.4 逆列混淆层

  这个流程与2.14章节是一致的，参考代码如下：

staticvoidInvMixColumns(u64 *state){
    uni s1;
    uni s;int c;for(c =0; c <2; c++){
        s1.d = state[c];
        s.d = s1.d;
        s.d ^=((s.d &0xFFFF0000FFFF0000uLL)>>16)|((s.d &0x0000FFFF0000FFFFuLL)<<16);
        s.d ^=((s.d &0xFF00FF00FF00FF00uLL)>>8)|((s.d &0x00FF00FF00FF00FFuLL)<<8);
        s.d ^= s1.d;XtimeLong(&s1.d);
        s.d ^= s1.d;
        s.b[0]^= s1.b[1];
        s.b[1]^= s1.b[2];
        s.b[2]^= s1.b[3];
        s.b[3]^= s1.b[0];
        s.b[4]^= s1.b[5];
        s.b[5]^= s1.b[6];
        s.b[6]^= s1.b[7];
        s.b[7]^= s1.b[4];XtimeLong(&s1.d);
        s1.d ^=((s1.d &0xFFFF0000FFFF0000uLL)>>16)|((s1.d &0x0000FFFF0000FFFFuLL)<<16);
        s.d ^= s1.d;XtimeLong(&s1.d);
        s1.d ^=((s1.d &0xFF00FF00FF00FF00uLL)>>8)|((s1.d &0x00FF00FF00FF00FFuLL)<<8);
        s.d ^= s1.d;
        state[c]= s.d;}}

2.3 轮秘钥处理

  轮秘钥的处理过程异常的复杂，其实我们在实际工作中并不怎么关心轮秘钥是怎么生成的，所以这里也不在对轮秘钥的生成过程进行详细的分析了。如果大家有兴趣可以参考如下博文：密码学基础：AES加密算法。

3. 总结

• AES算法的分组长度为128比特（16字节）；
• AES算法的秘钥长度有3种，分别为128比特、192比特、256比特；
• AES算法是是 Rijndael 的一个子集，两者不能完全画等号，只有分组长度为128比特，秘钥长度为128、192、256比特的Rijndael算法才是AES算法；
• OpenSSL中关于AES算法的软实现的文件为：openssl-xxxx\crypto\aes\aes_core.c，OpenSSL源码的下载路径为：https://github.com/openssl/openssl。

各种算法的链接地址如下：
【密码算法 之零】对称算法（DES,、3DES、 AES、DM5、HMAC、CMAC、SHAxx、SM3、SM4），非对称算法（RSA、ECC、ECDSA、ECDH、SM2、SM9…）