Tải bản đầy đủ (.pdf) (7 trang)

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

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (263.23 KB, 7 trang )

<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>

<b>VỀ CÁC S-HỘP 4</b><b>4-BIT CĨ TÍNH CHẤT MẬT MÃ MẠNH </b>
Hồng Văn Qn1*, Nguyễn Bùi Cương2


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


<b>Từ khóa:</b>Mã khối, S-hộp, Thám mã lượng sai, Thám mã tuyến tính, Hàm hầu phi tuyến hồn thiện.
<b>1. MỞ ĐẦU </b>


Đối với một lớp lớn các mã khối, các S-hộp là tổ hợp các véc tơ hàm Bool song
ánh S từ <sub>2</sub><i>n</i>vào <sub>2</sub><i>n</i>. Bài viết này tập trung vào các S-hộp 44-bit (n = 4) đã được
sử dụng cho thuật toán mã GOST 28147-89 [8] và một số mã khối khác cùng với
việc phân tích, đánh giá các tính chất mật mã mạnh. Để có thể đánh giá độ an toàn
của các S-hộp ta phải đưa ra được các tiêu chí đánh giá cụ thể, bên cạnh các tính
chất tối ưu chống lại tấn công lượng sai và tuyến tính cịn phải quan tâm tới các
tính chất khác như tính lan sai, bậc đại số,...Vì vậy, các khái niệm S-hộp mạnh đã
được đề xuất [1]. Trong bài viết này, chúng tôi bổ sung và chứng minh một số nội
dung cần thiết phục vụ cho việc tìm kiếm các S-hộp có tính chất mật mã mạnh và
sau đó là tìm kiếm các hộp thế này bằng thực hành.


<b>2. CÁC HÀM HẦU PHI TUYẾN HOÀN THIỆN YẾU </b>


<b>2.1. Khái niệm </b><b>-đều yếu và </b><i><b>l</b></i><b>-chống bất biến mạnh </b>


<i>2.1.1. Định nghĩa 1.</i> [1]Cho hàm Bool f :

<sub> </sub>

<sub>2</sub> <i>n</i>

<sub> </sub>

<sub>2</sub> <i>n</i>. Giả sử <i>f x</i>ˆ ( )<i><sub>u</sub></i> := f(x  u) 


f(x). Khi đó định nghĩa:



- Hàm f là -đều nếu |{x 

 

<sub>2</sub> <i>n</i> :<i>f x</i>ˆ ( )<i><sub>u</sub></i> = v}|  đối với mọi u

<sub> </sub>



2


<i>n</i>


  \{0} và


đối với mọi v 

 

<sub>2</sub> <i>n</i>,


- Và nó là -đều <b>yếu</b> (weakly -uniform) nếu đối với mọi u 

 

2


<i>n</i>


 \{0} chúng
ta có |Im(<i>f</i>ˆ<i><sub>u</sub></i>)|  2n-1/.


Chú ý rằng định nghĩa 1 khác với định nghĩa trong [5] (|Im( <i>f</i>ˆ<i>u</i>)|  2


<i>n</i>


/(+2) + 1).
Dễ thấy rằng nếu f là -đều thì cũng là -đều yếu. Thật vậy, nếu f là -đều thì với
mọi <i>u</i>

<sub> </sub>



2


<i>n</i>



  \{0} chúng ta có |Im(<i>f</i>ˆ<i>u</i>)|  2


<i>n</i>


</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>

|Im(<i>f</i>ˆ<i><sub>u</sub></i>)| > 2<i>n</i>-1-<i>r</i> nên số chiều của <i>W ít nhất là n – r. Đó là tính chất của f mà sẽ </i>
được cần đến trong chứng minh Định lý 4.4 [5].


<i>2.1.2. Mệnh đề 1.</i> Tính <i>-đều và </i><i>-đều yếu là một bất biến affine. </i>


<i><b>Chứng minh.</b> Mệnh đề 1 trong </i>[2] đã chứng minh rằng tính -đều là một bất
biến affine. Tương tự như vậy, bây giờ ta chứng minh rằng tính chất -đều yếu là
một bất biến affine. Đối với S-hộp S, ta đặt: 1

<sub> </sub>



, ,


<i>S</i>


<i>a b</i> <i>S a</i>


