Giáo trình tin học : Hệ mật mã và những khả năng tạo liên lạc tuyệt mật của nó phần 4

Với 1 ≤ i ≤ l và 1 ≤ k ≤ l. Tức là các phần tử ở hàng i và cột thứ k của AB được tạo ra bằng cách lấy hàng thứ i của A và cột thứ k của B, sau đó nhân tương ứng các phần tử với nhau và cộng lại.
Nội dung trích xuất từ tài liệu:
Giáo trình tin học : Hệ mật mã và những khả năng tạo liên lạc tuyệt mật của nó phần 4Vietebooks Nguyễn Hoàng CươngVíi 1 ≤ i ≤ l vµ 1 ≤ k ≤ l. Tøc lµ c¸c phÇn tö ë hµng i vµ cét thø k cña AB®−îc t¹o ra b»ng c¸ch lÊy hµng thø i cña A vµ cét thø k cña B, sau ®ã nh©nt−¬ng øng c¸c phÇn tö víi nhau vµ céng l¹i. CÇn ®Ó ý r»ng AB lµ mét ma trËncÊp l × n. Theo ®Þnh nghÜa nµy, phÐp nh©n ma trËn lµ kÕt hîp (tøc (AB)C =A(BC)) nh−ng noi© chung lµ kh«ng giao ho¸n ( kh«ng ph¶i lóc nµo AB =BA, thËm chÝ ®è víi ma trËn vu«ng A vµ B). Ma trËn ®¬n vÞ m × m (ký hiÖu lµ Im ) lµ ma trËn cÊp m × m cã c¸c sè 1n»m ë ®−êng chÐo chÝnh vµ c¸c sè 0 ë vÞ trÝ cßn l¹i. Nh− vËy ma trËn ®¬n vÞ2 × 2 lµ: 10 I2 = 01Im ®−îc gäi lµ ma trËn ®¬n vÞ v× AIm = A víi mäi ma trËn cÊp l × m vµ ImB =Bvíi mäi ma trËn cÊp m × n. Ma trËn nghÞch ®¶o cña ma trËn A cÊp m × m (nÕu tån t¹i) lµ ma trËn A-1 sao cho AA-1 = A-1A = Im . Kh«ng ph¶i mäi matrËn ®Òu cã nghÞch ®¶o, nh−ng nÕu tån t¹i th× nã duy nhÊt. Víi c¸c ®Þnh nghÜa trªn, cã thÓ dÔ dµng x©y dùng c«ng thøc gi¶i m· ®·nªu: V× y = xK, ta cã thÓ nh©n c¶ hai vÕ cña ®¼ng thøc víi K-1 vµ nhËn ®−îc: yK-1 = (xK)K-1 = x(KK-1) = xIm = x( Chó ý sö dông tÝnh chÊt kÕt hîp) Cã thÓ thÊy r»ng, ma trËn m· ho¸ ë trªn cã nghÞch ®¶o trong Z26: -1 11 8 7 18 = 37 23 11v× = 11×7+8×23 11×18+8×11 12 8 8 18 3×7+7×23 3×18+7×11 37 23 11 Trang 16Vietebooks Nguyễn Hoàng Cương 261 286 10 = = 182 131 01(H·y nhí r»ng mäi phÐp to¸n sè häc ®Òu ®−îc thùc hiÖn theo modulo 26). Sau ®©y lµ mét vÝ dô minh ho¹ cho viÖc m· ho¸ vµ i¶i m· trong hÖ mËtm· Hill.Via dô 1.5 11 8 = Gi¶ sö kho¸ K 37Tõ c¸c tÝnh to¸n trªn ta cã: 7 18 K-1 = 23 11Gi¶ sö cÇn m· ho¸ b¶n râ July. Ta cã hai phÇn tö cña b¶n râ ®Ó m· ho¸:(9,20) (øng víi Ju) vµ (11,24) (øng víi ly). Ta tÝnh nh− sau: 11 8 = (99+60, 72+140) = (3,4) (9,20) 37vµ 11 8 = (121+72, 88+168) = (11,22) (11,24) 37 Bëi vËy b¶n m· cña July lµ DELW. §Ó gi¶i m· Bob sÏ tÝnh 7 18 = (9,20) (3,4) 2 3 11vµ 7 18 = (11,24) (11,22) 2 3 11 Trang 17Vietebooks Nguyễn Hoàng Cương Nh− vËy Bob ®· nhËn ®−îc b¶n ®óng. Cho tíi lóc nµy ta ®· chØ ra r»ng cã thÓ thùc hiÖn phÐp gi¶i m· nÕu Kcã mét nghÞch ®¶o. Trªn thùc tÕ, ®Ó phÐp gi¶i m· lµ cã thÓ thùc hiÖn ®−îc,®iÒu kiÖn cÇn lµ K ph¶i cã nghÞch ®¶o. ( §iÒu nµy dÔ dµng rót ra tõ ®¹i sètuyÕn tÝnh s¬ cÊp, tuy nhiªn sÏ kh«ng chøng minh ë ®©y). Bëi vËy, chóng tachØ quan t©m tíi c¸c ma trËn K kh¶ nghich. TÝnh kh¶ nghÞch cña mét ma trËn vu«ng phô thuéc vµo gi¸ trÞ ®Þnhthøc cña nã. §Ó tr¸nh sù tæng qu¸t ho¸ kh«ng cÇn thiÕt, ta chØ giíi h¹n trongtr−êng hîp 2×2.§Þnh nghÜa 1.5 §Þnh thøc cña ma trËn A = (a,i j ) cÊp 2× 2 lµ gi¸ trÞ det A = a1,1 a2,2 - a1,2 a2,1NhËn xÐt: §Þnh thøc cña mét ma trËn vu«ng cÊp mm cã thÓ ®−îc tÝnh theoc¸c phÐp to¸n h»ng s¬ cÊp: h·y xem mét gi¸o tr×nh bÊt kú vÒ ®¹i sè tuyÕntÝnh. Hai tÝnh chÊt quan träng cña ®Þnh thøc lµ det Im = 1 vµ quy t¾c nh©ndet(AB) = det A × det B. Mét ma trËn thøc K lµ cã nghÞch ®¶o khi vµ chØ khi ®Þnh thøc cña nãkh¸c 0. Tuy nhiªn, ®iÒu quan träng cÇn nhí lµ ta ®ang lµm viÖc trªn Z26 . KÕtqu¶ t−¬ng øng lµ ma trËn K cã nghÞch ®¶o theo modulo 26 khi vµ chØ khiUCLN(det K,26) = 1. Sau ®©y sÏ chøng minh ng¾n gän kÕt qu¶ nµy. Tr−íc tiªn, gi¶ sö r»ng UCLN(det K,26) = 1. Khi ®ã det K cã nghÞch®¶o trong Z26 . Víi 1 ≤ i ≤ m, 1 ≤ j ≤ m, ®Þnh nghÜa Ki j ma trËn thu ®−îc tõ Kb»ng c¸ch lo¹i bá hµng thø i vµ cét thø j. Vµ ®Þnh nghÜa ma trËn K* cã phÇntö (i,j) cña nã nhËn gi¸ trÞ(- ...