Đề xuất phương pháp cài đặt hiệu quả cho tầng tuyến tính kích thước lớn trong mã khối - Trần Hồng Thái

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 149 ĐỀ XUẤT PHƯƠNG PHÁP CÀI ĐẶT HIỆU QUẢ CHO TẦNG TUYẾN TÍNH KÍCH THƯỚC LỚN TRONG MÃ KHỐI Trần Hồng Thái*, Phạm Đình Trọng Tóm tắt: Bài báo trình bày một phương pháp cài đặt hiệu quả cho tầng tuyến tính có kích thước lớn. Đặc biệt, đối với tầng tuyến tính kích thước lớn phương pháp đề xuất cho phép giữ nguyên số phép toán cơ sở, nhưng bộ nhớ giảm một nửa so với cách tiếp cận tra bảng thường được áp dụng trong các mã pháp SPN hiện đại. Cách tiếp cận trong bài báo là sử dụng kỹ thuật tra bảng khi khai thác các tính chất của ma trận tuyến tính truy hồi, ma trận Hadamard và ma trận dịch vòng. Từ khóa: Tầng tuyến tính, Ma trận MDS, Cài đặt hiệu quả, Mã pháp SPN. 1. GIỚI THIỆU Trong mật mã ứng dụng, các mã khối ngoài việc phải đảm bảo độ an toàn cần phải có tính chất mềm dẻo trong cài đặt trên các platform khác nhau. Hiện nay, cài đặt thường được áp dụng đối với các mã khối hiện đại khi kết hợp đồng thời cả hai phép tuyến tính và phi tuyến như AES [2, 5], GOST R 34.12-2015 [7], LED [3], ... là cách sử dụng bảng tra được tính trước. Nếu như trong AES sử dụng tầng tuyến tính với ma trận MDS kích thước 4×4, thì kích thước bảng tra yêu cầu là 8 KB [2, 5], còn trong GOST R 34.11-2012 là 128 KB đối với ma trận kích thước 16×16 [6, 8]. Đối với hai mã pháp trên, với kích thước khối là 128 bit, số phép truy cập bộ nhớ là 16 và số phép XOR các số 32 bit (cho AES) hoặc 64 bit (cho GOST R 34.12-2015) tương ứng là 16 và 32. Qua đó, có thể thấy rằng khi kích thước tầng tuyến tính tăng lên nhằm đảm bảo độ an toàn cần thiết thì độ phức tạp tính toán và đặc biệt là độ phức tạp bộ nhớ tăng lên đáng kể. Điều này trở thành vấn đề tác động lên tính mềm dẻo khi cài đặt các mã pháp trong các môi trường với năng lực tính toán và tài nguyên khác nhau. Những năm gần đây, nhằm đạt được các lợi thế trong cài đặt chủ yếu là trong phần cứng, có nhiều công trình tập trung nghiên cứu xây dựng các tầng tuyến tính truy hồi [1]. Theo đó, ma trận tuyến tính của chúng là lũy thừa của một ma trận đồng hành có dạng đơn giản và dễ dàng cài đặt phần cứng. Trong [8], nhóm tác giả đã đề xuất và đưa ra một loạt các phương pháp khai thác tính truy hồi đối với ma trận tuyến tính trong mã pháp Kuznyechik của nhóm tác giả Cơ quan FSB, Liên bang Nga đề xuất. Đã có một số lượng lớn các nghiên cứu tập trung lên việc sinh các ma trận truy hồi kích thước nhỏ, thường là 4×4, có lợi thế trong cài đặt phần cứng [11, 12, 13, 14]. Tuy nhiên, cài đặt phần mềm khi khai thác tính truy hồi của những ma trận này dường như chưa được quan tâm nhiều, đặc biệt là theo khía cạnh sử dụng các bảng tra được tính trước. Ở một hướng nghiên cứu khác liên quan đến xây dựng tầng tuyến tính sử dụng các ma trận MDS có dạng đặc biệt như các ma trận dịch vòng [15], ma trận Hadamard [16, 17]. Các ma trận này tuy không có tính truy hồi nhưng chúng lại có đặc điểm là tập các phần tử ở mỗi hàng hoặc mỗi cột trong ma trận tuyến tính là giống nhau mặc dù thứ tự của chúng là khác nhau. Trong cài đặt phần cứng tính chất này được khai thác một cách triệt để, còn trong cài đặt phần mềm sử dụng kỹ thuật tra bảng chủ yếu áp dụng cho những ma trận kích thước nhỏ, cỡ 4×4, hoặc 8×8. Khi kích thước ma trận tuyến tính tăng lên, sẽ phát sinh các vấn đề liên quan đến bộ nhớ cần lưu những bảng tra đã được tính trước. Điều này dường như là một điểm hạn chế khi cài đặt các ma trận lớn trong môi trường có năng lực tính toán hạn chế. Trên cơ sở khai thác tính chất các tầng tuyến tính truy hồi, các tầng tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng, trong bài báo này chúng tôi sẽ khảo sát một số đặc điểm của chúng và sau đó đề xuất phương pháp cài đặt hiệu quả tổng quát cho các tầng tuyến tính kích thước lớn dạng này. Công nghệ thông tin & Cơ sở toán học cho tin học T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả trong mã khối.” 150 Đóng góp của chúng tôi: Đề xuất phương pháp cài đặt hiệu quả tổng quát cho các tầng tuyến tính truy hồi kích thước lớn, trong đó tầng tuyến tính được xây dựng sử dụng các ma trận truy hồi, Hadamard hoặc dịch vòng. Bố cục các phần còn lại của bài báo như sau: Mục 2 trình bày về tầng tuyến tính truy hồi, tầng tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng. Mục 3 trình bày lại cách sử dụng bảng tra để cài đặt cho các tầng tuyến tính với biểu diễn thông qua một ma trận tuyến tính trên trường hữu hạn. Đề xuất phương pháp cài đặt hiệu quả tầng tuyến tính truy hồi và tầng tuyến tính sử dụng ma trận Hadamard hoặc dịch vòng sẽ được đưa ra ở mục 4 của. Cuối cùng là một số kết luận và danh mục tài liệu tham khảo. 2. MỘT SỐ CHIẾN LƯỢC THIẾT KẾ TẦNG TUYẾN TÍNH CHO THUẬT TOÁN MÃ KHỐI 2.1. Tầng tuyến tính truy hồi dựa trên ma trận đồng hành Trong ngữ cảnh của bài báo đề này, chúng tôi xem xét tầng tuyến tính nhận được từ một ma trận tuyến tính M kích thước m×m trên trường hữu hạn GF(2n) và m chẵn. Tính truy hồi của nó được thể hiện ở việc là ma trận M được xác định bằng lũy thừa bậc m của một ma trận đồng hành A kích thước m×m có dạng sau: 0 1 2 1 0 0 0 1 0 0 0 1 0 0 0 1 m a a A a a                           ,  2 , 0 1nia GF i m    (1) Biểu diễn của tầng tuyến tính trong bài báo này ký hiệu là : mn mnL V V , được quy định là phép nhân bên phải véc tơ hàng X với ma trận M, đầu ra là véc tơ hàng Y: ((( (( ) ) ... ) ) )m m Y X M X A X A A A A A            , (2) trong đó:  0 1 1, ,..., mY y y y  ,  0 1 1, ,..., mX x x x  ,  , 2ni ix y GF . 2.2. Tầng tuyến tính sử dụng ma trận Hadamard Với lợi thế trong cài đặt, các ma trận Hadamard có thể được sử dụng thiết kế tầng tuyến tính của các nguyên thủy mật mã. Trong mục này, chúng tôi sẽ giới thiệu ngắn gọn về dạng ma trận này. Ma trận Hadamard kích thước m×m là ma trận có dạng 1 2 2 1 H H H H H        , trong đó, các ma trận 1H và 2H là các ma trận con vuông kích thước 2 2 m m  . Ví dụ với các ma trận: 0 1 2 3 1 2 1 0 3 2 , a a a a H H a a a a              , có ma trận Hadamard 4×4 như sau: 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0 a a a a a a a a H a a a a a a a a             . 2.3. Tầng tuyến tính sử dụng ma trận dịch vòng Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 151 Ma trận dịch vòng (circulant matrix) là ma trận nhận được bằng cách dịch vòng đi 1 một phần tử ở mỗi hàng hoặc mỗi cột. Ví dụ một ma trận dịch vòng kích thước 4×4 có dạng sau: 0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0 a a a a a a a a C a a a a a a a a             . Thấy rằng, ở hai ma trận dạng này số phần tử ở mỗi hàng hoặc mỗi cột của chúng là như nhau. Đây là một tích chất mà được khai thác trong các cài đặt phần cứng cũng như phần mềm đối với những tầng tuyến tính sử dụng dạng ma trận này. 3. CÀI ĐẶT TẦNG TUYẾN TÍNH SỬ DỤNG CÁC BẢNG TRA Trong mục này, chúng tôi trình bày cách cài đặt tầng tuyến tính sử dụng kỹ thuật tra bảng. Tầng tuyến tính ký hiệu bởi ánh xạ tuyến tính L, được biểu diễn dưới dạng phép nhân bên phải một véc tơ hàng X với ma trận M trên GF(2n). Khi đó, biến đổi tuyến tính : mn mnL V V có thể biểu diễn dưới dạng:     0,0 0,1 0, 1 1,0 1,1 1, 1 0 1 1 1,0 1,1 1, 1 , ,..., m m m m m m m b b b b b b L X X M x x x b b b                               . (3) trong đó:  ,, 2 , , 0,1,..., 1ni i jx b GF i j m   . Xét biến đổi tuyến tính * : , 0, 1i n mnL V V i m   : * ,0 ,1 , 1: || || ... ||n i i i i mx V L x b x b x b       , (4) trong đó, phép || là phép ghép nối hai véc tơ. Từ (3) và (4) ta có * * * 0 0 1 1 1 1 0 0,0 0 0,1 0 0, 1 1 1,0 1 1,1 1 1, 1 1 1,0 1 1,1 1 1, 1 ( ) ( ) ( ) ... ( ) || || ... || || || ... || = || || ... || m m m m m m m m m m m Y L X L x L x L x x b x b x b x b x b x b x b x b x b                               Như vậy, ánh xạ : mn mnL V V có thể biểu diễn thông qua m ánh xạ tuyến tính * * 0 1,..., mL L  , mỗi ánh xạ iL có thể tính thông qua một bảng tra gồm 2 n dòng, mỗi dòng kích thước mn bit, các bảng tra này được sắp xếp theo thứ tự tăng dần như sau:                         ,0 ,1 , 1 ,0 ,1 , 1 ,0 ,1 , 1 ,0 ,1 , 1 0 || 0 || || 0 1 || 1 || || 1 || || || 2 1 || 2 1 || || 2 1 i i i m i i i m i i i m n n n i i i m b b b b b b b r b r b r b b b                            , Công nghệ thông tin & Cơ sở toán học cho tin học T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả trong mã khối.” 152 trong đó, phép nhân  ,0ib r được thực hiện trong GF(2 n), ở đây r là một phần tử của trường GF(2n). Như vậy, dòng thứ r của bảng này được xác định bởi          * ,0 ,1 , 1|| || ... || , 2 , 0,1,..., 1ni i i i mL r b r b r b r r GF i m        . Quá trình này cũng được thực hiện tương tự đối với biến đổi tuyến tính 1 : mn mnL V V   , nhưng khi đó sử dụng ma trận M-1. Ở đây, chúng tôi không trình bày cụ thể quá trình này. Như vậy, để cài đặt : mn mnL V V cần m phép truy cập bộ nhớ lưu m bảng tra và m phép XOR các từ mn bit. Cách sử dụng bảng tra này còn có thể áp dụng để kết hợp đồng thời hai phép biến đổi phi tuyến và tuyến tính cho các mã pháp dạng SPN, như trong AES [5], GOST R 34.12- 2015 [6], .... Theo đó, số lượng bảng tra cần lập ở đây là m bảng, với tổng kích thước bộ nhớ yêu cầu là m2×n×2n bit. Chi tiết cài đặt cho từng giá trị của m, n có thể tham khảo trong [2, 5, 6, 8]. Ví dụ với m = 32, n = 8 (áp dụng cho mã pháp SPN có kích thước khối m×n = 256 bit), bộ nhớ yêu cầu là 322×8×28 bit = 256 KB. Nếu áp dụng cho cả quá trình giải mã thì bộ nhớ cần phải tăng gấp 2 lần. Trong ví dụ này nếu xét đến năng lực tính toán của các máy tính thông dụng thì mỗi bảng tra không thể lưu bởi các số 256 bit. Do vậy, thay vì phải lập 32 bảng tra, chúng ta cần lập 32×4 = 96 bảng tra, các phần tử trong mỗi bảng là các số 64 bit (64 bit là thanh ghi của các máy tính thông dụng hiện nay). Với việc tăng số lượng bảng phụ thuộc vào năng lực tính toán thực tế như vậy sẽ làm tăng số phép truy cập bộ nhớ, và số phép XOR các số 64 bit sẽ tăng lên rất nhiều, ít nhiều chúng sẽ ảnh hưởng đến tốc độ thực thi. Rõ ràng đây là một vấn đề cần tối ưu hóa trong cài đặt đối với các tầng tuyến tính kích thước lớn. Trong phần tiếp theo, chúng tôi sẽ đề xuất một số cách tiếp cận đối với dạng cụ thể của ma trận M để từ đó có thể giảm số lượng các bảng tra nói trên. 4. MỘT CÁCH CÀI ĐẶT MỚI CHO TẦNG TUYẾN TÍNH SỬ DỤNG KỸ THUẬT TRA BẢNG 4.1. Đối với tầng tuyến tính truy hồi Đối với tầng tuyến tính (2) thay vì lập bảng tra cho ma trận M = Am, chúng tôi đề xuất phương pháp cài đặt khi lập bảng tra trước cho ma trận Am/2. Để đơn giản và trực quan hơn, chúng tôi xét trường hợp tầng tuyến tính kích thước nhỏ, với m = 4, và n = 4. Khi đó, xét ma trận đồng hành có dạng sau: 0 1 2 3 0 0 0 1 0 0 0 1 0 0 0 1 a a A a a             , với  42 ,0 3ia GF i   . (5) Khi đó: 0 0 3 0 0 3 1 0 1 3 1 0 1 32 4 2 1 2 3 2 1 2 3 2 2 3 2 3 3 2 3 0 0 0 0 , 1 0 0 1 a a a a a a a a a a a a a a A M A a a a a a a a a a a a a a a                                     , (6) Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 153 ở đây,  là một giá trị nào đó thuộc GF(24). Chúng tôi chỉ quan tâm đến sự giống nhau của hai cột cuối cùng và hai cột đầu tiên tương ứng trong hai ma trận A2 và A4. Với dạng biểu diễn như vậy, xét phép nhân bên phải véc tơ  0 1 2 3, , ,X x x x x với ma trận A 2, có           0 0 3 1 0 1 3* 2 0 1 2 3 0 1 2 3 2 1 2 3 2 3 2 3 0 2 1 3 2 0 0 1 1 2 2 3 3 2 3 0 3 0 0 1 3 1 1 2 3 2 2 3 3 0 0 0 0 , , , , , , 1 0 0 1 a a a a a a a Y y y y y X A x x x x a a a a a a a y x y x y a x a x a x a x y a a x a a a x a a a x a a x                                            (7) còn với ma trận A4, có           0 0 3 1 0 1 34 0 1 2 3 0 1 2 3 2 1 2 3 2 3 2 3 0 0 0 1 1 2 2 3 3 2 1 0 3 0 0 1 3 1 1 2 3 2 2 3 3 2 3 , , , , , , a a a a a a a Y y y y y X A x x x x a a a a a a a y a x a x a x a x y a a x a a a x a a a x a a x y y                                            (8) Từ (7) và (8) ta thấy 0 2y y  và 1 3y y  . Như vậy, đầu ra của tầng tuyến tính truy hồi có thể sử dụng ma trận A2 để tính được một nửa giá trị tọa độ của véc tơ đầu ra Y thông qua véc tơ Y  , sau đó áp dụng tiếp ma trận A2 này lên véc tơ đầu vào có tọa độ là  2 3 0 1, , ,x x y y  để nhận được một nửa giá trị các tọa độ còn lại của véc tơ Y. Trong trường hợp tổng quát, với ma trận A kích thước m×m trên trường GF(2n) nói trên, cách lập bảng tra và sử dụng bảng tra để tính các véc tơ đầu ra được mô tả như dưới đây. Có tất cả m bảng tra, ký hiệu là T0, T1, ... Tm – 1, mỗi bảng có 2 n phần tử, mỗi phần tử của bảng có kích thước bằng kích thước ghép nối (phép ||) một nửa số phần tử trên một hàng của ma trận, và bằng   / 2mn bit. Viết lại biểu thức (2) như sau:     /2 /20 1 1 0 1 1, ,..., , ,...,m m mm mY y y y X A x x x A A       . (9) Từ ma trận A có dạng (1), tính ma trận Am/2. Giả sử có dạng sau: 0, 0, 1 0, 1 1, 1, 1 1, 1/2 1, 1, 1 1, 1 0 0 0 j j m j j mm m j m j m m b b b b b b A b b b                                   , (10) trong đó:  , 2 , 0,1,..., 1, , 1, ..., 1 2 2 n i j m m b GF i m j m      . Công nghệ thông tin & Cơ sở toán học cho tin học T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả trong mã khối.” 154 Xét biến đổi tuyến tính * 2 : , 0, 1i n mnL V V i m   : * , , 1 , 1: || || ... || , / 2n i i j i j i mx V L x b x b x b j m        . (11) Từ những lập luận ở trên ta thấy khi nhân véc tơ X với ma trận A2 ta sẽ nhận được các tọa độ ở nửa đầu của véc tơ Y. Do vậy, từ công thức (9), (10), (11) ta có thể tính được nửa đầu của véc tơ Y như sau:      0 1 0 1 1 1 2 0 0, 0 0, 1 0 0, 1 1 1, 1 1, 1 1 1, 1 * * *|| || ... || || || ... || || || ... || m m j j m j j m y y y L x L x L x x b x b x b x b x b x b                            1 1, 1 1, 1 1 1, 1 , 2 || || ... ||m m j m m j m m m m j x b x b x b             . (12) Như vậy, các giá trị tọa độ 0 1 1 2 , ,..., my y y        có thể tính thông qua biểu thức (12) bởi m ánh xạ tuyến tính (11), mỗi ánh xạ tuyến tính này có thể tính thông qua một bảng gồm 2n phần tử, kích thước mỗi phần tử của bảng bằng kích thước ghép nối (phép ||) một nửa số phần tử trên một hàng của ma trận, và bằng   / 2mn bit. Các bảng tra này được tính và sắp xếp theo thứ tự tăng dần của giá trị x. Bảng tra thứ i được tính như sau:       , , 1 , 1 , , 1 , 1 , , 1 , 1 0 || 0 || || 0 || || || 2 1 || 2 1 || || 2 1 i j i j i m i j i j i m n n n i j i j i m b b b b k b k b k b b b                          , (13) trong đó  0, 1, , 2 2 nmi m j k GF    . Tương tự như vậy, để tính các tọa độ ở nửa sau của véc tơ Y ta chỉ việc áp dụng lặp lại quá trình trên khi nhân véc tơ X  với ma trận A2, các tọa độ của véc tơ này là: 1 0 1 1 1 2 2 2 , ,..., , , ,...,m m m mX x x x y y y            . Những tọa độ của véc tơ X  chính là các địa chỉ của mỗi bảng tra (13). Những phân tích ở trên chỉ ra rằng, cách tiếp cận sử dụng bảng tra để tính giá trị của tầng tuyến tính truy hồi cho phép giảm một nửa bộ nhớ khi lưu dữ liệu tính trước so với phép lập bảng cho toàn bộ ma trận như trong một số tài liệu đã đề cập [2, 5, 6, 8]. Trong khi số phép XOR như trong biểu thức (12) chỉ là cộng theo modulo 2 các số   / 2mn . Chú ý: Việc đánh giá số lượng bảng tra ở đây chỉ mang tính lý thuyết, bởi trong cài đặt thực tế, đối với tầng tuyến tính có kích thước lớn số lượng này sẽ thay đổi phụ thuộc vào năng lực lưu trữ (kích thước thanh ghi) cho phép của môi trường cài đặt và khả năng lưu trữ của trình biên dịch. Cụ thể sẽ phân tích ở bảng 1. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 155 Đối với tầng tuyến tính truy hồi dạng (2), ma trận nghịch đảo của nó cũng có dạng tương tự, do vậy cách tiếp cận ở trên có thể sử dụng để tính cho ánh xạ L-1. Ở đây, chúng tôi không trình bày chi tiết vấn đề này. 4.2. Đối với tầng tuyến tính sử dụng ma trận dịch vòng Như đã phân tích ở mục 2, các ma trận dịch vòng có tập các phần tử ở trên cùng một hàng hoặc một cột là giống nhau. Đặc điểm này sẽ được chúng tôi khai thác để đề xuất phương pháp cài đặt sử dụng kỹ thuật tra bảng. Cũng như trong mục 4.1 để đơn giản ở đây chúng tôi xét ma trận dịch vòng C kích thước 4×4 trên GF(24) như sau: 0 1 2 3 3 0 1 2 2 3 0 1 1 2 3 0 a a a a a a a a C a a a a a a a a             . (14) Khi đó, tầng tuyến tính được xác định bởi ánh xạ     16 16 0 1 2 3 3 0 1 2 0 1 2 3 0 1 2 3 2 3 0 1 1 2 3 0 : : , , , , , , L V V a a a a a a a a Y y y y y X C x x x x a a a a a a a a                  . (15) Từ đây có 0 0 1 0 2 0 3 0 3 1 0 1 1 1 2 1 0 1 2 3 2 2 3 2 0 2 1 2 1 3 2 3 3 3 0 3 || || || || || , || || || || || a x a x a x a x a x a x a x a x y y y y a x a x a x a x a x a x a x a x                                                  . (16) Thấy rằng, trong biểu thức (16) đối với công thức tính tổng XOR của 0 1||y y và 2 3||y y có các số hạng giống nhau đối với các hệ số của ma trận C, mà chỉ khác nhau ở thứ tự. Do vậy, nếu sử dụng cách lập bảng tra cho một nửa số cột của ma trận C thì ta có thể tính được toàn bộ các tọa độ đầu ra của véc tơ Y. Thật vậy, nếu lập 4 bảng tra cho ghép nối của hai cột cuối cùng của ma trận (14) như sau:                 2 3 1 2 2 3 1 20 1 4 4 4 4 2 3 1 2 0 1 3 0 0 1 3 02 3 4 4 4 4 0 1 3 0 0 || 0 0 || 0 || ||, , 2 1 || 2 1 2 1 || 2 1 0 || 0 0 || 0 || ||, 2 1 || 2 1 2 1 || 2 1 a a a a a k a k a k a kT T a a a a a a a a a k a k a k a kT T a a a a                                           (17) Công nghệ thông tin & Cơ sở toán học cho tin học T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả trong mã khối.” 156 trong đó 40 2 1k   và phép nhân được thực hiện trên GF(24). Khi đó, 0 1||y y và 2 3||y y được xác định bởi:                 0 1 2 0 3 1 0 2 1 3 2 3 0 0 1 1 2 2 3 3 || || y y T x T x T x T x y y T x T x T x T x         (18) Như vậy, trong trường hợp này ta cũng chỉ phải lập 4 bảng tra nhưng kích thước mỗi bảng tra giảm đi một nửa so với cách lập bảng tra cho toàn bộ ma trận như trong mục 3. Do đó, bộ nhớ yêu cầu giảm đi một nửa. Kết quả này cũng tương tự như kết quả so với tầng tuyến tính truy hồi trong mục 4.1. Trong trường hợp tổng quát, với ma trận A kích thước m×m trên trường GF(2n), cách lập bảng tra và sử dụng bảng tra để tính các véc tơ đầu ra được tổng quát hóa lại, theo đó, cần tất cả m bảng tra, ký hiệu là T0, T1, ... Tm – 1, mỗi bảng có 2 n phần tử, mỗi phần tử của bảng có kích thước bằng kích thước ghép nối (phép ||) một nửa số phần tử trên một hàng của ma trận, và bằng   / 2mn . 4.3. Đối với tầng tuyến tính sử dụng ma trận Hadamard Ma trận Hadamard kích thước m×m là ma trận có dạng 1 2 2 1 H H H H H        . Từ đây thấy rằng, tập các phần tử ở mỗi hàng hoặc mỗi cột của ma trận này là giống nhau. Do vậy, có thể áp dụng các tiếp cận tương tự như đối với ma trận dịch vòng để lập các bảng tra cho một nửa số cột của H. Độ phức tạp tính toán, cũng như độ phức tạp về bộ nhớ lưu trữ cũng tương tự như tầng tuyến tính sử dụng ma trận dịch vòng. 4.4. Một số nhận xét Trong mục này, chúng tôi thống kế phân tích độ phức tạp cho một số trường hợp cụ thể của tầng tuyến truy hồi và tầng tuyến tính dựa trên ma trận Hadamard (ký hiệu là ma trận H) hoặc ma trận dịch vòng (ký hiệu là ma trận C), trong đó, mỗi phần tử ở mỗi bảng sẽ lưu ở các số có độ lớn đến 64 bit (đây là kích thước thanh ghi của máy tính thông dụng). Bảng 1 dưới đây là độ phức tạp của kỹ thuật cài đặt sử dụng bảng tra cho ma trận kích thước m×m, với m = 2k trên trường hữu hạn GF(2n). Bảng 1. So sánh các tham số của hai cách cài đặt sử dụng bảng tra. TT Tham số Cách cài đặt sử dụng bảng tra Kích thước thanh ghi (bits) Kích thước bảng tra Số lượng bảng Số phép truy cập bộ nhớ Số phép XOR Kích thước của biến đổi tuyến tính 1 m = 4 n = 4 Cho ma trận M 16 128 B 4 4 4 16 bit Cho ma trận A2, một nửa số cột của H hoặc C 8 64 B 4 8 8 2 m = 4 n = 8 Cho ma trận M 32 4 KB 4 4 4 32 bit Cho ma trận A2, một nửa số cột của H hoặc C 16 2 KB 4 8 8 3 m = 8 Cho ma trận M 32 4 KB 8 8 8 32 bit Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 157 n = 4 Cho ma trận A4, một nửa số cột của H hoặc C 16 2 KB 8 16 16 4 m = 8 n = 8 Cho ma trận M 64 16 KB 8 8 8 64 bit Cho ma trận A4, một nửa số cột của H hoặc C 32 8 KB 8 16 16 5 m = 16 n = 8 Cho ma trận M 64 64 KB 32 32 32 128 bit Cho ma trận A8, một nửa số cột của H hoặc C 64 32 KB 16 32 32 6 m = 32 n = 8 Cho ma trận M 64 256 KB 128 128 128 256 bit Cho ma trận A8, một phần tư số cột của H hoặc C 64 64 KB 32 128 128 7 m = 64 n = 8 Cho ma trận M 64 1024 KB 512 512 512 512 bit Cho ma trận A8, một phần tám số cột của H hoặc C 64 128 KB 64 512 512 Trong bảng 1 thấy rằng khi kích thước tầng tuyến tính nhỏ hơn 128 bit. Khi đó, độ phức tạp của cách cài đặt sử dụng ma trận M và của phương pháp đề xuất khác nhau ở kích thước bộ nhớ cần lưu, và số lượng phép XOR của phương pháp đề xuất nhiều gấp 2 lần phương pháp cài đặt khi lập bảng tra cho ma trận M. Khi kích thước tầng tuyến tính bằng 128 bit khi đó số lượng bảng tra của phương pháp mới chỉ cần lập là 16 bảng, bằng một nửa so với 32 bảng của phương pháp sử dụng bảng tra cho ma trận M. Còn kích thước vẫn nhỏ hơn một nửa. Sự khác biệt này được giải thích như sau. Đối với phương pháp cài đặt sử dụng bảng tra cho ma trận M, theo như phân tích ở mục 3 chỉ cần lập 16 bảng, tuy nhiên, kích thước mỗi phần tử trong từng bảng bằng 128 bit. Đối với các máy tính thông thường hiện này giá trị này cần được chia thành hai số 64 bit. Do vậy, thay vì lập 16 bảng, chúng ta cần 32 bảng phụ thuộc vào kích thước thanh ghi của môi trường cài đặt phần mềm thực tế. Trong trường hợp ngược lại, phương pháp mới là chỉ lập bảng tra cho một nửa số cột của ma trận A8, hoặc một nửa số cột của ma trận H, hoặc C. Do vậy, chỉ cần 16 bảng tra cho những trường hợp này. Khi kích thước tầng tuyến tính tăng lên, ví dụ 256 và 512 bit, chúng tôi có thể sử dụng các ma trận không phài Am/2, mà tương ứng là là Am/4 = A8 và Am/8 = A8 đối với trường hợp tầng tuyến tính truy hồi. Đối với ma trận H hoặc C cũng tương tự như vậy, sẽ lập bảng tra cho 1/4 số cột hoặc 1/8 số cột của chúng. Làm như vậy để kích thước mỗi phần tử ở trong từng bảng phù hợp với kích thước thanh ghi 64 bit. Trong trường hợp này, kích thước bộ nhớ yêu cầu để lưu giảm không phải 2 lần mà tương ứng là 4 và 8 lần. Số lượng bảng cần lập cũng giảm trong ví dụ này tương ứng là 4 và 8 lần. Công nghệ thông tin & Cơ sở toán học cho tin học T. H. Thái, P. Đ. Trọng, “Đề xuất phương pháp cài đặt hiệu quả trong mã khối.” 158 5. KẾT LUẬN Trong bài báo này chúng tôi đề xuất một phương pháp cài đặt hiệu quả đối với tầng tuyến tính truy hồi, tầng tuyến tính sử dụng các ma trận Hadamard hoặc dịch vòng có kích thước lớn. Theo đó, kỹ thuật lập bảng tra khai thác tính chất truy hồi của ma trận tuyến tính, tính giống nhau ở tập các phần tử trong mỗi hàng của ma trận Hadamard hoặc dịch vòng, cho phép thực thực thi tầng tuyến tính với độ phức tạp tính toán (số phép XOR và phép truy cập bộ nhớ) không đổi so với cách cài đặt tra bảng thông thường. Tuy nhiên, phương pháp của chúng tôi cho phép giảm đáng kể bộ nhớ lưu trữ các bảng tra cần phải tính trước (bảng 1). Phương pháp này cho phép cài đặt mềm dẻo hơn các tầng tuyến tính có kích thước lớn trong các môi trường khác nhau. Hướng nghiên cứu tiếp theo của bài báo là áp dụng phương pháp cài đặt trên đối với các mã pháp thực tế sử dụng ma trận tuyến tính truy hồi để có thể đánh giá chính xác hiệu quả của nó. TÀI LIỆU THAM KHẢO [1]. Augot Daniel and Matthieu Finiasz. “Direct construction of recursive MDS diffusion layers using shortened BCH codes”. in Fast Software Encryption. 2014. Springer. [2]. Daemen, Joan, and Vincent Rijmen. “The design of Rijndael: AES-the advanced encryption standard”. Springer Science & Business Media, 2002. [3]. Guo, Jian, et al. “The LED block cipher”. Cryptographic Hardware and Embedded Systems- CHES 2011. Springer Berlin Heidelberg, 2011. 326-341. [4]. Мак-Вильямс Ф. Дж., Слоен Н. Дж. А. – “Теория кодов, исправляющих ошибки: Пер. С англ. – М.: Связь”, 1979. – 744 с., ил. [5]. Зензин О. С., Иванов М. А. “Стандарт криптографической защиты” - AES. Конечные поля. – М. : КУДИЦ-ОБРАЗ, 2002. – 176 с. [6]. Mikhail Borodin, Andrey Rybkin, Alexey Urivskiy. “HighSpeed Software Implementation of the Prospective 128-bit Block Cipher and Streebog Hash- Function”. CTCrypt 2014. pp. 189-198. [7]. GOST R 34.12–2015: “Information technology. Cryptographic data security. Block ciphers. Block Cipher”. [8]. Nikolay Borisenko, Nguyen Van Long, Alexey Bulygin. “Algorithm design software and hardware implementation of large size linear mapping”. CTCrypt 2013. pp. 192-205. [9]. Cannon John and Wieb Bosma, “Handbook of MAGMA functions”. Edition, 2006. 2: p. 4350. [10]. [11]. Kishan Chand Gupta and Indranil Ghosh Ray. “On Constructions of MDS Matrices form Companion Matrices for Lightweight Cryptography”. Security Engineering and Intelligence Informatics - Lecture Notes in Computer Science Volume 8128, 2013, pp 29-43. [12]. Sajadieh M., Dakhilalian M., Mala H., Sepehrdad P. “Recursive Diffusion Layers for Block Ciphers and Hash Functions”. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 385-401. Springer, Heidelberg (2012). [13]. G. Zeng, K. He, and W. Han. “A trinomial type of -LFSR oriented toward software implementation”. In Science in China Series F-Information Sciences, volume 50, pages 359{372. Springer-Verlag, 2007. [14]. Shengbao Wu, Mingsheng Wang, and Wenling Wu. “Recursive di usion layers for (lightweight) block ciphers and hash functions”. In Lars R. Knudsen and Huapeng Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 53, 02 - 2018 159 Wu, editors, Selected Areas in Cryptography, volume 7707 of Lecture Notes in Computer Science, pages 355{371. Springer, 2013. [15]. Chand Gupta K., Ghosh Ray I. (2014) “On Constructions of Circulant MDS Matrices for Lightweight Cryptography”. In: Huang X., Zhou J. (eds) Information Security Practice and Experience. ISPEC 2014. Lecture Notes in Computer Science, vol 8434. Springer, Cham. [16]. Youssef, A.M., Mister, S., Tavares, S.E.: “On the Design of Linear Transformations for Substitution Permutation Encryption Networks”. In: Workshop On Selected Areas in Cryptography, SAC 1997, pp. 40–48 (1997). [17]. Sajadieh, M., Dakhilalian, M., Mala, H. et al. “On construction of involutory MDS matrices from Vandermonde Matrices in GF(2q)”. Des. Codes Cryptogr. (2012) 64: 287. https://doi.org/10.1007/s10623-011-9578-x. ABSTRACT PROPOSING AN EFFICIENT IMPLEMENTATION METHOD FOR THE LARGE- SCALE LINEAR LAYER IN BLOCK CIPHERS In this paper, we propose an efficient implementation method for large-scale linear layers. Especially for large-scale linear layers, the proposed method allows to retain the underlying arithmetic operations, but memory is reduced by half compared to the table-based approach commonly used in modern SPN ciphers. The approach in the paper is to use a lookup table technique when exploiting the properties of the recursive linear matrix, the Hadamard matrix, and the circular matrix. Key words: Linear layer, MDS matrix, Efficient implementation, SPN cipher. Nhận bài ngày 25 tháng 8 năm 2017 Hoàn thiện ngày 22 tháng 9 năm 2017 Chấp nhận đăng ngày 26 tháng 02 năm 2018 Địa chỉ: Ban cơ yếu Chính phủ. *Email: thai_tranhong@gmail.com.