Lý thuyết mật mã - Chapter 1

Mật m∙ cổ điển1.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ênhkhông mật cho hai ng−ời sử dụng (tạm gọi lμ Alice vμ Bob) sao cho đốiph−ơ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ỳ ý....
Nội dung trích xuất từ tài liệu:
Lý thuyết mật mã - Chapter 1Vietebooks Nguyễn Hoàng Cương Ch−¬ng 1 MËt m∙ cæ ®iÓn1.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ªnhkh«ng mËt cho hai ng−êi sö dông (t¹m gäi lµ Alice vµ Bob) sao cho ®èiph−¬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¶nrâ 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 dungcña b¶n râ, nh−ng Bob (ng−êi ®· biÕt kho¸ m·) cã thÓ gi¶i m· vµ thu ®−îcb¶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äcnh− 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Õumé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 theodâ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µ taxem th«ng b¸o nµy lµ mét chuçi: Trang 1Vietebooks Nguyễn Hoàng Cương x = x1,x2 ,. . .,xnví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 ,. . .,ynsÏ ®−î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¹cH×nh 1.1. Kªnh liªn l¹c Oscar Bé m· ho¸ Alice 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−êngminh. 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¸nvÞ, 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µmm· 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 2Vietebooks 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−íctiª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) ®−îcgä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 (modm) khi vµ chØ khi r1 = r2 . Ta sÏ dïng ký hiÖu a mod m (kh«ng dïng c¸c dÊungoÆ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»nga 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Çnd− 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. Tuynhiª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©ntrong 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 ...