Một số kết quả mở rộng về phân loại S-Hộp 4 bit - Nguyễn Bùi Cươ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 125 MỘT SỐ KẾT QUẢ MỞ RỘNG VỀ PHÂN LOẠI S-HỘP 4 BIT Nguyễn Bùi Cương* Tóm tắt: Trong bài báo này, chúng tôi giải quyết bài toán xác định toàn bộ lớp tương đương affine của các S-hộp 4-bit. Đầu tiên, dựa trên cách tiếp cận trong [1], chúng tôi xác định tất cả 302 lớp tương đương cho tập các S-hộp 4 bit bất kì. Sau đó, một số kết quả lý thuyết đưa ra nhằm giải quyết bài toán tìm số lượng của một lớp tương đương affine. Cuối cùng, chúng tôi thực hành thuật toán đề xuất trong bài báo và thảo luận về khả năng tính toán cùng yêu cầu lưu trữ đối với tất cả các S- hộp 4-bit bất kì dựa trên quan hệ tương đương affine. Từ khóa: S-hộp 4-bit, Tương đương affine, Thám mã tuyến tính, Thám mã lượng sai. 1. MỞ ĐẦU Các S-hộp 4 bit đóng vai trò quan trọng trong thiết kế của một số mã khối hạng nhẹ (lightweight block cipher). Nó thường là thành phần phi tuyến duy nhất đảm bảo độ an toàn của mã pháp kháng lại tấn công tuyến tính và lượng sai. Vì vậy, các kết quả nghiên cứu về S-hộp 4 bit thu hút nhiều sự quan tâm nghiên cứu của các nhà lập mã trên thế giới. Tính chất mật mã của của chúng thường được khảo sát một cách tỉ mỉ nhằm đảm bảo độ an toàn của mã pháp tổng thể. Các công trình liên quan: Trong [2], Leander và Poschmann đã đưa ra những kết quả nghiên cứu đầu tiên về các tính chất mật mã đối với các S-hộp 4-bit dựa trên quan hệ tương đương affine giữa các S-hộp. Các tác giả đã đưa ra khái niệm S-hộp 4-bit tối ưu kháng lại thám mã tuyến tính và lượng sai, sau đó phân loại dựa trên quan hệ tương đương affine. Tuy nhiên, các kết quả của [2] mới chỉ liệt kê được đại diện cho 16 lớp tương đương affine của các S-hộp 4-bit tối ưu này và 1.396.032 S-hộp tối ưu thỏa mãn S(i) = i, i  {0, 1, 2, 4, 8} mà chưa đưa ra được số lượng tất cả các S-hộp trong mỗi lớp tương đương affine này. Điều này sẽ làm cho sự lựa chọn các hộp thế cho các mã pháp cần xây dựng bị hạn chế do sự tồn tại của các điểm bất động. Trong [1], Saarinen đã đưa ra thuật toán phân tích một số đại lượng mật mã của hộp thế dựa trên quan hệ tương đương hoán vị nhằm xác định các S-hộp có tính kháng thám mã lượng sai và tuyến tính tốt hơn. Tuy nhiên, có một số tính chất mật mã không tỉ lệ thuận với tính chất kháng lại thám mã tuyến tính và lượng sai như khái niệm bậc trong suốt (xem [3-5]) hay độ dư thừa tuyến tính (xem [6]) cũng như khả năng cài đặt an toàn của các hộp thế trong [7]. Do đó, chúng ta cũng cần xem xét các hộp thế không phải là tối ưu nhằm có thể lựa chọn được các S-hộp phù hợp với tiêu chí thiết kế của mình. Việc phân lớp các hộp thế cũng đã được đề cập trong luận án tiến sĩ Cannière [8] song tác giả sử dụng phương pháp tiếp cận khác dựa trên thuật toán kiểm tra tính tương đương affine của hai S-hộp trong trường hợp tổng quát. Đóng góp của chúng tôi. Bài báo đưa ra một số mở rộng của kết quả lý thuyết trong bài báo [2] về phân loại các hộp thế 4-bit. Cụ thể, chúng tôi đã tìm đủ 302 lớp tương đương affine của các hộp thế 4-bit. Hơn nữa, chúng tôi đã giải quyết triệt để bài toán xác định số lượng phần tử của mỗi lớp tương đương affine này, cũng như sinh đủ các hộp thế cho mỗi lớp. 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.” 126 Bố cục bài báo. Đầu tiên, các khái niệm cơ bản được trình bày. Sau đó, cách tiếp cận sinh ra đủ 302 lớp tương đương affine của S-hộp 4 bit được giới thiệu. Tiếp theo, chúng tôi trình bày chứng minh một số kết quả lý thuyết gồm một mệnh đề và ba bổ đề. Cuối cùng là một số kết quả thực hành và phân tích đối với các hộp thế 4-bit. 2. MỘT SỐ KHÁI NIỆM CƠ BẢN Đối với 2 vecto a,b  2 n , ký hiệu 1 0 , n i i i a b a b     là tích trong của a và b. Đối với hàm bool có n biến f: 2 2 n   và phần tử a  2 n , ta định nghĩa hệ số Walsh của f tại a bởi 2 ( ) ,( ) ( 1) n f x a x x f a       . Bậc tuyến tính của f được định nghĩa là: Lin(f) = 2 max ( ) na f a   . Với một S-hộp có kích cỡ nn, tức là ánh xạ n bit vào n bit, S: 2 2 n n  chúng ta ký hiệu đối với vecto bất kỳ b 2 n hàm thành phần (component function) Sb tương ứng: Sb : 2 n    , x  b, S(x). Chúng ta định nghĩa bậc tuyến tính (linearity) của S là: Lin(S) = 2 2, \{ } max ( ) n n ba b S a   0   . Để đo khả năng kháng lại thám mã lượng sai, chúng ta định nghĩa với a 2 n , 2 2: n m S a   , x  S(x)  S(x  a), Khi đó, giá trị sai khác của S-hộp S được xác định như sau: Diff(S) =  2 2 1 , \ , max ( ) n n S aa b b  0  với 1, ,( ) { : ( )= }S a S ab x x b    . Bài báo [2] đã định nghĩa tính tối ưu (chống lại thám mã lượng sai và tuyến tính) của S-hộp 4 bit là một ánh xạ song ánh mà có Lin(S) = 8 và Diff(S) = 4. Bài báo cũng đưa ra khái niệm tương đương affine của hai hộp thế và phân loại các hộp thế tối ưu dựa trên khái niệm quan hệ tương đương affine giữa hai S-hộp được định nghĩa như sau: Định nghĩa 1. ([9]) Gọi 2 S-hộp S1 và S2 từ 2 n vào 2 n là tương đương affine nếu tồn tại các biến đổi tuyến tính song ánh A, B ( GL(n, 2 )) và các hằng số a, b 2 n sao cho S2(x) = B(S1(A(x)  a))  b. (trường hợp đặc biệt khi a = b = 0 thì ta gọi S1 và S2 là tương đương tuyến tính). Nếu hai S-hộp S1 và S2 là tương đương (affine) thì ta ký hiệu chúng bởi S1 ~ S2. Để đơn giản, trong phần còn lại bài báo chúng tôi kí hiệu  là tập các biến đổi affine giữa hai hộp thế, khi đó nếu 1 2S S thì tồn tại hai phép biến đổi A1 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.