首页 > 代码库 > AES算法实现分析

AES算法实现分析

2024-08-19 19:21:28   221人阅读

    • AES算法实现分析
      • 主函数 char encryptchar str char key
      • 加密 void Cipher
      • 字节代替void SubBytes及int getSBoxValueint num
      • 行移位void ShiftRows
      • 列混合 void MixColumns
      • 秘钥轮加 AddRoundKeyround
      • 密钥调度算法 void KeyExpansion
      • 解密过程 char decryptchar str char key void InvCipher

AES算法实现分析

代码请见：https://pan.baidu.com/s/1geXlaHP

AES算法是一个迭代分组算法。

主函数 char *encrypt(char *str, char *key)


char *encrypt(char *str, char *key) 
{
    int i,j,Nl;
    double len;
    char *newstr;
    char *str2;

    Nk = Nc / 32;
    Nr = Nk + 6;

    len= strlen(str);
    Nl = (int)ceil(len / 16);

    newstr = (char *)malloc(Nl*32);
    memset(newstr,0,sizeof(newstr));

    for(i=0;i<Nl;i++)
    {
        for(j=0;j<Nk*4;j++)
        {
            Key[j]=key[j];
            in[j]=str[i*16+j];
        }

        KeyExpansion();
        Cipher();
        strcat(newstr,out);
    }
    return newstr;
}

该函数需要传入两个参数，明文str和秘钥key。

各个不同的变换都在称为状态（代码中的state数组）的中间结果上运算（见void Cipher()），状态定义为一个4行的字节矩阵，其列数记为Nb，Nb = 分组长度 / 32。密钥也采用类似的方式用4行的字节矩阵表示，该矩阵的列数记为Nk，Nk = 密钥长度 / 32。

AES密码的加密轮数是和秘钥长度有关的，准确地说，其轮数由Nb和Nk决定，如下表：

Nk, Nb 4 6 8
4 10 12 14
6 12 12 14
8 14 14 14

传入之后，首先计算明文的长度len，由len/16得到密文应分为多少个 8*16=128位的块。对每个块，进行加密操作Cipher()，加密操作的结果会保存在数组out中，并与最终的密文newstr连接。

下面首先分析加密操作Cipher。

加密 void Cipher()

void Cipher()
{
    int i,j,round=0;

    //Copy the input PlainText to state array.
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            state[j][i] = in[i*4 + j];
        }
    }

    // Add the First round key to the state before starting the rounds.
    AddRoundKey(0); 

    // There will be Nr rounds.
    // The first Nr-1 rounds are identical.
    // These Nr-1 rounds are executed in the loop below.
    for(round=1;round<Nr;round++)
    {
        SubBytes();
        ShiftRows();
        MixColumns();
        AddRoundKey(round);
    }

    // The last round is given below.
    // The MixColumns function is not here in the last round.
    SubBytes();
    ShiftRows();
    AddRoundKey(Nr);

    // The encryption process is over.
    // Copy the state array to output array.
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            out[i*4+j]=state[j][i];
        }
    }
}

首先，将第一轮的秘钥加入（与状态异或）。AddRoundKey(0);

对于前Nr-1论，每一轮进行如下操作：

字节代替 SubBytes();
行移位 ShiftRows();
列混合 MixColumns();
密钥轮加 AddRoundKey(round);

对于最后一轮，只需要进行
字节代替 SubBytes()
行移位 ShiftRows()
密钥轮加 AddRoundKey(round);

然后将存储在state中的密文复制到out中。

下面详细看加密中的每一轮的操作。

字节代替void SubBytes()及int getSBoxValue(int num)

void SubBytes()
{
    int i,j;
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            state[i][j] = getSBoxValue(state[i][j]);

        }
    }
}

int getSBoxValue(int num)
{
    int sbox[256] =   {
    //0     1    2      3     4    5     6     7      8    9     A      B    C     D     E     F
    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 };
    return sbox[num];
}

字节代替的操作本身是一个简单的查表操作，将输入的16位密文作为下标，查找到S盒中对应的数据即可state[i][j] = getSBoxValue(state[i][j]);也即state[i][j]=sbox[i][j];。代码中直接给出了S盒，不过实际上，S盒的构造却比较复杂，用到了字节在在有限域GF(2^8)中的逆以及矩阵变换。

行移位void ShiftRows()

行移位的操作本身是很简单的， 由于移位是以字节为单位，就为编码提供了很大的方便。由于加密程序中写死了密文的位数为128位，代码中甚至没有用循环去实现移位。

其逆向变换只需将移位的行向相反的方向移动对应位数即可。

不过，行移位的意义在于，提供了很好的扩散机制，使得一个位的改变可以影响到较远的地方。

