Luận văn Khảo sát mã ma trận, phân tích độ an toàn, hiệu năng và cải tiến

znn ni zA A p A p A pφ = … … ( ) ( )11mod , , mod , , mod i znn ni zB B p B p B pφ = … … ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 mod , , mod , , mod mod , , mod , , mod = mod , , mod , , mod = i z i z i z nn n i z nn n i z nn n i z A B A p A p A p B p B p B p A B p A B p A B p φ φ+ = + + + + … … … … … … ( )A Bφ + ( ) ( ) ( ) ( ) ( ) ( ) 1 1 1 1 1 1 . mod , , mod , , mod . mod , , mod , , mod = . mod , , . mod , , . mod = . i z i z i z nn n i z nn n i z nn n i z A B A p A p A p B p B p B p A B p A B p A B p A B φ φ φ = … … … … … … „ 29  Bổ đề 3: Nếu ma trận A khả nghịch mod m nếu và chỉ nếu ( )Aφ khả nghịch Chứng minh: Nếu A khả nghịch mod m thì ( ) ( )1 1( ) ( )A A AA Iφ φ φ φ− −= = . Do φ là đẳng cấu vành nên ( )Aφ khả nghịch Nếu ( )Aφ khả nghịch thì tồn tại B sao cho ( ) ( ) ( ) ( )A B AB Iφ φ φ φ= = Vậy ta có A×B = I do đó A khả nghịch. Định lý 3: [7, 2.3.3] Số lượng ma trận vuông d×d trên ]m là (với 1 21 2 knn n km p p p= … ) ( ) ( )2 11 0 ( , ) i k d n d d j m i i i i j GL d p p p −− = ⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏] (2.8) Chứng minh: Gọi A là ma trận vuơng khả nghịch trên m] ; thì ( )Aφ khả nghịch. Do φ là một đẳng cấu vành nên số lượng ma trận vuơng khả nghịch trên m] sẽ bằng với số lượng các vectơ của φ . Ta cĩ: ( ) ( )11 mod , , mod , , mod zi nnn i zA A p A p A pφ → … … Áp dụng định lý 2 thì từng thành phần mod iniA p có ( )2 1( 1) 0 i d n d d j i i j p p p −− = −∏ Vậy số vectơ của φ là: ( ) ( )2 11 0 i k d n d d j i i i i j p p p −− = ⎛ ⎞−⎜ ⎟⎝ ⎠∏ ∏ Ta có: ( ) ( )2 11 0 ( , ) i k d n d d j m i i i i j GL d p p p −− = ⎛ ⎞= −⎜ ⎟⎝ ⎠∏ ∏] „ 30  5.4. Không gian tốt nhất của Alphabet Định nghĩa Đặt tỷ số giữa tổng các ma trận vuông cấp d > 0 khả nghịch với tổng các ma trận vuông trên ]m , với m ≥ 2 là: ( , ) ( , ) ( ) m d d m GL d f d m M × = ]] (2.9) Ý nghĩa của f(d,m) sẽ cho ta con số đánh giá để chọn ra kích thước khóa và không gian Alphbet. Nếu ( ) ( )/ /, ,f d m f d m> thì ta nên chọn d, m tương ứng với d là kích thước khóa và m là lượng trong Alphabet. Bổ đề 4:[7, bổ đề 4.3] Nếu d là số nguyên dương và p là số nguyên tố thì ( ) 2 1 0 1 1 0 0 1 ( , ) ( , ) ( ) 1 = 1 1 d d i p i d d d p d i id d d d d j i i j p pGL d f d p M p p p p p p p − = × − − = = = − = = ⎛ ⎞ ⎛ ⎞ ⎛ ⎞− = − = −⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎝ ⎠ ⎝ ⎠ ∏ ∏ ∏ ∏ ] ] (2.10) Định lý 4:[7, định lý 4.4] Nếu d là số nguyên dương và m là số nguyên dương bất kỳ, 0 i k n i i m p = =∏ thì : ( ) 1 1 1, 1 k d j i j i f d m p= = ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠∏∏ (2.11) 31  ( ) ( ) ( ) 2 2 2 2 2 2 2 2 1 ( 1) 1 0 1 1 0 1 1 0 1 ( , ) ( , ) ( ) = = i i i i i i k d n d d l i i i i lm k n dd d m i i k d n d d d l i i i i i l k n d i i d n d d d l k i i i i l n d i i p p p GL d f d m M p p p p p p p p p p p −− = = × −− = = = −− = = ⎛ ⎞−⎜ ⎟⎝ ⎠= = ⎛ ⎞−⎜ ⎟⎝ ⎠ ⎛ ⎞−⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ ∏ ∏ ∏ ∏ ∏ ∏ ∏∏ ] ] ( ) 2 1 0 1 1 1 1 = 1 d d l k k di i l jd i i j ii p p pp − = = = = ⎛ ⎞−⎜ ⎟ ⎛ ⎞⎜ ⎟ = −⎜ ⎟⎜ ⎟⎜ ⎟ ⎝ ⎠⎜ ⎟⎝ ⎠ ∏∏ ∏∏ (2.12) Nhận xét : Từ (2.12) ta thấy f(d,m) không phụ thuộc vào số mũ của thừa số nguyên tố trong phân tích thừa số nguyên tố của m (tức không phụ thuộc vào in ) Định lý 5:[7, định lý 4.6] Cho d là nguyên dương và p là số nguyên tố thì lim ( , ) 1 p f d p→∞ = (2.13) Chứng minh: Áp dụng bổ đề 4: 1 1lim ( , ) lim 1 lim1 1→∞ →∞ →∞= ⎛ ⎞= − = =⎜ ⎟⎝ ⎠∏ d jp p pj f d p p „ 32  Ta xét Hàm Zeta Riemann như sau: 1 1 1 1 1( ) 1 2 3s s s sk s k ζ ∞ = = = + + +∑ … (2.14) Với ( )1ζ = ∞ (2.15) Công thức tích Euler: (2.16) 1 1 1( ) 11 s k p prime s s k p ζ ∞ = − = = − ∑ ∏ 1 1 1 1 1 1 1 2 1 3 1 5 1s s s s sp prime p p− − − − − =− − − − −∏ " " ( ) 1 1 1 11 1s sp pp p sζ −∞ ∞ − ⎛ ⎞⎛ ⎞− = =⎜ ⎟⎜ ⎟ −⎝ ⎠ ⎝ ⎠∏ ∏   Áp dụng hàm Zeta Riemann và công thức Euler ta sẽ chứng minh lim ( , ) 0 k f d m →∞ = Định lý 6:[7, định lý 4.7] Cho d là số nguyên dương và m là số nguyên dương với 11 k nn km p p= … thì lim ( , ) 0 k f d m →∞ = Chứng minh: Từ định lý 4; (2.12) và ta xét 11= … knn km p p ; với k là số các số nguyên tố trong phân tích thừa số nguyên tố của m; ta có: 1 1 1 1 1lim ( , ) lim 1 1 = lim 1 k d jk k i j i d k jk j i i f d m p p →∞ →∞ = = →∞ = = ⎛ ⎞= −⎜ ⎟⎜ ⎟⎝ ⎠ ⎛ ⎞−⎜ ⎟⎜ ⎟⎝ ⎠ ∏∏ ∏∏ (2.17) 33  Ta có: 1 1 1lim 1 ( ) k jk i ip jζ→∞ = ⎛ ⎞− =⎜ ⎟⎝ ⎠∏ (từ công thức tích Euler) Do đó: 1 1 1 1 1 2 1 1lim ( , ) lim 1 lim 1 1 1 1 = ( ) (1) ( ) d k d k j jk k k j i j ii i d d j j f d m p p j jζ ζ ζ →∞ →∞ →∞= = = = = = ⎛ ⎞ ⎛ ⎞= − = −⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ = ∏∏ ∏ ∏ ∏ ∏ (2.18) Theo (2.18) ta có (1)ζ = ∞ do đó 1 1 1lim 1 0 d k jk j i ip→∞ = = ⎛ ⎞− =⎜ ⎟⎜ ⎟⎝ ⎠∏∏ Vậy lim ( , ) 0 k f d m →∞ = nghĩa là k càng lớn thì số ma trận khả nghịch gần bằng 0. „ Ta xét các trường hợp sau: Xét f(10,n) với n là các giá trị trong khoảng 2 đến 29. Hình 2.1 34  Trong hình 2.1; với dấu . thì ta biểu diễn n là số nguyên tố trong khoảng từ 2 đến 29 và dấu + là các trường hợp còn lại trong khoảng từ 2 đến 29. Quan sát hình 2.1, ta thấy các trường hợp số nguyên tố thì f(10,p)luôn lớn hơn các trường hợp còn lại. Xét f(10,n) với n là các giá trị trong khoảng 29 đến 100 Hình 2.2 Với dấu . cho trường hợp f(10,29) và f(10,n) với n là các hợp số trong khoảng từ 30 đến 100. Quan sát hình 2.2 ta thấy f(10,n) và f(10,29) ta thấy f(10,29) luôn nằm trên f(10,n). Vậy khi chọn không gian cho Alphabet thì ta không cần chọn m quá lớn; và ta nên chọn là số nguyên tố. 35  Kết luận: - Không gian bảng chữ cái không cần phải lớn. - Bảng chữ cái nên có số lượng là một số nguyên tố. - Ta chỉ khảo sát và sinh khóa trên trường p]  với p là số nguyên tố. 6. Xét các trường hợp khóa yếu 6.1. Ma trận đối hợp (Involutory matrix) 6.1.1. Xây dựng ma trận đối hợp 6.1.1.1. Ma trận đối hợp trên trường ; 2p p >] Gọi H là ma trận đối hợp n × n trên trường p] , nghĩa là 2 nH I= nên H có thể là: 1. nI 2. nI− 3. r r s s r s I Z J Z I × × ⎛ ⎞= ⎜ ⎟−⎝ ⎠ Với ,0r s n s n+ = < < Định lý 7: (Theo [9]) Điều kiện cần và đủ để ma trận vuông H với kích thước n × n, trên trường ; 2>] p p với 0 < s < n, thì 2 2nH I Q P= − × là ma trận đối hợp với 2Q là ma trận n × s và 2P là ma trận s × n sao cho 2 2 2 sP Q I× = × (với s < n và hạng của 2P bằng s thì luơn tồn tại 2Q sao cho 2 2 2 sP Q I× = × ).Tương tự cho 1 1 nH Q P I= × − với 1Q là ma trận n × r và 1P là ma trận r × n sao cho 1 1 2 rP Q I× = × và r + s = n (với r < n và hạng của 1P bằng r thì luôn tồn tại 1 1 2 rP Q I× = × ) 36  Chứng minh Điều kiện cần. Ta đặt 1H Q J Q−= × × ; với Q là ma trận khả nghịch bất kỳ trên p] Ta đặt ( )/ /1 2Q Q Q= ; với /2Q là ma trận có kích thước n s× Và đặt 11 2 P Q P − ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; với 2P là ma trận có kích thước s n× ( ) 11 / / / /1 2 1 1 2 2 2 n P Q Q Q Q Q P Q P I P − ⎛ ⎞× = × = × + × =⎜ ⎟⎝ ⎠ (2.19) ( ) / /11 / / 1 1 1 21 2 / / 2 2 1 2 2 r r s s r s I ZP P Q P Q Q Q Q Q Z IP P Q P Q ×− × ⎛ ⎞× × ⎛ ⎞⎛ ⎞× = × = =⎜ ⎟ ⎜ ⎟⎜ ⎟ × ×⎝ ⎠ ⎝ ⎠⎝ ⎠ (2.20) ( ) ( ) 11 / / 1 2 2 1/ / / / 1 2 1 1 2 2 2 = r r s s r s I Z P H Q J Q Q Q Z I P P Q Q Q P Q P P ×− × ⎛ ⎞ ⎛ ⎞= × × = × ×⎜ ⎟ ⎜ ⎟− ⎝ ⎠⎝ ⎠ ⎛ ⎞− × = × − ×⎜ ⎟⎝ ⎠ 2.21) Từ (2.19),(2.21) ta có: /2 22nH I Q P= − × × Đặt /2 22Q Q= × Ta có: 2 2nH I Q P= − × Từ (2.20) ta có: /2 2 2 22 2 sP Q P Q I× = × × = × Trường hợp 1 1 nH Q P I= × − ta xét tương tự Điều kiện đủ: H×H=( 2 2nI Q P− × )×( 2 2nI Q P− × )= nI - 2 2Q P× - 2 2Q P× + 2 2Q P× 2 2Q P× × = nI -2 2 2Q P× × + 2 22 sQ I P× × × = nI „ Ví dụ: Ta xây dựng ma trận đối hợp trên 7] : 37  n=3; s=2 2 1 2 3 1 3 5 P ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; 2Q được xây dựng bằng cách giải hệđ 2 1 2 2 2 0 0 2 P X P X ⎧ ⎛ ⎞=⎪ ⎜ ⎟⎪ ⎝ ⎠⎨ ⎛ ⎞⎪ = ⎜ ⎟⎪ ⎝ ⎠⎩ với ( )2 1 2Q X X= Lần lượt giải các hệ ta được 1 6 5 5 a X a a +⎛ ⎞⎜ ⎟= +⎜ ⎟⎜ ⎟⎝ ⎠ với 7a∈] 2 3 2 5 b X b b +⎛ ⎞⎜ ⎟= +⎜ ⎟⎜ ⎟⎝ ⎠ với 7b∈] Với 1; 1a b= = thì 2 0 4 3 0 1 1 Q ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ma trận đối hợp 1 0 0 0 4 1 0 0 4 5 6 4 2 1 1 2 3 0 1 0 3 0 0 1 0 3 6 2 4 2 5 1 3 5 0 0 1 1 1 0 0 1 2 5 1 5 2 0 H ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟= − = − =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 6.1.1.2. Ma trận đối hợp trên trường 2] [Theo 9] Gọi H là ma trận đối hợp n × n trên trường F, có đặc số 2, nghĩa là 2 nH I= nên H có thể là: 1. nI 2. 2 2 2 r r s t s r s I Z J Z K × × ⎛ ⎞= ⎜ ⎟⎝ ⎠ 2sK là tổng trực tiếp của s ma trận 1 1 0 1 ⎛ ⎞⎜ ⎟⎝ ⎠ và 12 ;0 2 r s n s n+ = < ≤ 38  Định nghĩa tổng trực tiếp như sau: 0 0 A A B B ⎛ ⎞⊕ = ⎜ ⎟⎝ ⎠ Định lý 8: (Theo [9]) Nếu F là trường có đặc số 2, thì điều kiện cần và đủ để ma trận vuông nxn H là ma trận đối hợp với 10 2 s n< ≤ , 2 2nH I Q P= + × sao cho 2Q là ma trận n×s có hạng là s và ma trận 2P là ma trận s×n và có hạng là s sao cho 2 2 ,0s sP Q× = (do s < n nên luôn tồn tại 2Q sao cho 2 2 ,0s sP Q× = ) Chứng minh Điều kiện đủ: H×H = ( 2 2nI Q P+ × )×( 2 2nI Q P+ × )= nI + 2 2Q P× + 2 2Q P× + 2 2Q P× × 2 2Q P× = = nI +2 2 2Q P× × + 2 2Q P× × 2 2Q P× = nI + 2Q ,0s s× × 2P = nI Điều kiện cần: Ta đặt 11H Q J Q −= × × ; với Q là ma trận khả nghịch bất kỳ trên p] Ta đặt ( )/ /1 2Q Q Q= ; với /2Q là ma trận có kích thước 2n s× Và đặt / 1 1 / 2 P Q P − ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; với /2P là ma trận có kích thước 2s n× Ta có: ( ) /1 / / / / / /11 2 1 1 2 2/ 2 n P Q Q Q Q Q P Q P I P − ⎛ ⎞× = × = × + × =⎜ ⎟⎝ ⎠ (2.22) ( )/ / / / / 21 / /1 1 1 1 21 2/ / / / / 2 22 2 1 2 2 r r s n s r s I ZP P Q P Q Q Q Q Q I Z IP P Q P Q ×− × ⎛ ⎞ ⎛ ⎞× × ⎛ ⎞× = × = = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟× × ⎝ ⎠⎝ ⎠ ⎝ ⎠ (2.23) 39  ( ) ( ) / 21 / / 1 1 1 2 / 2 2 2 / / / 1 1 2 2 / 2 / / / / 1 1 2 2 2 r r s s r s s s I Z P H Q J Q Q Q Z K P P Q Q K P Q P Q K P ×− × ⎛ ⎞⎛ ⎞= × × = × ×⎜ ⎟⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎛ ⎞= × ×⎜ ⎟⎝ ⎠ = × + × × (2.24) Từ (2.22) và (2.24), ta có: ( ) = − × + × × + × − × / / / / 2 2 2 2 2 / / 2 2 2 2 = n s n s s H I Q P Q K P I Q K I P Đặt ( )−= − = …2 2 2 .1 .3 .2 10, ,0, ,0, ,0,s s s sL K I i i u Với 0 là vectơ cột 0 và . ji là vectơ cột thứ j trong ma trận đơn vị. ( )−× = …/2 2 .1 .3 .2 10, ,0, ,0, ,0,s sQ L q q q với . jq là cột thứ j trong ma trận / 2Q ( )/ / /2 2 2 .1 .3 .2 1 2 .1 2. .3 4. .2 1 2 .0, ,0, ,0, ,0,s s s sQ K P q q q P q p q p q p− −× × = × = × + × + + ×… … Với .jp là dòng thứ j trong ma trận / 2P . Như vậy ta chỉ sử dụng cột lẻ trong /2Q và dòng chẵn trong / 2P . Ta đặt ( )× − × = ×/ /2 2 2 2 2 2s sQ K I P Q P Từ (2.23) ta có: 2 2 ,s sP Q Z× = vì dòng chẵn trong là vectơ 0 „ Ví dụ: Xây dựng ma trận đối hợp trên 2] : n=3; s=2 2 1 0 1 1 0 1 P ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; 2 Q được xây dựng bằng cách giải hệđ 40  2 1 2 2 0 0 0 0 P X P X ⎧ ⎛ ⎞=⎪ ⎜ ⎟⎪ ⎝ ⎠⎨ ⎛ ⎞⎪ = ⎜ ⎟⎪ ⎝ ⎠⎩ với ( )2 1 2Q X X= Lần lượt giải các hệ ta được 1 b X a b ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ với 8a∈] 2 d X c d ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ với 8,c d ∈] Với 1; 0, 1; 1a b c d= = = = thì 2 0 1 1 1 0 1 Q ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ma trận đối hợp 1 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 H ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟= + = + =⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ Định lý 9: Cho hai ma trận A,B có kích thước lần lượt là r × s và s × r với các phần tử được chọn tùy ý trên vành giao hoán có đơn vị thì ma trận M có kích thước là n×n sao cho n= r+s thì M được xây dựng nhưng sau thì M là ma trận đối hợp: 2 s r BA I B M A ABA I AB −⎛ ⎞= ⎜ ⎟− −⎝ ⎠ (2.25) Định lý 10: (Về ma trận đối hợp) 1. A là ma trận đối hợp nếu và chỉ nếu 1A A−= 2. Nếu A là ma trận đối hợp thì ( )1 2 B I A= + là ma trận lũy đẳng. 41  3. Định thức của ma trận đối hợp A trên trường p] là 1 hoặc p –1 Chứng minh: 1. (⇒ ) A là ma trận đối hợp nên A.A = I . gọi A’ là ma trận nghịch đảo của A thì ta có A.A’=A’.A=I. do đó A=A’= 1A− (⇐) Ta có 1A A−= A. 1A− =I (định nghĩa) Suy ra A.A=I . Vậy A là ma trận đối hợp 2. B.B=( ( )1 2 I A+ )( ( )1 2 I A+ )= ( )21 4 I A+ ( ) ( ) ( )21 1 12 24 4 2I A A I A I A B+ + = + = + = „ Bổ đề 5 (vành ma trận) : Cho n là số nguyên lớn hơn hoặc bằng 1. Thì tập hợp các ma trận n×n có các phần tử trên trường p] với hai phép toán cộng và nhân ma trận tạo thành một vành. Bổ đề 6: A là ma trận đối hợp trên trường p] thì một số ma trận dễ thấy là các dạng sau : 1. In 2. (p–1)In 3. , , r r s s r s I Z J Z I ⎛ ⎞= ⎜ ⎟−⎝ ⎠ với r+s = n và 0 < s < n 42  4. ,21 2 , 2 r r s s r s I Z J Z K ⎛ ⎞= ⎜ ⎟⎝ ⎠ với r+2s = n và 0 < s ≤ 1 2 n và K2s là tổng trực tiếp của s ma trận 1 1 0 1 ⎛ ⎞⎜ ⎟⎝ ⎠ Nhận xét: Ma trận đối hợp trên trường ] p hoặc ]2 là ma trận tam giác trên với 1; p – 1 trên đường chéo chính và 1 hoặc 0 trong tất cả các phần tử phía trên đường chéo chính. Định thức của ma trận đối hợp A là bằng 1 hoặc p – 1 6.1.2. Đếm số ma trận đối hợp [Theo 6] Đếm số ma trận đối hợp (involutory) bậc d×d trên p] Đặt ( ) 0 t t i t i g p p = = −∏ là số ma trận khả nghịch bậc t trên trường p] Trường hợp p > 2 Đặt ( )0 ,N d t là số ma trận X cấp d × d thỏa 2 0X I− = Nếu X là ma trận có det(xI – X) có đa thức đặc trưng mà có t nghiệm là 1 và d – t nghiệm p–1 thì (mod ) M X J p≡ với J được định nghĩa trong 6.1.1.1 với 0 t d≤ ≤ Đặt ( )0 ,S d t là số ma trận X sao cho (mod )MX J p≡ Thì ( ) ( )0 0 0 , , = = ∑d t N d t S d t ; 0 t d≤ ≤ (do ma trận X trong ( )0 ,S d t là khác nhau) 43  Q là ma trận khả nghịch bậc m trên p] sao cho 1−× ×Q J Q ; thì ( )1 mod −× × ≡MQ J Q J p . Nếu 1−× × =Q J Q J thì Q J J Q× = × . Đặt ( )0 ,C d t là số ma trận Q sao cho thỏa Q và J giao hoán. Ta có: ( ) ( )0 0, ,dg C d t S d t= Do Q J J Q× = × nên ( )0 , t d tC d t g g −= Suy ra: ( ) ( )0 0, ,d dt d t g g S d t g gC d t − = = Do đó số ma trận đối hợp trên p] là: ( )0 0 0 1, = =− − = =∑ ∑d dd d t tt d t t d t gN d t g g g g g (2.26) Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ . „ Trường hợp p = 2 [Theo 6] Đặt X là ma trận cấp d×d; X là ma trận thỏa mãn: 2 0X I− = trên 2] . Tương tự trường hợp trên thì (mod ) M tX J p≡ với tJ được định nghĩa trong 6.1.1 phần b. Đặt ( ),eS d t là tổng số ma trận X sao cho (mod )M tX J p≡ với 0 2t d≤ ≤ Ta có: ( ) ( ) 0 , , = = ∑de e t N d t S d t ; 0 2≤ ≤t d (do ma trận X trong ( ),eS d t là khác nhau) Đặt ( ),eC d t là số lượng ma trận khả nghịch Q bậc d trên 2] thỏa mãn t tJ Q Q J× = × . Ta có: ( ) ( ), ,d e eg S d t C d t= Theo [10] ( ) ( )2 3 2, 2t m te t d tC d t g g− −= 44  Suy ra: ( ) (2 3 )2 0 2 2, ⎢ ⎥⎢ ⎥ − −⎣ ⎦ = − = ∑ d t d t e d t t d t N d t g g g (2.27) Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ Ta xét trường hợp f(d,29) với d trong khoảng 2 đến 30 Hình 2.3 Quan sát hình 2.3 ta thấy với khoảng d thay đổi từ 2 đến 30 thì các f(d,29) có xu hướng bằng nhau. Từ (2.26) và (2.5). Ta đặt g(t) tỷ số giữa tổng ma trận đối hợp trong (2.26) và tổng số ma trận khả nghịch trong (2.5);ta xét trên ] p : 0 0 1( ) d d d t t d t td t d t g g g g t g g g = − = − = = ∑ ∑ (2.28) 45  Với ( )1 0 0 ; 1 t t i t i g p p g − = = − =∏ Ý nghĩa của g(t) càng nhỏ thì càng tốt vì lúc đó sẽ có tỷ lệ khóa yếu là ít nhất. Ta xét trường hợp d trong khoảng từ 2 đến 5 Hình 2.4 Quan sát hình 2.4 ta thấy với d=2 lớn thì g(t)= 0.0012, còn d từ 3 trở lên thì g(t) càng tiến về 0. Như vậy khi sinh khóa thì kích thước khóa càng lớn thì tỷ lệ khóa yếu càng ít. 6.2. K là khóa yếu với K×v = v hoặc v×K = v: Ta xét khóa là ma trận vuông d×d khả nghịch trên p] 6.2.1. Xác định khóa yếu bằng định thức Với cách mã hóa: K×v = v thì K được gọi là khóa yếu. 46  ( ) ( ) 11 1 1 1 1 11 1 1 1 1 1 0 1 0 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ − + + =⎧⎪⎨⎪ + + − =⎩ … # % # # # … … … … d d dd d d d d d dd d k k m m k k m m k m k m k m k m (2.29) det(K – I) ≠ 0 thì hệ (2.29) có nghiệm duy nhất là nghiệm tầm thường 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ # det(K – I) = 0 thì hệ (2.29) có vô số nghiệm hoặc vô nghiệm, nhưng do hệ luôn có nghiệm tầm thường nên khi det(K – I) = 0 thì hệ (2.29) vô số nghiệm. Nhưng do trên ] p có hữu hạn phần tử hệ (2.29) cũng có hữu hạn nghiệm. Ví dụ: Trên 11] 2 3 2 7 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ , có det K ≠ 0 nhưng det(K – I) = 0 Véc tơ dạng 1 17 m v m ⎛ ⎞= ⎜ ⎟⎝ ⎠ với 1 11m ∈] thì Kv = v Thì 0 1 2 3 4 5 6 7 8 9 10 , , , , , , , , , , 0 7 3 10 6 2 9 5 1 8 4 v ⎧ ⎫⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞∈⎨ ⎬⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎩ ⎭ Do 11] hữu hạn phần tử nên v cũng thuộc tập nghiệm hữu hạn Nếu thông điệp M mà ta cần mã hóa sau khi chuyển thành dạng ma trận có các cột là các nghiệm trong tập trên thì K×M=M Với 2 9 7 3 8 5 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Thì khi mã hóa: 47  2 3 2 9 7 2 9 7 2 7 3 8 5 3 8 5 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠C K M Cipher text sẽ bằng plaintext; như vậy khi mã hóa khóa yếu như trên thì người ta sẽ biết được plaintext. Với cách mã hóa: v×K = v thì K được gọi là khóa yếu ( ) ( ) ( ) ( ) 11 1 1 1 1 11 1 1 1 1 1 0 1 0 ⎛ ⎞⎜ ⎟× = ⇔⎜ ⎟⎜ ⎟⎝ ⎠ − + + =⎧⎪⎨⎪ + + − =⎩ … … # % # … … … … … d d d d dd d d d dd d k k m m m m k k k m k m k m k m (2.30) det(KT – I) ≠ 0 thì hệ (2.30) có nghiệm duy nhất là nghiệm tầm thường. det(KT – I) = 0 thì hệ (2.30) có vô số nghiệm hoặc vô nghiệm, nhưng do hệ luôn có nghiệm tầm thường nên khi det(KT – I) = 0 thì hệ (2.30) có vô số nghiệm. Nhưng do trên ] p có hữu hạn phần tử hệ (2.30) cũng có hữu hạn nghiệm. Ta có nhận xét: 1/ Trên trường ] p với m là số nguyên dương thì một khóa K gọi là yếu khi và chỉ khi det ( K – I ) = 0 với cách mã K×v = v. 2/ Trên trường ] p với m là số nguyên dương thì một khóa K gọi là yếu khi và chỉ khi det ( KT – I ) = 0 với cách mã v×K = v 6.2.2. Xác định khóa yếu bằng trị riêng Định nghĩa: Cho A là ma trận vuông d×d và c ∈ p] Đặt { }/n T TcE X AX cX= ∈ =\ c được gọi là trị riêng và cE được gọi là không gian riêng ứng với trị riêng 48  Với mỗi { }\ 0cEα ∈ thì α là vec tơ riêng ứng với trị riêng c Ta đặt ( ) ( )detA nP x cI A= − gọi là đa thức đặc trưng của A Mệnh đề (Mối liên hệ giữa trị riêng và đa thức đặc trưng) Nếu c là trị riêng trên p] của A thì ( )AP c =0 trên p] Suy ra nếu muốn tìm trị riêng thì ta tìm tất cả các nghiệm của ( )AP x trên p] Tính chất của trị riêng và vectơ riêng: 1. Nếu c = 0 thì ma trận A không khả nghịch 2. Nếu A là ma trận tam giác trên và ma trận tam giác dưới, ma trận đường chéo thì trị riêng là nhưng phần tử trên đường chéo chính. 3. A và AT có cùng trị riêng. 4. Transition matrix thì luôn có trị riêng là 1 Trasition matrix có tính chất là tất cả các hàng có tổng là 1 Ví dụ: Xét ma trận có trị riêng là 1 trên 7] 1 2 5 4 4 0 3 2 3 A ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ta tính trị riêng cho K ( ) 1 2 5 det 4 4 0 3 2 3 − − − − = − − − − − x xI K x x = 49  ( ) ( )( )( ) ( ) ( )( ) ( ) ( ) ( )( )( )3 2 2 4 0 4 0 4 4 = 1 2 5 2 3 3 3 3 2 = 1 4 3 8 3 5 8 3 4 = 4 4 1 4 1 1 2 2 − − − −− + −− − − − − − − − − − − − + − − − + = − − − = − − + x x x x x x x x x x x x x x x x x x x A có trị riêng là 1 Tìm v sao cho K×v = v ⇔ (K – I)×v = 0 á phé biê dơ so câ trê dị 0 2 5 0 1 1 5 0 4 3 0 0 0 2 5 0 3 2 2 0 0 0 0 0 c c p n i p n ng ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯→⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ Suy ra b v b b ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Nếu 2 3 2 3 2 3 M ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ 1 2 5 2 3 2 3 4 4 0 2 3 2 3 3 2 3 2 3 2 3 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ K M Ta có nhận xét: Nếu trị riêng ma trận vuông A có trị riêng là 1 thì tồn tại những vectơ riêng X sao cho × =T TK X X . Muốn tìm được XT thì ta phải giả hệ phương trình tuyến tính. Một khóa là ma trận khả nghịch nhưng không yếu thì ma trận có các giá trị riêng phải khác 1. Ở đây ta có thể xét một trường hợp là loại những ma trận Trasition matrix có tính chất là tất cả các hàng có tổng là 1. Ta xét định thức thì: det(K – I) ≠ 0 và det(KT – I) ≠ 0 50  7. Tóm tắt Mã ma trận bậc d khi ta mã hóa cần khóa là ma trận vuông khả nghịch trên m] , m bất kỳ. Ở đây không gian các chữ cái(Alphabet) là m nên là số nguyên tố và số chiều d của ma trận khóa nên lớn để hạn chế khóa yếu. Trường hợp các khóa yếu thì ta có ma trận đối hợp (involutory matrix) đối với trường hợp này thì khi ta xây dựng ma trận K = L × U thì ta chỉ cần xây dựng ma trận K sao detK ≠ 1 và p – 1 Trường hợp K×v = v thì ta xây dựng ma trận K có det(K – I) ≠ 0. 51  Chương 3 XÂY DỰNG THUẬT GIẢI SINH KHÓA CHO Mà HILL 1. Định lý sinh khóa trên p] (1) 11 1 1 0 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … # % # % # # % … … … tt tt d dt dd l l L l l l l khả nghịch ⇔ ( ) 1 0 mod p = ≠∏d ii i l (3.1) (2) 11 1 1 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … % # … % % … d tt tt td dd u u u u u U u khả nghịch ⇔ ( ) 1 0 mod p = ≠∏d ii i u (3.2) (3) K L U= × khả nghịch khi và chỉ khi L,U khả nghịch (3.3) (4) K khả nghịch ⇒ P×K cũng khả nghịch với P là ma trận hoán vị Với P là ma trận hoán vị được định nghĩa như sau: ( ) 1 2 nk k k P e e e= … với ik e là các hàng trong ma trận đơn vị. ( )ijP p= với 1 nếu 0 ngược lạiiij j kp ⎧ =⎪= ⎨⎪⎩ (3.4) 52  (5) 11 1 1 1 1 1 0 0 0 0 1 0 1 0 0 + + ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟= × = ×⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ … … … # % % # # … % % # # % % … … … … d tt tt td tt d dt dd u u u u u K L U l l l u (3.5) thì không tồn tại ma trận L1; U1 sao cho L≠L1(L1 là ma trận tam giác trên với đường chéo chính gồm các phần tử 1) và U≠U1 thì L×U=L1×U1 (6) Với ma trận K khả nghịch trên p] thì luôn tồn tại ma trận P, L,U (với ma trận L là ma trận tam giác trên sao cho các đường chéo chính là 1)khả nghịch trên p] sao cho K= P×L×U (theo [5, trang 153]) Chứng minh Chứng minh (5) Không tồn tại ma trận L1, U1 (với L1 là ma trận tam giác dưới có đường chéo chính là 1)sao cho L1≠L và U1≠U mà K = L1 × U1 Chứng minh: Ta xét trên p] ; với 1 1K L U= × . Ta giả sử ta có 2 2K L U= × Lúc này ta có 1 1 2 2L U L U× = × . Do K khả nghịch nên 1 2,U U khả nghịch. Ta có: 1 11 1 2 2 2 1 2 1L U L U L L U U − −× = × ⇔ × = × (3.6) Do 2L là ma trận tam giác dưới nên 1 2L − cũng là ma trận tam giác dưới. Suy ra 1 2 1L L − × là ma trận tam giác dưới. Tương tự thì 1U là ma trận tam giác trên nên 1 1U − là ma trận tam giác trên. Suy ra 12 1U U −× là ma trận tam giác trên. Từ (3.6) thì vế trái là ma trận tam giác dưới và vế phải là ma trận tam giác trên 53  1 12 1 2 1L L U U − −× = × = D (3.7) Với D là ma trận đường chéo. Do 12 1;L L − có các lii là 1 nên D là ma trận đơn vị. Từ (3.7) ta có: 1 12 1 2 1 dL L U U I − −× = × = (3.8) Từ (3.8) thì 2 1 2 1;= =L L U U „ Chứng minh (6) Với K là ma trận vuông cấp d khả