Một số kết quả mở rộng về phân loại S-hộp 4 bit

và A2 
thuộc  sao cho 2 1 1 2S A S A   với ( là kí hiệu của phép toán nhân trong nhóm 
các hộp thế), ta dễ dàng kiểm tra quan hệ này này là một quan hệ tương đương. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 127
Điều này cho phép phân loại các S-hộp n-bit theo quan hệ tương đương affine, nhất 
là khi biết các đại lượng Lin và Diff bảo toàn qua phép biến đổi này (xem [9]). 
3. CÁC LỚP TƯƠNG ĐƯƠNG AFFINE CỦA CÁC S-HỘP 4 BIT 
Bài báo [2] cũng đã chứng minh rằng hai đại lượng Diff và Lin của S-hộp 4-bit 
bất kì sẽ bảo toàn qua quan hệ tương đương affine. Từ đó, các tác giả đã xem xét 
một kết quả lý thuyết (bổ đề 1, [2]) để giảm không gian tìm kiếm từ 16! 244 về 
chỉ còn 11! = 39.916.800 225 hoán vị (đã xác định tại 5 điểm) để đưa ra các phần 
tử đại diện cho mỗi lớp tương đương của các S-hộp tối ưu. Với cách tiếp cận này, 
ta có thể mở rộng cho việc xác định các đại diện cho tất cả các lớp tương đương 
của các S-hộp bất kì bằng kết quả mở rộng sau: 
Bổ đề 1. Mọi lớp tương đương affine trên 2
n luôn tồn tại một hộp thế S thỏa mãn 
( )S i i với 10,1,..., 2ni . 
Chứng minh. Tương tự như trong mệnh đề 2 của bài báo [9]. 
Dựa vào bổ đề trên, ta có thể thực hiện phân lớp tất cả các hộp thế n bit bất kỳ 
trên tập các hộp thế thỏa mãn ( )S i i với 10,1,..., 2ni . Chúng tôi đã thực hành 
theo cách cài đặt của [9] và đã xác định được các đại diện của 302 lớp tương 
đương affine của các S-hộp 4-bit. Tiếp theo, ta sẽ xem xét khả năng tính chính xác 
số lượng các hộp thế có trong mỗi lớp và đưa ra thuật toán sinh tất cả các phép thế 
4 bit tương đương affine với một phần tử cho trước. Một cách tự nhiên, ta có thể 
làm được điều này bằng phương pháp vét cạn bằng cách tác động lần lượt vào bên 
trái và bên phái S-hộp các biến đổi affine tuy nhiên để giảm độ phức tạp ta có thể 
xem xét một thuật toán cải tiến như sau: 
Thuật toán 1: 
Đầu vào: s,  với s là phép thế bất kỳ,  là tập các phép biến đổi affine. 
Đầu ra: Tập S= s , #S. 
Các bước của thuật toán: 
1. S ← Ø; m ← 0. 
2. for i = 1 to # do 
 2.1 r ← s [i]; 
 2.2 if r not in S then 
 2.2.1 for j = 1 to # do S ← S{ [j]r}; 
 2.2.2 m ← m + # ; 
3. Return: S, m. 
Ở đây, ta thấy, thuật toán 1 với bước 2 có cải tiến so với vét cạn là giảm số lần 
kiểm tra điều kiện cho mỗi hộp thế tương đương affine với s sinh ra có thuộc vào S 
trước đó. Trong thuật toán 1, với r được sinh từ bước 2.1, khi đó, với tác động trái 
vào r tại bước này ta sẽ có m phần tử (đã khác nhau), tuy nhiên, vấn đề là m phần 
tử này thuộc tập S hay không lại cần xem xét do ta mới chỉ có kiểm tra điều kiện r 
không thuộc S. Song ta vẫn chứng minh m phần tử này không thuộc S như sau: Xét 
vòng lặp for (2) tại bước thứ i ta sẽ có tập S = { .s. [j]| j=1,..,i-1}, khi đó, nếu r 
không thuộc S thì ta sẽ chứng minh các tập  r cũng không thuộc S. Để chứng 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Nguyễn Bùi Cương, “Một số kết quả mở rộng về phân loại S-hộp 4 bit.” 128 
minh điều này ta dùng phản chứng giả sử tồn tại a  sao cho ar thuộc vào S, 
khi đó, tồn tại một cặp   ',a A j với j<i sao cho  'a r a s A j   khi đó 
   1 ' " ,r a a s A j a s A j j i      , dẫn đến r thuộc vào S, trái giả thiết. Từ đó, 
