Luận văn 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 toång tröïc tieáp nhö sau: 0 0 A A B B ⎛ ⎞⊕ = ⎜ ⎟⎝ ⎠ Ñònh lyù 8: (Theo [9]) Neáu F laø tröôøng coù ñaëc soá 2, thì ñieàu kieän caàn vaø ñuû ñeå ma traän vuoâng nxn H laø ma traän ñoái hôïp vôùi 10 2 s n< ≤ , 2 2nH I Q P= + × sao cho 2Q laø ma traän n×s coù haïng laø s vaø ma traän 2P laø ma traän s×n vaø coù haïng laø s sao cho 2 2 ,0s sP Q× = (do s < n neân luoân toàn taïi 2Q sao cho 2 2 ,0s sP Q× = ) Chöùng minh Ñieàu kieän ñuû: 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 Ñieàu kieän caàn: Ta ñaët 11H Q J Q −= × × ; vôùi Q laø ma traän khaû nghòch baát kyø treân p] Ta ñaët ( )/ /1 2Q Q Q= ; vôùi /2Q laø ma traän coù kích thöôùc 2n s× Vaø ñaët / 1 1 / 2 P Q P − ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; vôùi /2P laø ma traän coù kích thöôùc 2s n× Ta coù: ( ) /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) vaø (2.24), ta coù: ( ) = − × + × × + × − × / / / / 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 Ñaët ( )−= − = …2 2 2 .1 .3 .2 10, ,0, ,0, ,0,s s s sL K I i i u Vôùi 0 laø vectô coät 0 vaø . ji laø vectô coät thöù j trong ma traän ñôn vò. ( )−× = …/2 2 .1 .3 .2 10, ,0, ,0, ,0,s sQ L q q q vôùi . jq laø coät thöù j trong ma traä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 laø doøng thöù j trong ma traän / 2P . Nhö vaäy ta chæ söû duïng coät leû trong /2Q vaø doøng chaün trong / 2P . Ta ñaët ( )× − × = ×/ /2 2 2 2 2 2s sQ K I P Q P Töø (2.23) ta coù: 2 2 ,s sP Q Z× = vì doøng chaün trong laø vectô 0 „ Ví duï: Xaây döïng ma traän ñoái hôïp treân 2] : n=3; s=2 2 1 0 1 1 0 1 P ⎛ ⎞= ⎜ ⎟⎝ ⎠ ; 2 Q ñöôïc xaây döïng baèng caùch giaûi heäđ 40  2 1 2 2 0 0 0 0 P X P X ⎧ ⎛ ⎞=⎪ ⎜ ⎟⎪ ⎝ ⎠⎨ ⎛ ⎞⎪ = ⎜ ⎟⎪ ⎝ ⎠⎩ vôùi ( )2 1 2Q X X= Laàn löôït giaûi caùc heä 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 traän ñoá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 lyù 9: Cho hai ma traän A,B coù kích thöôùc laàn löôït laø r × s vaø s × r vôùi caùc phaàn töû ñöôïc choïn tuøy yù treân vaønh giao hoaùn coù ñôn vò thì ma traän M coù kích thöôùc laø n×n sao cho n= r+s thì M ñöôïc xaây döïng nhöng sau thì M laø ma traän ñoái hôïp: 2 s r BA I B M A ABA I AB −⎛ ⎞= ⎜ ⎟− −⎝ ⎠ (2.25) Ñònh lyù 10: (Veà ma traän ñoái hôïp) 1. A laø ma traän ñoái hôïp neáu vaø chæ neáu 1A A−= 2. Neáu A laø ma traän ñoái hôïp thì ( )1 2 B I A= + laø ma traän luõy ñaúng. 41  3. Ñònh thöùc cuûa ma traän ñoái hôïp A treân tröôøng p] laø 1 hoaëc p –1 Chöùng minh: 1. (⇒ ) A laø ma traän ñoái hôïp neân A.A = I . goïi A’ laø ma traän nghòch ñaûo cuûa A thì ta coù A.A’=A’.A=I. do ñoù A=A’= 1A− (⇐) Ta coù 1A A−= A. 1A− =I (ñònh nghóa) Suy ra A.A=I . Vaäy A laø ma traän ñoá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+ + = + = + = „ Boå ñeà 5 (vaønh ma traän) : Cho n laø soá nguyeân lôùn hôn hoaëc baèng 1. Thì taäp hôïp caùc ma traän n×n coù caùc phaàn töû treân tröôøng p] vôùi hai pheùp toaùn coäng vaø nhaân ma traän taïo thaønh moät vaønh. Boå ñeà 6: A laø ma traän ñoái hôïp treân tröôøng p] thì moät soá ma traän deã thaáy laø caùc daï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 vaø 0 < s < n 42  4. ,21 2 , 2 r r s s r s I Z J Z K ⎛ ⎞= ⎜ ⎟⎝ ⎠ vôùi r+2s = n vaø 0 < s ≤ 1 2 n vaø K2s laø toång tröïc tieáp cuûa s ma traän 1 1 0 1 ⎛ ⎞⎜ ⎟⎝ ⎠ Nhaän xeùt: Ma traän ñoái hôïp treân tröôøng ] p hoaëc ]2 laø ma traän tam giaùc treân vôùi 1; p – 1 treân ñöôøng cheùo chính vaø 1 hoaëc 0 trong taát caû caùc phaàn töû phía treân ñöôøng cheùo chính. Ñònh thöùc cuûa ma traän ñoái hôïp A laø baèng 1 hoaëc p – 1 6.1.2. Ñeám soá ma traän ñoái hôïp [Theo 6] Ñeám soá ma traän ñoái hôïp (involutory) baäc d×d treân p] Ñaët ( ) 0 t t i t i g p p = = −∏ laø soá ma traän khaû nghòch baäc t treân tröôøng p] Tröôøng hôïp p > 2 Ñaët ( )0 ,N d t laø soá ma traän X caáp d × d thoûa 2 0X I− = Neáu X laø ma traän coù det(xI – X) coù ña thöùc ñaëc tröng maø coù t nghieäm laø 1 vaø d – t nghieä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≤ ≤ Ñaët ( )0 ,S d t laø soá ma traä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 traän X trong ( )0 ,S d t laø khaùc nhau) 43  Q laø ma traän khaû nghòch baäc m treân p] sao cho 1−× ×Q J Q ; thì ( )1 mod −× × ≡MQ J Q J p . Neáu 1−× × =Q J Q J thì Q J J Q× = × . Ñaët ( )0 ,C d t laø soá ma traän Q sao cho thoûa Q vaø J giao hoaùn. Ta coù: ( ) ( )0 0, ,dg C d t S d t= Do Q J J Q× = × neâ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 ñoù soá ma traän ñoái hôïp treân p] laø: ( )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] Ñaët X laø ma traän caáp d×d; X laø ma traän thoûa maõn: 2 0X I− = treân 2] . Töông töï tröôøng hôïp treân thì (mod ) M tX J p≡ vôùi tJ ñöôïc ñònh nghóa trong 6.1.1 phaàn b. Ñaët ( ),eS d t laø toång soá ma traän X sao cho (mod )M tX J p≡ vôùi 0 2t d≤ ≤ Ta coù: ( ) ( ) 0 , , = = ∑de e t N d t S d t ; 0 2≤ ≤t d (do ma traän X trong ( ),eS d t laø khaùc nhau) Ñaët ( ),eC d t laø soá löôïng ma traän khaû nghòch Q baäc d treân 2] thoûa maõn t tJ Q Q J× = × . Ta coù: ( ) ( ), ,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 xeùt tröôøng hôïp f(d,29) vôùi d trong khoaûng 2 ñeán 30 Hình 2.3 Quan saùt hình 2.3 ta thaáy vôùi khoaûng d thay ñoåi töø 2 ñeán 30 thì caùc f(d,29) coù xu höôùng baèng nhau. Töø (2.26) vaø (2.5). Ta ñaët g(t) tyû soá giöõa toång ma traän ñoái hôïp trong (2.26) vaø toång soá ma traän khaû nghòch trong (2.5);ta xeùt treâ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 − = = − =∏ YÙ nghóa cuûa g(t) caøng nhoû thì caøng toát vì luùc ñoù seõ coù tyû leä khoùa yeáu laø ít nhaát. Ta xeùt tröôøng hôïp d trong khoaûng töø 2 ñeán 5 Hình 2.4 Quan saùt hình 2.4 ta thaáy vôùi d=2 lôùn thì g(t)= 0.0012, coøn d töø 3 trôû leân thì g(t) caøng tieán veà 0. Nhö vaäy khi sinh khoùa thì kích thöôùc khoùa caøng lôùn thì tyû leä khoùa yeáu caøng ít. 6.2. K laø khoùa yeáu vôùi K×v = v hoaëc v×K = v: Ta xeùt khoùa laø ma traän vuoâng d×d khaû nghòch treân p] 6.2.1. Xaùc ñònh khoùa yeáu baèng ñònh thöùc Vôùi caùch maõ hoùa: K×v = v thì K ñöôïc goïi laø khoùa yeá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ì heä (2.29) coù nghieäm duy nhaát laø nghieäm taàm thöôøng 0 0 ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ # det(K – I) = 0 thì heä (2.29) coù voâ soá nghieäm hoaëc voâ nghieäm, nhöng do heä luoân coù nghieäm taàm thöôøng neân khi det(K – I) = 0 thì heä (2.29) voâ soá nghieäm. Nhöng do treân ] p coù höõu haïn phaàn töû heä (2.29) cuõng coù höõu haïn nghieäm. Ví duï: Treân 11] 2 3 2 7 K ⎛ ⎞= ⎜ ⎟⎝ ⎠ , coù det K ≠ 0 nhöng det(K – I) = 0 Veùc tô daï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 haïn phaàn töû neân v cuõng thuoäc taäp nghieäm höõu haïn Neáu thoâng ñieäp M maø ta caàn maõ hoùa sau khi chuyeån thaønh daïng ma traän coù caùc coät laø caùc nghieäm trong taäp treân thì K×M=M Vôùi 2 9 7 3 8 5 M ⎛ ⎞= ⎜ ⎟⎝ ⎠ Thì khi maõ hoùa: 47  2 3 2 9 7 2 9 7 2 7 3 8 5 3 8 5 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= × = × =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎝ ⎠ ⎝ ⎠ ⎝ ⎠C K M Cipher text seõ baèng plaintext; nhö vaäy khi maõ hoùa khoùa yeáu nhö treân thì ngöôøi ta seõ bieát ñöôïc plaintext. Vôùi caùch maõ hoùa: v×K = v thì K ñöôïc goïi laø khoùa yeá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ì heä (2.30) coù nghieäm duy nhaát laø nghieäm taàm thöôøng. det(KT – I) = 0 thì heä (2.30) coù voâ soá nghieäm hoaëc voâ nghieäm, nhöng do heä luoân coù nghieäm taàm thöôøng neân khi det(KT – I) = 0 thì heä (2.30) coù voâ soá nghieäm. Nhöng do treân ] p coù höõu haïn phaàn töû heä (2.30) cuõng coù höõu haïn nghieäm. Ta coù nhaän xeùt: 1/ Treân tröôøng ] p vôùi m laø soá nguyeân döông thì moät khoùa K goïi laø yeáu khi vaø chæ khi det ( K – I ) = 0 vôùi caùch maõ K×v = v. 2/ Treân tröôøng ] p vôùi m laø soá nguyeân döông thì moät khoùa K goïi laø yeáu khi vaø chæ khi det ( KT – I ) = 0 vôùi caùch maõ v×K = v 6.2.2. Xaùc ñònh khoùa yeáu baèng trò rieâng Ñònh nghóa: Cho A laø ma traän vuoâng d×d vaø c ∈ p] Ñaët { }/n T TcE X AX cX= ∈ =\ c ñöôïc goïi laø trò rieâng vaø cE ñöôïc goïi laø khoâng gian rieâng öùng vôùi trò rieâng 48  Vôùi moãi { }\ 0cEα ∈ thì α laø vec tô rieâng öùng vôùi trò rieâng c Ta ñaët ( ) ( )detA nP x cI A= − goïi laø ña thöùc ñaëc tröng cuûa A Meänh ñeà (Moái lieân heä giöõa trò rieâng vaø ña thöùc ñaëc tröng) Neáu c laø trò rieâng treân p] cuûa A thì ( )AP c =0 treân p] Suy ra neáu muoán tìm trò rieâng thì ta tìm taát caû caùc nghieäm cuûa ( )AP x treân p] Tính chaát cuûa trò rieâng vaø vectô rieâng: 1. Neáu c = 0 thì ma traän A khoâng khaû nghòch 2. Neáu A laø ma traän tam giaùc treân vaø ma traän tam giaùc döôùi, ma traän ñöôøng cheùo thì trò rieâng laø nhöng phaàn töû treân ñöôøng cheùo chính. 3. A vaø AT coù cuøng trò rieâng. 4. Transition matrix thì luoân coù trò rieâng laø 1 Trasition matrix coù tính chaát laø taát caû caùc haøng coù toång laø 1 Ví duï: Xeùt ma traän coù trò rieâng laø 1 treân 7] 1 2 5 4 4 0 3 2 3 A ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Ta tính trò rieâ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 coù trò rieâng laø 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 coù nhaän xeùt: Neáu trò rieâng ma traän vuoâng A coù trò rieâng laø 1 thì toàn taïi nhöõng vectô rieâng X sao cho × =T TK X X . Muoán tìm ñöôïc XT thì ta phaûi giaû heä phöông trình tuyeán tính. Moät khoùa laø ma traän khaû nghòch nhöng khoâng yeáu thì ma traän coù caùc giaù trò rieâng phaûi khaùc 1. ÔÛ ñaây ta coù theå xeùt moät tröôøng hôïp laø loaïi nhöõng ma traän Trasition matrix coù tính chaát laø taát caû caùc haøng coù toång laø 1. Ta xeùt ñònh thöùc thì: det(K – I) ≠ 0 vaø det(KT – I) ≠ 0 50  7. Toùm taét Maõ ma traän baäc d khi ta maõ hoùa caàn khoùa laø ma traän vuoâng khaû nghòch treân m] , m baát kyø. ÔÛ ñaây khoâng gian caùc chöõ caùi(Alphabet) laø m neân laø soá nguyeân toá vaø soá chieàu d cuûa ma traän khoùa neân lôùn ñeå haïn cheá khoùa yeáu. Tröôøng hôïp caùc khoùa yeáu thì ta coù ma traän ñoái hôïp (involutory matrix) ñoái vôùi tröôøng hôïp naøy thì khi ta xaây döïng ma traän K = L × U thì ta chæ caàn xaây döïng ma traän K sao detK ≠ 1 vaø p – 1 Tröôøng hôïp K×v = v thì ta xaây döïng ma traän K coù det(K – I) ≠ 0. 51  Chöông 3 XAÂY DÖÏNG THUAÄT GIAÛI SINH KHOÙA CHO MAÕ HILL 1. Ñònh lyù sinh khoùa treân p] (1) 11 1 1 0 0 0 0 + ⎛ ⎞⎜ ⎟⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠ … # % # % # # % … … … tt tt d dt dd l l L l l l l khaû 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 khaû nghòch ⇔ ( ) 1 0 mod p = ≠∏d ii i u (3.2) (3) K L U= × khaû nghòch khi vaø chæ khi L,U khaû nghòch (3.3) (4) K khaû nghòch ⇒ P×K cuõng khaû nghòch vôùi P laø ma traän hoaùn vò Vôùi P laø ma traän hoaùn vò ñöôïc ñònh nghóa nhö sau: ( ) 1 2 nk k k P e e e= … vôùi ik e laø caùc haøng trong ma traän ñôn vò. ( )ijP p= vôùi 1 neáu 0 ngöôïc laï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ì khoâng toàn taïi ma traän L1; U1 sao cho L≠L1(L1 laø ma traän tam giaùc treân vôùi ñöôøng cheùo chính goàm caùc phaàn töû 1) vaø U≠U1 thì L×U=L1×U1 (6) Vôùi ma traän K khaû nghòch treân p] thì luoân toàn taïi ma traän P, L,U (vôùi ma traän L laø ma traän tam giaùc treân sao cho caùc ñöôøng cheùo chính laø 1)khaû nghòch treân p] sao cho K= P×L×U (theo [5, trang 153]) Chöùng minh Chöùng minh (5) Khoâng toàn taïi ma traän L1, U1 (vôùi L1 laø ma traän tam giaùc döôùi coù ñöôøng cheùo chính laø 1)sao cho L1≠L vaø U1≠U maø K = L1 × U1 Chöùng minh: Ta xeùt treân p] ; vôùi 1 1K L U= × . Ta giaû söû ta coù 2 2K L U= × Luùc naøy ta coù 1 1 2 2L U L U× = × . Do K khaû nghòch neân 1 2,U U khaû nghòch. Ta coù: 1 11 1 2 2 2 1 2 1L U L U L L U U − −× = × ⇔ × = × (3.6) Do 2L laø ma traän tam giaùc döôùi neân 1 2L − cuõng laø ma traän tam giaùc döôùi. Suy ra 1 2 1L L − × laø ma traän tam giaùc döôùi. Töông töï thì 1U laø ma traän tam giaùc treân neân 1 1U − laø ma traän tam giaùc treân. Suy ra 12 1U U −× laø ma traän tam giaùc treân. Töø (3.6) thì veá traùi laø ma traän tam giaùc döôùi vaø veá phaûi laø ma traän tam giaùc treân 53  1 12 1 2 1L L U U − −× = × = D (3.7) Vôùi D laø ma traän ñöôøng cheùo. Do 12 1;L L − coù caùc lii laø 1 neân D laø ma traän ñôn vò. Töø (3.7) ta coù: 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 laø ma traän vuoâng caáp d khaû nghòch treân p] ; thì K cuõng khaû nghòch treân\ . Theo [5, trang 153] thì toàn taïi ma traän ( ), , ,P L U M d∈ \ sao cho K P L U= × × . Do K khaû nghòch treân p] , neân P L U× × cuõng khaû nghòch treân p] ; suy ra L, U khaû nghòch treân p] . Vaäy vôùi K khaû nghòch treân p] thì toàn taïi ma traän L, U khaû nghòch treân p] sao cho K P L U= × × „ 2. Xaùc ñònh cơ sở hình thaønh thuaät giaûi Ta sinh ra hai ma traän L vaø U treâ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 Khoù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 traän U phaûi khaû nghòch: 11 1 0 d i u = ≠∏ Ñeå ma traän khoùa K khoâng laø khoùa yeáu thì ma traän khoùa K phaûi thoûa laø: K khoâng laø ma traän ñoái hôïp (Involutory matrix) nghóa laø 11 1 1 vaø 1 d i u p = ≠ −∏ Ñoái vôùi tröôøng hôïp khoùa yeáu K v v× = thì ta xeùt det(K – I) phaûi khaùc 0. Vôùi muïc (5) trong phaàn 1 cuûa chöông naøy thì vôùi moät boä (L,U) seõ coù moät khoùa K neân khi ta xaùc ñònh toång soá khoùa K coù theå sinh ra baèng thuaät giaûi thì baèng soá löôïng ma traän L nhaân vôùi soá löôïng ma traän U. Vôùi muïc (6) cuûa phaàn 1 cuûa chöông naøy thì ta coù nhaän xeùt laø vôùi K khaû nghòch thì ta luoân coù K = P × L ×U neân khoâng gian khoùa maø ta sinh baèng boä L×U thì ñaûm baûo khoâng gian sinh ra gaàn baèng khoâng gian ma traän vuoâng khaû nghòch. 3. Thuaät giaûi: Ta phaûi xaùc ñònh tröôùc p] vôùi p laø soá nguyeân toá; laø khoâng gian baûng caùc chöõ caùi. Böôùc 1: Ta seõ phaùt sinh ma traän tam giaùc treân U sao cho U phaûi thoûa moät soá tính chaát sau: U phaûi khaû nghòch nghóa laø: 1 0 d ii i u = ≠∏ det(K) ≠ 1 vaø p – 1 nghóa laø: det(U) ≠ 1 vaø p – 1 ⇔ 1 1 vaø 1 d ii i u p = ≠ −∏ 56  Böôùc 2 : Ta seõ phaùt sinh ma traän tam giaùc döôùi L sao cho caùc phaàn töû treân ñöôøng cheùo chính baèng 1. Böôùc 3 : Ta tính khoùa K L U= × Böôùc 4: Tính det(K – I). Neáu det(K – I) = 0 thì ta quay laïi böôùc 2 tính laïi ma traän L. Neáu det(K – I) ≠ 0 thì ta tieáp böôùc 5. Böôùc 5: Ta seõ hoaùn vò khoùa K ñeå khoùa K trôû neân an toaøn hôn môùiK P K= × Vôùi P laø ma traän hoaùn vò. 4. Ví duï: Ta xeùt treân tröôøng 29] ; ta seõ sinh khoùa coù baäc laø 4 Böôùc 1: Ta sinh ma traän tam giaùc döôùi L baát kyø sao cho caùc ñöôøng cheùo chính baèng 1. 1 0 0 0 2 1 0 0 6 4 1 0 5 3 0 1 ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ L Böôùc 2: Ta phaùt sinh ma traän tam giaùc treân U baát kyø khaû nghòch vaø thoû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 khoù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: Kieåm tra K coù laø khoùa yeáu khoâng? Tính : det (K – I) =18 ≠ 0 Neân K laø khoùa maø ta chaáp nhaän ñöôïc (khoâng yeáu) Chaáp nhaän laø khoùa vaø chuyeån sang böôùc 5. Böôùc 5: Ta coù theå hoaùn vò ma traän khoùa vöøa phaùt sinh Ví duï: 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0 P ⎛ ⎞⎜ ⎟⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ Nhö vaäy khoùa môùi laø: 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. Khaûo saùt khoâng gian khoùa vöøa sinh theo thuaät giaûi Ta xeùt treân p] vôùi p laø soá nguyeân toá Ta sinh khoùa K laø ma traän vuoâng khaû nghòch d×d Soá ma traän khaû nghòch treân p] laø : ( )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 −− = = = − = −∏ ∏ vaø 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ö vaäy soá ma traän khoùa laø soá ma traän khaû nghòch treân p] tröø ñi soá ma traän khoùa yeáu. Ma traän tam giaùc döôùi L vaø ma traän tam giaùc treân U baäc d coù ( )1 2 d d + coù theå khaùc 0. Theo thuaät giaûi treân thì soá ma traän tam giaùc döôùi L laø ( )1 2 d d d p + − (3.13) Theo thuaät giaûi treân thì soá ma traän U, khi ta xaây döïng thì treân ñöôøng cheùo chính coù d – 1 phaàn töû choïn sao cho khaùc 0. Phaàn töû udd seõ phuï thuoäc caùc phaàn töû tröôùc sao cho tích caùc ñöôøng cheùo chính khaùc 1. Vaäy ta coù ( ) 11 dp −− caùch choïn phaàn töû treân ñöôøng cheùo chính. Caùc phaàn töû coøn laïi choïn baát kyø neân ta coù: 59  ( )1 2 d d d p + − caùch choïn. Vaäy soá ma traän tam giaùc treân U laø: ( ) ( )11 21 d d ddp p + −−− (3.14) Vaäy soá löôïng ma traän khoùa K = L × U coù theå laø: ( ) ( ) ( ) ( ) 21 11 12 21 1d d d dd dd d d dp p p p p+ +− −− − −− = − (3.15) 60  Chöông 4: CAÙC VAÁN ÑEÀ LIEÂN QUAN ÑEÁN MAÕ HILL Moâ taû: Ngöôøi A vaø ngöôøi B trao ñoåi thoâng tin cho nhau; söû duïng maõ hoùa ñoái xöùng vaø cuï theå laø maõ ma traän. A vaø B seõ coù khoùa bí maät laø ma traän; vaø aùp duïng thuaät toaùn maõ hoùa theo ma traän ñeå maõ hoùa thoâng ñieäp M vaø chuyeån cho B. B seõ söû duïng khoùa bí maät ñeå giaûi maõ vaø tính toaùn ñöôïc M. 1. Sinh khoùa theo pincodes Hình 4.1 Ngöôøi göûi A seõ coù moät pin codes vaø duøng pin codes ñeå sinh ra khoùa bí maät laø ma traän K. Ngöôøi A seõ duøng khoùa K ñeå maõ hoùa thoâng ñieäp C = K × M. Ngöôøi nhaän B cuõng coù pincodes vaø cuõng duøng pincodes ñeå sinh ra khoùa laø ma traän K. Vaø duøng khoùa K ñeå tính M = K-1 × C. Thuaät toaùn: sinh hoùa töø pincodes vaø maõ hoùa baèng maõ ma traän Cho tröôùc pincodes S coù chieàu daøi xaùc ñònh tröôùc. Thoâng ñieäp         M  Ngöôøi göûi          A  Sinh Khoùa K Sinh khóa K   Theo pin codes  Ngöôøi nhaän B         Mã hóa Thoâng ñieäp M  C= K × M Sinh khóa K   Theo pin codes  Thoâng ñieäp         M = K‐1×  C  61  Thuaät toaùn sinh khoùa K laø tích cuûa ma traän tam giaùc döôùi L vaø ma traän tam giaùc treân U coù kích thöôùc laø d × d Goïi f laø haøm băm (hash). Baûng chöõ caù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 Thuaät toaùn: Ta seõ aùp duïng baûng chöõ caùi ñeå chuyeån töø chöõ sang soá; trong tröôøng hôïp laø soá thì chính laø giaù trò cuûa soá ñoù; chæ coù tröôøng hôïp soá 0 ta chuyeån thaønh soá 10. Nhö vaäy chæ coù tröôøng hôïp duy nhaát laø A hay a thì chuyeån thaønh 0. Sinh khoùa K Böôùc 1: Duøng haøm baêm f ñeå tính giaù trò t:=f(S): Ma traän U coù ( )1 2 d d + phaàn töû caàn tính toaùn Ta tính: ( ) ( )1 1: ( ) 2 2* ( ) + +⎡ ⎤ ⎡ ⎤= =⎢ ⎥ ⎢ ⎥⎢ ⎥ ⎢ ⎥ d d d d length t a length t Neáu 1a > ; thì Laàn 1 ta seõ tính t:=f(S) Laàn 2 Ta tính: S:= S+t vaø tính t:= t + f(S) Vaø töông töï nhö nhö vaäy laäp laïi a laàn. Böôùc 2: Tính ma traän L: 62  Ta seõ gaùn caùc phaàn töû ñöôøng cheùo chính: 11 22 33, , , , ddl l l l… caùc giaù trò laø 1. for i from 1 to d do L[i][i]:=1; end do; Duyeät chuoãi t sau khi chuyeån sang soá vaø gaùn cho caùc giaù 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 traän U: Gaùn caùc phaàn töû treân ñöôøng cheùo chính khaùc 0 vaø choïn udd sao cho 1 0 1; 1 d ii dd i u u p − = ⎛ ⎞ ≠ −⎜ ⎟⎝ ⎠∏ Duyeät chuoãi t ngöôïc töø cuoái chuoãi sang ñaàu chuoãi. Gaùn caùc phaàn töû u11;….;ud-1d-1 sao cho caùc uii ñoù khaù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; Gaùn caùc phaàn töû baát kyø trong t (duyeät ngöôïc chuoã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 khoùa K: K:= L × U; Tính det(K – I); Neáu det(K – I ) = 0 thì laäp laïi böôùc 1 vôùi pincodes S:= S +f(S); Ngöôïc laïi chuyeån sang böôùc 5. Böôùc 5: Chuyeån thoâng ñieäp thaønh daïng ma traän Chuyeån caùc kyù töï trong thoâng ñieäp M thaønh daïng soá. 64  Tính ( ):β = −length M d ; Neáu 0β = thì thoâng ñieäp seõ laø ma traän daïng d×1 Neáu 0β > thì theâm ( ) ( )⎡ ⎤ −⎢ ⎥⎢ ⎥ length Md length M d khoaûng traéng vaøo cuoái M; luùc naøy ma traän thoâng ñieäp daïng ( )⎡ ⎤× ⎢ ⎥⎢ ⎥ length Md d . Neáu 0β < thì theâm β khoaûng traéng vaøo cuoái M; thoâng ñieäp laø ma traän daïng d×1. Taïo thoâng ñieäp thaønh ma traän vaø chuyeån sang soá. Böôùc 6: Tieán haønh maõ hoùa M vaø göûi cho B: C = K × M; Böôùc 7: Gôûi C (Ciphertext) cho ngöôøi B; Taïi ngöôøi B coù pincodes vaø sinh ma traän khoùa K töông töï caùc böôùc 1,2,3,4. Tính nhanh ma traän K-1 (phaàn 4 Chöông 4). Giaûi maõ vaø tính thoâng ñieäp M M = K-1 × C; Tính toaùn ngöôïc laïi thoâng ñieä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  Chuyeån ngöôïc töø soá sang chöõ caùi döa vaøo baûng Alphabet. Ngöôøi B ñaõ coù ñöôïc thoâng ñieäp cuûa ngöôøi A 2. Caùch taán coâng maõ Hill goác Hình 4.2 Tröôøng hôïp 1: Ta maõ hoùa: ta coù khoùa K laø ma traän vuoâng khaû nghòch baäc d; vaø M laø ma traän thoâng ñieäp; M coù soá chieàu laø d×m neáu thoâng ñieäp M khoâng ñuû d×m thì ta theâm caùc khoaûng traéng cho ñuû d×m. Nhöng trong tröôøng hôïp thoâng ñieäp M coù soá m = d thì M laø ma traän vuoâng. Nhö vaäy neáu nhö ta maõ hoùa thoâng ñieäp M = Id C = K × M = K × Id = K Nhö vaäy khi maõ hoùa nhö treân thì ta seõ tính ñöôïc khoùa K vaø nhö vaäy khoùa K khoâng coøn an toaøn nöõa. Tröôøng hôïp 2: Ta coù ma traän khoùa K coù kích thöôùc d×d Ta coù d vectô 1, dp p… (d × 1); caùc plaintext caàn maõ hoùa thì ta thu ñöôïc d vectô caùc ciphertext 1, dc c… (d × 1). Nhö vaäy ta coù: ( ) ( )1 1d dp p K c c× =… … . Thoâng ñieäp         M  Ngöôøi göûi          A  Sinh Khóa K  Sinh khóa K   Theo pin codes  Ngöôøi nhaän B         Mã hóa Thoâng ñieäp M    C= K ×  M   Sinh khóa K   Theo pin codes  Thoâng ñieäp         M = K‐1× C         Cipher text  66  Nhö vaäy khoùa K ñöôïc tính deã daøng: ( ) ( )11 1d dK p p c c−= ×… … 3. Caûi tieán thuaät giaûi (sinh khoùa töø pincodes vaø chuoãi ngaãu nhieân) Ñoái vôùi thoâng ñieäp coù kích thöôùc nhoû hôn d×(d – 1) Hình 4.3 Ngöôøi göûi A vaø ngöôøi nhaän B coù chung pincodes. Thuaät toaùn ñöôïc caûi tieán baèng caùch theâm chuoãi ngaãu nhieân u. Taïi ngöôøi göûi A: Böôùc 1: Sinh chuoãi u ngaãu nhieân; keát hôïp pincodes ñaõ coù vôùi u thaønh pincodes môùi . Böôùc 2: Töø pincodes môùi sinh ra ma traän khoùa K nhö trong phaàn 1 chöông 4. Böôùc 3: Tính C = K × M Böôùc 4: Göûi cho ngöôøi B : C vaø u. Taïi ngöôøi nhaän B: Böôùc 1: Tính pincodes môùi = pincodes + u Böôùc 2: Töø pincodes môùi tính ma traän khoùa K nhö trong phaàn 1 chöông 4. Böôùc 3: Giaûi maõ tìm thoâng ñieäp M: Sinh chuoãi t baát kyø; Keát hôïp pincodes vôùi t baát kyø Pin codes môùi = pincodes + u Thoâng ñieäp         M  Ngöôøi göûi          A  Sinh Khoùa K theo Pin codes môùi Ngöôøi nhaän B         Mã hóa Thoâng ñieäp M    C= K ×  M  Chuoãi ngaãu nhieân u   Thoâng ñieäp         M = K‐1×  C  Nhaän ñöôïc chuoãi u. Tính Pin codes môùi = pincodes + u 67  M = K-1 × C Caûi tieán thuaät toaùn ôû ñaây laø khoùa K duøng ñeå maõ hoùa luoân thay ñoåi trong moãi laàn maõ hoùa. Duø ai ñoù coù tính toaùn ñöôïc khoùa trong moät laàn maõ hoùa vaø giöõa ñeå giaûi maõ thoâng ñieäp khi baét ñöôïc cipher thì khoâng ñöôïc vì laàn maõ hoùa tieáp theo khoùa K cuõng ñaõ thay ñoåi vì chuoãi u ñöôïc sinh ra laø ngaãu nhieân. Nhö vaäy thì giaûi quyeát ñöôïc tröôøng hôïp 2 trong phaàn 2 (taán coâng maõ Hill goác) do d laàn maõ hoùa caùc vectô 1, dp p… vôùi d khoùa K khaùc nhau. Neáu M laø ma traän ñôn vò thì chæ bieát ñöôïc khoùa K vaø chuoãi ngaãu nhieân u cuûa laàn maõ hoùa ñoù maø nhöõng laàn maõ hoùa khaùc thì K vaø u ñaõ thay ñoåi; nhö vaäy giaûi quyeát tröôøng hôïp 1 trong phaàn 2 (taán coâng maõ Hill goác) Ñoái vôùi thoâng ñieäp coù kích thöôùc lôùn hôn d×(d – 1) Hình 4.4 Taïi ngöôøi A: Chia thoâng ñieäp thaønh k khoái moãi khoái coù kích thöôùc d×(d – 1); rieâng khoái k coù theå coù kích thöôùc nhoû hôn d×(d – 1). Thoâng ñieäp         M  Sinh chuoãi t baát kyø; Keát hôïp pincodes vôùi ui baát kyø Pin codes môùi thứ i= pincodes + ui Ngöôøi göûi          A  Sinh Khoùa Ki theo Pin codes môùi Ngöôøi nhaän B         Mã hóa Thoâng ñieäp M    Ci= Ki ×  Mi  Chuoãi ngaãu nhieân ui   Thoâng ñieäp         Mi = Ki ‐1×  Ci  Nhaän ñöôïc chuoãi ui. Tính Pin codes môùi thứ i = pincodes + ui M=ΣMi  Thoâng ñieäp M ñöôïc chia thaønh k khoái;k – 1 khoái coù kích thöôùc d×(d – 1); khoái k coù theå coù kích thöôùc nhoû hôn d×(d – 1) 68  Ngöôøi A tieán haønh maõ hoùa töøng khoái töông töï nhö trong tröôøng hôïp maõ hoùa thoâng ñieäp coù kích thöôùc nhoû hôn d×(d – 1) vaø göûi cho ngöôøi B. Taïi ngöôøi B: Ngöôøi B nhaän töøng khoái vaø tieán haønh giaûi maõ töøng khoái töông töï nhö tröôøng hôïp ôû treân. Sau ñoù gheùp caùc khoái laïi seõ coù thoâng ñieäp ban ñaàu. Do ta maõ hoùa töøng khoái coù kích thöôùc nhoû hôn d×(d – 1) neân seõ traùnh ñöôïc tröôøng hôïp choïn tröôùc vaên baûn ñeå maõ(choosen plaintext). 4. Tính nhanh ma traän khaû nghòch cuûa khoùa: 1 1 1K U L− − −= × Theo thuaät toaùn ta sinh ma traän K L U= × K khaû nghòch; L laø ma traän tam giaùc döôùi khaû nghòch vaø U laø ma traän tam giaùc treân khaû nghòch. Ma traän K,L,U laø ma traän vuoâng caáp d × d treân p] . Ta ñaët ( )1 .1 .nK k k− = … thì ki laø nghieäm cuûa heä phöông trình Thì caùc .ik (vectô coät) laø nghieäm cuûa heä . .i iK k I× = vôùi .iI laø vectô coät vôùi vò trí thöù i laø 1 coøn laïi laø 0. Maø . . . .i i i iK k I L U k I× = ⇔ × × = Ta ñaët: . .i i i iU k Y L Y I× = ⇒ × = Nghóa laø ta giaûi heä phöông trình sau: . i i i i L Y I U k Y × =⎧⎨ × =⎩ Ta goïi: 1i i di Y Y Y ⎛ ⎞⎜ ⎟= ⎜ ⎟⎜ ⎟⎝ ⎠ # vaø ta seõ giaûi heä 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 xeùt heä 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ö vaäy ta coù theå tính nhanh ma traän nghòch ñaûo cuûa K töø L × U. Vôùi ( )1 .iK k− = vôùi .ik laø vectô coä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  KEÁT LUAÄN VAØ KIEÁN NGHÒ Luaän vaên ñaõ taäp trung khaûo saùt veà maõ Ma traän; vaø khaûo saùt khoâng gian khoùa vaø ñöa ra ñöôïc tyû soá f(d,m) ñeå ñaùnh giaù choïn khoâng gian khoùa vaø khoâng gian Alphabet sao cho toát nhaát. Theo luaän vaên thì khoâng gian Alphabet toát nhaát thì m(kích thöôùc khoâng gian Alphabet) neân laø soá nguyeân toá. Luaän vaên cuõng ñaõ ñöa ra thuaät giaûi sinh khoùa, vôùi khoùa K = L×U an toaøn vôùi L laø ma traän tam giaùc döôùi vôùi caùc phaàn töø treân ñöôøng cheùo chính baèng 1 vaø U laø ma traän tam giaùc treân khaû nghòch. Luaän vaên cuõng ñöa caûi tieán cho maõ Ma traän laø theâm chuoãi ngaãu nhieân u khi maõ hoùa ñeå khoùa K thay ñoåi trong nhöõng laàn maõ hoùa khaùc nhau. Vaø ñeà xuaát khi maõ hoùa thoâng ñieäp thì neân choïn thoâng ñieäp coù kích thöôùc nhoû hôn d×(d – 1); vôùi d laø kích thöôùc khoùa. Tuy nhieân trong luaän vaên cuõng coøn nhieàu thieáu soùt vaø trong thuaät toaùn sinh khoùa K = L×U thì khoâng loaïi boû tröïc tieáp khoùa yeáu (K×v=v) maø chæ loaïi boû ñöôïc (K laø ma traän ñoái hôïp.). Kieán nghò tìm ñieàu kieän L, U sao cho khi tính L×U thì loaïi boû tröôøng hôïp khoùa yeáu laø det(L×U – I)≠0 72  TAØI LIEÄU THAM KHAÛO Key word Hill cipher, Matrix Modular, General Matrix. Tieáng Vieät: [1] Döông Anh Ñöùc, Traàn Minh Trieát (2005), Maõ hoùa vaø öùng duïng, Nhaø xuaát baûn Đại học Quốc Gia TPHCM, Thaønh Phoá Hoà Chí Minh. [2] Buøi Xuaân Haûi, Traàn Nam Duõng, Trònh Thanh Ñeøo, Thaùi Minh Ñöôøng, Traàn Ngoïc Hoäi (2001), Ñaïi soá tuyeán tính, Nhaø xuaát baûn Ñaïi hoïc Quoác Gia TPHCM, Thaønh Phoá Hoà Chí Minh. [3] Haø Huy Khoaùi (2003), Maõ hoùa thoâng tin cô sôû toaùn hoïc vaø öùng duïng, Boä saùch toaùn cao caáp – Vieän Toaùn Hoïc, Haø Noäi [4] Nguyeãn Ñình Thuùc, Buøi Doaõn Khanh (2006), Maõ hoùa – Maät maõ, Nhaø Xuaát Baûn Lao Ñoäng Xaõ Hoäi, Thaønh Phoá Hoà Chí Minh. Tieá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  PHUÏ LUÏC DEMO THUAÄT TOAÙN CHÖÔNG 4 BAÈNG MAPLE // Khai baùo thö vieän with(StringTools); with(inttrans); with(Maplets); with(linalg); with(LinearAlgebra); //Vieát haøm chuyeån ñoåi töø chöõ sang soá (tröôøng hôïp laø soá thì giöõ nguyeân; soá 0 chuyeån thaønh soá 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; // Vieát haøm chuyeån töø soá thaønh chöõ(trong ví duï naøy chæ maõ hoùa chöõ khoâng maõ hoùa soá) 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 chuoãi ngaãu nhieân coù chieàu daøi d sinhchuoingaunhien := proc (d) return Random(d, 'upper') end proc; // Soá laàn laëp haøm baêm pinccodes ñuû ñeå taïo ma traä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; // Haøm baêm pincodes vôùi soá laàn ñöôïc tính ôû treâ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; //Taïo ma traän tam giaù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  //Taïo ma traän tam giaùc treâ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 Khoù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 tieán haønh maõ hoùa vaø 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 giaûi maõ vaø tìm ñöôïc thoâng ñieä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"); //Caûi tieán thuaät toaùn vôùi theâm moät chuoãi ngaãu nhieân u vaø keát hôïp vôùi pincodes taïo thaønh pincodes môùi vaø duøng pincodes môùi sinh khoùa, khi gôûi ma traän ñaõ maõ hoùa thì daáu chuoãi ngaãu nhieân u vaøo coät cuoái vaø haøng cuoái cuûa ma traä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 tieán haønh maõ hoù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 tieán haønh giaûi maõ 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;