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

7. MixColumns (tiếp)

Giải đáp bài tập phần trước: Công thức tính phần tử ở cột $j$ trong mỗi hàng lúc này có thể rút gọn lại thành:

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

Ví dụ, với state table:

Dựa theo công thức trên chúng ta có:

$S'_{0,0}=(0x02\ *\ S_{0,0})\oplus (0x03\ *\ S_{1,0})\oplus S_{2,0}\oplus S_{3,0}$ $\ \ \ \ \ \ =(0x02\ *\ 0xC9)\oplus (0x03\ *\ 0x7A)\oplus (0x63)\oplus (0xB0)$ $\ \ \ \ \ \ =[(0000\ 0010)\ *\ (1100\ 1001)]\oplus [(0000\ 0011)\ *\ (0111\ 1010)]\oplus (0110\ 0011)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =[(1001\ 0010)\oplus (0001\ 1011)]\oplus \{[(0000\ 0010)\ *\ (0111\ 1010)]\oplus (0111\ 1010)\}\oplus (0110\ 0011)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =[(1001\ 0010)\oplus (0001\ 1011)]\oplus [(111\ 10100)\oplus (0111\ 1010)]\oplus (0110\ 0011)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =(1000\ 1001)\oplus (1000\ 1110)\oplus (0110\ 0011)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =(0000\ 0111)\oplus (0110\ 0011)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =(0110\ 0100)\oplus (1011\ 0000)$ $\ \ \ \ \ \ =1101\ 0100$ $\ \ \ \ \ \ =0xD4$

Tương tự chúng ta tính được state table mới:

Tiếp theo chúng ta cùng phân tích cách thực hiện quá trình MixColumns trong lập trình. Đối với phép toán $\oplus$ có thể dễ dàng thực hiện bằng toán tử ^ trong Python. Có thể thấy việc biểu diễn phép toán sau qua ngôn ngữ lập trình đóng vai trò then chốt:

$$(0000\ 0010)\ * \ (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}$$

Đặt $a_7a_6a_5a_4\ a_3a_2a_1a_0 = x$ đại diện cho tham số truyền vào. Để ý một chút, chúng ta có hai trường hợp:

• $a_7=0$: Loại bỏ bit $a_7$ và bổ sung vào bên phải bit $0$ đối với $x$.
• $a_7=1$. Loại bỏ bit $a_7$ và bổ sung vào bên phải bit $0$ đối với $x$ rồi mang kết quả thực hiện phép toán $\oplus$ với $0001\ 1011$ (hay 0x1B).

(Bạn đọc cần lưu ý giá trị $a_6a_5a_4a_3\ a_2a_1a_00$ KHÔNG PHẢI là kết quả của phép dịch trái một bit, do dịch trái một bit chúng ta thu được kết quả $a_7\ a_6a_5a_4a_3\ a_2a_1a_00$ )

Định nghĩa hàm xtime() như sau:

def xtime1(x):
    if (x & 0x80):
        return (((x << 1) ^ 0x1B) & 0xFF)
    else:
        return (x << 1)

Kiểm tra điều kiện trường hợp $1$ bằng cách thực hiện phép & với số 0x80 (1000 0000), phép toán & với số 0xFF (1111 1111) nhằm đảm bảo kết quả trong phạm vi $8$ bit (Do x << 1 đã tăng số lượng bit lên một). Đối với trường hợp còn lại $a_7=0$ chúng ta chỉ cần thực hiện phép dịch bit sang trái một đơn vị bởi bit đầu tiên $a_7=0$ sẽ không ảnh hưởng đến kết quả.

Ngoài ra, do đây là một hàm đơn giản nên các bạn cũng có thể sử dụng hàm nặc danh lambda định nghĩa:

xtime = lambda x: (((x << 1) ^ 0x1B) & 0xFF) if (x & 0x80) else (x << 1)

Từ đây, phép tính $(0000\ 0011)\ * \ (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)$ có thể biểu diễn thành: xtime(x) ^ x

