[AES] Bài 5 - Tối ưu logic tính S-Box dựa trên biến đổi toán học

Bài viết này trình bày cách thiết kế mạch tính S-Box và S-Box đảo bằng cách tối ưu dựa trên biến đổi toán học. Cách thiết kế này có nhiều ưu điểm hơn so với việc dùng bảng tra (Look-up table) với một MUX chọn 256 giá trị.

Tác giả gửi lời cảm ơn đến bạn Lê Nguyễn Tố Quỳnh đã giúp giải thích phần biến đổi của các công thức toán học trong bài viết này.

Danh sách cái bài viết trước:

Bài 4 - Thiết kế bộ giải mã AES-128

Bài 3 - Thiết kế bộ mã hóa AES-128

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

Bài 1 - Lý thuyết về mã hóa AES-128

1) Tổng quan về tối ưu logic mạch tính S-BOX và S-BOX đảo

Để thực hiện quá trình SubByte() trong các bước mã hóa và SubWord() trong bước tính các khóa vòng (round key), Chúng ta có thể thực hiện bằng một trong các cách sau:

• Phương pháp bảng tra (Look-up table): Cách này đơn giản, dễ thực hiện nhưng tốn nhiều tài nguyên. Bảng tra là một MUX chọn các giá trị cố định từ 256 giá trị đã được tính sẵn.
• Phương pháp biến đổi toán học: Cách này phức tạp hơn, để có thể tối ưu được như mong muốn thì người thiết kế cần có kiến thức nhất định về toán học, nhưng tài nguyên phần cứng sẽ giảm đáng kể so với phương pháp dùng bảng tra.

Phương pháp dùng bảng tra đã được sử dụng trong thiết kế được trình bày ở các bài viết trước (bài 1, bài 2, bài 3 và bài 4).

Bài viết này sẽ trình bày một thiết kế dựa trên phương pháp biến đổi toán học để tính các giá trị S-BOX và S-BOX đảo. Tác giả sẽ mô tả RTL code trên một cách biến đổi có sẵn được trình bày trong các tài liệu tham khảo kèm theo bài viết.

Lưu ý, do kiến thức toán học hạn chế nên tác giả chưa thể đọc hiểu toàn bộ nguồn gốc sinh ra các công thức nên nhiều công thức toán học sẽ được lấy từ các bài báo khoa học đã có để sử dụng mà không giải thích thêm. Việc đọc hiểu và cập nhật giải thích sẽ được thực hiện vào thời điểm thích hợp. Hy vọng, bạn đọc nào đã từng nghiên cứu và hiểu rõ vấn đề này có thể chia sẻ thêm.

2) Cách tính S-BOX và S-BOX đảo

Giá trị của S-BOX và S-BOX đảo được sinh ra từ chức năng SubBytes() và InvSubByte(). Hai chức năng này sẽ làm nhiệm vụ chuyển đổi phi tuyến (non-linear) mỗi byte dữ liệu đầu vào thành một byte khác. Quá trình chuyển đổi này gồm 2 bước.

SubBytes() thực hiện tính toán theo thứ tự sau:

• Tính nghịch đảo nhân trong trường hữu hạn GF(2^8). Giá trị 0 có nghịch đảo là 0. Các giá trị khác phải biến đổi để tìm nghịch đảo.
• Thực hiện biến đổi Affine trên GF(2)

Trong hai bước tính, bước biến đổi Affine đã được quy định rõ trong chuẩn AES và thể hiện bằng phép nhân và cộng ma trận như sau:

Hình 1: Biến đổi Affine

Trong đó, mỗi bit sẽ được tính theo công thức:

Với 0 <= I < 8,

• yi là bit thứ i của byte cần chuyển đổi
• xi là bit thứ i của byte kết quả sau khi chuyển đổi
• ci là bit thứ i của byte có giá trị là H63 = B01100011.

 Biểu thức tính toán Affine cho từng bit (chú ý, "+" là XOR):

Hình 2: Biểu thức tính giá trị từng bit trong biến đổi Affine

InvSubBytes() thực hiện tính toán theo thứ tự sau:

• Thực hiện biến đổi Affine nghịch đảo trên GF(2)
• Tính nghịch đảo nhân trong trường hữu hạn GF(2^8). Giá trị 0 có nghịch đảo là 0. Các giá trị khác phải biến đổi để tìm nghịch đảo.

Trong hai bước tính, bước biến đổi Affine nghịch đảo thể hiện bằng phép nhân và cộng ma trận như sau:

Hình 3: Biến đổi Affine nghịch (đảo)

Trong đó mỗi bit sẽ được tính theo công thức:

Với 0 <= i < 8:

