Tóm tắt Luận án Nghiên cứu xây dựng các thành phần mật mã cho thuật toán mã khối hạng nhẹ

ày, cụ thể là hàng loạt công trình về xây dựng S-hộp 4 bit và tầng tuyến tính dựa trên ma trận MDS. 1.3.2. Tình hình nghiên cứu trong nước Các kết quả về xây dựng các thành phần cho mã khối trong nước còn hạn chế. Chủ yếu tập trung cho các mã khối có độ mật cao không phù hợp với các thiết bị có tài nguyên hạn chế. 1.4. Khái lược về nội dung nghiên cứu Trong phần này, luận án khái lược về mô hình mã pháp có cấu trúc SPN dạng AES, tầng phi tuyến sử dụng các S-hộp 4 bit, tầng tuyến tính dựa trên các ma trận MDS. 1.5. Kết luận chương 1 Trong chương này, luận án đã phân tích một số đặc điểm yêu cầu cũng như nhu cầu sử dụng của mật mã hạng nhẹ hiện nay. Từ cơ sở đó kết hợp với các kết quả đã được nghiên cứu trên thế giới, các S-hộp 4 bit và các ma trận MDS hạng nhẹ cho thuật toán mã khối được lựa chọn cho việc nghiên cứu định hướng xây dựng một mã khối hạng nhẹ dạng SPN đảm bảo độ an toàn và có hiệu quả cao. 6 CHƯƠNG 2 NGHIÊN CỨU XÂY DỰNG CÁC HỘP THẾ 4 BIT CHO MÃ KHỐI HẠNG NHẸ 2.1. Cơ sở sinh cho việc sinh các S-hộp có tính chất mật mã tốt Đầu tiên, các ký hiệu và một số khái niệm sử dụng trong luận án được trình bày. Sau đó, luận án trình bày các quan hệ tương đương được sử dụng trong khảo sát các S-hộp, cụ thể là quan hệ tương đương affine tương đương tuyến tính, quan hệ tương đương hoán vị, ... Cuối cùng, các tính chất mật mã quan trọng của S-hộp S được định nghĩa là bậc tuyến tính Lin(S), đặc trưng lượng sai Diff(S), bậc đại số deg(S), bậc vào\ra degIO(S), bậc trong suốt , độ dư thừa tuyến tính và một số tính chất khác (số nhánh, điểm bất động, tính chất cuộn). 2.2. Phân tích một số kết quả nghiên cứu đã có cho S-hộp 4 bit 2.2.1. Các S-hộp 4 bit tối ưu chống lại thám mã lượng sai và tuyến tính Phần này, luận án phân tích về cận dưới của Lin(S), Diff(S) với S là một S-hộp 4 bit bất kì nhằm đưa ra được các giá trị tối ưu cho khả năng chống lại thám mã tuyến tính và lượng sai cho các S-hộp này, các kết quả này đã có song chưa được chi tiết, cụ thể bậc phi tuyến của một S- hộp 4 bit song ánh sẽ thỏa mãn Lin(S)8 (Mệnh đề 2.3), còn đối với đặc trưng lượng sai thỏa mãn Diff(S)  4 (Nhận xét 2.2) với mọi S-hộp 4 bit. Như vậy, các S-hộp 4 bit có các giá trị tối ưu nhất để chống lại tấn công tuyến tính sẽ được định nghĩa như sau: Định nghĩa 2.14. Giả sử S: 4 42 2  là một S-hộp. Nếu S thỏa mãn các điều kiện sau thì ta gọi S là một S-hộp tối ưu chống lại thám mã tuyến tính và lượng sai: 1. S là một song ánh. 2. Lin(S) = 8. 3. Diff(S) = 4. Ta có: 7 Mệnh đề 2.6. Giả sử A, B  GL(4, 2) là 2 ma trận khả nghịch 44 và a,b 42 . Giả sử S: 4 42 2  là một S-hộp tối ưu chống lại thám mã tuyến tính và lượng sai. Khi đó, S-hộp S’ với S’(x)=B(S(A(x)a)b cũng là một S-hộp tối ưu chống lại thám mã tuyến tính và lượng sai. Mệnh đề 2.7. Giả sử S: 4 42 2  , S là tối ưu chống lại thám mã tuyến tính và lượng sai khi và chỉ khi S-1 là tối ưu chống lại thám mã tuyến tính và lượng sai. Bằng thực hành, luận án đã nhận được 16 lớp tương đương affine cho các S-hộp tối ưu chống lại thám mã tuyến tính và lượng sai, giống như các kết quả đã có. 2.2.2. Tính Serpent của S-hộp 4 bit Ngoài các tính chất Diff(S)=4 và Lin(S)=8 ra, ta xem xét một tính chất quan trọng có trong các S-hộp của thuật toán Serpent Định nghĩa 2.15. Giả sử S: 42  42 là một S-hộp. Nếu S thỏa mãn các điều kiện sau ta gọi S là một S-hộp kiểu Serpent. 1. S là tối ưu chống lại thám mã tuyến tính và lượng sai. 2. Diff1(S) = 0, tức là sai khác đầu vào 1 bit bất kỳ gây ra sai khác đầu ra ít nhất 2 bit. với            2 1 2 0, w w 1 Diff max | .          n n a b t a t b S x S x S x a b   Để khảo sát giá trị này, ta sử dụng quan hệ tương đương hoán vị. Khi đó, phép tương đương hoán vị bảo toàn tính chất kiểu Serpent của S-hộp 4 bit (Bổ đề 2.2), số nhánh (Bổ đề 2.3), quan hệ nghịch đảo (Bổ đề 2.4), tính chất không cuộn của các S-hộp kiểu Serpent (Hệ quả 2.1). Để thực hành phân lớp các S-hộp dạng này, luận án sử dụng thuật toán 2 và nhận được 2.211.840 S-hộp Serpent được phân theo 20 lớp tương đương hoán vị. 8 2.2.3. Các S-hộp 4 bit tối ưu có tính chất cuộn Một số kết quả đánh giá tính tối ưu chống lại thám mã lượng sai và tuyến tính trong bài báo [45] được giới thiệu; cụ thể là không có S-hộp kiểu Serpent nào có tính chất cuộn và khi có số điểm bất động lớn hơn 5 thì S-hộp có tính chất cuộn sẽ không đạt được tính tối ưu. Sau đó, luận án cũng đã thực hành sinh các S-hộp 4 bit có tính chất cuộn theo các kết quả nghiên cứu trong bài báo [45]. 2.3. Các kết quả phát triển mới trong luận án 2.3.1. Một số đặc trưng đại số của S-hộp 4-bit Luận án trình bày một số kết quả liên quan tới hai đại lượng bậc đại số deg(S) và bậc vào ra degIO(S) của một S-hộp. Đầu tiên, số lượng các phương trình vào/ra của một S-hộp được đánh giá thông qua kết quả sau: Mệnh đề 2.8. Cho một S-hộp bất kì có kích thước n×m và tập  gồm t phần tử là các đơn thức cho trước như sau  1,..., tg g , khi đó số lượng các phương trình đa biến độc lập tuyến tính có các đơn thức trong  là  rank SL t M , với ma trận  , i jM m có kích thước 2n×t trong đó  , ( , )i j jm g i S i 0,...,2 1;  ni 1,...,j t . Hệ quả 2.2. Cho một S-hộp bất kì có kích thước n×m, khi đó số lượng các phương trình đa biến độc lập tuyến tính có bậc không quá d từ m+n biến 1 1,..., , ,...,n mx x y y trên 2 là:   0 rank         d i m n M i Tiếp theo, luận án xem xét một số tính chất đại số của các S-hộp kích thước nm đối với quan hệ tương đương affine như sau: Bổ đề 2.7. Cho f là hàm Bool n biến, A là ma trận tuyến tính khả nghịch kích cỡ nn trên trường F2, còn b 2 n . Khi đó, ta có: deg f(x) = deg f(Ax  b). 9 Mệnh đề 2.10. Bậc đại số của một S-hộp là bất biến đối với quan hệ tương đương affine. Hơn nữa, tập đa giá trị (multiset) D={deg(Sc)|c 2 m } cũng bất biến khi chịu tác động của phép biến đổi affine. Mệnh đề 2.11. Bậc vào/ra của một S-hộp là bất biến dưới quan hệ tương đương affine. Tức là, degIOS1 = degIOS2 với S1 tương đương affine với S2. Hơn nữa, số lượng các phương trình vào/ra độc lập tuyến tính cũng bất biến qua quan hệ tương đương affine. Mệnh đề 2.12. Nếu S: 2 2 n n  là song ánh thì degIO(S) = degIO(S-1). Hơn nữa, số lượng các phương trình vào/ra độc lập tuyến tính là không đổi. Đối với các S-hộp 4-bit, ta có : Nhận xét 2.4. Số lượng các phương trình vào/ra bậc hai độc lập tuyến tính của S-hộp 4 bit bất kỳ ít nhất bằng 21. Như vậy, đối với các S-hộp này, bậc vào\ra của chúng lớn nhất là bằng 2, tức là degIOS  2. Tiếp theo, bậc vào/ra của 16 lớp S-hộp được xem xét trên dựa theo kết quả lý thuyết sau: Bổ đề 2.9. Bậc vào/ra của S-hộp 4 bit tối ưu ít nhất bằng 2. Hệ quả 2.5. Cả 16 lớp S-hộp 4 bit tối ưu chống thám mã lượng sai và tuyến tính có bậc vào/ra là 2 và số lượng các phương trình vào/ra bậc hai độc lập tuyến tính đạt giá trị tối ưu, tức là bằng 21. 2.3.2. Khảo sát bậc trong suốt của các S-hộp 4-bit kiểu Serpent Trong phần này, luận án trình bày một số kết quả nghiên cứu về bậc trong suốt, là đại lượng định lượng cho khả năng chống lại tấn công DPA đối với mã pháp dạng SPN. Đầu tiên, chúng ta có kết quả mở rộng sau, Bổ đề 2.10. Đối với các S-hộp có phổ tự tương quan của hàm thành phần Si thỏa mãn     12 1\ 0 , 2       i nn n Si a a ; hàm S sẽ đạt cực đại tại β {0, 2n-1}, tức là    0 2 1  nS S S   . 10 Từ kết quả này, ta có: Mệnh đề 2.13. Cho S-hộp S1 thỏa mãn điều kiện phổ tương quan của các hàm thành phần 1Sif thỏa mãn  2 \ 0 ,  n  1 11 2     S i n n i f và S- hộp S2 tương đương hoán vị với S1. Khi đó, 1. S-hộp S2 cũng thỏa mãn điều kiện phổ tương quan của các hàm thành phần 2Sif thỏa mãn  2 \ 0 ,  n  2 11 2     S i n n i f . 2. 1 2 S S  . Khi đó ta có thể xác định được bậc trong suốt của toàn bộ các S-hộp kiểu Serpent như sau: Bảng 2.3: Bậc trong suốt của các S-hộp 4-bit kiểu Serpent Lớp Đại diện S (0123456789ABCDEF) Số lượng Bậc trong suốt R0 03567ABCD4E9812F 73728 3.53 R1 035869A7BCE21FD4 147456 3.40 . .. R18 0358BC6FE9274AD1 73728 3.33 R19 035A7CB6D429E18F 73728 3.27 2.3.3. Một số nghiên cứu về độ dư thừa tuyến tính Trong phần này, một số nghiên cứu về độ dư thừa tuyến tính của S-hộp và sự ảnh hưởng của nó lên hàm vòng được trình bày. Mệnh đề 2.14. Cho hai hộp thế tương đương affine S1, S2 có kích thước n×n bit. Khi đó,    1 2S S  . Như vậy, các S-hộp trong cũng một lớp tương đương affine sẽ cùng có độ dư thừa tuyến tính. Khảo sát cho 16 lớp tương đương affine tối ưu chống thám mã tuyến tính và lượng sai của S-hộp 4 bit, ta nhận được kết quả sau: 11 Bảng 2.4: Độ dư thừa tuyến tính của 16 lớp S-hộp 4 bit tối ưu Tên lớp Phần tử đại diện (0123456789ABCDEF)  S Tên lớp Phần tử đại diện (0123456789ABCDEF)  S LS1 0123469A8BCE7FD5 69 LS9 0123469A8BCEF75D 83 LS2 0123469A8BCED57F 85 LS10 0123469A85CEBDF7 92 LS3 0123469A8BCE5DF7 85 LS11 0123469C85DAE7BF 92 LS4 0123469A8CBD7EF5 105 LS12 0123469C85FDB7AE 105 LS5 0123469A8C5D7EFB 105 LS13 0123469A8C5DBEF7 105 LS6 0123469A8CBDE57F 105 LS14 0123469A85CE7DFB 34 LS7 0123469A8CBD5FE7 105 LS15 0123469A85CFDBE7 100 LS8 0123469C85BFED7A 105 LS16 0123469A85CE7FDB 100 Xuất phát từ các kết quả về độ dư thừa tuyến tính của S-hộp sử dụng trong hàm vòng dạng SPN, luận án đưa ra một số phân tích tính tương đương affine của các hàm Bool là tổ hợp tuyến tính của các hàm tọa độ đầu ra của hàm vòng dạng SPN. Với hàm vòng dạng SPN sử dụng hộp thế sở hữu độ dư thừa tuyến tính hoàn toàn, ta có kết quả sau: Mệnh đề 2.15. Tất cả hàm tọa độ của hàm vòng SPN khi sử dụng các hộp thế có độ dư thừa tuyến tính hoàn toàn đều thuộc cùng một lớp tương đương affine. Hơn nữa, tổ hợp tuyến tính của chúng cũng cùng thuộc một lớp tương đương affine đó. Tiếp theo, chúng ta sẽ xem xét trường hợp S-hộp chỉ sở hữu một số cặp hàm Bool thành phần là tương đương affine. Ta có thuật toán xác định 3. Như vậy, luận án đã chỉ ra sự ảnh hưởng của độ dư thừa tuyến tính của S-hộp lên tính tương đương affine của các hàm tọa độ đầu ra của hàm vòng của các mã pháp dạng SPN. Với việc sử dụng các hộp thế có độ dư thừa hoàn toàn sẽ khiến cho các hàm Bool tọa độ đầu ra cũng như tổ hợp tuyến tính của chúng đều thuộc cùng một lớp tương đương affine. Còn trong trường hợp các hộp thế có độ dư thừa tuyến tính với số lượng lớn các hàm thành phần tương đương affine thì khả năng cao chúng ta sẽ 12 chỉ ra tồn tại và xác định được hàm tọa độ đầu ra tương đương affine. Do đó, khi xây dựng một mã pháp an toàn người thiết kế nên quan tâm đến độ dư thừa tuyến tính và có thể xem xét nó như là một tiêu chí cho việc sinh các hộp thế có tính chất mật mã tốt. Thuật toán 3: Kiểm tra tính tương đương affine của hai hàm tọa độ trong hàm vòng SPN Đầu vào: Chỉ số t, t’ của hai hàm tọa độ với , ' 1,...,t t m . Đầu ra: Trả về 1 khi tương đương cùng với tập D = {D1, ... , Dk, a = {a1,...,ak}, b = {b1,...,bk}, c}; ngược lại trả về 0 khi không tương đương. Các bước của thuật toán: 1. , , , 0   D a b c 2. For i=1 to k do 2.1. If (checkafffine(  / 1,Tr       t t n ih S X ,  ' '/ 1,Tr       t t n ih S X )) 2.1.1. Di  Dtemp; ai  atemp; bi  btemp; ci  cctemp; ( Dtemp, atemp, btemp, ctemp đầu ra của thuật toán 1 với đầu vào là hai hàm Bool  / 1,Tr       t t n ih S X ,  ' '/ 1,Tr       t t n ih S X ) else Return 0 3. Return 1 2.3.4 Kết quả mở rộng cho việc phân loại các S-hộp 4 bit bất kỳ Mệnh đề 2.16. 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 i∈   2 | 0, 1 0  j j n . Dựa vào kết quả 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  2 | 0, 1  ji j n . Tiếp theo, để giảm chi phí tính toán cho việc xác định các phần tử trong một lớp, ta xem xét một kết quả lý thuyết sau: Mệnh đề 2.17. Cho A và B là hai nhóm con của nhóm G và g∈G. Khi đó tập 13  :    C c B g c A g (2.26) là nhóm con của B và ta có đẳng thức sau:   # ## #     A BA g B C . Để chứng minh mệnh đề này, ta sẽ chứng minh hai Bổ đề sau: Bổ đề 2.11. Tập C cho bởi (2.26) là nhóm con của nhóm B. Bổ đề 2.12. Cho A và B là hai nhóm con của nhóm G và nhóm C được xác định theo (2.26) . Khi đó ∀g∈G và ∀ b, b’ ∈ B, ta có:    '    A g b A g b khi và chỉ khi ' b b C . Từ Mệnh đề 2.9, ta có hệ quả sau: Hệ quả 2.7. Cho A và B là hai nhóm con của nhóm G, C là nhóm con được xác định trong (2.26) 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, luận án đưa ra một số thuật toán xác định 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, cùng một số đánh giá độ phức tạp và thực hành. Luận án đã thực hành và xác định được các đại diện của 302 lớp tương đương affine cùng số lượng các phần tử trong mỗi lớp của các S-hộp 4 bit. 2.4. Kết luận của chương 2 Trong chương này, luận án đã tập trung xem xét các S-hộp 4 bit. Cụ thể:  Về mặt lý thuyết, ngoài việc phân tích chi tiết một số kết quả đã có, luận án đã nghiên cứu đánh giá về mặt lý thuyết các tích chất mật mã quan trọng của S-hộp như bậc tuyến tính, đặc trưng lượng sai, đặc trưng đại số (Mệnh đề 2.10, Mệnh đề 2.11, Mệnh đề 2.12), bậc trong suốt (Mệnh đề 2.13), độ dư thừa tuyến tính (Mệnh đề 2.14). Ngoài ra, luận án cũng đã phân tích sự ảnh hưởng của độ dư thừa tuyến tính của S-hộp lên tính tương đương affine của các hàm đầu 14 ra của hàm vòng SPN đảm bảo độ an toàn dự phòng cho các mã khối được thiết kế (Mệnh đề 2.15, Thuật toán 3). Hơn nữa, luận án đã chứng minh một số kết quả lý thuyết mới đảm bảo cho việc thực hiện phân lớp được toàn bộ các S-hộp 4 bit theo quan hệ tương đương affine (Mệnh đề 2.16, Mệnh đề 2.17).  Về mặt thực hành, luận án đã xây dựng được đầy đủ các S-hộp trong 16 lớp tối ưu cũng như trong một lớp bất kì bằng các thuật toán đề xuất (Thuật toán 4, Thuật toán 5, Thuật toán 6). Ngoài ra, cũng đã thực hành việc khảo sát bậc trong suốt của các S-hộp 4 bit dạng Serpent. Các kết quả nhận được cho phép người thiết kế chủ động lựa chọn các S-hộp 4 bit phù hợp với thiết bị mà mình hướng tới. Cụ thể, nếu thiết bị có tài nguyên rất hạn chế, đòi hỏi các thuật toán mã khối siêu nhẹ (ultralightweight block cipher), thì khi đó người thiết kế có thể sử dụng các S-hộp tối ưu có tính chất cuộn vì sẽ giảm được chi phí cài đặt; còn khi thiết bị hạn chế nhưng vẫn đủ chi phí cài đặt cho phép chúng ta tăng cường độ an toàn thì khi đó ta cần phải xem xét thêm các tính chất mật mã đối với các lớp S-hộp 4 bit tối ưu nhằm tăng cường độ an toàn của thuật toán như tính Serpent, bậc trong suốt, độ dư thừa tuyến tính. Người thiết kế cần cân nhắc lựa chọn các S-hộp 4 bit phù hợp với thiết kế của mình nhằm đạt được sự tối ưu giữa chi phí cài đặt, độ an toàn và hiệu quả thực thi. Hơn nữa, với sự phát triển không ngừng của khoa học thám mã đòi hỏi người thiết kế luôn luôn phải xem xét cập nhật các tiêu chí cho S-hộp 4 bit đảm bảo cho mã khối hạng nhẹ được thiết kế có đủ độ an toàn đối với nhu cầu người sử dụng. 15 CHƯƠNG 3 NGHIÊN CỨU XÂY DỰNG TẦNG TUYẾN TÍNH CHO MÃ KHỐI HẠNG NHẸ 3.1. Cơ sở xây dựng tầng tuyến tính trong mã khối hạng nhẹ Phần này sẽ xem xét một số khái niệm và kí hiệu liên quan tới tầng tuyến tính. Những khái niệm này là cơ sở cho việc nghiên cứu và lựa chọn các phép biến đổi tuyến tính cụ thể nhằm hướng một tầng tuyến tính an toàn và hiệu quả cho một thuật toán mã khối hạng nhẹ. 3.2. Mô hình tầng tuyến tính hạng nhẹ dạng AES Các mã pháp sử dụng cấu trúc SPN dạng AES là các mã pháp có các phép toán xử lý định hướng theo khối bit (cụ thể trong trường hợp 64 bit là các “mẩu” (nibble) có kích thước là 4 bit, mà ta gọi là cell) gồm các phép biến đổi AddRoundKey, SubCells, ShiftRows, MixColumns. Tầng khuếch tán đề xuất sẽ bao gồm hai biến đổi chính, đó là biến đổi chuyển vị các ô nhớ, ký hiệu là TranCells, biến đổi này được minh họa như hình 3.2 (Tranposition là chuyển vị, một dạng đặc biệt của hoán vị) và biến đổi MixColumns, cái mà được xây dựng trực tiếp trên cơ sở ma trận MDS 44 trên 42 . Hình 3.2: Biến đổi TranCells lên khối dữ liệu 64 bit 16 Độ an toàn chống thám mã lượng sai và tuyến tính của mã pháp dạng AES sử dụng mô hình đề xuất được đánh giá dựa trên các kết quả lý thuyết sau: Mệnh đề 3.1. Số lượng các cell chủ động của hai vòng mã liên tiếp nhau bị chặn dưới bởi 5Q, trong đó Q là số lượng các cột chủ động ở đầu vào của vòng thứ 2. Bổ đề 3.1. Trong hai vòng mã liên tiếp, tổng số cột chủ động ở đầu vào và đầu ra không nhỏ hơn 5. Nói một cách khác    0 2 5 col colW a W a . Mệnh đề 3.2. Bốn vòng mã liên tiếp bất kỳ có số cell chủ động nhỏ nhất bằng 25. a) b) Hình 3.3: Mô tả sự thay đổi các byte dưới tác động của tầng khuếch tán trong AES(a) và mô hình đề xuất (b) Về điểm bất động của mô hình tầng tuyến tính đề xuất, ta có đánh giá sau: Nhận xét 3.1. Phép biến đổi TranCells (cũng như ShiftRows) không ảnh hưởng đến số lượng điểm bất động của của tầng khuếch tán mà nó tham gia vào. 17 Nhận xét 3.2. Nếu biến đổi tuyến tính có ma trận biểu diễn M có N điểm bất động thì biến đổi MixColumns có số điểm bất động là N4 cũng chính là số lượng điểm bất động của tầng khuếch tán. Trong phần tiếp, luận án cũng đã phân tích một số lợi thế về cài đặt của cấu trúc này trên các nền tảng 32 bit và 64 bit. 3.3. Xây dựng ma trận MDS cho tầng tuyến tính của mã khối hạng nhẹ dạng AES Trong phần trước, ta đang xét xét mô hình tầng tuyến tính cho mã khối hạng nhẹ có kích thước 64 bit dạng AES với phép MixColumns là một biến đổi tuyến tính từ không gian 4 44 42 2  thực hiện biến đổi một véc tơ cột biểu diễn trạng thái có dạng (x3,x2,x1,x0)T thành véc tơ cột biểu diễn trạng thái tiếp theo bằng cách nhân véc tơ này với một ma trận A (là ma trận biển diễn của phép biến đổi tuyến tính có kích thước 4×4 trên trường 42 ). Do đó, trong phần này trọng tâm sẽ hướng tới việc xem xét và chọn lựa các ma trận MDS có kích thước 4 4 trên trường 42 . Những ma trận này là phù hợp cho phép biến đổi MixColumns đối với mô hình tầng tuyến tính này dựa trên một số chiến lược xây dựng các ma trận MDS cho mã khối hạng nhẹ như sau: Ma trận dùng cho phép biến đổi MixColumns Các tiêu chi lựa chọn  Số nhánh  Số điểm bất động  Khả năng cài đặt Xây dựng ma trận MDS 4x4 trên có dạng dịch vòng.42 Xây dựng ma trận MDS 4x4 trên có dạng đồng hành.42 Xây dựng ma trận MDS 4x4 trên có dạng Hadamard.42 Hình 3.7: Định hướng xây dựng các ma trận MDS. Để có một độ đo cho hiệu quả cài đặt phần cứng của phép biến đổi đang xét, luận án sử dụng khái niệm số cổng XOR mà ta sẽ sử dụng 18 như một độ đo để đánh giá tính “nhẹ” của một ma trận cho trước và là cơ sở cho việc lựa chọn các ma trận MDS phù hợp. 3.3.1. Xây dựng các ma trận MDS dựa trên các ma trận đồng hành Ma trận 0 1 1 0 1 0 0 ... 0 0 0 1 0 ... 0 0 0 0 0 ... 1 ... ... ...                        dz z z được gọi là ma trận đồng hành (companion matrix) của đa thức 2 1 0 1 2 1...       d d dz z x z x z x x và kí hiệu là Serial(z0,z1,,zd-1). Bảng 3.3: Liệt kê và đánh giá các ma trận Serial(z1,z2,z3,z4) có lũy thừa bậc 4 là ma trận MDS trên 42 Lớp Lớp con Tổng XOR Số xung nhịp Số điểm bất động Số lượng Lớp Lớp con Tổng XOR Số xung nhịp Số điểm bất động Số lượng 1 1 31 3 1 2 4 19 1 49 4 1 180 186 2 31 4 1 2 2 49 4 16 5 2 1 32 3 16 2 5 3 48 4 32 1 2 32 4 1 1 20 1 50 4 1 251 265 3 32 4 16 2 2 50 4 16 14 15 1 45 4 1 66 68 33 1 63 4 1 8 8 2 45 4 16 2 34 1 64 4 1 2 2 16 1 46 4 1 115 125 35 1 65 4 1 2 2 2 46 4 16 10 36 1 66 4 1 4 4 Đối với trường hợp mà luận án xem xét, ta có thể tiến hành tìm kiếm toàn bộ các ma trận đồng hành thỏa mãn lũy thừa bậc 4 của nó là những ma trận MDS trên trường 42 với đa thức khả quy là 19   4 1  f x x x thì có tất cả 3.660 ma trận thỏa mãn. Dễ thấy, việc cài đặt ma trận MDS nhận được khi lũy thừa các ma trận đồng hành không phụ thuộc vào các phần tử của ma trận này vì đơn giản nó có thể được cài đặt truy hồi qua ma trận đồng hành. Cho nên khi lựa chọn ta chỉ cần quan tâm đến các hệ số trong ma trận đồng hành. Từ việc đánh giá các cổng XOR cài đặt cho các phép toán nhân được thực hiện, tất cả 3.660 ma trận đồng hành tìm được được thống kê trong bảng 3.3 dựa trên tiêu chí về điểm bất động, số lượng các cổng XOR và số xung nhịp trong cài đặt các phép toán thực hiện ma trận. Luận án cũng đã xem xét ma trận có cài đặt và các tham số mật mã tốt nhất tìm được là Serial(2,1,1,4). 3.3.2. Xây dựng các ma trận MDS dựa trên ma trận Hadamard Ma trận Hadamard được định nghĩa như sau: Định nghĩa 3.3. Một ma trận Hadamard trường hữu hạn là một ma trận kk với k=2s có thể được biểu diễn bởi hai ma trận con H1 và H2 mà chúng cũng là ma trận Hadamard như sau: 1 2 2 1        H H H H H Mệnh đề 3.3. Tầng khuếch tán gồm 2 biến đổi TranCells và MixColumns, trong đó biến đổi MixColumns sử dụng ma trận Hadamard MDS cuộn kích thước 44 trên trường 42 , có số điểm bất động là 2 32. Để xem xét phân loại các ma trận Hadamard, ta có xem xét một quan hệ tương đương sau: Định nghĩa 3.4. Cho hai ma trận Hadamard kích cỡ kk là H=had(h0,h1,,hk-1) và H’=had( ' ' '0 1 1, ,..., kh h h ), hai ma trận này được gọi là có quan hệ tương đương khi tồn tại một hoán vị k phần tử  sao cho   ' i ih h . Kí hiệu, HH’. 20 Nhận xét 3.3. Cho hai ma trận Hadamard tương đương H  H’. Khi đó, hai ma trận H, H’ có cùng tính cuộn, cùng số nhánh, cùng số điểm bất động, cùng số cổng XOR cài đặt. Như vậy, dựa trên tính chất này, ta có thể giảm được độ phức tạp khi xem xét số lượng các ma trận Hadamard bằng cách chỉ xem xét các phần tử đại diện (có xét thứ tự) trong mỗi lớp tương đương hoán vị vì trong mỗi lớp các phần tử đều có cùng tính chất mật mã và cài đặt. Bảng 3.3 là kết quả phân lớp theo thứ tự tăng dần theo số cổng XOR cần thiết khi cài đặt phần cứng của toàn bộ các ma trận Hadamard MDS 44 này, trong đó “+” – là ký hiệu các ma trận có tính cuộn còn “-” – là không có tính cuộn. Như vậy, trong số 22680 ma trận Hadamard MDS cuộn Had(1,4,9,13) là đại diện của lớp 1 trong bảng 3.4 có cài đặt tốt nhất với các tính chất mật mã cần thiết. Bảng 3.4: Liệt kê và đánh giá các ma trận Hadamard MDS 44 trên Lớp Tổng XOR Tính cuộn Số điểm bất động Số lượng theo lớp Lớp Tổng XOR Tính cuộn Số điểm bất động Số lượng theo lớp 1 17 + 232 24 11 40 - 1 144 2 18 + 232 24 12 41 - 1 192 3 20 + 232 24 13 42 - 1 192 4 21 + 232 96 14 43 - 1 240 5 22 + 232 192 15 44 - 1 480 6 23 + 232 120 16 45 - 1 816 7 24 + 232 120 17 46 - 1 1104 8 [2531] + 232 912 18 47 - 1 1104 9 37 - 1 48 19 48 - 1 1728 10 38 - 1 96 20 [4964] - 1 15024 Tổng số: 22680 Ma trận Hadamard MDS cuộn Had(1,4,9,13) tốt nhất được đánh giá và phân tích. 42  21 3.3.4. Xây dựng các ma trận MDS dựa trên các ma trận vòng Ma trận dịch vòng được định nghĩa như sau: Định nghĩa 3.5. Ma trận d có dạng: 0 1 1 1 0 2 1 2 0                       d d d a a a a a a a a a được gọi là ma trận dịch vòng và kí hiệu là Circ(a0,..., ad-1) với 2 nia  . Bảng 3.5: Liệt kê và đánh giá các ma trận MDS dịch vòng 44 trên STT Tổng XOR Số xung nhịp Số điểm bất động Số lượng theo lớp STT Tổng XOR Số xung nhịp Số điểm bất động Số lượng theo lớp 1 15 3 1 8 16 21 3 1 8 2 4 8 17 4 1 840 3 16 3 1 16 18 24 40 4 24 8 19 22 4 (1,24) (1128,40) 5 17 3 1 40 20 23 4 (1,24) (1392,120) 6 4 56 21 24 4 (1,24) (1592,104) 7 24 16 22 25 4 (1,24) (1760,160) 8 18 3 1 8 23 26 4 (1,24) (1640,160) 9 4 24 24 24 27 4 (1,24) (1672,128) 10 4 1 160 25 28 4 (1,24) (1408,48) 11 19 3 1 24 26 29 4 (1,24) (1184,80) 12 4 296 27 30 4 (1,24) (816,24) 13 24 32 28 31 4 (1,24) (520,72) 14 20 4 1 560 29 32 4 1 232 15 24 32 30 33 4 (1,24) (72,8) 31 34 4 24 16 Tổng số: 16560 42  22 Tương tự như ma trận Hadamard, các ma trận dịch vòng này cũng có quan hệ tương đương như sau: Định nghĩa 3.6. Cho hai ma trận dịch vòng kích cỡ kk là C=Circ(c0,c1, ,ck-1) và C’=Circ( ' ' '0 1 1, ,..., kc c c ), hai ma trận này được gọi là có quan hệ tương