Chương 4 : Kiểm tra tính nguyên tử

Chia sẻ: Thao Thao | Ngày: | Loại File: PDF | Số trang:26

Thêm vào BST

Báo xấu

47
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tuỳ vào bạn, nhưng đây là một phương pháp quan trọng để thể hiện sư liên quan của các các màu sắc. Đây là các màu phù hợp với kiểu phối 3 màu. Đây không phải là kiểu mà bạn nghĩ về bánh xe màu

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 4 : Kiểm tra tính nguyên tử

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Ën to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ n lµ hîp lÖ 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 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 ®· 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 trng 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 trng 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) nhng 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, (1)2=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× p 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µ sè nguyªn tè lÎ. Víi mét sè nguyªn tè bÊt kú a 0, ta a   p  ®Þnh nghÜa ký hiÖu Legendre nh sau: 0 nÕu a  0 (mod p) a   p = 1 nÕu lµ th¨ng d bËc hai theo modulo p  -1 nÕu 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× ap-1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. a   a(p-1)/2 (mod p).  p Gi¶ sö p lµ mét sè nguyªn tè. Khi ®ã  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 Ký hiÖu  r   Jacobi ®îc ®Þnh nghÜa nh sau: ei a  K a        n  i 1 p i   
VÝ dô 4.7.  6278  XÐt ký hiÖu Jacobi  9975  . Ph©n tÝch luü thõa nguyªn tè cña   9975 lµ: 9975=3 x 52 x 7 x 19. Bëi vËy ta cã: 2  6278   6278  6278   6278  6278         9975   3  5   7  19  2  2  3   6  8  =        3   5   7   19  =(-1)(-1)2(-1)(-1) = -1. Gi¶ sö n > 1 lµ mét sè lÎ. NÕu n lµ mét sè nguyªn tè th×  a a(n-1)/2 (mod n) víi a bÊt kú. MÆt kh¸c nÕu n lµ mét hîp sè th× ®ång d  n thøc trªn cã thÓ ®óng hoÆc kh«ng. NÕu ph¬ng tr×nh ®ã vÉn ®óng th× a ®îc gäi lµ sè gi¶ nguyªn tè Euler theo c¬ sè n. VÝ dô: 10 lµ sè gi¶ nguyªn tè Euler theo c¬ sè 91 v× :  10   = -1 = 1045 mod 91  91  Tuy nhiªn cã thÓ chøng tá r»ng, víi mét hîp sè lÎ n bÊt kú, sÏ cãp nhiÒu nhÊt mét nöa c¸c sè nguyªn a (sao cho 1  a  n-1) lµ c¸c sè gi¶ nguyªn tè Euler c¬ sè n (xem c¸c bµi tËp). §iÒu ®ã chøng tá r»ng, viÖc kiÓm tra tÝnh nguyªn tè theo thuËt to¸n Soloway-Strasson ®îc nªu ë h×nh 4.7 lµ thuËt to¸n Monte-Carlo ®Þnh híng “cã”víi x¸c xuÊt sai tèi ®a lµ 1/2.
§Õn ®©y vÉn cha x¸c ®Þnh râ thuËt to¸n ttrªn cã theo thêi gian ®a thøc hay kh«ng. Ta ®· biÕt c¸ch ®¸nh gi¸ a(n-1)/2 (mod n) trong thêi gian ®a thøc O((log n)3), tuy nhiªn cÇn ph¶i lµm thÕ nµo ®Ó tÝnh c¸c ký hiÖu Jacobi mét c¸ch cã hiÖu qu¶. V× ký hiÖu Jacobi ®îc x¸c ®Þnh theo c¸c thõa sè trong ph©n tÝch cña n. Tuy nhiªn nÕu cã thÓ ph©n tÝch ®îc n th× ta ®· biÕt nã cã ph¶i lµ sè nguyªn tè hay kh«ng, bëi vËy c¸ch lµm nµy sÏ dÉn tíi mét vßng luÈn quÈn. H×nh 4.7. ThuËt to¸n kiÓm tra tÝnh nguyªn tè Solova-Strassen víi sè nguyªn lÎ n. 1. Chän mét sè nguyªn ngÉu nhiªn a, 1  a  n-1  a(n-1)/2 (mod n) th× 2. NÕu  a  Tr¶ lêi “ n lµ sè nguyªn tè ”  n NÕu kh«ng Tr¶ lêi “ n lµ mét hîp sè ” RÊt may lµ cã thÓ ®¸nh gi¸ ký hiÖu Jacobi mµ kh«ng cÇn ph¶i ph©n tÝch n nhê sö dông mét sè kÕt qu¶ cña lý thuyÕt sè, trong ®ã kÕt qu¶ quan träng nhÊt lµ tÝnh chÊt 4 (tæng qu¸t ho¸ luËt t¬ng hç bËc hai ). Ta sÏ liÖt kª mµ kh«ng chøng minh c¸c tÝnh chÊt nµy. 1. NÕu n lµ mét sè nguyªn tè lÎ vµ m1  m2 (mod n) th×:  m1   m2     n =   n     2. NÕu n lµ mét sè nguyªn lÎ th× 1 nÕu n   1 (mod 8) 2 = -1 nÕu n   3 (mod 8) n 3. NÕu n lµ mét sè nguyªn lÎ th×  m 1 m 2   m 1  m 2       n   n  n 
§Æc biÖt nÕu m=2kt víi t lµ mét sè lÎ th×: k m  2  t      n n n 4. Gi¶ sö m vµ n lµ c¸c sè nguyªn lÎ, khi ®ã:  n   m  nÕu m  n  3 (mod 4)   2  =    n  trong c¸c trêng hîp cßn l¹i n   m  vÝ dô §Ó minh ho¹ cho viÖc ¸p dông c¸c tÝnh chÊt trªn , ta sÏ ®¸nh gi¸ kÝ  7411  hiÖu Jacobi nh trong b¶ng díi ®©y. CÇn chó ý lµ trong vÝ    9283  dô nµy, ta ®· sö dông liªn tiÕp c¸c tÝnh chÊt4, 1,3 ,vµ 2. Nãi chung, b»ng c¸ch ¸p dông 4 tÝnh chÊt trªn, cã thÓ tÝnh to¸nkÝ m hiÖu Jacobi trong thêi gian ®a thøc. C¸c phÐp tÝnh sè häc dïng ë ®©y  n chØ lµ rót gän theo modulo vµ ph©n tÝch ra c¸c luü thõa cña thuËt to¸n ®îc biÓu diÔn díi d¹ng nhÞ ph©n th× viÖc ph©n tÝch ra c¸c luü thõa cña hai sè chÝnh lµ viÖc x¸c ®Þnh sè c¸c sè 0 tiÕp sau. Bëi vËy, ®é phøc t¹p cña thuËt to¸n ®îc x¸c ®Þnh bëi sè c¸c phÐp rót gän theo modulo cÇn tiÕn hµnh. Kh«ng khã kh¨n l¾m cã thÓ chøng tá r»ng, cÇn thùc hiÖn nhiÒu nhÊt lµ.  9283   7411  theo tÝnh chÊt 4       7411   9283   1872  = theo tÝnh chÊt 1  
O(log n) phÐp rót gän theo modulo. Mçi phÐp cã thÓ thùc hiÖn trong thêi gian O((log n)2). §iÒu ®ã chøng tá r»ng, ®é phøc t¹p lµ O((log n)3) lµ ®a thøc theo log n. Thùc ra b»ng c¸c ph©n tÝch chÝnh x¸c h¬n, cã thÓ chøng tá r¨ng, ®é phøc t¹p chØ cì O((log n)2). Gi¶ sö ta ®· t¹o ®îc mét sè ngÉu nhiªn n vµ ®· kiÓm tra tÝnh nguyªn tè cña nã theo thuËt to¸n Soloway- Strasen. NÕu ch¹y thuËt to¸n m lÇn th× c©u tr¶ lêi “ n lµ mét sè nguyªn tè” sÏ cã møc ®é tin cËy nh thÕ nµo? Qu¶ lµ liÒu lÜnh nÕu coi r¨ng, x¸c suÊt nµy lµ 1-2-m. KÕt luËn nµy thêng ®îc nªu trong c¸c gi¸o tr×nh vµ bµi b¸o kÜ thuËt, tuy nhiªn ta kh«ng thÓ dÉn ra theo c¸c sè liÖu cho tríc. CÇn ph¶i thËn träng h¬n khi sù dông c¸c tÝnh to¸n x¸c suÊt. Ta sÏ ®Þnh nghÜa c¸c biÕn ngÉu nhiªn sau: a- ChØ sù kiÖn “ sè nguyªn lÎ n cã kÝch thíc ®· ®Þnh lµ mét hîp sè”. b- ChØ sù kiÖn “ thuËt to¸n tr¶ lêi n lµ sè nguyªn tè m lÇn liªn tiÕp . §iÒu ch¾c ch¾n lµ prob(b a)2-m. Tuy nhiªn x¸c suÊt mµ ta thùc sù quan t©m lµ prob(a/b), x¸c suÊt nµy thêng kh«ng gièng nh prob(b/a). Cã thÓ tÝnh prob(a/b) b»ng ®Þnh lý Bayes (®Þnh lý2.1). Tríc hÕt cÇn ph¶i biÕt prob(a). Gi¶ sö N  n  2N. ¸p dông ®Þnh lý vÒ sè nguyªn tè: c¸c sè nguyªn tè(lÎ) giöa N vµ 2N xÊp xØ b»ng:
2N/ln 2N – N/ln N  N/ ln N  n/ln n ` V× cã N/2  n/2 sè nguyªn tè lÎ giöa N vµ 2N, ta sÏ dïng íc lîng Prob(a)  1 – 2/ln n Sau ®ã cã thÓ tÝnh to¸n nh sau: prob(b a) prob(a) prob(a b) = prob(b) prob(b a) prob(a) = prob(b a )prob(a)  prob(b a )prob(a)  = Chó ý r»ng trong tÝnh to¸n trªn ? chØ sù kiÖn “sè nguyªn lÎ ngÉu nhiªn n lµ mét sè nguyªn tè”. Kh¸ thó vÞ nÕu so s¸nh hai hµm sau cña m ????/ Gi¶ sù n  2256  e177 (®©y lµ kÝch thíc cña c¸c sè nguyªn tè sù dông trong hÖ mÆt RSA). Khi ®ã hµm ®Çu tiªn xÊp xØ b»ng????. Ta sÏ lËp b¶ng cho hai hµm øng víi mét sè gi¸ trÞ cña m (xem h×nh4.8). H×nh 4.8. C¸c x¸c suÊt sai ®èi víi phÐp kiÓm tra Solovay- Strasen 2- m M
1 0,500 0,978 2 0250, 0,956 0,312.10-1 5 0,732 0,977.10-3 0,787.10- 10 0,954.10-6 0,834.10-4 20 0,930.10-9 0,815.10-7 30 0,888.10-15 0,777.10-13 50 0,789.10-30 0,690.10-28 100 MÆc dï????? tiÕn tíi o kh¸ nhanh theo hµm mò nhng vÉn kh«ng tiÕn nhanh b»ng 2-m. Tuy nhiªn, nÕu lÊy m vµo cì 50 hoÆc 100 th× c¸c x¸c suÊt sai ®ã cïng qui vÒ mét lîng rÊt nhá. PhÇn nµy sÏ kÕt thóc b»ng mét thuËt to¸n Monte- Carlo kh¸c cho bµi to¸n hîp sè, ®ã lµ thuËt to¸n Miller- Rabin (M-R) (®îc coi lµ mét phÐp kiÓm tra gi¶ nguyªn tè m¹nh). ThuËt to¸n ®îc m« t¶ trong h×nh 4.9. §©y l¸ mét thuËt to¸n víi thêi gian ®a thøc: ®é phøc t¹p cña nã cì O((log n)3) t¬ng tù nh thuËt to¸n S-S Thùc ra trong thøc tÕ thuËt to¸n M-R thùc hiÖn tèt h¬n thuËt to¸n S-S. B©y giê chóng ta sÏ chØ ra r»ng thuËt to¸n nµy kh«ng thÓ lêi “n lµ mét hîp sè ” nÕu n lµ sè nguyªn tè, tøc nã lµ mét thuËt to¸n ®Þnh híng “cã” . §Þnh lý 4.10 thuËt to¸n Miller – Rabin vÒ c¸c hîp sè lµ thuËt to¸n monte-carlo ®Þnh híng “cã “ H×nh 4.9 ThuËt to¸n kiÓm tra tÝnh nguyªn tè Miller-rabin víi sè nguyªn lÎ n 1. ViÕt n-1=2km, trong ®ã m lµ mét sè lÎ 2. Chän sè nguyªn ngÉu nhiªn a, 1  a  (n-1 ) 3. TÝnh b=am mod n 4. IF b1 (mod n) then Tr¶ lêi “ n lµ sè nguyªn tè “ vµ quit 5. For I=0 to k-1 do 6. IF b-1 (mod n) then Tr¶ lêi “n lµ sè nguyªn tè “ vµ quit Else b=b2 mod n 7.Tr¶ lêi “ n lµ hîp sè “
Chøng minh: Ta sÏ chøng minh b»ng c¸ch gi¶ sö thuËt to¸n tr¶ lêi “ n lµ hîp sè” víi sè nguyªn tè n nµo ®ã vµ nh©n ®îc m©u thuÉt. V× thuËt to¸n tr¶ lêi “ nlµ hî sè “ nªn ch¾c ch¾n lµ am  1(mod n). B©y giê xÐt d·y c¸c gi¸ trÞ b ®îc kiÓm tra trong bíc 2 cña thuËt to¸n .V× b ®îc b×nh ph¬ng trong mçi phÐp lÆp cña vßng For nªn ta sÏ kiÓm tra c¸c gi¸ trÞ am , a2m ,,a2k-1m. V× thuËt to¸n tr¶ lêi “n lµ hîp sè” nªn suy ra: A2m  -1 (mod n) Víi 0  i  k-1 B©y giê sö dông gi¶ thiÕt n lµ sè nguyªn tè. Theo ®Þnh lý Ferma (hÖ qu¶ 4.6) ta cã A2km  1 (mod 1) V× n-1 = 2km. Khi ®ã a2k-1m lµ c¨n bËc hai cña mét modulo n =  1 mod n. §iÒu nµy cã thÓ thÊy râ nh sau: x lµ c¨n bËc hai cña 1 theo modulo n khi vµ chØ khi n(x-1)(x+1) V× n lµ mét sè nguyªn tè nªn hoÆc n(x-1)(tøc lµ x1 modun) hoÆc n(x+1) (tøc lµ x-1 modun) Ta ®· cã a2k-1m  -1(mod n) bëi vËy ta ph¶i cã: a2k-1m  1(mod n) Khi ®ã a2k-2m ph¶i lµ c¨n bËc hai cña 1. B»ng lËp luËn t¬ng tù: A2k-1m  1(mod n) ®iÒu nµy lµ m©u thuÉn, bëi vËy trong trêng hîp nµy thuËt to¸n ph¶i cã c©u tr¶ lêi “n lµ sè nguyªn tè”. Cßn mét vÊn ®Ò cha cha ®îc xem xÐt lµ x¸c xuÊt sai cña thuËt to¸n M-R. MÆc dï kh«ng chøng minh ë ®©y nhng cã thÓ chøng tá ®îc r»ng x¸c xuÊt nµy nhiÒu nhÊt lµ ¼.
4.6 C¸c ph¬ng ph¸p tÊn c«ng hÖ mËt rsa Trong phÇn nµy ta sÏ lu t©m ®Õn vÊn ®Ò:LiÖu cã c¸c ph¬ng ph¸p tÊn c«ng RSA kh¸c víi ph¬ng ph¸p ph©n tÝch n kh«ng ? tríc tiªn ta thÊy r»ng th¸m m· chØ cÇn tÝnh ®îc (n) lµ ®ñ. NÕu ®· biÕt n vµ (n) vµ n lµ tÝch cña 2 sè nguyªn tè p vµ q th× cã thÓ dÔ dµng ph©n tÝch ®îc n b»ng c¸ch gi¶i 2 ph¬ng tr×nh sau ®Ó t×m hai sè p vµ q cha biÕt: n=pq (n)=(p-1)(q-1) NÕu thay q=n/p vµ ph¬ng tr×nh thø 2 th× ta sÏ thu ®îc ph¬ng tr×nh bËc 2 cña biÕn cha biÕt p : P2-(n-(n) + 1)p + n=0 Hai nghiÖmncña ph¬ng tr×nh nµy lµ p vµ q lµ c¸c nh©n t÷ cña n. Bëi vËy th¸m m· biÕt ®îc (n) th× anh ta cã thÓ ph©n tÝch ®îc n vµ ph¸ ®îc hÖ mËt.Nãi c¸ch kh¸c, viÖc tÝnh (n) kh«ng dÔ h¬n viÖc ph©n tÝch n.Sau ®©y lµ mét vÝ dô dô minh ho¹ : VÝ dô 4.9 Gi¶ sö th¸m m· ®¶ biÕt r»ng n=84773093 vµ (n)= 4754668. Th«ng tin nµy sÏ dÉn tíi ph¬ng tr×nh: P2-18426p+84773093=0 Gi¶i ph¬ng tr×nh nµy thu ®îc hai nghiÖm 9539 vµ 8887.§©y lµ hai thõa sè cña n. 4.6.1 Sè mò gi¶i m· B©y giê chóng ta sÏ chøng minh mét kÕt qu¶ rÊt thó vÞ lµ mét thuËt to¸n bÊt kú ®Ó tÝnh sè mò gi¶i m· a ®Òu cã thÓ ®îc dïng nh mét ch¬ng tr×nh con (hay mét ®iÒu kiÖn )trong thuËt to¸n x¸c suÊt ph©n tÝch n .Bëi vËy viÖc tÝnh a sÏ kh«ng dÔ h¬n viÖc ph©n tÝch n.Tuy nhiªn, cã mét ®iÒu kh«ng ngoµi quy luËt lµ ta vÉn cã thÓ ph¸ hÖ mËt mµ kh«ng cÇn tÝnh a.
KÕt qu¶ nµy cã ý nghÜa nhiÒu h¬n vÒ mÆt lý thuyÕt .Nã cho thÊy r»ng nÕu a bÞ lé th× gi¸ trÞ m còng kh«ng cßn khã ph©n tÝch n÷a.NÕu ®iÒu nµy xÈy ra th× viÖc Bob chän mét sè mò míi còng ch¼ng cã ý nghÜa; §iÒu cÇn thiÕt lµ Bob ph¶i chän l¹i n. ThuËt to¸n mµ ta sÏ m« t¶ lµ mét thuËt to¸n x¸c suÊt kiÓu las vegas.Sau ®©y lµ ®Þnh nghÜa cña kiÓu thuËt to¸n nµy. §Þnh nghÜa 4.5 Gi¶ sö 0   1 lµ mét sè thùc.ThuËt to¸n las vegas lµ mét thuËt to¸n x¸c suÊt cao cho víi mét trêng hîp bÊt kú cña bµi to¸n I, thuËt to¸n cã thÓ kh«ng cho kÕt qu¶ víi mét x¸c suÊt  nµo ®ã (ch¼ng h¹n thuËt to¸n cã thÓ kÕt thóc víi th«ng b¸o “ kh«ng tr¶ lêi”).Tuy nhiªn, nÕu thuËt to¸n cho lêi gi¶i th× lêi gi¶i nµy lµ ®óng . Nh©n xÐt:ThuËt to¸n las vegas cã thÓ kh«ng cho c©u tr¶ lêi nhng mét c©u tr¶ lêi bÊt kú mµ thuËt to¸n cho lµ ®Òu lµ c©u tra lêi ®óng.Ngîc l¹i, thuËt to¸n monte-carlo lu«n lu«n cho c©u tr¶ lêi nhng c©u trµ lêi nµy cã thÓ lµ sai. NÕu ta cã mét thuËt to¸n las vegas ®Ó gi¶i mét bµi to¸n th× ®¬n gi¶n ta chØ ch¹y lÆp ®i lÆp l¹i thuËt to¸n nµy cho tíi khi nã t×m ra mét c©u tr¶ lêi.X¸c suÊt ®Ó thuËt to¸n kh«ng tr¶ lêi sau m lÇn liªn tiÕp lµ m.Sè lÇn ch¹y trung b×nh ®Ó thu ®îc c©u tra lêi thùc tÕ lµ 1/ (Xem c¸c bµi tËp ). Gi¶ sö A lµ mét thuËt to¸n gi¶ ®Þnh tÝnh sè mò gi¶i m· a tõ b. Ta sÏ m« t¶ mét thuËt to¸n las vegas dïng A nh mét ch¬ng tr×nh gi¶ ®Þnh (oracle) con.ThuËt to¸n sÎ ph©n tÝch n víi x¸c suÊt tèi thiÓu lµ 1/2.Bëi vËy nÕu thuËt to¸n ch¹y m lÇn th× n sÏ ®îc ph©n tÝch víi x¸c suÊt tèi thiÓu lµ 1-1/2m. ThuËt to¸n ®îc x©y dùng trªn c¬ së mét sè nguyªn tè nhÊt ®Þnh liªn quan tíi c¸c c¨n bËc 2 cña mét theo modulo n, trong ®ã n=pq lµ tÝch cña hai sè nguyªn tè lÎ ph©n biÖt ta biÕt r»ng ph¬ng tr×nh ®ång d X2 1( mod p) cã hai nghiÖm theo modulo p lµ X=1 mod p .T¬ng tù, ph¬ng tr×nh ®ång d X21(mod q) còng cã hai nghiÖm lµ X=1 mod q .
V× X2 1 (mod n) khi vµ chØ khi X21 (mod p) vµ X21 (mod q) nªn suy ra X2 1 (mod n) khi vµ chØ khi X= 1 mod p vµ X=1 mod q.Bëi vËy cã 4 c¨n bËc 2 cña 1 theo modulo n vµ c¸c c¨n nµy cã thÓ t×m ®îc th«ng qua ®Þnh lý phÇn d china.Hai trong c¸c nghiÖm nµy lµ X=1 mod n; chóng ®îc gäi lµ c¸c c¨n bËc hai tÇm thêng vµ lµ c¸c gi¸ trÞ ®èi cña nhau theo modulo n. Sau ®©y lµ mét vÝ dô dô nhá ®Ó minh ho¹ : VÝ dô 4.10 Gi¶ sö n=403=13 11.Bèn c¨n bËc hai cña mét theo modulo 403 lµ 1,92,311 vµ 402.C¨n bËc hai 92 nhËn ®îc b»ng c¸ch gi¶i hÖ X1 (mod 13) , X-1 (mod 31) theo ®Þnh lý phÇn d china.NÕu t×m ®îc kh«ng tÇm thêng nµy, nghiÖm kh«ng tÇm thêng kia ph¶i lµ 403-92=311.§ã lµ nghiÖm cña hÖ X-1(mod 13), X1 (mod 31). Gi¶ sö X lµ c¨n bËc hai kh«ng tÇm thêng cña 1 modulo n. Khi ®ã ta cã n(x-1)(x+1) nhng n kh«ng lµ íc cña mét nh©n tö nµo ë vÕ ph¶i .§iÒu ®ã kÐo theo UCLN (X+1,n) = p hoÆc q(vµ t¬ng tù UCLN(X-1,n)=p hoÆc q).TÊt nhiªn cã thÓ tÝnh UCLN b»ng thuËt to¸n Euclide mµ kh«ng cÇn ph¶i biÕt ph©n tÝch nh©n tö cña n.Bëi vËy, hiÓu biÕt vÒ c¨n bËc hai kh«ng tÇm thêng cña 1 mod n sÏ lµm cho viÖc ph©n tÝch n chØ cÇn thùc hiÖn trong thêi gian ®a thøc. Trong vÝ dô dô 4.10 ë trªn, UCLN (93,403) =31 vµ UCLN (312,403)=13 Trªn h×nh 4.10 tr×nh bµy thuËt to¸n (dïng thuËt to¸n gi¶ ®Þnh A lµm ch¬ng tr×nh con) ®Ó ph©n tÝch n b»ng c¸ch t×m mét c¨n bËc hai kh«ng tÇm thêng cña 1 modulo n (A thùc hiÖn tÝnh sè mò gi¶i m· a theo sè mò m· b ).Tríc tiªn ta sÏ ®a ra mét vÝ dô ®Ó minh ho¹ cho viÖc ¸p dông thuËt to¸n nµy. vÝ dô 4.11 Gi¶ sö n=89855713, b=34986517 vµ a=82330933 vµ gi¸ trÞ ngÉu nhiªn w=5.Ta cã : ab-1=23.360059073378795
trong bíc 6, v=85877701 cßn ë bíc 10 , v=1.Trong bíc 12 ta tÝnh UCLN (85877702,n)=9103. §©y lµ mét thõa sè cña n; thõa sè kia lµ n/9103=9871. B©y giê sÏ tiÕn hµnh ph©n tÝch thuËt to¸n.Tríc tiªn, nh©n thÊy r»ng nÕu ta may m¾n chän ®îc w lµ béi cña p hoÆc q th× cã thÓ ngay lËp tøc ph©n tÝch ®îc n.§iÒu nµy ®îc biÓu thÞ ë bíc 2. NÕu nguyªn tè cïng nhau víi n th× chóng ta sÏ tÝnh w r , w2r, w4r,…,B»ng c¸ch b×nh ph¬ng liÖn tiÕp cho tíi khi W2r 1 (mod n) Víi gi¸ trÞ t nµo ®ã.V× Ab-1=2sr0 (mod (n)) H×nh 4.10 ThuËt to¸n ph©n tÝch thõa sè (cho tríc sè mò gi¶i m· a). 1. Chän w ngÉu nhiªn sao cho 1 w  n-1 2. TÝnh x=UCLN(w,n) 3. IF 1 < x < n then quit (thµnh c«ng :x=p hoÆc x=q) 4. TÝnh a=A(b) 5. ViÕt ab-1=2sr, r Lî 6. TÝnh v=wr mod n 7. IF v=1 (mod n) then quit (kh«ng thµmh c«ng) 8. While v  1 (mod n) do 9. V0=v v=v2 mod n 10. 11. If v0 -1 (mod n) then Quit (kh«ng thµnh c« g) Else TÝnh x=UCLN(v0+1,n) (thµnh c«ng :x=p hoÆc x=q) NÕu ta cã W2r1(mod n) .Bëi vËy, vßng lÆp while sÏ kÕt thóc sau nhiÒu nhÊt lµ s bíc lÆp .kÕt thóc vßng lÆp, ta t×m ®îc mét gi¸ trÞ v0 sao cho v021 (mod n) nhng v0 1 (mod n) .NÕu v0-1 (mod ,n ) th× thuËt to¸n kh«ng thµnh c«ng ; ngîc l¹i , v0 sÏ lµ mét c¨n bËc
hai kh«ng tÇm thêng cña 1 modulo n vµ ta ph©n tÝch ®îc n (bíc 12 ). NhiÖm vô chÝnh cßn l¹i b©y giê lµ ph¶i chøng minh r»ng, thuËt to¸n thµnh c«ng víi x¸c suÊt lµ ½ .Cã hai c¸ch mµ theo ®ã thuËt to¸n cã thÓ kh«ng thµnh c«ng khi ph©n tÝch n : 1.Wr1 (mod n) (bíc 7) 2.W2r-1 ( mod n ) víi gi¸ trÞ t nµo ®ã , 0  t  s-1 (bíc 11) Chóng ta cã n+1 ph¬ng tr×nh ®ång d ®Ó xem xÐt.NÕu gi¸ trÞ ngÉu nhiªn w lµ mét nghiÖm cña Ýt nhÊt mét trong c¸c ®ång d thøc nµy th× phÐp lùa chän w nµy lµ “tåi” vµ thuËt to¸n sÏ kh«ng thµnh c«ng .Bëi vËy, ta sÏ chuyÓn sang tÝnh sè c¸c nghiÖm cña mçi ®«ng d thøc nµy. Tríc tiªn xÐt ®ång d thøc wr1 (md n).Ph¬ng ph¸p ph©n tÝch mét ®ång d thøc gièng nh c¸ch xem xÐt mét c¸ch riªng rÎ c¸c nghiÖm theo modulo q .Sau ®ã kÕt hîp chóng nhê ®Þnh lý phÇn d China . CÇn ®Ò ý r»ng x1 (mod n) khi vµ chØ khi x1 (mod p) vµ x1 (mod q). Nh vËy, tríc hÕt ta ph¶i xÐt wr1 (mod n) .V× p lµ mét sè nguyªn tè nªn z*p lµ mét nhãm cyclic theo ®Þnh lý 4.7.Gi¶ sö g lµ mét phÇn tö nguyªn thuû theo modulo p.Ta cã thÓ viÕt w=gu víi sè nguyªn duy nhÊt u nµo ®ã, 0  u  p-2. Khi ®ã ta cã : r W 1(mod p) gur1 (mod p) (p-1) ur Gi¶ sö ta biÓu diÔn p-1=2ip1 trong ®ã p1 lµ mét sè lÎ vµ q-1 =2jq1, q1 lµ mét sè lÎ. V× (n)=(p-1)(q-1) (ab-1)=2sr Nªn ta cã 2i+jp1q12sr Bëi vËy: i+j s
Vµ P 1 q1  r B©y giê ®iÒu kiÖn p-1  ur sÎ trë thµnh 2ip1 ur. V× p1r vµ r lÎ nªn ®iÒu kiÖn cÇn vµ ®ñ lµ 2iu.V× thÕ, u=k. 2i, 0 k  p1-1 vµ sè c¸c nghiÖm cña d thøc wr1 (mod p) sÎ lµ p1. B»ng lËp luËn t¬ng t, ta thÊy ®ång d thøc w r 1 (mod q) sÎ cã ®óng q1 nghiÖm.Cã thÓ kÕt hîp nghiÖm bÊt kú theo modulo p víi nghiÖm bÊt kú theo modulo q ®Ó thu ®îc mét nghiÖm duy nhÊt theo modulo n nhê ®Þnh lý phÇn d China. Do vËy sè c¸c nghiÖm cña ®ång d thøc wr1 (mod n ) sÎ lµ p1q1. TiÕp theo, xÐt ®ång d thøc w2r 1(mod n) víi gi¸ trÞ t cè ®Þnh (trong ®ã : 0  t  s-1). Tríc tiªn l¹i xÐt ®ång d thøc theo modulo p råi sau ®o xÐt theo modulo q. (§Ó ý r»ng, ???-1 (mod n) khi vµ chØ khi w2r-1 (mod p) vµ t t w 2 r  1mod q  . §Çu tiªn ta xÐt w 2 r  1mod q  nÕu viÕt nh ë phÇn t g 0 2 r  1mod q  trªn ta nhËn ®îc V× g(p-1)/2 -1(mod p) nªn ta cã u2tr (p-1)/2( mod p-1) (p-1) │ (u2tr-(p-1)/2) 2(p-1)│ (u2t+1r-(p-1)) V× p-1=2ip1 nªn ta nhËn ®îc 2i+2 p1 │ u 2t+1r-2ip1) Loai bá thõa sè chung ta cã u 2 i 1 r  1 i 2i+1 │ (u -2 ) p1 XÐt thÊy nÕu t  i th× cã thÓ lµ kh«ng cã nghiÖm do 2i+1 │ 2t+1 nhng 2i+1 │ 2i MÆt kh¸c nÕu t  i -1 th× u sÏ lµ mét nghiÖm khi vµ chØ khi u lµ béi lÎ cña 2i-t-1 . (chó ý r»ng r/p1 lµ mét sè nguyªn lÎ). Bëi vËy, sè c¸c nghiÖm trong trênh hîp nµy lµ
p 1 1  = 2 t p1 i t 1 2 2 i T¬ng tù, ®ång d thøc w 2 r  1 (mod q) sÏ : - Kh«ng cã nghiÖm nÕu t  j - Cã 2tq1 nghiÖm nÕu t  j-1 Tõ ®Þnh lý phÇn d China ta sÏ thÊy r»ng sè c¸c nghiÖm cña i w 2 r  1mod n  lµ - 0 nÕu t  min{ i, j} - 22t p1q1 nÕu t  min{i, j )  1 t cã thÓ n»m trong d¶i tõ 0 tíi s-1. Kh«ng mÊt tÝnh tænh qu¸t gi¶ sö i  j; khi ®ã sè c¸c nghiÖm sÏ b»ng 0 nÕu t  i . Tæng sè c¸c lùa chän”tåi” cña w nhiÒu nhÊt lµ 2 2i  1 2 4 2i-1) p1q1+p1q1(1+2 +2 ++2 = p1q1(1+ ) 3  2 2 2i  = p1q1    3 3    §Ó ý lµ p-1 = 2ip1 cßn q-1=2jq1. B©y giê gi¶ sö j  i 1 khi ®ã p1q1
thÊp cña x. 2. Cho y=eK(x), h·y tÝnh half(y) trong ®ã half(y)=0 nÕu 0  x  n / 2 vµ half(y)=1 nÐu n / 2  x  n  1 Ta sÏ chøng minh r»ng víi y=eK(x) cho tríc mét thuËt to¸n bÊt kú tÝnh parity(y) hoÆc half(y) ®Òu cã thÓ ®îc dïng nh mét ch¬ng tr×nh con ®Ó x©y dùng mét thuËt to¸n tÝnh b¶n x. §iÒu ®ã cã nghÜa lµ, víi mét b¶n m· cho tríc, viÖc tÝnh bit bËc thÊp cña b¶n râ sÏ t¬ng ®¬ng ®a thøc víi viÖc x¸c ®Þnh toµn bé b¶n râ ! Tríc hÕt, ta sÏ chøng minh r»ng, viÖc tÝnh parity(y) lµ t¬ng ®¬ng ®a thøc víi viÖc tÝnh half (y). §iÒu nµy rót ra tõ hai ®ång nhÊt thøc ®¬n gi¶n sau (xÐt bµi tËp ): halt(y)=parity(y x eK(2) mod n) (4.1) parity(y)=half(y x eK(2-1)mod n) (4.2) vµ tõ quy t¾c nhËn eK(x1) eK(x2)=eK(x1x2) Ta sÏ chØ ra c¸ch tÝnh x=dK(y) theo mét thuËt to¸n gi¶ ®Þnh cho tríc ®Ó tÝnh half(y). ThuËt to¸n ®îc tr×nh bµy trªn h×nh 4.11 .Trong c¸c bíc 2.4 ta tÝnh : yi = half(y x (eK(2))I)=half(eK(x x2i)) víi 0  x  log 2 n . NhËn thÊy r»ng: n half (eK(x))= 0  x  0,   2   n n 3n half(eK(2x)=0  x  0,  U  ,   4  2 4     n n 3n  n 5n  3n 7 n half(eK(4x))= 0  x  0, U  , U  , U  , ...... 4 8   8 4 8  2 8       Bëi vËy ta cã thÓ t×m theo kü thuËt t×m t×m kiÕm nhÞ ph©n (®îc lµm trong c¸c bíc 7-11). Díi ®©y lµ mét vÝ dô nhá ®Ó minh ho¹ VÝ dô 4.12
Gi¶ sö n=1457, b=779 vµ ta cã b¶n m· y=772. eK(2) ®îc tÝnh b»ng 946. Gi¶ giö r»ng (sö dông thuËt to¸n gi¶ ®Þnh ®èi víi half(y)) . ta nhËn ®îc c¸c gi¸ trÞ yi sau theo bíc 3 thuËt to¸n: H×nh 4.11.Gi¶ m· b¶n m· RSA víi mét thuËt to¸n gi¶ ®Þnh tÝnh half(y) cho tríc 1. Ký hiÖu k=│log2 n │ 2. For i=0 to k do yi =half(y) 3. y=(y* eK(2)) mod 2 4. lo=0 5. hi=n 6. 7. for i=0 to k do mid=(hi+lo)/2 8. IF yi=1 then 9. lo=mid else hi=mid 10. x=│hi│