void ShiftRows()
{
    unsigned char temp;

    // Rotate first row 1 columns to left    
    // 将第一行向左循环移动一个字节
    temp=state[1][0];
    state[1][0]=state[1][1];
    state[1][1]=state[1][2];
    state[1][2]=state[1][3];
    state[1][3]=temp;

    // Rotate second row 2 columns to left    
    // 将第二行向左循环移动两个字节
    temp=state[2][0];
    state[2][0]=state[2][2];
    state[2][2]=temp;

    temp=state[2][1];
    state[2][1]=state[2][3];
    state[2][3]=temp;

    // Rotate third row 3 columns to left
   // 将第三行向左循环移动三个字节
    temp=state[3][0];
    state[3][0]=state[3][3];
    state[3][3]=state[3][2];
    state[3][2]=state[3][1];
    state[3][1]=temp;
}

列混合 void MixColumns();

void MixColumns()
{
    int i;
    unsigned char Tmp,Tm,t;
    for(i=0;i<4;i++)
    {    
        t=state[0][i];
        Tmp = state[0][i] ^ state[1][i] ^ state[2][i] ^ state[3][i] ;
        Tm = state[0][i] ^ state[1][i] ; Tm = xtime(Tm); state[0][i] ^= Tm ^ Tmp ;
        Tm = state[1][i] ^ state[2][i] ; Tm = xtime(Tm); state[1][i] ^= Tm ^ Tmp ;
        Tm = state[2][i] ^ state[3][i] ; Tm = xtime(Tm); state[2][i] ^= Tm ^ Tmp ;
        Tm = state[3][i] ^ t ; Tm = xtime(Tm); state[3][i] ^= Tm ^ Tmp ;
    }
}

在列混合变换中，将状态的列视作有限域GF(2^8)上的4维向量并与GF(2^8)上的一个固定的可逆方阵A相乘。代码实现中，将这个运算转换为了位运算。通过行移位和列混合，经过几轮变换后，所有的输入位和输出位有关。

可逆方阵中的系数实际上是基于码字间最大距离的线性辨别，从而保证了列混合的效果。

技术分享

在解密过程中，需要使用该变换的逆变换，如下：

技术分享

秘钥轮加 AddRoundKey(round);

void AddRoundKey(int round) 
{
    int i,j;
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            state[j][i] ^= RoundKey[round * Nb * 4 + i * Nb + j];
        }
    }
}

将状态与密钥异或state[j][i] ^= RoundKey[round * Nb * 4 + i * Nb + j]，使得密钥发挥作用。对于第r轮，选取从第(r - 1)*Nb比特到第Nb-1比特的密钥作为该轮中使用的密钥。

密钥调度算法 void KeyExpansion()

void KeyExpansion()
{
    int i,j;
    unsigned char temp[4],k;

    // The first round key is the key itself.
    for(i=0;i<Nk;i++)
    {
        RoundKey[i*4]=Key[i*4];
        RoundKey[i*4+1]=Key[i*4+1];
        RoundKey[i*4+2]=Key[i*4+2];
        RoundKey[i*4+3]=Key[i*4+3];
    }

    // All other round keys are found from the previous round keys.
    while (i < (Nb * (Nr+1)))
    {
        for(j=0;j<4;j++)
        {
            temp[j]=RoundKey[(i-1) * 4 + j];
        }
        if (i % Nk == 0)
        {
            // This function rotates the 4 bytes in a word to the left once.
            // [a0,a1,a2,a3] becomes [a1,a2,a3,a0]
            {
                k = temp[0];
                temp[0] = temp[1];
                temp[1] = temp[2];
                temp[2] = temp[3];
                temp[3] = k;
            }

            // SubWord() is a function that takes a four-byte input word and 
            // applies the S-box to each of the four bytes to produce an output word.
            {
                temp[0]=getSBoxValue(temp[0]);
                temp[1]=getSBoxValue(temp[1]);
                temp[2]=getSBoxValue(temp[2]);
                temp[3]=getSBoxValue(temp[3]);
            }
            // 与轮常数异或
            temp[0] =  temp[0] ^ Rcon[i/Nk];
        }
        else if (Nk > 6 && i % Nk == 4)
        {
            {
                temp[0]=getSBoxValue(temp[0]);
                temp[1]=getSBoxValue(temp[1]);
                temp[2]=getSBoxValue(temp[2]);
                temp[3]=getSBoxValue(temp[3]);
            }
        }
        RoundKey[i*4+0] = RoundKey[(i-Nk)*4+0] ^ temp[0];
        RoundKey[i*4+1] = RoundKey[(i-Nk)*4+1] ^ temp[1];
        RoundKey[i*4+2] = RoundKey[(i-Nk)*4+2] ^ temp[2];
        RoundKey[i*4+3] = RoundKey[(i-Nk)*4+3] ^ temp[3];
        i++;
    }
}