<i>n</i>  <i>b</i>


 . Giả sử S1 và S2 là hai
S-hộp tương đương affine, điều này có nghĩa là tồn tại các ma trận khả nghịch C, D


 GL(n, <sub>2</sub>), c, d 

<sub></sub>

<sub>2</sub>

<sub></sub>

<i>n</i>


 sao cho S2(x) = D(S1(Cx  c))  d với mọi x. Giả sử:
2 2

<sub> </sub>

<sub> </sub>

<sub></sub>

<sub></sub>



1 2 2



, , # 2 |


<i>S</i> <i>n</i>


<i>a b</i> <i>S</i> <i>a</i>


<i>n</i>  <i>b</i> <i>x</i> <i>S</i> <i>x</i> <i>S</i> <i>x</i> <i>a</i> <i>b</i>


      .


Có S2(x)  S2(x  a) = b tương đương với D(S1(Cx  c)  d  D(S1(C(x  a)


 c))  d = b. Đặt y = Cx  c ta có:


<i>D(S</i>1(y))  D(S1(y  Ca)) = b  S1(y)  S1(y  Ca) = D-1<i>b </i>


Như vậy, <sub>,</sub>2 1<sub>,</sub> 1
<i>S</i> <i>S</i>
<i>a b</i> <i>Ca D b</i>


<i>n</i> <i>n</i>  . Điều này có nghĩa rằng <i>b</i> Im(


1


<i>a</i>


<i>S</i> )  <i>D</i>-1<i>b</i> Im( 2


<i>Ca</i>



<i>S</i> ).
Do vậy, |Im( 1


<i>a</i>


<i>S</i> ) | = |Im( 2


<i>Ca</i>


<i>S</i> )|, và vì thế S1 và S2 đồng thời thỏa mãn tính -đều
yếu. ■


<i>2.1.3. Định nghĩa 2. </i>[1] <i>Giả sử A =</i>

 

<sub>2</sub> <i>m. Khi đó: </i>


- <i>f là l-chống bất biến (l-anti-invariant) nếu đối với không gian con bất kỳ U </i>
<i> A sao cho f(U) = U, chúng ta có dim(U) < m - l hoặc U = A. </i>


- <i>f là l-chống bất biến mạnh (strongly l-anti-invariant) nếu đối với 2 không </i>
<i>gian con bất kỳ U, W </i><i> A, sao cho f(U) = W, chúng ta có dim(U) = dim(W) </i>
<i>< m - l hoặc U = W = A. </i>


Các mã pháp dựa trên dịch chuyển (Định nghĩa 3.1 [5]) tạo nên một lớp thú vị
các mã khối lặp chẳng hạn AES. Theo Định lý 4.4 trong [5], nếu C là một mã pháp
dựa trên dịch chuyển và các S-hộp của mỗi tầng thay thế thỏa mãn tính 2<i>r</i>-đều yếu
và r-chống bất biến mạnh đối với r nào đó mà 1  r  m/2, và tồn tại một vòng với
tầng tuyến tính có tính chất tầng xáo trộn đúng cách thức (proper mixing layer)
(trong [5] đã định nghĩa chính xác của tính chất này) thì (C) (tức là nhóm được


sinh ra bởi các hàm vịng) là các nhóm ngun thủy (nhóm hốn vị G tác động trên


một tập X được gọi là nguyên thủy nếu nó tác động dịch chuyển trên X và G khơng
bảo tồn phân hoạch khơng tầm thường nào của X). Đó chính là lý do vì sao tính 
-đều yếu và l-chống bất biến mạnh được quan tâm đến. Dường như là Định lý 4.4
trong [5] yêu cầu các điều kiện quá mạnh để đảm bảo tính nguyên thủy, nhưng
thực ra nó trở nên khá tự nhiên, như được chỉ ra ở các Hệ quả 4.6 và 4.7 của [5].
Theo đó, AES, Serpent thỏa mãn các điều kiện đã nêu ra và có (Serpent) là các


</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>

-

<i>r = 1, khi đó yêu cầu mỗi S-hộp thỏa mãn tính 2-đều yếu và 1-chống bất </i>
biến mạnh;


-

<i>r = 2, khi đó yêu cầu mọi S-hộp là 4-đều yếu và 2-chống bất biến mạnh. </i>
Chúng ta quan tâm tới tính 2-đều yếu và tính 4-đều yếu. Chú ý rằng với  < ’
thì một hàm mà thỏa mãn tính -đều sẽ thỏa mãn tính ’-đều và một hàm thỏa mãn
tính -đều yếu sẽ thỏa mãn tính ’-đều yếu. Hơn nữa, chúng ta chỉ xét các S-hộp
tối ưu, có nghĩa là Diff(S) = 4 hay S có tính 4-đều và như thế nó có tính 4-đều yếu.
Vì vậy, sau đây chúng ta chỉ quan tâm đến tính 2-đều yếu.


Theo kết quả 1 trong [2], trên <sub>2</sub>4 khơng tồn tại hốn vị APN (Almost Perfect
Nonlinear – hầu phi tuyến hồn thiện) tức là khơng có các S-hộp thỏa mãn Diff(S)
= 2 (đó chính là tính 2-đều).


<i>2.1.4. Định nghĩa 3. Chúng ta nói rằng một hàm Bool là một hàm phi tuyến hầu </i>
hồn thiện yếu (weakly APN) nếu nó là 2-đều yếu.


Một số kết quả lý thuyết được nêu trong [1] về các hàm APN yếu. Mệnh đề 2
và mệnh đề 4 sau đây đưa ra 2 điều kiện đủ của một hàm Bool thỏa mãn APN yếu.
<i>2.1.5. Mệnh đề 2 (Preposition 1, </i>[1])<i>. </i>Giả sử f :

<sub> </sub>

<sub>2</sub> 4

<sub> </sub>

<sub>2</sub> 4 là một hàm Bool sao
cho f là 4-đều và là 2 – chống bất biến mạnh. Khi đó f là APN yếu.


Với f:

<sub> </sub>

<sub>2</sub> <i>n</i>

<sub> </sub>

<sub>2</sub><i>n</i> ta định nghĩa: <i>n</i>ˆ(f) =


 


2


( ) \ 0


max


<i>n</i>


<i>u</i> |{v

 

2


  <i>n</i>\{<b>0</b>}: deg( <i>f</i>ˆ<i><sub>u</sub></i>, v) = 0}|.
<i>2.1.6. Mệnh đề 3. n</i>ˆ(f) là một bất biến affine.


<i>Chứng minh: Giả sử f</i>2(x) =Af1(x) + a với A  GL(n, <sub>2</sub>), a 

 

2
<i>n</i>


 . Khi đó,


<i>f</i>2(x  u)  f2(u), (A<i>T</i>)-1<i>v</i> = (Af1(x  u)  a)  (Af1(x)  a), (A<i>T</i>)-1<i>v </i>


= <i>A(f</i>1(x  u)  f1(x)), (A<i>T</i>)-1<i>v</i> = <i>f</i>1(x  u)  f1(x), A<i>T</i>(A<i>T</i>)-1<i>v</i> = <i>f</i>1(x  u)


 f1(x), v


Vì thế, <i>v </i><sub>  </sub>


2



<i>n</i>


 \{<b>0</b>} : deg( ˆ1


<i>u</i>


<i>f</i> , <i>v</i>) = 0} = {v  <sub> </sub>
2


<i>n</i>


 \{<b>0</b>} : deg( ˆ2


<i>u</i>


<i>f</i> , <i>v</i>) = 0}
nên <i>n</i>ˆ(f1) = (f2). Giả sử f2 = f1(Bx  b) với B  GL(n, 2), b

 

