[AES] Bài 2 - Lý thuyết về giải mã AES-128

Bài viết này trình bày ngắn gọn và giúp hiểu nhanh về giải mã (decryption, decipher) AES-128 để có thể thiết kế và mô tả RTL tổng hợp được.

Tham khảo lại bài 1 - Lý thuyết về mã hóa AES-128.

1) Tổng quan về giải mã AES-128

Mã hóa chuyển một "bản rõ" (plaintext) thành một "bản mã" (ciphertext) thông qua một khóa mã (key) giúp che dấu thông tin gốc ban đầu. Giải mã là quá trình nghịch đảo (Inverse cipher) của quá trình mã hóa. Nó giúp khôi phục lại bản rõ từ một bản mã.

Trong quá trình giải mã, ma trận ciphertext sẽ bị biến đổi bởi các chức năng AddRoundKey, InvSubBytes, InvShiftRows hoặc InvMixColumns để tạo ra các dữ liệu trung gian gọi là ma trận trạng thái. Ma trận khóa mã sẽ bị biến đổi bởi chức năng KeyExpansion như trong quá trình mã hóa. Tuy nhiên, thứ tự sử dụng các khóa vòng trong quá trình giải mã ngược với quá trình mã hóa, nghĩa là khóa vòng số 10 sẽ được sử dụng đầu tiên. Tiếp theo đó là khóa vòng số 9, số 8, ..., cuối cùng là khóa mã gốc.

Quá trình giải mã được thực hiện qua 5 chức năng cơ bản là AddRoundKey, InvSubBytes, InvShiftRows, InvMixColumns và InvKeyExpansion. Chú ý, InvKeyExpansion không phải là một chức năng được mô tả trong chuẩn mà là một tên gọi được tác giả thêm vào để chỉ quá trình biến đổi ngược giá trị khóa vòng từ khóa vòng số 10 đến khóa mã gốc.

• Bước 1. Bước khởi tạo: Dữ liệu cần được mã hóa cipher_text[127:0] kết hợp với khóa vòng thứ 10, round_key_10[127:0], bằng chức năng AddRoundKey
• Bước 2. Bước lặp giải mã: kết quả bước 1 được sử dụng để thực hiện tuần tự các chức năng InvShiftRows, InvSubBytes, AddRoundKey và InvMixColumns. Bước này được lặp lại 9 lần. Chú ý, InvKeyExpansion thực hiện song song với bước AddRoundKey để tạo khóa vòng cho chức năng này.
• Bước 3. Bước tạo ngõ ra: Sau 9 lần lặp ở bước 2, kết quả được sử dụng để thực hiện tuần tự các chức năng InvShiftRows, InvSubBytes và AddRoundKey với khóa mã ban đầu để khôi phục lại plain_text[127:0].

Hình 1: Quá trình giải mã (Inverse Cipher)

Quá trình giải mã AES-128 sẽ được giải thích trên một ví dụ cụ thể. Giả sử chuỗi dữ liệu cần mã hóa cipher_text[127:0] và khóa vòng cuối cùng lấy từ quá trình mã hóa round_key_10[127:0] có giá trị như sau:

• cipher_text[127:0] =  69 c4 e0 d8 6a 7b 04 30 d8 cd b7 80 70 b4 c5 5a
• round_key_10[127:0] = 13 11 1d 7f e3 94 4a 17 f3 07 a7 8b 4d 2b 30 c5

Dữ liệu và khóa mã được sắp xếp dưới dạng ma trận với mỗi phần tử là một byte.

Hình 2: Ma trận khóa vòng thứ 10 và ma trận dữ liệu đã mã hóa

Giá trị dùng làm ví dụ lấy từ phần "INVERSE CIPHER (DECRYPT)" của phụ lục "C.1 AES-128 (Nk=4, Nr=10)" của tài liệu mô tả chuẩn mã hóa.

2) Chức năng AddRoundKey đảo

Chức năng AddRoundKey đảo trong quá trình giải mã cũng chính là chức năng AddRoundKey trong quá trình mã hóa nên gọi chung là AddRoundKey.

Hình 3: Chức năng AddRoundKey

3) Chức năng InvShiftRows

