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

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ả nghịch trên p] ; thì K cũng khả nghịch trên\ . Theo [5, trang 153] thì tồn tại ma trận ( ), , ,P L U M d∈ \ sao cho K P L U= × × . Do K khả nghịch trên p] , nên P L U× × cũng khả nghịch trên p] ; suy ra L, U khả nghịch trên p] . Vậy với K khả nghịch trên p] thì tồn tại ma trận L, U khả nghịch trên p] sao cho K P L U= × × „ 2. Xác định cơ sở hình thành thuật giải Ta sinh ra hai ma trận L và U trên p] Với 1 1 1 0 0 1 0 1 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … # % # % # # % … … … tt d dt L l l l 54  11 1 1 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … % # … % % … d tt tt td dd u u u u u U u Khóa K được tính như sau: 11 1 1 1 1 11 1 1 0 0 0 1 0 1 0 0 + + ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟= × = ×⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … … … # % # % # … % % # # % % … … … … … … # % # … # % # % # … … d tt tt td tt d dt dd tt tj jt d dd u u u u u K L U l l l u k k k k k k (3.9) Với ( ) ( ) ( ) 1 1 2 2 1 1 2 2 1 1 2 2 ⎧ + + + ⎪⎩ … … … i j i j ij ij i j i j ii i j i j ij jj l u l u u i j k l u l u u i j l u l u l u i j (3.10) Ta tính: 11 1 1 1 1 tt tj jt d dd k k k A K I k k k −⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟−= − = ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟−⎝ ⎠ … … # % # … # % # % # … … (3.11) 55  Với ( ) ( ) ( ) 1 1 2 2 1 1 2 2 1 1 2 2 1 ⎧ + + + ⎪⎩ … … … i j i j ij ij i j i j ii i j i j ij jj l u l u u i j a l u l u u i j l u l u l u i j (3.12) Ma trận U phải khả nghịch: 11 1 0 d i u = ≠∏ Để ma trận khóa K không là khóa yếu thì ma trận khóa K phải thỏa là: K không là ma trận đối hợp (Involutory matrix) nghĩa là 11 1 1 và 1 d i u p = ≠ −∏ Đối với trường hợp khóa yếu K v v× = thì ta xét det(K – I) phải khác 0. Với mục (5) trong phần 1 của chương này thì với một bộ (L,U) sẽ có một khóa K nên khi ta xác định tổng số khóa K có thể sinh ra bằng thuật giải thì bằng số lượng ma trận L nhân với số lượng ma trận U. Với mục (6) của phần 1 của chương này thì ta có nhận xét là với K khả nghịch thì ta luôn có K = P × L ×U nên không gian khóa mà ta sinh bằng bộ L×U thì đảm bảo không gian sinh ra gần bằng không gian ma trận vuông khả nghịch. 3. Thuật giải: Ta phải xác định trước p] với p là số nguyên tố; là không gian bảng các chữ cái. Bước 1: Ta sẽ phát sinh ma trận tam giác trên U sao cho U phải thỏa một số tính chất sau: U phải khả nghịch nghĩa là: 1 0 d ii i u = ≠∏ det(K) ≠ 1 và p – 1 nghĩa là: det(U) ≠ 1 và p – 1 ⇔ 1 1 và 1 d ii i u p = ≠ −∏ 56  Bước 2 : Ta sẽ phát sinh ma trận tam giác dưới L sao cho các phần tử trên đường chéo chính bằng 1. Bước 3 : Ta tính khóa K L U= × Bước 4: Tính det(K – I). Nếu det(K – I) = 0 thì ta quay lại bước 2 tính lại ma trận L. Nếu det(K – I) ≠ 0 thì ta tiếp bước 5. Bước 5: Ta sẽ hoán vị khóa K để khóa K trở nên an toàn hơn mớiK P K= × Với P là ma trận hoán vị. 4. Ví dụ: Ta xét trên trường 29] ; ta sẽ sinh khóa có bậc là 4 Bước 1: Ta sinh ma trận tam giác dưới L bất kỳ sao cho các đường chéo chính bằng 1. 1 0 0 0 2 1 0 0 6 4 1 0 5 3 0 1 ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ L Bước 2: Ta phát sinh ma trận tam giác trên U bất kỳ khả nghịch và thỏa: 4 1 0;1;28ii i u = ≠∏ 57  5 2 1 2 0 3 2 5 0 0 1 1 0 0 0 1 U ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Bước 3: Tính khóa K 1 0 0 0 5 2 1 2 5 2 1 2 2 1 0 0 0 3 2 5 10 7 4 9 6 4 1 0 0 0 1 1 1 24 15 4 5 3 0 1 0 0 0 1 25 19 11 26 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ K L U Bước 4: Kiểm tra K có là khóa yếu không? Tính : det (K – I) =18 ≠ 0 Nên K là khóa mà ta chấp nhận được (không yếu) Chấp nhận là khóa và chuyển sang bước 5. Bước 5: Ta có thể hoán vị ma trận khóa vừa phát sinh Ví dụ: 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 P ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Như vậy khóa mới là: mới 0 1 0 0 5 2 1 2 10 7 4 9 0 0 0 1 10 7 4 9 25 19 11 26 1 0 0 0 1 24 15 4 5 2 1 2 0 0 1 0 25 19 11 26 1 24 15 4 K P K ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠ 58  5. Khảo sát không gian khóa vừa sinh theo thuật giải Ta xét trên p] với p là số nguyên tố Ta sinh khóa K là ma trận vuông khả nghịch d×d Số ma trận khả nghịch trên p] là : ( )1 0 p d i i p p − = −∏ Số ma trận involutory: Trường hợp p > 2 0 d d t t d t g g g= − ⎛ ⎞⎜ ⎟⎝ ⎠∑ Với ( ) ( )2 1 1 0 1 t t t i t i t i i g p p p p −− = = = − = −∏ ∏ và 0 1g = Trường hợp p = 2 (2 3 )2 0 2 2 d t d t d t t d t g g g ⎢ ⎥⎢ ⎥ − −⎣ ⎦ = − ∑ Như vậy số ma trận khóa là số ma trận khả nghịch trên p] trừ đi số ma trận khóa yếu. Ma trận tam giác dưới L và ma trận tam giác trên U bậc d có ( )1 2 d d + có thể khác 0. Theo thuật giải trên thì số ma trận tam giác dưới L là ( )1 2 d d d p + − (3.13) Theo thuật giải trên thì số ma trận U, khi ta xây dựng thì trên đường chéo chính có d – 1 phần tử chọn sao cho khác 0. Phần tử udd sẽ phụ thuộc các phần tử trước sao cho tích các đường chéo chính khác 1. Vậy ta có ( ) 11 dp −− cách chọn phần tử trên đường chéo chính. Các phần tử còn lại chọn bất kỳ nên ta có: 59  ( )1 2 d d d p + − cách chọn. Vậy số ma trận tam giác trên U là: ( ) ( )11 21 d d ddp p + −−− (3.14) Vậy số lượng ma trận khóa K = L × U có thể là: ( ) ( ) ( ) ( ) 21 11 12 21 1d d d dd dd d d dp p p p p+ +− −− − −− = − (3.15) 60  Chương 4: CÁC VẤN ĐỀ LIÊN QUAN ĐẾN Mà HILL Mô tả: Người A và người B trao đổi thông tin cho nhau; sử dụng mã hóa đối xứng và cụ thể là mã ma trận. A và B sẽ có khóa bí mật là ma trận; và áp dụng thuật toán mã hóa theo ma trận để mã hóa thông điệp M và chuyển cho B. B sẽ sử dụng khóa bí mật để giải mã và tính toán được M. 1. Sinh khóa theo pincodes Hình 4.1 Người gửi A sẽ có một pin codes và dùng pin codes để sinh ra khóa bí mật là ma trận K. Người A sẽ dùng khóa K để mã hóa thông điệp C = K × M. Người nhận B cũng có pincodes và cũng dùng pincodes để sinh ra khóa là ma trận K. Và dùng khóa K để tính M = K-1 × C. Thuật toán: sinh hóa từ pincodes và mã hóa bằng mã ma trận Cho trước pincodes S có chiều dài xác định trước. Thông điệp         M  Người gửi          A  Sinh Khóa K Sinh khĩa K   Theo pin codes  Người nhận B         Mã hĩa Thông điệp M  C= K × M Sinh khĩa K   Theo pin codes  Thông điệp         M = K‐1×  C  61  Thuật toán sinh khóa K là tích của ma trận tam giác dưới L và ma trận tam giác trên U có kích thước là d × d Gọi f là hàm băm (hash). Bảng chữ cái (Alphabet) A B C D E F G H I J K L M N O 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 P Q R S T U V W X Y Z . ? ∪ 15 16 17 18 19 20 21 22 23 24 25 26 27 28 Thuật toán: Ta sẽ áp dụng bảng chữ cái để chuyển từ chữ sang số; trong trường hợp là số thì chính là giá trị của số đó; chỉ có trường hợp số 0 ta chuyển thành số 10. Như vậy chỉ có trường hợp duy nhất là A hay a thì chuyển thành 0. Sinh khóa K Bước 1: Dùng hàm băm f để tính giá trị t:=f(S): Ma trận U có ( )1 2 d d + phần tử cần tính toán Ta tính: ( ) ( )1 1: ( ) 2 2* ( ) + +⎡ ⎤ ⎡ ⎤= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ d d d d length t a length t Nếu 1a > ; thì Lần 1 ta sẽ tính t:=f(S) Lần 2 Ta tính: S:= S+t và tính t:= t + f(S) Và tương tự như như vậy lập lại a lần. Bước 2: Tính ma trận L: 62  Ta sẽ gán các phần tử đường chéo chính: 11 22 33, , , , ddl l l l… các giá trị là 1. for i from 1 to d do L[i][i]:=1; end do; Duyệt chuỗi t sau khi chuyển sang số và gán cho các giá trị cho lij với i > j k:=0; for i from 2 to d do for j from 1 to i do L[i][j]:=t[k]; k:=k+1; end do; end do; Bước 3: Tính ma trận U: Gán các phần tử trên đường chéo chính khác 0 và chọn udd sao cho 1 0 1; 1 d ii dd i u u p − = ⎛ ⎞ ≠ −⎜ ⎟⎝ ⎠∏ Duyệt chuỗi t ngược từ cuối chuỗi sang đầu chuỗi. Gán các phần tử u11;….;ud-1d-1 sao cho các uii đó khác 0. k:==length(t); S:=1; for i:= 1 from d – 1 do 63  U[i][i]:=t[k]; k:=k-1; if U[i][i]=0 then U[i][i]:= U[i][i]+1; end if; S:=S*U[i][i] mod p; end do; U[d][d]:=t[k]; k:=k – 1; if(S*U[d][d]=1) or (S* U[d][d]=p – 1) then U[d][d]:= U[d][d]+1; end if; Gán các phần tử bất kỳ trong t (duyệt ngược chuỗi t)cho uij for j from 1 to d – 1 do for i from j+1 to d do U[i][j]:=t[k]; k:=k – 1; end do; end do; Bước 4: Tính khóa K: K:= L × U; Tính det(K – I); Nếu det(K – I ) = 0 thì lập lại bước 1 với pincodes S:= S +f(S); Ngược lại chuyển sang bước 5. Bước 5: Chuyển thông điệp thành dạng ma trận Chuyển các ký tự trong thông điệp M thành dạng số. 64  Tính ( ):β = −length M d ; Nếu 0β = thì thông điệp sẽ là ma trận dạng d×1 Nếu 0β > thì thêm ( ) ( )⎡ ⎤ −⎢ ⎥⎢ ⎥ length Md length M d khoảng trắng vào cuối M; lúc này ma trận thông điệp dạng ( )⎡ ⎤× ⎢ ⎥⎢ ⎥ length Md d . Nếu 0β < thì thêm β khoảng trắng vào cuối M; thông điệp là ma trận dạng d×1. Tạo thông điệp thành ma trận và chuyển sang số. Bước 6: Tiến hành mã hóa M và gửi cho B: C = K × M; Bước 7: Gởi C (Ciphertext) cho người B; Tại người B có pincodes và sinh ma trận khóa K tương tự các bước 1,2,3,4. Tính nhanh ma trận K-1 (phần 4 Chương 4). Giải mã và tính thông điệp M M = K-1 × C; Tính toán ngược lại thông điệp M: k:=1; for i from 1 to d for j from 1 to d m[k]:= M[i][j]; k:=k+1; od; od; 65  Chuyển ngược từ số sang chữ cái dưa vào bảng Alphabet. Người B đã có được thông điệp của người A 2. Cách tấn công mã Hill gốc Hình 4.2 Trường hợp 1: Ta mã hóa: ta có khóa K là ma trận vuông khả nghịch bậc d; và M là ma trận thông điệp; M có số chiều là d×m nếu thông điệp M không đủ d×m thì ta thêm các khoảng trắng cho đủ d×m. Nhưng trong trường hợp thông điệp M có số m = d thì M là ma trận vuông. Như vậy nếu như ta mã hóa thông điệp M = Id C = K × M = K × Id = K Như vậy khi mã hóa như trên thì ta sẽ tính được khóa K và như vậy khóa K không còn an toàn nữa. Trường hợp 2: Ta có ma trận khóa K có kích thước d×d Ta có d vectơ 1, dp p… (d × 1); các plaintext cần mã hóa thì ta thu được d vectơ các ciphertext 1, dc c… (d × 1). Như vậy ta có: ( ) ( )1 1d dp p K c c× =… … . Thông điệp         M  Người gửi          A  Sinh Khĩa K  Sinh khĩa K   Theo pin codes  Người nhận B         Mã hĩa Thông điệp M    C= K ×  M   Sinh khĩa K   Theo pin codes  Thông điệp         M = K‐1× C         Cipher text  66  Như vậy khóa K được tính dễ dàng: ( ) ( )11 1d dK p p c c−= ×… … 3. Cải tiến thuật giải (sinh khóa từ pincodes và chuỗi ngẫu nhiên) Đối với thông điệp có kích thước nhỏ hơn d×(d – 1) Hình 4.3 Người gửi A và người nhận B có chung pincodes. Thuật toán được cải tiến bằng cách thêm chuỗi ngẫu nhiên u. Tại người gửi A: Bước 1: Sinh chuỗi u ngẫu nhiên; kết hợp pincodes đã có với u thành pincodes mới . Bước 2: Từ pincodes mới sinh ra ma trận khóa K như trong phần 1 chương 4. Bước 3: Tính C = K × M Bước 4: Gửi cho người B : C và u. Tại người nhận B: Bước 1: Tính pincodes mới = pincodes + u Bước 2: Từ pincodes mới tính ma trận khóa K như trong phần 1 chương 4. Bước 3: Giải mã tìm thông điệp M: Sinh chuỗi t bất kỳ; Kết hợp pincodes với t bất kỳ Pin codes mới = pincodes + u Thông điệp         M  Người gửi          A  Sinh Khóa K theo Pin codes mới Người nhận B         Mã hĩa Thông điệp M    C= K ×  M  Chuỗi ngẫu nhiên u   Thông điệp         M = K‐1×  C  Nhận được chuỗi u. Tính Pin codes mới = pincodes + u 67  M = K-1 × C Cải tiến thuật toán ở đây là khóa K dùng để mã hóa luôn thay đổi trong mỗi lần mã hóa. Dù ai đó có tính toán được khóa trong một lần mã hóa và giữa để giải mã thông điệp khi bắt được cipher thì không được vì lần mã hóa tiếp theo khóa K cũng đã thay đổi vì chuỗi u được sinh ra là ngẫu nhiên. Như vậy thì giải quyết được trường hợp 2 trong phần 2 (tấn công mã Hill gốc) do d lần mã hóa các vectơ 1, dp p… với d khóa K khác nhau. Nếu M là ma trận đơn vị thì chỉ biết được khóa K và chuỗi ngẫu nhiên u của lần mã hóa đó mà những lần mã hóa khác thì K và u đã thay đổi; như vậy giải quyết trường hợp 1 trong phần 2 (tấn công mã Hill gốc) Đối với thông điệp có kích thước lớn hơn d×(d – 1) Hình 4.4 Tại người A: Chia thông điệp thành k khối mỗi khối có kích thước d×(d – 1); riêng khối k có thể có kích thước nhỏ hơn d×(d – 1). Thông điệp         M  Sinh chuỗi t bất kỳ; Kết hợp pincodes với ui bất kỳ Pin codes mới thứ i= pincodes + ui Người gửi          A  Sinh Khóa Ki theo Pin codes mới Người nhận B         Mã hĩa Thông điệp M    Ci= Ki ×  Mi  Chuỗi ngẫu nhiên ui   Thông điệp         Mi = Ki ‐1×  Ci  Nhận được chuỗi ui. Tính Pin codes mới thứ i = pincodes + ui M=ΣMi  Thông điệp M được chia thành k khối;k – 1 khối có kích thước d×(d – 1); khối k có thể có kích thước nhỏ hơn d×(d – 1) 68  Người A tiến hành mã hóa từng khối tương tự như trong trường hợp mã hóa thông điệp có kích thước nhỏ hơn d×(d – 1) và gửi cho người B. Tại người B: Người B nhận từng khối và tiến hành giải mã từng khối tương tự như trường hợp ở trên. Sau đó ghép các khối lại sẽ có thông điệp ban đầu. Do ta mã hóa từng khối có kích thước nhỏ hơn d×(d – 1) nên sẽ tránh được trường hợp chọn trước văn bản để mã(choosen plaintext). 4. Tính nhanh ma trận khả nghịch của khóa: 1 1 1K U L− − −= × Theo thuật toán ta sinh ma trận K L U= × K khả nghịch; L là ma trận tam giác dưới khả nghịch và U là ma trận tam giác trên khả nghịch. Ma trận K,L,U là ma trận vuông cấp d × d trên p] . Ta đặt ( )1 .1 .nK k k− = … thì ki là nghiệm của hệ phương trình Thì các .ik (vectơ cột) là nghiệm của hệ . .i iK k I× = với .iI là vectơ cột với vị trí thứ i là 1 còn lại là 0. Mà . . . .i i i iK k I L U k I× = ⇔ × × = Ta đặt: . .i i i iU k Y L Y I× = ⇒ × = Nghĩa là ta giải hệ phương trình sau: . i i i i L Y I U k Y × =⎧⎨ × =⎩ Ta gọi: 1i i di Y Y Y ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ # và ta sẽ giải hệ phương trình: 69  1 1 1 1 0 0 0 1 0 0 1 0 1 0 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔ × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎝ ⎠⎝ ⎠ ⎝ ⎠ … # % # # # … … % # # … i i ii i i d di Y l Y L Y I l Y 1 1 2 21 1 2 1 1 2 2 1 1 11 1 12 2 1 1 2 2 21 1 22 2 2 1 2 1 1 2 1 1 2 2 0 0 0 0 1 1 0 0 0 + + + + + + + + + + + + + + + ==⎧ =⎪ + =⎪⎪ =⎪ + + + =⎪ = −⇔ ⇔⎨ + + + =⎪ = −⎪ + + + + =⎪⎪⎪ + + + =⎩ ## … … … # … i i i i i ii i i i i ii i i i i i i i i i i ii i i i i i i i i i i i i ii i i i i i d i d i di Y Y Y l Y Y Y l Y l Y Y Y l l Y l Y l Y Y Y l l l Y l Y l Y l Y Y l Y l Y Y 1 2 1 + + − = ⎧⎪⎪⎪⎪⎪⎪⎨⎪ −⎪⎪⎪ ⎛ ⎞⎪ = −⎜ ⎟⎪ ⎝ ⎠⎩ ∑ # i i i i d di dj ji j i l Y l Y Ta xét hệ phương trình: 11 12 1 1 22 1 0 0 0 1. 0 0 0 − = ⎛ ⎞⎛ ⎞ ⎛ ⎞ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟× = ⇔ × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟ ⎜ ⎟ ⎛ ⎞⎜ ⎟⎜ ⎟ ⎜ ⎟ −⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎜ ⎟⎝ ⎠⎝ ⎠∑ … ## # # … % # … # #% # … d i i i ii ii d dd di dj ji j i u u u k u U k Y u k u k l Y 70  ( ) 1 2 1 1 1 ( 1) 1 ( 1)( 1) 1 1 1 1 1 1 1 1 1 1 11 d di di dj ji j idd dd d d d i d i d d di dj ji dj ji d d j i j id d dd d d d ii ij ji j i ii d i i ij ji j i k Y l Y u u k Y u k l Y l Y u u u u k u k u k u k − = − − − − − − = =− − − − − = + − = ⎛ ⎞= = −⎜ ⎟⎝ ⎠ ⎡ ⎤⎛ ⎞⎛ ⎞ ⎛ ⎞⎡ ⎤= − = − − −⎢ ⎥⎜ ⎟⎜ ⎟ ⎜ ⎟⎜ ⎟⎣ ⎦ ⎢ ⎥⎝ ⎠ ⎝ ⎠⎝ ⎠⎣ ⎦ ⎡ ⎤⇔ = −⎢ ⎥⎣ ⎦ = − ∑ ∑ ∑ ∑ ∑ # 1 1 2 1 1 1 i i d i ij ji j i u k u k u − = ⎧⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪ ⎛ ⎞⎪ ⎜ ⎟⎪ ⎝ ⎠⎪⎪⎪ ⎛ ⎞⎪ = −⎜ ⎟⎪ ⎝ ⎠⎩ ∑ # Như vậy ta có thể tính nhanh ma trận nghịch đảo của K từ L × U. Với ( )1 .iK k− = với .ik là vectơ cột 2 1 1 1 11 . 1 1 2 1 1 1 1 1 1 11 1 1 d ij ji j i di ij ji j i i i di i ij jii ii j i ii d i d d di dj ji dj ji d d j i j i dd d d dj u k u k u k u k u kk k u k k l Y l Y u u u l Y = = − −− = + − − − −= = − − ⎛ ⎞−⎜ ⎟⎝ ⎠ ⎛ ⎞ ⎛ ⎞⎜ ⎟ −⎜ ⎟⎜ ⎟ ⎝ ⎠⎜ ⎟ ⎡ ⎤⎜ ⎟ −= = ⎢ ⎥⎜ ⎟ ⎣ ⎦⎜ ⎟⎜ ⎟⎜ ⎟ ⎡ ⎤⎛ ⎞⎛ ⎞ ⎛ ⎞⎜ ⎟ − − −⎢ ⎥⎜ ⎟⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎢ ⎥⎝ ⎠⎣ ⎦ − ∑ ∑ ∑ ∑ ∑ # # # # 1 1d ji j i ddu − = ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠⎝ ⎠∑ 71  KẾT LUẬN VÀ KIẾN NGHỊ Luận văn đã tập trung khảo sát về mã Ma trận; và khảo sát không gian khóa và đưa ra được tỷ số f(d,m) để đánh giá chọn không gian khóa và không gian Alphabet sao cho tốt nhất. Theo luận văn thì không gian Alphabet tốt nhất thì m(kích thước không gian Alphabet) nên là số nguyên tố. Luận văn cũng đã đưa ra thuật giải sinh khóa, với khóa K = L×U an toàn với L là ma trận tam giác dưới với các phần từ trên đường chéo chính bằng 1 và U là ma trận tam giác trên khả nghịch. Luận văn cũng đưa cải tiến cho mã Ma trận là thêm chuỗi ngẫu nhiên u khi mã hóa để khóa K thay đổi trong những lần mã hóa khác nhau. Và đề xuất khi mã hóa thông điệp thì nên chọn thông điệp có kích thước nhỏ hơn d×(d – 1); với d là kích thước khóa. Tuy nhiên trong luận văn cũng còn nhiều thiếu sót và trong thuật toán sinh khóa K = L×U thì không loại bỏ trực tiếp khóa yếu (K×v=v) mà chỉ loại bỏ được (K là ma trận đối hợp.). Kiến nghị tìm điều kiện L, U sao cho khi tính L×U thì loại bỏ trường hợp khóa yếu là det(L×U – I)≠0 72  TÀI LIỆU THAM KHẢO Key word Hill cipher, Matrix Modular, General Matrix. Tiếng Việt: [1] Dương Anh Đức, Trần Minh Triết (2005), Mã hóa và ứng dụng, Nhà xuất bản Đại học Quốc Gia TPHCM, Thành Phố Hồ Chí Minh. [2] Bùi Xuân Hải, Trần Nam Dũng, Trịnh Thanh Đèo, Thái Minh Đường, Trần Ngọc Hội (2001), Đại số tuyến tính, Nhà xuất bản Đại học Quốc Gia TPHCM, Thành Phố Hồ Chí Minh. [3] Hà Huy Khoái (2003), Mã hóa thông tin cơ sở toán học và ứng dụng, Bộ sách toán cao cấp – Viện Toán Học, Hà Nội [4] Nguyễn Đình Thúc, Bùi Doãn Khanh (2006), Mã hóa – Mật mã, Nhà Xuất Bản Lao Động Xã Hội, Thành Phố Hồ Chí Minh. Tiếng Anh: [5] Carl D Meyer (2000), “Matrix Analysis & Applied Linear Algebra”. [6] Hodges, J. (1958), “The Matrix Equation X2 – I = 0 over a Finite Field”, American Math. Monthly, 65, pp. 518 – 520. 73  [7] Jeffrey Overbey, William Traves, and Jerzy Wojdylo (2005), “On the Keyspace of the Hill Cipher”, Cryptologia, 29(1), pp. 59 – 72. [8] Levine, J., and R.R. Korfhage (1964), “Automorphisms of Abelian Groups Induced by Involutory Matrices, General Modulus”, Duke Math J, 31, pp.631 - 654. [9] Levine, J., and H.M. Nahikian (1962), “On the Construction of Involutory Matrices”, American. Math. Monthly, 69,pp. 267 – 272 . [10] Murray Eisenberg (1999), “Hill Cipher and Modular Linear Algebra”, Mimeographed notes, University of Massachusetts, 19 pages . [11] Tran Ngoc Bao, Nguyen Dinh Thuc (2008), “Modular Matrix Cipher and Its application in Authentication Protocol”, The IEEE 9th ACIS International Conference on Software Engineering, Artifical Intelligence, Networking and Parallel/ Distributed Computing, pp 318 – 323. 74  PHỤ LỤC DEMO THUẬT TOÁN CHƯƠNG 4 BẰNG MAPLE // Khai báo thư viện with(StringTools); with(inttrans); with(Maplets); with(linalg); with(LinearAlgebra); //Viết hàm chuyển đổi từ chữ sang số (trường hợp là số thì giữ nguyên; số 0 chuyển thành số 10) chuyensangso := proc (s) if s = "a" or s = "A" then return 0 end if; if s = "b" or s = "B" then return 1 end if; if s = "c" or s = "C" then return 2 end if; if s = "d" or s = "D" then return 3 end if; if s = "e" or s = "E" then return 4 end if; if s = "f" or s = "F" then return 5 end if; if s = "g" or s = "G" then return 6 end if; if s = "h" or s = "H" then return 7 end if; if s = "i" or s = "I" then return 8 end if; if s = "j" or s = "J" then return 9 end if; if s = "k" or s = "K" then return 10 end if; if s = "l" or s = "L" then return 11 end if; if s = "m" or s = "M" then return 12 end if; 75  if s = "n" or s = "N" then return 13 end if; if s = "o" or s = "O" then return 14 end if; if s = "p" or s = "P" then return 15 end if; if s = "q" or s = "Q" then return 16 end if; if s = "r" or s = "R" then return 17 end if; if s = "s" or s = "S" then return 18 end if; if s = "t" or s = "T" then return 19 end if; if s = "u" or s = "U" then return 20 end if; if s = "v" or s = "V" then return 21 end if; if s = "w" or s = "W" then return 22 end if; if s = "x" or s = "X" then return 23 end if; if s = "y" or s = "Y" then return 24 end if; if s = "z" or s = "Z" then return 25 end if; if s = "." then return 26 end if; if s = "?" then return 27 end if; if s = " " then return 28 end if; if s = "1" then return 1 end if; if s = "2" then return 2 end if; if s = "3" then return 3 end if; if s = "4" then return 4 end if; if s = "5" then return 5 end if; if s = "6" then return 6 end if; if s = "7" then return 7 end if; if s = "8" then return 8 end if; if s = "9" then return 9 end if; if s = "0" then return 10 end if; 76  end proc; // Viết hàm chuyển từ số thành chữ(trong ví dụ này chỉ mã hóa chữ không mã hóa số) chuyensangchu := proc (t) if t = 0 then return "A" end if; if t = 1 then return "B" end if; if t = 2 then return "C" end if; if t = 3 then return "D" end if; if t = 4 then return "E" end if; if t = 5 then return "F" end if; if t = 6 then return "G" end if; if t = 7 then return "H" end if; if t = 8 then return "I" end if; if t = 9 then return "J" end if; if t = 10 then return "K" end if; if t = 11 then return "L" end if; if t = 12 then return "M" end if; if t = 13 then return "N" end if; if t = 14 then return "O" end if; if t = 15 then return "P" end if; if t = 16 then return "Q" end if; if t = 17 then return "R" end if; if t = 18 then return "S" end if; if t = 19 then return "T" end if; if t = 20 then return "U" end if; 77  if t = 21 then return "V" end if; if t = 22 then return "W" end if; if t = 23 then return "X" end if; if t = 24 then return "Y" end if; if t = 25 then return "Z" end if; if t = 26 then return "." end if; if t = 27 then return "?" end if; if t = 28 then return " " end if ; end proc; //Sinh chuỗi ngẫu nhiên có chiều dài d sinhchuoingaunhien := proc (d) return Random(d, 'upper') end proc; // Số lần lặp hàm băm pinccodes đủ để tạo ma trận d × d solanlapdesinhchuoitupincodes := proc (d) local temp; temp := iquo(d*(d+1), 64); if temp < 1 then return 1 else temp+1; end if; end proc; // Hàm băm pincodes với số lần được tính ở trên hambampincodestaomatran := proc (d, pincodes) local t, i, S; if solanlapdesinhchuoitupincodes(d) = 1 then return Hash(pincodes) else t := Hash(pincodes); 78  for i to solanlapdesinhchuoitupincodes(d) do S := cat(S, t); t := cat(t, Hash(S)) end do; return t; end if; end proc; //Tạo ma trận tam giác dưới L taomatrantamgiacduoi := proc (d, S, p) local i, j, k, T; T := Matrix(d); for j to d do T[j, j] := 1; end do; k := 1; for i from 2 to d do for j to i-1 do k := k+1; T[i, j] := chuyensangso(S[k]); end do; end do; return T mod p; end proc; L := taomatrantamgiacduoi(10, hambampincodestaomatran(10, "thanhDMZUEVXNZNRUOZYPUSJE"), 31); 79  //Tạo ma trận tam giác trên U taomatrantamgiactren := proc (d, S, p) local i, j, k, U, V, T; U := Matrix(d); k := length(S); T := 1; for i to d-1 do U[i, i] := chuyensangso(S[k]); k := k-1; if U[i, i] = 0 then U[i, i] := U[i, i]+1 end if; T := T*U[i, i] end do; U[d, d] := chuyensangso(S[k]); k := k-1; while T*U[d, d] = 1 or T*U[d, d] = p-1 do U[d, d] := U[d, d]+1 end do; for i to d-1 do for j from i+1 to d do U[i, j] := chuyensangso(S[k]); k := k-1 80  end do end do; return U mod p end proc; U := taomatrantamgiactren(10, hambampincodestaomatran(10, "thanhE"), 29); //Sinh Khóa K Sinhkhoa := proc (d, pincodes, p) local L, U, K; L := taomatrantamgiacduoi(d, hambampincodestaomatran(d, pincodes), p); U := taomatrantamgiactren(d, hambampincodestaomatran(d, pincodes), p); K := `mod`(MatrixMatrixMultiply(L, U), p); while det(K-Indentity(d)) = 0 do pincodes := cat(pincodes, "1"); L := taomatrantamgiacduoi(d, hambampincodestaomatran(d, pincodes), p); U := taomatrantamgiactren(d, hambampincodestaomatran(d, pincodes), p); K := `mod`(MatrixMatrixMultiply(L, U), p); 81  end do; return K end proc; K := Sinhkhoa(10, "thanh", 29);print(); //Người A tiến hành mã hóa và gởi cho B nguoiAgui := proc (Message, d, pincodes) local kq, a, i, M, j, K, p, l, b, X, Messagenew; a := iquo(length(Message), d); b:=0; c:=length(Message) – d; if c<0 then b:=abs(c); else b:=(a+1).d – length(Message); end if; X := Random(b, " "); Messagenew := cat(Message, X); a := iquo(length(Messagenew), d); M := Matrix(d, a); 82  l := 1; p := 29; for i to d do for j to a do M[i, j] := chuyensangso(Messagenew[l]); l := l+1; end do; end do; K := Sinhkhoa(d, pincodes, p); kq := MatrixMatrixMultiply(K, M) mod p; return kq; end proc; X := nguoiAgui("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 10, "thanh"); //Người B giải mã và tìm được thông điệp nguoiBgiaima := proc (Cipher, d, pincodes) local i, j, p, kq, temp, c, k, K; p := 29; K := Sinhkhoa(d, pincodes, p); temp := MatrixMatrixMultiply(MatrixInverse(K), Cipher) mod p; 83  c := coldim(temp); kq := " "; k := 0; for i to d do for j to c do kq := Insert(kq, k, chuyensangchu(temp[i, j])); k := k+1; end do; end do; return kq; end proc; D1 := nguoiBgiaima(X, 10, "thanh"); //Cải tiến thuật toán với thêm một chuỗi ngẫu nhiên u và kết hợp với pincodes tạo thành pincodes mới và dùng pincodes mới sinh khóa, khi gởi ma trận đã mã hóa thì dấu chuỗi ngẫu nhiên u vào cột cuối và hàng cuối của ma trận nguoiAguicaitien := proc (Message, d, pincodes) local kq, a, i, M, j, K, p, l, b, X, Messagenew, u, kqcaitien, pincodesmoi; a := iquo(length(Message), d); b:=0; c:=length(Message) – d; if c<0 then b:=abs(c); else b:=(a+1).d – length(Message); end if; X := Random(b, " "); 84  Messagenew := cat(Message, X); a := iquo(length(Messagenew), d); M := Matrix(d, a); l := 1; p := 29; for i to d do for j to a do M[i, j] := chuyensangso(Messagenew[l]); l := l+1; end do; end do; u := sinhchuoingaunhien(d+a+1); pincodesmoi := cat(pincodes, u); K := Sinhkhoa(d, pincodesmoi, p); kq := MatrixMatrixMultiply(K, M) mod p; kqcaitien := Matrix(d+1, a+1); for i to d do for j to a do kqcaitien[i, j] := kq[i, j]; end do; end do; for i to d do kqcaitien[i, a+1] := chuyensangso(u[i]); end do; kqcaitien[d+1, a+1] := chuyensangso(u[d+1]); for i to a do kqcaitien[d+1, i] := chuyensangso(u[1+i+d]);  end do; return kqcaitien; 85  end proc; Xcaitien1 := nguoiAguicaitien("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 9, "thanh"); //Người B tiến hành mã hóa Xcaitien2 := nguoiAguicaitien("Lop Cao hoc dam bao toan hoc cho may tinh va he thong tinh toan", 9, "thanh"); 86  >   87  //Người B tiến hành giải mã nguoiBgiaima := proc (Cipher, d, pincodes) local i, j, p, kq, temp, c, k, K, u, demu, rC, cC, pincodesmoi, Ciphermoi; p := 29; rC := rowdim(Cipher); cC := coldim(Cipher); demu := 0; u := " "; for i to rC do u := Insert(u, demu, chuyensangchu(Cipher[i, cC])); demu := demu+1 end do; for i to cC-1 do u := Insert(u, demu, chuyensangchu(Cipher[rC, i])); demu := demu+1 end do; demu := length(u); u := Delete(u, demu .. demu); pincodesmoi := cat(pincodes, u); K := Sinhkhoa(d, pincodesmoi, p); Ciphermoi := Matrix(rC-1, cC-1); for i to rC-1 do for j to cC-1 do 88  Ciphermoi[i, j] := Cipher[i, j]; end do; end do; temp := MatrixMatrixMultiply(MatrixInverse(K), Ciphermoi) mod p; c := coldim(temp); kq := " "; k := 0; for i from 1 to d do for j from 1 to c do kq := Insert(kq, k, chuyensangchu(temp[i, j])); k := k+1; end do; end do; return kq; end proc; nguoiBgiaima(Xcaitien2, 9, "thanh"); nguoiBgiaima(Xcaitien1, 9, "thanh"); Xcaitien3 := nguoiAguicaitien("Waiter Why is this key in my soup? What do you think of it? Sir I am very happy replied the waiter I have looked for it everywhere from yesterday. Thank you very much Thank you very much It is lucky that you did not swallow up it.", 9, "thanh"); print(); # input placeholder 89  nguoiBgiaima(Xcaitien3, 9, "thanh");print(); # input placeholder timetinh3 := time()-starttime3;print(); # input placeholder starttime4 := time();print(); # input placeholder Xcaitien4 := nguoiAguicaitien("The association said up to fourty percent of garment export orders for the remaining months of the year are from Japan. Under the Economic Partnership Agreement Vietnam has textile and garment products shipped to Japan will enjoy tax exemptions starting next month. Nguyen Hong Trang general director of lingerie producer Son Kim said the agreement will absolutely bring more orders to local exporters. Trang said her company plans to build a new factory next year to meet the rising demand from Japan. Pham Xuan Hong general director of Saigon three Garment Company said the agreement would benefit Japanese importers who would then offer to pay Vietnamese producers more. Saigon three Garment the largest Vietnamese jeans exporter to Japan said it has even received many orders for the first half of next year. But exporters also said it would be hard to boost shipments to Japan sharply even with the free trade agreement because they have to meet many strict requirements. Hong said his company used to offer a wide range of products. Now it only focuses on making jeans and khaki trousers for the Japanese market as it is the only way to ensure standard and output he said. Son Kim has Trang said exports to Japan are unlikely to advance suddenly since the market has set many strict standard barriers that many Vietnamese companies may find hard to 90  overcome.Japan is one of Vietnam is biggest export markets but Vietnamese products still hold a small share there accounting for only one percent of total Japan is imports according to the Ministry of Industry. About nine percent of Vietnamese export products to Japan would be exempted from tariffs within ten years under the Vietnam Japan Economic Partnership Agreement which the Japanese House of Councilors approved on June twenty four The association said up to fourty percent of garment export orders for the remaining months of the year are from Japan. Under the Economic Partnership Agreement Vietnam has textile and garment products shipped to Japan will enjoy tax exemptions starting next month. Nguyen Hong Trang general director of lingerie producer Son Kim said the agreement will absolutely bring more orders to local exporters. Trang said her company plans to build a new factory next year to meet the rising demand from Japan. Pham Xuan Hong general director of Saigon three Garment Company said the agreement would benefit Japanese importers who would then offer to pay Vietnamese producers more. Saigon three Garment the largest Vietnamese jeans exporter to Japan said it has even received many orders for the first half of next year. But exporters also said it would be hard to boost shipments to Japan sharply even with the free trade agreement because they have to meet many strict requirements. Hong said his company used to offer a wide range of products. Now it only focuses on making jeans and khaki trousers for the Japanese market as it is the only way to ensure standard and output he said. Son Kim has Trang said exports to Japan are unlikely to advance suddenly since the market has set many strict standard barriers that many Vietnamese companies may find hard to overcome.Japan is one of Vietnam is biggest export markets but Vietnamese products still hold a small share there accounting for only one percent of total Japan is imports according to the Ministry of Industry. About nine percent of Vietnamese export products to Japan would be exempted from tariffs within ten years under the Vietnam Japan Economic Partnership Agreement which the Japanese House of Councilors approved on June twenty four", 9, "thanh");print(); # input placeholder 91  nguoiBgiaima(Xcaitien4, 9, "thanh");print(); # input placeholder timetinh4 := time()-starttime4;