III. Thuật toán AES - thực hiện (tiếp)

4. AddRoundKey

Trong suốt quá trình mã hóa và giải mã, AddRoundKey được thực hiện $11$ lần (đối với AES-128), và được thực hiện ngay trước khi đi vào các round mã hóa/giải mã, đồng thời được thực hiện cuối cùng trong mỗi round:

AddRoundKey sử dụng thuật toán XOR đối với state table hiện tại và nhóm secret key tương ứng với thứ tự lần thực hiện của AddRoundKey. Kết quả thu được một state table mới đưa vào sử dụng trong giai đoạn tiếp theo.

Tuy chỉ được thực hiện mã hóa đơn giản bằng cách sử dụng thuật toán XOR, nhưng AddRoundKey là công việc duy nhất trong $4$ công việc của quá trình mã hóa AES có sự tham gia của secret key. Bởi vậy, khi kẻ tấn công có được văn bản mã hóa nhưng không có thông tin về secret key sẽ vô cùng khó khăn để giải mã.

Chương trình Python minh họa thực hiện AddRoundKey (Challenge Round Keys):

state = [
    [206, 243, 61, 34],
    [171, 11, 93, 31],
    [16, 200, 91, 108],
    [150, 3, 194, 51],
]

round_key = [
    [173, 129, 68, 82],
    [223, 100, 38, 109],
    [32, 189, 53, 8],
    [253, 48, 187, 78],
]

def add_round_key(state, round_key):
    state_arr, round_key_arr, new_state_arr = [], [], []
    for i in state:
        for j in i:
            state_arr.append(j)
    for i in round_key:
        for j in i:
            round_key_arr.append(j)
    for i in range(16):
        new_state_arr.append(state_arr[i] ^ round_key_arr[i])
    return new_state_arr

new_state_arr = add_round_key(state, round_key)
print(new_state_arr)    # [99, 114, 121, 112, 116, 111, 123, 114, 48, 117, 110, 100, 107, 51, 121, 125]

Trước hết, chương trình lưu các phần tử trong hai ma trận state và round_key vào hai mảng, sau đó thực hiện XOR lần lượt từng phần tử tương ứng trong hai mảng này và lưu vào mảng new_state_arr. State table mới có thể thu được bằng cách chuyển các phần tử trong mảng new_state_arr vào ma trận $4\times 4$.

5. SubBytes

SubBytes là công việc được thực hiện ở đầu mỗi round, tổng thực hiện $10$ lần (xét AES-128). Đối với các round giải mã, chúng ta có InvSubBytes thực hiện ngược lại với SubBytes là công việc thứ hai trong mỗi round.

SubBytes sẽ thay thế mỗi phần tử trong state table hiện tại thành một phần tử tương ứng (ánh xạ 1-1) trong một mảng các phần tử cố định (Gọi là S-box). S-Box là một bảng $16\times 16$ các phần tử (thường được biểu diễn dưới dạng Hex):

Quy tắc thay thế như sau: Đối với phần tử $0x\alpha\beta$ trong state table, chúng ta sẽ thay thế nó bằng phần tử hàng $\alpha$, cột $\beta$ trong bảng S-box. Ví dụ, với phần tử 0x4c, chúng ta tìm kiếm ở hàng $4$, cột $c$ trong S-box thu được 0x29 sẽ là giá trị thay thế.

Tương tự, đối với InvSubBytes chính là tra cứu bảng Inv-S-box để thay thế ngược lại:

Đối với thực hiện bước SubBytes trong lập trình, xin dành cho bạn đọc thử sức với challenge Confusion through Substitution.

6. ShiftRows

ShiftRows được thực hiện sau công việc SubBytes trong mỗi round, tổng $10$ lần (đối với AES-128). Đối với các round giải mã, chúng ta có InvShiftRows thực hiện ngược lại.

ShiftRows làm việc với mỗi hàng trong state table, trong đó thực hiện dịch chuyển vòng quanh các phần tử sang trái $i$ đơn vị đối với hàng $i$ (tính từ hàng $0$).

Chú ý thứ tự đã quy ước khi biểu diễn state table trong mảng hai chiều Python, chúng ta có hàm shift_rows() thực hiện như sau:

def shift_rows(s):
    s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
    s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
    s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]

Trong quá trình giải mã, InvShiftRows sẽ dịch chuyển vòng quanh các phần tử trong mỗi hàng của state table theo hướng ngược lại (dịch phải), số đơn vị dịch chuyển không đổi so với mã hóa. Dựa vào hàm shift_rows() trên, các bạn có thể viết lại hàm inv_shift_rows() nhé!

7. MixColumns

MixColumns có một điểm khác biệt với $3$ công việc còn lại là nó được thực hiện ít hơn một lần so với các giai đoạn khác, tổng $9$ lần (xét AES-128). Trong round cuối cùng của cả quá trình mã hóa và giải mã sẽ không thực hiện MixColumns và InvMixColumns.

