Tài liệu Các hệ mật khoá công khai và các hàm băm

Bé gi¸o dôc vµ ®µo t¹o Tr-êng ®¹i häc b¸ch khoa Hµ néi Khoa C«ng nghÖ th«ng tin TrÇn ViÖt Dòng C¸c hÖ mËt khãa c«ng khai vµ c¸c hµm b¨m LuËn v¨n th¹c sÜ ngµnh: Xö lý th«ng tin vµ truyÒn th«ng Hµ Néi – 2004 Bé gi¸o dôc vµ ®µo t¹o Tr-êng ®¹i häc b¸ch khoa hµ néi Khoa c«ng nghÖ th«ng tin TrÇn ViÖt Dòng C¸c hÖ mËt khãa c«ng khai vµ c¸c hµm b¨m LuËn v¨n th¹c sÜ ngµnh: Xö lý th«ng tin vµ truyÒn th«ng Ng-êi h-íng dÉn khoa häc: GS.TSKH. Hå ThuÇn Hµ Néi – 2004 Môc lôc Trang I.1 - Nguyªn lý chung ................................................................................. 01 I.2 - C¸c yªu cÇu chung ®èi víi hÖ mËt ....................................................... 04 I.3 - Ph©n lo¹i hÖ mËt .................................................................................. 04 1.3.1 – Lo¹i phÐp to¸n dïng ®Ó chuyÓn b¶n râ thµnh b¶n m·: ......... 04 1.3.2 – Sè khãa sö dông .................................................................... 04 1.3.3 – C¸ch thøc xö lý b¶n râ .......................................................... 05 I.4. HÖ mËt cæ ®iÓn dùa trªn kü thuËt thay thÕ (Substitution) ..................... 05 I.4.1 – MËt m· dÞch vßng (m· Caesar). ............................................ 05 I.4.3 – MËt m· b¶ng ch÷ c¸i ®¬n (Monoalphabetic Ciphers)........... 07 I.4.4 – M· Playfair (Playfair Cipher) ............................................... 07 I.4.5 - M· Hill (Hill Cipher) ............................................................... 08 I.4.6 – MËt m· trËt tù ®a ch÷ c¸i (Polyalphabetic Ciphers) ............. 10 I.5. HÖ mËt cæ ®iÓn dùa trªn kü thuËt chuyÓn dÞch (Transposition) ........... 12 I.5.2 - M· Affine ................................................................................. 14 I.5.3 - HÖ m· tÝch ................................................................................ 16 I.5.4 - HÖ m· dßng .............................................................................. 17 I.6. Kü thuËt mËt m· hiÖn ®¹i ...................................................................... 20 I.6.1 - ThuËt to¸n m· hãa DES ............................................................ 20 I.6.2 - C¸c chÕ ®é ho¹t ®éng cña DES ................................................ 23 Ch-¬ng Hai C¬ së to¸n häc cña ®Ò tµi II.1 – Kh¸i niÖm vÒ ®ång d-: .................................................................... 27 II.2 – Nguyªn lý cña sè häc Modulo: ....................................................... 28 II.3 - Sè nguyªn tè vµ c¸c sè nguyªn tè cïng nhau: ................................... 29 II.3.1- §Þnh nghÜa sè nguyªn tè: ........................................................ 29 II.3.2 - ¦íc sè chung lín nhÊt (Greatest Common Divior): .............. 31 II.4 . §Þnh lý Fermat vµ ®Þnh lý Euler: ....................................................... 32 II.4.1 - Hµm Euler: .............................................................................. 32 II.4.2 - §Þnh lý Fermat:....................................................................... 32 II.4.3 - §Þnh lý Euler: ......................................................................... 33 II.4.5 - §Þnh lý sè d- Trung Hoa: ....................................................... 36 II.4.6 – Tr-êng Galoa vµ tÝnh to¸n trong tr-êng Galoa .................... 38 i II.4.7 – Lý thuyÕt vÒ ®é phøc t¹p ...................................................... 43 II.4.7.1 - §é phøc t¹p cña thuËt to¸n .......................................... 44 II.4.7.2 - §é phøc t¹p vµ líp NP - §Çy ®ñ .................................. 46 II.4.7.3 – MËt m· dùa trªn c¸c bµi to¸n khã tÝnh to¸n: ............ 48 II.5 – Mét sè thuËt to¸n ph©n tÝch sè ........................................................ 49 II.5.1 – ThuËt to¸n ph©n tÝch ra thõa sè nguyªn tè ........................... 49 II.5.2 – ThuËt to¸n kiÓm tra sè nguyªn tè......................................... 51 II.5.2 – Mét sè thuËt to¸n ph©n tÝch bµi to¸n Logarit rêi r¹c............ 54 Ch-¬ng Ba C¸c hÖ mËt khãa c«ng khai III..1 – Nguyªn lý chung cña hÖ mËt khãa c«ng khai: ............................ 61 III.1.1 – TÝnh bÝ mËt (Secrecy) cña hÖ mËt khãa c«ng khai: ........... 62 III.1.2 – TÝnh ®Ých thùc trong hÖ mËt khãa c«ng khai: .................... 63 III.3.3 – TÝnh mËt vµ tÝnh ®Ých thùc hÖ mËt khãa c«ng khai: .......... 63 III.2 – C¸c øng dông cña hÖ mËt khãa c«ng khai: ................................... 65 III.3 – C¸c yªu cÇu ®èi víi hÖ mËt khãa c«ng khai: ................................ 67 III.4 – So s¸nh gi÷a hÖ mËt ®èi xøng vµ hÖ mËt khãa c«ng khai: ............ 68 III.5 - Mét sè hÖ mËt khãa c«ng khai: ....................................................... 69 III.5.1 - HÖ mËt ba l« (Knapsack System): ........................................ 69 III.5.2 – HÖ mËt McELICE: ............................................................. 74 III.5.3 - HÖ mËt RaBin: ...................................................................... 78 III.5.4 - HÖ mËt ELGAMAL: ............................................................ 80 III.5.5 - HÖ RSA: ............................................................................... 82 III.5.6 - HÖ mËt Schnorr: ................................................................... 86 III.5.7 - HÖ mËt ®-êng cong Elipptic (ECC): .................................... 86 III.5.8 - Mét biÕn thÓ cña hÖ mËt RSA: ............................................. 86 Ch-¬ng Bèn: C¸c hµm b¨m IV.1 – Tæng quan vÒ hµm b¨m: ................................................................ 97 IV.2 - §Þnh nghÜa hµm b¨m: ...................................................................... 97 IV.3 – TÝnh chÊt: ...................................................................................... 98 IV.4 – Ph©n lo¹i hµm b¨m: ....................................................................... 98 ii IV.4.1 – C¸c hµm b¨m kh«ng cã khãa: ............................................. 99 IV.4.2 – C¸c hµm b¨m cã khãa (Keyed hash functions): ............... 101 IV.5 – øng dông hµm b¨m mËt m· MAC: ............................................. 102 IV.6 – §é an toµn (security) cña hµm b¨m vµ MAC: ............................. 103 IV.7 – Mét sè lo¹i hµm b¨m: ................................................................. 106 IV.7.1 – Hµm b¨m MD2: ............................................................... 106 IV.7.2 – Hµm b¨m MD4: ............................................................... 108 IV.7.3 – Hµm b¨m MD5: ............................................................... 110 IV.7.4 - ThuËt to¸n b¨m b¶o mËt SHA (Secure Hash Algorithm): .. 115 IV.7.5 - RIPEMD – 160: ................................................................ 122 IV.8 – øng dông kü thuËt mËt m· ,,, ...................................................... 126 KÕt luËn: ............................................................................................ 128 Tµi liÖu tham kh¶o: .......................................................................... 131 Phô lôc: Ch-¬ng tr×nh m· ho¸ File: ................................................. 132 iii Danh môc h×nh vÏ Trang H×nh 1.1: Nguyªn lý chung cña mËt m· kho¸ bÝ mËt .................................... 2 H×nh 1.2: Luång th«ng tin trªn ®-êng truyÒn ................................................ 3 H×nh 1.4: B¶ng VigenÌre ............................................................................. 11 H×nh 1.3: Thanh ghi dÞch håi tiÕp tuyÕn tÝnh .............................................. 19 H×nh 1.4: S¬ ®å tæng qu¸t cho gi¶i thuËt DES ............................................ 20 H×nh 1.5: Hµm f(A, B) ................................................................................. 21 H×nh 1.6: S¬ ®å m· hãa ®iÖn tö (ECB) ........................................................ 23 H×nh 1.7: M· hãa theo d·y khèi .................................................................. 24 H×nh 1.7: S¬ ®å m· hãa th«ng tin ra ph¶n håi (CFB) ................................. 25 H×nh 2.1 : Minh häa nguyªn lý cña sè häc modulo..................................... 29 H×nh 2.2: C¸c líp phøc t¹p ......................................................................... 46 H×nh 2.3: Sinh sè gi¶ ngÉu nhiªn ................................................................ 53 Hinh 3.1: TÝnh mËt trong hÖ mËt khãa c«ng khai........................................ 63 Hinh 3.2: TÝnh ®Ých thùc cña hÖ mËt khãa c«ng khai ................................. 63 H×nh 3.3: TÝnh mËt vµ tÝnh x¸c thùc trong hÖ mËt khãa c«ng khai ............. 64 H×nh 3.4 : §-êng cong Elliptic ................................................................... 88 H×nh 4.1: Ph©n lo¹i hµm b¨m ..................................................................... 98 H×nh 4.2: TÝnh toµn vÑn cña d÷ liÖu .......................................................... 100 H×nh 4.3: C¸c thuËt to¸n b¨m MDC ......................................................... 101 H×nh 4.4: ThuËt to¸n MAC dïng CBC ...................................................... 102 H×nh 4.5: TÝnh toµn vÑn cña d÷ liÖu khi sö dông MAC ............................. 103 H×nh 4.6: M« t¶ qu¸ tr×nh xö lý b¶n tin ®Ó t¹o ra m· tãm l-îc b¶n tin.... 111 H×nh 4.7: MD5 xö lý khèi ®¬n 512 bÝt (chøc n¨ng nÐn MD5) .................. 113 H×nh 4.8: PhÇn c¬ b¶n cña thuËt to¸n [ABCD k s i] ................................ 114 H×nh 4.9: Xö lý b¶n tin t¹o ra chuçi 160 bÝt cña thuËt to¸n SHA-1 ......... 116 H×nh 4.10: SHA-1 xö lý mét khèi ®¬n 512 bÝt ........................................... 118 H×nh 4.11: PhÐp to¸n c¬ b¶n SHA (thùc hiÖn trªn mçi b-íc)................... 119 H×nh 4.12: Qu¸ tr×nh xö lý mét khèi ®¬n 512 bit ...................................... 123 H×nh 4.13: øng dông kü thuËt mËt m· song song ..................................... 127 iv Lêi giíi thiÖu MËt m· ®· ®-îc sö dông trong ®êi sèng tõ nh÷ng thêi kú xa x-a. X-a kia ng-êi ta th-êng hiÓu mËt m· chØ dïng cho qu©n ®éi, cho c¸c bé m¸y nhµ n-íc... Nh-ng ngµy nay, víi sù ph¸t triÓn cña m¹ng m¸y tÝnh ®Æc biÖt lµ m¹ng Internet mang l¹i nhiÒu lîi Ých to lín. Bªn c¹nh nh÷ng mÆt thuËn lîi, tÝch cùc th× ®©y còng lµ m«i tr­êng ®Ó nh÷ng kÎ “trém tin” th¶ søc khai th¸c, nhÊt lµ nh÷ng th«ng tin cã gi¸ trÞ trªn nh÷ng lÜnh vùc An ninh quèc phßng, Th­¬ng m¹i vµ Ngo¹i giao. “Trém tin” vµ “Chèng trém tin” lµ hai hai trËn tuyÕn ®èi nghÞch nhau. Cã nhiÒu biÖn ph¸p ®Ó b¶o vÖ th«ng tin vµ mét trong nh÷ng ph-¬ng ph¸p quan träng nhÊt lµ mËt m·. Cã thÓ nãi sù trao ®æi th«ng tin vµ an toµn th«ng tin ®· trë thµnh mét nhu cÇu g¾n liªn nh- h×nh víi bãng, vµ c«ng cô ®Ó trao ®æi th«ng tin ph¸t triÓn tõ “th« s¬” ®Õn “hiÖn ®¹i” th× mËt m· còng theo ®ã ph¸t triÓn cho phï hîp. T¸c gi¶ c«ng t¸c trong lÜnh vùc b¶o mËt th«ng tin, nªn nh÷ng kiÕn thøc vÒ mËt m· häc cÇn ®-îc nghiªn cøu mét c¸ch cã hÖ thèng. ChÝnh v× lý do ®ã mµ t¸c gi¶ chän ®Ò tµi “C¸c hÖ mËt khãa c«ng khai vµ c¸c hµm b¨m” ®Ó cñng cè vµ n©ng cao kiÕn thøc phôc vô c«ng t¸c ®-îc tèt h¬n. Trong luËn v¨n nµy, t¸c gi¶ nghiªn cøu sù ph¸t triÓn cña c¸c hÖ mËt, mËt m· khãa bÝ mËt, mËt m· khãa c«ng khai vµ c¸c hµm b¨m nh»m vµo ba môc ®Ých ®ã lµ b¶o ®¶m tÝnh bÝ mËt, tÝnh x¸c thùc vµ tÝnh toµn vÑn trong b¶o vÖ th«ng tin ®-îc truyÒn hoÆc cho l-u tr÷. Lu©n v¨n bao gåm bèn ch-¬ng vµ mét phô lôc: Ch-¬ng 1: Tæng quan vÒ lý thuyÕt mËt m· Ch-¬ng 2: C¬ së to¸n häc cña ®Ò tµi Ch-¬ng 3: C¸c hÖ mËt khãa c«ng khai Ch-¬ng 4: C¸c hµm b¨m Phô lôc: Ch-¬ng tr×nh m· ho¸ File kÕt hîp víi gi¶i thuËt nÐn/gi¶i nÐn tù ®éng (khi chän File ®Ó m·/gi¶i m·) øng dông trong truyÒn tin ®iÓm v ®iÓm. PhÇn phô lôc, t¸c gi¶ cã tr×nh bµy mét øng dông mËt m· (hÖ mËt m· mét kho¸) kÕt hîp víi gi¶i thuËt nÐn tù ®éng nh»m gi¶m ®é d- ng«n ng÷, tiÕt kiÖm chi phÝ truyÒn th«ng øng dông trong truyÒn tin b¶o mËt, s¸t víi chuyªn m«n mµ t¸c gi¶ ®ang c«ng t¸c. T¸c gi¶ xin bµy tá lßng biÕt ¬n c¸c ThÇy gi¸o, C« gi¸o khoa C«ng nghÖ Th«ng tin tr-êng §¹i häc B¸ch khoa Hµ Néi, Trung t©m ®µo t¹o vµ Båi d-ìng sau ®¹i häc, c¸c ThÇy gi¸o, C« gi¸o lµ céng t¸c viªn víi Trung t©m ®µo t¹o vµ Båi d-ìng sau ®¹i häc, C¸n bé qu¶n lý häc viªn cña Trung t©m, TËp thÓ líp Xö lý th«ng tin vµ TruyÒn th«ng còng nh- C¬ quan ®· t¹o ®iÒu kiÖn thuËn lîi trong suèt hai n¨m nghiªn cøu vµ häc tËp t¹i tr-êng. §Æc biÖt, t¸c gi¶ xin bµy tá lßng biÕt ¬n s©u s¾c tíi thÇy gi¸o GS.TSKH. Hå ThuÇn ®· d¹y vµ h-íng dÉn, chØ b¶o tËn t×nh trong suèt thêi gian häc tËp, còng nh- lµm luËn v¨n vµ sù ®éng viªn vµ cæ vò cña c¶ Gia ®×nh. Th¸ng 9 n¨m 2004 vi Ch−¬ng Mét HÖ mËt mét khãa Ch−¬ng Mét Tæng quan vÒ lý thuyÕt mËt m· Trong sù ph¸t triÓn cña x· héi loμi ng−êi, sù trao ®æi th«ng tin vμ an toμn th«ng tin ®· trë thμnh mét nhu cÇu g¾n bã víi nhau nh− h×nh víi bãng. Tõ thña s¬ khai, an toμn th«ng tin ®−îc hiÓu ®¬n gi¶n lμ gi÷ ®−îc bÝ mËt vμ ®iÒu nμy ®−îc xem nh− lμ mét nghÖ thuËt chø ch−a ph¶i lμ mét ngμnh khoa häc. Víi sù ph¸t triÓn cña khoa häc vμ c«ng nghÖ ®Æc biÖt lμ c¸c øng dông cña to¸n häc vμo mËt m·, cïng víi sù ph¸t triÓn m¹ng m¸y tÝnh th× nhu cÇu trao ®æi th«ng tin cña con ng−êi cμng t¨ng, nhu cÇu b¶o mËt th«ng tin ngμy cμng ®−îc c¶i thiÖn vμ n©ng cao, khoa häc mËt m· ngμy cμng ®−îc ph¸t triÓn, cã liªn quan mËt thiÕt víi nhiÒu nhμnh ngμnh to¸n häc nh−: §¹i sè tuyÕn tÝnh, Lý thuyÕt th«ng tin, Lý thuyÕt ®é phøc t¹p tÝnh to¸n v.v... Kü thuËt mËt m· nh»m ®¶m b¶o ba dÞch vô an toμn c¬ b¶n sau:  BÝ mËt (Confidential, Secrecy)  X¸c thùc (Authentication) cña d÷ liÖu (Data);  §¶m b¶o tÝnh toμn vÑn (Intergrity) cña th«ng tin. Trong ch−¬ng mét, chóng t«i sÏ tr×nh bμy c¸c kh¸i niÖm c¬ b¶n cña lý thuyÕt mËt m· vμ kh¶o s¸t mét sè hÖ mËt cæ ®iÓn trªn quan ®iÓm kÕ thõa vμ ph¸t triÓn. Khai th¸c c¸c −u viÖt cña c¸c hÖ mËt cæ ®iÓn, kÕt hîp víi c¸c hÖ mËt hiÖn ®¹i (hÖ mËt khãa c«ng khai) trong c¸c øng dông b¶o mËt th«ng tin trªn truyÒn th«ng m¹ng m¸y tÝnh vμ an ninh m¹ng. I – C¸c kh¸i niÖm c¬ b¶n cña lý thuyÕt mËt m· Lý thuyÕt mËt m· lμ khoa häc nghiªn cøu vÒ c¸ch viÕt bÝ mËt ®Ó ®¶m b¶o sù riªng t− vμ x¸c thùc cña d÷ liÖu phôc vô cho l−u tr÷ b¶o mËt hoÆc sö dông trong c¸c hÖ truyÒn th«ng. Víi l−îng th«ng tin cμng nhiÒu vμ truyÒn cμng xa th× kh¶ n¨ng “rß rØ” th«ng tin cμng lín, nh−ng khi th«ng tin ®· ®−îc m· hãa th× x¸c xuÊt bÞ mÊt bÝ mËt th«ng tin hÇu nh− ®−îc ng¨n chÆn. I.1 - Nguyªn lý chung XuÊt ph¸t tõ b¶n tin ban ®Çu ch−a ®−îc b¶o vÖ (Unprotected Message) cßn ®−îc gäi lμ b¶n râ (Plaintext, Original data), qua c«ng ®o¹n biÕn ®æi 1 Ch−¬ng Mét HÖ mËt mét khãa thμnh mét d¹ng khã hiÓu ®−îc gäi lμ b¶n m· (Ciphertext, Cryptogram, Scrambled data). Qu¸ tr×nh ®ã gäi lμ m· hãa (Encryption, Encipherment). ThuËt to¸n gi¶i m· (Decryption) lμ biÕn ®æi b¶n m· vÒ b¶n râ. H×nh 1.1: Nguyªn lý chung cña mËt m· kho¸ bÝ mËt HÖ thèng dÔ dμng m· hãa ®Ó biÕn ®æi b¶n râ thμnh b¶n m· vμ ng−îc l¹i ®−îc gäi lμ hÖ thèng mËt m· hay hÖ mËt. Trong c¸c hÖ mËt, tËp c¸c tham sè ®Ó chän sù m· hãa riªng ®−îc gäi lμ khãa (Key set). C¶ hai qu¸ tr×nh m· hãa vμ gi¶i m· ®Òu ®−îc ®iÒu khiÓn bëi khãa. Tuú theo hÖ mËt, khãa dïng ®Ó m· hãa b¶n tin vμ còng ®Ó dïng ®Ó gi¶i m· b¶n tin gäi lμ hÖ mËt khãa ®èi xøng (Symmetric cryptosystem) hay hÖ mËt mét khãa, trong ®ã c¸c khãa m· hãa vμ gi¶i m· lμ ®ång nhÊt vÒ nguyªn t¾c theo nghÜa biÕt khãa nμy cã thÓ suy ra khãa khia. Trong hÖ mËt nμy c¸c khãa ®ã ph¶i gi÷ bÝ mËt tuyÖt ®èi, v× lý do ®ã, hÖ mËt ®èi xøng cßn ®−îc gäi lμ hÖ mËt khãa bÝ mËt. Trong hÖ mËt hai khãa hay hÖ mËt khãa c«ng khai (Public-key Cryptosystem) hai khãa kh¸c nhau ®−îc sö dông. Mét khãa dïng khi m· hãa, khãa cßn l¹i dïng ®Ó gi¶i m· (vμ ph¶i gi÷ bÝ mËt khãa nμy). Sù trém tin (Eavesdropping) lμ sù th©m nhËp chÆn lÊy d÷ liÖu th«ng tin ®−îc thùc hiÖn bëi mét c¸ nh©n hoÆc mét tæ chøc kh«ng hîp ph¸p trong kªnh liªn l¹c. NÕu ®èi ph−¬ng chØ nghe hoÆc ghi th«ng tin truyÒn ®i th× ®−îc gäi lμ tÊn c«ng bÞ ®éng (Passive attack). Cßn nÕu ®èi ph−¬ng biÕn ®æi c¸c th«ng tin ®−îc truyÒn trªn kªnh liªn l¹c hoÆc chÌn c¸c th«ng tin sai l¹c vμo kªnh truyÒn th× ®−îc gäi lμ tÊn c«ng tÝch cùc (Active). BÊt kú sù cè g¾ng cña ®èi ph−¬ng ®Ó gi¶i m· b¶n m· kh«ng cÇn hiÓu biÕt vÒ khãa ®−îc gäi lμ th¸m m· (Cryptanalysis). Th¸m m· lμ mét ngμnh khoa häc ph¸ b¶n m·, cßn mËt – th¸m m· (Cryptology) lμ khoa häc cña mËt m· vμ th¸m m·: Cryptology = Cryptography + Cryptanalysis C¸c phÐp to¸n m· hãa vμ gi¶i m· ®−îc biÓu diÔn tæng qu¸t: 2 Ch−¬ng Mét HÖ mËt mét khãa Y = EKe(X) M· hãa X = DKd(Y) Gi¶i m· Trong ®ã: X lμ th«ng tin b¶n râ, Y lμ b¶n m·, Ke lμ khãa m· hãa, Kd lμ khãa gi¶i m·. Ph©n tÝch mËt m· B¶n râ X Gi¶i thuËt m· hãa X K Gi¶i thuËt gi¶i m· Y X B¶n râ K Nguån khãa Kªnh an toμn H×nh 1.2 – Luång th«ng tin trªn ®−êng truyÒn Mét hÖ thèng mËt th−êng cã 5 thμnh phÇn c¬ b¶n sau:  Mét kh«ng gian c¸c b¶n râ (th«ng b¸o) M  Mét kh«ng gian c¸c m· C  Mét kh«ng gian khãa K  Mét hä c¸c biÕn ®æi m· hãa (Encipering Transformation) EK  Mét hä c¸c phÐp biÕn ®æi gi¶i m· (Deciphering) DK PhÐp biÕn ®æi m· hãa EK ®−îc x¸c ®Þnh bëi thuËt to¸n lËp m· (m· hãa) E chung vμ mét khãa K ®Ó ph©n biÖt víi c¸c phÐp biÕn ®æi m· hãa kh¸c: EK  EK’. PhÐp biÕn ®æi gi¶i m· DK ®−îc x¸c ®Þnh bëi thuËt to¸n gi¶i m· D vμ mét kho¸ K. Th−êng yªu cÇu phÐp biÕn ®æi DK lμ phÐp biÕn ®æi ng−îc cña EK nghÜa lμ: DK(EK(M)) = M víi M  M (1.1) Trong mét hÖ mËt, c¸c phÐp biÕn ®æi EK vμ DK ®−îc m« t¶ bëi c¸c tham sè ®−îc dÉn xuÊt tõ K (hay trùc tiÕp tõ K). TËp c¸c tham sè ®iÒu khiÓn qu¸ tr×nh lËp m· EK ®−îc gäi lμ khãa lËp m·, tËp c¸c tham sè ®iÒu khiÓn qu¸ tr×nh gi¶i m· DK ®−îc gäi lμ khãa gi¶i m·. 3 Ch−¬ng Mét HÖ mËt mét khãa I.2 - C¸c yªu cÇu chung ®èi víi hÖ mËt Trong c¸c hÖ mËt cÇn ph¶i tho¶ m·n 3 yªu cÇu sau:  C¸c phÐp EK vμ DK ph¶i hiÖu qu¶ víi khãa (tÝnh to¸n nhanh)  HÖ dÔ sö dông  B¶o ®¶m tÝnh an toμn, nã th−êng phô thuéc vμo tÝnh mËt cña khãa chø kh«ng phï thuéc vμo tÝnh mËt cña thuËt to¸n m· hãa vμ gi¶i m·. Ngoμi ra cßn cã c¸c yªu cÇu phô lμ ®¶m b¶o tÝnh mËt (Secrecy) vμ tÝnh x¸c thùc (Authenticity).  TÝnh mËt: Ng−êi göi th«ng b¸o M cho ng−êi nhËn d−íi d¹ng b¶n m· C, chØ ng−êi nhËn hîp ph¸p míi gi¶i m· C ®Ó thu ®−îc b¶n râ M. KÎ trém tin kh«ng cã kh¶ n¨ng kh«i phôc ®−îc M.  TÝnh x¸c thùc: Ng−êi trém tin chÆn ®−îc C kh«ng cã kh¶ n¨ng thay ®æi C thμnh C’ mμ kh«ng bÞ ph¸t hiÖn. Víi hÖ mËt cæ ®iÓn,, DK hoÆc trïng hoÆc ®−îc suy tõ EK. Bëi vËy ®Ó b¶o ®¶m ®−îc tÝnh mËt vμ tÝnh x¸c thùc cña hÖ m· cÇn ph¶i gi÷ bÝ mËt c¶ EK vμ DK. I.3 - Ph©n lo¹i hÖ mËt HÖ thèng mËt m· cã thÓ ®−îc ph©n lo¹i tæng qu¸t dùa trªn ba h−íng: 1.3.1 Lo¹i phÐp to¸n dïng ®Ó chuyÓn b¶n râ thμnh b¶n m·: TÉt c¶ c¸c thuËt to¸n m· hãa ®−îc dùa trªn hai nguyªn lý sau:  HÖ mËt thay thÕ (Substitution), trong ®ã mçi mét phÇn tö trong b¶n râ (bit, ch÷ c¸i v.v..) ®−îc ¸nh x¹ mét mét vμo phÇn tö kh¸c.  HÖ mËt chuyÓn dÞch (Transposition), trong ®ã c¸c phÇn tö cña b¶n râ ®−îc s¾p ®Æt l¹i.  Lo¹i kÕt hîp 1.3.2 Sè khãa sö dông.  NÕu c¶ hai bªn göi vμ bªn nhËn dïng cïng khãa, hÖ ®ã ®−îc gäi lμ ®èi xøng, khãa ®¬n, khãa bÝ mËt hay m· hãa quy −íc (Conventional Encryption).  NÕu bªn nhËn vμ bªn göi dïng khãa kh¸c nhau, hÖ ®−îc gäi lμ kh«ng ®èi xøng, hai khãa hay hÖ mËt khãa c«ng khai. 4 Ch−¬ng Mét 1.3.3 HÖ mËt mét khãa C¸ch thøc xö lý b¶n râ.  M· khèi (Block Cipher): Xö lý mét khèi ®Çu vμo c¸c phÇn tö t¹i mét thêi ®iÓm vμ t¹o ra mét khèi ®Çu ra cho mçi khèi ®Çu vμo.  M· dßng (Stream Cipher): Xö lý c¸c phÇn tö ®Çu vμo mét c¸ch liªn tôc, t¹o ra mét phÇn tö ®Çu ra t¹i mét thêi ®iÓm vμ cø thÕ tiÕp tôc. I.4. HÖ mËt cæ ®iÓn dùa trªn kü thuËt thay thÕ (Substitution) I.4.1 MËt m· dÞch vßng (m· Caesar). Cã thÓ nãi, mËt m· ®· cã tõ thêi cæ ®¹i. Ng−êi ta cho r»ng, ng−êi ®Çu tiªn ¸p dông mËt m· mét c¸ch cã hÖ thèng ®Ó ®¶m b¶o bÝ mËt th«ng tin qu©n sù lμ nhμ qu©n sù thiªn tμi cña La M· cæ ®¹i, Julius Caesar. Sù ph¸t triÓn cña x· héi dÉn ®Õn viÖc ngμy nay mËt m· kh«ng nh÷ng chØ ®−îc dïng trong bÝ mËt qu©n sù vμ ngo¹i giao mμ cã thÓ chñ yÕu lμ dïng trong bÝ mËt kinh tÕ, th−¬ng m¹i. Kh¸c víi ho¹t ®éng qu©n sù, ngo¹i giao, trong ho¹t ®éng kinh tÕ, sè l−îng ®¬n vÞ ph¶i cïng trao ®æi th«ng tin th−êng lμ rÊt lín. ThËm chÝ, nh÷ng ng−êi ch−a hÒ quen biÕt nhau còng cã nhu cÇu trao ®æi nh÷ng th«ng tin mËt víi nhau. Bëi vËy, nh÷ng hÖ thèng mËt m· x©y dùng theo nguyªn t¾c cò khã cã thÓ thÝch hîp; trong c¸c hÖ mËt ®ã, khi ®· biÕt khãa lËp m·, ta dÔ dμng t×m ra khãa gi¶i m·. HiÓn nhiªn lμ muèn göi mét th«ng b¸o mËt cho mét ®èi t−îng nμo ®ã, ta cÇn ph¶i biÕt khãa lËp m· cña hä, v× thÕ nh÷ng ng−êi cïng dïng mét hÖ m· ®Òu biÕt hÕt bÝ mËt cña nhau. Khi mét bÝ mËt cã qu¸ nhiÒu ng−êi biÕt th× kh«ng cßn lμ bÝ mËt n÷a. C¸c hÖ thèng mËt m· hiÖn ®¹i, mËt m· khãa c«ng khai kh¾c phôc ®−îc nh÷ng nh−îc ®iÓm ®ã: mçi ng−êi tham gia trong hÖ thèng chØ cÇn gi÷ bÝ mËt khãa gi¶i m· cña m×nh, trong khi khãa lËp m· ®−îc th«ng b¸o c«ng khai. ViÖc biÕt khãa lËp m· kh«ng cho phÐp t×m ra khãa gi¶i m· trong mét thêi gian chÊp nhËn ®−îc, ngay c¶ khi sö dông nh÷ng m¸y tÝnh hiÖn ®¹i nhÊt ghÐp nèi vμ chia sÎ c«ng viÖc tÝnh to¸n víi nhau. Nh÷ng mËt m· khãa c«ng khai t×m thÊy ®Çu tiªn lμ nh÷ng mËt m· dïng hμm sè häc. Mét sè kh¸i niÖm:  V¨n b¶n: tøc lμ th«ng b¸o cÇn chuyÓn, ®−îc viÕt b»ng ng«n ng÷ th«ng th−êng.  M· hãa: viÖc chuyÓn v¨n b¶n ®ã thμnh d¹ng khã hiÓu theo mét luËt nμo ®ã gäi lμ m· hãa. 5 Ch−¬ng Mét HÖ mËt mét khãa  V¨n b¶n mËt: b¶n ®· ®−îc m· hãa cña v¨n b¶n.  Gi¶i m·: chuyÓn mét v¨n b¶n mËt thμnh v¨n b¶n ban ®Çu. Caesar chuyÓn th«ng b¸o mËt b»ng c¸ch sau ®©y. Tr−íc tiªn, lËp t−¬ng øng mçi ch÷ c¸i víi mét sè. Nhê b¶ng t−¬ng øng ®ã, ta cã thÓ chuyÓn v¨n b¶n thμnh d¹ng ch÷ sè. Sau ®ã céng thªm 3 vμo mçi ch÷ sè nhËn ®−îc. VÝ dô lËp b¶ng chuyÓn ®æi ch÷ c¸i sang d¹ng ch÷ sè (lËp m· tiÕng Anh víi 26 ch÷ c¸i, ®Ó minh ho¹ ta xö dông tiÕng ViÖt): a ¨ © Ë · b c d ® e 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 m n o « ¬ p q r s t ª Õ u − h v i x j y k l ý 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 M· Caesar ®−îc thμnh lËp theo c«ng thøc sau: C  P + 3 mod 33 (1.2) Trong ®ã P lμ ch÷ sè trong v¨n b¶n, C lμ ch÷ sè t−¬ng øng trong v¨n v¨n b¶n mËt. Ch¼ng h¹n ta muèn m· hãa th«ng b¸o sau: Lý thuyÕt mËt m· Tr−íc hÕt nh»m n©ng cao tÝnh mËt, ta t¸ch th«ng b¸o thμnh tõng nhãm 5 ch÷ c¸i, ®Ó tr¸nh viÖc mét sè tõ cña th«ng b¸o dÔ bÞ ph¸t hiÖn c¨n cø vμo sè ch÷ c¸i. Nh− vËy th«ng b¸o cÇn m· hãa lμ: Lýthu yÕtmË tm·xx nhê b¶ng trªn, ta chuyÓn th«ng b¸o thμnh d¹ng ch÷ sè 17 33 27 13 28 32 12 27 18 4 27 18 5 31 31 ¸p dông c«ng thøc (1.2) b¶ng ch÷ sè trªn ®−îc chuyÓn thμnh: 20 30 30 16 31 29 15 30 21 7 31 21 8 32 32 §Ó cã v¨n b¶n mËt ta cÇn chuyÓn l¹i thμnh d¹ng ch÷ c¸i dùa vμo b¶ng: ovvkx −xv«c x«dyy Sè 3 trong c«ng thøc trªn ®−îc gäi lμ khãa cña m· Caesar, v× nã ®−îc dïng ®Ó m· hãa còng nh− gi¶i m·. Ta còng cã thÓ lËp mét hÖ mËt m· míi b»ng c¸ch thay sè 3 trong c«ng thøc trªn b»ng mét sè k tuú ý trong kho¶ng 1 < k < 33. 6 Ch−¬ng Mét HÖ mËt mét khãa Trong tr−êng hîp tæng qu¸t ta thay c«ng thøc b»ng c«ng thøc sau: C  aP + b mod 26 (1.3) Trong ®ã a, b lμ c¸c sè nguyªn vμ −íc chung lín nhÊt gcd(a, 26) = 1. Nh÷ng m· nh− vËy ®−îc gäi lμ m· biÕn ®æi aphin. NhËn xÐt: lo¹i h×nh m· Caesar (hay m· chuyÓn dÞch) lμ kh«ng an toμn, nã cã thÓ bÞ th¸m m· theo ph−¬ng ph¸p t×m khãa vÐt c¹n. Víi 26 ch÷ c¸i (trong b¶ng m· tiÕng Anh), trung b×nh cã thÓ t×m ®−îc b¶n râ ®óng sau khi thö kho¶ng 26/2 = 13 quy t¾c gi¶i m·. I.4.3 MËt m· b¶ng ch÷ c¸i ®¬n (Monoalphabetic Ciphers) §Ó t¨ng kh«ng gian khãa (m· Caesar cã kh«ng gian khãa K lμ 25). Ng−êi ta ho¸n vÞ b¶ng ch÷ c¸i (x©y dùng b¶n râ) thμnh b¶n m· t−¬ng øng. VÝ dô: B¶n râ: abcdefghijklmnopqrstuvwxyz B¶n m·: DEFGH IJKLMNOPQRSTUVWXYZABC M· b¶ng ch÷ c¸i ®¬n lμ m· thay thÕ ký tù trong b¶n râ bëi mét ký tù kh¸c trong b¶n m·. Nh− vËy, ¸nh x¹ mét ®èi mét ®¬n gi¶n tõ b¶n râ tíi c¸c ký tù b¶n m· ®−îc dïng ®Ó m· hãa toμn bé v¨n b¶n râ. Víi tiÕng Anh cã 26 ch÷ cμi, kh«ng gian khãa sÏ lμ 26! = 4 x 1026 (hay nãi c¸ch kh¸c sÏ lËp ®−îc 26! B¶ng m·) I.4.4 M· Playfair (Playfair Cipher) M· nμy do nhμ khoa häc Anh lμ Sir Charles Wheatstone ph¸t m×nh vμo n¨m 1854. Nh−ng nã ®−îc mét ng−êi b¹n lμ Baron Playfair, nhμ qu¸n qu©n vÒ mËt m· ë Bé Ngo¹i giao Anh ph¸t triÓn. ThuËt to¸n Playfair ®−îc dùa trªn viÖc dïng ma trËn 5 x 5 c¸c ch÷ c¸i t¹o ra tõ khãa sö dông. VÝ dô cña Lond Peter Winsey M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z 7 Ch−¬ng Mét HÖ mËt mét khãa Trong tr−êng hîp nμy, tõ khãa lμ MONARCHY. Ma trËn ®−îc t¹o nªn b»ng c¸ch ®iÒn vμo c¸c ch÷ c¸i cña tõ khãa (kh«ng ®−îc lÆp) tõ tr¸i sang ph¶i, tõ trªn xuèng d−íi, tiÕp ®ã ®iÒn vμo c¸c phÇn tö sau cña ma trËn b»ng c¸c ch÷ c¸i cßn l¹i theo trËt tù b¶ng ch÷ c¸i. Ch÷ c¸i I vμ J coi lμ mét ch÷. B¶n râ ®−îc m· hãa hai ch÷ c¸i mét lóc theo c¸c luËt sau:  Ch÷ c¸i b¶n râ lÆp l¹i mμ r¬i vμo cïng mét cÆp sÏ ®−îc ng¨n c¸ch b»ng ch÷ c¸i läc (filter letter), ch¼ng h¹n lμ x ; do vËy ch÷ ballon sÏ ®−îc m· hãa lμ ba lx lo on.  C¸c ch÷ c¸i b¶n râ mμ r¬i vμo cïng dßng cña ma trËn th× mçi mét ch÷ ®−îc thay thÕ b»ng ch÷ c¸i bªn ph¶i, víi ch÷ c¸i r¬i vμo vÞ trÝ cuèi cïng cña dßng th× ®−îc thay thÕ bëi ch÷ c¸i ®Çu tiªn cña dßng ®ã. VÝ dô: ar ®−îc m· hãa lμ RM.  C¸c ch÷ c¸i b¶n râ mμ r¬i vμo cïng cét th× mçi ch÷ ®−îc thay thÕ b»ng ch÷ c¸i ë d−íi, víi ch÷ c¸i r¬i vμo vÞ trÝ cuèi cïng cña cét th× ®−îc thay thÕ bëi ch÷ c¸i ®Çu tiªn cña cét ®ã. VÝ dô: ch÷ mu ®−îc m· hãa lμ CM.  C¸c tr−êng hîp cßn l¹i, mçi ch÷ c¸i b¶n râ ®−îc thay thÕ b»ng ch÷ c¸i n»m ë giao dßng chøa nã vμ cét chiÕm bëi ch÷ c¸i kia cña b¶n râ. VÝ dô ch÷ hs ®−îc m· hãa lμ BP vμ ch÷ ea m· hãa lμ IM (hoÆc lμ JM). M· Playfair tiÕn bé h¬n m· ®¬n ch÷ c¸i (monoalphabetic Ciphers). Mét ®iÒu lμ do cã 26 ch÷ c¸i, nªn cã 26 x 26 = 676 diagram, do vËy x¸c ®Þnh mét diagram riªng biÖt lμ khã h¬n. H¬n n÷a tÇn sè t−¬ng ®èi cña ch÷ c¸i riªng biÖt biÓu thÞ ph¹m vi lín h¬n nhiÒu tÇn sè cña diagram lμm cho viÖc ph©n tÝch tÇn sè khã kh¨n h¬n. Do c¸c nguyªn nh©n ®ã mμ m· Playfair trong mét thêi gian dμi an toμn víi tÊn c«ng th¸m m·. Nã ®−îc dïng nh− mét hÖ thèng file chuÈn cña qu©n ®éi Anh trong thÕ chiÕn I vμ ®−îc qu©n ®éi Mü vμ c¸c l−îc l−îng kh¸c dïng ®¸ng kÓ trong thÕ chiÕn II. I.4.5 - M· Hill (Hill Cipher) MËt m· nhiÒu ch÷ c¸i (multiletter) kh¸c do nhμ to¸n häc Lester Hill ph¸t minh vμo n¨m 1929. ThuËt to¸n m· nμy lÊy m ch÷ c¸i liªn tiÕp cña b¶n râ vμ thay thÕ b»ng m ch÷ c¸i b¶n m·. Sù thay thÕ ®−îc x¸c ®Þnh b»ng m ph−¬ng tr×nh tuyÕn tÝnh, trong ®ã mçi mét ký tù ®−îc g¸n mét trÞ sè (a = 0, b = 1, z = 25). Víi m = 3, hÖ thèng cã thÓ ®−îc m« t¶ nh− sau: 8 Ch−¬ng Mét HÖ mËt mét khãa C1  (k11p1  k12 p 2  C 2  (k 21p1  k 22 p 2  C 3  (k 31p1  k 32 p 2  k13 p 3 ) mod 26   k 23 p 3 ) mod 26   k 33 p 3 ) mod 26  (1.4) HÖ trªn cã thÓ ®−îc biÓu diÔn d−íi d¹ng vect¬ cét vμ ma trËn nh− sau: C   k k k  p   1   11 12 13   1   C   k k k   p   2   21 22 23   2  C   k k k  p   3   31 32 33   3  HoÆc: C = KP trong ®ã C vμ P lμ c¸c vÐc t¬ cét ®é dμi 3 biÓu thÞ t−¬ng øng v¨n b¶n m· vμ b¶n râ, K lμ ma trËn 3 x 3 biÓu thÞ khãa m· hãa. C¸c phÐp to¸n thùc hiÖn víi mod 26. VÝ dô: kh¶o s¸t b¶n râ lμ: “paymoremoney”, dïng khãa m· hãa: 17 17 5   K   21 18 21    2 2 19 Ba ch÷ c¸i ®Çu tiªn cña b¶n râ ®−îc biÓu diÔn b»ng vector (15 0 24). Khi ®ã K (15 0 24) = (375 819 486) mod 26 = (11 13 18) = L N S. TiÕp tôc tÝnh to¸n nh− trªn, toμn bé b¶n râ sÏ ®−îc m· hãa lμ: LNSHDLEWMTRW. Gi¶i m· yªu cÇu dïng ma trËn nghÞch ®¶o cña ma trËn K lμ K-1. Nã ®−îc x¸c ®Þnh bëi ph−¬ng tr×nh: KK-1 = K-1K = I, trong ®ã I lμ ma trËn ®¬n vÞ. Nãi chung ma trËn nghÞch ®¶o kh«ng lu«n tån t¹i, muèn tån t¹i nã ph¶i tho¶ mét ®iÒu kiÖn nμo ®ã. Víi tr−¬ng hîp trªn, ma trËn nghÞch ®¶o lμ:  4 9 15   K 1  15 17 6     24 0 17  §iÒu nμy ®−îc chøng minh nh− sau: 17 17 5   4 9 15   443 442 442 1 0 0         21 18 21 15 17 6    858 495 780 mod 26   0 1 0         2 2 19   24 0 17  494 52 365   0 0 1 9 Ch−¬ng Mét HÖ mËt mét khãa DÔ dμng thÊy r»ng nÕu ma trËn K-1 ®−îc ¸p vμo b¶n m· sÏ thu ®−îc b¶n râ. Tæng qu¸t, hÖ thèng mËt m· Hill cã thÓ ®−îc biÓu diÔn nh− sau: C  E K (P)  KP mod 26 P  D K C  K -1 C mod 26  K -1 KP = P      (1.5) Còng nh− mËt m· Playfair, søc m¹nh cña m· Hill lμ che dÊu toμn bé tÇn suÊt ch÷ c¸i ®¬n. Víi m· Hill dïng ma trËn lín h¬n th× che dÊu nhiÒu th«ng tin tÇn suÊt h¬n (frequency information). Ch¼ng h¹n mËt m· Hill 3 x 3 kh«ng chØ che dÊu th«ng tin tÇn suÊt ch÷ c¸i ®¬n mμ c¶ tÇn suÊt diagram. MÆc dï m· Hill lμ m¹nh ®Ó chèng l¹i tÊn c«ng chØ b¶n m·, nã dÔ dμng bÞ ph¸ vì víi tÊn c«ng b¶n râ ®· biÕt. ThËt vËy, cho m· Hill m x m, gi¶ thiÕt chóng ta cã m cÆp b¶n râ – b¶n m·, mçi cÆp ®Òu dμi m. Chóng ta ®¸nh nh·n cÆp Pj = (p1j, p2j, , pmj) v μ Cj = (C1j, C2j, .., Cmj) sao cho Cj = KPj víi 1  j  m vμ ma trËn khãa kh«ng biÕt nμo ®ã . B©y giê ®Þnh nghÜa hai ma trËn kÝch th−íc m x m lμ X = (pij) vμ Y = (Cij). Khi ®ã chóng ta cã thÓ t¹o ph−¬ng tr×nh ma trËn: Y = XK. NÕu X cã nghÞch ®¶o, khi ®ã chóng ta cã thÓ x¸c ®Þnh K = X-1Y. NÕu X lμ kh«ng nghÞch ®¶o, khi ®ã t¹o phiªn b¶n míi cña X víi cÆp b¶n râ – b¶n m· t¨ng thªm cho ®Õn khi X lμ kh¶ ®¶o. I.4.6 MËt m· trËt tù ®a ch÷ c¸i (Polyalphabetic Ciphers) Mét c¸ch kh¸c ®Ó c¶i thiÖn kü thuËt trËt tù ®¬n ch÷ c¸i lμ dïng phÐp thÕ trËt tù ®¬n ch÷ c¸i ®¬n gi¶n kh¸c nhau mμ thùc hiÖn ®ång thêi khi m· hãa b¶n râ. Tªn chung cho phÐp tiÕp cËn nμy lμ Polyalphabetic Ciphers. TÊt c¶ c¸c kü thuËt ®ã cã nh÷ng ®Æc ®iÓm sau:  TËp c¸c quy t¾c thay thÕ ch÷ c¸i ®¬n ®−îc sö dông  Mét khãa x¸c ®Þnh quy t¾c riªng ®−îc chän cho phÐp biÕn ®çi ®· cho. Næi tiÕng nhÊt vμ ®¬n gi¶n nhÊt lμ thuËt to¸n gäi lμ Vigenere Cipher. S¬ ®å nh− b¶ng sau: 10 Ch−¬ng Mét HÖ mËt mét khãa a b c d ef g h ij kl m n op q r s t u v w x yz a ABCDEFGHIJKLMNOPQRSTUVWXYZ b BCDEFGHIJKLMNOPQRSTUVWXYZA c CDEFGHIJKLMNOPQRSTUVWXYZAB d D E F G H IJ K L M N O P Q R S T U V W X Y Z A B C e EFGHIJKLMNOPQRSTUVWXYZABCD f FGHIJKLMNOPQRSTUVWXYZABCDE g GHIJKLMNOPQRSTUVWXYZABCDEF h HIJKLMNOPQRSTUVWXYZABCDEFG i IJKLMNOPQRSTUVWXYZABCDEFGH j JKLMNOPQRSTUVWXYZABCDEFGHI k KLMNOPQRSTUVWXYZABCDEFGHIK l LMNOPQRSTUVWXYZABCDEFGHIJK m MNOPQRSTUVWXYZABCDEFGHIJKL n NOPQRSTUVWXYZABCDEFGHIJKLM o OPQRSTUVWXYZABCDEFGHIJKLMN p PQRSTUVWXYZABCDEFGHIJKLMNO q QRSTUVWXYZABCDEFGHIJKLMNOP r RSTUVWXYZABCDEFGHIJKLMNOPQ s STUVWXYZABCDEFGHIJKLMNOPQR t TUVWXYZABCDEFGHIJKLMNOPQRS u UVWXYZABCDEFGHIJKLMNOPQRST v VWXYZABCDEFGHIJKLMNOPQRSTU − WXYZABCDEFGHIJKLMNOPQRSTUV x XYZABCDEFGHIJKLMNOPQRSTUVW y YZABCDEFGHIJKLMNOPQRSTUVWX z ZABCDEFGHIJKLMNOPQRSTUVWXY H×nh (1.4): B¶ng VigenÌre Trong s¬ ®å nμy tËp c¸c phÐp thÕ trËt tù ®¬n ch÷ c¸i cã liªn quan gåm 26 m· Caesar víi k tõ 0 tíi 25. Mçi m· ®−îc ký hiÖu b»ng ch÷ c¸i khãa, nã 11 Ch−¬ng Mét HÖ mËt mét khãa lμ ch÷ c¸i b¶n m· thay thÕ cho ch÷ c¸i b¶n râ a. Nh− vËy m· Caesar víi k = 3 ®−îc ký hiÖu bëi trÞ khãa lμ d. B¶ng m· VigenÌre ®−îc thiÕt lËp tõ bé 26 ch÷ m· (26 ciphers) ®−îc xÕp theo hμng ngang, hμng tiÕp sau x©y dùng b»ng c¸ch dÞch hμng tr−íc ®i mét ký tù m·. Qu¸ tr×nh m· hãa lμ ®¬n gi¶n: cho ch÷ c¸i khãa x vμ ch÷ c¸i b¶n râ y, ®iÓm giao nhau gi÷a cét chøa ch÷ c¸i x vμ hμng chøa ch÷ c¸i y lμ tõ m·, trong tr−êng hîp nμy b¶n m· lμ V. §Ó m· hãa mét th«ng b¸o, khãa cÇn ph¶i dμi nh− th«ng b¸o. Th«ng th−êng khãa lμ tõ khãa lÆp. VÝ dô nh−: nÕu tõ khãa lμ deceplive, th«ng b¸o “we are discovered save yourself” ®−îc m· hãa nh− sau: deceptivedeceptivedeceptive Khãa: B¶n râ: wearediscoveredsaveyourself ZICVTWQNGRZGVTWAVZHCQYGLMGJ B¶n m·: Gi¶i m· còng ®¬n gi¶n. Ch÷ c¸i khãa l¹i x¸c ®Þnh dßng. VÞ trÝ cña ch÷ c¸i b¶n m· ë chç x¸c ®Þnh cét vμ ch÷ c¸i b¶n râ ë ®Ønh cña cét ®ã. Søc m¹nh cña m· nμy lμ ë chç cã nhiÒu ch÷ c¸i b¶n m· øng víi mçi ch÷ c¸i b¶n râ, t−¬ng øng víi ch÷ c¸i duy nhÊt cña tõ khãa. Nh− vËy th«ng tin tÇn sè ch÷ c¸i lμ mê mÞt. I.5. HÖ mËt cæ ®iÓn dùa trªn kü thuËt chuyÓn dÞch (Transposition) TÊt c¶ c¸c kü thuËt ®· kh¶o s¸t cho ®Õn b©y giê míi bao gåm thay thÕ ký tù b¶n râ bëi ký tù b¶n m·. Mét lo¹i ¸nh x¹ kh¸c n÷a thùc hiÖn mét sè ho¸n vÞ trªn b¶n râ. Kü thuËt nμy ®−îc gäi lμ mËt m· chuyÓn dÞch (Transposition cipher). Kü thuËt ®¬n gi¶n nhÊt lμ kü thuËt ®−êng r¨ng c−a. Trong kü thuËt nμy, b¶n râ ®−îc viÕt theo ®−êng r¨ng c−a. Sau ®ã thu ®−îc b¶n m· lμ d·y c¸c hμng ngang. VÝ dô: víi ®é s©u ®−êng r¨ng c−a lμ 2, b¶n râ “meet me m e e m t a e t f r e h t g t e o p a y r a t after the toga party” ®−îc viÕt nh− sau: B¶n m· thu ®−îc lμ: mematrhtgpryetefeteoaat Mét d¹ng phøc t¹p h¬n lμ viÕt th«ng b¸o trong h×nh ch÷ nhËt, dßng 12