Về các S-hộp 4x4-bit có tính chất mật mã mạnh

 ta có hai tổng sau đây bằng nhau: 
         
1 1
2 1
2 2
, , , , , ,
1 1
T
T
n n
b S x a x bD S y a C y b d a C c
x y
    
 
     hay 
    12, 1, T
Tw w
b bD
S a S a C  . Nếu C, D là các ma trận hoán vị và wt(a) = wt(b) = 1 thì 
cũng có wt(bDT) = 1, wt(a(C-1)T) = 1, hơn nữa khi a, b chạy khắp tập wt(a) = wt(b) 
= 1 thì bDT, a(C-1)T cũng vậy. Đặt bDT = b’ và a(C-1)T = a’ ta có 
Lin1(S2)=  2,max | wt( ) = wt( ) = 1
w
bS a a b =  1, 'max ' | wt( ') = wt( ') = 1
w
bS a a b = Lin1(S1). 
Bằng cách lập trình, chúng tôi đã tính Lin1(S) cho 20 lớp S-hộp kiểu Serpent và 
thấy rằng không tồn tại S-hộp kiểu Serpent sao cho Lin1(S) = 0. 
Bảng 1. Lin1(S) cho tất cả 20 lớp S-hộp kiểu Serpent. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 213
Lớp R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 
Lin1(S) 4 4 8 4 4 4 4 4 4 8 
Lớp R10 R11 R12 R13 R14 R15 R16 R17 R18 R19 
Lin1(S) 8 8 8 4 4 4 4 8 4 4 
Vì thế, Lin1(S) nhỏ nhất có thể đạt được là bằng 4, tức là trong số 20 lớp S-hộp 
kiểu Serpent, chúng ta sẽ quan tâm hơn tới 14 lớp có tính chất này. Ngoài ra, để 
kháng lại tấn công đại số, người ta còn quan tâm đến các đại lượng 
ni(S) = |{  2
n
v  \{0} : deg(S, v) = i}|. 
Theo kết quả 4.1 [4] thì ta luôn có deg(S, v)  3 nếu S là song ánh. Cũng theo 
Mệnh đề 2.1 [4] thì deg(S, v) là một đại lượng bất biến theo tương đương affine, 
và vì thế nó là bất biến trong một lớp các S-hộp kiểu Serpent. Chúng ta mong 
muốn deg(S, v) lớn nên sẽ quan tâm tới n3(S), n3(S) càng lớn càng tốt. Trong [3] 
đã tính đại lượng n3(S) cho 20 lớp S-hộp kiểu Serpent với kết quả là: 
Bảng 2. n3(S) cho tất cả 20 lớp S-hộp kiểu Serpent. 
Lớp R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 
n3(S) 12 12 12 14 14 14 12 12 14 12 
Lớp R10 R11 R12 R13 R14 R15 R16 R17 R18 R19 
n3(S) 12 12 12 14 12 14 12 12 12 12 
Hệ quả 1. Đối với S-hộp kiểu Serpent S bất kỳ, tồn tại phần tử b 42 sao cho Sb là 
một hàm Bool bậc 2. 
3.2.3.Định nghĩa 5.([1]) Chúng ta nói rằng một hoán vị Boolean f:    
4 4
2 2  
là 
một S-hộp mạnh nếu: f là APN yếu, Lin(f) = 8, Diff(f) = 4, Diff1(f) = 0, Lin1(f) = 
4, n3(f)  14. 
Trong định nghĩa trên, tính chất APN yếu có tính bất biến affine. Các đại lượng 
Lin và Diff cũng có tính chất bất biến affine. Tính chất Diff1(f) = 0 là bất biến dưới 
tương đương hoán vị. Đại lượng Lin1(f) là một đại lượng bất biến theo tương 
đương hoán vị, còn n3(f) có tính bất biến affine. 
Bảng 1 cho thấy rằng 14 lớp Serpent có Lin1(f) = 4 là R0, R1, R3, R4, R5, R6, R7, 
R8, R13, R14, R15, R16, R18 và R19. Bảng 2 ta thấy rằng các lớp Serpent có n3(f)  14 
là R3, R4, R5, R8, R13 và R15. Tức là các lớp Serpent mà thỏa mãn n3(f)  14 thì cũng 
thỏa mãn Lin1(f) = 4. Như vậy, trong 6 điều kiện của Định nghĩa 4, chỉ còn phải 
quan tâm đến điều kiện APN yếu. Chúng tôi đã lập trình kiểm tra các tính chất của 
16 lớp tối ưu sau: 
Bảng 3. Một số tính chất cho 16 lớp tối ưu. 
Lớp wAPN deg(f) n1(f) n2(f) n3(f)  nˆ f Lớp wAPN deg(f) n1(f) n2(f) n3(f)  nˆ f 
G0 - 3 0 3 12 1 G8 - 3 0 3 12 1 
G1 - 3 0 3 12 1 G9 + 3 0 1 14 1 
G2 - 3 0 3 12 1 G10 + 3 0 1 14 1 
G3 + 3 0 0 15 0 G11 + 3 0 0 15 0 
Công nghệ thông tin & Khoa học máy tính 
H.V. Quân, N. B. Cương, “Về các S-hộp 4x4 bit có tính chất mật mã mạnh.” 214 
G4 + 3 0 0 15 0 G12 + 3 0 0 15 0 
G5 + 3 0 0 15 0 G13 + 3 0 0 15 0 
G6 + 3 0 0 15 0 G14 + 3 0 1 14 1 
G7 + 3 0 0 15 0 G15 + 3 0 1 14 1 
Chú ý rằng, tất cả các đại lượng trong bảng thống kê trên đều có tính bất biến 
affine (deg(f), ni(f) tính bất biến của tập {degf, v}). Bảng trên cũng minh họa các 
kết quả lý thuyết (Bổ đề 1 và định lí 1 ở trên) cho 16 lớp tương đương affine của 
các S-hộp tối ưu. Từ bảng trên, ta có thể kiểm tra thấy khẳng định sau: 
Khẳng định 1 [1]. Giả sử f:    442 2  
là một hoán vị Boolean sao cho Lin(f) = 8, 
Diff(f) = 4, n3(f)  14. Khi đó f là một APN yếu. 
Rõ ràng, như đã nhắc tới ở trên, các S-hộp kiểu Serpent là các S-hộp tối ưu và 
vì thế mỗi lớp S-hộp tương đương kiểu Serpent Ri cần phải thuộc một lớp tương 
đương theo affine Gj nào đó. Trong [3] đã đưa ra kết quả rằng 20 lớp tương đương 
kiểu Serpent chỉ thuộc vào 7 lớp tương đương affine, cụ thể là: 
Bảng 4. Quan hệ giữa các lớp Serpent và các lớp tối ưu. 
Lớp tối ưu G0 G1 G2 G9 G10 G14 G15 
Lớp 
Serpent 
R9, R11, R16, 
R19 
R0, R1, R2, R6, R17, R18 R7, R10, R12, R14 R4, R13 R3, R5 R15 R8 
Bằng lập trình, chúng tôi tính cả 6 lớp R3, R4, R5, R8, R13 và R15 đều có lực 
lượng bằng 147.456. Vì thế số các S-hộp mạnh sẽ là 147.456  6 = 844.736. Hơn 
nữa, một số đại lượng chặt hơn được xem xét đó là nd là số các đặc trưng mà tại đó 
đạt được độ đo lượng sai nhỏ nhất (bằng 1/4) và nl là số các xấp xỉ tuyến tính mà 
đạt được độ đo tuyến tính nhỏ nhất (bằng 1/4). Ta có, tính chất sau: 
3.2.4. Mệnh đề 6. nd và nl là các đại lượng được bảo toàn qua biến đổi affine. 
Chứng minh. Trong chứng minh tính chất bất biến của Lin(S) và Diff(S), chúng ta 
rút ra     12, 1, T
Tw w
b bD
S a S a C  và 2 1 1, ,
S S
a b Ca D b
n n  . Vì vậy, các đại lượng nd và nl là 
bất biến trong một lớp tương đương affine.■ 
Vì người ta muốn đạt tới số nhánh cực đại nên sẽ chỉ quan tâm tới các lớp có 
chứa S-hộp mà có số nhánh (đại lượng thể hiện khả năng khuếch tán của hộp thế, 
xem [6]) bằng 3. Trong số những lớp như vậy, giá trị nd cực tiểu là 18, giá trị nl cực 
tiểu là 32. Chỉ có 4 lớp tương đương affine có các tính chất mong muốn, đó là G9, 
G10, G14 và G15. Nếu ta quan tâm tới các S-hộp có tính Serpent, thì sẽ chỉ có 6 lớp 
đó là R3, R4, R5, R8, R13 và R15. Như vậy, xuất phát từ mối quan tâm đến các đại 
lượng nd, nl và số nhánh bằng 3, chúng ta cũng đi đến đúng 6 lớp Serpent như định 
nghĩa của S-hộp mạnh. Trong [7] đã đưa ra thống kê cho các S-hộp có tính chất tối 
ưu (bảng 5). Điều này đã được chúng tôi kiểm tra lại bằng lập trình: 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 215
Bảng 5. Tính chất của 16 lớp tối ưu. 
Đại diện chuẩn tắc 
0123456789ABCDEF 
Thành viên & 
nghịch đảo 
DL LC Số nhánh 
cực đại p nd  nl 
0123468A5BCF79DE G2, 
1
0G
 1/4 24 1/4 36 3 