2


<i>n</i>


 . Khi đó, <i>f</i>2(x 


<i>B</i>-1<i>u) </i> f2(u), v = <i>f</i>1(B(x  B-1<i>u) </i> b)  f1(Bx  b), v = <i>f</i>1(Bx  b  u)  f1(Bx


 b), v Đặt Bx  b = y thì <i>f</i>2(x  B-1<i>u) </i> f2(u), v = <i>f</i>1(y  u)  f1(y), v . Vì thế
{v <sub> </sub><sub></sub><sub>2</sub> <i>n</i><sub>\{</sub>


<b>0</b>}: deg( <sub>ˆ</sub>1



<i>u</i>


<i>f</i> , v) = 0} = {v 

<sub> </sub>

<sub>2</sub> <i>n</i>\{<b>0</b>} : deg( <sub>ˆ</sub>2


<i>u</i>


<i>f</i> , v) = 0} nên <i>n</i>ˆ(f1) =


ˆ


<i>n</i>(f2). ■


<b>2.2. Một số tính chất APN yếu của hàm Bool </b>


<i><b>Mệnh đề 4 (Preposition 2</b></i>[1]<b>)</b>. Giả sử f :

<sub> </sub>

<sub>2</sub>4

<sub> </sub>

<sub>2</sub>4 là một hàm Bool sao cho <i>n</i>ˆ(f)
= 0. Khi đó f là một APN yếu.