• xi là bit thứ i của byte cần chuyển đổi
• yi là bit thứ i của byte kết quả sau khi chuyển đổi
• di là bit thứ i của byte có giá trị là H05 = B00000101.

Logic tính toán Affine nghịch đảo cho từng bit (chú ý, "+" là XOR):

Hình 4: Biểu thức tính giá trị từng bit trong biến đổi Affine nghịch (đảo)

Hình 5: Sơ đồ khối bộ tính giá trị S-BOX và S-BOX đảo, khối "nghịch đảo nhân"" là bộ tính giá trị nghịch đảo trên các trường có bậc thấp hơn trường GF(2^8)

Vấn đề “phức tạp” còn lại trong việc tính toán và tối ưu nằm ở bước “Tính nghịch đảo nhân trong trường hữu hạn GF(2^8)”. Có nhiều cách khác nhau để thực hiện logic tính toán nghịch đảo nhưng một cách được áp dụng rộng rãi là biến đổi giá trị đầu vào từ trường GF(2^8) xuống các trường có bậc thấp hơn như GF(2^4), GF(2^2) và GF(2), gọi là trường hỗn hợp, để đơn giản hóa mạch logic các phép toán nhân và lũy thừa.

3) Nguyên lý bộ tính nghịch đảo trên trường hỗn hợp

Mạch nguyên lý chung của bộ tính nghịch đảo trên trường như sau:

Hình 6: Sơ đồ nguyên lý logic bộ tính nghịch đảo nhân được lấy từ bài báo [3]

Chi tiết các khối chức năng trong sơ đồ trên như sau:

• Imp, gọi là Isomorphic Mapping, là khối ánh xạ phần tử của trường GF(2^8)  vào trong trường hỗn hợp.
• S là khối tính bình phương trong trường 𝐺𝐹(2^4).
• C là khối tính nhân với hằng số lambda ( λ ) trong trường 𝐺𝐹(2^4). Lambda = B1100
• Inv là khối tính phần tử nghịch đảo trong trường 𝐺𝐹(2^4).
• X là khối nhân 2 số hạng trong trường 𝐺𝐹(2^4).
• ImpInv, gọi là Inverse Isomorphic Mapping, là khối ánh xạ đảo của Imp, chuyển giá trị tình toán về trường GF(2^8)

Tác giả đổi các ký hiệu trong hình vẽ so với tài liệu gốc vì việc viết các ký tự đặc biệt và công thức toán học trên trình soạn thảo blog gặp nhiều khó khăn.
4) Ánh xạ Isomorphic (Imp) và Isomorphic đảo (ImpInv)

Phép tính phần tử nghịch đảo trong trường hỗn hợp không thể được áp dụng trực tiếp vào phần tử trên trường 𝐺𝐹(2^8). Nó phải được ánh xạ vào trường hỗn hợp thông qua biến đổi Isomorphic, Imp. Sau khi thực hiện xong phép tính phần tử nghịch đảo, kết quả sẽ được ánh xạ ngược trở lại từ trường hỗn hợp sang trường 𝐺𝐹(2^8) tương ứng thông qua biến đối ImpInv.

Gọi q là phần tử cần chuyển đổi, trong đó q7 là MSB còn q0  là LSB.  

Khối Imp thực hiện phép nhân ma trận sau đây:

Hình 7: Phép nhân ma trận trong của biến đổi Imp

Logic của chức năng Imp trong RTL code:

Hình 8: Logic khối chức năng Imp

Khối ImpInv thực hiện phép nhân ma trận sau đây:

Hình 9: Phép nhân ma trận của biến đổi ImpInv

Logic của chức năng ImpInv trong RTL code:

Hình 10: Logic của chức năng ImpInv

5) Tính bình phương (khối S)

Các đa thức bất kỳ có thể biểu diễn dưới dạng 𝑏𝑥 + 𝑐 trong đó b là các phần trọng số caocòn c là phần trọng số thấp. Từ đó, một số nhị phân 𝑞 có thể được biểu diễn là qH.x + pL.

Ví dụ, q=B1001 thì có thể biểu diễn là B10.𝑥 + B01, trong đó, qH=B10 và qL=B01. qH và qL có thể tiếp tục được biểu diễn như sau:

qH = B1.x + B0

qL = B0.x + B1

Đây là ý tưởng được dùng để thực hiện các phép toán như cộng, nhân hay bình phương. Bên cạnh đó, quá trình hạ bậc đa thức để tính toán và biến đổi trong trường hỗn hợp sẽ sử dụng các đa thức tối giản sau đây:

Hình 11: Đa thức tối giản được sử dụng để biến đổi 

Trong đó: ϕ = B10 và λ = B1100