0123468A5BCF7D9E G15, 
1
14G
 1/4 18 1/4 32 3 
0123468A5BCF7E9D G0,
1
2G
 1/4 24 1/4 36 3 
0123468A5BCFDE79 G8,
1
8G
 1/4 24 1/4 36 2 
0123468A5BCFED97 G1,
1
1G
 1/4 24 1/4 36 3 
0123468B59CED7AF G9,
1
9G
 1/4 18 1/4 32 3 
0123468B59CEDA7F G13,
1
13G
 1/4 15 1/4 30 2 
0123468B59CF7DAE G14,
1
15G
 1/4 18 1/4 32 3 
0123468B5C9DE7AF G12,
1
12G
 1/4 15 1/4 30 2 
0123468B5C9DEA7F G4,
1
4G
 1/4 15 1/4 30 2 
0123468B5CD79FAE G6,
1
6G
 1/4 15 1/4 30 2 
0123468B5CD7AF9E G5,
1
5G
 1/4 15 1/4 30 2 
0123468B5CD7F9EA G3,
1
3G
 1/4 15 1/4 30 2 
0123468C59BDE7AF G10,
1
10G
 1/4 18 1/4 32 3 
0123468C59BDEA7F G7,
1
0G
 1/4 15 1/4 30 2 
0123468C59DFA7BE G11,
1
11G
 1/4 15 1/4 30 2 