Xét a là một cột bất kỳ của state table trước khi tiến hành MixColumns, dựa vào công thức:

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

Chúng ta có:

$a'[0] = \text{xtime}(a[0])\ \oplus\ (\text{xtime}(a[1])\ \oplus\ a[1])\ \oplus\ a[2]\ \oplus\ a[3]$ $a'[0] = (\text{xtime}(a[0])\ \oplus\ \text{xtime}(a[1]))\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3]$ $a'[0] = \text{xtime}(a[0]\ \oplus\ a[1])\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3]$ $a'[0] = \text{xtime}(a[0]\ \oplus\ a[1])\ \oplus\ a[0]\ \oplus\ a[0]\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3]$ $a'[0] = \text{xtime}(a[0]\ \oplus\ a[1])\ \oplus\ a[0]\ \oplus\ t$

Với $t=a[0]\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3]$. Từ đó biểu diễn bằng ngôn ngữ Python có: a[0] ^= t ^ xtime(a[0] ^ a[1])

Tương tự biến đổi như trên, xây dựng được hàm mix_single_column() thực hiện MixColumns cho một cột bất kỳ và hàm mix_columns() thực hiện cho toàn bộ state table có dạng:

def mix_single_column(a):
    t = a[0] ^ a[1] ^ a[2] ^ a[3]
    u = a[0]
    a[0] ^= t ^ xtime(a[0] ^ a[1])
    a[1] ^= t ^ xtime(a[1] ^ a[2])
    a[2] ^= t ^ xtime(a[2] ^ a[3])
    a[3] ^= t ^ xtime(a[3] ^ u)
    
def mix_columns(s):
    for i in range(4):
        mix_single_column(s[i])

Cần sử dụng thêm biến u = a[0] để bước tính a[3] không bị ảnh hưởng bởi giá trị của a[0] đã thay đổi.

Tiếp theo chúng ta cần giải quyết vấn đề InvMixColumns. Dựa theo quy tắc "nhân" ma trận với các phép toán được quy ước trong GF(2^8), xét các phép tính đặc biệt sau:

$$S_{0,j}=(0x01\ *\ S_{0,j})\ +\ (0x00\ *\ S_{1,j})\ +\ (0x00\ *\ S_{2,j})\ +\ (0x00\ *\ S_{3,j})\\ S_{1,j}=(0x00\ *\ S_{0,j})\ +\ (0x01\ *\ S_{1,j})\ +\ (0x00\ *\ S_{2,j})\ +\ (0x00\ *\ S_{3,j})\\ S_{2,j}=(0x00\ *\ S_{0,j})\ +\ (0x00\ *\ S_{1,j})\ +\ (0x01\ *\ S_{2,j})\ +\ (0x00\ *\ S_{3,j})\\ S_{3,j}=(0x00\ *\ S_{0,j})\ +\ (0x00\ *\ S_{1,j})\ +\ (0x00\ *\ S_{2,j})\ +\ (0x01\ *\ S_{3,j})\\$$

Biểu diễn dạng ma trận:

$$\begin{bmatrix} 0x01 & 0x00 & 0x00 & 0x00\\ 0x00 & 0x01 & 0x00 & 0x00\\ 0x00 & 0x00 & 0x01 & 0x00\\ 0x00 & 0x00 & 0x00 & 0x01\\ \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} \ =\ \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}$$

Như vậy, nếu ta có thể tìm được một ma trận $X$ thỏa mãn phương trình ma trận X:

$$\begin{bmatrix} X_{0,0} & X_{0,1} & X_{0,2} & X_{0,3}\\ X_{1,0} & X_{1,1} & X_{1,2} & X_{1,3}\\ X_{2,0} & X_{2,1} & X_{2,2} & X_{2,3}\\ X_{3,0} & X_{3,1} & X_{3,2} & X_{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} 0x01 & 0x00 & 0x00 & 0x00\\ 0x00 & 0x01 & 0x00 & 0x00\\ 0x00 & 0x00 & 0x01 & 0x00\\ 0x00 & 0x00 & 0x00 & 0x01\\ \end{bmatrix}$$

