Search code examples
c++matrixaes

Array Circular left shift


I am trying to implement AES with an array of boolean values. I am stuck on the ShiftRows() function that left shifts a 4*4 matrix a specified amount.

For example, some random input would create a 128bit array as such:

Enter a message: random bits more!
Before:
01110010        01100001        01101110        01100100
01101111        01101101        00100000        01100010
01101001        01110100        01110011        00100000
01101101        01101111        01110010        01100101

The AES algorithm then states the following left shifts per row:

Row 1: 0 Shift
Row 2: 1 left shift
Row 3: 2 left shifts
Row 4: 3 left shits

Ideally, after the left shift operations, the output should be:

After:
01110010        01100001        01101110        01100100
01101101        00100000        01100010        01101111
01110011        00100000        01101001        01110100
01100101        01101101        01101111        01110010

However, this is what I get:

After:
01110010        01100001        01101110        01100100
01101101        00100000        01100010        01101111
01110011        00100000        01101001        01110100
01101111        01101101        01110010        01100101

This is my current function that works perfectly, however, it breaks down in the final row:

for (int i = 1; i < 4; i++) {May have to research further.
    for (int j = 0; j < 4 - i; j++) {
        temp2D = matrix[i][mod_floor(-i + j, 4)];
        matrix[i][mod_floor(-i + j, 4)] = matrix[i][j];
        matrix[i][j] = temp2D;
    }
}

The mod_floor() function just returns mod with floor division:

int mod_floor(int shift, int size) {//Size is number of bytes in row
    return ((shift % size) + size) % size;
}

I have found a temporary fix by hardcoding the final row:

//Manually does final row shift since algorithm is not working properly for last row in matrix.
    temp2D = matrix[3][1];
    matrix[3][1] = matrix[3][0];
    matrix[3][0] = temp2D;
    temp2D = matrix[3][2];
    matrix[3][2] = matrix[3][0];
    matrix[3][0] = temp2D;
    temp2D = matrix[3][3];
    matrix[3][3] = matrix[3][0];
    matrix[3][0] = temp2D;

However, I am unable to see why it is breaking down at this last row. I know I can create a temporary matrix and copy the updated byte shifts as they occur, although this would ruin the in place algorithm.

Any help would be appreciated, also, let me know if more information can help communicate my problem more clearly.

**EDIT

Using Rotate() worked perfectly. I will study why my algorithm breaks down; which I think corelates with what Goswin is saynig.


Solution

  • You are swapping numbers instead of shifting. This works for shifting by 1 since the first value ripples along getting swapped over and over. And for 2 since numbers just swap places. But shifting by 3 you only swap the first and second number and nothing else.

    for (int j = 0; j < 4 - i; j++) {
    

    with i = 3 that only processes j = 0.

    Simplify the whole thing:

    1. copy whole row
    2. copy the row back shifted.

    Let the compiler optimize that into loading the 4 numbers into registers and writing them back.