+2

Symmetric ciphers - Mật mã đối xứng AES (phần 4)

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 jj trong mỗi hàng lúc này có thể rút gọn lại thành:

S0,j=(0x02  S0,j)(0x03  S1,j)S2,jS3,jS1,j=S0,j(0x02  S1,j)(0x03  S2,j)S3,jS2,j=S0,jS1,j(0x02  S2,j)(0x03  S3,j)S3,j=(0x03  S0,j)S1,jS2,j(0x02  S3,j)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:

image.png

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

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

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

image.png

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)  (a7a6a5a4 a3a2a1a0)={a6a5a4a3 a2a1a00neˆˊa7=0(a6a5a4a3 a2a1a00) (0001 1011)neˆˊa7=1(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 a7a6a5a4 a3a2a1a0=xa_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:

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

(Bạn đọc cần lưu ý giá trị a6a5a4a3 a2a1a00a_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ả a7 a6a5a4a3 a2a1a00a_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 11 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 88 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 a7=0a_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 a7=0a_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)  (a7a6a5a4 a3a2a1a0)=[(0000 0010)  (a7a6a5a4 a3a2a1a0)](a7a6a5a4 a3a2a1a0)(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:

S0,j=(0x02  S0,j)(0x03  S1,j)S2,jS3,jS1,j=S0,j(0x02  S1,j)(0x03  S2,j)S3,jS2,j=S0,jS1,j(0x02  S2,j)(0x03  S3,j)S3,j=(0x03  S0,j)S1,jS2,j(0x02  S3,j)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]=xtime(a[0])  (xtime(a[1])  a[1])  a[2]  a[3]a'[0] = \text{xtime}(a[0])\ \oplus\ (\text{xtime}(a[1])\ \oplus\ a[1])\ \oplus\ a[2]\ \oplus\ a[3] a[0]=(xtime(a[0])  xtime(a[1]))  a[1]  a[2]  a[3]a'[0] = (\text{xtime}(a[0])\ \oplus\ \text{xtime}(a[1]))\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3] a[0]=xtime(a[0]  a[1])  a[1]  a[2]  a[3]a'[0] = \text{xtime}(a[0]\ \oplus\ a[1])\ \oplus\ a[1]\ \oplus\ a[2]\ \oplus\ a[3] a[0]=xtime(a[0]  a[1])  a[0]  a[0]  a[1]  a[2]  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]=xtime(a[0]  a[1])  a[0]  ta'[0] = \text{xtime}(a[0]\ \oplus\ a[1])\ \oplus\ a[0]\ \oplus\ t

Với t=a[0]  a[1]  a[2]  a[3]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:

S0,j=(0x01  S0,j) + (0x00  S1,j) + (0x00  S2,j) + (0x00  S3,j)S1,j=(0x00  S0,j) + (0x01  S1,j) + (0x00  S2,j) + (0x00  S3,j)S2,j=(0x00  S0,j) + (0x00  S1,j) + (0x01  S2,j) + (0x00  S3,j)S3,j=(0x00  S0,j) + (0x00  S1,j) + (0x00  S2,j) + (0x01  S3,j)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:

[0x010x000x000x000x000x010x000x000x000x000x010x000x000x000x000x01][S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3] = [S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3]\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 XX thỏa mãn phương trình ma trận X:

[X0,0X0,1X0,2X0,3X1,0X1,1X1,2X1,3X2,0X2,1X2,2X2,3X3,0X3,1X3,2X3,3][0x020x030x010x010x010x020x030x010x010x010x020x030x030x010x010x02] = [0x010x000x000x000x000x010x000x000x000x000x010x000x000x000x000x01]\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:

[X0,0X0,1X0,2X0,3X1,0X1,1X1,2X1,3X2,0X2,1X2,2X2,3X3,0X3,1X3,2X3,3][S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3]\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}

 =[X0,0X0,1X0,2X0,3X1,0X1,1X1,2X1,3X2,0X2,1X2,2X2,3X3,0X3,1X3,2X3,3][0x020x030x010x010x010x020x030x010x010x010x020x030x030x010x010x02][S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3]\ = \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}

 =[0x010x000x000x000x000x010x000x000x000x000x010x000x000x000x000x01][S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3] =[S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3]\ = \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ả:

[0x0E0x0B0x0D0x090x090x0E0x0B0x0D0x0D0x090x0E0x0B0x0B0x0D0x090x0E]\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 XX 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:

[0x0E0x0B0x0D0x090x090x0E0x0B0x0D0x0D0x090x0E0x0B0x0B0x0D0x090x0E] =[0x020x030x010x010x010x020x030x010x010x010x020x030x030x010x010x02][0x050x000x040x000x000x050x000x040x040x000x050x000x000x040x000x05]\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 đó:

[0x050x000x040x000x000x050x000x040x040x000x050x000x000x040x000x05][S0,0S0,1S0,2S0,3S1,0S1,1S1,2S1,3S2,0S2,1S2,2S2,3S3,0S3,1S3,2S3,3]\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.34.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


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.