Tài liệu Giáo trình mật mã và ứng dụng chương 4

  • Số trang: 58 |
  • Loại file: PDF |
  • Lượt xem: 129 |
  • Lượt tải: 0
tranphuong

Đã đăng 59174 tài liệu

Mô tả:

Ch−¬ng 4 HÖ mËt RSA vµ vÊn ®Ò ph©n tÝch thõa sè 4.1. Giíi thiÖu vÒ hÖ mËt kho¸ c«ng khai Trong m« h×nh mËt m cæ ®iÓn tr−íc ®©y mµ hiÖn nay ®ang ®−îc nghiªn cøu Alice (ng−êi göi) vµ Bob (ng−êi nhËn) chän mét c¸ch bÝ mËt kho¸ K. Sau ®ã dïng K ®Ó t¹o luËt m ho¸ ekvµ luËt gi¶i m dk. Trong hÖ mËt nµy dk hoÆc gièng nh− ek hoÆc dÔ dµng nhËn ®−îc tõ nã (vÝ dô trong hÖ DES qu¸ tr×nh gi¶i m hoµn toµn t−¬ng tù nh− qu¸ tr×nh m nh−ng thñ tôc kho¸ ng−îc l¹i). C¸c hÖ mËt thuéc lo¹i nµy ®−îc gäi lµ hÖ mËt kho¸ bÝ mËt, nÕu ®Ó lé ek th× lµm cho hÖ thèng mÊt an toµn. Nh−îc ®iÓm cña hÖ mËt nµy lµ nã yªu cÇu ph¶i cã th«ng tin tr−íc vÒ kho¸ K gi÷a Alice vµ Bob qua mét kªnh an toµn tr−íc khi göi mét b¶n m bÊt kú. Trªn thùc tÕ ®iÒu nµy rÊt khã ®¶m b¶o. Ch¼ng h¹n khi Alice vµ Bob ë c¸ch xa nhau vµ hä chØ cã thÓ liªn l¹c víi nhau b»ng th− tÝn ®iÖn tö (Email). Trong t×nh huèng ®ã Alice vµ Bob kh«ng thÓ t¹o mét kªnh b¶o mËt víi gi¸ ph¶i ch¨ng. ý t−ëng x©y dùng mét hÖ mËt kho¸ c«ng khai (hay kho¸ dïng chung) lµ t×m mét hÖ mËt kh«ng cã kh¶ n¨ng tÝnh to¸n ®Ó x¸c ®Þnh dkkhi biÕt ek. NÕu thùc hiÖn ®−îc nh− vËy th× quy t¾c m ek cã thÓ ®−îc c«ng khai b»ng c¸ch c«ng bè nã trong mét danh b¹ (bëi vËy nªn cã thuËt ng÷ hÖ mËt kho¸ c«ng khai). ¦u ®iÓm cña hÖ mËt kho¸ c«ng khai lµ ë chç Alice (hoÆc bÊt k× mét ai) cã thÓ göi mét b¶n tin ® m cho Bob (mµ kh«ng cÇn th«ng tin tr−íc vÒ kho¸ mËt) b»ng c¸ch dïng luËt m c«ng khai ek. Ng−êi nhËn A sÏ lµ ng−êi duy nhÊt cã thÓ gi¶i ®−îc b¶n m nµy b»ng c¸ch sö dông luËt gi¶i m bÝ mËt dk cña m×nh. Cã thÓ h×nh dung hÖ mËt nµy t−¬ng tù nh− sau. Alice ®Æt mét vËt vµo mét hép kim lo¹i vµ råi kho¸ nã l¹i b»ng mét kho¸ sè do Bob ®Ó l¹i. ChØ cã Bob lµ ng−êi duy nhÊt cã thÓ më ®−îc hép v× chØ cã anh ta míi biÕt tæ hîp m cña kho¸ sè cña m×nh. ý t−ëng vÒ mét hÖ mËt kho¸ c«ng khai ® ®ùoc Diffie vµ Hellman ®−a ra vµo n¨m 1976. Cßn viÖc hiÖn thùc ho¸ nã th× do Rivesrt, Shamir vµ Adleman ®−a ra ®Çu tiªn vµo n¨m 1977, hä ® t¹o nªn hÖ mËt næi tiÕng RSA (sÏ ®−îc nghiªn cøu trong ch−¬ng nµy). KÓ tõ ®ã mét sè hÖ ®−îc c«ng bè, ®é mËt cña chóng dùa trªn c¸c bµi to¸n tÝnh to¸n kh¸c nhau. Sau ®©y lµ c¸c hÖ mËt kho¸ c«ng khai quan träng : + HÖ mËt RSA: §é b¶o mËt cña hÖ RSA dùa trªn ®é khã cña viÖc ph©n tÝch ra thõa sè nguyªn tè c¸c sè nguyªn lín. HÖ nµy sÏ ®−îc m« t¶ trong phÇn 4.3. + HÖ mËt xÕp ba l« Merkle - Hellman: HÖ nµy vµ c¸c hÖ liªn quan dùa trªn tÝnh khã gi¶i cña bµi to¸n tæng c¸c tËp con (bµi to¸n nµy lµ bµi to¸n NP ®Çy ®ñ – lµ mét líp kh¸ lín c¸c bµi to¸n kh«ng cã thuËt gi¶i ®−îc biÕt trong thêi gian ®a thøc). Tuy nhiªn tÊt c¶ c¸c hÖ mËt xÕp ba l« kh¸c nhau ®Òu ® bÞ chøng tá lµ kh«ng mËt (ngo¹i trõ hÖ mËt Chor – Rivest sÏ ®−îc nªu d−íi ®©y). HÖ mËt nµy ®−îc xÐt ë ch−¬ng 5. + HÖ mËt McEliece: HÖ nµy dùa trªn lý thuyÕt m ®¹i sè vµ vÉn cßn ®−îc coi lµ an toµn. HÖ mËt McEliece dùa trªn bµi to¸n gi¶i m cho c¸c m tuyÕn tÝnh (còng lµ mét bµi to¸n NP ®Çy ®ñ). HÖ mËt McEliece ®−îc tr×nh bµy ë ch−¬ng 5. + HÖ mËt Elgamal: HÖ mËt Elgamal dùa trªn tÝnh khã gi¶i cña bµi to¸n logarithm rêi r¹c trªn c¸c tr−êng h÷u h¹n (xem trong ch−¬ng 5). + HÖ mËt Chor - Rivest: HÖ mËt Chor - Rivest còng ®−îc xem nh− mét lo¹i hÖ mËt xÕp ba l«. Tuy nhiªn nã vÉn ®−îc coi lµ an toµn. + HÖ mËt trªn c¸c ®−êng cong Elliptic C¸c hÖ mËt nµy lµ biÕn t−íng c¶u c¸c hÖ mËt kh¸c (ch¼ng h¹n nh− hÖ mËt Elgamal) , chóng lµm viÖc trªn c¸c ®−êng cong Elliptic chø kh«ng ph¶i lµ trªn c¸c tr−êng h÷u h¹n. HÖ mËt nµy ®¶m b¶o ®é mËt víi kho¸ sè nhá h¬n c¸c hÖ mËt kho¸ c«ng khai kh¸c (xem ch−¬ng 5). Mét chó ý quan träng lµ mét hÖ mËt kho¸ c«ng khai kh«ng bao giê cã thÓ ®¶m b¶o ®−îc ®é mËt tuyÖt ®èi (an toµn v« ®iÒu kiÖn). Së dÜ nh− vËy v× ®èi ph−¬ng khi nghiªn cøu mét b¶n m y cã thÓ m lÇn l−ît c¸c b¶n râ b»ng luËt m c«ng khai ek cho tíi khi anh ta t×m ®−îc b¶n râ duy nhÊt x ®¶m b¶o y = ek (x). B¶n râ nµy chÝnh lµ kÕt qu¶ gi¶i m cña y. Bëi vËy ta chØ nghiªn cøu ®é mËt vÒ mÆt tÝnh to¸n cña c¸c hÖ mËt nµy. Mét kh¸i niÖm cã Ých khi nghiªn cøu hÖ mËt kho¸ c«ng khai lµ kh¸i niÖm vÒ hµm cöa sËp mét chiÒu. Ta ®Þnh nghÜa kh¸i niÖm nµy mét c¸ch kh«ng h×nh thøc. Hµm m kho¸ c«ng khai ek cña Bob ph¶i lµ mét hµm dÔ tÝnh to¸n. Song viÖc t×m hµm ng−îc (hµm gi¶i m ) ph¶i rÊt khã kh¨n (®èi víi bÊt kú ai kh«ng ph¶i lµ Bob). §Æc tÝnh dÔ tÝnh to¸n nh−ng khã tÝnh to¸n hµm ng−îc th−êng ®−îc gäi lµ ®Æc tÝnh mét chiÒu. Bëi vËy ®iÒu kiÖn c©n thiÕt lµ ek ph¶i lµ hµm mét chiÒu. C¸c hµm mét chiÒu ®ãng vai trß quan träng trong mËt m häc: chóng rÊt quan trong c¸c hÖ mËt kho¸ c«ng khai vµ trong nhiÒu lÜnh vùc kh¸c. §¸ng tiÕc lµ mÆc dï cã rts nhiÒu hµm ®−îc coi lµ hµm mét chiÒu nh−ng cho tíi nay vÉn kh«ng tån t¹i mét hµm nµo cã thÓ chøng minh ®−îc lµ hµm mét chiÒu. Sau ®©y lµ mét vÝ dô vÒ mét hµm ®−îc coi lµ hµm mét chiÒu. Gi¶ sö n lµ tÝch cña hai sè nguyªn tè lín p vµ q, gi¶ sö b lµ mét sè nguyªn d−¬ng. Khi ®ã ta x¸c ®Þnh ¸nh x¹ f : Zn  Zn lµ f(x) = xb mod n (víi b vµ n ® ®−îc chän thÝch hîp th× ®©y chÝnh lµ hµm m RSA, sau nµy sÏ cßn nãi nhiÒu vÒ nã). §Ó x©y dùng mét hÖ mËt kho¸ c«ng khai th× viÖc t×m ®−îc mét hµm mét chiÒu vÉn ch−a ®ñ. Ta kh«ng muèn ek lµ hµm mét chiÒu ®èi víi Bob v× anh ta ph¶i cã kh¶ n¨ng gi¶i m c¸c b¶n tin nhËn ®−îc mét c¸ch hiÖu qu¶. §iÒu cÇn thiÕt lµ Bob ph¶i cã mét cöa sËp chøa th«ng tin bÝ mËt cho phÐp dÔ dµng t×m hµm ng−îc cña ek. Nh− vËy Bob cã thÓ gi¶i m mét c¸ch h÷u hiÖu v× anh ta cã mét hiÓu biÕt tuyÖt mËt nµo ®ã vÒ K. Bëi vËy mét hµm ®−îc gäi lµ cöa sËp mét chiÒu nÕu nã lµ hµm mét chiÒu vµ nã trë nªn dÔ tÝnh ng−îc nÕu biÕt mét cöa sËp mhÊt ®Þnh. Ta sÏ xÐt c¸ch t×m mét cöa sËp ®èi víi hµm f nªu ë trªn trong phÇn 4.3. C¸c t×m nµy sÏ dÉn ®Õn hÖ mËt RSA. 4.2. mét sè vÊn ®Ò s©u h¬n vÒ lý thuyÕt sè Tr−íc khi m« t¶ hÖ mËt RSA lµm viÖc ra sao cÇn ph¶i xem xÐt mét sè yÕu tè liªn quan ®Õn lý thuyÕt sè vµ sè häc modulo. Hai kÕt qu¶ cÇn biÕt lµ thuËt to¸n Euclide vµ ®Þnh lý phÇn d− China. 4.2.1 ThuËt to¸n Euclide Trong ch−¬ng 1 ® xÐt Zn lµ mét vµnh víi sè nguyªn d−¬ng bÊt kú n. Ta còng ® chøng tá r»ng phÇn tö b ∈ Zn cã phÇn tö nghÞch ®¶o (phÇn tö ng−îc cña phÐp nh©n) khi vµ chØ khi −CLN(b,n) = 1 vµ c¸c sè nguyªn d−¬ng nhá h¬n n vµ nguyªn tè cïng nhau víi n b»ng φ (n). TËp c¸c thÆng d− theo modulo n vµ nguyªn tè cïng nhau víi n ®−îc ký hiÖu lµ Zn* .Kh«ng khã kh¨n cã thÓ thÊy r»ng Zn* sÏ t¹o nªn mét nhãm Abel ®èi víi phÐp nh©n. Ta còng biÕt r»ng, phÐp nh©n theo modulo n lµ giao ho¸n vµ kÕt hîp vµ phÇn tö ®¬n vÞ lµ 1. Mét phÇn tö bÊt kú trong Zn*®Òu cã nghÞch ®¶o béi (còng n»m trong Zn*). Cuèi cïng Zn* lµ ®ãng ®èi víi phÐp nh©n v× xy lµ nguyªn tè cïng nhau víi n khi x vµ y nguyªn tè cïng nhau víi n. (H y chøng minh ®iÒu nµy!) Cho tíi b©y giê ta chØ biÕt r»ng mét phÇn tö b bÊt k× ∈ Zn* ®Òu cã nghÞch ®¶o b-1 song viÖc tÝnh nã vÉn ch−a nãi ®Õn. Mét thuËt to¸n nh− vËy ®−îc gäi lµ thuËt to¸n Euclide më réng. Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Euclide, th«ng th−êng thuËt to¸n nµy ®−îc dïng ®Ó tÝnh −íc sè chung lín nhÊt (−CLN) cña hai sè nguyªn d−¬ng r0 vµ r1 víi r0 > r1.ThuËt to¸n Euclide bao gåm viÖc thùc hiÖn c¸c phÐp to¸n nh− sau: r0 = q1 r1 +r2 r1 = q2 r2 +r3 . . rm -2 = qm -1 rm -1 +rm rm -1 = qm rm 0 < r2 < r1 0 < r3 < r2 0 < rm -1 < rm Khi ®ã dÔ dµng chøng tá ®−îc r»ng −CLN(r0 , r1 ) = −CLN(r1 , r2 ) = . . . −CLN(rm-1 , rm ) = rm Bëi vËy −CLN(r0 , r1 ) = rm V× thuËt to¸n Euclide tÝnh c¸c −CLN nªn cã thÓ ¸p dông nã ®Ó x¸c ®Þnh xem liÖu mét sè nguyªn d−¬ng b < n cã nghÞch ®¶o theo modulo n kh«ng b»ng c¸ch b¾t ®Çu víi r0 = n vµ r1 = b. Tuy nhiªn thuËt to¸n nµy kh«ng cho phÐp tÝnh gi¸ trÞ cña phÇn tö nghÞch ®¶o (nÕu nã tån t¹i). B©y giê gi¶ sö ®Þnh nghÜa mét d y sè t0 , t1 ,.... ,tm theo c¸c c«ng thøc truy to¸n sau (trong ®ã c¸c gi¸ trÞ qj ® ®−îc x¸c ®Þnh ë trªn) t0 = 0 t1 = 1 tj = tj-2- qj-1 tj-1 mod r0 nÕu j ≥ 2 Ta cã kÕt qu¶ quan träng sau §Þnh lý 4.1. Víi 0 ≤ j ≤ m, ta cã rj ≡ tjr1 (mod r0), trong ®ã c¸c gi¸ trÞ qj vµ rj ®−îc x¸c ®Þnh theo thuËt to¸n Euclide cßn c¸c gi¸ trÞ tj ®−îc x¸c ®Þnh theo c«ng thøc truy to¸n ë trªn. Chøng minh: Ta chøng minh b»ng c¸ch quy n¹p theo j. §Þnh lý hiÓn nhiªn ®óng víi j = 0 vµ j = 1. Gi¶ sö ®Þnh lý còng ®óng víi j = i-1 vµ j = i-2, trong ®ã i ≥ 2; sau ®©y ta sÏ chøng tá ®Þnh lý ®óng víi j = i. Theo quy n¹p ta cã vµ B©y giê ta tÝnh ri-2 ≡ ti-2 r1 (mod r0) ri-1 ≡ ti-1 r1 (mod r0) ri = ri-2 - qi-1 ri-1 ≡ ti-2 r1 - qi-1 ti-1 r1 (mod r0) ≡ (ti-2 - qi-1 ti-1)r1 (mod r0) ≡ ti r1 (mod r0) Bëi vËy theo quy n¹p ®Þnh lý lµ ®óng. HÖ qu¶ rót ra trùc tiÕp tõ ®Þnh lý trªn. HÖ qu¶ 4.2: Gi¶ sö −CLN (r0,r1) = 1, khi ®ã tm = r1-1 mod r0. H×n 2.1 ThuËt to¸n Euclide më réng: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. n0 = n b0 = b t0 = 0 t=1 q = n0 /b0 r = n0 - q×b0 While r > 0 do temp = t0 -q×t if temp ≥ 0 then temp = temp mod n if temp < 0 then temp = n - ((- temp) mod n) t0 = t t = temp n0 = b 0 b0 = r q = n0 /b0 r = n0 - q×b0 if b0 ≠ 1 then b kh«ng cã nghÞch ®¶o theo modulo n -1 else b = t mod n . XÐt thÊy d y c¸c sè t0, t1, . . . , tm cã thÓ ®−îc tÝnh to¸n trong thuËt to¸n Euclide ®ång thêi nh− c¸c gi¸ trÞ qj vµ rj. H×nh 4.1 tr×nh bµy thuËt to¸n Euclide më réng ®Ó tÝnh nghÞch ®¶o cña b theo modulo n (nÕu nã tån t¹i). Trong thuËt to¸n nµy kh«ng ph¶i dïng m¶ng (array) ®Ó ghi c¸c gi¸ trÞ qj, rj vµ tj v× chØ cÇn nhí hai gi¸ trÞ cuèi cïng trong mçi d y nµy ë mét ®iÓm bÊt k× trong thuËt to¸n. Trong b−íc 10 cña thuËt to¸n ta ® viÕt biÓu thøc cho biÕn temp theo c¸ch ®Ó phÐp rót gän theo modulo n ®−îc thùc hiÖn ®èi víi sè d−¬ng. (Tr−íc ®©y ® biÕt r»ng viÖc rót gän theo modulo cña c¸c sè ©m sÏ dÉn ®Õn c¸c kÕt qu¶ ©m ë nhiªï ng«n ng÷ m¸y tÝnh; cßn ë ®©y ta muèn kÕt thóc víi kÕt qu¶ d−¬ng). ë b−íc 12 lu«n cã tb ≡ r (mod n) (kÕt qu¶ nµy ® ®−îc chøng minh ë ®Þnh lý 4.1). Sau ®©y lµ mét vÝ dô nhá ®Ó minh ho¹ VÝ dô 4.1. Gi¶ sö ta cÇn tÝnh 28-1 mod 75. ThuËt to¸n Euclide më réng thùc hiÖn nh− sau: 75 = 2 × 28 +29 73 × 28 mod 75 = 19 28 = 1 × 19 + 9 3 × 28 mod 75 = 9 19 = 2 × 9 + 1 67 × 28 mod 75 = 1 9=9×1 b−íc 6 b−íc 12 b−íc 16 b−íc 12 b−íc 16 b−íc 12 b−íc 16 V× thÕ 28-1 mod 75 = 67. 4.2.2. §Þnh lý phÇn d− China §Þnh lý nµy thùc sù lµ mét ph−¬ng ph¸p gi¶i c¸c hÖ ph−¬ng tr×nh ®ång d−. Gi¶ sö m1, . . . , mr lµ c¸c sè nguyªn tè cïng nhau tõng ®«i mét (tøc −CLN(mi,mj)=1 nÕu j≠i). Gi¶ sö a1,. . ., ar lµ c¸c sè nguyªn xÐt hÖ ph−¬ng tr×nh ®ång d− sau: x ≡ a1 (mod m1) x ≡ a2 (mod m2) . . x ≡ ar (mod mr) §Þnh lý phÇn d− China kh¼ng ®Þnh r»ng hÖ nµy cã nghiÖm duy nhÊt theo modulo M = m1×m2×. . . ×mr. Ta sÏ chøng minh kÕt qu¶ ®ã trong phÇn nµy vµ còng m« t¶ mét thuËt to¸n h÷u hiÖu ®Ó gi¶i hÖ ®ång d− thøc d¹ng trªn. §Ó thuËn tiÖn, xÐt hµm π : ZM  Zm1× . . .×Zmr. Hµm nµy ®−îc ®Þnh nghÜa nh− sau: π(x) = (x mod m1, . . . , x mod mr ) VÝ dô 4.2 Gi¶ sö r = 2, m1 = 5 vµ m2 = 3, bëi vËy M = 15. Khi ®ã hµm π cã gi¸ trÞ sau π(0) = (0,0) π(3) = (3,0) π(6) = (1,0) π(9) = (4,0) π(12) =(2,0) π(1) = (1,1) π(4) = (4,1) π(7) = (2,1) π(10) =(0,1) π(13) =(3,1) π(2) = (2,2) π(5) = (0,2) π(8) = (3,2) π(11) =(1,2) π(14) =(4,2) ViÖc chøng minh ®Þnh lý phÇn d− China t−¬ng ®−¬ng víi viÖc chøng minh r»ng hµm π lµ mét song ¸nh. §iÒu nµy cã thÓ dÔ dµng thÊy ®−îc ë vÝ dô 4.2. Trong thùc tÕ cã thÓ ®−a ra mét c«ng thøc t−êng minh tæng qu¸t cho hµm ng−îc π-1. Víi 1 ≤ i ≤ r, ®Þnh nghÜa: Mi = M/mi Khi ®ã, dÔ dµng thÊy r»ng −CLN(Mi,mi) = 1 víi 1 ≤ i ≤ r. TiÕp theo, víi 1 ≤ i ≤ r, ®Þnh nghÜa yi = Mi-1 mod mi (phÇn tö nghÞch ®¶o nµy tån t¹i do −CLN(Mi,mi) = 1 vµ cã thÓ t×m ®−îc b»ng thuËt to¸n Euclide). CÇn ®Ó ý r»ng Miyi ≡ 1 (mod mi) víi 1 ≤ i ≤ r. B©y giê ta ®Þnh nghÜa hµm ρ: Zm1 × . . . × Zmr  ZM nh− sau ( ) r ρ a ,...a r = ∑ a M y mod 1 i i i=1 i M Ta sÏ chøng tá r»ng ρ = π-1 , tøc lµ nã cho mét c«ng thøc t−êng minh ®Ó gi¶i hÖ ®ång d− thøc ban ®Çu. KÝ hiÖu X = ρ(a1, . . . ,ar) vµ cho 1 ≤ j ≤ r. XÐt sè h¹ng aiMiyi trong tæng trªn khi rót gän theo modulo mj. NÕu i = j th× aiMiyi ≡ ai (mod mi) v× Miyi ≡ 1 (mod mi) MÆt kh¸c, nÕu i ≠ j th× aiMiyi ≡ 0(mod mj) do mi Mi trong tr−êng hîp nµy. Bëi vËy chóng ta cã X ≡ ∑ a iM ≡ a i (mod i y i (mod m j m j ) ) Do ®iÒu nµy ®óng ®èi víi mäi j, 1 ≤ j ≤ r, nªn X lµ nghiÖm cña hÖ ph−¬ng tr×nh ®ång d−. Tíi lóc nµy cÇn ph¶i chøng tá r»ng nghiÖm X lµ duy nhÊt theo modulo M vµ ®iÒu nµy cã thÓ ®−îc chøng tá b»ng c¸ch tÝnh to¸n ®¬n gi¶n. π lµ hµm tõ mét miÒn cã lùc l−îng M sang mét miÒn cã lùc l−îng M. Ta võa míi chøng tá r»ng π lµ mét toµn ¸nh. Bëi vËy π ph¶i còng lµ mét ®¬n ¸nh (tøc lµ phÐp t−¬ng øng 1 - 1) do miÒn x¸c ®Þnh vµ miÒn gi¸ trÞ cã cïng lùc l−îng. §iÒu ®ã kÐo theo π lµ mét song ¸nh vµ π-1 = p. Còng cÇn chó ý lµ π-1 lµ mét hµm tuyÕn tÝnh cña c¸c biÕn a1,. . ., ar. Sau ®©y lµ mét vÝ dô lín h¬n ®Ó minh ho¹ VÝ dô 4.3 Gi¶ sö r = 3, m1 = 7, m2 = 11 vµ m3 = 13. Khi ®ã M = 1001. Ta tÝnh M1 = 143, M2 = 91 vµ M3 = 77 vµ sau ®ã tÝnh y1 = 5, y2 = 4 vµ y3 = 12. Khi ®ã hµm π-1: Z7×Z11×Z13  Z1001 cã d¹ng: π-1(a1,a2,a3) = 715a1 +364a2 + 924a3 mod 1001 VÝ dô, nÕu x ≡ 5 (mod 7), x ≡ 3 (mod 11) vµ x ≡ 10 (mod 13) th× c«ng thøc trªn sÏ cho ta biÕt r»ng x = 715 × 5 + 364 × 3 + 924 × 10 mod 1001 = 13907 mod 1001 = 894 mod 1001 §iÒu nµy cã thÓ kiÓm tra ®−îc b»ng c¸ch rót gän 894 theo modulo 7, 11 vµ 13. §Ó tham kh¶o sau nµy, ta sÏ ghi c¸c kÕt qu¶ ë phÇn nµy d−íi d¹ng mét ®Þnh lý §Þnh lý 4.3 (§Þnh lý phÇn d− China) Gi¶ sö m1, . . . ,mr lµ c¸c sè nguyªn d−¬ng nguyªn tè cïng nhau tõng ®«i mét vµ cho a1, . . ., ar lµ c¸c sè nguyªn. Khi ®ã, hÖ r ®ång d− thøc x ≡ ai (mod mi) (1 ≤ i ≤ r ) sÏ cã mét nghiÖm duy nhÊt theo modulo M = m1× . . . × mr ®−îc cho theo c«ng thøc r x = ∑ a i M i y i mod M trong ®ã Mi = M/mi vµ yi = i =1 Mi-1 mod mi, víi 1 ≤ i ≤ r. 4.2.3. C¸c kiÕn thøc cÇn thiÕt kh¸c Sau ®©y sÏ nh¾c tíi mét kÕt qu¶ kh¸c trong lý thuyÕt nhãm s¬ cÊp: ®Þnh lý Lagrange. §Þnh lý nµy cã liªn quan ®Õn c¸ch ®Ò cËp vÒ hÖ mËt RSA. Víi mét nhãm nh©n h÷u h¹n G, ta ®Þnh nghÜa cÊp cña mét phÇn tö g ∈ G lµ sè nguyªn d−¬ng m bÐ nhÊt sao cho gm = 1. Ta cã kÕt qu¶ sau ®©y (kh«ng chøng minh ). §Þnh lý 4.4 (Lagrange ) Gi¶ sö G lµ mét nhãm cÊp n vµ g ∈ G. Khi ®ã cÊp cña g lµ −íc cña n. Víi môc ®Ých ®−a ra, hÖ qu¶ sau rÊt quan träng. HÖ qu¶ 4.5 NÕu b ∈ Zn* th× bφ(n) ≡ 1 (mod n) Chøng minh: Zn* lµ nhãm nh©n cÊp φ(n). HÖ qu¶ 4.6 (Ferma) Gi¶ sö p lµ sè nguyªn tè vµ b ∈ Zp. Khi ®ã bp ≡ b (mod p). Chøng minh: NÕu p lµ sè nguyªn tè th× φ(n) = p-1. Bëi vËy, víi b≡0(mod p), kÕt qu¶ trªn ®−îc rót ra tõ hÖ qu¶ 4.5. Víi b ≡ 0 (mod p), kÕt qu¶ trªn vÉn ®óng do 0p ≡ 0 (mod 0). Cho tíi giê ta ® biÕt r»ng, nÕu p lµ sè nguyªn tè th× Zp* lµ mét nhãm cÊp p-1 vµ mét phÇn tö bÊt k× trong Zp* sÏ cã bËc lµ −íc cña p-1. Tuy nhiªn, nÕu p lµ sè nguyªn tè th× nhãm Zp* lµ nhãm cyclic: tån t¹i mét phÇn tö α ∈ Zp* cã cÊp b»ng p-1. Ta kh«ng chøng minh kÕt qu¶ quan träng nµy nh−ng sÏ ghi l¹i ®Ó tham kh¶o sau nµy. §Þnh lý 4.7. NÕu p lµ sè nguyªn tè th× Zp* lµ nhãm cyclic. Mét phÇn tö α cã cÊp p-1 ®−îc gäi lµ phÇn tö nguyªn thuû modulo p. XÐt thÊy α lµ phÇn tö nguyªn thuû khi vµ chØ khi: {αi : 0 ≤ i ≤ p-2} = Zp* B©y giê gi¶ sö p – nguyªn tè vµ α - phÇn tö nguyªn thuû modulo p. Mét phÇn tö bÊt k× β ∈ Zp* cã thÓ ®−îc viÕt nh− sau: β = αi, trong ®ã 0 ≤ i ≤ p-2 (theo mét c¸ch duy nhÊt ). Kh«ng khã kh¨n cã thÓ chøng tá r»ng cÊp cña β = αi lµ: p -1 UCLN(p - 1, i) Nh− vËy b¶n th©n β lµ phÇn tö nguyªn thuû khi vµ chØ khi −CLN (p-1,i) = 1. §iÒu ®ã dÉn ®Õn lµ sè c¸c phÇn tö nguyªn thuû theo modulo p = φ(p-1). VÝ dô 4.4: Gi¶ sö p=13. B»ng c¸ch tÝnh c¸c luü thõa liªn tiÕp cña 2 ta cã thÓ thÊy r»ng 2 lµ phÇn tö nguyªn thuû theo modulo 13: 20 mod 13 =1 23 mod 13 =8 26 mod 13 =12 29 mod 13 =5 21 mod 13 =2 24 mod 13 =3 27 mod 13 =11 210 mod 13 =10 22 mod 13 =4 25 mod 13 =6 28 mod 13 =9 211 mod 13 =7 PhÇn tö 2i lµ nguyªn thuû khi vµ chØ khi −CLN(i,12) = 1; nghÜa lµ khi vµ chØ khi i = 1, 5, 7 hoÆc 11. Bëi vËy c¸c phÇn tö nguyªn thuû theo modulo 13 lµ 2, 6, 7 vµ 11. 4.3. hÖ mËt RSA B©y giê chóng ta cã thÓ m« t¶ hÖ mËt RSA. HÖ mËt nµy sö dông c¸c tÝnh to¸n trong Zn, trong ®ã n lµ tÝch cña 2 sè nguyªn tè ph©n biÖt p vµ q. Ta nhËn thÊy r»ng φ(n) = (p-1)(q-1). M« t¶ h×nh thøc cña hÖ mËt ®−îc cho trong h×nh 4.2 . Ta h y kiÓm tra xem c¸c phÐp m vµ gi¶i m cã ph¶i lµ c¸c phÐp to¸n nghÞch ®¶o cña nhau hay kh«ng. V× ab ≡ 1 (mod φ(n)) nªn ta cã ab = t φ(n) + 1 víi mét sè nguyªn t ≥ 1 nµo ®ã. Gi¶ sö x ∈ Zp*; khi ®ã ta cã: (xb)a ≡ xtφ(n)+1 (mod n) ≡ (xφ(n))t x (mod n) ≡ 1t x (mod n) ≡ x (mod n) H×nh 4.2: HÖ mËt RSA Cho n = p.q trong ®ã p vµ q lµ c¸c sè nguyªn tè. §Æt P = C = Zn vµ ®Þnh nghÜa K = {(n,p,q,a,b): n = p.q, p,q lµ c¸c sè nguyªn tè, ab ≡ 1(mod φ(n))} Víi K = (n,p,q,a,b) ta x¸c ®Þnh eK (x) = xb mod n vµ dK (y) = ya mod n (x,y) ∈ Zn. C¸c gi¸ trÞ n vµ b ®−îc c«ng khai , c¸c gi¸ trÞ p,q,a ®−îc gi÷ bÝ mËt. ®óng nh− mong muèn. Xem nh− mét bµi tËp, b¹n ®äc h y chøng tá r»ng (xb)a ≡ x (mod n) nÕu x ∈ Zn\ Zp*. Sau ®©y lµ mét vÝ dô nhá (tÊt nhiªn lµ kh«ng mËt ) vÒ hÖ mËt RSA. VÝ dô 4.5: Gi¶ sö Bob chän p = 101 vµ q = 113. Khi ®ã n = 11413 vµ φ(n) = 100×112 = 11200. V× 11200 = 26527, nªn cã thÓ dïng mét sè nguyªn b nh− mét sè mò m ho¸ khi vµ chØ khi b kh«ng chia hÕt cho 2, 5 hoÆc 7. (V× thÕ trong thùc tÕ Bob sÏ kh«ng ph©n tÝch φ(n), anh ta sÏ kiÓm tra ®iÒu kiÖn −CLN(φ(n),b) = 1 b»ng thuËt to¸n Euclide. Gi¶ sö Bob chän b = 3533, khi ®ã theo thuËt to¸n Euclide më réng: b-1 = 6597 mod 11200 Bëi vËy sè mò mËt ®Ó gi¶i m cña Bob lµ a = 6597. Bob sÏ c«ng bè n = 11413 vµ b = 3533 trong mét danh b¹. B©y giê, gi¶ sö Alice muèn göi b¶n râ 9726 tíi Bob. C« ta tÝnh 97263533 mod 11413 = 5761 råi göi b¶n m 5761 trªn kªnh. Khi ®ã Bob nhËn ®−îc b¶n m 5761, anh ta sö dông sè mò a mËt ®Ó tÝnh: 57616597 mod 11413 = 9762 (cho tíi lóc nµy, c¸c phÐp m vµ gi¶i m cho hÖ mËt ® kh¸ phøc t¹p, tuy nhiªn ta sÏ th¶o luËn vÒ c¸c thuËt to¸n h÷u hiÖu cho c¸c phÐp to¸n nµy ë phÇn sau). §é mËt cña hÖ RSA ®−îc dùa trªn gi¶ thiÕt lµ hµm m ek(x)= xb mod n lµ hµm mét chiÒu. Bëi vËy th¸m m sÏ kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n ®Ó gi¶i m mét b¶n m . Cöa sËp cho phÐp Bob gi¶i m ®−îc chÝnh lµ th«ng tin vÒ phÐp ph©n tÝch thõa sè n (n = pq). V× Bob biÕt ph©n tÝch nµy, anh ta cã thÓ tÝnh φ(n) = (p-1)(q-1) vµ råi tÝnh sè mò gi¶i m a b»ng c¸ch sö dông thuËt to¸n Euclide më réng. Sau nµy chóng ta sÏ cßn tiÕp tôc nãi thªm vÒ vÊn dÒ nµy. 4.4. Thùc hiÖn hÖ mËt RSA Cã nhiÒu khÝa c¹nh cÇn th¶o luËn vÒ hÖ mËt RSA bao gåm c¸c chi tiÕt vÒ viÖc thiÕt lËp hÖ mËt, tÝnh hiÖu qu¶ cña phÐp m vµ gi¶i m vµ ®é mËt cña hÖ. §Ó thiÕt lËp hÖ thèng, Bob sÏ tu©n theo c¸c b−íc ®−îc nªu trong h×nh 4.3. H×nh 4.3 ThiÕt lËp hÖ mËt RSA 1. Bob t¹o hai sè nguyªn tè lín p vµ q 2. Bob tÝnh n = p.q vµ φ(n) = (p-1)(q-1) 3. Bob chän mét sè ngÉu nhiªn b (0< b < φ(n)) sao cho −CLN(b,φ(n)) = 1 4. Bob tÝnh a = b-1 mod φ(n) b»ng c¸ch dïng thuËt to¸n Euclide 5. Bob c«ng bè n vµ b trong mét danh b¹ vµ chóng lµm kho¸ c«ng khai. ViÖc Bob tiÕn hµnh c¸c b−íc nµy nh− thÕ nµo sÏ cßn ®−îc tiÕp tôc th¶o luËn trong ch−¬ng nµy. C¸ch tÊn c«ng dÔ thÊy nhÊt hÖ mËt nµy lµ th¸m m cè g¾ng ph©n tÝch n ra c¸c thõa sè nguyªn tè. NÕu thùc hiÖn ®−îc viÖc nµy th× cã thÓ dÔ dµng tÝnh ®−îc φ(n) = (p-1)(q-1) råi tÝnh sè mò a tõ b nh− Bob lµm (ng−êi ta pháng ®o¸n r»ng, viÖc ph¸ hÖ mËt RSA lµ t−¬ng ®−¬ng ®a thøc víi viÖc ph©n tÝch n, tuy nhiªn ®iÒu nµy vÉn cßn ch−a ®−îc chøng minh. Hai bµi to¸n ®−îc gäi lµ t−¬ng ®−¬ng ®a thøc nÕu tån t¹i mét thuËt to¸n thêi gian ®a thøc cho bµi to¸n nµy sÏ suy ra ®−îc sù tån t¹i mét thuËt to¸n thêi gian ®a thøc cho bµi to¸n kia). V× thÕ hÖ mËt RSA ®−îc coi lµ mËt th× nhÊt thiÕt n = pq ph¶i lµ mét sè ®ñ lín ®Ó viÖc ph©n tÝch nã kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n. C¸c thuËt to¸n ph©n tÝch hiÖn thêi cã kh¶ n¨ng ph©n tÝch c¸c sè cã 130 ch÷ sè thËp ph©n (chi tiÕt h¬n vÒ bµi to¸n ph©n tÝch thõa sè nguyªn tè xem trong phÇn 4.8). V× vËy ®Ó ®¶m b¶o an toµn nªn chän c¸c sè p vµ q chõng 100 ch÷ sè, khi ®ã n sÏ cã tíi 200 ch÷ sè. Mét vµi ¸p dông phÇn cøng cña RSA sö dông m« ®un cã ®é dµi 512 bit. Tuy nhiªn mét m« ®un 512 bit t−¬ng øng víi mét sè cã 154 ch÷ sè thËp ph©n (v× sè c¸c bit trong biÓu diÔn nhÞ ph©n cña mét sè nguyªn b¨ng log210 lÇn cña c¸c ch÷ sè thËp ph©n) v× vËy kh«ng ®ñ ®¶m b¶o an toµn l©u dµi. B©y giê t¹m thêi g¸c l¹i vÊn ®Ò t×m c¸c sè nguyªn tè cã 100 ch÷ sè ®Ó xem xÐt viÖc thùc hiÖn c¸c phÐp to¸n sè häc trong m vµ gi¶i m . PhÐp m (hoÆc gi¶i m ) sÏ xoay quanh phÐp lÊy luü thõa theo modulo n. V× n lµ mét sè rÊt lín nªn ta ph¶i sö dông sè häc lÊy chÝnh x¸c nhiÒu lÇn (multi – precision) ®Ó thùc hiÖn c¸c tÝnh to¸n trong Zn vµ thêi gian tÝnh to¸n cÇn thiÕt sÏ phô thuéc vµo sè c¸c bÝt trong biÓu diÔn nhÞ ph©n cña n. Gi¶ sö n cã k bit trong biÓu diÔn nhÞ ph©n, tøc lµ k = log2 n + 1. Sö dông kÜ thuËt sè häc ë bËc trung häc, dÔ dµng thÊy r»ng mét phÐp céng hai sè nguyªn k bit cã thÓ thùc hiÖn trong thêi gian O(k) vµ mét phÐp nh©n cã thÓ thùc hiÖn trong thêi gian O(k2). Còng vËy, phÐp rót gän mét sè nguyªn theo modulo n (sè nµy cã nhiÒu nhÊt lµ 2K bÝt )cã thÓ thùc hiÖn trong thêi gian O(k2) (®Ó thùc hiÖn phÐp chia vµ phÐp t×m phÇn d−). B©y giê gi¶ sö r»ng x,y∈Zn (ë ®©y xem r»ng 0 ≤ x,y ≤ n-1). Khi ®ã cã thÓ tÝnh xy mod n tr−íc tiªn b»ng viÖc tÝnh tÝch xy (lµ mét sè nguyªn 2k bÝt), råi rót gän cho modulo n. Hai b−íc nµy cã thÓ thùc hiÖn trong thêi gian O(k2). Ta gäi phÐp tÝnh nµy lµ nh©n modulo. B©y giê xÐt phÐp lÊy luü thõa theo modulo (tøc lµ tÝnh hµm d¹ng xc mod n). Nh− nhËn xÐt ë trªn, c¶ hai phÐp m vµ gi¶i m trong RSA ®Òu lµ c¸c phÐp luü thõa theo modulo. ViÖc tÝnh xc mod n cã thÓ thùc hiÖn b»ng c-1 phÐp nh©n modulo, tuy nhiªn khi c lín th× c¸ch tÝnh nµy rÊt cång kÒnh. Chó ý r»ng c lín cì nh− φ(n) -1 (lµ mét sè lín cÊp luü thõa so víi k). Sö dông biÖn ph¸p "b×nh ph−¬ng vµ nh©n" ® biÕt sÏ lµm gi¶m sè phÐp nh©n modulo cÇn thiÕt, ®Ó tÝnh x mod n nhiÒu nhÊt lµ 2l, trong ®ã l lµ sè c¸c bit trong biÔu diÔn nhÞ ph©n cña c. V× l ≤ k nªn cã thÓ coi xc mod n ®−îc thùc hiÖn trong thêi gian O(k3). V× thÕ c¸c phÐp m vµ gi¶i m ®−îc thùc hiÖn theo thêi gian ®a thøc (nh− mét hµm cña k lµ sè c¸c bÝt trong mét b¶n râ (hoÆc b¶n m ). Trong thuËt to¸n “ b×nh ph−¬ng vµ nh©n”, ta coi r»ng sè mò b ®−îc biÓu thÞ ë d¹ng nhÞ ph©n nh− sau: l -1 b = ∑ bi 2i 2 i =0 Trong ®ã bi = 0 hoÆc 1, 0 ≤ i ≤ l-1. ThuËt to¸n ®Ó tÝnh z = xb mod n ®−îc m« t¶ ë h×nh 4.4. H×nh 2.5 ThuËt to¸n b×nh ph−¬ng vµ nh©n ®Ó tÝnh xb mod n 1. 2. 3. 4. z=1 for i = l-1 down to 0 do z = z2 mod n if bi = 1 then z = z.x mod n DÔ dµng tÝnh ®−îc sè c¸c phÐp nh©n modulo thùc hiÖn bëi thuËt to¸n trªn. Lu«n lu«n ph¶i thùc hiÖn l phÐp b×nh ph−¬ng (ë b−íc 3). Sè phÐp nh©n trong b−íc 4 b»ng sè c¸c bit "1" trong biÓu diÔn nhÞ ph©n cña b (sè nµy thuéc kho¶ng tõ 0 tíi l). Bëi vËy tæng sè phÐp nh©n modulo cÇn thùc hiÖn n»m trong kho¶ng tõ l tíi 2l. Ta sÏ minh ho¹ c¸ch sö dông thuËt to¸n trªn b»ng c¸ch quay trë l¹i vÝ dô 4.5. VÝ dô 4.5 (tiÕp): Ta cã n = 11413 vµ sè mò m ho¸ c«ng khai b = 3533. Alice sÏ m ho¸ b¶n râ 9726 b»ng c¸ch tÝnh 97263533 mod 11413 theo thuËt to¸n “b×nh ph−¬ng vµ nh©n” nh− sau: i bi z 11 1 12× 9726 = 9726 10 1 9 0 97262 × 9726 = 2659 26592 = 5634 8 1 56342 × 9726 = 9167 7 1 91672 × 9726 = 4958 6 1 5 0 4 0 49582 × 9726 = 7783 77832 = 6298 62982 = 4629 3 1 46292 × 9726 = 10185 2 1 1 0 101852 × 9726 = 105 1052 = 11025 0 1 110252 × 9726 = 5761 Nh− vËy b¶n m lµ 5761. CÇn ph¶i nhÊn m¹nh r»ng, nh÷ng øng dông phÇn cøng hiÖu qu¶ nhÊt hiÖn thêi cña RSA chØ ®¹t ®−îc tèc ®é m ho¸ chõng 600Kb/s (sö dông c¸c m« ®un 512 bÝt) so víi DES cã tèc ®é 1 Gb/s. Nãi c¸ch kh¸c RSA chËm h¬n kho¶ng 1500 lÇn so víi DES. §Õn ®©y, ta chØ míi xÐt ®−îc c¸c phÐp m ho¸ vµ gi¶i m cho RSA. §Ó thiÕt lËp hÖ mËt RSA, ta cßn ph¶i xÐt viÖc t¹o c¸c sè nguyªn tè p vµ q (b−íc 1), b−íc nµy sÏ ®−îc nghiªn cøu ë phÇn sau. B−íc 2 kh¸ ®¬n gi¶n vµ ®−îc thùc hiÖn trong thêi gian O((log n)2). C¸c b−íc 3 vµ 4 xoay quanh thuËt to¸n Euclide, v× thÕ sÏ xÐt qua vÒ ®é phøc t¹p cña thuËt to¸n nµy. Gi¶ sö ta ph¶i tÝnh −CLN cña r0 vµ r1, trong ®ã r0 > r1 . Trong mçi b−íc lÆp ®Òu ph¶i tÝnh th−¬ng vµ phÇn d−, ®iÒu nµy cã thÓ thùc hiÖn ®−îc trong thêi gian O((log r0)2). NÕu t×m ®−îc giíi h¹n trªn cho sè phÐp lÆp th× ta sÏ cã ®−îc giíi h¹n cho ®é phøc t¹p cña thuËt to¸n. KÕt qu¶ nµy ® ®−îc nªu trong ®Þnh lý LamÐ. §Þnh lý kh¼ng ®Þnh r»ng nÕu s lµ sè c¸c phÐp lÆp th× f3+2 ≤ r0 , trong ®ã fi lµ sè Fibonacci thø i . V× 1 + 5   fi =   2   Nªn ®iÒu ®ã kÐo theo s lµ O(log r0). §iÒu nµy chøng tá r»ng thêi gian ch¹y cña thuËt to¸n Euclide lµ O((log n)3) (trªn thùc tÕ, b»ng c¸c ph©n tÝch chi tiÕt h¬n, cã thÓ chøng tá r»ng thêi gian ch¹y chØ lµ O((log n)2). 4.5. KiÓm tra tÝnh nguyªn tè x¸c suÊt §Ó thiÕt lËp hÖ mËt RSA, ta ph¶i t¹o ra c¸c sè nguyªn tè ngÉu nhiªn lín (ch¼ng h¹n cã 80 ch÷ sè). Trong thùc tÕ, ph−¬ng c¸ch thùc hiÖn ®iÒu nµy lµ: tr−íc hÕt ph¶i t¹o ra c¸c sè ngÈu nhiªn lín, sau ®ã kiÓm tra tÝnh nguyªn thuû cña chóng b»ng c¸ch dïng thuËt to¸n x¸c suÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh− thuËt to¸n Miller- Rabin hoÆc lµ thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸n trªn ®Òu ®−îc tr×nh bµy trong phÇn nµy. Chóng lµ c¸c thuËt to¸n nhanh (tøc lµ mét sè nguyªn n ®−îc kiÓm tra trong thêi ®a thøc theo log2n, lµ sè c¸c bÝt trong biÓu diÖn nhÞ ph©n cña n). Tuy nhiªn, vÉn cã kh¶ n¨ng lµ thuËt to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ n lµ hîp sè. Bëi vËy, b»ng c¸ch thay ®æi thuËt to¸n nhiÒu lÇn, cã thÓ gi¶m x¸c suÊt sai sè d−íi mét møc ng−ìng cho phÐp (sau nµy sÏ th¶o luËn kü h¬n mét chót vÒ vÊn ®Ò nµy). Mét vÊn ®Ò quan träng kh¸c: lµ cÇn ph¶i kiÓm tra bao nhiªu sè nguyªn ngÉu nhiªn (víi kÝch th−íc x¸c ®Þnh) cho tíi khi t×m ®−îc mét sè nguyªn tè. Mét kÕt qu¶ nçi tiÕng trong lý thuyÕt sè (®−îc gäi lµ ®Þnh lý sè nguyªn tè) ph¸t biÓu r»ng: sè c¸c sè nguyªn tè kh«ng lín h¬n N xÊp xØ b»ng N/ln N. Bëi vËy, nÕu p ®−îc chän ngÉu nhiªn th× x¸c suÊt p lµ mét sè nguyªn tè sÏ vµo kho¶ng 1/ln p. Víi mét mo®un 512 bÝt, ta cã 1/ln p ≈ 1/77. §iÒu nµy cã nghÜa lµ tÝnh trung b×nh, cø 177 sè nguyªn ngÉu nhiªn p víi kÝch th−íc t−¬ng øng sÏ cã mét sè lµ sè nguyªn tè. DÜ nhiªn, nÕu chÜ h¹n chÕ xÐt c¸c sè nguyªn lÎ th× x¸c suÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, hoµn toµn cã kh¶ n¨ng t¹o ®−îc c¸c nguyªn tè ®ñ lín vµ do ®ã vÒ mÆt thùc thÓ ta cã thÓ thiÕt lËp ®−îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xem xÐt ®iÒu nµy ®−îc thùc hiÖn nh− thÕ nµo. Mét bµi to¸n quyÕt ®Þnh lµ mét bµi to¸n trong ®ã mét c©u hái cÇn ®−îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt lµ mét thuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ng−îc l¹i, thuËt to¸n kh«ng sö dông c¸c sè ngÉu nhiªn sÏ ®−îc gäi lµ mét thuËt to¸n tÊt ®Þnh). C¸c ®Þnh nghÜa sau cã liªn quan tíi c¸c thuËt to¸n x¸c suÊt cho c¸c bµi to¸n quyÕt ®Þnh. §Þnh nghÜa 4.1 ThuËt to¸n Monte Carlo ®Þnh h−íng “cã” lµ mét thuËt to¸n x¸c suÊt cho mét bµi to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«n lµ ®óng cßn c©u tr¶ lêi “kh«ng” cã thÓ lµ sai. ThuËt to¸n Monte Carlo ®Þnh h−íng “kh«ng“ còng ®−îc ®Þnh nghÜa theo c¸ch t−¬ng tù. Chóng ta nãi r»ng, mét thuËt to¸n Monte Carlo ®Þnh h−íng “cã” cã x¸c suÊt sai b»ng ε nÕu víi bÊt kú mæt tr−êng hîp nµo mµ c©u tr¶ lêi lµ “cã” th× thuËt to¸n cã c©u tr¶ lêi sai “kh«ng” víi x¸c suÊt kh«ng lín h¬n ε (x¸c suÊt nµy ®−îc tÝnh trªn mäi phÐp chon ngÉu nhiªn, cã thÓ thùc hiªn bëi thuËt to¸n víi mét c©u vµo ®U cho). Bµi to¸n quyÕt ®Þnh ë ®©y lµ bµi to¸n hîp lÖ sè m« t¶ ë h×nh 4.5. CÇn chó ý r»ng mét thuËt to¸n quyÕt ®Þnh chØ cã c©u tr¶ lêi “cã” hoÆc “kh«ng” ®Æc biÖt trong bµi to¸n hîp lÖ sè lµ ta kh«ng yªu cÇu thuËt to¸n tÝnh tÝch thõa sè khi n lµ hîp lÖ sè. Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµ mét thuËt to¸n Monte- Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè cã Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Soloway- Strasson. §©y lµ mét thuËt to¸n Monte-Carlo ®Þnh h−íng “cã” cho bµi to¸n hîp sè vµ x¸c xuÊt sai 1/2. Bëi vËy, nÕu thuËt to¸n tr¶ lêi “cã” th× n lµ hîp sè; ng−îc l¹i nÕu n lµ hîp sè th× thuËt to¸n tr¶ lêi “cã” víi x¸c xuÊt tèi thiÓu 1/2. H×nh 4.5. Bµi to¸n hîp sè. §Æc tr−ng cña bµi to¸n: mét sè nguyªn d−¬ng n ≥ 2 C©u hái: n cã ph¶i lµ hîp sè kh«ng ? H×nh 4.6. Bµi to¸n vÒ c¸c thÆng d− bËc hai. §Æc tr−ng cña bµi to¸n: cho p lµ mét sè nguyªn tè lÎ vµ mét sè nguyªn x sao cho 0 ≤ x ≤ p-1 C©u hái: x cã ph¶i lµ thÆng d− bËc hai phÐp modulo p ? MÆc dï thuËt to¸n Miller-Rabin (ta sÏ xÐt sau) nhanh h¬n thuËt to¸n Soloway-Strasson (S-S) nh−ng ta sÏ xÐt thuËt to¸n S-S tr−íc v× nã dÔ hiÓu h¬n vÒ kh¸i niÖm, ®ång thêi l¹i liªn quan tíi mét sè vÊn ®Ò cña lý thuyÕt sè (mµ ta sÏ cßn dïng trong c¸c ch−¬ng tr×nh sau). Ta sÏ x©y dùng mét sè nÒn t¶ng s©u s¾c h¬n trong lý thuyÕt sè tr−íc khi m« t¶ thuËt to¸n. §Þnh nghÜa 4.2. Gi¶ sö p lµ mét sè nguyªn tè lÎ vµ x lµ mét sè nguyªn, 1 ≤ x ≤ p-1. x ®−îc gäi lµ thÆng d− bËc hai theo modulo p nÕu ph−¬ng tr×nh ®ång d− y2 ≡ x (modulo p) cã mét nghiÖm y∈Zp x ®−îc gäi lµ thÆng d− kh«ng bËc hai theo modulo p nÕu x ??? 0 (mod p) vµ x kh«ng ph¶i lµ thÆng d− bËc hai theo modulo p. VÝ dô 4.6. C¸c thÆng d− bËc hai theo modulo 11 lµ 1,3,4,5 vµ 9. CÇn ®Ó ý r»ng, 2 (±1) =1, (±5)2=3, (±2)2=4, (±4)2=5, (±3)2=9 (ë ®©y tÊt c¶ c¸c phÐp sè häc ®Òu thùc hiÖn trong Z11). Bµi to¸n quyÕt ®Þnh thÆng d− bËc hai ®−îc tr×nh bµy trªn h×nh 4.6 sÏ ®−îc thÊy mét c¸ch t−¬nngf minh nh− sau: Tr−íc hÕt, ta sÏ chøng minh mét kÕt qu¶- tiªu chuÈn Euler –t¹o nªn thuËt to¸n tÊt ®Þnh theo thêi gian ®a thøc cho bµi to¸n vÒ c¸c thÆng d− bËc hai. §Þnh lý 4.8. (Tiªu chuÈn Euler) Gi¶ sö p lµ mét sè nguyªn tè, khi ®ã x lµ mét thÆng d− bËc hai theo modulo p khi vµ chØ khi: x(p-1)/2 ≡1 (mod p) Chøng minh: Tr−íc hÕt gi¶ sö r»ng, x≡y2(mod p). Theo hÖ qu¶ 4.6, nÕu p lµ sè nguyªn tè th× xp-1≡1 (mod p) víi mäi x ≡ 0 (mod p). Bëi vËy ta cã : x(p-1)/2 ≡ (y2)(p-1)/2 (mod p) ≡yp-1(mod p) ≡1 (mod p) Ng−îc l¹i, gi¶ sö r»ng x(p-1)/2≡1 (mod p). Cho p lµ mét phÇn tö nguyªn thuû theo modulo p. Khi ®ã x≡bi (mod p) víi gi¸ trÞ i nµo ®ã. Ta cã x(p-1)/2 ≡ (bi)(p-1)/2 (mod p) ≡bi(p-1)/2(mod p) V× b cã bËc b»ng p-1 nªn p-1 ph¶i lµ −íc cña i(p-1)/2. Bëi vËy i lµ sè ch½n vµ nh− vËy c¨n bËc hai cña x lµ ±bi/2. §Þnh lý 4.8 sÏ dÉn tíi mét thuËt to¸n thêi gian ®a thøc cho c¸c thÆng d− bËc hai nhê sö dông kü thuËt “b×nh ph−¬ng vµ nh©n” cho phÐp lÊy luü thõa theo modulo p. §é phøc t¹p cña thuËt to¸n kho¶ng O((log p)3). Sau ®©y tiÕp tôc ®−a ra mét sè ®Þnh nghÜa tõ lý thuyÕt sè: § Þnh nghÜa 4.3 Gi¶ sö p lµ mét sè nguyª n tè lÎ. Víi mét sè nguyª n bÊt kú a ≥ 0 , a ta dÞnh nghÜa ký hiÖu Legendre   nh− sau :  p 0 nÕu a ≡ 0 (mod p) a   = 1 nÕu a lµ thÆng d− bËc hai theo modulo p  p - 1 nÕu a lµ thÆng d− kh«ng bËc hai theo modulo p Ta ® biÕt lµ a(p-1)/2≡ 1 (mod p) khi vµ chØ khi a lµ mét thÆng d− bËc hai theo modulo p. NÕu a lµ béi cña p th× râ rµng a(p-1)/2≡ 0(mod p). Cuèi cïng, nÕu a lµ mét thÆng d− kh«ng bËc hai theo modulo p th× a(p-1)≡ -1 (mod p) v× ap1 ≡1(mod p). Bëi vËy, ta cã kÕt qu¶ cho phÐp x©y dùng mét thuËt to¸n h÷u hiÖu ®Ó ®¸nh gi¸ c¸c ký hiÖu Legendre nh− sau §Þnh Lý 4.9. Gi¶ sö p lµ mét sè nguyªn tè. Khi ®ã a   p ≡ a(p-1)/2 (mod p). Sau ®©y lµ mét ®Þnh nghÜa tæng qu¸t ho¸ cho ký hiÖu Legendre. §Þnh nghÜa 4.4. Gi¶ sö n lµ mét sè nguyªn d−¬ng lÎ vµ ph©n tÝch theo c¸c luü thõa nguyªn tè cña n lµ p1e1 ....... pKek . Gi¶ sö a ≥ 0 lµ mét sè nguyªn. a   r
- Xem thêm -