ta có tính đúng đắn của thuật toán 1. Tiếp theo, độ phức tạp tính toán của thuật 
toán 1 sẽ chỉ phụ thuộc vào phép kiểm tra xem r có thuộc vào S. Chúng tôi thực 
hiện việc này bằng cách sử dụng sắp xếp QuickSort và tìm kiếm nhị phân. Phương 
pháp này có độ phức tạp khi sắp xếp tìm kiếm trên tập n phần tử là cỡ nlog2n. Khi 
đó, độ phức tạp thuật toán trong trường hợp xấu nhất sẽ cỡ 
#
1
# log #
A
i
i i
    . Trong trường hợp S-hộp 4-bit, tập biến đổi affine có 
lực lượng là 322560 phần tử. Do đó, độ phức tạp của thuật toán này trong trường 
hợp xấu nhất sẽ là 
322560 59
1
322560 log 322560 2
i
i i
   . Độ phức tạp này vẫn 
còn rất lớn. Để giảm độ phức tạp tính toán này, chúng ta xem xét một kết quả lý 
thuyết sau: 
Mệnh đề 1. Cho A và B là hai nhóm con của nhóm G và g∈G. Khi đó, tập 
 :C c B g c A g   (1) 
là nhóm con của B và ta có đẳng thức sau: 
# #
#
#
A B
A g B
C
  . 
Để chứng minh mệnh đề này, ta sẽ chứng minh hai bổ đề sau: 
Bổ đề 2. Tập C cho bởi (1) là nhóm con của nhóm B. 
Chứng minh. Quả vậy, trước hết, nếu e là đơn vị của G thì e cũng là đơn vị của B 
và hiển nhiên ge =g∈Ag nên theo (1) thì e∈C tức là C≠Ø. 
Tiếp đến ∀c,d ∈ C, theo (1) thì gc ∈ Ag tức là tồn tại a’∈A sao cho: 
gc = a’g (2) 
Tương tự, tồn tại a”∈A sao cho: 
gd = a” g (3) 
từ (2) và (3), ta có: 
'
' ' ''
' "
g c d g c d a g d
a g d a a g
a a g A g
     
    
   
Lại theo (1) thì cd ∈ C tức là tập C là đóng với phép nhân. Cuối cùng, để chứng 
minh C là nhóm con của B, cần chứng tỏ với mọi c ∈ C thì c-1 ∈ C. Quả vậy, từ c 
∈C nên tồn tại a ∈ A sao cho a g g c  
lấy nghịch đảo hai vế của đẳng thức trên ta được 
1 1 1 1g a c g   (4) 
nhân bên trái và bên phải cả hai vế của đẳng thức trên với g, ta có 
 1 1 1 1g g a g g c g g       
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 129
Từ tính kết hợp của phép nhân trong nhóm nên đẳng thức (4) tương đương với 
1 1a g g c   (5) 
Vì A là nhóm nên a-1∈A cho nên đẳng thức (5) cho thấy c-1∈C vậy bổ đề đã 
được chứng minh.■ 
Bổ đề 3. Cho A và B là hai nhóm con của nhóm G và nhóm C được xác định theo 
(1). Khi đó, ∀g ∈ G và ∀b, b’ ∈ B, ta có 'A g b A g b    khi và chỉ khi 
'b b C  . 
Chứng minh: Thật vậy, 
1
1
1
(1)
1
' '
'
'
'
'
A g b A g b A g A g b b
A g b b
g b b A g
b b C
b b C
       
   
   
  
 
Bổ đề đã được chứng minh.■ 
Chứng minh (mệnh đề1). Biết rằng 
b B
A g B A g b
    
theo bổ đề 3 thì số các tập kề bên phải của nhóm A là A(gb) khác nhau có trong 
biểu thức hợp trên đúng bằng số tập kề bên trái khác nhau của nhóm con C trong B 
mà với định lý Lagrange thì số này chính bằng # / #B C . Mặt khác, số phần tử của 
mọi tập kề của nhóm A đều bằng #A nên ta thu được đẳng thức: 
# #
#
#
A B
A g B
C
  