Việc tính bình phương trong trường GF(2^4) được thực hiện trên số k (4 bit) sẽ được biến đổi như các bước sau đây. Lưu ý, do việc trình bày các công thức mất nhiều thời gian nên tác giải chỉ giải thích chi tiết cách tính cho trường hợp tính bình phương. Các biến đổi khác như nhân hai toán hạng, nhân với hằng số sẽ áp dụng phương pháp tương tự.

Đầu tiên, giá trị k sẽ được biểu diễn dưới dạng:

Trong đó:

qH = q3q2 (2 bit cao)qL = q1q0 (2 bit thấp)

Bình phương của k được tính như sau: 

Modulo (chia lấy dư) cho đa thức tối giản x^2 + x + ϕ (như đã đề cập bên trên).

Phép chia lấy dưu trên có thể được thực hiện đơn giản bằng cách thay x^2 = x + ϕ vào biểu thức số chia như sau (cách thay thế này sẽ được dùng ở các tính toán về sau):

Thay tính kH dựa trên qH = q3q2:

Modulo kết quả trên cho đa thức tối giản x^2 + x + 1 bằng cách thay x^2 = x + 1 vào biểu thức trên.

Bên cạnh đó kH = k3k2 nên:

Tiếp theo, phần tửu kL được tính tương tự bằng cách thay qH=q3q2, qL=q1q0 và ϕ=B10 vào biểu thức:

Modulo kết quả trên cho  x^2 + x + 1 hoặc thực hiện thay thế x^2 = x + 1 . Trong đó, chuyển x^3 = x^2.x rồi thực hiện thay thế. Kết quả thu được như sau:

Trong đó, kL=k1k0. Như vậy, phép tính bình phương một giá trị 4 bit q=q3q2q1q0 trong trường GF(2^4) sẽ cho kết quả là một giá trị 4 bit k=k3k2k1k0 bằng logic sau đây:

Logic trong RTL code như sau:

Hình 12: Logic của phép bình phương trong trường GF(2^4)

6) Tính nhân với hằng số Lambda (khối C)

Đặt 𝑘 = 𝑞λ, trong đó 𝑘=k3k2k1k0 và 𝑞=q3q2q1q0 và λ=B1100 là các phần tử 4 bit thuộc trường GF(2^4). Áp dụng phương pháp tính đưa về biểu thức dạng bx + c.

Trong đó, λ𝐿=B00 nên được giản lược. Modulo giá trị trên với đa thức tối giản x^2 + x + ϕ bằng cách thay x^2 = x + ϕ vào biểu thức.

kH tiếp tục được tính trên trường GF(2) như sau:

Modulo kết quả trên cho đa thức tối giản  x^2 + x + 1 bằng cách thay x^2 = x + 1 vào biểu thức.

Tương tự, kL được biến đổi trên trường GF(2):

Modulo cho đa thức tối giản  x^2 + x + 1 bằng cách thay x^2 = x + 1 vào biểu thức. Chú ý, x^3=x^2.x

Phép nhân một giá trị 4 bit q=q3q2q1q0 trong trường GF(2^4) với hằng số lambda sẽ cho kết quả là một giá trị 4 bit k=k3k2k1k0 bằng logic sau đây:

Logic trong RTL code:

Hình 13: Logic cúa phép nhân với hằng số lambda trong trường GF(2^4)

7) Tính nhân hai phần tử (khối X)

Đặt 𝑘=𝑞𝑤, trong đó 𝑘=𝑘3𝑘2𝑘1𝑘0, 𝑞=𝑞3𝑞2𝑞1𝑞0 và 𝑤=𝑤3𝑤2𝑤1𝑤0 là phần tử 4 bit của trường GF(2^4).

Modulo giá trị trên với đa thức tối giản x^2 + x + ϕ bằng cách thay x^2 = x + ϕ vào biểu thức.

Trong đó, hệ số của x có thể được biến đổi như sau:

Mạch nguyên lý của phép tính nhân hai phần tử như sau:

Hình 14: Mạch nguyên lý phép nhân 2 phần tử 4 bit trong trường GF(2^4), tên tín hiệu ứng với RTL code

Trong mạch nguyên lý trên, chúng ta cần xác định logic cho phép nhân 2 phần tử, mỗi phần tử 2 bit. Cách tìm mạch logic nhân 2 phần tử 2 bit tương tự như cách làm với hai phần tử 4 bit.
Đặt 𝑘=𝑞𝑤, trong đó 𝑘=𝑘1𝑘0, 𝑞=𝑞1𝑞0 và 𝑤=𝑤1𝑤0 là phần tử 2 bit của trường GF(2^2).

Modulo kết quả trên cho đa thức tối giản  x^2 + x + 1 bằng cách thay x^2 = x + 1 vào biểu thức.

