AES的Rijndael mix columns算法实现源码

#include
#include

void gmix_column(unsigned char *r) {
    unsigned char a[4];
    unsigned char b[4];
    unsigned char c;
    unsigned char h;
    /* The array 'a' is simply a copy of the input array 'r'
         * The array 'b' is each element of the array 'a' multiplied by 2
         * in Rijndael's Galois field
         * a[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */
    for(c=0;c<4;c++) {
        a[c] = r[c];
        h = r[c] & 0x80; /* hi bit */
        b[c] = r[c] << 1;
        if(h == 0x80)
            b[c] ^= 0x1b; /* Rijndael's Galois field */
    }
    r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
    r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
    r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
    r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
}

int main(int argc, char *argv[])
{
    unsigned char r[4];
    r[0] = strtol(argv[1],NULL,0);
    r[1] = strtol(argv[2],NULL,0);
    r[2] = strtol(argv[3],NULL,0);
    r[3] = strtol(argv[4],NULL,0);

    printf("[%02x %02x %02x %02x] ==> ", r[0], r[1], r[2], r[3]);
    gmix_column(r);
    printf("[%02x %02x %02x %02x]\n", r[0], r[1], r[2], r[3]);
}

以上代码可以验证后面红色字体部分数据

luther@gliethttp:/vobs/tmp$ ./a.out 0xdb 0x13 0x53 0x45
[db 13 53 45] ==> [8e 4d a1 bc]

下面一组测试数据来自FIPS-197.pdf第37页
luther@gliethttp:/vobs/tmp$ ./a.out 0xd4 0xbf 0x5d 0x30
[d4 bf 5d 30] ==> [04 66 81 e5]
luther@gliethttp:/vobs/tmp$ ./a.out 0xe0 0xb4 0x52 0xae
[e0 b4 52 ae] ==> [e0 cb 19 9a]
luther@gliethttp:/vobs/tmp$ ./a.out 0xb8 0x41 0x11 0xf1
[b8 41 11 f1] ==> [48 f8 d3 7a]
luther@gliethttp:/vobs/tmp$ ./a.out 0x1e 0x27 0x98 0xe5
[1e 27 98 e5] ==> [28 06 26 4c]

========================================

The MixColumns operation performed by the cipher, along with the shift-rows step, is the primary source of in Rijndael. Each column is treated as a polynomial over GF(2⁸) and is then multiplied modulo x⁴ + 1 with a fixed polynomial c(x) = 3x³ + x² + x + 2; the inverse of this polynomial is c ^{− 1}(x) = 11x³ + 13x² + 9x + 14.

Contents

[]

//

[] MixColumns

The MixColumns step can be performed by multiplying a of four numbers in by the following circulant :

This can also be seen as the following:

r₀ = 2a₀ + 3a₁ + a₂ + a₃r₁ = 2a₁ + 3a₂ + a₃ + a₀r₂ = 2a₂ + 3a₃ + a₀ + a₁r₃ = 2a₃ + 3a₀ + a₁ + a₂

Since this math is done in , the addition above is actually an operation, and multiplication is a .

[] Implementation example

This can be simplified somewhat in actual implementation by replacing the multiply by 2 with a single shift and conditional exclusive or, and replacing a multiply by 3 with a multiply by 2 combined with an exclusive or. A example of such an implementation follows:

void gmix_column(unsigned char *r) {
unsigned char a[4];
unsigned char b[4];
unsigned char c;
unsigned char h;
/* The array 'a' is simply a copy of the input array 'r'
* The array 'b' is each element of the array 'a' multiplied by 2
* in Rijndael's Galois field
* a[n] ^ b[n] is element n multiplied by 3 in Rijndael's Galois field */
for(c=0;c<4;c++) {
a[c] = r[c];
h = r[c] & 0x80; /* hi bit */
b[c] = r[c] << 1;
if(h == 0x80)
b[c] ^= 0x1b; /* Rijndael's Galois field */
}
r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
}

Note that this implementation is vulnerable to a .

[] InverseMixColumns

The MixColumns operation has the following inverse (numbers are decimal):

Or:

r₀ = 14a₀ + 9a₃ + 13a₂ + 11a₁r₁ = 14a₁ + 9a₀ + 13a₃ + 11a₂r₂ = 14a₂ + 9a₁ + 13a₀ + 11a₃r₃ = 14a₃ + 9a₂ + 13a₁ + 11a₀

[] Test vectors

Hexadecimal		Decimal
Before	After	Before	After
db 13 53 45	8e 4d a1 bc	219 19 83 69	142 77 161 188
f2 0a 22 5c	9f dc 58 9d	242 10 34 92	159 220 88 157
01 01 01 01	01 01 01 01	1 1 1 1	1 1 1 1
c6 c6 c6 c6	c6 c6 c6 c6	198 198 198 198	198 198 198 198
d4 d4 d4 d5	d5 d5 d7 d6	212 212 212 213	213 213 215 214
2d 26 31 4c	4d 7e bd f8	45 38 49 76	77 126 189 248

[] References

• ( compressed PDF file).
• (PDF file)

[] See also

Retrieved from ""

: |