Tài liệu 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

Vietebooks Nguyễn Hoàng Cương Ch−¬ng 1 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ó MËt m∙ cæ ®iÓn 1.1 më ®Ç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 kho¸ ®−îc x¸c ®Þ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â. 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: Trang 1 Vietebooks Nguyễn Hoàng Cương 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¸ lµ mét phÐp ho¸n vÞ, tøc lµ nÕu tË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) Trang 2 Vietebooks Nguyễn Hoàng Cương 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 = q1m + 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 r1 = 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Þ r1 ë 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: Zm ®−î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 Trang 3 Vietebooks Nguyễn Hoàng Cương 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 Zm 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 Zm . 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 Zm 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 Z31, 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) Trang 4 Vietebooks Nguyễn Hoàng Cương 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 0 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9 K L M 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 0 4 19 22 12 8 8 11 3 11 13 12 8 4 6 4 7 19 19 sau ®ã céng 11 vµo mçi gi¸ trÞ råi rót gän tæng theo modulo 26 7 11 15 4 7 23 19 19 22 14 22 24 23 19 15 17 15 18 4 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ù. Trang 5