各轮密钥是通过密钥调度算法从密钥中产生的。共需要产生比特长度为轮数加1乘以分组长度(32 * Nb * (Nr+1))的密钥。

第一轮的密钥就是给出的密钥：

    // The first round key is the key itself.
    for(i=0;i<Nk;i++)
    {
        RoundKey[i*4]=Key[i*4];
        RoundKey[i*4+1]=Key[i*4+1];
        RoundKey[i*4+2]=Key[i*4+2];
        RoundKey[i*4+3]=Key[i*4+3];
    }

之后的各轮密钥由前面的密钥递归定义。

对于Nk小于等于6，第r+1轮的密钥中，前Nk个字由密钥填充

        for(j=0;j<4;j++)
        {
            temp[j]=RoundKey[(i-1) * 4 + j];
        }

随后的每个字wi等于前面的字wi-1和Nk个位置之前的字wi-Nk的异或

        RoundKey[i*4+0] = RoundKey[(i-Nk)*4+0] ^ temp[0];
        RoundKey[i*4+1] = RoundKey[(i-Nk)*4+1] ^ temp[1];
        RoundKey[i*4+2] = RoundKey[(i-Nk)*4+2] ^ temp[2];
        RoundKey[i*4+3] = RoundKey[(i-Nk)*4+3] ^ temp[3];

对于Nk整数倍处的字，在异或之前，要对wi-1进行变换，首先将输入字的四个字节循环移位一个字节，然后将AES的S盒作用到输入字的每个字节让。然后异或一个轮常数Rcon[i/Nk]：

        if (i % Nk == 0)
        {
            // This function rotates the 4 bytes in a word to the left once.
            // [a0,a1,a2,a3] becomes [a1,a2,a3,a0]
            {
                k = temp[0];
                temp[0] = temp[1];
                temp[1] = temp[2];
                temp[2] = temp[3];
                temp[3] = k;
            }

            // SubWord() is a function that takes a four-byte input word and 
            // applies the S-box to each of the four bytes to produce an output word.
            {
                temp[0]=getSBoxValue(temp[0]);
                temp[1]=getSBoxValue(temp[1]);
                temp[2]=getSBoxValue(temp[2]);
                temp[3]=getSBoxValue(temp[3]);
            }
            // 与轮常数异或
            temp[0] =  temp[0] ^ Rcon[i/Nk];
        }

而对于Nk>6，其与Nk<=6时的区别在于，当i满足i-4是Nk的整数倍时，在异或之前，要把AES的S盒作用到wi-1的每个字节。

 else if (Nk > 6 && i % Nk == 4)
        {
            {
                temp[0]=getSBoxValue(temp[0]);
                temp[1]=getSBoxValue(temp[1]);
                temp[2]=getSBoxValue(temp[2]);
                temp[3]=getSBoxValue(temp[3]);
            }
        }

解密过程 char *decrypt(char *str, char *key) ,void InvCipher()

解密过程需要依次调用上述加密过程的逆函数，由于已经详细分析过加密过程，解密此处略过。

char *decrypt(char *str, char *key) 
{
    int i,j,len,Nl;
    char *newstr;

    Nk = Nc / 32;
    Nr = Nk + 6;

    len= strlen(str);
    Nl = (int)ceil(len / 16);

    newstr = (char *)malloc(16*Nl);
    memset(newstr,0,sizeof(newstr));

    for(i=0;i<Nl;i++)
    {
        for(j=0;j<Nk*4;j++)
        {
            Key[j]=key[j];
            in[j]=str[i*16+j];
        }

        KeyExpansion();
        InvCipher();
        strcat(newstr,out);
    }
    return newstr;
}

void InvCipher()
{
    int i,j,round=0;

    //Copy the input CipherText to state array.
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            state[j][i] = in[i*4 + j];
        }
    }

    // Add the First round key to the state before starting the rounds.
    AddRoundKey(Nr); 

    // There will be Nr rounds.
    // The first Nr-1 rounds are identical.
    // These Nr-1 rounds are executed in the loop below.
    for(round=Nr-1;round>0;round--)
    {
        InvShiftRows();
        InvSubBytes();
        AddRoundKey(round);
        InvMixColumns();
    }

    // The last round is given below.
    // The MixColumns function is not here in the last round.
    InvShiftRows();
    InvSubBytes();
    AddRoundKey(0);

    // The decryption process is over.
    // Copy the state array to output array.
    for(i=0;i<4;i++)
    {
        for(j=0;j<4;j++)
        {
            out[i*4+j]=state[j][i];
        }
    }
}

附：另请参见 http://www.cnblogs.com/block2016/p/5596676.html 一篇很好的AES算法分析文章

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

    AES算法实现分析


联系
我们