Đề 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

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