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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:9

Thêm vào BST

Báo xấu

29
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thông thường các hộp thế là thành phần phi tuyến duy nhất trong mã khối và đóng vai trò quan trọng trong việc bảo đảm khả năng kháng lại các thám mã. Vì vậy việc thiết kế và sử dụng các hộp thế trong một mã pháp cụ thể cần được xem xét cẩn thận. Trong bài viết này chúng tôi nghiên cứu chi tiết và bổ sung chứng minh một số tính chất của S-hộp 44 bit có tính chất mật mã mạnh. Trong đó, chúng tôi sinh và phân loại toàn bộ các hộp thế thỏa mãn các tính chất này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

Công nghệ thông tin & Khoa học máy tính VỀ CÁC S-HỘP 44-BIT CÓ TÍNH CHẤT MẬT MÃ MẠNH Hoàng Văn Quân1*, Nguyễn Bùi Cương2 Tóm tắt: Thông thường các hộp thế là thành phần phi tuyến duy nhất trong mã khối và đóng vai trò quan trọng trong việc bảo đảm khả năng kháng lại các thám mã. Vì vậy việc thiết kế và sử dụng các hộp thế trong một mã pháp cụ thể cần được xem xét cẩn thận. Trong bài viết này chúng tôi nghiên cứu chi tiết và bổ sung chứng minh một số tính chất của S-hộp 44 bit có tính chất mật mã mạnh. Trong đó, chúng tôi sinh và phân loại toàn bộ các hộp thế thỏa mãn các tính chất này. Từ khóa: Mã khối, S-hộp, Thám mã lượng sai, Thám mã tuyến tính, Hàm hầu phi tuyến hoàn thiện. 1. MỞ ĐẦU Đối với một lớp lớn các mã khối, các S-hộp là tổ hợp các véc tơ hàm Bool song ánh S từ 2n vào 2n . Bài viết này tập trung vào các S-hộp 44-bit (n = 4) đã được sử dụng cho thuật toán mã GOST 28147-89 [8] và một số mã khối khác cùng với việc phân tích, đánh giá các tính chất mật mã mạnh. Để có thể đánh giá độ an toàn của các S-hộp ta phải đưa ra được các tiêu chí đánh giá cụ thể, bên cạnh các tính chất tối ưu chống lại tấn công lượng sai và tuyến tính còn phải quan tâm tới các tính chất khác như tính lan sai, bậc đại số,...Vì vậy, các khái niệm S-hộp mạnh đã được đề xuất [1]. Trong bài viết này, chúng tôi bổ sung và chứng minh một số nội dung cần thiết phục vụ cho việc tìm kiếm các S-hộp có tính chất mật mã mạnh và sau đó là tìm kiếm các hộp thế này bằng thực hành. 2. CÁC HÀM HẦU PHI TUYẾN HOÀN THIỆN YẾU 2.1. Khái niệm -đều yếu và l-chống bất biến mạnh n n 2.1.1. Định nghĩa 1. [1] Cho hàm Bool f :  2    2  . Giả sử fˆu ( x) := f(x  u)  f(x). Khi đó định nghĩa: n n - Hàm f là -đều nếu |{x   2  : fˆu ( x) = v}|   đối với mọi u    2 \{0} và n đối với mọi v  2  , n - Và nó là -đều yếu (weakly -uniform) nếu đối với mọi u  2  \{0} chúng ta có |Im( fˆu )|  2n-1/. Chú ý rằng định nghĩa 1 khác với định nghĩa trong [5] (|Im( fˆu )|  2n/(+2) + 1). Dễ thấy rằng nếu f là -đều thì cũng là -đều yếu. Thật vậy, nếu f là -đều thì với n mọi u   2  \{0} chúng ta có |Im( fˆu )|  2n/ > 2n-1/. Nếu một hàm f là 2r-đều yếu và ảnh Im( fˆu ) được chứa trong một không gian con W, thì ta có card(W)  208 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.” Nghiên cứu khoa học công nghệ |Im( fˆu )| > 2n-1-r nên số chiều của W ít nhất là n – r. Đó là tính chất của f mà sẽ được cần đến trong chứng minh Định lý 4.4 [5]. 2.1.2. Mệnh đề 1. Tính -đều và -đều yếu là một bất biến affine. Chứng minh. Mệnh đề 1 trong [2] đã chứng minh rằng tính -đều là một bất biến affine. Tương tự như vậy, bây giờ ta chứng minh rằng tính chất -đều yếu là một bất biến affine. Đối với S-hộp S, ta đặt: naS,b  S,1a  b  . Giả sử S1 và S2 là hai S- hộp tương đương affine, điều này có nghĩa là tồn tại các ma trận khả nghịch C, D  GL(n, 2 ), c, d   2 n sao cho S2(x) = D(S1(Cx  c))  d với mọi x. Giả sử: naS,b  S21,a  b   # x  2n | S 2  x   S 2  x  a   b . 2 Có S2(x)  S2(x  a) = b tương đương với D(S1(Cx  c)  d  D(S1(C(x  a)  c))  d = b. Đặt y = Cx  c ta có: D(S1(y))  D(S1(y  Ca)) = b  S1(y)  S1(y  Ca) = D-1b S 2 S 1   Như vậy, na,b  nCa,D1b . Điều này có nghĩa rằng b Im( S a1 )  D-1b Im( SCa 2 ).   Do vậy, |Im( S a1 ) | = |Im( SCa 2 )|, và vì thế S1 và S2 đồng thời thỏa mãn tính -đều yếu. ■ m 2.1.3. Định nghĩa 2. [1] Giả sử A =  2  . Khi đó: - f là l-chống bất biến (l-anti-invariant) nếu đối với không gian con bất kỳ U  A sao cho f(U) = U, chúng ta có dim(U) < m - l hoặc U = A. - f là l-chống bất biến mạnh (strongly l-anti-invariant) nếu đối với 2 không gian con bất kỳ U, W  A, sao cho f(U) = W, chúng ta có dim(U) = dim(W) < m - l hoặc U = W = A. Các mã pháp dựa trên dịch chuyển (Định nghĩa 3.1 [5]) tạo nên một lớp thú vị các mã khối lặp chẳng hạn AES. Theo Định lý 4.4 trong [5], nếu C là một mã pháp dựa trên dịch chuyển và các S-hộp của mỗi tầng thay thế thỏa mãn tính 2r-đều yếu và r-chống bất biến mạnh đối với r nào đó mà 1  r  m/2, và tồn tại một vòng với tầng tuyến tính có tính chất tầng xáo trộn đúng cách thức (proper mixing layer) (trong [5] đã định nghĩa chính xác của tính chất này) thì (C) (tức là nhóm được sinh ra bởi các hàm vòng) là các nhóm nguyên thủy (nhóm hoán vị G tác động trên một tập X được gọi là nguyên thủy nếu nó tác động dịch chuyển trên X và G không bảo toàn phân hoạch không tầm thường nào của X). Đó chính là lý do vì sao tính - đều yếu và l-chống bất biến mạnh được quan tâm đến. Dường như là Định lý 4.4 trong [5] yêu cầu các điều kiện quá mạnh để đảm bảo tính nguyên thủy, nhưng thực ra nó trở nên khá tự nhiên, như được chỉ ra ở các Hệ quả 4.6 và 4.7 của [5]. Theo đó, AES, Serpent thỏa mãn các điều kiện đã nêu ra và có (Serpent) là các nhóm luân phiên trên các tập tương ứng. Trong trường hợp của các S-hộp 4 bit, do quan tâm đến các r thỏa mãn 1  r  m/2 = 2, nên chỉ có 2 khả năng: Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 209 Công nghệ thông tin & Khoa học máy tính - r = 1, khi đó yêu cầu mỗi S-hộp thỏa mãn tính 2-đều yếu và 1-chống bất biến mạnh; - r = 2, khi đó yêu cầu mọi S-hộp là 4-đều yếu và 2-chống bất biến mạnh. Chúng ta quan tâm tới tính 2-đều yếu và tính 4-đều yếu. Chú ý rằng với  < ’ thì một hàm mà thỏa mãn tính -đều sẽ thỏa mãn tính ’-đều và một hàm thỏa mãn tính -đều yếu sẽ thỏa mãn tính ’-đều yếu. Hơn nữa, chúng ta chỉ xét các S-hộp tối ưu, có nghĩa là Diff(S) = 4 hay S có tính 4-đều và như thế nó có tính 4-đều yếu. Vì vậy, sau đây chúng ta chỉ quan tâm đến tính 2-đều yếu. Theo kết quả 1 trong [2], trên 24 không tồn tại hoán vị APN (Almost Perfect Nonlinear – hầu phi tuyến hoàn thiện) tức là không có các S-hộp thỏa mãn Diff(S) = 2 (đó chính là tính 2-đều). 2.1.4. Định nghĩa 3. Chúng ta nói rằng một hàm Bool là một hàm phi tuyến hầu hoàn thiện yếu (weakly APN) nếu nó là 2-đều yếu. Một số kết quả lý thuyết được nêu trong [1] về các hàm APN yếu. Mệnh đề 2 và mệnh đề 4 sau đây đưa ra 2 điều kiện đủ của một hàm Bool thỏa mãn APN yếu. 4 4 2.1.5. Mệnh đề 2 (Preposition 1, [1]) . Giả sử f :  2   2  là một hàm Bool sao cho f là 4-đều và là 2 – chống bất biến mạnh. Khi đó f là APN yếu. n n n Với f:  2     2 ta định nghĩa: nˆ (f) = max |{v    2 \{0}: deg( fˆu , v) = 0}|. u( 2 )n \0 2.1.6. Mệnh đề 3. nˆ (f) là một bất biến affine. Chứng minh: Giả sử f2(x) =Af1(x) + a với A  GL(n, 2 ), a   2  . Khi đó, n f2(x  u)  f2(u), (AT)-1v = (Af1(x  u)  a)  (Af1(x)  a), (AT)-1v  = A(f1(x  u)  f1(x)), (AT)-1v = f1(x  u)  f1(x), AT(AT)-1v = f1(x  u)  f1(x), v Vì thế, v   2 n \{0} : deg( fˆu1 , v) = 0} = {v   2 n \{0} : deg( fˆu2 , v) = 0} nên nˆ (f1) = (f2). Giả sử f2 = f1(Bx  b) với B  GL(n, 2 ), b  2 n . Khi đó, f2(x  B-1u)  f2(u), v = f1(B(x  B-1u)  b)  f1(Bx  b), v = f1(Bx  b  u)  f1(Bx  b), v Đặt Bx  b = y thì f2(x  B-1u)  f2(u), v = f1(y  u)  f1(y), v . Vì thế {v   2 n \{0}: deg( fˆu1 , v) = 0} = {v   2 n \{0} : deg( fˆu2 , v) = 0} nên nˆ (f1) = nˆ (f2). ■ 2.2. Một số tính chất APN yếu của hàm Bool 4 4 Mệnh đề 4 (Preposition 2 [1]). Giả sử f :  2  2 là một hàm Bool sao cho nˆ (f) = 0. Khi đó f là một APN yếu. Mệnh đề ngược lại một phần của mệnh đề 4 đúng với mọi n  2, thật vậy: n n Bổ đề 1 [1]. Giả sử f :  2    2  là một hàm APN yếu. Khi đó nˆ (f)  1. 210 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.” Nghiên cứu khoa học công nghệ 4 4 Định lý 1 [1]. Giả sử f :  2   2  là một hoán vị APN yếu. Khi đó, deg(f) = 3 và n3(f) {12, 14, 15}, trong đó n3(f) – là số lượng các tổ hợp tuyến tính của các hàm Bool thành phần có bậc đại số là 3. 3. CÁC S-HỘP 44-BIT MẠNH 3.1. Đại lượng đo độ kháng chống lại thám mã lượng sai và thám mã tuyến tính Để đo độ kháng chống lại thám mã lượng sai của một S-hộp từ 2n vào 2n , người ta quan tâm đến đại lượng Diff(S) được xây dựng như sau: với a  2n , xét ánh xạ S,a : 2n  2n , x  S(x)  S(x  a), ta có S,1a (b)  {x : S ,a (x)=b} và Diff(S) = max S,1a (b) . a2n \0,b2n n 1 Đối với 2 vecto a, b  2n , ký hiệu a, b   ai bi là tích trong của a và b. Đối i 0 với hàm bool có n biến f:   2 và phần tử a  2n chúng ta định nghĩa hệ số n 2 Walsh của f tại a bởi f  (a) =  (1) f ( x ) a , x . Bậc tuyến tính của f được định x2n nghĩa như là Lin(f) = max f  (a) . Với một S-hộp có kích cỡ nn, ta ký hiệu đối a2n với vecto bất kỳ b  2n hàm thành phần (component function) Sb tương ứng: Sb : 2n  2 , x  b, S(x). Chúng ta định nghĩa bậc tuyến tính (linearity) của S như là Lin(S) = max Sb ( a ) . a2n ,b2n \{0} Giá trị Lin(S) và Diff(S) càng nhỏ thì tương ứng các mã pháp sử dụng các hộp thế S này có khả năng kháng lại thám mã lượng sai và tuyến tính càng tốt. Trong [2] đã có xem xét chi tiết về định nghĩa của một S-hộp 44-bit tối ưu (các giá trị Lin(S) và Diff(S) đạt giá trị nhỏ nhất có thể), đó là những S-hộp song ánh thỏa mãn điều kiện Diff(S)=4 và Lin(S)=8. Nhưng ngoài tính chất tối ưu đó, người ta còn quan tâm tới các tính chất khác nữa, ví dụ như có thể cho rằng sai khác đầu vào 1 bit bất kỳ gây ra sai khác đầu ra có ít nhất 2 bit (như đối với DES hoặc Serpent). Một điều kiện như vậy có thể được sử dụng để tăng số cực tiểu các S-hộp tích cực trong 2 vòng liên tiếp. Tính chất này được nghiên cứu thông qua các đại lượng:   Diff1  S   max n S,1a (b) | wt(a) = wt(b) =1 , với wt(a) là trọng số Hamming của a. a  0 ,b2 Một S-hộp 44-bit tối ưu mà thỏa mãn điều kiện Diff1(S)=0 được gọi là một S-hộp kiểu Serpent. 3.2. Các S-hộp 44 mạnh Một yêu cầu đối với thám mã tuyến tính là xác suất của một biểu thức xấp xỉ tuyến tính mà chỉ sử dụng 1 bit đầu vào và 1 bit đầu ra cần phải nhỏ một cách đặc biệt. Tính chất này được nghiên cứu thông qua đại lượng Lin1(S) =   max Sb (a ) | wt(a)  wt(b)  1 . Để xem xét các tính chất của S-hộp trong bài viết a ,b2n Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 211 Công nghệ thông tin & Khoa học máy tính này chúng tôi sẽ dựa trên một quan hệ tương đương đặc biệt sau: 3.2.1. Định nghĩa 4 ([3]). Hai S-hộp S1, S2 được gọi là tương đương hoán vị khi tồn tại P0, P1 là hai ma trận hoán vị n  n và a, b  2n sao cho: S2(x) = P1(S1(P0(x)  a))  b x  2n . Trong đó, ma trận hoán vị M được định nghĩa thông qua một hoán vị  của n 1 nÕu   i   j phần tử là ma trận có các phần tử mij thỏa mãn: mi , j   . Dễ thấy 0 nÕu   i   j rằng định nghĩa 4 xác định một quan hệ tương đương của tập các S-hộp. Nếu hai S-hộp S1 và S2 là tương đương theo nghĩa ở trên chúng ta ký hiệu điều đó bởi S1 ~S S2. Trong [3] cũng đã nghiên cứu việc phân loại các S-hộp 44-bit kiểu Serpent thành 20 lớp theo tính tương đương hoán vị. 3.2.2. Mệnh đề 5. Lin1(S) là bất biến trong một lớp tương đương kiểu Serpent. Chứng minh: Nếu S1 và S2 là 2 S-hộp tương đương theo kiểu Serpent thì tồn tại hai ma trận hoán vị C, D kích thước n  n và c,  2n thỏa mãn: S 2  x   D  S1  Cx  c    d  x  2n . Hệ số Walsh của hàm S2 tại điểm a b , S2  x   a , x S2,wb  a    xn  1 . Xét tích trongb, S2(x)  a, x = b, D(S1(Cx  c)) 2  d  a, x, đặt y  Cx  c dẫn đến x = C-1 (y  c) = C-1y  C-1c. Khi đó, tích trong ở trên sẽ có dạng: b, D(S1(y))  d   a, C-1x  C-1c = b, D(S1(y))  a, C-1x   b, d  a, C-1c Theo tính chất của tích trong của hai vecto: x, Ay = xAT, y x, y  2n , A  GL(n, 2n ), ta có: b, S2(x)  a, x = bDT, S1(y)  a(C-1)T, y  b, d  a, C- 1 c. Do các ma trận C, D là các ma trận khả nghịch nên khi biến x nhận một lượt tất cả các phần tử trên không gian vecto 2n thì giá trị y = Cx  c nhận một lượt tất cả các phần tử trên không gian vecto 2n . Do đó, ta có hai tổng sau đây bằng nhau: T b , S2  x   a , x   bDT , S1  y   a C 1 , y  b , d  a ,C 1c   1 x2n   yn  1 2 hay  S 2,wb  a    S1,wbDT a  C 1  T  . 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)= max S 2,wb  a  | wt(a ) = wt(b) = 1 = max S1,wb '  a ' | wt(a ') = wt(b ') = 1 = 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. 212 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.” Nghiên cứu khoa học công nghệ 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) = |{ v   2  \{0} : deg(S, v) = i}|. n 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  24 sao cho Sb là một hàm Bool bậc 2. 4 4 3.2.3.Định nghĩa 5.([1]) Chúng ta nói rằng một hoán vị Boolean f:  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 Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 213 Công nghệ thông tin & Khoa học máy tính 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: 4 4 Khẳng định 1 [1]. Giả sử f:  2    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 R9, R11, R16, R0, R1, R2, R6, R17, R18 R7, R10, R12, R14 R4, R13 R 3, R 5 R15 R8 Serpent R19 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  S 2,wb  a    S1,wbDT a  C 1  T  và n S2 a ,b S1  nCa , D 1b . 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: 214 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.” Nghiên cứu khoa học công nghệ Bảng 5. Tính chất của 16 lớp tối ưu. Đại diện chuẩn tắc Thành viên & DL LC Số nhánh 0123456789ABCDEF nghịch đảo p nd  nl cực đại 0123468A5BCF79DE G2, G01 1/4 24 1/4 36 3 0123468A5BCF7D9E G15, G 1 14 1/4 18 1/4 32 3 0123468A5BCF7E9D G0, G 1 2 1/4 24 1/4 36 3 0123468A5BCFDE79 G8, G 1 8 1/4 24 1/4 36 2 0123468A5BCFED97 G1, G 1 1 1/4 24 1/4 36 3 0123468B59CED7AF G9, G91 1/4 18 1/4 32 3 0123468B59CEDA7F G13, G131 1/4 15 1/4 30 2 0123468B59CF7DAE G14, G151 1/4 18 1/4 32 3 0123468B5C9DE7AF G12, G121 1/4 15 1/4 30 2 0123468B5C9DEA7F G4, G 1 4 1/4 15 1/4 30 2 0123468B5CD79FAE G6, G 1 6 1/4 15 1/4 30 2 0123468B5CD7AF9E G5, G 1 5 1/4 15 1/4 30 2 0123468B5CD7F9EA G3, G 1 3 1/4 15 1/4 30 2 0123468C59BDE7AF G10, G101 1/4 18 1/4 32 3 0123468C59BDEA7F G7, G01 1/4 15 1/4 30 2 0123468C59DFA7BE G11, G111 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 Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san Viện Điện tử, 10 - 2015 215 Công nghệ thông tin & Khoa học máy tính 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]. Http://en.wikipedia.org/wiki/GOST_(block_cipher). 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 1 Địa chỉ: Cục Cơ yếu – BTTM; *Email: hoangvanquan@gmail.com; 2 Viện KHCN Mật mã/Ban Cơ yếu Chính phủ 216 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.”