Do đó, ta nhận được điều phải chứng minh. ■ 
Từ mệnh đề 1, ta có hệ quả sau: 
Hệ quả 1. Cho A và B là hai nhóm con của nhóm G, C là nhóm con được xác định 
trong (1) và g∈G, C là tập đại diện của các lớp kề trái của C trong B. Ta có: 
  | |s s A g C s s A g B     . 
Dựa trên các kết quả nhận được, ta có thuật toán xác định số lượng các phần tử 
của một lớp tương đương affine với một phần tử cho trước như sau: 
Thuật toán 2 
Đầu vào: s,  với s là phép thế bất kỳ,  là tập các biến đổi affine. 
Đầu ra: #(  s ), C là tập được định nghĩa (1). 
Các bước của thuật toán: 
1. S ← Ø; m ← 0. 
2. for i = 1 to # do S ← S{ [i] s}; 
3. for i = 1 to # do 
 3.1 r ← s [i]; 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Nguyễn Bùi Cương, “Một số kết quả mở rộng về phân loại S-hộp 4 bit.” 130 
 3.2 if r in S then 
 3.2.1 m ← m+1; 
 3.2.2 C ←  [i]; 
4. Return: # ×# /m, C; 
Như vậy, đầu ra của thuật toán 2 là số lượng các phần tử cần tính và tập C thỏa 
mãn điều kiện (1). Tương tự với thuật toán 1, độ phức tạp của thuật toán 2 phụ 
thuộc vào việc kiểm tra phần tử r có thuộc vào tập S không song điểm khác biệt ở 
đây là tập S sẽ không thay đổi trong vòng lặp tại bước 3. Do đó, độ phức tạp thuật 
toán 2 trong trường hợp tổng quát tại bước này cỡ # # log #    
2
# log #   . Trong trường hợp S-hộp 4 bit, độ phức tạp tính toán cụ thể là 
240. Còn đối với tập C , chúng ta có thể xác định tập này với độ phức tạp không 
quá 
# 1
2
1
# log #
i
i i
 

  ; trong trường hợp các S-hộp 4-bit thì độ phức tạp 
cỡ 240. Tính xong tập C , chúng ta xác định toàn bộ các phần tử của lớp tương 
đương affine với S-hộp s theo thuật toán sau: 
Thuật toán 3 
Đầu vào: s,  , C với s là phép thế bất kỳ,  là tập các thép thế affine. 
 C là tập được xác định theo hệ quả 1. 
Đầu ra: S =  s , 
Các bước của thuật toán: 
1. S ← Ø; m ← 0. 
2. for i = 1 to # do 
 for j = 1 to #C do S ← S{ [i] sC [j]}; 
