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 3

Điều cần thiết ở đây là có một thuật toán hữu hiệu để làm việc đó. Rất mayb là một số kết quả tiếp sau về số học modulo sẽ cung cấp một thuật toán giải mã hữu hiệu cần tìm. Định nghĩa 1.4 Giả sử a ∈ Zm .
Nội dung trích xuất từ tài liệu:
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 3Vietebooks Nguyễn Hoàng Cươngnµy cã mét nghiÖm duy nhÊt trong Z26 . Tuy nhiªn ta vÉn ch−a biÕt métph−¬ng ph¸p h÷u hiÖu ®Ó t×m nghiÖm. §iÒu cÇn thiÕt ë ®©y lµ cã mét thuËtto¸n h÷u hiÖu ®Ó lµm viÖc ®ã. RÊt mayb lµ mét sè kÕt qu¶ tiÕp sau vÒ sè häcmodulo sÏ cung cÊp mét thuËt to¸n gi¶i m· h÷u hiÖu cÇn t×m.§Þnh nghÜa 1.4 Gi¶ sö a ∈ Zm . PhÇn tö nghÞch ®¶o (theo phÐp nh©n) cña a lµ phÇn töa ∈ Zm sao cho aa-1 ≡ a-1a ≡ 1 (mod m). -1 B»ng c¸c lý luËn t−¬ng tù nh− trªn, cã thÓ chøng tá r»ng a cã nghÞch®¶o theo modulo m khi vµ chØ khi UCLN(a,m) =1, vµ nÕu nghÞch ®¶o nµy tånt¹i th× nã ph¶i lµ duy nhÊt. Ta còng thÊy r»ng, nÕu b = a-1 th× a = b-1 . NÕu p lµsè nguyªn tè th× mäi phÇn tö kh¸c kh«ng cña ZP ®Òu cã nghÞch ®¶o. Métvµnh trong ®ã mäi phÇn tö ®Òu cã nghÞch ®¶o ®−îc gäi lµ mét tr−êng. Trong phÇn sau sÏ m« t¶ mét thuËt to¸n h÷u hiÖu ®Ó tÝnh c¸c nghÞch®¶o cña Zm víi m tuú ý. Tuy nhiªn, trong Z26 , chØ b»ng ph−¬ng ph¸p thö vµsai còng cã thÓ t×m ®−îc c¸c nghÞch ®¶o cña c¸c phÇn tö nguyªn tè cïngnhau víi 26: 1-1 = 1, 3-1 = 9, 5-1 = 21, 7-1 = 15, 11-1 = 19, 17-1 =23, 25-1 = 25.(Cã thÓ dÔ dµng kiÓm chøng l¹i ®iÒu nµy, vÝ dô: 7 × 5 = 105 ≡ 1 mod 26, bëivËy 7-1 = 15). XÐt ph−¬ng tr×nh ®ång d− y ≡ ax+b (mod 26). Ph−¬ng tr×nh nµy t−¬ng®−¬ng víi ax ≡ y-b ( mod 26)V× UCLN(a,26) =1 nªn a cã nghÞch ®¶o theo modulo 26. Nh©n c¶ hai vÕ cña®ång d− thøc víi a-1 ta cã: a-1(ax) ≡ a-1(y-b) (mod 26) ¸p dông tÝnh kÕt hîp cña phÐp nh©n modulo: a-1(ax) ≡ (a-1a)x ≡ 1x ≡ x. KÕt qu¶ lµ x ≡ a-1(y-b) (mod 26). §©y lµ mét c«ng thøc t−êng minhcho x. Nh− vËy hµm gi¶i m· lµ: d(y) = a-1(y-b) mod 26 Trang 11Vietebooks Nguyễn Hoàng Cương H×nh 1.4 cho m« t¶ ®Çy ®ñ vÒ m· Affine. Sau ®©y lµ mét vÝ dô nháH×nh 1.4 MËt m∙A ffine Cho P = C = Z26 vµ gi¶ sö P = { (a,b) ∈ Z26 × Z26 : UCLN(a,26) =1 } Víi K = (a,b) ∈K , ta ®Þnh nghÜa: eK(x) = ax +b mod 26 vµ dK(y) = a-1(y-b) mod 26, x,y ∈ Z26VÝ dô 1.3 Gi¶ sö K = (7,3). Nh− ®· nªu ë trªn, 7-1 mod 26 = 15. Hµm m· ho¸ lµ eK(x) = 7x+3Vµ hµm gi¶i m· t−¬ng øng lµ: dK(x) = 15(y-3) = 15y -19 ë ®©y, tÊt c¶ c¸c phÐp to¸n ®Òu thùc hiÖn trªn Z26. Ta sÏ kiÓm tra liÖudK(eK(x)) = x víi mäi x ∈ Z26 kh«ng?. Dïng c¸c tÝnh to¸n trªn Z26 , ta cã dK(eK(x)) =dK(7x+3) =15(7x+3)-19 = x +45 -19 = x. §Ó minh ho¹, ta h·y m· ho¸ b¶n râ hot. Tr−íc tiªn biÕn ®æi c¸c ch÷h, o, t thµnh c¸c thÆng du theo modulo 26. Ta ®−îc c¸c sè t−¬ng øng lµ 7, 14vµ 19. B©y giê sÏ m· ho¸: 7 × 7 +3 mod 26 = 52 mod 26 = 0 7 × 14 + 3 mod 26 = 101 mod 26 =23 7 × 19 +3 mod 26 = 136 mod 26 = 6 Trang 12Vietebooks Nguyễn Hoàng Cương Bëi vËy 3 ký hiÖu cña b¶n m· lµ 0, 23 vµ 6 t−¬ng øng víi x©u ký tùAXG. ViÖc gi¶i m· sÏ do b¹n ®äc thùc hiÖn nh− mét bµi tËp.1.1.4 M∙ VigenÌre Trong c¶ hai hÖ MDV vµ MTT (mét khi kho¸ ®· ®−îc chän) mçi ký tùsÏ ®−îc ¸nh x¹ vµo mét ký tù duy nhÊt. V× lý do ®ã, c¸c hÖ mËt cßn ®−îc gäihÖ thay thÕ ®¬n biÓu. B©y giê ta sÏ tr×nh bµy ( trong hïnh 1.5) mét hÖ mËtkh«ng ph¶i lµ bé ch÷ ®¬n, ®ã lµ hÖ m· VigenÌre næi tiÕng. MËt m· nµy lÊytªn cña Blaise de VigenÌre sèng vµo thÕ kû XVI. Sö dông phÐp t−¬ng øng A ⇔ 0, B ⇔ 1, . . . , Z ⇔ 25 m« t¶ ë trªn, tacã thÓ g¾n cho mçi khoa K víi mét chuçi kÝ tù cã ®é dµi m ®−îc gäi lµ tõkho¸. MËt m· VigenÌre sÏ m· ho¸ ®ång thêi m kÝ tù: Mçi phÇn tö cña b¶n rât−¬ng ®−¬ng víi m ký tù. XÐt mét vÝ dô nháVÝ dô 1.4 Gi¶ sö m =6 vµ tõ kho¸ lµ CIPHER. Tõ kho¸ nµy t−¬ng øng víi d·y sèK = (2,8,15,4,17). Gi¶ sö b¶n râ lµ x©u: thiscryptosystemisnotsecureH×nh 1.5 MËt m∙ VigenÌreCho m lµ mét sè nguyªn d−¬ng cè ®Þnh nµo ®ã. §Þnh nghÜa P = C = K =(Z26)m . Víi kho¸ K = (k1, k2, . . . ,km) ta x¸c ®Þnh : eK(x1, x2, . . . ,xm) = (x1+k1, x2+k2, . . . , xm+km)vµ dK(y1, y2, . . . ,ym) = (y1-k1, y2-k2, . . . , ym-km)trong ®ã tÊt c¶ c¸c phÐp to¸n ®−îc thùc hiÖn trong Z26Ta sÏ biÕn ®æi c¸c phÇn tö cña b¶n râ thµnh c¸c thÆng d− theo modulo 26,viÕt chóng thµnh c¸c nhãm 6 råi céng víi tõ kho¸ theo modulo 26 nh− sau: Trang 13Vietebooks ...