MẬT MÃ CỔ ĐIỂN

Chia sẻ: Nguyen Hoang Tung Tung | Ngày: | Loại File: DOC | Số trang:49

Thêm vào BST

Báo xấu

117
lượt xem 16
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Alice sẽ mã hoá bản rõ bằng một kháo đã được xacs định trước và gửi bản mã kết quả trên kênh. Oscar có bản mã thu trộm được trên kênh song không thể xác định nội dung của bản rõ, nhưng Bob (người đã biết khoá mã) có thể giải mã và thu được bản rõ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: MẬT MÃ CỔ ĐIỂN

Ch¬ng 1 MËt m· cæ ®iÓn 1.1më ®Çu - mét sè hÖ mËt ®¬n gi¶n §èi tîng c¬ b¶n cña mËt m· lµ t¹o ra kh¶ n¨ng liªn l¹c trªn mét kªnh kh«ng mËt cho hai ngêi sö dông (t¹m gäi lµ Alice vµ Bob) sao cho ®èi ph¬ng (Oscar) kh«ng thÓ hiÓu ®îc th«ng tin ®îc truyÒn ®i. Kªnh nµy cã thÓ lµ mét ®êng d©y ®iÖn tho¹i hoÆc mét m¹ng m¸y tÝnh. Th«ng tin mµ Alice muèn göi cho Bob (b¶n râ) cã thÓ lµ mét v¨n b¶n tiÕng Anh, c¸c d÷ liÖu b»ng sè hoÆc bÊt cø tµi liÖu nµo cã cÊu tróc tuú ý. Alice sÏ m· ho¸ b¶n râ b»ng mét kh¸o ®· ®îc xacs ®Þnh tríc vµ göi b¶n m· kÕt qu¶ trªn kªnh. Oscar cã b¶n m· thu trém ®îc trªn kªnh song kh«ng thÓ x¸c ®Þnh néi dung cña b¶n râ, nhng Bob (ngêi ®· biÕt kho¸ m·) cã thÓ gi¶i m· vµ thu ®îc b¶n râ. Ta sÏ m« t¶ h×nh thøc ho¸ néi dung b»ng c¸ch dung kh¸i niÖm to¸n häc nh sau: §Þnh nghÜa 1.1 Mét hÖ mËt lµ mét bé 5 (P,C,K,E,D) tho¶ m·n c¸c ®iÒu kiÖn sau: 1. P lµ mét tËp h÷u h¹n c¸c b¶n râ cã thÓ. 2. C lµ mét tËp h÷u h¹n c¸c b¶n m· cã thÓ. 3. K (kh«ng gian kho¸) lµ tËp h÷u h¹n c¸c kho¸ cã thÓ. 4. §èi víi mçi k∈ K cã mét quy t¾c m· ek: P → C vµ mét quy t¾cv gi¶i m· t¬ng øng dk ∈ D. Mçi ek: P → C vµ dk: C → P lµ nh÷ng hµm mµ: dk(ek (x)) = x víi mäi b¶n râ x ∈ P. Trong tÝnh chÊt 4 lµ tÝnh chÊt chñ yÕu ë ®©y. Néi dung cña nã lµ nÕu mét b¶n râ x ®îc m· ho¸ b»ng ek vµ b¶n m· nhËn ®îc sau ®ã ®îc gi¶i m· b»ng dk th× ta ph¶i thu ®îc b¶n râ ban ®Çu x. Alice vµ Bob sÏ ¸p dông thñ tôc sau dïng hÖ mËt kho¸ riªng. Tríc tiªn hä chän mét kho¸ ngÉu nhiªn K ∈ K . §iÒu nµy ®îc thùc hiÖn khi hä ë cïng
mét chç vµ kh«ng bÞ Oscar theo dâi hoÆc khi hä cã mét kªnh mËt trong trêng hîp hä ë xa nhau. Sau ®ã gi¶ sö Alice muèn göi mét th«ng baã cho Bob trªn mét kªnh kh«ng mËt vµ ta xem th«ng b¸o nµy lµ mét chuçi: x = x1,x2 ,. . .,xn víi sè nguyªn n ≥ 1 nµo ®ã. ë ®©y mçi ký hiÖu cña mçi b¶n râ xi ∈ P , 1 ≤ i ≤ n. Mçi xi sÏ ®îc m· ho¸ b»ng quy t¾c m· ek víi kho¸ K x¸c ®Þnh tríc ®ã. Bëi vËy Alice sÏ tÝnh yi = ek(xi), 1 ≤ i ≤ n vµ chuçi b¶n m· nhËn ®îc: y = y1,y2 ,. . .,yn sÏ ®îc göi trªn kªnh. Khi Bob nhËn ®¬c y1,y2 ,. . .,yn anh ta sÏ gi¶i m· b»ng hµm gi¶i m· dk vµ thu ®îc b¶n râ gèc x1,x2 ,. . .,xn. H×nh 1.1 lµ mét vÝ dô vÒ mét kªnh liªn l¹c H×nh 1.1. Kªnh liªn l¹c Oscar Alice Bé m· ho¸ Bé gi¶i m· Bob Kªnh an toµn Nguån kho¸ Râ rµng lµ trong trêng hîp nµy hµm m· ho¸ ph¶i lµ hµm ®¬n ¸nh ( tøc lµ ¸nh x¹ 1-1), nÕu kh«ng viÖc gi¶i m· sÏ kh«ng thùc hiÖn ®îc mét c¸ch têng minh. VÝ dô y = ek(x1) = ek(x2)
trong ®ã x1 ≠ x2 , th× Bob sÏ kh«ng cã c¸ch nµo ®Ó biÕt liÖu sÏ ph¶i gi¶i m· thµnh x1 hay x2 . Chó ý r»ng nÕu P = C th× mçi hµm m· ho¸ ize="2">B¶n quyÒn C«ng ty Ph¸t ttËp c¸c b¶n m· vµ tËp c¸c b¶n râ lµ ®ång nhÊt th× mçi mét hµm m· sÏ lµ mét sù s¾p xÕp l¹i (hay ho¸n vÞ ) c¸c phÇn tö cña tËp nµy. 1.1.1 M· dÞch vßng ( shift cipher) PhÇn nµy sÏ m« t¶ m· dÞch (MD) dùa trªn sè häc theo modulo. Tríc tiªn sÏ ®iÓm qua mét sè ®Þnh nghÜa c¬ b¶n cña sè häc nµy. §Þnh nghÜa 1.2 Gi¶ sö a vµ b lµ c¸c sè nguyªn vµ m lµ mét sè nguyªn d¬ng. Khi ®ã ta viÕt a ≡ b (mod m) nÕu m chia hÕt cho b-a. MÖnh ®Ò a ≡ b (mod m) ®îc gäi lµ " a ®ång d víi b theo modulo m". Sè nguyªn m ®îc gäi lµ mudulus. Gi¶ sö chia a vµ b cho m vµ ta thu ®îc th¬ng nguyªn vµ phÇn d, c¸c phÇn d n»m gi÷a 0 vµ m-1, nghÜa lµ a = q 1m + r1 vµ b = q2m + r2 trong ®ã 0 ≤ r1 ≤ m-1 vµ 0 ≤ r2 ≤ m-1. Khi ®ã cã thÓ dÔ dµng thÊy r»ng a ≡ b (mod m) khi vµ chØ khi r 1 = r2 . Ta sÏ dïng ký hiÖu a mod m (kh«ng dïng c¸c dÊu ngoÆc) ®Ó x¸c ®Þnh phÇn d khi a ®îc chia cho m (chÝnh lµ gi¸ trÞ r 1 ë trªn). Nh vËy: a ≡ b (mod m) khi vµ chØ khi a mod m = b mod m. NÕu thay a b»ng a mod m th× ta nãi r»ng a ®îc rót gän theo modulo m. NhËn xÐt: NhiÒu ng«n ng÷ lËp tr×nh cña m¸y tÝnh x¸c ®Þnh a mod m lµ phÇn d trong d¶i - m+1,.. ., m-1 cã cïng dÊu víi a. VÝ dô -18 mod 7 sÏ lµ -4, gi¸ trÞ nµy kh¸c víi gi¸ trÞ 3 lµ gi¸ trÞ ®îc x¸c ®Þnh theo c«ng thøc trªn. Tuy nhiªn, ®Ó thuËn tiÖn ta sÏ x¸c ®Þnh a mod m lu«n lµ mét sè kh«ng ©m. B©y giê ta cã thÓ ®Þnh nghÜa sè häc modulo m: Z m ®îc coi lµ tËp hîp {0,1,. . .,m-1} cã trang bÞ hai phÐp to¸n céng vµ nh©n. ViÖc céng vµ nh©n trong Zm ®îc thùc hiÖn gièng nh céng vµ nh©n c¸c sè thùc ngoµi trõ mét ®iÓm lµc¸c kÕt qu¶ ®îc rót gän theo modulo m. VÝ dô tÝnh 11× 13 trong Z16 . T¬ng tù nh víi c¸c sè nguyªn ta cã 11 × 13 = 143. §Ó rót gän 143 theo modulo 16, ta thùc hiÖn phÐp
chia b×nh thêng: 143 = 8 × 16 + 15, bëi vËy 143 mod 16 = 15 trong Z16 . C¸c ®Þnh nghÜa trªn phÐp céng vµ phÐp nh©n Zm th¶o m·n hÇu hÕt c¸c quy t¾c quyen thuéc trong sè häc. Sau ®©y ta sÏ liÖt kª mµ kh«ng chøng minh c¸c tÝnh chÊt nµy: 1. PhÐp céng lµ ®ãng, tøc víi bÊt k× a,b ∈ Zm ,a +b ∈ Zm 2. PhÐp céng lµ giao ho¸n, tøc lµ víi a,b bÊt k× ∈ Zm a+b = b+a 3. PhÐp céng lµ kÕt hîp, tøc lµ víi bÊt k× a,b,c ∈ Zm (a+b)+c = a+(b+c) 4. 0 lµ phÇn tö ®¬n vÞ cña phÐp céng, cã nghÜa lµ víi a bÊt k× ∈ Zm a+0 = 0+a = a 5. PhÇn tö nghÞch ®¶o cña phÐp céngcña phÇn tö bÊt k× (a ∈ Zm ) lµ m-a, nghÜa lµ a+(m-a) = (m-a)+a = 0 víi bÊt k× a ∈ Zm . 6. PhÐp nh©n lµ ®ãng , tøc lµ víi a,b bÊt k× ∈ Zm , ab ∈ Zm . 7. PhÐp nh©n lµ gioa ho¸n , nghÜa lµ víi a,b bÊt k× ∈ Zm , ab = ba 8. PhÐp nh©n lµ kÕt hîp, nghÜa lµ víi a,b,c ∈ Zm , (ab)c = a(cb) 9. 1 lµ phÇn tö ®¬n vÞ cña phÐp nh©n, tøc lµ víi bÊt kú a ∈ Zm a× 1 = 1× a = a 10. PhÐp nh©n cã tÝnh chÊt ph©n phèi ®èi víi phÐp céng, tøc lµ ®èi víi a,b,c ∈ Zm , (a+b)c = (ac)+(bc) vµ a(b+c) = (ab) + (ac) C¸c tÝnh chÊt 1,3-5 nãi lªn r»ng Z m l©p nªn mét cÊu tróc ®¹i sè ®îc gäi lµ mét nhãm theo phÐp céng. V× cã thªm tÝnh chÊt 4 nhãm ®îc gäi lµ nhãm Aben (hay nhãm gioa ho¸n). C¸c tÝnh chÊt 1-10 sÏ thiÕt lËp nªn mét vµnh Z m . Ta sÏ cßn thÊy nhiÒu vÝ dô kh¸c vÒ c¸c nhãm vµ c¸c vµnh trong cuèn s¸ch nµy. Mét sè vÝ dô quªn thuéc cña vµnh lµ c¸c sè nguyªn Z, c¸c sè thùc R vµ c¸c sè phøc C. Tuy nhiªn c¸c vµnh nµy ®Òu v« h¹n, cßn mèi quan t©m cña chóng ta chØ giíi h¹n trªn c¸c vµnh h÷u h¹n. V× phÇn tö ngîc cña phÐp céng tån t¹i trong Z m nªn còng cã thÓ trõ c¸c phÇn tö trong Zm . Ta ®Þnh nghÜa a-b trong Zm lµ a+m-
b mod m. Mét c¸ch t¬ng cã thÓ tÝnh sè nguyªn a-b råi rót gon theo modulo m. VÝ dô : §Ó tÝnh 11-18 trong Z 31, ta tÝnh 11+13 mod 31 = 24. Ngîc l¹i, cã thÓ lÊy 11-18 ®îc -7 råid sau ®ã tÝnh -7 mod 31 = 24. Ta sÏ m« t¶ m· dÞch vßng trªn h×nh 1.2. Nã ®îc x¸c ®Þnh trªn Z26 (do cã 26 ch÷ c¸i trªn b¶ng ch÷ c¸i tiÕng Anh) mÆc dï cã thÓ x¸c ®Þnh nã trªn Zm víi modulus m tuú ý. DÔ dµng thÊy r»ng, MDV sÏ t¹o nªn mét hÖ mËt nh ®· x¸c ®Þnh ë trªn, tøc lµ dK (eK(x)) = x víi mäi x∈ Z26 . H×nh 1.2: M· dÞch vßng Gi¶ sö P = C = K = Z26 víi 0 ≤ k ≤ 25 , ®Þnh nghÜa: eK(x) = x +K mod 26 vµ dK(x) = y -K mod 26 (x,y ∈ Z26) NhËn xÐt: Trong trêng hîp K = 3, hÖ mËt thêng ®îc gäi lµ m· Caesar ®· tõng ®îc Julius Caesar sö dông. Ta sÏ sö dông MDV (víi modulo 26) ®Ó m· ho¸ mét v¨n b¶n tiÕng Anh th«ng thêng b»ng c¸ch thiÕt lËp sù t¬ng ønggi÷a c¸c kÝ tù vµ c¸c thÆng d theo modulo 26 nh sau: A ↔ 0,B ↔ 1, . . ., Z ↔ 25. V× phÐp t¬ng øng nµy cßn dïng trong mét vµi vÝ dô nªn ta sÏ ghi l¹i ®Ó cßn tiÖn dïng sau nµy: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25 Sau ®©y lµ mét vÝ dô nhá ®Ó minh ho¹ VÝ dô 1.1: Gi¶ sö kho¸ cho MDV lµ K = 11 vµ b¶n râ lµ: wewillmeetatmidnight
Tríc tiªn biÕn ®æi b¶n râ thµnh d·y c¸c sè nguyªn nhê dïng phÐp t¬ng øng trªn. Ta cã: 22 4 22 8 11 11 12 4 4 19 0 19 12 8 3 13 8 6 7 19 sau ®ã céng 11 vµo mçi gi¸ trÞ råi rót gän tæng theo modulo 26 7 15 7 19 22 22 23 15 15 4 11 4 23 19 14 24 19 17 18 4 Cuèi cïng biÕn ®æi d·y sè nguyªn nµy thµnh c¸c kÝ tù thu ®îc b¶n m· sau: HPHTWWXPPELEXTOYTRSE §Ó gi¶ m· b¶n m· nµy, tríc tiªn, Bob sÏ biÕn ®æi b¶n m· thµnh d·y c¸c sè nguyªn råi trõ ®i gi¸ trÞcho 11 ( rót gän theo modulo 26) vµ cuèi cïng biÕn ®æi l¹i d·y nµythµnh c¸c ký tù. NhËn xÐt: Trong vÝ dô trªn , ta ®· dïng c¸c ch÷ in hoa ch o b¶n m·, c¸c ch÷ thêng cho b¶n râ ®ªr tiÖn ph©n biÖt. Quy t¾c nµy cßn tiÕp tôc sö dông sau nµy. NÕu mét hÖ mËt cã thÓ sö dông ®îc trong thùc tÕ th× nã ph¶o tho¶ m·n mét sè tÝnh chÊt nhÊt ®Þnh. Ngay sau ®©y sÐ nªu ra hai trong sè ®ã: 1. Mçi hµm m· ho¸ eK vµ mçi hµm gi¶i m· dK ph¶i cã kh¶ n¨ng tÝnh to¸n ®îc mét c¸ch hiÖu qu¶. 2. §èi ph¬ng dùa trªn x©u b¶n m· ph¶i kh«ng cã kh¶ n¨ng x¸c ®Þnh kho¸ K ®· dïng hoÆc kh«ng cã kh¶ n¨ng x¸c ®Þnh ®îc x©u b¶n râ x. TÝnh chÊt thø hai x¸c ®Þnh (theo c¸ch kh¸ mËp mê) ý tëng ý t- ëng "b¶o mËt". Qu¸ tr×nh thö tÝnh kho¸ K (khi ®· biÕt b¶n m· y) ®îc gäi lµ m· th¸m (sau nµy kh¸i niÖm nµy sÏ ®ùc lµm chÝnh x¸c h¬n). CÇn chó ý r»ng, nÕu Oscar cã thÓ x¸c ®Þnh ®îc K th× anh ta cã thÓ gi¶i m· ®îc y nh Bob b»ng c¸ch dïng dK. Bëi vËy, viÖc x¸c ®Þnh K chÝ Ýt còng khã nh viÖc x¸c ®Þnh b¶n râ x. NhËn xÐt r»ng, MDV (theo modulo 26) lµ kh«ng an toµn v× nã cã thÓ bÞ th¸m theo ph¬ng ph¸p vÐt c¹n. Do chØ cã 26 kho¸ nªn dÔ
dµng thö mäi kho¸ dK cã thÓ cho tíi khi nhËn ®îc b¶n râ cã nghÜa. §iÒu nµy ®îc minh ho¹ theo vÝ dô sau: VÝ du 1.2 Cho b¶n m· JBCRCLQRWCRVNBJENBWRWN ta sÏ thö liªn tiÕp c¸c kho¸ gi¶i m· d0 ,d1 .. . vµ y thu ®îc: jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk jxynyhmnsynrjexfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvodyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwfojof astitchintimesavesnine Tíi ®©y ta ®· x¸c ®Þnh ®îc b¶n râ vµ dõng l¹i. Kho¸ t¬ng øng K = 9. Trung b×nh cã thÓ tÝnh ®îc b¶n râ sau khi thö 26/2 = 13 quy t¾c gi¶i m·. Nh ®· chØ ra trong vÝ dô trªn , ®iÒu kiÖn ®Ó mét hÖ mËt an toµn lµ phÐp t×m kho¸ vÐt c¹n ph¶i kh«ng thÓ thùc hiÖn ®îc; tøc kh«ng gian kho¸ ph¶i rÊt lín. Tuy nhiªn, mét kh«ng gian kho¸ lín vÉn cha ®ñ ®¶m b¶o ®é mËt. 1.1.2 M· thay thÕ Mét hÖ mËt næi tiÕng kh¸c lµ hÖ m· thay thÕ. HÖ mËt nµy ®· ®îc sö dông hµng tr¨m n¨m. Trß ch¬i ®è ch÷ "cryptogram" trong c¸c bµi b¸o lµ nh÷ng vÝ dô vÒ MTT. HÖ mËt nµy ®îc nÕu trªn h×nh 1.3. Trªn thùc tÕ MTT cã thÓ lÊy c¶ P vµ C ®Òu lµ bé ch÷ c¸i tiÕng anh, gåm 26 ch÷ c¸i. Ta dïng Z26 trong MDV v× c¸c phÐp m· vµ gi¶i m· ®Òu lµ c¸c phÐp to¸n ®¹i sè. Tuy nhiªn, trong MTT, thÝch hîp h¬n lµ xem phÐp m· vµ gi¶i m· nh c¸c ho¸n vÞ cña c¸c kÝ tù.
H×nh 1.3 M· thay thÕ Cho P =C = Z26 . K chøa mäi ho¸n vÞ cã thÓ cña 26 kÝ hiÖu 0,1, . . . ,25 Víi mçi phÐp ho¸n vÞ π ∈K , ta ®Þnh nghÜa: eπ(x) = π(x) vµ dπ(y) = π -1(y) trong ®ã π -1 lµ ho¸n vÞ ngîc cña π. Sau ®©y lµ mét vÝ dô vÒ phÐp ho¸n vÞ ngÉu nhiªn π t¹o nªn mét hµm m· ho¸ (còng nhb tríc, c¸c kÝ hiÖu cña b¶n râ ®îc viÕt b»ng ch÷ thêng cßn c¸c kÝ hiÖu cña b¶n m· lµ ch÷ in hoa). a b c d e f g h i j k l M X N Y A H P O G Z Q W B T n o p q r s t u v w x y Z S F L R C V M U E K J D I Nh vËy, eπ (a) = X, eπ (b) = N,. . . . Hµm gi¶i m· lµ phÐp ho¸n vÞ ngîc. §iÒu nµy ®îc thùc hiÖn b»ng c¸ch viÕt hµng thø hai lªn tríc råi s¾p xÕp theo thø tù ch÷ c¸i. Ta nhËn ®îc: A B C D E F G H I J K L M d l r y v o h e z x w p T N O P Q R S T U V W X Y Z b g f j q n m u s k a c I Bëi vËy dπ (A) = d, dπ(B) = 1, . . . §Ó lµm bµi tËp, b¹n ®äc cã gi¶i m· b¶n m· sau b»ng c¸ch dïng hµm gi¶i m· ®¬n gi¶n: M G Z V Y Z L G H C M H J M Y X S S E M N H A H Y C D L M H A.
MçÜ kho¸ cña MTT lµ mét phÐp ho¸n vÞ cña 26 kÝ tù. Sè c¸c ho¸n vÞ nµy lµ 26!, lín h¬n 4 × 10 26 lµ mét sè rÊt lín. Bëi vËy, phÐp t×m kho¸ vÐt c¹n kh«ng thÓ thùc hiÖn ®îc, thËm chÝ b»ng m¸y tÝnh. Tuy nhiªn, sau nµy sÏ thÊy r»ng MTT cã thÓ dÔ dµng bÞ th¸m b»ng c¸c ph¬ng ph¸p kh¸c. 1.1.3 M· Affine MDV lµ mét trêng hîp ®Æc biÖt cña MTT chØ gåm 26 trong sè 26! c¸c ho¸n vÞ cã thÓ cña 26 phÇn tö. Mét trêng hîp ®Æc biÖt kh¸c cña MTT lµ m· Affine ®îc m« t¶ díi ®©y. trong m· Affine, ta giíi h¹n chØ xÐt c¸c hµm m· cã d¹ng: e(x) = ax + b mod 26, a,b ∈ Z26 . C¸c hµm nµy ®îc gäi lµ c¸c hµm Affine (chó ý r»ng khi a = 1, ta cã MDV). §Ó viÖc gi¶i m· cã thÓ thùc hiÖn ®îc, yªu cÇu cÇn thiÕt lµ hµm Affine ph¶i lµ ®¬n ¸nh. Nãi c¸ch kh¸c, víi bÊt kú y ∈ Z26, ta muèn cã ®ång nhÊt thøc sau: ax + b ≡ y (mod 26) ph¶i cã nghiÖm x duy nhÊt. §ång d thøc nµy t¬ng ®¬ng víi: ax ≡ y-b (mod 26) V× y thay ®æi trªn Z 26 nªn y-b còng thay ®æi trªn Z 26 . Bëi vËy, ta chØ cÇn nghiªn cøu ph¬ng tr×nh ®ång d: ax ≡ y (mod 26) (y∈ Z26 ). Ta biÕt r»ng, ph¬ng tf×nh nµy cã mét nghiÖm duy nhÊt ®èi víi mçi y khi vµ chØ khi UCLN(a,26) = 1 (ë ®©y hµm UCLN lµ íc chung lín nhÊt cña c¸c biÕn cña nã). Tríc tiªn ta gi¶ sö r»ng, UCLN(a,26) = d >1. Khi ®ã, ®ång d thøc ax ≡ 0 (mod 26) sÏ cã Ýt nhÊt hai nghiÖm ph©n biÖt trong Z26 lµ x = 0 vµ x = 26/d. Trong trêng hîp nµy, e(x) = ax + b mod 26 kh«ng ph¶i lµ mét hµm ®¬n ¸nh vµ bëi vËy nã kh«ng thÓ lµ hµm m· ho¸ hîp lÖ.
VÝ dô, do UCLN(4,26) = 2 nªn 4x +7 kh«ng lµ hµm m· ho¸ hîp lÖ: x vµ x+13 sÏ m· ho¸ thµnh cïng mét gi¸ trÞ ®èi víi bÊt k× x ∈ Z26 . Ta gi¶ thiÕt UCLN(a,26) = 1. Gi¶ sö víi x 1 vµ x2 nµo ®ã th¶o m·n: ax1 ≡ ax2 (mod 26) Khi ®ã a(x1- x2) ≡ 0(mod 26) bëi vËy 26 | a(x1- x2) B©y giê ta sÏ sö dông mét tÝnh chÊt cña phÐp chia sau: NÕu USLN(a,b)=1 vµ a  th× a  V× 26  a(x1- x2) vµ USLN(a,26) = 1 bc c. nªn ta cã: 26 1- x2) (x tøc lµ x1 ≡ x2 (mod 26) Tíi ®©y ta chøng tá r»ng, nÕu UCLN(a,26) = 1 th× mét ®ång d thøc d¹ng ax ≡ y (mod 26) chØ cã (nhiÒu nhÊt) mét nghiÖm trong Z26 . Do ®ã , nÕu ta cho x thay ®æi trªn Z 26 th× ax mod 26 sÏ nhËn ®îc 26 gi¸ trÞ kh¸c nhau theo modulo 26 vµ ®ång d thøc ax ≡ y (mod 26) chØ cã mét nghiÖm y duy nhÊt. Kh«ng cã g× ®Æc biÖt ®èi v¬Ý sè 26 trong kh¼ng ®Þnh nµy. Bëi vËy, b»ng c¸ch t¬ng tù ta cã thÓ chøng minh ®îc kÕt qu¶ sau: §Þnh lÝ 1.1 §ång d thøc ax ≡ b mod m chØ cã mét nghiÖm duy nhÊt x ∈ Zm víi mäi b ∈ Zm khi vµ chØ khi UCLN(a,m) = 1. V× 26 = 2 × 13 nªn c¸c gi¸ trÞ a ∈ Z26 tho¶ m·n UCLN(a,26) = 1 lµ a = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 vµ 25. Tham sè b cã thÓ lµ mét phÇn tö bÊt kú trong Z 26 . Nh vËy, m· Affine cã 12 × 26 = 312 kho¸ cã thÓ ( dÜ nhiªn con sè nµy qu¸ nhØ ®Ó b¶o ®¶m an toµn). B©y giê ta sÏ xÐt bµi to¸n chung víi modulo m. Ta cÇn mét ®Þnh nghÜa kh¸c trong lý thuyÕt sè.
§Þnh nghÜa 1.3 Gi¶ sö a ≥ 1 vµ m ≥ 2 lµ c¸c sè nguyªn. UCLN(a,m) = 1 th× ta nãi r»ng a vµ m lµ nguyªn tè cïng nhau. Sè c¸c sè nguyªn trong Z m nguyªn tè cïng nhau víi m thêng ®îc ký hiÖu lµ φ(m) ( hµm nµy ®îc gäi lµ hµm Euler). Mét kÕt qu¶ quan träng trong lý thuyÕt sè cho ta gi¸ trÞ cña φ(m) theo c¸c thõa sè trong phÐp ph©n tÝch theo luü thõa c¸c sè nguyªn tè cña m. ( Mét sè nguyªn p >1 lµ sè nguyªn tè nÕu nã kh«ng cã íc d¬ng nµo kh¸c ngoµi 1 vµ p. Mäi sè nguyªn m >1 cã thÓ ph©n tÝch ®îc thµnh tÝch cña c¸c luü thõa c¸c sè nguyªn tè theo c¸ch duy nhÊt. VÝ dô 60 = 2 3 × 3 × 5 vµ 98 = 2 × 7 2 ). Ta sÏ ghi l¹i c«ng thøc cho φ(m) trong ®Þnh lÝ sau: §Þnh lý 1.2. ( thiÕu ) Gi¶ sö m = ∏ pi Trong ®ã c¸c sè nguyªn tè pi kh¸c nhau vµ ei >0 ,1 §Þnh lý nµy cho thÊy r»ng, sè kho¸ trong m· Affine trªn Z m b»ng mφ(m), trong ®ã φ(m) ®îc cho theo c«ng thøc trªn. ( Sè c¸c phÐp chän cña b lµ m vµ sè c¸c phÐp chän cña a lµ φ(m) víi hµm m· ho¸ lµ e(x) = ax + b). VÝ dô, khi m = 60, φ(60) = 2 × 2 × 4 = 16 vµ sè c¸c kho¸ trong m· Affine lµ 960. B©y giê ta sÏ xÐt xem c¸c phÐp to¸n gi¶i m· trong mËt m· Affine víi modulo m = 26. Gi¶ sö UCLN(a,26) = 1. §Ó gi¶i m· cÇn gi¶i ph¬ng tr×nh ®ång d y ≡ ax+b (mod 26) theo x. Tõ th¶o luËn trªn thÊy r»ng, ph¬ng tr×nh nµy cã mét nghiÖm duy nhÊt trong Z 26 . Tuy nhiªn ta vÉn cha biÕt mét ph¬ng ph¸p h÷u hiÖu ®Ó t×m nghiÖm. §iÒu cÇn thiÕt ë ®©y lµ cã mét thuËt to¸n h÷u hiÖu ®Ó lµm viÖc ®ã. RÊt mayb lµ mét sè kÕt qu¶ tiÕp sau vÒ sè häc modulo sÏ cung cÊp mét thuËt to¸n gi¶i m· h÷u hiÖu cÇn t×m. §Þnh nghÜa 1.4
Gi¶ sö a ∈ Zm . PhÇn tö nghÞch ®¶o (theo phÐp nh©n) cña a lµ phÇn tö a-1 ∈ Zm sao cho aa-1 ≡ a-1a ≡ 1 (mod m). B»ng c¸c lý luËn t¬ng tù nh trªn, cã thÓ chøng tá r»ng a cã nghÞch ®¶o theo modulo m khi vµ chØ khi UCLN(a,m) =1, vµ nÕu nghÞch ®¶o nµy tån t¹i th× nã ph¶i lµ duy nhÊt. Ta còng thÊy r»ng, nÕu b = a-1 th× a = b-1 . NÕu p lµ sè nguyªn tè th× mäi phÇn tö kh¸c kh«ng cña ZP ®Òu cã nghÞch ®¶o. Mét vµnh trong ®ã mäi phÇn tö ®Òu cã nghÞch ®¶o ®îc gäi lµ mét trêng. Trong phÇn sau sÏ m« t¶ mét thuËt to¸n h÷u hiÖu ®Ó tÝnh c¸c nghÞch ®¶o cña Zm víi m tuú ý. Tuy nhiªn, trong Z 26 , chØ b»ng ph- ¬ng ph¸p thö vµ sai còng cã thÓ t×m ®îc c¸c nghÞch ®¶o cña c¸c phÇn tö nguyªn tè cïng nhau víi 26: 1 -1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 = 19, 17-1 =23, 25-1 = 25. (Cã thÓ dÔ dµng kiÓm chøng l¹i ®iÒu nµy, vÝ dô: 7 × 5 = 105 ≡ 1 mod 26, bëi vËy 7-1 = 15). XÐt ph¬ng tr×nh ®ång d y ≡ ax+b (mod 26). Ph¬ng tr×nh nµy t¬ng ®¬ng víi ax ≡ y-b ( mod 26) V× UCLN(a,26) =1 nªn a cã nghÞch ®¶o theo modulo 26. Nh©n c¶ hai vÕ cña ®ång d thøc víi a-1 ta cã: a-1(ax) ≡ a-1(y-b) (mod 26) ¸p dông tÝnh kÕt hîp cña phÐp nh©n modulo: a-1(ax) ≡ (a-1a)x ≡ 1x ≡ x. KÕt qu¶ lµ x ≡ a-1(y-b) (mod 26). §©y lµ mét c«ng thøc têng minh cho x. Nh vËy hµm gi¶i m· lµ: d(y) = a-1(y-b) mod 26
H×nh 1.4 cho m« t¶ ®Çy ®ñ vÒ m· Affine. Sau ®©y lµ mét vÝ dô nhá H×nh 1.4 MËt m·A ffine Cho P = C = Z26 vµ gi¶ sö P = { (a,b) ∈ Z26 × Z26 : UCLN(a,26) =1 } Víi K = (a,b) ∈K , ta ®Þnh nghÜa: eK(x) = ax +b mod 26 vµ dK(y) = a-1(y-b) mod 26, x,y ∈ Z26 VÝ dô 1.3 Gi¶ sö K = (7,3). Nh ®· nªu ë trªn, 7-1 mod 26 = 15. Hµm m· ho¸ lµ eK(x) = 7x+3 Vµ hµm gi¶i m· t¬ng øng lµ: dK(x) = 15(y-3) = 15y -19 ë ®©y, tÊt c¶ c¸c phÐp to¸n ®Òu thùc hiÖn trªn Z26. Ta sÏ kiÓm tra liÖu dK(eK(x)) = x víi mäi x ∈ Z26 kh«ng?. Dïng c¸c tÝnh to¸n trªn Z26 , ta cã dK(eK(x)) =dK(7x+3) =15(7x+3)-19 = x +45 -19 = x. §Ó minh ho¹, ta h·y m· ho¸ b¶n râ "hot". Tríc tiªn biÕn ®æi c¸c ch÷ h, o, t thµnh c¸c thÆng du theo modulo 26. Ta ®îc c¸c sè t¬ng øng lµ 7, 14 vµ 19. B©y giê sÏ m· ho¸: 7 × 7 +3 mod 26 = 52 mod 26 = 0
7 × 14 + 3 mod 26 = 101 mod 26 =23 7 × 19 +3 mod 26 = 136 mod 26 = 6 Bëi vËy 3 ký hiÖu cña b¶n m· lµ 0, 23 vµ 6 t¬ng øng víi x©u ký tù AXG. ViÖc gi¶i m· sÏ do b¹n ®äc thùc hiÖn nh mét bµi tËp. 1.1.4 M· VigenÌre Trong c¶ hai hÖ MDV vµ MTT (mét khi kho¸ ®· ®îc chän) mçi ký tù sÏ ®îc ¸nh x¹ vµo mét ký tù duy nhÊt. V× lý do ®ã, c¸c hÖ mËt cßn ®îc gäi hÖ thay thÕ ®¬n biÓu. B©y giê ta sÏ tr×nh bµy ( trong hïnh 1.5) mét hÖ mËt kh«ng ph¶i lµ bé ch÷ ®¬n, ®ã lµ hÖ m· VigenÌre næi tiÕng. MËt m· nµy lÊy tªn cña Blaise de VigenÌre sèng vµo thÕ kû XVI. Sö dông phÐp t¬ng øng A ⇔ 0, B ⇔ 1, . . . , Z ⇔ 25 m« t¶ ë trªn, ta cã thÓ g¾n cho mçi khoa K víi mét chuçi kÝ tù cã ®é dµi m ®îc gäi lµ tõ kho¸. MËt m· VigenÌre sÏ m· ho¸ ®ång thêi m kÝ tù: Mçi phÇn tö cña b¶n râ t¬ng ®¬ng víi m ký tù. XÐt mét vÝ dô nhá VÝ dô 1.4 Gi¶ sö m =6 vµ tõ kho¸ lµ CIPHER. Tõ kho¸ nµy t¬ng øng víi d·y sè K = (2,8,15,4,17). Gi¶ sö b¶n râ lµ x©u: thiscryptosystemisnotsecure H×nh 1.5 MËt m· VigenÌre Cho m lµ mét sè nguyªn d¬ng cè ®Þnh nµo ®ã. §Þnh nghÜa P = C = K = (Z26)m . Víi kho¸ K = (k1, k2, . . . ,km) ta x¸c ®Þnh : eK(x1, x2, . . . ,xm) = (x1+k1, x2+k2, . . . , xm+km) vµ dK(y1, y2, . . . ,ym) = (y1-k1, y2-k2, . . . , ym-km) trong ®ã tÊt c¶ c¸c phÐp to¸n ®îc thùc hiÖn trong Z26
Ta sÏ biÕn ®æi c¸c phÇn tö cña b¶n râ thµnh c¸c thÆng d theo modulo 26, viÕt chóng thµnh c¸c nhãm 6 råi céng víi tõ kho¸ theo modulo 26 nh sau: 19 7 8 18 2 17 24 15 19 14 18 24 2 8 15 7 4 17 2 8 15 7 4 17 21 15 23 25 6 8 0 23 8 21 22 15 18 19 4 12 8 18 13 14 19 18 4 2 2 8 15 7 4 17 2 8 15 7 4 17 20 1 19 19 12 9 15 22 8 15 8 19 20 17 4 2 8 15 22 25 19 Bëi vËy, d·y ký tù t¬ng øng cña x©u b¶n m· sÏ lµ: VPXZGIAXIVWPUBTTMJPWIZITWZT §Ó gi¶i m· ta cã thÓ dïng cïng tõ kho¸ nhng thay cho céng, ta trõ cho nã theo modulo 26. Ta thÊy r»ng c¸c tõ kho¸ cã thÓ víi sè ®é dµi m trong mËt m· VigenÌre lµ 26m, bëi vËy, thËm chÝ víi c¸c gi¸ trÞ m kh¸ nhá, ph¬ng ph¸p t×m kiÕm vÐt c¹n còng yªu cÇu thêi gian kh¸ lín. VÝ dô, nÕu m = 5 th× kh«ng gian kho¸ còng cã kÝch thíc lín h¬n 1,1 × 107 . Lîng kho¸ nµy ®· ®ñ lín ®Ó ngaen ngõa viÖc t×m kho¸ b»ng tay( chø kh«ng ph¶i dïng m¸y tÝnh).
Trong hÖ mËt VigenÌre cã tõ kho¸ ®é dµi m,mçi ký tù cã thÓ ®- îc ¸nh x¹ vµo trong m ký tù cã thÓ cã (gi¶ sö r»ng tõ kho¸ chøa m ký tù ph©n biÖt). Mét hÖ mËt nh vËy ®îc gäi lµ hÖ mËt thay thÕ ®a biÓu (polyalphabetic). Nãi chung, viÖc th¸m m· hÖ thay thÕ ®a biÓu sÏ khã kh¨n h¬n so viÖc th¸m m· hÖ ®¬n biÓu. 1.1.5 MËt m· Hill Trong phÇn nµy sÏ m« t¶ mét hÖ mËt thay thÕ ®a biÓu kh¸c ®- îc gäi lµ mËt m· Hill. MËt m· nµy do Lester S.Hill ®a ra n¨m 1929. Gi¶ sö m lµ mét sè nguyªn d¬ng, ®Æt P = C = (Z26)m . ý tëng ë ®©y lµ lÊy m tæ hîp tuyÕn tÝnh cña m ký tù trong mét phÇn tö cña b¶n râ ®Ó t¹o ra m ký tù ë mét phÇn tö cña b¶n m·. VÝ dô nÕu m = 2 ta cã thÓ viÕt mét phÇn tö cña b¶n râ lµ x = (x1,x2) vµ mét phÇn tö cña b¶n m· lµ y = (y1,y2). ë ®©y, y1còng nh y2 ®Òu lµ mét tæ hîp tuyÕn tÝnh cña x1vµ x2. Ch¼ng h¹n, cã thÓ lÊy y1 = 11x1+ 3x2 y2 = 8x1+ 7x2 TÊt nhiªn cã thÓ viÕt gän h¬n theo ký hiÖu ma trËn nh sau 11 8 (y1 y2) = (x1 x2) 3 7 Nãi chung, cã thÓ lÊy mét ma trËn K kÝch thíc m × m lµm kho¸. NÕu mét phÇn tö ë hµng i vµ cét j cña K lµ k i,,j th× cã thÓ viÕt K = (ki,,j), víi x = (x1, x2, . . . ,xm) ∈ P vµ K ∈K , ta tÝnh y = eK(x) = (y1, y2, . . . ,ym) nh sau: k1,1 k1,2 ... k1,m (y1,. . .,ym) k2,1 k2,2 ... k2,m (x1, . . . ,xm) ... ... ... .. km,1 km,2 ... km,m
Nãi mét c¸ch kh¸c y = xK. Chóng ta nãi r»ng b¶n m· nhËn ®îc tõ b¶n râ nhê phÐp biÕn ®æi tuyÕn tÝnh. Ta sÏ xÐt xem ph¶i thùc hiÖn gi¶i m· nh thÕ nµo, tøc lµ lµm thÕ nµo ®Ó tÝnh x tõ y. B¹n ®äc ®· lµm quen víi ®¹i sè tuyÕn tÝnh sÏ thÊy r»ng ph¶i dïng ma trËn nghÞch ®¶o K -1 ®Ó gi¶ m·. B¶n m· ®îc gi¶i m· b»ng c«ng thøc y K-1 . Sau ®©y lµ mét sè ®Þnh nghÜa vÒ nh÷ng kh¸i niÖm cÇn thiÕt lÊy tõ ®¹i sè tuyÕn tÝnh. NÕu A = (x i,j) lµ mét ma trËn cÊp l × m vµ B = (b1,k ) lµ mét ma trËn cÊp m × n th× tÝch ma trËn AB = (c1,k ) ®îc m c1,k = Σ ai,j bj,k j=1 ®Þnh nghÜa theo c«ng thøc: 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. CÇn ®Ó ý r»ng AB lµ mét ma trËn cÊ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)) nhng 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è 1 n»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µ: 1 0 I2 = 0 1 Im ®îc gäi lµ ma trËn ®¬n vÞ v× AI m = A víi mäi ma trËn cÊp l × m vµ ImB =B ví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 ma trËn ®Òu cã nghÞch ®¶o, nhng 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 -1 8 18 3 7 = 23 11 Z26: v× 8 18 = 11× 7+ 23 11× 18+ 11 8× 8× 3 7 23 3× 7+ 23 7× 3× 18+ 11 7× 11 261 0 = 286 = 0 1 182 131 (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Ët m· Hill. Via dô 1.5 11 8 Gi¶ sö kho¸ K = 3 7 Tõ c¸c tÝnh to¸n trªn ta cã: 7 18 K-1 = 23 11
Gi¶ 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: vµ Bëi vËy b¶n m· cña July lµ DELW. §Ó gi¶i m· Bob sÏ tÝnh vµ 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· 8 (9,20) 8 =(99+ 72+ 60, 140) =(3,4) (11,24) 3 7 =(121+ 88+ 72, 168) = 3 7 18 (3,4) (11,22) = (9,20) 23 11 nÕu K cã mét nghÞch ®¶o. Trªn thùc tÕ, ®Ó phÐp gi¶i m· lµ cã thÓ 18 (11,22) = (11,24) 23 11 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 ta chØ 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Þ ®Þnh thøc cña nã. §Ó tr¸nh sù tæng qu¸t ho¸ kh«ng cÇn thiÕt, ta chØ giíi h¹n trong trê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,1 NhËn xÐt: §Þnh thøc cña mét ma trËn vu«ng cÊp mm cã thÓ ®îc tÝnh theo c¸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Õn tÝnh. Hai tÝnh chÊt quan träng cña ®Þnh thøc lµ det Im = 1 vµ quy t¾c nh©n det(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Õt qu¶ t¬ng øng lµ ma trËn K cã nghÞch ®¶o theo modulo 26 khi vµ chØ khi UCLN(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õ K b»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Çn tö (i,j) cña nã nhËn gi¸ trÞ(-1) det K j i (K* ®îc gäi lµ ma trËn bï ®¹i sè cña K). Khi ®ã cã thÓ chøng tá r»ng: K-1 = (det K)-1K* . Bëi vËy K lµ kh¶ nghÞch. Ngîc l¹i K cã nghÞch ®¶o K-1 . Theo quy t¾c nh©n cña ®Þnh thøc 1 = det I = det (KK-1) = det K det K-1 Bëi vËy det K cã nghÞch ®¶o trong Z26 . NhËn xÐt: C«ng thøc ®èi víi ë trªn kh«ng ph¶i lµ mét c«ng thøc tÝnh to¸n cã hiÖu qu¶ trõ c¸c trêng hîp m nhá ( ch¼ng h¹n m = 2, 3). Víim lín, ph¬ng ph¸p thÝch hîp ®Ó tÝnh c¸c ma trËn nghÞch ®¶o ph¶i dùa vµo c¸c phÐp to¸n h»ng s¬ cÊp. Trong trêng hîp 2× 2, ta cã c«ng thøc sau: §Þnh lý 1.3 Gi¶ sö A = (ai j) lµ mét ma trËn cÊp 2 × 2 trªn Z26 sao cho det A = a1,1a2,2 - a1,2 a2,1 cã nghÞch ®¶o. Khi ®ã a2,2 -a1,2 -1 -1 A =(det A) -a2,1 a1,1 Trë l¹i vÝ dô ®· xÐt ë trªn . Tríc hÕt ta cã: det 8 =11 × 7 - 8 × 3 mod 2 3 =77 - 24 mod 26 =53 mod 7 26 =1 -1 8 18 3 7 = 23