Thì ta có thể biến đổi:

$$\begin{bmatrix} X_{0,0} & X_{0,1} & X_{0,2} & X_{0,3}\\ X_{1,0} & X_{1,1} & X_{1,2} & X_{1,3}\\ X_{2,0} & X_{2,1} & X_{2,2} & X_{2,3}\\ X_{3,0} & X_{3,1} & X_{3,2} & X_{3,3}\\ \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}$$

$$\ = \begin{bmatrix} X_{0,0} & X_{0,1} & X_{0,2} & X_{0,3}\\ X_{1,0} & X_{1,1} & X_{1,2} & X_{1,3}\\ X_{2,0} & X_{2,1} & X_{2,2} & X_{2,3}\\ X_{3,0} & X_{3,1} & X_{3,2} & X_{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}$$

$$\ = \begin{bmatrix} 0x01 & 0x00 & 0x00 & 0x00\\ 0x00 & 0x01 & 0x00 & 0x00\\ 0x00 & 0x00 & 0x01 & 0x00\\ 0x00 & 0x00 & 0x00 & 0x01\\ \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} \ = \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}$$

Giải phương trình ma trận X chúng ta thu được kết quả:

$$\begin{bmatrix} 0x0E & 0x0B & 0x0D & 0x09\\ 0x09 & 0x0E & 0x0B & 0x0D\\ 0x0D & 0x09 & 0x0E & 0x0B\\ 0x0B & 0x0D & 0x09 & 0x0E\\ \end{bmatrix}$$

Do thực hiện phép tính với ma trận $X$ khá phức tạp nên chúng ta có thể tận dụng hàm MixColumns bằng cách biến đổi:

$$\begin{bmatrix} 0x0E & 0x0B & 0x0D & 0x09\\ 0x09 & 0x0E & 0x0B & 0x0D\\ 0x0D & 0x09 & 0x0E & 0x0B\\ 0x0B & 0x0D & 0x09 & 0x0E\\ \end{bmatrix} \ = \begin{bmatrix} 0x02 & 0x03 & 0x01 & 0x01\\ 0x01 & 0x02 & 0x03 & 0x01\\ 0x01 & 0x01 & 0x02 & 0x03\\ 0x03 & 0x01 & 0x01 & 0x02\\ \end{bmatrix} \begin{bmatrix} 0x05 & 0x00 & 0x04 & 0x00\\ 0x00 & 0x05 & 0x00 & 0x04\\ 0x04 & 0x00 & 0x05 & 0x00\\ 0x00 & 0x04 & 0x00 & 0x05\\ \end{bmatrix}$$

Như vậy, công việc trở nên đơn giản hơn là lập trình phép tính ma trận dưới, sau đó thực hiện hàm MixColumns trước đó:

$$\begin{bmatrix} 0x05 & 0x00 & 0x04 & 0x00\\ 0x00 & 0x05 & 0x00 & 0x04\\ 0x04 & 0x00 & 0x05 & 0x00\\ 0x00 & 0x04 & 0x00 & 0x05\\ \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}$$

Bạn đọc có thể tham khảo hàm inv_mix_columns() dưới đây và đường dẫn thực hiện https://cs.ru.nl/~joan/papers/JDA_VRI_Rijndael_2002.pdf mục $4.1.3$

def inv_mix_columns(s):
    for i in range(4):
        u = xtime(xtime(s[i][0] ^ s[i][2]))
        v = xtime(xtime(s[i][1] ^ s[i][3]))
        s[i][0] ^= u
        s[i][1] ^= v
        s[i][2] ^= u
        s[i][3] ^= v

    mix_columns(s)

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://cs.ru.nl/~joan/papers/JDA_VRI_Rijndael_2002.pdf