MixColumns được thực hiện thông qua một phép tính ma trận đặc biệt với ma trận:

$$\begin{bmatrix} 0x02 & 0x03 & 0x01 & 0x01 \\ 0x01 & 0x02 & 0x03 & 0x01 \\ 0x01 & 0x01 & 0x02 & 0x03 \\ 0x03 & 0x01 & 0x01 & 0x02 \\ \end{bmatrix}$$

Tức là thu được ma trận mới thông qua phép tính:

$$\begin{bmatrix}\\ S'_{0,0} & S'_{0,1} & S'_{0,2} & S'_{0,3}\\ S'_{1,0} & S'_{1,1} & S'_{1,2} & S'_{1,3}\\ S'_{2,0} & S'_{2,1} & S'_{2,2} & S'_{2,3}\\ S'_{3,0} & S'_{3,1} & S'_{3,2} & S'_{3,3}\\ \end{bmatrix} \ =\ \begin{bmatrix}\\ 0x02 & 0x03 & 0x01 & 0x01\\ 0x01 & 0x02 & 0x03 & 0x01\\ 0x01 & 0x01 & 0x02 & 0x03\\ 0x03 & 0x01 & 0x01 & 0x02\\ \end{bmatrix} \begin{bmatrix}\\ S_{0,0} & S_{0,1} & S_{0,2} & S_{0,3}\\ S_{1,0} & S_{1,1} & S_{1,2} & S_{1,3}\\ S_{2,0} & S_{2,1} & S_{2,2} & S_{2,3}\\ S_{3,0} & S_{3,1} & S_{3,2} & S_{3,3}\\ \end{bmatrix}$$

Cách tính phần tử ở cột $j$ trong mỗi hàng như sau:

$$S'_{0,j}=(0x02\ *\ S_{0,j})\ +\ (0x03\ *\ S_{1,j})\ +\ (0x01\ *\ S_{2,j})\ +\ (0x01\ *\ S_{3,j})\\ S'_{1,j}=(0x01\ *\ S_{0,j})\ +\ (0x02\ *\ S_{1,j})\ +\ (0x03\ *\ S_{2,j})\ +\ (0x01\ *\ S_{3,j})\\ S'_{2,j}=(0x01\ *\ S_{0,j})\ +\ (0x01\ *\ S_{1,j})\ +\ (0x02\ *\ S_{2,j})\ +\ (0x03\ *\ S_{3,j})\\ S'_{3,j}=(0x03\ *\ S_{0,j})\ +\ (0x01\ *\ S_{1,j})\ +\ (0x01\ *\ S_{2,j})\ +\ (0x02\ *\ S_{3,j})\\$$

Như đã đề cập, phép tính ma trận trên đặc biệt bởi vì phép nhân và phép cộng ở đây là các phép toán được quy ước trong GF(2^8). Chúng ta sẽ cố gắng theo hướng tiếp cận đơn giản nhất đối với hai phép toán này.

Phép cộng ở đây chính là phép toán XOR bit, tức là $a + b = a \oplus b$.

Phép nhân sẽ mang tính phức tạp hơn, chúng ta đang xét với các số hạng có độ dài $8$ bit, chỉ cần tính được ba dạng phép tính $A\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0)$ với $A\in\{0x01;\ 0x02;\ 0x03\}$. Với $A = 0000\ 0001$, ta có:

$$(0000\ 0001)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0) = a_7a_6a_5a_4\ a_3a_2a_1a_0$$

Với $A = 0000\ 0010$, cách tính dựa trên giá trị của $a_7$:

$$(0000\ 0001)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0)= \begin{cases} a_6a_5a_4a_3\ a_2a_1a_00& \text{nếu }a_7=0\\ (a_6a_5a_4a_3\ a_2a_1a_00)\ \oplus (0001\ 1011)& \text{nếu }a_7=1 \end{cases}$$

Với $A = 0000\ 0011$, dựa trên phép toán XOR và tính chất kết hợp chúng ta có:

$\ \ \ \ (0000\ 0011)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0)$ $=[(0000\ 0010) \oplus (0000\ 0001)]\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0)$ $=[(0000\ 0010)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0) ]\oplus [(0000\ 0001)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0) ]$ $=[(0000\ 0010)\ * \ (a_7a_6a_5a_4\ a_3a_2a_1a_0) ]\oplus (a_7a_6a_5a_4\ a_3a_2a_1a_0)$

Biểu thức cuối có thể tính bình thường dựa trên các quy tắc trước.

Bài tập dành cho bạn đọc, từ các công thức trên, hãy hoàn thiện quá trình MixColumns cho state table sau:

Tài liệu tham khảo

• https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
• https://www.geeksforgeeks.org/advanced-encryption-standard-aes/
• https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf
• https://en.wikipedia.org/wiki/AES_key_schedule