Mệnh đề ngược lại một phần của mệnh đề 4 đúng với mọi n  2, thật vậy:


</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>

<i><b>Định lý 1</b></i>[1]<b>.</b> Giả sử f :

<sub> </sub>

<sub>2</sub> 4

<sub> </sub>

<sub>2</sub>4 <i>là một hốn vị APN yếu. Khi đó, deg(f) = 3 và </i>
<i>n</i>3(f) {12, 14, 15}, trong đó n3(f) – là số lượng các tổ hợp tuyến tính của các hàm


<i>Bool thành phần có bậc đại số là 3. </i>


<b>3. CÁC S-HỘP 4</b><b>4-BIT MẠNH</b>


<b>3.1. Đại lượng đo độ kháng chống lại thám mã lượng sai và thám mã tuyến tính </b>


Để đo độ kháng chống lại thám mã lượng sai của một S-hộp từ <sub>2</sub><i>n</i>



vào <sub>2</sub><i>n</i>


,
người ta quan tâm đến đại lượng Diff(S) được xây dựng như sau: với a <sub>2</sub><i>n</i>


 , xét
ánh xạ <i><sub>S a</sub></i><sub>,</sub>:<sub>2</sub><i>n</i> <sub>2</sub><i>n</i>, x<i>S(x) </i> S(x  a), ta có 1


, ( ) { : , ( )= }


<i>S a</i> <i>b</i> <i>x</i> <i>S a</i> <i>x b</i>


 <sub></sub> 

Diff(S) =
 
2 2
1
,
\ 0 ,


max ( )


<i>n</i> <i>n</i> <i>S a</i>


<i>a</i> <i>b</i>


<i>b</i>

 



.


Đối với 2 vecto <i>a, b </i><sub>2</sub><i>n</i>, ký hiệu 1
0


,


<i>n</i>
<i>i i</i>
<i>i</i>


<i>a b</i> <i>a b</i>





  là tích trong của <i>a và b. Đối </i>
với hàm bool có <i>n biến f: </i><sub>2</sub><i>n</i><sub>2</sub>


và phần tử <i>a </i> <sub>2</sub><i>n</i>


chúng ta định nghĩa hệ số
Walsh của <i>f tại a bởi </i> <i>f</i>(a) =


2


( ) ,


( 1)



<i>n</i>


<i>f x</i> <i>a x</i>
<i>x</i>






. Bậc tuyến tính của <i>f được định </i>
nghĩa như là Lin(f) =


2


max ( )


<i>n</i>


<i>a</i> <i>f</i> <i>a</i>




. Với một S-hộp có kích cỡ <i>n</i><i>n, ta ký hiệu đối </i>
với vecto bất kỳ b <sub>2</sub><i>n</i> hàm thành phần (component function) S<i>b</i> tương ứng: <i>Sb</i>


:<sub>2</sub><i>n</i> <sub>2</sub>, x <i>b, S(x)</i>. Chúng ta định nghĩa bậc tuyến tính (linearity) của S như là
Lin(S) =



2, 2\{0}


max ( )


<i>n</i> <i>n</i> <i>b</i>


<i>a</i> <i>b</i>


<i>S</i> <i>a</i>


 




.