InvShiftRows là đảo của chức năng ShiftRows. InvShiftRows thực hiện quay phải từng hàng của ma trận trạng thái, sinh ra từ bước trước đó, theo byte với hệ số quay tăng dần từ 0 đến 3. Hàng đầu tiên có hệ số quay là 0 thì các byte được giữ nguyên vị trí. Hàng thứ hai có hệ số quay là 1 thì các được quay một byte. Hàng thứ ba quay hai byte và hàng thứ tư quay ba byte.

Hình 4: Chức năng InvShiftRows

4) Chức năng InvSubBytes

Chức năng InvSubBytes là thực hiện thay thế từng byte của ma trận trạng thái, bằng một giá trị đã quy định trong chuẩn AES. Bảng quy định giá trị thay thế cho InvSubBytes gọi là S-box đảo (Inverse S-box).

Hình 5: Bảng S-box đảo của chuẩn AES

Ví dụ, byte cần thay thế là Ha7 thì dò ở hàng "a" và cột số 7 trong bảng S-box đảo sẽ được kết quả là H89.

Hình 6: Chức năng InvSubBytes

5) Chức năng InvMixColumns

InvMixColumns của quá trình giả mã là đảo của MixColumns trong quá trình mã hóa. Từng cột của ma trận trạng thái sẽ được nhân với ma trận chuyển đổi sau đây.

Hình 7: Ma trận chuyển đổi dùng trong InvMixColumns

Việc biến đổi một cột của ma trận trạng thái được thực hiện bởi hai phép toán là nhân (.) và XOR (+).

Nguyên tắc tính toán InvMixColumns là biến đổi phép nhân với một số thành phép nhân với H02 và H01. Phép nhân với H01 thì giữ nguyên giá trị. Phép nhân với H02 tương đương với việc dịch trái một bit và XOR có điều kiện như sau: 

• Nếu bit MSB của giá trị được dịch bằng 1 thì giá trị sau khi dịch được XOR với H1b 
• Nếu bit MSB của giá trị được dịch bằng 0 thì giữ giá trị sau khi dịch. 

Nguyên tắc trên đã được trình bày ở bài 1 khi nói về lý thuyết mã hóa. 

Như vậy, việc biến đổi về phép nhân với H01 và H02 sẽ giúp dễ dàng thiết kế mạch logic thực hiện chức năng InvMixColumns với tài nguyên được tối ưu hóa. Thiết kế và RTL code sẽ được phân tích trong những bài sau. Tuy nhiên, các bạn cần hiểu cách tính InvMixColumns sẽ được trình bày sau đây: 

Phép nhân một byte A với H0e=B00001110 sẽ tương đương như sau: 

A.H0e = A.H08 + A.H04 + A.H02 

Trong đó, phép nhân với H04 và H08 hoàn toàn có thể chuyển về phép nhân với H02.

A.H04 = A.H02.H02
A.H08 = A.H02.H02.H02 

Như vậy: 

A.H0e = A.H02.H02.H02 + A.H02.H02 + A.H02 

Phép nhân một byte A với H0b=B00001011 sẽ tương đương như sau: 

A.H0e
= A.H08 + A.H02 + A.H01
= A.H02.H02.H02 + A.H02 + A.H01 

Phép nhân một byte A với H0d=B00001101 sẽ tương đương như sau: 

A.H0e
= A.H08 + A.H04 + A.H01
= A.H02.H02.H02 + A.H02.H02 + A.H01 

Phép nhân một byte A với H09=B00001001 sẽ tương đương như sau:

A.H0e
= A.H08 + A.H01
= A.H02.H02.H02 + A.H01

Biểu thức sau là biến đổi của phần tử H54, H là ký hiệu của số Hex, ở cột 1 trong hình minh họa "chức năng InvMixColumns".

H54 = He9.H0e + Hf7.H0b + H4e.H0d + Hec.H09

Hình 8: Chi tiết cách tính InvMixColumns tạo ra phần tử H54 từ cột 1 của ma trận trạng thái

Việc tính InvMixColumn cho toàn bộ một ma trận trạng thái như sau:

Hình 9: Chức năng InvMixColumns

Với việc quy đổi phép nhân về dạng nhân với H02 và H01. Mạch logic nhân một byte với H0e, H0b, H0d và H09 có thể được thực hiện như hình sau.

Hình 10. Mạch nguyên lý nhân một byte A với các phần tử trong ma trận chuyển đổi InvMixColumns

