intTypePromotion=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ó phần 9

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:5

0
61
lượt xem
2
download

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ó phần 9

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

Cuốn " Những ng−ời mã thám " của Kahn [KA67] là một cấu chuyện hấp dẫn và phong phú về mật mã cho tới năm 1967, trong đó Kahn khẳng định rằng mật mã Vigenère thực sự không phải là phát minh của Vigenère.

Chủ đề:
Lưu

Nội dung Text: 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ó phần 9

  1. Vietebooks Nguyễn Hoàng Cương gi¸ cho 26 kÝ tù ®−îc lÊy cña Beker vµ Piper. Còng vËy, viÖc ph©n tÝch m· VigenÌre ®−îc söa ®æi theo m« t¶ cña Beker vµ Piper. Rosen [Ro93] lµ mét tµi liÖu tham kh¶o tèt vÒ lý thuyÕt sè. C¬ së cña §¹i sè tuyÕn tÝnh s¬ cÊp cã thÓ t×m thÊy trong s¸ch cña Anton [AN91]. Cuèn " Nh÷ng ng−êi m· th¸m " cña Kahn [KA67] lµ mét cÊu chuyÖn hÊp dÉn vµ phong phó vÒ mËt m· cho tíi n¨m 1967, trong ®ã Kahn kh¼ng ®Þnh r»ng mËt m· VigenÌre thùc sù kh«ng ph¶i lµ ph¸t minh cña VigenÌre. MËt m· Hill lÇn ®Çu tiªn ®−îc m« t¶ trong [HI29]. C¸c th«ng tin vÒ mËt m· dßng cã thÓ t×m ®−îc trong s¸ch cña Rueppel [RU86]. Bµi tËp 1.1. D−íi ®©y lµ 4 b¶n m· thu ®−îc tõ m· thay thÕ. Mét b¶n thu ®−îc tõ m· VigenÌre, mét tõ mËt m· Affine vµ mét b¶n ch−a x¸c ®Þnh. NhiÖm vô ë ®©y lµ x¸c ®Þnh b¶n râ trong mçi tr−êng hîp. H·y m« t¶ c¸c b−íc cÇn thùc hiÖn ®Ó gi¶i m· mçi b¶n m· ( bao gåm tÊt c¶ c¸c ph©n tÝch thèng kª vµ c¸c tÝnh to¸n cÇn thùc hiÖn). Hai b¶n râ ®Çu lÊy tõ cuèn " The diary of samuenl marchbanks " cña Robertson Davies, Clack Iriwin,1947; b¶n râ thø t− lÊy tõ " Lake wobegon days" cña Garrison Keillor, Viking Penguin, 1985. a) M· thay thÕ: EMGLXUDCGDNCUSWYXFPHNSFCYKDPUMLWGYICOXYFIPJCK QPKUGKMGOLICGINCGACKFNIFACYKZSCKXECJCKFHYFXCG 0IDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUFIGLEDFPWZU GFZCCNDGYYFFUSZCNXEOJNCGYEOWEUPXEZGACGNFGLKNF ACIGOYCKXCJUCIUZCFZCCNDGYYSFEUEKUZCSOCSZCCNC IACZEJNCFFZEJZEGMXCYHCJUMGKUSI ChØ dÉn: F sÏ gi¶i m· thµnh W. b) HÖ m· VigenÌre KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGLLTXRGUD DKBTMBPVGEGLTGCKQRACQCWDNAWCRXIZAKSTLEWRPTYC QKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRL SVSKCGCZQQDZXGSFRLFWCWSJTBHAFSIASPRJAHKJRJUMP FFSQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHI CWHJVLNHIQIBTKHJVNPIST Trang 41
  2. Vietebooks Nguyễn Hoàng Cương c) HÖ m· Affine. KQEREJEBCPPCJCRKIEACUZBKRVPKRBCIBQCARBJCVFCUP KRIOFKPACUZQEPBKRXPEIIEABDKPBCPFCDCAFIEABDKP BCPFEQPKAZBKRHAIBKAPCCIBURCCDKDCCJCIDFUIXPAFF ERBICZDFKABICBBENEFCUPJCVKABPCYDCCDPKBCOCPERK IVKSCPICBRKIJPKABI d) HÖ m· ch−a x¸c ®Þnh ®−îc. BNVSNSIHQCEELSSKKYERISJKXUMBGYKAMQLJTYAVFBKVT DVBPVVRJYYLAOKYMPQSCGDLFLLPROYGEFEBUUALRWXM MASAZLGLEDFJBZAVVPXWYCGJXASCBYEHOSNMULKCEAHTQ OKMFLEBKFXLRRFDTZXCIWBJSICBGAWDVYDHAVFJXZIBKC GJIWEAHTTOEWTUHKRQVVRGZBXYIREMMASCSPBNLHJGBLR FFJELHWEYLWISTFVVYFJCMHYURUFSFMGESIGRLWALSWM NUHSIMYYITCCQPZSICEHBCCMZFEGVJYOCDEMMPGHVAAMU ELCMOEHVLTIPSUYILVGFLMVWDVYDBTHERAYISYSGKVSUU HYHGGCKTMBLRX 1.2. a) Cã bao nhiªu ma trËn kh¶ nghÞch cÊp 2×2 trªn Z26 . b) Gi¶ sö p lµ sè nguyªn tè. H·y chøng tá sè c¸c ma trËn kh¶ nghÞch cÊp 2×2 trªn Zp lµ (p2-1)(p2-p). ChØ dÉn: V× p lµ sè nguyªn tè nªn Zp lµ mét tr−êng. H·y sö dông kh¼ng ®Þnh sau: Mét ma trËn lµ kh¶ nghÞch trªn mét tr−êng lµ kh¶ nghÞch khi vµ chØ khi c¸c hµng cña nã lµ c¸c vÐc t¬ ®éc lËp tuyÕn tÝnh ( tøc kh«ng tån t¹i mét tæ hîp tuyÕn tÝnh c¸c hµng kh¸c 0 mµ tæng cña chóng lµ mét vÐc t¬ toµn sè 0). c) Víi p lµ sè nguyªn tè vµ m lµ mét sè nguyªn ≥ 2. H·y t×m c«ng thøc tÝnh sè c¸c ma trËn kh¶ nghÞch cÊp m×m trªn Zp. 1.3. §«i khi chän mét kho¸ mµ phÐp m· vµ gi¶i m· lµ ®ång nhÊt rÊt h÷u Ých. Trong tr−êng hîp mÊt m· Hill, ta ph¶i t×m c¸c ma trËn K sao cho K = K-1 ( ma trËn nµy ®−îc gäi lµ ma trËn ®èi hîp). Trªn thùc tÕ, Hill ®· ®Ò nghÞ sö dông c¸c ma trËn nµy lµm kho¸ trong c¸c hÖ mËt cña m×nh. H·y x¸c ®Þnh sè c¸c ma trËn ®èi hîp trªn Z26 trong tr−êng hîp m = 2. ChØ dÉn: H·y dïng c«ng thøc trong ®Þnh lý 1.3 vµ ®Ó ý r»ng detA = ± víi mét ma trËn ®èi hîp trªn Z26. 1.4. Gi¶ sö ta ®· biÕt r»ng b¶n râ " conversation " sÏ t¹o nªn b¶n m· " HIARRTNUYTUS " ( ®−îc m· theo hÖ m· Hill nh−ng ch−a x¸c ®Þnh ®−îc m). H·y x¸c ®Þnh ma trËn m· ho¸. Trang 42
  3. Vietebooks Nguyễn Hoàng Cương 1.5. HÖ m· Affine - Hill lµ hÖ m· Hill ®−îc söa ®æi nh− sau: Gi¶ sö m lµ mét sè nguyªn d−¬ng vµ P = C = (Z26)m. Trong hÖ mËt nµy, kho¸ K gåm c¸c cÆp (L,b), trong ®ã L lµ mät ma trËn kh¶ nghÞch cÊp m×m trªn Z26 vµ b∈(Z26)m. Víi x = ( x1,. . .,xm)∈P vµ K = (L,b) ∈ K, ta tÝnh y = eK(x) = (y1,. . .,ym) theo c«ng thøc y = xL + b. Bëi vËy, nÕu L = (li,j) vµ b = (b1,. . .,bm) th×: ⎡l 1,1 l 1,2 ⎤ . . . l 1,m ⎢ ⎥ ⎢l 2,1 l 2,2 . . . l 2, m ⎥ (y 1 ,...,y m ) = (x 1 ,....,x m )⎢. ⎥ + ( b ,.....,b ) . . . . ⎢ ⎥ 1 m ⎢. ⎥ . . . . ⎢l l m,m ⎥ ⎣ m,1 l m,2 . . . ⎦ Gi¶ sö Oscar ®· biÕt b¶n râ lµ "adisplayedequation" vµ b¶n m· t−¬ng øng lµ " DSRMSIOPLXLJBZULLM". Oscar còng biÕt m =3. H×nh tÝnh kho¸ vµ chØ ra tÊt c¶ c¸c tÝnh to¸n cÇn thiÕt. 1.6. Sau ®©y lµ c¸ch th¸m m· hÖ m· Hill sö dông ph−¬ng ph¸p tÊn c«ng chØ víi b¶n m·. Gi¶ sö ta biÕt m = 2. Chia c¸c b¶n m· thµnh c¸c khèi cã ®é dµi 2 kÝ tù ( c¸c bé ®«i). Mçi bé ®«i nµy lµ b¶n m· cña mét bé ®«i cña b¶n râ nhê dïng mét ma trËn m· ho¸ ch−a biÕt. H·y nhÆt ra c¸c bé ®«i th−êng gÆp nhÊt trong b¶n m· vµ coi r»ng ®ã lµ m· cña mét bé ®«i th−êng gÆp trong danh s¸ch ë b¶ng 1.1 ( vÝ dô TH vµ ST). Víi mçi gi¶ ®Þnh, h·y thùc hiÖn phÐp tÊn c«ng víi b¶n râ ®· biÕt cho tíi khi t×m ®−îc ma trËn gi¶i m· ®óng. Sau ®©y lµ mét vÝ dô vÒ b¶n m· ®Ó b¹n gi¶i m· theo ph−¬ng ph¸p ®· nªu: LMQETXYEAGTXCTUIEWNCTXLZEWUAISPZYVAPEWLMGQWYA XFTCJMSQCADAGTXLMDXNXSNPJQSYVAPRIQSMHNOCVAXFV. 1.7. Ta sÏ m« t¶ mét tr−êng hîp ®Æc biÖt cña m· ho¸n vÞ. Gi¶ sö m, n lµ c¸c sè nguyªn d−¬ng. H·y viÕt b¶n râ theo thµnh tõng hµng thµnh mét h×nh ch÷ nhËt m×n. Sau ®ã t¹o ra b¶n m· b»ng c¸ch lÊy c¸c cét cña h×nh ch÷ nhËt nµy. VÝ dô, nÕu m = 4, n = 3 th× ta sÏ m· ho¸ b¶n râ "cryptography" b»ng c¸ch x©y dùng h×nh ch÷ nhËt : cryp togr aphy B¶n m· sÏ lµ: 'CTAROPYGHPRY' a) H·y m« t¶ c¸ch Bob gi¶i m· mét b¶n m· ( víi m, n ®· biÕt) b) H·y gi¶i m· b¶n m· sau: ( nhËn ®−îc theo ph−¬ng ph¸p ®· nªu): Trang 43
  4. Vietebooks Nguyễn Hoàng Cương MYAMRARUYIQTENCTORAHROYWDSOYEOUARRGDERNOGW 1.8. Cã 8 phÐp ®Ö quy tuyÕn tÝnh bËc 4 kh¸c nhau trªn Z2 víi c0 = 1. H·y x¸c ®Þnh nh÷ng phÐp ®Ö quy nµo t¹o ®−îc dßng kho¸ cã chu kú 15 ( víi vÐc t¬ khëi t¹o kh¸c 0). 1.9. Môc ®Ých cña bµi tËp nµy ®Ó chøng minh kh¼ng ®Þnh ë phÇn 1.2.5 lµ : ma trËn hÖ sè cÊp m×m cã nghÞch ®¶o. §iÒu nµy t−¬ng ®−¬ng víi kh¼ng ®Þnh r»ng, c¸c hµng ma trËn nµy lµ c¸c vÐc t¬ ®éc lËp tuyÕn tÝnh trªn Z2. Gi¶ sö r»ng phÐp ®Ö quy cã d¹ng: m −1 z m + i = ∑ c j z i + j mod 2 j =0 ( z1,. . .,zm) lµ vÐc t¬ khëi t¹o. Víi i ≥ 1 ta x¸c ®Þnh: vi = (zi,. . .,zi+m-1) Chó ý r»ng, ma trËn hÖ sè cã c¸c vÐc t¬ v1,. . .,vm lµ c¸c hµng cña nã. Bëi vËy, nhiÖm vô cña ta lµ chøng tá r»ng m vÐc t¬ nµy lµ ®éc lËp tuyÕn tÝnh. H·y chøng minh hai kh¼ng ®Þnh sau: a) Víi i ≥ 1 bÊt k×: m −1 v m+ i = ∑ c j v i + j mod 2 j =0 b)Chän h lµ sè nguyªn nhá nhÊt sao cho tån t¹i mét tæ hîp tuyÕn tÝnh kh«ng tÇm th−êng cña c¸c vÐc t¬ v1,. . .,vh cã tæng lµ vÐc t¬ (0, . . . , 0) theo modulo 2. Khi ®ã: h −2 v h = ∑ c j v j +1 mod 2 j =0 ( C¸c αj kh«ng ®ång nhÊt b»ng 0). §Ó ý r»ng, h ≤ m+1 v× m+1 lµ vÐc t¬ bÊt kú trong kh«ng gian tuyÕn tÝnh m chiÒu ®Òu phô thuéc tuyÕn tÝnh . c) H·y chøng tá r»ng dßng kho¸ ph¶i th¶o m·n phÐp ®Ö quy: h −2 z h −1+ i = ∑α j z j + i mod 2 j =0 víi bÊt k× i ≥ 1. Trang 44
  5. Vietebooks Nguyễn Hoàng Cương d) Ta nhËn thÊy r»ng, nÕu h ≤ m th× dßng kho¸ th¶o m·n phÐp ®Ö quy tuyÕn tÝnh cã bËc nhá h¬n m. §iÒu nµy m©u thuÉn. Bëi vËy h = m + 1 vµ ma trËn ph¶i lµ kh¶ nghÞch. 1.10. H·y gi¶i m· b¶n m· sau ( thu ®−îc tõ m· kho¸ tù sinh ) b»ng ph−¬ng ph¸p t×m kho¸ vÐt c¹n. MALVVMAFBHBUQPTSOXALTGVWWRG 1.11. Ta sÏ m« t¶ mét hÖ m· dßng lµ biÕn thÓ cña m· VigenÌre nh− sau. Víi mét tõ kho¸ ®é dµi m cho tr−íc ( k1,. . .,km ), ta t¹o dßng kho¸ theo quy t¾c zi=ki (1 ≤ i ≤ m), zi+m = zi+1 mod 26 ( i ≥ m+1). Nãi c¸ch kh¸c, mçi lÇn dïng tõ kho¸ ta sÏ thay mçi kÝ tù b»ng kÝ tù ®øng sau nã theo modulo 26. VÝ dô, nÕu SUMMER lµ tõ kho¸ th× ta dïng SUMMER ®Ó m· ho¸ 6 kÝ tù ®Çu.,sau ®ã dïng TVNNFS ®Ó m· ho¸ 6 kÝ tù tiÕp theo vµ có tiÕp tôc nh− vËy. H·y m« t¶ c¸ch cã thÓ dïng kh¸i niÖm chØ sè trïng hîp nh− thÕ nµo ®Ó tr−íc hÕt lµ x¸c ®Þnh ®é dµi tõ kho¸ vµ sau ®ã lµ t×m tõ kho¸. H·y kiÓm tra ph−¬ng ph¸p cña b¹n b»ng c¸ch b»ng c¸ch ph©n tÝch b¶n m· sau: IYMYSILONRFNCQXQJEDSHBUIBCJUZBOLFQYSCHATPEQGQ JEJNGNXZWHHG¦FSUKULJQACZKKJOAAHGKEMTAFGMKVRDO PXNEHEKZNKFSKIFRQVHHOVXINPHMRTJPYWQGJWPUUKFP OAWPMRKKQZWLQDYAZDRMLPBJKJOBWIWPSEPVVQMBCRYVC RUZAAOUMBCHDAGDIEMSZFZHALIGKEMJJFPCIWKRMLMPIN AYOFIREAOLDTHITDVRMSE B¶n râ ®−îc lÊy tõ "The codebreakers" cña D.Kahn, 1967. Trang 45
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2