galois field multiplication for AES mix column block in c language

Question

I am working on AES encryption program using c, while doing the galois field multiplication in mix column block,

ex. [https://crypto.stackexchange.com/questions/2402/how-to-solve-mixcolumns][1]

code

for galois field multiplication
    int galois_multiply( int a,int b){
        int flag,res;
        switch (a){
            case 1:
                return b;
                break;
            case 2: flag= b * 0x80;
                b= b << 1;      //left shift
                if (flag)
                    res= b ^ 0x1b;
                else
                    res= b ^0x00;
                printf("\nnumber  %d returned by galois_multiply function\n",res);
                return res;

            case 3: res= b ^ galois_multiply(2,b);
                printf("\nnumber  %d returned by galois_multiply function\n",res);
                return res;

            default:
                printf("Invalid number  %d passed to galois_multiply function\n",a);
                exit(EXIT_FAILURE);
        }
                         return 0;
    }

suppose for

d4×02 is d4<<1, exclusive-ored with 1b (because the high bit of d4 is set), correct ans is b3; whereas using this code I am getting 1b3
bf×03 is bf<<1 exclusive-ored with 1b (because the high bit of bf is set) and bf (because we're multiplying by 3), should give da; but using the code result is 1da

even though the above problem is solved by masking the msb, when used in mixcolumn in following code, the answer seems to be incorrect,its general matrix operation only where multiplication is replaced by galois multilication and addition by XOR operation

void mixColumn(unsigned char **state){
    int mc[4][4]={{2,3,1,1},{1,2,3,1},{1,1,2,3},{3,1,1,2}};
    int res[4][4]={{0}};
    int i,j,k;

    for(i=0;i<4;i++){
            for(j=0;j<4;j++){
                    res[i][j]=0;
                    for(k=0;k<4;k++)
                        res[i][j]= res[i][j] ^ galois_multiply(mc[i][k],state[k][j]);
                    state[i][j]=res[i][j];
            }
    }

}

can u locate any mistakes which might be causing the error...

Ok, so it sounds like you should be masking away the high bit. — Oliver Charlesworth, Apr 26 '14 at 16:16
any suggestion how should I do that, I tried number & 0x100 , but it didn't help.. — Himanshu Sourav, Apr 26 '14 at 16:22
I'd start by using unsigned types. Signed ints can do ugly things when shifted. Also `b= b << 1;` can be written as `b <<= 1;`, and `res= b ^0x00;` AS `res = b; — wildplasser, Apr 26 '14 at 17:05
The link you posted appears to be using `short` sized variables. Why are you using `int`? — ryyker, Apr 26 '14 at 17:23
If binary is easier for you to think in (as it often is if you haven't spent a lot of time using hex), you could use binary literals. http://stackoverflow.com/questions/2611764/can-i-use-a-binary-literal-in-c-or-c — Tyler, Apr 27 '14 at 04:21

ryyker · Answer 1 · 2014-08-26T15:27:49.253

For an int
If you want to clear the MSB of an int x; use x &=7fffffff; (removes only first bit)
For a short int
If you want to clear the MSB of a short x; use x &=7fff; (removes only first bit)

if short x == 1001011111001010 and
short mask == 0111111111111111; then
x &= mask; ==0001011111001010 (or 0x18ca)

However, given you have: 0x1b3, (or 0x1da), but desire 0xb3 (or 0xda) if appears you want to mask the first two bytes.

In that case, set your mask to 0x00ff

It appears you are working in short int, change your code then from int to short, or (as @wildplasser comments) to unsigned short.

The code example you posted has unreachable code in several places, and does not include a return statement:

int galois_multiply( int a,int b){
    int flag,res;
    switch (a){
        case 1:
            return b;
            break;//unreachable code
        case 2: flag= b * 0x80;
            b= b << 1;      //left shift
            if (flag)
                res= b ^ 0x1b;
            else
                res= b ^0x00;
            printf("\nnumber  %d returned by galois_multiply function\n",res);
            return res;
            break;//unreachable code
        case 3: res= b ^ galois_multiply(2,b);
            printf("\nnumber  %d returned by galois_multiply function\n",res);
            return res;
            break;//unreachable code
        default:
            printf("Invalid number  %d passed to galois_multiply function\n",a);
            exit(EXIT_FAILURE);
    }
    //no return statement (prototype specifies one)
}

The switch() statement does not require break; statements when preceded with some other exit method, such as return x;

thanks ryyker for your efforts and tips on fundamentals.. any suggestion how can I mask the MSB, see Oli's comments... — Himanshu Sourav, Apr 26 '14 at 16:47
Thanks ryyker, its giving correct answer now.. :) but when I try to use it in mixcolumn method it seems to give incorrect values — Himanshu Sourav, Apr 26 '14 at 17:33
@Himu - I suggest posting another specific question on that topic. also, consider using the suggestions ***[HERE](http://www.sscce.org/)*** for the best responses. — ryyker, Apr 26 '14 at 17:50

score 0 · Accepted Answer · answered Apr 27 '14 at 04:17

finally caught the mistake i did in case 2, I have used

flag= b * 0x80;

but What I should have used is

flag= b & 0x80;

thinking in biary made me think both these are same operators, but at byte level the story is quite different, * will multiply the content by 80h whereas & will bitwise AND(multiply) the two operands, which is what I needed.

galois field multiplication for AES mix column block in c language

2 Answers2