3. Return: S; 
Thuật toán 3 có độ phức tạp tính toán không đáng kể và độ phức tạp lưu trữ phụ 
thuộc vào số lượng các phần tử trong C. Tuy nhiên, có một điều khá có ý nghĩa 
trong thực hành là khi #C=1, thì rõ ràng C   , do đó, ta không cần phải đi xác 
định tập C do đó sẽ giảm được độ phức tạp của bước này. 
Về độ phức tạp dữ liệu, thuật toán 1 và thuật toán 3 đều cần lưu trữ cùng một 
tập tương đương affine với hộp thế s. Với phương pháp lưu các hộp thế 4-bit sử 
dụng biễu diễn thông quá 2 từ 4 Byte (xem mô tả trong [9]), ta cần 8 Byte để lưu 
trữ cho một S-hộp do đó với một lớp có lực lượng nhiều nhất là # #   (theo 
mệnh đề 1) sẽ cần # # 8   Byte bộ nhớ, cỡ tối đa 775 GB cho mỗi lớp trong 
trường hợp S-hộp 4 bit. 
4. MỘT SỐ KẾT QUẢ THỰC HÀNH 
Chúng tôi đã thực hành thực thi thuật toán 2 và 3 trên máy tính có năng lực tính 
toán là CPU i3-4145 tốc độ 3.50GHz, RAM 8G thì thời gian tính toán cho thuật 
toán 2 và 3 là chấp nhận được (không quá một ngày tính toán đối với cả hai thuật 
toán trong trường hợp lớn nhất), tuy nhiên, việc lưu trữ cho tất cả các lớp là vấn đề 
cần quan tâm. Sau đây, chúng tôi đưa ra bảng tổng kết đại diện, bậc tuyến tính Lin, 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 131
giá trị sai khác Diff, lực lượng của tập C và yêu cầu về lưu trữ cho từng lớp tương 
đương (do khuân khổ bài báo chúng tôi chỉ đưa ra số liệu cho một số lớp trong tất 
cả 302 lớp) trong bảng sau đây: 
Bảng 1. Lực lượng của tập C và yêu cầu lưu trữ của 302 lớp tương đương affine 
của các S-hộp 4-bit. 
STT Đại diện Lin Diff #C 
Yêu cầu 
lưu trữ 
(GB) 
STT Đại diện Lin Diff #C 
Yêu cầu 
lưu trữ 
(GB) 
1 0123456789ABCDEF 16 16 322560 0.002 152 012345798ACFBDE6 12 6 1 775.20 
2 0123456789ABCDFE 16 16 2688 0.28 153 012345798ACFD6BE 12 6 1 775.20 
3 0123456789ABCEFD 16 12 288 2.69 154 012345798ACFDBE6 12 6 2 387.60 
4 0123456789ABDCFE 16 16 3072 0.25 155 012345798ACFDE6B 12 8 2 387.60 
5 0123456789ABDEFC 16 16 384 2.02 156 012345798ACFDEB6 12 6 1 775.20 
6 0123456789ACBDFE 16 12 64 12.11 157 012345798ACFE6BD 12 6 1 775.20 
.  
134 012345798ACDF6BE 12 8 1 775.20 285 0123469A85CE7DFB 8 4 1 775.20 
135 012345798ACDF6EB 12 8 1 775.20 286 0123469A85CE7FDB 8 4 1 775.20 
136 012345798ACE6BFD 12 6 1 775.20 287 0123469A85CEBDF7 8 4 1 775.20 
137 012345798ACE6DFB 12 6 1 775.20 288 0123469A85CFDBE7 8 4 1 775.20 
138 012345798ACE6FBD 12 6 1 775.20 289 0123469A8BCE5DF7 8 4 4 193.80 
139 012345798ACEB6DF 12 8 2 387.60 290 0123469A8BCE7FD5 8 4 4 193.80 
140 012345798ACEBD6F 12 6 1 775.20 291 0123469A8BCED57F 8 4 4 193.80 
141 012345798ACEBFD6 12 6 1 775.20 292 0123469A8BCED75F 12 4 2 387.60 
142 012345798ACEDBF6 12 6 1 775.20 293 0123469A8BCEF75D 8 4 4 193.80 
143 012345798ACEF6BD 12 8 2 387.60 294 0123469A8C5D7EFB 8 4 4 193.80 
144 012345798ACEFD6B 12 8 2 387.60 295 0123469A8C5DBEF7 8 4 5 155.04 
145 012345798ACF6BDE 12 8 2 387.60 296 0123469A8C5DF7BE 12 4 7 110.74 
146 012345798ACF6BED 12 6 1 775.20 297 0123469A8CBD5FE7 8 4 4 193.80 
147 012345798ACF6DBE 12 6 1 775.20 298 0123469A8CBD7EF5 8 4 60 12.92 
148 012345798ACF6EBD 12 6 1 775.20 299 0123469A8CBDE57F 8 4 12 64.60 
149 012345798ACFB6DE 12 6 1 775.20 300 0123469C85BFED7A 8 4 5 155.04 
150 012345798ACFB6ED 12 6 1 775.20 301 0123469C85DAE7BF 8 4 1 775.20 
151 012345798ACFBD6E 12 6 1 775.20 302 0123469C85FDB7AE 8 4 5 155.04 
Các lớp có nền xám chính là 16 lớp tối ưu kháng lại thám mã lượng sai và tuyến 
tính. Do đó, để lưu trữ hết các hộp thế tối ưu ta cần 6079.75GB và cho tất cả 302 
lớp thì chúng ta cần 155886.93 GB dữ liệu. 
5. KẾT LUẬN 
Bài báo đã đưa ra một cách tiếp cận hiệu quả cho việc phân loại các S-hộp 4-bit 
bất kì theo quan hệ tương đương affine. Từ đó, ta xác định được tất cả các lớp 
tương đương affine và các hộp thế có trong nó đối với S-hộp 4-bit. Kết quả này 
cho phép ta xem xét đầy đủ hơn các tính chất mật mã khác lên các S-hộp 4-bit sau 
khi đã xét đến hai thám mã quan trọng là lượng sai và tuyến tính. Hơn nữa, có thể 
cải tiến thuật toán 2 trên cơ sở tìm ra được một thuộc tính T (hay còn gọi là tính 
chất mật mã) nào đó của S-hộp bất biến trong  s (tập kề bên phải của nhóm  ) 
nhưng không bất biến trong s (tập kề bên trái của nhóm  ) vì khi đó ta có thể 
giảm được kích cỡ của tập cần duyệt. 
Công nghệ thông tin & Cơ sở toán học cho tin học 
Nguyễn Bùi Cương, “Một số kết quả mở rộng về phân loại S-hộp 4 bit.” 132 
TÀI LIỆU THAM KHẢO 
[1]. Markku-Juhani O Saarinen. "Cryptographic analysis of all 4× 4-bit s-boxes". 
in Selected Areas in Cryptography. 2012. Springer. 
[2]. Gregor Leander and Axel Poschmann, "On the classication of 4 bit s-boxes", 
in Arithmetic of Finite Fields. 2007, Springer. p. 159-176. 
[3]. Cuong Nguyen, Lai Tran, and Khoa Nguyen. "On the resistance of serpent-type 
4 bit s-boxes against differential power attacks". in Communications and 
Electronics (ICCE), 2014 IEEE Fifth International Conference on. 2014. IEEE. 
[4]. Stjepan Picek, Barıs Ege, Kostas Papagiannopoulos, Lejla Batina, and Domagoj 
Jakobovic, "Optimality and Beyond: The Case of 4×4 S-boxes". IEEE 
International Symposium on Hardware-Oriented Security and Trust, 2014. 
[5]. Emmanuel Prouff. "DPA attacks and S-boxes". in Fast Software Encryption. 
2005. Springer. 
[6]. Joanne Fuller and William Millan. "Linear redundancy in S-boxes". in Fast 
Software Encryption. 2003. Springer. 
[7]. Begül Bilgin, Svetla Nikova, Ventzislav Nikov, Vincent Rijmen, and Georg 
Stütz, "Threshold implementations of all 3×3 and 4×4 S-boxes", in 
Cryptographic Hardware and Embedded Systems–CHES 2012. 2012, 
Springer. p. 76-91. 
[8]. De Cannière, "Analysis and Design of Symmetric Encrytption Algorithms", 
Ph.D. thesis, 2007. 
[9]. Nguyễn Văn Long, Nguyễn Bùi Cương, and Trần Duy Lai, "Về định nghĩa S-
hộp tối ưu chống thám mã tuyến tính và lượng sai". Tạp chí Nghiên cứu Khoa 
học và Công nghệ quân sự, 2012. Số đặc san tháng 5: p. 62-70. 
ABSTRACT 
SOME EXTENDED RESULTS ON THE CLASSIFICATION 
OF 4-BIT S-BOXES 
In this paper, we solve the problem of determing all affine equivalent 
classes of 4-bit S-boxes. Firstly, based on the approach in [1], we find 302 
affine equivalent class of 4-bit S-bit. Then, some theoretical results are given 
to solve that problem. Finally, we practice the algorithm proposed in the 
paper and discuss the possibility of calculating with storage requirements for 
all 4-bit S-boxes based on the affine equivalent classes. 
Keywords: 4-bit S-boxes, Affine equivalence, Linear cryptanalysis, Differential cryptanalysis. 
Nhận bài ngày 29 tháng 9 năm 2016 
Hoàn thiện ngày 12 tháng 10 năm 2016 
Chấp nhận đăng ngày 14 tháng 12 năm 2016 
Địa chỉ: Viện Khoa học – Công nghệ mật mã, Ban Cơ yếu Chính phủ; 
 * Email: nguyenbuicuong@gmail.com.