Giá trị Lin(S) và Diff(S) càng nhỏ thì tương ứng các mã pháp sử dụng các hộp
thế S này có khả năng kháng lại thám mã lượng sai và tuyến tính càng tốt. Trong
[2] đã có xem xét chi tiết về định nghĩa của một S-hộp 44-bit tối ưu (các giá trị
Lin(S) và Diff(S) đạt giá trị nhỏ nhất có thể), đó là những S-hộp song ánh thỏa mãn
điều kiện Diff(S)=4 và Lin(S)=8. Nhưng ngồi tính chất tối ưu đó, người ta cịn
quan tâm tới các tính chất khác nữa, ví dụ như có thể cho rằng sai khác đầu vào 1
bit bất kỳ gây ra sai khác đầu ra có ít nhất 2 bit (như đối với DES hoặc Serpent).
Một điều kiện như vậy có thể được sử dụng để tăng số cực tiểu các S-hộp tích cực
trong 2 vòng liên tiếp. Tính chất này được nghiên cứu thông qua các đại lượng:


 



2



1


1 ,


,


Diff max ( ) | wt( ) = wt( ) =1


<i>n</i> <i>S a</i>


<i>a</i> <i>b</i>


<i>S</i>  <i>b</i> <i>a</i> <i>b</i>


 



<b>0</b> 


, với wt(a) là trọng số Hamming của <i>a. </i>
Một S-hộp 44-bit tối ưu mà thỏa mãn điều kiện Diff1(S)=0 được gọi là một S-hộp


kiểu Serpent.


<b>3.2. Các S-hộp 44 mạnh </b>


Một yêu cầu đối với thám mã tuyến tính là xác suất của một biểu thức xấp xỉ
tuyến tính mà chỉ sử dụng 1 bit đầu vào và 1 bit đầu ra cần phải nhỏ một cách đặc
biệt. Tính chất này được nghiên cứu thông qua đại lượng Lin1(S) =





2


,


max ( ) | wt( ) wt( ) 1


<i>n</i> <i>b</i>


<i>a b</i>


<i>S</i> <i>a</i> <i>a</i> <i>b</i>




 





</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>

này chúng tôi sẽ dựa trên một quan hệ tương đương đặc biệt sau:


<i>3.2.1. Định nghĩa 4</i> ([3])<b>. </b>Hai S-hộp S1, S2 được gọi là tương đương hoán vị khi


tồn tại P0, P1 là hai ma trận hoán vị n  n và a, b 2


<i>n</i>


 sao cho: S2(x) = P1(S1(P0(x)


 a))  b <sub>2</sub><i>n</i>


<i>x</i>


  .


Trong đó, ma trận hốn vị <i>M được định nghĩa thơng qua một hốn vị </i> của n
phần tử là ma trận có các phần tử m<i>ij</i> thỏa mãn:


 


 



,


1
0


<i>i j</i>


<i>i</i> <i>j</i>
<i>m</i>


<i>i</i> <i>j</i>




 




 







nÕu


nÕu . Dễ thấy


rằng định nghĩa 4 xác định một quan hệ tương đương của tập các S-hộp. Nếu hai
S-hộp S1 và S2 là tương đương theo nghĩa ở trên chúng ta ký hiệu điều đó bởi S1 ~<i>S</i>


<i>S</i>2. Trong [3] cũng đã nghiên cứu việc phân loại các S-hộp 44-bit kiểu Serpent


thành 20 lớp theo tính tương đương hoán vị.


<i>3.2.2. Mệnh đề 5<b>.</b></i>Lin1(S) là bất biến trong một lớp tương đương kiểu Serpent.


<i>Chứng minh: Nếu S</i>1 và S2 là 2 S-hộp tương đương theo kiểu Serpent thì tồn tại


hai ma trận hốn vị <i>C, </i> <i>D </i> kích thước <i>n </i>  <i>n và </i> <i>c,</i><sub>2</sub><i>n</i> thỏa mãn:


 



2 1


<i>S</i> <i>x</i> <i>D S Cx</i><i>c</i> <i>d</i>  <i>x</i> <sub>2</sub><i>n</i>. Hệ số Walsh của hàm <i>S</i>2 tại điểm <i>a </i>



 

 

2 


2


, ,


2, <i>n</i> 1


<i>b S</i> <i>x</i> <i>a x</i>


<i>w</i>


<i>b</i> <i><sub>x</sub></i>


<i>S</i> <i>a</i> 




<sub></sub>

<sub></sub>  . Xét tích trong<i>b, S</i>2(x)<i>a, x</i> = <i>b, D(S</i>1(Cx  c))
 d  <i>a, x</i>, đặt <i>y</i><i>Cx</i><i>c</i> dẫn đến <i>x = C</i>-1 (y  c) = <i>C</i>-1<i>y </i> C-1<i>c. Khi đó, tích </i>
