Giáo trình Mật mã và ứng dụng: Chương 1

Giáo trình Mật mã và ứng dụng - Chương 1: Mật mã cổ điển, trình bày các nội dung chính: mật mã cổ điển, một số hệ mật cơ bản, mã dịch vòng, mã thay thế, mã Affine, mật mã Hill, mã hoán vị, các hệ mã dòng, mật mã khóa tự sinh, mã thám các hệ mã cổ điển, thám hệ mã thay thế, thám hệ mã dòng xây dựng trên LFSR,... Đây là tài liệu tham khảo dành cho sinh viên ngành Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Giáo trình Mật mã và ứng dụng: Chương 1 Ch−¬ng 1 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 khãa ® ®−îc x¸c ®Þnh tr−íc v göi b¶n m kÕt qu¶ lªn kªnh liªn l¹c . 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 mm : dk(ek (x)) = x víi mäi b¶n râ x ∈ P. 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 Alic Bé m Bé gi¶i Bo 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) 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 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 giao 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 ...