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

Nghiên cứu khoa học công nghệ<br /> <br /> MỘT SỐ KẾT QUẢ MỞ RỘNG VỀ PHÂN LOẠI S-HỘP 4 BIT<br /> Nguyễn Bùi Cương*<br /> 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<br /> 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],<br /> 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<br /> đó, 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<br /> 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<br /> 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-<br /> hộp 4-bit bất kì dựa trên quan hệ tương đương affine.<br /> 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.<br /> <br /> 1. MỞ ĐẦU<br /> 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<br /> nhẹ (lightweight block cipher). Nó thường là thành phần phi tuyến duy nhất đảm<br /> 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<br /> 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<br /> 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<br /> một cách tỉ mỉ nhằm đảm bảo độ an toàn của mã pháp tổng thể.<br /> Các công trình liên quan: Trong [2], Leander và Poschmann đã đưa ra những<br /> 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<br /> 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<br /> 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<br /> 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ê<br /> đượ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à<br /> 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<br /> 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<br /> 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<br /> 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ố<br /> đạ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<br /> đị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,<br /> 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<br /> 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<br /> 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 đó,<br /> 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<br /> đượ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ế<br /> cũng đã được đề cập trong luận án tiến sĩ Cannière [8] song tác giả sử dụng<br /> 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<br /> của hai S-hộp trong trường hợp tổng quát.<br /> Đó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<br /> 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<br /> 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<br /> để 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<br /> như sinh đủ các hộp thế cho mỗi lớp.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 125<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> 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<br /> 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.<br /> 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<br /> đề 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<br /> thế 4-bit.<br /> 2. MỘT SỐ KHÁI NIỆM CƠ BẢN<br /> n 1<br /> Đố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<br /> i 0<br /> <br /> với hàm bool có n biến f:   2 và phần tử a  2n , ta định nghĩa hệ số Walsh<br /> n<br /> 2<br /> <br /> của f tại a bởi f  (a )   (1) f ( x ) a , x<br /> . Bậc tuyến tính của f được định nghĩa là:<br /> x2n<br /> <br /> Lin(f) = max<br /> n<br /> f  (a) .<br /> a2<br /> <br /> 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: 2n  2n chúng<br /> ta ký hiệu đối với vecto bất kỳ b  2n hàm thành phần (component function) Sb<br /> tương ứng: Sb : 2n   , x  b, S(x).<br /> Chúng ta định nghĩa bậc tuyến tính (linearity) của S là:<br /> Lin(S) = max Sb (a ) .<br /> a2n ,b2n \{0}<br /> <br /> Để đo khả năng kháng lại thám mã lượng sai, chúng ta định nghĩa với a  2n<br /> S ,a : 2n  2m , x  S(x)  S(x  a),<br /> Khi đó, giá trị sai khác của S-hộp S được xác định như sau:<br /> Diff(S) = max S,1a (b) với S,1a (b)  {x : S ,a (x)=b} .<br /> a2n \0,b2n<br /> <br /> 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<br /> 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<br /> 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<br /> 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<br /> định nghĩa như sau:<br /> Định nghĩa 1. ([9]) Gọi 2 S-hộp S1 và S2 từ 2n vào 2n là tương đương affine nếu<br /> 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<br />  2n sao cho S2(x) = B(S1(A(x)  a))  b.<br /> (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).<br /> 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.<br /> Để đơ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<br /> affine giữa hai hộp thế, khi đó nếu S1  S 2 thì tồn tại hai phép biến đổi A1 và A2<br /> thuộc  sao cho S2  A1  S1  A2 với ( là kí hiệu của phép toán nhân trong nhóm<br /> 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.<br /> <br /> <br /> 126 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.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Đ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<br /> 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]).<br /> 3. CÁC LỚP TƯƠNG ĐƯƠNG AFFINE CỦA CÁC S-HỘP 4 BIT<br /> 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<br /> bất kì sẽ bảo toàn qua quan hệ tương đương affine. Từ đó, các tác giả đã xem xét<br /> một kết quả lý thuyết (bổ đề 1, [2]) để giảm không gian tìm kiếm từ 16!  244 về<br /> 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<br /> 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,<br /> 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<br /> của các S-hộp bất kì bằng kết quả mở rộng sau:<br /> Bổ đề 1. Mọi lớp tương đương affine trên 2n luôn tồn tại một hộp thế S thỏa mãn<br /> S (i )  i với i  0,1,..., 2n 1 .<br /> Chứng minh. Tương tự như trong mệnh đề 2 của bài báo [9]. <br /> 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ỳ<br /> trên tập các hộp thế thỏa mãn S (i )  i với i  0,1,..., 2n 1 . Chúng tôi đã thực hành<br /> 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<br /> đươ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<br /> 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ế<br /> 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ể<br /> 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<br /> 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ể<br /> xem xét một thuật toán cải tiến như sau:<br /> Thuật toán 1:<br /> Đầ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.<br /> Đầu ra: Tập S=  s  , #S.<br /> Các bước của thuật toán:<br /> 1. S ← Ø; m ← 0.<br /> 2. for i = 1 to #  do<br /> 2.1 r ← s  [i];<br /> 2.2 if r not in S then<br /> 2.2.1 for j = 1 to #  do S ← S{  [j]r};<br /> 2.2.2 m ← m + #  ;<br /> 3. Return: S, m.<br /> Ở đâ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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> 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<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 127<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> 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,<br /> khi đó, tồn tại một cặp  a ', A  j  với j