Mật mã - Khoa học khám phá: Phần 1

Tài liệu “Mật mã” (The Code Book) sẽ dẫn dắt chúng ta nhìn lại lịch sử dưới góc nhìn của mật mã học. Tài liệu bắt đầu bằng những dạng mật mã đơn giản nhất ra đời từ cuối thế kỉ 16 và kết thúc ở cuối thế kỉ 20 bằng việc giới thiệu về ý tưởng mật mã lượng tử, một loại mật mã được cho là bất khả chiến bại dựa trên lí thuyết lượng tử. Mời các bạn cùng tham khảo nội dung phần 1 Tài liệu.
Nội dung trích xuất từ tài liệu:
Mật mã - Khoa học khám phá: Phần 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 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−ê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µc¸c kÕt qu¶ ®−îc rót gän theo ...