Tài liệu Giáo trình mật mã học phần 1– hv bưu chính viễn thông

Lêi nãi ®Çu Trong sù ph¸t triÓn cña x· héi loµi ng−êi, kÓ tõ khi cã sù trao ®æi th«ng tin, an toµn th«ng tin trë thµnh mét nhu cÇu g¾n liÒn víi nã 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− 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 kü thuËt vµ c«ng nghÖ, cïng víi c¸c nhu cÇu ®Æc biÖt cã liªn quan tíi an toµn th«ng tin, ngµy nay c¸c kü thuËt chÝnh trong an toµn th«ng tin bao gåm: Kü thuËt mËt m· (Cryptography), Kü thuËt nguþ trang (Steganography), Kü thuËt t¹o bãng mê (Watermarking - hay x¨m ®iÖn tö). Kü thuËt mËt m· nh»m ®¶m b¶o ba dÞch vô an toµn c¬ b¶n:BÝ mËt (Confidential), X¸c thùc (Authentication), §¶m b¶o tÝnh toµn vÑn (Integrity). Cã thÓ thÊy r»ng mËt m· häc lµ mét lÜnh vùc khoa häc réng lín cã liªn quan rÊt nhiÒu ®Õn 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…. N¾m b¾t ®−îc nhu cÇu t×m hiÓu vÒ mËt m· häc, Häc viÖn C«ng nghÖ B−u chÝnh ViÔn th«ng phèi hîp víi Nhµ xuÊt b¶n B−u ®iÖn xuÊt b¶n cuèn gi¸o tr×nh "MËt m· häc" do PGS.TS NguyÔn B×nh chñ biªn. Cuèn gi¸o tr×nh nµy sÏ giíi thiÖu víi b¹n ®äc vÒ c¸c kiÕn thøc to¸n häc c¬ b¶n nh−: lý thuyÕt sè, c¸c cÊu tróc ®¹i sè nh− vµnh nhãm, tr−êng...; mét sè thuËt to¸n mËt m· cæ ®iÓn vµ hiÖn ®¹i; c¸c thñ tôc vµ c¸c chuÈn øng dông trong thùc tÕ. Víi nhiÒu vÝ dô cô thÓ, cuèn s¸ch gióp cho b¹n ®äc thuËn tiÖn trong qu¸ tr×nh häc tËp nghiªn cøu ®Ó n©ng cao kiÕn thøc vÒ mËt m· häc. §©y lµ gi¸o tr×nh phôc vô ®µo t¹o t¹i Häc viÖn C«ng nghÖ B−u chÝnh ViÔn th«ng. Hy väng cuèn s¸ch sÏ lµ tµi liÖu tham kh¶o h÷u Ých cho gi¶ng viªn, sinh viªn c¸c tr−êng ®¹i häc vÒ kü thuËt vµ c«ng nghÖ. Xin tr©n träng giíi thiÖu cïng b¹n ®äc. Hµ Néi, ngµy 23 th¸ng 10 n¨m 2003 Häc viÖn c«ng nghÖ b−u chÝnh viÔn th«ng thuËt ng÷ viÕt t¾t DES Data Encryption Standard ChuÈn m· d÷ liÖu LAN Local Area Network M¹ng côc bé MDV M· dÞch vßng MTT M· thay thÕ MHV M· ho¸n vÞ ECB Electronic Code Book ChÕ ®é quyÓn m· ®iÖn tö CFB Cripher Feedback ChÕ ®é ph¶n håi m· CBC Cripher Block Chaining ChÕ ®é liªn kÕt khèi m· RSA Rivest - Shamir - Adleman MAC Message Authentication Code M· x¸c thùc th«ng b¸o OWHF Oneway Hash Funtion Hµm b¨m mét chiÒu CRHF Collision Resistant hash function Hµm b¨m khã va ch¹m MDC Manipulation Detection Code M· ph¸t hiÖn sù söa ®æi LSB Least Signification Bit Bit thÊp nhÊt (cã gi¸ trÞ nhá nhÊt Tiªu ®Ò Header IDEA International Data Encryption Algorithm ThuËt to¸n m· hãa d÷ liÖu quèc tÕ PGP Pretty Good Privacy ThuËt to¸n m· hãa PGP SET Secure Electronic Transaction Giao dÞch ®iÖn tö an toµn LFSR Linear Feedback Sequence Register Thanh ghi håi tiÕp tuyÕn tÝnh Firewall Bøc t−êng löa Server M¸y chñ Router Bé ®Þnh tuyÕn PhÇn I C¸c kiÕn thøc to¸n häc phô trî bæ tóc vÒ lý thuyÕt sè 1.1. Sè nguyªn TËp c¸c sè nguyªn {K, − 3, − 2, − 1, 0,1, 2, 3,K}= Z. 1.1.1. §Þnh nghÜa 1.1 Cho a, b ∈ Ζ a lμ −íc cña b nÕu ∃c ∈ Z : b = a.c. Ký hiÖu lμ a b. 1.1.2. C¸c tÝnh chÊt chia hÕt ∀ a, b, c ∈ Ζ ta cã: (i) a a. (ii) NÕu a b vμ b c th× a c. (iii) NÕu a b vμ a c th× a (bx + cy ) víi ∀x, y ∈ Z. (iv) NÕu a b vμ b a th× a = ± b. 1.1.3. §Þnh nghÜa 1.2 (ThuËt to¸n chia ®èi víi c¸c sè nguyªn) NÕu a vμ b lμ c¸c sè nguyªn víi b ≥ 1 th× a = qb + r; 0 ≤ r < b q vμ r lμ nh÷ng gi¸ trÞ duy nhÊt. 10 Gi¸o tr×nh MËt m· häc PhÇn d− cña phÐp chia a vμ b ®−îc ký hiÖu a mod b = r Th−¬ng cña phÐp chia a vμ b ®−îc ký hiÖu a div b = q ⎡a ⎤ ⎡a ⎤ Ta cã a div b = ⎢ ⎥, a mod b = a − b⎢ ⎥. ⎣b⎦ ⎣b⎦ VÝ dô: a = 73, b = 17. 73 div 17 = 4, 73 mod 17 = 5. 1.1.4. §Þnh nghÜa 1.3 (¦íc chung) c lμ −íc chung cña a vμ b nÕu c a & c b. 1.1.5. §Þnh nghÜa 1.4 (¦íc chung lín nhÊt (¦CLN)) Sè nguyªn d−¬ng d lμ ¦CLN cña c¸c sè nguyªn a vμ b (Ký hiÖu d = (a, b)) nÕu: (i) d lμ −íc chung cña a vμ b. (ii) NÕu cã c a vμ c b th× c d . Nh− vËy (a,b) lμ sè nguyªn d−¬ng lín nhÊt −íc cña c¶ a vμ b kh«ng kÓ (0,0) = 0. VÝ dô: C¸c −íc chung cña 12 vμ 18 lμ {± 1, ± 2, ± 3, ± 6} (12,18) = 6 1.1.6. §Þnh nghÜa 1.5 (Béi chung nhá nhÊt (BCNN)) Sè nguyªn d−¬ng d lμ BCNN cña c¸c sè nguyªn a vμ b (Ký hiÖu d = BCNN (a,b)) nÕu: (i) a d, b d. (ii) NÕu cã a c, b c th× d c. Nh− vËy d lμ sè nguyªn d−¬ng nhá nhÊt lμ béi cña c¶ a vμ b. Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 11 1.1.7. TÝnh chÊt BCNN (a , b) = a.b (a , b) VÝ dô: (12 ,18 ) = 6 ⇒ BCNN(12 ,18 ) = 12 .18 = 36 . 6 1.1.8. §Þnh nghÜa 1.6 Hai sè nguyªn d−¬ng a vμ b ®−îc gäi lμ nguyªn tè cïng nhau nÕu: (a,b) = 1. 1.1.9. §Þnh nghÜa 1.7 Sè nguyªn p ≥ 2 ®−îc gäi lμ sè nguyªn tè nÕu c¸c −íc d−¬ng cña nã chØ lμ 1 vμ p. Ng−îc l¹i p ®−îc gäi lμ hîp sè. 1.1.10. §Þnh lý c¬ b¶n cña sè häc Víi mçi sè nguyªn n ≥ 2 ta lu«n ph©n tÝch ®−îc d−íi d¹ng tÝch cña luü thõa cña c¸c sè nguyªn tè. n = p1e1 pe22 K pekk Trong ®ã pi lμ c¸c sè nguyªn tè kh¸c nhau vμ ei lμ c¸c sè nguyªn d−¬ng. H¬n n÷a ph©n tÝch trªn lμ duy nhÊt. 1.1.11. §Þnh nghÜa 1.8 Víi n ≥ 2, hμm Φ(n ) ®−îc x¸c ®Þnh lμ sè c¸c sè nguyªn trong kho¶ng [1 , n ] nguyªn tè cïng nhau víi n. 1.1.12. C¸c tÝnh chÊt cña hμm Φ(n) (i) NÕu p lμ c¸c sè nguyªn tè th× Φ(p) = p – 1. (ii) NÕu (m, n) = 1 th× Φ(m.n) = Φ(m). Φ(n). 12 Gi¸o tr×nh MËt m· häc (iii) NÕu n = p1e1 pe22 K pekk lμ ph©n tÝch ra thõa sè nguyªn tè cña n th×: ⎛ 1 ⎞⎛ 1 ⎞ ⎛ 1 ⎟⎟ K ⎜⎜1 − Φ (n ) = n⎜⎜1 − ⎟⎟ ⎜⎜1 − p1 ⎠ ⎝ p2 ⎠ ⎝ pk ⎝ ⎞ ⎟⎟ . ⎠ 1.1.13. §Þnh lý 1.1 Víi ∀n ≥ 5 th× Φ (n ) > n 6 ln (ln n ) 1.2. c¸c thuËt to¸n trong z Cho a vμ b lμ c¸c sè nguyªn kh«ng ©m vμ nhá h¬n hoÆc b»ng n. CÇn chó ý r»ng sè c¸c bit trong biÓu diÔn nhÞ ph©n cña n lμ [lgn] + 1 vμ sè nμy xÊp xØ b»ng lgn. Sè c¸c phÐp to¸n bit ®èi víi bèn phÐp to¸n c¬ b¶n trªn c¸c sè lμ céng, trõ, nh©n vμ chia sö dông c¸c thuËt to¸n kinh ®iÓn ®−îc tãm l−îc trªn b¶ng 1.1. C¸c kü thuËt tinh tÕ h¬n ®èi víi c¸c phÐp to¸n nh©n vμ chia sÏ cã ®é phøc t¹p nhá h¬n. B¶ng 1.1: §é phøc t¹p bit cña c¸c phÐp to¸n c¬ b¶n trong Z PhÐp to¸n §é phøc t¹p bit Céng a+b 0(lga + lgb) = 0(lgn) Trõ a–b 0(lga + lgb) = 0(lgn) Nh©n a.b 0((lga).(lgb)) = 0((lgn)2) Chia a = qb + r 0((lga).(lgb)) = 0((lgn)2) ¦CLN cña 2 sè nguyªn a vμ b cã thÓ ®−îc tÝnh theo ®Þnh lý sau: 1.2.1. §Þnh lý 1.2 NÕu a = p1e1 pe22 K pekk , b = p1f1 p2f2 ...p fkk trong ®ã e i ≥ 0, fi ≥ 0 (e2 , f2 ) (ek , fk ) K pmin th× − CLN(a , b) = p1min (e1 , f1 ) p min 2 k Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 13 (e2 ,f2 ) (ek ,fk ) vμ BCNN (a , b) = p1max (e1 ,f1 ) pmax K pmax . 2 k VÝ dô: Cho a = 4864 = 28.19; b = 3458 = 2.7.13.19. Khi ®ã: − CLN(a , b) = (4864, 3458 ) = 2.19 = 38 BCNN(a , b) = (4864, 3458 ) = 28.7.13.19 = 442624 . 1.2.2. §Þnh lý 1.3 NÕu a vμ b lμ c¸c sè nguyªn d−¬ng víi a > b th× ¦CLN(a,b) = ¦CLN (b,a mod b). ThuËt to¸n Euclide sau sÏ cho ta c¸ch tÝnh ¦CLN rÊt hiÖu qu¶ mμ kh«ng cÇn ph¶i ph©n tÝch ra thõa sè nguyªn tè. 1.2.3. ThuËt to¸n Euclide TÝnh ¦CLN cña 2 sè nguyªn Vμo : Hai sè nguyªn kh«ng ©m a vμ b víi a > b Ra : ¦CLN cña a vμ b. (1) While b ≠ 0 do r ← a mod b, a ← b, b ← r (2) Return (a). 1.2.4. §Þnh lý 1.4 ThuËt to¸n trªn cã thêi gian ch¹y chõng 0 ( (lg n ) ) c¸c phÐp 2 to¸n bit. VÝ dô: Sau ®©y lμ c¸c b−íc chia cña thuËt to¸n trªn khi tÝnh: (4864, 3458 ) = 38 4864 = 1.3458 + 1406 3458 = 2.1406 + 646 1406 = 2.646 + 76 646 = 5.114 + 38 76 = 2.38 + 0 14 Gi¸o tr×nh MËt m· häc ThuËt to¸n trªn cã thÓ ®−îc më réng ®Ó kh«ng nh÷ng chØ tÝnh ®−îc ¦CLN cña 2 sè nguyªn a vμ b mμ cßn tÝnh ®−îc c¸c sè nguyªn x vμ y tho¶ m·n ax + by = d . 1.2.5. ThuËt to¸n Euclide më réng Vμo : Hai sè nguyªn kh«ng ©m a vμ b víi a ≥ b Ra : d = ¦CLN(a,b) vμ c¸c sè nguyªn x vμ y tháa m·n ax + by = d . (1) NÕu b= 0 th× ®Æt d ← a , x ← 1 , y ← 0 vμ return (d, x, y) (2) §Æt x 2 ← 1, x1 ← 0, y 2 ← 0 , y1 ← 1 (3) While b > 0 do (3.1) q ← ⎣a / b⎦ , r ← a − qb , x ← x 2 − qx1 , y ← y 2 − qy1 (3.2) a ← b, b ← r, x 2 ← x1 , x1 ← x, y 2 ← y1 , y1 ← y (4) §Æt d ← a, x ← x 2 , y ← y 2 vμ vμ return (d, x, y). 1.2.6. §Þnh lý 1.5 ThuËt to¸n trªn cã thêi gian ch¹y cì 0((lgn)2) c¸c phÐp to¸n bit. VÝ dô: B¶ng 1.2 sau chØ ra c¸c b−íc cña thuËt to¸n trªn víi c¸c gi¸ trÞ vμo a = 4864 vμ b = 3458 B¶ng 1.2: ThuËt to¸n Euclide më réng Q r x y a b x2 x1 y2 y1 − − − − 4864 3458 1 0 0 1 1 1406 1 −1 3458 1406 0 1 1 −1 2 646 −2 3 1406 646 1 −2 −1 3 2 114 5 −7 646 114 −2 5 3 7 5 76 −27 38 114 76 5 −27 −7 38 1 38 32 −45 76 38 −27 32 38 −45 2 0 −91 128 38 0 32 −91 −45 128 Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 15 Víi c¸c ®Çu vμo a = 4864 vμ b = 3458 Bëi vËy ta cã: ¦CLN(4864,3458) = 38 vμ (4864)(32) + (3458)(-45) = 38. 1.3. C¸c sè nguyªn modulo n 1.3.1. §Þnh nghÜa 1.9 NÕu a vμ b lμ c¸c sè nguyªn th× a ®−îc gäi lμ ®ång d− víi b theo modulo (ký hiÖu lμ a = b mod n) nÕu n (a − b) . Sè nguyªn n ®−îc gäi lμ modulo ®ång d−. VÝ dô: 24 ≡ 9 mod 5 v× 24 – 9 = 3.5 − 11 ≡ 17 mod 7 v× − 11 − 17 = −4.7 . 1.3.2. C¸c tÝnh chÊt §èi víi a, a1 , b, b1 , c ∈ Ζ ta cã: (1) a ≡ b(mod n ) nÕu vμ chØ nÕu a vμ b còng cã phÇn d− khi chia cho n. (2) TÝnh ph¶n x¹: a ≡ a(mod n ) . (3) TÝnh ®èi xøng: NÕu a ≡ b(mod n ) th× b ≡ a(mod n ) (4) TÝnh b¾c cÇu: NÕu a ≡ b(mod n ) vμ b ≡ c(mod n ) th× a ≡ c(mod n ) (5) NÕu a ≡ a1 (mod n ) vμ b ≡ b1 (mod n ) th× a + b ≡ a1 + b1 (mod n ) vμ a.b ≡ a1 .b1 (mod n ) Líp t−¬ng ®−¬ng cña mét sè nguyªn a lμ tËp c¸c sè nguyªn ®ång d− víi a modulo n. Tõ c¸c tÝnh chÊt (2), (3) vμ (5) ë trªn ta cã thÓ thÊy r»ng ®èi víi n cè ®Þnh, quan hÖ ®ång d− theo modulo n sÏ ph©n ho¹ch Z thμnh c¸c líp t−¬ng ®−¬ng. 16 Gi¸o tr×nh MËt m· häc NÕu a = qn + r víi 0 ≤ r ≤ n th× a ≡ r(mod n ) . Bëi vËy mçi sè nguyªn a lμ ®ång d− theo modulo n víi mét sè nguyªn duy nhÊt n»m trong kho¶ng tõ 0 tíi n - 1, sè nμy ®−îc gäi lμ thÆng d− tèi thiÓu cña a mod n. Nh− vËy a vμ r cã thÓ ®−îc dïng ®Ó biÓu thÞ cho líp t−¬ng ®−¬ng nμy. 1.3.3. §Þnh nghÜa 1.10 C¸c sè nguyªn modulo n (ký hiÖu Zn) lμ tËp (c¸c líp t−¬ng ®−¬ng) cña c¸c sè nguyªn {0,1, 2,K, n − 1}. C¸c phÐp céng, trõ, nh©n trong Zn ®−îc thùc hiÖn theo modulo n. VÝ dô: Z25 = {0,1,K, 24}. Trong Z 25 ta cã: 13 + 16 = 4 v× 13 + 16 = 29 ≡ 4 (mod 25 ) T−¬ng tù 13.16 = 8 trong Z25. 1.3.4. §Þnh nghÜa 1.11 (PhÇn tö nghÞch ®¶o) Cho a ∈ Z n , PhÇn tö nghÞch ®¶o (ng−îc theo phÐp nh©n) cña a mod n lμ mét sè nguyªn x ∈ Z n sao cho: ax ≡ 1(mod n ) NÕu x tån t¹i th× nã lμ duy nhÊt, a ®−îc gäi lμ kh¶ nghÞch. PhÇn tö nghÞch ®¶o cña a ®−îc ký hiÖu lμ a−1. 1.3.5. §Þnh nghÜa 1.12 PhÐp chia cña a cho b mod n lμ tÝch cña a vμ b−1 mod n tÝch nμy ®−îc x¸c ®Þnh nÕu b lμ phÇn tö kh¶ nghÞch 1.3.6. §Þnh lý 1.6 Cho a ∈ Z n , khi ®ã a lμ kh¶ nghÞch nÕu vμ chØ nÕu: (a, n ) = 1 VÝ dô: C¸c phÇn tö kh¶ nghÞch trong Z9 lμ 1, 2, 3, 4, 5, 7 vμ 8. Ch¼ng h¹n 4 − 1 = 7 v× 4 . 7 ≡ 1 (mod 9 ) . Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 17 1.3.7. §Þnh lý 1.7 Cho d = (a,n). Ph−¬ng tr×nh ®ång d− ax ≡ b(mod n ) cã nghiÖm x nÕu vμ chØ nÕu d b , trong tr−êng hîp nμy cã ®óng d nghiÖm n»m gi÷a 0 vμ n - 1, nh÷ng nghiÖm nμy lμ tÊt c¶ c¸c ®ång d− theo modulo n d . 1.3.8. §Þnh lý 1.8 (PhÇn d− China) NÕu c¸c sè nguyªn n1 , n 2 ,K, n k lμ nguyªn tè cïng nhau tõng ®«i mét th× hÖ c¸c ph−¬ng tr×nh ®ång d−: x ≡ a 1 (mod n 1 ) x ≡ a 2 (mod n 2 ) .......... .......... .... x ≡ a k (mod n k ) sÏ cã nghiÖm duy nhÊt theo modulo n (n = n 1 . n 2 K n k ) . 1.3.9. ThuËt to¸n Gausse NghiÖm x cña hÖ ph−¬ng tr×nh ®ång d− trong ®Þnh lý phÇn d− China cã thÓ ®−îc tÝnh b»ng: x= k ∑a N M i i i mod n i =1 Trong ®ã: N i = n / n i vμ M i = N i− 1 mod n i C¸c tÝnh to¸n nμy cã thÓ ®−îc thùc hiÖn trong 0 ( (lg n ) ) c¸c 2 phÐp to¸n trªn bit. VÝ dô: CÆp ph−¬ng tr×nh ®ång d− x ≡ 3 (mod 7 ), x ≡ 7 (mod 13 ) cã nghiÖm duy nhÊt x ≡ 59 (mod 91 ) . 18 Gi¸o tr×nh MËt m· häc 1.3.10. §Þnh lý 1.9 NÕu (n1 , n 2 ) = 1 th× cÆp ph−¬ng tr×nh ®ång d−. x ≡ a (mod n 1 ) , x ≡ a (mod n 2 ) cã mét nghiÖm duy nhÊt x ≡ a (mod n 1 , n 2 ) . 1.3.11. §Þnh nghÜa 1.13 Nhãm nh©n cña Z n lμ Z *n = {a ∈ Z n (a, n ) = 1} §Æc biÖt, nÕu n lμ sè nguyªn tè th× Z *n = {a 1 ≤ a ≤ n − 1}. 1.3.12. §Þnh nghÜa 1.14 CÊp cña Z *n lμ sè c¸c phÇn tö trong Z *n (ký hiÖu Z *n ) Theo ®Þnh nghÜa cña hμm Phi-Euler ta thÊy: Z *n = Φ(n ) CÇn ®Ó ý r»ng nÕu a ∈ Z *n vμ b ∈ Z *n th× a, b ∈ Z *n vμ bëi vËy Z *n lμ ®ãng ®èi víi phÐp nh©n. 1.3.13. §Þnh lý 1.10 Cho p lμ mét sè nguyªn tè: (1) §Þnh lý Euler: NÕu a ∈ Z *n th× a Φ (n ) ≡ 1 (mod n ) . (2) NÕu n lμ tÝch cña c¸c sè nguyªn kh¸c nhau vμ nÕu r ≡ s (mod Φ (n )) th× a r ≡ as (mod n ) ®èi víi mäi sè nguyªn a. Nãi mét c¸ch kh¸c khi lμm viÖc víi modulo n th× c¸c sè mò cã thÓ ®−îc rót gän theo modulo Φ(n ). Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 19 1.3.14. §Þnh lý 1.11 Cho p lμ mét sè nguyªn tè: (1) §Þnh lý Ferma: NÕu (a, p) = 1 th× a p −1 ≡ 1 (mod p ) . (2) NÕu r ≡ s (mod p − 1 ) th× a r ≡ a s (mod p ) ®èi víi mäi sè nguyªn a. Nãi mét c¸ch kh¸c khi lμm viÖc víi modulo cña mét sè nguyªn tè p th× c¸c luü thõa cã thÓ ®−îc rót gän theo modulo p - 1. (3) §Æc biÖt a p ≡ a (mod p ) víi mäi sè nguyªn a. 1.3.15. §Þnh nghÜa 1.15 Cho a ∈ Z *n . CÊp cña a (ký hiÖu lμ ord(a ) ) lμ sè nguyªn d−¬ng nhá nhÊt t sao cho a t ≡ 1 (mod n ) . 1.3.16. §Þnh nghÜa 1.16 Cho a ∈ Z *n , ord(a ) = t vμ a s ≡ 1 (mod n ) khi ®ã t lμ −íc cña s. §Æc biÖt t Φ (n ) . VÝ dô: Cho n = 21, khi ®ã Z *21 = {1, 2, 4 , 5, 8 , 10 , 11 , 13 , 16 , 17 , 19 , 20 } Chó ý r»ng Φ (21 ) = Φ (7 ) Φ (3 ) = 12 = Z *21 . CÊp cña c¸c phÇn tö trong Z *21 ®−îc nªu trong b¶ng sau: B¶ng 13: CÊp cña c¸c phÇn tö trong Z *21 * a ∈ Z 21 1 2 4 5 8 10 11 13 16 17 19 20 Ord(a) 1 6 3 6 2 6 6 2 3 6 6 2 20 Gi¸o tr×nh MËt m· häc 1.3.17. §Þnh nghÜa 1.17 Cho α ∈ Z *n . NÕu cÊp cña α lμ Φ(n ) th× α ®−îc gäi lμ phÇn tö sinh hay phÇn tö nguyªn thñy cña Z *n . NÕu Z *n cã mét phÇn tö sinh th× Z *n ®−îc gäi lμ cyclic. 1.3.18. C¸c tÝnh chÊt cña c¸c phÇn tö sinh cña (1) Z*n Z*n cã phÇn tö sinh nÕu vμ chØ nÕu n = 2, 4, p k hoÆc lμ 2p k , trong ®ã p lμ mét sè nguyªn tè lÎ vμ k ≥ 1 . §Æc biÖt, nÕu p lμ * mét sè nguyªn tè th× Z n cã phÇn tö sinh. * (2) NÕu α lμ mét phÇn tö sinh cña Z n th×: Z *n = { α i mod n 0 ≤ i ≤ Φ(n ) − 1 } (3) Gi¶ sö r»ng α lμ mét phÇn tö sinh cña b = α i mod n còng lμ mét phÇn tö sinh cña (i, Φ(n )) = 1 . Tõ ®ã ta rót ra r»ng nÕu Z*n tö sinh lμ Φ(Φ(n )) . Z*n Z*n , khi ®ã nÕu vμ chØ nÕu lμ cyclic th× sè c¸c phÇn (4) α ∈ Zn lμ mét phÇn tö sinh cña Z n nÕu vμ chØ nÕu * * α Φ (n ) / p ≠ 1(mod n ) ®èi víi mçi nguyªn tè p cña Φ(n ) . VÝ dô: Z*21 kh«ng lμ cyclic v× nã kh«ng chøa mét phÇn tö cã cÊp Φ(21) = 12 (Chó ý r»ng 21 kh«ng tháa m·n ®iÒu kiÖn (1) ë trªn). Z *25 lμ cyclic vμ cã mét phÇn tö sinh α = 2 . Ch−¬ng 1: Bæ tóc vÒ lý thuyÕt sè 21 1.3.19. §Þnh nghÜa 1.18 Cho a ∈ Z*n , a ®−îc gäi lμ thÆng d− bËc hai modulo n (hay b×nh ph−¬ng cña modulo n) nÕu tån t¹i x ∈ Z*n sao cho x 2 ≡ a(mod n ) . NÕu kh«ng tån t¹i x nh− vËy th× a ®−îc gäi lμ thÆng d− kh«ng bËc hai mod n. TËp tÊt c¶ c¸c thÆng d− bËc hai modulo n ®−îc ký hiÖu lμ Qn, cßn tËp tÊt c¶ c¸c thÆng d− kh«ng bËc hai ®−îc ký hiÖu lμ Q n . CÇn chó ý r»ng theo ®Þnh nghÜa 0 ∉ Z*n . Bëi vËy 0 ∉ Q n vμ 0 ∉ Qn . 1.3.20. §Þnh lý 1.12 Cho p lμ mét sè nguyªn tè lÎ vμ α lμ mét phÇn tö sinh cña Z*p . Khi ®ã a ∈ Z*p lμ mét thÆng d− bËc hai modulo p nÕu vμ chØ nÕu a = α i mod p , trong ®ã i lμ mét sè nguyªn ch½n. Tõ ®ã rót ra r»ng Q p = (p − 1) 2 vμ Q p = (p − 1) , tøc lμ mét nöa sè phÇn tö trong 2 Z*p lμ c¸c thÆng d− bËc hai vμ nöa cßn l¹i thÆng d− kh«ng bËc hai. * VÝ dô: α = 6 lμ mét phÇn tö sinh cña Z13 . C¸c lòy thõa cña α ®−îc liÖt kª ë b¶ng sau: i 0 1 2 3 4 5 6 7 8 9 10 11 αi mod 13 1 6 10 8 9 2 12 7 3 5 4 11 Bëi vËy Q13 = { 1, 3, 4, 9, 10,12 }, Q13 = { 2, 5, 6, 7, 8,11 } . 1.3.21. §Þnh lý 1.13 Cho n lμ tÝch cña hai sè nguyªn tè lÎ kh¸c nhau q vμ p, n = p.q, khi ®ã a ∈ Z*n lμ mét thÆng d− bËc hai modulo n nÕu vμ chØ nÕu a ∈ Q p vμ a ∈ Q p . §iÒu ®ã dÉn tíi Q n = Q q . Q p = (p − 1)(q − 1) 4 22 Gi¸o tr×nh MËt m· häc vµ Qn = 3(p − 1)(q − 1) 4 VÝ dô: Cho n = 21. Khi ®ã Q 21 = { 1, 4,16 } Q 21 = {2,5, 8,10,11,13,17,19, 20} 1.3.22. §Þnh nghÜa 1.19 Cho a ∈ Q n . NÕu x ∈ Z*n tháa m·n x 2 ≡ a(mod n ) th× x ®−îc gäi lμ c¨n bËc hai cña a mod n. 1.3.23. §Þnh lý 1.14 (Sè c¸c c¨n bËc hai) (1) NÕu p lμ mét sè nguyªn tè lÎ vμ a ∈ Q n th× a ®−îc gäi lμ c¨n bËc hai theo modulo p. (2) Tæng qu¸t h¬n, cho n = p1e1 pe22 K pekk , trong ®ã pi lμ c¸c sè nguyªn tè lÎ ph©n biÖt vμ e i ≥ 1 . NÕu a ∈ Q n th× cã ®óng 2k c¨n bËc hai kh¸c nhau theo modulo n. VÝ dô: C¸c c¨n bËc 2 cña 12 mod 37 lμ 7 vμ 30. C¸c c¨n bËc 2 cña 121 mod 315 lμ 11, 74, 101, 151, 164, 214, 241 vμ 304. 1.4. C¸c thuËt to¸n trong Zn Cho n lμ mét sè nguyªn d−¬ng. C¸c phÇn tö cña Zn sÏ ®−îc biÓu thÞ bëi c¸c sè nguyªn Q 21 = {0,1, 2,..., n − 1}. Ta thÊy r»ng, nÕu a, b ∈ Z n th× a+b ⎩a + b − r (a + b)mod n = ⎧⎨ a+b 1 th× a−1 mod n kh«ng tån t¹i. Ng−îc l¹i return (x). PhÐp lòy thõa theo modulo cã thÓ ®−îc thùc hiÖn cã hiÖu qu¶ b»ng thuËt to¸n nh©n vμ b×nh ph−¬ng cã lÆp. §©y lμ mét thuËt to¸n rÊt quan träng trong nhiÒu thñ tôc mËt m·. Cho biÓu diÔn nhÞ ph©n cña k lμ: t k i 2 i trong ®ã mçi k i ∈ {0,1} khi ®ã ∑ i =0 a k 2 i = (a 2 ∏ i =0 t a = k i 0 ) (a ) K (a ) k0 21 k1 2t kt 1.4.2. ThuËt to¸n nh©n vμ b×nh ph−¬ng cã lÆp ®Ó lÊy luü thõa trong Zn Vμo: a ∈ Z n vμ sè nguyªn k, (0 ≤ k < n ) cã biÓu diÔn nhÞ ph©n: k= t k i 2i ∑ i =0 Ra: ak mod n. (1) §Æt b ← 1 . NÕu k = 0 th× return (b). (2) §Æt A ← a . 24 Gi¸o tr×nh MËt m· häc (3) NÕu k0 = 1 th× ®Æt b ← a . (4) For i from 1 to t do (4.1) §Æt A ← A 2 mod n (4.2) NÕu k i = 1 th× ®Æt b ← A.b mod n (5) Return (b). VÝ dô: B¶ng 1.4 sau chØ ra c¸c b−íc tÝnh to¸n 5596 mod 1234 = 1013 B¶ng 1.4: TÝnh 5596 mod 1234 i 0 1 2 3 4 5 6 7 8 9 ki 0 0 1 0 1 0 1 0 0 1 A 5 25 625 681 1011 369 421 779 947 925 b 1 1 625 625 67 67 1059 1059 1059 1013 Sè c¸c phÐp to¸n bit ®èi víi phÐp to¸n c¬ b¶n trong Zn ®−îc tãm l−îc trong b¶ng 1.5. B¶ng 1.5: §é phøc t¹p bit cña c¸c phÐp to¸n c¬ b¶n trong Zn PhÐp to¸n §é phøc t¹p bit Céng modulo a+b 0(lgn) Trõ modulo a-b 0(lgn) Nh©n modulo a.b 0((lgn)2) a-1 mod n 0((lgn)2) ak mod n, k < n 0((lgn)3) NghÞch ®¶o modulo Lòy thõa modulo 1.5. c¸c ký hiÖu legendre vμ jacobi Ký hiÖu Legendre lμ mét c«ng cô h÷u Ých ®Ó xem xÐt liÖu mét sè nguyªn a cã lμ mét thÆng d− bËc hai theo modulo cña mét sè nguyªn tè p hay kh«ng?