Phép nhân hai phần tử 2 bit cho kết quả như sau:

Logic trong RTL code:

Hình 15: Logic tính nhân 2 phần tử, mỗi phần tử 2 bit

Với cách biến đổi tương tự, chúng ta có thể tính được phép nhân một phần tử 2 bit với với hằng số ϕ = B10.
Đặt k=qϕ, trong đó 𝑘=𝑘1𝑘0 và 𝑞=𝑞1𝑞0 là phần tử 2 bit của trường GF(2^2).

Modulo kết quả trên cho đa thức tối giản  x^2 + x + 1 bằng cách thay x^2 = x + 1 vào biểu thức.

Phép nhân một phần tử 2 bit với ϕ cho kết quả như sau:

8) Tính nghịch đảo trên trường GF(2^4)
Đối với phép tính này, các bạn tham khảo bài báo khoa học số 2. Giá trị nghịch đảo của một số q=q3q2q1q0 được tính như sau:

Theo công thức trên, tác giả thiết kế mạch tính bằng 1 MUX chọn 16 giá trị như sau:

Hình 16: Logic tính giá trị nghịch đảo trong trường GF(2^4)

9) Một ví dụ về tính giá trị nghịch đảo
Ví dụ này lấy từ tài liệu tham khảo [1].

Hình 17: Ví dụ về tính giá trị nghịch đảo nhân cho trường GF(2^8) [1]

10) Kết quả tổng hợp trên FPGA
10.1) Bộ mã hóa sử dụng S-BOX là bảng tra
Family Cyclone IV GX
Device EP4CGX110DF31C7
Total logic elements          5,064 / 109,424 ( 5 % )
Total combinational functions 5,064 / 109,424 ( 5 % )
Dedicated logic registers  261 / 109,424 ( < 1 % )
Total registers 261
Total pins 388 / 508 ( 76 % )

10.2) Bộ mã hóa sử dụng S-BOX dựa trên biến đổi toán học
Family Cyclone IV GX
Device EP4CGX110DF31C7
Total logic elements          2,534 / 109,424 ( 2 % )
Total combinational functions 2,533 / 109,424 ( 2 % )
Dedicated logic registers  261 / 109,424 ( < 1 % )
Total registers 261
Total pins 388 / 508 ( 76 % )

10.3) Bộ mã hóa sử dụng S-BOX và S-BOX đảo là bảng tra
Family Cyclone IV GX
Device EP4CGX110DF31C7
Timing Models Final
Total logic elements          5,092 / 109,424 ( 5 % )
Total combinational functions 5,091 / 109,424 ( 5 % )
Dedicated logic registers 261 / 109,424 ( < 1 % )
Total registers 261
Total pins 388 / 508 ( 76 % )

10.4) Bộ mã hóa sử dụng S-BOX và S-BOX dựa trên biến đổi toán học
Family Cyclone IV GX
Device EP4CGX110DF31C7
Timing Models Final
Total logic elements          2,245 / 109,424 ( 2 % )
Total combinational functions 2,239 / 109,424 ( 2 % )
Dedicated logic registers 261 / 109,424 ( < 1 % )
Total registers 261
Total pins 388 / 508 ( 76 % )

10.5) Nhận xét
Việc tổng hợp được thực hiện trên phần mềm Quartus II (Altera - Intel) trên cùng 1 linh kiện FGPA là EP4CGX110DF31C7. Chỉ logic phần S-BOX và S-BOX đảo được thay đổi để so sánh. Logic này chỉ là mạch tổ hợp nên tài nguyên phần mạch này sẽ thay đổi, còn số lượng Flip-Flop (thanh ghi) và các chân tín hiệu không đổi.

Hình 18: So sánh lượng tài nguyên giữa hai thiết kế

Có thể thấy dùng cách thiết kế S-BOX và S-BOX đảo dựa trên biến đổi toán học như đã trình bày trong bài viết sẽ giúp giảm khoảng 50% tài nguyên thiết kế so với cách sử dụng bảng tra (look-up table).

Dữ liệu có thể tải:
Source code trên Github

Tài liệu tham khảo:
1) Lê Nguyễn Tố Quỳnh, bài luận "thiết kế lõi chuẩn mã hóa nâng cao AES-128", 07/2019
2) Xinmiao Zhang and Keshab K. Parhi; High-Speed VLSI Architectures for the AES, IEEE Transactions on Very Large Scale  Integration (VLSI) Systems, Vol.12, No. 9, September 2004
3) Sushma D K, Dr. Manju Devi; Design of S-box and IN V S-box using Composite Field Arithmetic for AES Algorithm; International Journal of Engineering Research & Technology (IJERT), 2018

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