Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin An ninh bảo mật Giáo trình mật mã và ứng dụng chương 4...

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

.PDF
58
379
84

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 -

Tài liệu liên quan