trong ở trên sẽ có dạng: <i>b, D(S</i>1(y))  d  <i>a, C</i>-1<i>x </i> C-1<i>c</i> = <i>b, D(S</i>1(y)) <i>a, </i>


<i>C</i>-1<i>x </i><i>b, d</i><i>a, C</i>-1<i>c</i>


Theo tính chất của tích trong của hai vecto: <i>x, Ay</i> = <i>xAT</i>, y<i>x, y </i> <sub>2</sub><i>n</i>


 , A 


GL(n, <sub>2</sub><i>n</i><sub>), ta có: </sub><sub></sub><i><sub>b, S</sub></i>



2(x) <i>a, x</i> = <i>bDT</i>, S1(y)<i>a(C</i>-1)<i>T</i>, y<i>b, d</i><i>a, C</i>
-1


<i>c</i>. Do các ma trận C, D là các ma trận khả nghịch nên khi biến x nhận một lượt
tất cả các phần tử trên khơng gian vecto <sub>2</sub><i>n</i>


thì giá trị y = Cx  c nhận một lượt tất
cả các phần tử trên khơng gian vecto <sub>2</sub><i>n</i>. Do đó, ta có hai tổng sau đây bằng nhau:


 

2 

 

1   1 1


2 2


, , , , , ,


1 1


<i>T</i>
<i>T</i>


<i>n</i> <i>n</i>


<i>b S</i> <i>x</i> <i>a x</i> <i>bD</i> <i>S</i> <i>y</i> <i>a C</i> <i>y</i> <i>b d</i> <i>a C c</i>


<i>x</i> <i>y</i>


 


   



    


 hay


 

1



2, 1, <i>T</i>


<i>T</i>


<i>w</i> <i>w</i>


<i>b</i> <i>bD</i>


<i>S</i> <i>a</i>  <i>S</i> <i>a C</i> . Nếu C, D là các ma trận hoán vị và wt(a) = wt(b) = 1 thì
cũng có wt(bD<i>T</i>) = 1, wt(a(C-1)<i>T</i>) = 1, hơn nữa khi a, b chạy khắp tập wt(a) = wt(b)
= 1 thì bD<i>T</i>, a(C-1)<i>T</i> cũng vậy. Đặt bD<i>T</i> = b’ và a(C-1)<i>T</i> = a’ ta có


Lin1(S2)=max 2,

 

| wt( ) = wt( ) = 1


<i>w</i>
<i>b</i>


<i>S</i> <i>a</i> <i>a</i> <i>b</i> = max 1, '

 