6) Chức năng InvKeyExpansion
Như đã trình bày, chuẩn AES không nói về InvKeyExpansion vì cả mã hóa và giải mã đều dùng chung một khóa mã. KeyExpansion giúp tính tất cả các khóa vòng từ khóa mã. Ví dụ, trong AES-128, chúng ta sẽ có một khóa mã và 10 khóa vòng. Khi mã hóa, các khóa được sử dụng theo thứ tự như sau:

Khóa mã (key) -> khóa vòng 1 -> khóa vòng 2 -> ... -> khóa vòng 10

Khi giải mã theo phương pháp nghịch đảo (Inverse cipher), các khóa được sử dụng theo thứ tự như sau:

Khóa vòng 10 -> khóa vòng 9 -> ... -> khóa vòng 1 -> khóa mã

Như vậy, trước khi giải mã, tất cả các khóa vòng phải được tính trước và lưu lại trong một bộ nhớ, ví dụ như RAM hay mảng thanh ghi. Tác giả sẽ thực hiện một cách làm khác là chỉ dùng khóa vòng cuối cùng, khóa vòng 10, sau đó áp dụng InvKeyExpansion để tính ngược lại các khóa vòng trước đó và khóa mã. Cách này giúp không tốn tài nguyên bộ nhớ lưu lại tất cả các khóa nhưng tốn logic thực hiện mạch tính InvKeyExpansion.
Nguyên tắc tính InvKeyExpansion của khóa thứ n-1 từ khóa thứ n như sau (n >= 1, n = 0 là khóa mã gốc) như sau:

• Mỗi khóa gồm 4 word với word 3 là MSB và word 0 là LSB
• word[0] của khóa thứ n-1 = word[0] của khóa thứ n XOR word[1] của khóa thứ n
• word[1] của khóa thứ n-1 = word[1] của khóa thứ n XOR word[2] của khóa thứ n
• word[2] của khóa thứ n-1 = word[2] của khóa thứ n XOR word[3] của khóa thứ n
• word[3] của khóa thứ n-1 = word[3] của khóa thứ n XOR với giá trị sau khi biến đổi word[0] của khóa thứ n-1 (đã tính trên đây) qua các bước:
• RotWord
• SubWord
• InvAddRcon

Trong đó, RotWord và SubWord áp dụng tương tự như quá trình mã hóa. InvAddRcon là bước XOR kết quả SubWord với Rcon nhưng thứ tự giá trị Rcon được sử dụng sẽ ngược với quá trình mã hóa.

Rcon     Giá trị HEX Vị trí sử dụngRcon[1] 36000000 sử dụng cho lần tính khóa thứ 9
Rcon[2] 1b000000 sử dụng cho lần tính khóa thứ 8
Rcon[3] 82000000 sử dụng cho lần tính khóa thứ 7
Rcon[4] 40000000 sử dụng cho lần tính khóa thứ 6
Rcon[5] 20000000 sử dụng cho lần tính khóa thứ 5
Rcon[6] 10000000 sử dụng cho lần tính khóa thứ 4
Rcon[7] 08000000 sử dụng cho lần tính khóa thứ 3
Rcon[8] 04000000 sử dụng cho lần tính khóa thứ 2
Rcon[9] 02000000 sử dụng cho lần tính khóa thứ 1
Rcon[10] 01000000 sử dụng cho lần tính khóa mã gốc

Như vậy, trong AES-128, ở lần tính đầu tiên, tính giá trị khóa vòng số 9 từ khóa vòng số 10 thì giá trị Rcon[1] = H36000000 được sử dụng. Khác với quá trình giải mã, Rcon[1] = H01000000 được dùng cho lần tính đầu tiên.

Bài viết này đã trình bày ngắn gọn về quá trình giải mã và phân tích một số điểm giúp việc thiết kế và mô tả RTL code dễ dàng hơn. Chi tiết về một bộ mã hóa, giải mã AES-128 với RTL đầy đủ sẽ được trình bày ở những bài tiếp theo.

Tài liệu tham khảo:
1) Federal Information, Processing Standards Publication 197; ADVANCED ENCRYPTION STANDARD (AES); November 26, 2001

Lịch sử cập nhật:
1) 2019.10.02 - Tạo lần đầu