4. KẾT LUẬN 
Nội dung bài viết đã phân tích chi tiết và chứng minh chặt chẽ một số tính chất 
đối với các S-hộp có tính chất mật mã mạnh (mệnh đề 1,3,5,6). Bằng lập trình 
chúng tôi đã xác định toàn bộ 844.736 S-hộp thỏa mãn các tính chất này. Kết quả 
này cho phép chúng ta chủ động thay đổi tham số S-hộp trong các mã khối có kích 
thước khối là 64 bit sử dụng các S-hộp 4 bit. Nhất là đối với các thuật toán có 
nguyên lý thiết kế đặc biệt như giữ bí mật hộp thế (GOST 28147-89) thì hộp thế 
đóng vai trò cực kì quan trọng trong việc đảm bảo độ an toàn của thuật toán kháng 
lại các tấn công thám mã. Do đó, các tiêu chuẩn hộp thế cần được xem xét, đánh 
giá chặt chẽ cũng như luôn luôn được cập nhật bởi người sử dụng thuật toán. 
 TÀI LIỆU THAM KHẢO 
[1]. Fontanari, Claudio, et al. "On weakly APN functions and 4-bit S-Boxes." Finite 
Fields and Their Applications 18.3 (2012): 522-528. 
[2]. N. V. Long, N. B. Cương, T. D. 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ự (Số chuyên đề - Tuyển tập các Báo cáo khoa học hội nghị – 
ATTT&CNTT’12). 
[3]. N. B. Cương, T. D. Lai – “Về phân loại các S-hộp 44-bit kiểu Serpent” – Tạp 
chí Nghiên cứu khoa học và Công nghệ quân sự (Số chuyên đề - Tuyển tập 
Công nghệ thông tin & Khoa học máy tính 
H.V. Quân, N. B. Cương, “Về các S-hộp 4x4 bit có tính chất mật mã mạnh.” 216 
các báo cáo khoa học hội nghị – ATTT&CNTT’13). 
[4]. N. B. Cương, N. V. Long, T. D. Lai, “Một số đặc trưng đại số của các S-hộp 
44-bit chống thám mã lượng sai và tuyến tính”, Tạp chí Ứng dụng toán học, 
số 10, ISSN 1858-4492, 9/2012. 
[5]. Caranti, A., Francesca Dalla Volta, and M. Sala. "On some block ciphers and 
imprimitive groups." Applicable algebra in engineering, communication and 
computing 20.5-6 (2009): 339-350. 
[6]. Leander, Gregor, and Axel Poschmann. "On the Classification of 4 Bit S-
boxes." Arithmetic of Finite Fields. Springer Berlin Heidelberg, 2007. 159-
176. 
[7]. Saarinen, Markku-Juhani O. "Cryptographic analysis of all 44-bit s-boxes". 
Selected Areas in Cryptography. Springer Berlin Heidelberg, 2012. 
[8].  
 ABSTRACT 
 ON STRONGLY CRYPTOGRAPHIC 44-BIT S-BOXES 
Often S-boxes are the only nonlinear component in a block cipher and as 
such play an important role in ensuring its resistance to cryptanalysis. Thus, 
the design and use of the S-box in a specific cipher should be considered 
carefully. In this paper, we discuss some properties of strongly cryptographic 
44 S-boxes. Morever, we have generated and classified all the S-boxes 
satisfying these properties. 
Keywords: Block cipher, Differential cryptanalysis, Linear cryptanalysis, Weakly APN function, Strongly S-
boxes 
 Nhận bài ngày 21 tháng 07 năm 2015 
 Hoàn thiện ngày 10 tháng 08 năm 2015 
 Chấp nhận đăng ngày 07 tháng 09 năm 2015 
Địa chỉ: 1 Cục Cơ yếu – BTTM; *Email: hoangvanquan@gmail.com; 
 2 Viện KHCN Mật mã/Ban Cơ yếu Chính phủ