' | wt( ') = wt( ') = 1


<i>w</i>
<i>b</i>


<i>S</i> <i>a</i> <i>a</i> <i>b</i> = Lin1(S1).



Bằng cách lập trình, chúng tơi đã tính Lin1(S) cho 20 lớp S-hộp kiểu Serpent và


thấy rằng không tồn tại S-hộp kiểu Serpent sao cho Lin1(S) = 0.


</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>

Lớp <i>R</i>0 <i>R</i>1 <i>R</i>2 <i>R</i>3 <i>R</i>4 <i>R</i>5 <i>R</i>6 <i>R</i>7 <i>R</i>8 <i>R</i>9


Lin1(<i>S</i>) 4 4 8 4 4 4 4 4 4 8


Lớp <i>R</i>10 <i>R</i>11 <i>R</i>12 <i>R</i>13 <i>R</i>14 <i>R</i>15 <i>R</i>16 <i>R</i>17 <i>R</i>18 <i>R</i>19


Lin1(<i>S</i>) 8 8 8 4 4 4 4 8 4 4


Vì thế, Lin1(S) nhỏ nhất có thể đạt được là bằng 4, tức là trong số 20 lớp S-hộp


kiểu Serpent, chúng ta sẽ quan tâm hơn tới 14 lớp có tính chất này. Ngồi ra, để
kháng lại tấn cơng đại số, người ta cịn quan tâm đến các đại lượng


<i>ni</i>(S) = |{

 

2


<i>n</i>


<i>v</i>  \{<b>0</b>} : deg(<i>S, v</i>) = i}|.


Theo kết quả 4.1 [4] thì ta ln có deg(<i>S, v</i>)  3 nếu S là song ánh. Cũng theo
Mệnh đề 2.1 [4] thì deg(<i>S, v</i>) là một đại lượng bất biến theo tương đương affine,
và vì thế nó là bất biến trong một lớp các S-hộp kiểu Serpent. Chúng ta mong
muốn deg(<i>S, v</i>) lớn nên sẽ quan tâm tới n3(S), n3(S) càng lớn càng tốt. Trong [3]


đã tính đại lượng n3(S) cho 20 lớp S-hộp kiểu Serpent với kết quả là:



<i><b>Bảng 2.</b> n3(S) cho tất cả 20 lớp S-hộp kiểu Serpent. </i>


Lớp <i>R</i>0 <i>R</i>1 <i>R</i>2 <i>R</i>3 <i>R</i>4 <i>R</i>5 <i>R</i>6 <i>R</i>7 <i>R</i>8 <i>R</i>9


<i>n</i>3(<i>S</i>) 12 12 12 14 14 14 12 12 14 12
Lớp <i>R</i>10 <i>R</i>11 <i>R</i>12 <i>R</i>13 <i>R</i>14 <i>R</i>15 <i>R</i>16 <i>R</i>17 <i>R</i>18 <i>R</i>19


<i>n</i>3(<i>S</i>) 12 12 12 14 12 14 12 12 12 12


<i><b>Hệ quả 1</b></i>. Đối với S-hộp kiểu Serpent S bất kỳ, tồn tại phần tử b 4
2


 sao cho S<i>b</i> là


một hàm Bool bậc 2.


<i>3.2.3.Định nghĩa 5.</i>([1]) Chúng ta nói rằng một hoán vị Boolean f:  <sub>2</sub> 4 <sub>2</sub>4 là


một S-hộp mạnh nếu: f là APN yếu, Lin(f) = 8, Diff(f) = 4, Diff1(f) = 0, Lin1(f) =


4, n3(f)  14.


Trong định nghĩa trên, tính chất APN yếu có tính bất biến affine. Các đại lượng
Lin và Diff cũng có tính chất bất biến affine. Tính chất Diff1(f) = 0 là bất biến dưới


tương đương hoán vị. Đại lượng Lin1(f) là một đại lượng bất biến theo tương


đương hốn vị, cịn n3(f) có tính bất biến affine.


Bảng 1 cho thấy rằng 14 lớp Serpent có Lin1(f) = 4 là R0, R1, R3, R4, R5, R6, R7,



<i>R</i>8, R13, R14, R15, R16, R18 và R19. Bảng 2 ta thấy rằng các lớp Serpent có n3(f)  14


là R3, R4, R5, R8, R13 và R15. Tức là các lớp Serpent mà thỏa mãn n3(f)  14 thì cũng


thỏa mãn Lin1(f) = 4. Như vậy, trong 6 điều kiện của Định nghĩa 4, chỉ còn phải


quan tâm đến điều kiện APN yếu. Chúng tôi đã lập trình kiểm tra các tính chất của
16 lớp tối ưu sau:


<i><b>Bảng 3</b>. Một số tính chất cho 16 lớp tối ưu. </i>
Lớp wAPN deg(<i>f</i>) <i>n</i>1(<i>f</i>) <i>n</i>2(<i>f</i>) <i>n</i>3(<i>f</i>) <i>n f</i>ˆ  Lớp wAPN deg(<i>f</i>) <i>n</i>1(<i>f</i>) <i>n</i>2(<i>f</i>) <i>n</i>3(<i>f</i>) <i>n f</i>ˆ 


</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>

<i>G</i>4 + 3 0 0 15 0 <i>G</i>12 + 3 0 0 15 0
<i>G</i>5 + 3 0 0 15 0 <i>G</i>13 + 3 0 0 15 0
<i>G</i>6 + 3 0 0 15 0 <i>G</i>14 + 3 0 1 14 1
<i>G</i>7 + 3 0 0 15 0 <i>G15</i> + 3 0 1 14 1


Chú ý rằng, tất cả các đại lượng trong bảng thống kê trên đều có tính bất biến
affine (deg(f), n<i>i</i>(f) tính bất biến của tập {deg<i>f, v</i>}). Bảng trên cũng minh họa các


kết quả lý thuyết (Bổ đề 1 và định lí 1 ở trên) cho 16 lớp tương đương affine của
các S-hộp tối ưu. Từ bảng trên, ta có thể kiểm tra thấy khẳng định sau:


<b>Khẳng định 1 </b>[1]. Giả sử f:

 

2 4

 

2 4 <i>là một hoán vị Boolean sao cho Lin(f) = 8, </i>


Diff(f) = 4, n3(f)  14. Khi đó f là một APN yếu.


Rõ ràng, như đã nhắc tới ở trên, các S-hộp kiểu Serpent là các S-hộp tối ưu và
vì thế mỗi lớp S-hộp tương đương kiểu Serpent R<i>i</i> cần phải thuộc một lớp tương



đương theo affine G<i>j</i> nào đó. Trong [3] đã đưa ra kết quả rằng 20 lớp tương đương


kiểu Serpent chỉ thuộc vào 7 lớp tương đương affine, cụ thể là:


<i><b>Bảng 4.</b> Quan hệ giữa các lớp Serpent và các lớp tối ưu. </i>


Lớp tối ưu <i>G</i>0 <i>G</i>1 <i>G</i>2 <i>G</i>9 <i>G</i>10 <i>G</i>14 <i>G</i>15


Lớp
Serpent


<i>R</i>9, <i>R</i>11, <i>R</i>16,
<i>R</i>19


<i>R</i>0, <i>R</i>1, <i>R</i>2, <i>R</i>6,<i> R</i>17, <i>R</i>18 <i>R</i>7, <i>R</i>10, <i>R</i>12, <i>R</i>14 <i>R</i>4, <i>R</i>13 <i>R</i>3,<i> R</i>5 <i>R</i>15 <i>R</i>8


Bằng lập trình, chúng tơi tính cả 6 lớp <i>R</i>3, <i>R</i>4, <i>R</i>5, <i>R</i>8, <i>R</i>13 và <i>R</i>15 đều có lực


lượng bằng 147.456. Vì thế số các S-hộp mạnh sẽ là 147.456  6 = 844.736. Hơn
nữa, một số đại lượng chặt hơn được xem xét đó là n<i>d</i> là số các đặc trưng mà tại đó


đạt được độ đo lượng sai nhỏ nhất (bằng 1/4) và n<i>l</i> là số các xấp xỉ tuyến tính mà


đạt được độ đo tuyến tính nhỏ nhất (bằng 1/4). Ta có, tính chất sau:


<i>3.2.4. Mệnh đề 6.</i><b> </b>nd và nl là các đại lượng được bảo toàn qua biến đổi affine.


<i><b>Chứng minh</b>. Trong chứng minh tính chất bất biến của Lin(S) và Diff(S), chúng ta </i>
rút ra

 

1




2, 1, <i>T</i>


<i>T</i>


<i>w</i> <i>w</i>


<i>b</i> <i>bD</i>


<i>S</i> <i>a</i> <i>S</i> <i>a C</i>


  và 2 1


1


, ,


<i>S</i> <i>S</i>


<i>a b</i> <i>Ca D b</i>


<i>n</i> <i>n</i>  . Vì vậy, các đại lượng n<i>d</i> và n<i>l</i> là


bất biến trong một lớp tương đương affine.■


Vì người ta muốn đạt tới số nhánh cực đại nên sẽ chỉ quan tâm tới các lớp có
chứa S-hộp mà có số nhánh (đại lượng thể hiện khả năng khuếch tán của hộp thế,
xem [6]) bằng 3. Trong số những lớp như vậy, giá trị n<i>d</i> cực tiểu là 18, giá trị n<i>l</i> cực


tiểu là 32. Chỉ có 4 lớp tương đương affine có các tính chất mong muốn, đó là G9,



<i>G</i>10, G14 và G15. Nếu ta quan tâm tới các S-hộp có tính Serpent, thì sẽ chỉ có 6 lớp


đó là <i>R</i>3, R4, R5, <i>R</i>8, R13 và <i>R</i>15. Như vậy, <i>xuất phát từ mối quan tâm đến các đại </i>


<i>lượng nd, nl và số nhánh bằng 3, chúng ta cũng đi đến đúng 6 lớp Serpent như định </i>


</div>

<!--links-->

×