Tài liệu Nghiên cứu một số giao thức trong tính toán hình học đa bên an toàn

BË GIO DÖC V€ €O T„O TR×ÍNG „I HÅC S× PH„M H€ NËI 2 NGUY™N THÀ NG…U NGHI–N CÙU MËT SÈ GIAO THÙC TRONG TNH TON HœNH HÅC A B–N AN TO€N LUŠN V‹N TH„C Sž TON HÅC H  Nëi, 2017 BË GIO DÖC V€ €O T„O TR×ÍNG „I HÅC S× PH„M H€ NËI 2 NGUY™N THÀ NG…U NGHI–N CÙU MËT SÈ GIAO THÙC TRONG TNH TON HœNH HÅC A B–N AN TO€N Chuy¶n ng nh: To¡n ùng döng M¢ sè: 60 46 01 12 LUŠN V‹N TH„C Sž TON HÅC Ng÷íi h÷îng d¨n khoa håc: TS. TR†N V‹N DÔNG H€ NËI, 2017 LÍI CƒM ÌN Luªn v«n n y ÷ñc thüc hi»n t¤i Tr÷íng ¤i håc S÷ ph¤m H  Nëi 2. º ho n th nh ÷ñc luªn v«n n y tæi ¢ nhªn ÷ñc r§t nhi·u sü ëng vi¶n, gióp ï cõa nhi·u c¡ nh¥n v  tªp thº. Tr÷îc h¸t, tæi xin b y tä láng bi¸t ìn s¥u s­c ¸n th¦y gi¡o TS. Tr¦n V«n Dông  Gi£ng vi¶n tr÷íng HGTVT H  Nëi ¢ nhi»t t¼nh gióp ï, trüc ti¸p ch¿ b£o, h÷îng d¨n tæi trong suèt qu¡ tr¼nh thüc hi»n luªn v«n cao håc. Xin còng b y tä láng bi¸t ìn ch¥n th nh tîi c¡c th¦y cæ gi¡o trong tr÷íng ¤i håc S÷ ph¤m H  Nëi 2, ng÷íi ¢ em l¤i cho tæi nhúng ki¸n thùc bê trñ, væ còng câ ½ch trong nhúng n«m håc vøa qua. Công xin gûi líi c¡m ìn ch¥n th nh tîi Ban Gi¡m hi»u, Pháng  o t¤o sau ¤i håc, Khoa To¡n tr÷íng ¤i håc S÷ ph¤m H  Nëi 2 ¢ t¤o i·u ki»n cho tæi trong qu¡ tr¼nh håc tªp. Cuèi còng tæi xin gûi líi c¡m ìn ¸n gia ¼nh, b¤n b±, nhúng ng÷íi ¢ luæn b¶n tæi, ëng vi¶n v  khuy¸n kh½ch tæi trong qu¡ tr¼nh thüc hi»n · t i nghi¶n cùu cõa m¼nh. H  Nëi, th¡ng 06 n«m 2017 T¡c gi£ Nguy¹n Thà Ng¥u LÍI CAM OAN Tæi xin cam oan: Nhúng sè li»u v  k¸t qu£ nghi¶n cùu tr¼nh b y trong luªn v«n n y l  ho n to n trung thüc, cõa tæi khæng vi ph¤m b§t cù i·u g¼ trong luªt sð húu tr½ tu» v  ph¡p luªt Vi»t Nam. Måi sü gióp ï cho vi»c thüc hi»n luªn v«n n y ¢ ÷ñc c£m ìn v  c¡c thæng tin tr½ch d¨n trong luªn v«n ·u ÷ñc ghi rã nguçn gèc. Nhúng ki¸n thùc tæi tr¼nh b y trong luªn v«n n y ch÷a ÷ñc tr¼nh b y ho n ch¿nh trong b§t cù t i li»u n o. H  Nëi, th¡ng 06 n«m 2017 T¡c gi£ Nguy¹n Thà Ng¥u Möc löc Líi mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Ch÷ìng 1. C¡c ki¸n thùc cì sð . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1. Sè håc Modulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2. Chú k½ i»n tû DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3. M¢ hâa Elgamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 Ch÷ìng 2. Mët sè giao thùc t½nh to¡n h¼nh håc a b¶n an to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.1. C¡c kh¡i ni»m v  mæ h¼nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2. Mët sè thuªt to¡n v  giao thùc bê trñ . . . . . . . . . . . . . . . . . . . . 23 2.2.1. M¢ Pallier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2. Giao thùc trëi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.3. Giao thùc vectì trëi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3. Giao thùc t½ch væ h÷îng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.4. Giao thùc h¼nh håc hai b¶n an to n . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.1. Giao thùc chùa iºm hai b¶n an to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.4.2. Giao thùc giao nhau hai b¶n an to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Ch÷ìng 3. Mët sè v½ dö giao thùc t½nh to¡n h¼nh håc a b¶n an to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1. Mët sè v½ dö m¢ çng c§u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 45 3.1.1. V½ dö m¢ Pallier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.2. V½ dö giao thùc kiºm tra b¬ng nhau ri¶ng t÷ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1.3. V½ dö giao thùc trëi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.1.4. V½ dö giao thùc vectì trëi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.1.5. Giao thùc truy·n khæng bi¸t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 1 3.2. V½ dö giao thùc t½ch væ h÷îng . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.1. V½ dö giao thùc t½ch væ h÷îng hai b¶n an to n 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2.2. V½ dö giao thùc ho¡n và . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2.3. V½ dö giao thùc t½ch væ h÷îng hai b¶n an to n 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.3. V½ dö b i to¡n chùa iºm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.4. V½ dö b i to¡n giao cõa hai a gi¡c . . . . . . . . . . . . . . . . . . . . . . . 60 3.5. ¡nh gi¡ t½nh an to n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Danh möc t i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2 LÍI MÐ †U 1. L½ do chån · t i Trong cuëc sèng ng y nay, nhu c¦u trao êi thæng tin, dú li»u giúa c¡c cì quan, tê chùc, cæng ty,. . . luæn ái häi ng y c ng cao, ch½nh v¼ vªy vi»c giú b½ mªt c¡c thæng tin l  mët trong nhúng v§n · quan trång h ng ¦u, khi thüc hi»n k¸t nèi m¤ng nëi bë cõa c¡c cì quan, tê chùc, cæng ty vîi Internet,. . . Ng y nay, c¡c bi»n ph¡p an to n thæng tin cho m¡y t½nh c¡ nh¥n công nh÷ c¡c m¤ng nëi bë ¢ ÷ñc nghi¶n cùu v  triºn khai. Tuy nhi¶n, v¨n th÷íng xuy¶n câ c¡c m¤ng bà t§n cæng, câ c¡c tê chùc bà ¡nh c­p thæng tin, g¥y n¶n nhúng hªu qu£ væ còng nghi¶m trång, khi â ái häi nhúng ng÷íi tham gia giú b½ mªt ph£i thªt sü tin t÷ðng v o nhau, mët quy¸t ành cõa ng÷íi n y công ph£i l  sü quy¸t ành cõa t§t c£ nhúng ng÷íi tham gia. Hi»n nay ¢ câ nhi·u bi»n ph¡p nh¬m n¥ng cao b£o mªt v  an to n thæng tin nh¬m phöc vö cho nhu c¦u v  möc ½ch cõa con ng÷íi trong vi»c giú b½ mªt, giao thùc chia s´ b½ mªt l  mët trong nhúng bi»n ph¡p giú b½ mªt ÷ñc £m b£o an to n. Bði trong chia s´ b½ mªt th¼ thæng tin quan trång khæng giao cho mët ng÷íi n­m giú, m  thæng tin â ÷ñc chia th nh nhi·u m£nh, trao cho méi ng÷íi giú mët m£nh hay mët sè m£nh, thæng tin quan trång ch¿ ÷ñc xem l¤i, khi tªp nhúng ng÷íi ÷ñc ch¿ ành tr÷îc ·u nh§t tr½. V¼ vªy m  mët ng÷íi tham gia giú b½ mªt cõa ri¶ng m¼nh v  khæng thº bi¸t ÷ñc b½ mªt cõa ng÷íi kh¡c. Do â nâ £m b£o vi»c t½nh to¡n a b¶n ÷ñc an to n. Giao thùc trong t½nh to¡n h¼nh håc a b¶n an to n l  mët l¾nh vüc mîi m´ cõa an to n b£o mªt thæng tin, nh÷ng hùa hµn s³ mang ¸n nhúng ùng döng rëng kh­p ð t§t c£ c¡c l¾nh vüc, c¡c ng nh ngh· c¦n £m b£o giú b½ mªt. Ch¯ng h¤n, mët ng÷íi câ mët iºm v  ng÷íi kia câ mët a gi¡c lçi, hai ng÷íi c¦n xem iºm â câ n¬m trong a gi¡c lçi khæng, m  khæng b¶n n o ti¸t lë thæng tin cõa m¼nh cho b¶n kia. B i to¡n â thuëc l¾nh vüc t½nh to¡n h¼nh håc a b¶n an to n. ÷ñc sü gñi þ cõa TS. Tr¦n V«n Dông h÷îng d¨n v  nhªn th§y t½nh thi¸t thüc cõa v§n · em ¢ chån · t i Nghi¶n cùu mët sè giao thùc trong t½nh to¡n h¼nh håc a b¶n an to n º l m nëi dung cho luªn v«n. 2. Möc ½ch nghi¶n cùu L m th¸ n o º chia s´ ÷ñc thæng tin mªt düa tr¶n c¡c thuªt to¡n v  c¡c giao thùc t½nh to¡n a b¶n an to n nâi chung v  trong l¾nh vüc h¼nh håc nâi ri¶ng. 3. Nhi»m vö nghi¶n cùu Nghi¶n cùu cì sð lþ thuy¸t v  mët sè giao thùc t½nh to¡n trong h¼nh håc a b¶n an to n, cö thº ÷a ra gi£i ph¡p cho c¡c b i to¡n chùa iºm, giao hai a gi¡c lçi, t¼m c°p iºm g¦n nh§t (vîi méi tªp iºm thuëc v· mët b¶n), t¼m bao lçi chung. 4. èi t÷ñng v  ph¤m vi nghi¶n cùu èi t÷ñng nghi¶n cùu Nghi¶n cùu c¡c giao thùc trong t½nh to¡n h¼nh håc a b¶n an to n v  ùng döng Ph¤m vi nghi¶n cùu Nghi¶n cùu tr¶n cì sð to¡n håc v  tr÷íng sè modulo, c¡c giao thùc 4 t½nh to¡n a b¶n an to n v  c¡c v½ dö minh ho¤. 5. Ph÷ìng ph¡p nghi¶n cùu Nghi¶n cùu lþ thuy¸t, k¸t hñp vîi c¡c gi£i ph¡p thüc t¸ v  ¡p döng v o thüc ti¹n cuëc sèng. 6. Dü ki¸n âng gâp mîi Têng quan v· cì sð lþ thuy¸t T½nh to¡n h¼nh håc a b¶n an to n v  tr¼nh b y gi£i ph¡p thæng qua c¡c giao thùc v  c¡c t½nh to¡n cö thº vîi sè li»u cõa m¼nh. 5 NËI DUNG Ngo i ph¦n mð ¦u, k¸t luªn v  t i li»u tham kh£o. Luªn v«n ÷ñc chia l m 3 ch÷ìng: Ch÷ìng 1: C¡c ki¸n thùc cì sð. Ch÷ìng 2: Mët sè giao thùc t½nh to¡n h¼nh håc a b¶n an to n Ch÷ìng 3: Mët sè ùng döng t½nh to¡n h¼nh håc a b¶n an to n 6 Ch÷ìng 1 C¡c ki¸n thùc cì sð Ch÷ìng n y s³ tr¼nh b y c¡c l½ thuy¸t º bê trñ v  x¥y düng c¡c giao thùc t½nh to¡n h¼nh håc a b¶n an to n nh÷: modulo, c¡c b i to¡n logarit ríi r¤c, c¡c ành l½ Euler, Fermat; Chú k½ i»n tû DSA, m¢ Elgamal. 1.1. Sè håc Modulo C¡c sè nguy¶n tè v  nguy¶n tè còng nhau Cho sè nguy¶n d÷ìng n, hai sè nguy¶n a, b ÷ñc gåi l  çng d÷ theo mæ-un n n¸u chóng câ còng sè d÷ khi chia cho n. i·u n y t÷ìng ÷ìng vîi hi»u a − b chia h¸t cho n. K½ hi»u a, b çng d÷ theo mæ-un n l : a ≡ b(modn). Quan h» ≡ l  quan h» t÷ìng ÷ìng. V½ dö 1.1. V¼ 21 v  9 khi chia cho 4 ·u cho sè d÷ l  1 n¶n ành ngh¾a 1.1. 21 ≡ 9(mod4). N¸u trong â d÷ cõa a l  sè nguy¶n d÷ìng nhä hìn n, th¼ a ÷ñc gåi l  ph¦n b khi chia cho n, æi khi a ÷ñc gåi l  th°ng d÷ cõa b theo modun n. Tªp hñp c¡c sè nguy¶n tø ho n to n modulo modulo n 0 ¸n n−1 ÷ñc gåi l  tªp hñp th°ng d÷ n. i·u n y câ ngh¾a l  vîi méi sè nguy¶n a, th°ng d÷ l  mët sè d÷ n¬m trong tªp hñp th°ng d÷ ho n to n modulo n. 7 Modulo sè håc công nh÷ sè håc b¼nh th÷íng, bao gçm c¡c ph²p to¡n cëng, nh¥n câ t½nh giao ho¡n, k¸t hñp v  ph¥n phèi. M°t kh¡c, gi£m méi gi¡ trà trung gian trong suèt qu¡ tr¼nh t½nh to¡n b¬ng c¡ch thay c¡c sè b¬ng c¡c sè t÷ìng ÷ìng vîi chóng theo modulo: T½nh ch§t 1.1.1. (a + b) mod n = ((a mod n) + (b mod n)) mod n (a − b) mod n = ((a mod n) − (b mod n)) mod n (a.b) mod n = ((a mod n).(b mod n)) mod n (a.(b + c)) mod n = ((a.b) mod n) + ((a.c) mod n) mod n Sè nguy¶n tè. Sè nguy¶n tè l  sè tü nhi¶n lîn hìn 1, ch¿ câ hai ÷îc sè d÷ìng ph¥n bi»t l  1 v  ch½nh nâ. ành ngh¾a 1.2. V½ dö 1.2. 2, 3, 5, 7, 11, 17, 43, 73, 524287, 2147483647, . . . l  c¡c sè nguy¶n tè. Sè c¡c sè nguy¶n tè l  væ tªn. H» mªt m¢ th÷íng dòng sè nguy¶n tè cï 512 bits v  thªm ch½ lîn hìn vªy. Sè nguy¶n tè còng nhau. Hai sè nguy¶n d÷ìng a, b ÷ñc gåi l  nguy¶n tè còng nhau n¸u ÷îc chung lîn nh§t cõa chóng b¬ng 1. K½ hi»u: Gcd(a, b) = 1 ho°c ng­n gån l  (a, b)=1. ành ngh¾a 1.3. V½ dö 1.3. 21 v  25 l  hai sè nguy¶n tè còng nhau v¼ Gcd(21, 25) = 1. C¡ch d¹ nh§t º t½nh to¡n ra ÷îc sè chung lîn nh§t cõa hai sè l  nhí v o thuªt to¡n Euclid. ành ngh¾a 1.4. Sè nghàch £o modulo. 8 N¸u sè nguy¶n d÷ìng n v  sè nguy¶n a nguy¶n tè còng nhau th¼ tçn t¤i duy nh§t mët sè x ∈ {0, 1, 2, ..., n − 1} sao cho a.x ≡ 1(modn). Sè x n y ÷ñc gåi l  nghàch £o cõa a theo modulo n v  kþ hi»u x = a−1 (modn). Nghàch £o cõa 5 modulo 17 l  7 v¼ 35 ≡ 1(mod17). Vªy 5−1 ≡ 7(mod17). V½ dö 1.4. T½nh ch§t 1.1.2. Sè nghàch £o modulo câ c¡c t½nh ch§t sau * Cho a, b ∈ Zn. Ph²p chia a cho b theo modulo n l  t½ch cõa a v  b−1 theo modulo n v  ch¿ ÷ñc x¡c ành khi b câ nghàch £o theo modulo n. * Cho a ∈ Zn, a l  kh£ nghàch khi v  ch¿ khi gcd(a, n) = 1. * Gi£ sû d = Gcd(a, n). Ph÷ìng tr¼nh çng d÷ ax = b mod n câ nghi»m x, n¸u v  ch¿ n¸u d chia h¸t b, trong tr÷íng hñp c¡c nghi»m n¬m trong kho£ng 0 ¸n n − 1, th¼ c¡c nghi»m çng d÷ theo modulo n . d Cho sè nguy¶n a > 0 nguy¶n tè còng nhau vîi n th¼ luæn tçn t¤i ph¦n tû nghàch £o cõa a theo modulo n. Chùng minh: X²t tªp hñp {1, 2, 3, ..., n − 1} , nh¥n tøng ph¦n tû cõa tªp hñp vîi a theo modulo n, nhªn ÷ñc tªp hñp (a mod n), (2a mod n), (3a mod n), . . . ((n−1)a mod n). Tªp n y s³ gçm c¡c sè: 1, 2, 3, . . . , n−1, câ ngh¾a èi vîi óng mët sè gi¡ trà i n o â s³ thäa m¢n i·u ki»n ia mod n = 1. Vªy ta t¼m ÷ñc i l  ph¦n tû nghàch £o cõa a v  i l  duy nh§t. ành lþ 1.1. 9 N¸u nh÷ p l  sè nguy¶n tè, th¼ b§t ký sè a sao cho 0 < a < p luæn tçn t¤i ph¦n tû nghàch £o theo modulo p. H» qu£ 1.1. V½ dö 1.5. 5.2 ≡ 1(mod9) hay 2 ≡ 5−1 mod 9. ành l½ Fermat. N¸u p l  sè nguy¶n tè v  a l  sè nguy¶n tè còng nhau vîi p th¼ ành lþ 1.2. ap−1 ≡ 1(modp). V½ dö 1.6. 34 ≡ 1 mod 5, 26 mod 7 = 1, 2100 mod 7 = 24 mod 7 = 2. H m Euler. H m Euler t¤i sè nguy¶n d÷ìng n, kþ hi»u ϕ(n) ÷ñc t½nh b¬ng sè c¡c sè nguy¶n tø 1 ¸n n m  nguy¶n tè còng nhau vîi n. ành ngh¾a 1.5. Ta cæng nhªn mët sè t½nh ch§t quan trång cõa h m Euler T½nh ch§t 1: ϕ(1) = 1. T½nh ch§t 2: N¸u p l  sè nguy¶n tè th¼ T½nh ch§t 3: N¸u nh÷ p v  q ϕ(p) = p − 1. l  hai sè nguy¶n tè còng nhau th¼ ϕ(pq) = ϕ(p) . ϕ(q). T½nh ch§t 4: ϕ(ps ) = ps−1 (p − 1). T½nh ch§t 5: N¸u nh÷ n = pe1 pe2 ...pek , 1 2 k ð ¥y p1 , p2 , ..., pk tè th¼ ϕ(n) = n 1 − 1 p1 1− 10 1 p2 ... 1 − 1 pk . l  sè nguy¶n B£ng d÷îi ¥y tr¼nh b y 30 gi¡ trà ¦u ti¶n cõa khæng x¡c ành, nh÷ng coi r¬ng nâ b¬ng Gi¡ trà ϕ(1) l  1. Mët sè gi¡ trà cõa h m Euler ϕ(n) n ϕ(n) n ϕ(n) n ϕ(n) 1 1 11 10 21 12 2 1 12 4 22 10 3 2 13 12 23 22 4 2 14 6 24 8 5 4 15 8 25 20 6 2 16 8 26 12 7 6 17 16 27 18 8 4 18 6 28 12 9 6 19 18 29 28 10 V½ dö 1.7. ϕ(n). 4 20 8 30 8 Theo t½nh ch§t tr¶n ta câ ϕ(7) = 6 ϕ(13) = 12 ϕ(p) = p − 1 ϕ(p.q) = ϕ(p).ϕ(q) v¼ (p, q) = 1 ϕ(pk ) = pk − pk−1 ϕ(8) = 23 − 22 = 4 ϕ(56) = ϕ(7).ϕ(8) = 6.(23 − 22 ) = 24 ành lþ 1.3. (ành lþ Euler) N¸u n l  sè nguy¶n d÷ìng b§t k¼ v  a l  sè nguy¶n tè còng nhau vîi n th¼ aϕ(n) ≡ 1(modn). 11 ¥y l  têng qu¡t hâa cõa ành lþ nhä Fermat, v¼ n¸u n = p l  sè nguy¶n tè th¼ ϕ(p) = p − 1. Chùng minh: Gåi a1, a2, ..., aϕ(n) l  c¡c sè nguy¶n d÷ìng nhä hìn n v  nguy¶n tè còng nhau vîi n. Vîi måi 2 sè ph¥n bi»t i, j ∈ {1, 2, ..., ϕ(n)}, (ai, n) = (aj , n) = 1, (aai , n) = (aaj , n) = 1; aai = aaj (modn). Do vªy, aa1, aa2, ..., aaϕ(n) l  mët ho¡n và theo mæ-un n cõa aa1, aa2, ..., aaϕ(n) . Suy ra a1 a2 ...aϕ(n) ≡ (aa1 )(aa2 )...(aaϕ(n) ) ≡ aϕ(n) a1 a2 ...aϕ(n) (modn). Gi£n ÷îc çng d÷ thùc ta câ: aϕ(n) ≡ 1(modn) (pcm). ành lþ n y câ thº ÷ñc sû döng º d¹ d ng gi£n ÷îc vîi mæun n r§t lîn. ành lþ Euler công l  ành lþ cì b£n cõa c¡c h» thèng m¢ hâa RSA. V½ dö 1.8. a = 3, n = 10, ϕ(10) = 4, 34 = 81 ≡ 1(mod10), a = 2, n = 11, ϕ(11) = 10, 210 = 1024 ≡ 1(mod11). V½ dö 1.9. T¼m chú sè tªn còng cõa sè 7222. Ta câ 7222 ≡ 74.55+2 ≡ 74 55.72 ≡ 155.72 ≡ 49 ≡ 9(mod10). Vªy 7222 câ chú sè tªn còng l  9. Bê · 1.1. Bê · Bezout: N¸u d l  ÷îc chung lîn nh§t cõa hai sè nguy¶n a, b th¼ s³ tçn t¤i 2 sè nguy¶n x, y sao cho d = ax + by 12 ành lþ ph¦n d÷ Trung Hoa ành lþ ph¦n d÷ trung hoa l  t¶n ng÷íi ph÷ìng t¥y °t cho ành lþ n y. Ng÷íi Trung Quèc gåi â l  b i to¡n H n T½n iºm binh. Töc truy·n r¬ng khi H n T½n iºm qu¥n sè, æng cho qu¥n l½nh x¸p h ng 3, h ng 5, h ng 7, rçi b¡o c¡o sè d÷. Tø â æng t½nh ÷ñc ch½nh x¡c qu¥n sè ¸n tøng ng÷íi. ành lþ ph¦n d÷ Trung Hoa ÷ñc ph¡t biºu nh÷ sau: Cho n ≥ 2, m1, m2, ..., mn l  nhúng sè nguy¶n d÷ìng kh¡c 0, æi mët nguy¶n tè còng nhau v  a1 , a2 , ..., an l  n sè nguy¶n b§t ký. Khi â h» ph÷ìng tr¼nh çng d÷ x ≡ ai(modmn) câ nghi»m v  nghi»m n y duy nh§t theo mæ-un M = m1.m2....mn. ành lþ 1.4. Chùng minh: Câ hai v§n · c¦n chùng minh: Tr÷îc ti¶n l  sü tçn t¤i nghi»m cõa b i to¡n v  sau â l  chùng minh t½nh duy nh§t cõa nghi»m. B¥y gií chóng ta chùng minh sü tçn t¤i nghi»m v  t½nh duy nh§t nghi»m. Theo lþ thuy¸t çng d÷ tçn t¤i u v  v sao cho x = a1 + m1 u, x = a2 + m2 v. Do vªy ta ch¿ c¦n chån u, v thäa m¢n: a1 − a2 = m2 v − m1 u, hiºn nhi¶n theo bê · Berzout ð tr¶n. Nh÷ vªy tçn t¤i x i·u n y thäa m¢n h» ph÷ìng tr¼nh çng d÷ tr¶n. B¥y gií ta s³ chùng minh t½nh duy nh§t cõa nghi»m. Thªt vªy, gi£ sû x, x l  2 nghi»m cõa h» ph÷ìng tr¼nh ¢ cho ta câ x ≡ x (modmi ), ∀i = 1, ...n. 13 Do æi mët nguy¶n tè còng nhau n¶n ta ph£i câ x ≡ x (modm1 ...mn ). Ta kh¯ng ành ÷ñc t½nh duy nh§t cõa nghi»m theo mod V½ dö 1.10. m1 .m2 ...mn . Gi£i h» ph÷ìng tr¼nh çng d÷:   x ≡ 2(mod3)    x ≡ 3(mod5)     x ≡ 5(mod7) Gi£i: Ta câ M = 3.5.7 = 105 M1 = 5.7 = 35 M2 = 3.7 = 21 M3 = 3.5 = 15 Tø â, y1 = 35−1 (mod3) = 2−1 (mod3) = 2 y2 = 21−1 (mod5) = 1−1 (mod5) = 1 y3 = 15−1 (mod7) = 1−1 (mod7) = 1 D¨n ¸n x ≡ 2.35.2 + 3.21.1 + 5.15.1(mod105) x ≡ 140 + 63 + 75(mod105) x ≡ 278(mod105) x ≡ 68(mod105). Nh÷ vªy x câ d¤ng: x = 68 + 105k (k l  mët sè nguy¶n b§t ký). C«n nguy¶n thu v  logarit ríi r¤c ành ngh¾a 1.6. (C§p cõa mët sè nguy¶n) 14 Cho n > 1 v  a l  mët sè nguy¶n d÷ìng, (a, n) = 1. Sè nguy¶n d÷ìng k nhä nh§t thäa m¢n ak ≡ 1(modn) ÷ñc gåi l  c§p cõa a modulo n. K½ hi»u k = ordn(a). V½ dö 1.11. : a = 3, n = 10 câ 34 ≡ 1(mod10). Vªy 4 = ord10(3). ành ngh¾a 1.7. (C«n nguy¶n thõy) Cho n > 1 v  a l  mët sè nguy¶n d÷ìng: (a, n) = 1. N¸u ϕ(n) = ordn(a) th¼ a ÷ñc gåi l  mët c«n nguy¶n thõy modulo n. V½ dö 1.12. 4 = ord10 (3) 3 l  mët c«n nguy¶n thõy modulo 10 v¼ (3, 10) = 1, ϕ(10) = n¶n 3 l  mët c«n nguy¶n thõy modulo 10. Ta câ c¡c t½nh ch§t sau T½nh ch§t 1: N¸u a l  c«n nguy¶n thõy (modn) th¼ måi sè còng lîp vîi a theo (modn) ·u l  c«n nguy¶n thõy (modn). T½nh ch§t 2: N¸u a l  c«n nguy¶n thõy ( mod n) th¼ tªp A = 1, a, a2, ..., ah−1 l  h» th°ng d÷ thu gån (modn) (lóc n y h = ϕ(n)). T½nh ch§t 3: N¸u p l  mët sè nguy¶n tè th¼ câ óng ϕ(p − 1) c«n nguy¶n thõy (modp). T½nh ch§t 4: N¸u p l  mët sè nguy¶n tè l´ v  a l  mët c«n nguy¶n thõy (modp2 ) th¼ a công l  c«n nguy¶n thõy (modpn ) vîi n ≥ 3. T½nh ch§t 5: Cho m l  mët sè nguy¶n, m > 1 khi â m câ c«n nguy¶n thõy khi v  ch¿ khi m câ mët trong 4 d¤ng sau: 2, 4, pα, 2pα (trong â p l  mët sè nguy¶n tè l´). T½nh ch§t 1.1.3. Logarit ríi r¤c Ta nh­c l¤i r¬ng vîi hai sè thüc th¼ x ÷ñc gåi l  logarit cì sè a x, y cõa y, 15 v  cì sè a > 0, a = 1, n¸u ax = y kþ hi»u x = loga y . Logarit ríi r¤c câ ùng döng trong h» mªt m¢ khâa cæng khai H» mªt m¢ Elgamal. Cho p l  mët sè nguy¶n tè. X²t nhâm nh¥n c¡c sè nguy¶n modulo ∗ Zp = {1, 2, ..., p} vîi ph²p nh¥n modulo k N¸u ta t½nh luÿ thøa bªc modulo p p: p. cõa mët sè trong nhâm rçi rót gån theo th¼ ta ÷ñc mët sè trong nhâm â. Qu¡ tr¼nh n y ÷ñc gåi l  luÿ thøa ríi r¤c modulo Ch¯ng h¤n vîi p. p = 17 a = 3, k = 4 l§y ta câ 34 = 81 ≡ 13(mod17). Logarit ríi r¤c l  ph²p t½nh ng÷ñc l¤i. Bi¸t: 3k ≡ 13(mod17) k. h¢y t¼m º gi£i chóng ta ph£i thæng qua ph²p thû l¦n l÷ñt t½nh lôy thøa ríi r¤c, ch¯ng h¤n t½nh v  t¼m ÷ñc 32 ≡ 9(mod17), 33 ≡ 10(mod17), 34 ≡ 13(mod17) k = 4. Nh÷ vªy b i to¡n logarit ríi r¤c l  b i to¡n khâ. 1.2. Chú k½ i»n tû DSA Chú kþ i»n tû ÷ñc sû döng trong c¡c giao dàch i»n tû. Xu§t ph¡t tø thüc t¸, chú kþ i»n tû công c¦n £m b£o c¡c chùc n«ng: x¡c ành ÷ñc ng÷íi chõ cõa mët dú li»u n o â: v«n b£n, £nh, video,... dú li»u â câ bà thay êi hay khæng. 1. Chån sè nguy¶n tè 160 bit q. L bit 2. Chån mët sè nguy¶n tè n o â, 512 ≤ L ≤ 1024 , L • Chån sè ng¨u nhi¶n • Chån x h, vîi p, sao cho chia h¸t cho 0 < x < q. 16 vîi sè nguy¶n 64. 1 < h < p − 1, ng¨u nhi¶n, tho£ m¢n p = qz + 1 t½nh g sao cho g=h p−1 q . z