Mật mã cổ điển- Chương 4

Chia sẻ: Son Cung | Ngày: | Loại File: DOC | Số trang:33

Thêm vào BST

Báo xấu

178
lượt xem 61
download

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

Tham khảo tài liệu 'mật mã cổ điển- chương 4', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

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

Lưu

Nội dung Text: Mật mã cổ điển- Chương 4

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 MonteCarlo ®Þ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 ≤ p1 C©u hái: x cã ph¶i lµ thÆng d bËc hai phÐp MÆc dï thuËt to¸n MillerRabin (ta sÏ xÐt sau) nhanh h¬n thuËt to¸n SolowayStrasson (S S) nhng ta sÏ xÐt thuËt to¸n SS 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 ≤ p1. 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(p1)/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× xp1≡ 1 (mod p) víi mäi x ≡ 0 (mod p). Bëi vËy ta cã : x(p1)/2 ≡ (y2)(p1)/2 (mod p) ≡ yp1(mod p) ≡ 1 (mod p) Ngîc l¹i, gi¶ sö r»ng x(p1)/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(p1)/2 ≡ (bi)(p1)/2 (mod p) ≡ bi(p1)/2(mod p)
V× p cã bËc b»ng p1 nªn p1 ph¶i lµ íc cña i(p1)/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(p1)/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(p1)/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(p1)≡ 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. Gi¶ sö p lµ mét sè nguyªn tè. Khi ®ã a    p ≡ a(p1)/2 (mod p).    a    r
 a    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. Ký hiÖu Jacobi ®îc ®Þnh nghÜa nh sau: ei   a K  a   = ∏   n  i 1 pi =   VÝ dô 4.7.  6278   XÐt ký hiÖu Jacobi . Ph©n  9975 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    n a(n1)/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 thøc trªn cã thÓ ®óng  a   hoÆc kh«ng. NÕu ph¬ng tr×nh ®ã vÉn ®óng th× a  n ®î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 ≤ n1) 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 MonteCarlo ®Þ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(n1)/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è SolovaStrassen víi sè nguyªn lÎ n.
1. Chän mét sè nguyªn ngÉu nhiªn a, 1 ≤ a ≤ n1 2. NÕu ≡ a(n1)/2 (mod n) th× Tr¶ lêi “ n lµ sè nguyªn tè ” NÕu kh«ng  a   Tr¶ lêi “ n lµ mét hîp sè ”  n 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×:  m 1 m 2     =  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 1m 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 −   u ≡ n ≡ 3 m od4)  mnÕ m (      2 =  n  r c rêng p ¹    tongc¸ t hî cßnli    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    9283 ®©y. CÇn chó ý lµ trong vÝ 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  7411  9283  trªn, cã thÓ tÝnh to¸nkÝ theo tÝnh chÊt 4   = −   9283  7411  m  hiÖu Jacobi 1872   trong thêi gian ®a thøc. C¸c  n= −      theo tÝnh chÊt 1 phÐp tÝnh sè häc dïng ë ®©y  7411 4 . = −  2   117  theo tÝnh chØ lµ rót gän theo modulo vµ ph©n tÝch ra c¸c      7411  7411  luü thõa cña thuËt to¸n ®îc biÓu diÔn díi d¹ng chÊt 3 nhÞ ph©n th× viÖc ph©n tÝch ra c¸c luü thõa  117  cña hai sè chÝnh lµ viÖc x¸c ®Þnh sè c¸c sè 0 = −   theo  7411 tiÕp sau. Bëi vËy, ®é phøc t¹p cña thuËt to¸n tÝnh chÊt 2 ®îc x¸c ®Þnh bëi sè c¸c phÐp rót gän theo  7411 = −  modulo cÇn tiÕn theo tÝnh  hµnh. Kh«ng khã kh¨n l¾m cã  117  thÓ chøng tá r»ng, cÇn thùc hiÖn nhiÒu nhÊt chÊt 4 lµ.  40  = −   theo  177 tÝnh chÊt 1 2 3  5  = −      theo tÝnh  117  117  chÊt 3  5  =   theo  117 tÝnh chÊt 2  117
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µ 12m. 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: aChØ sù kiÖn “ sè nguyªn lÎ n cã kÝch thíc ®∙ ®Þnh lµ mét hîp sè”. bChØ 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)2m. 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: pr ba)pr a) ob( ob( prob(a| b) = pr b) ob( pr ba)pr a) ob( ob( = pr ba) ob( + pr ba) ob() ob( pr a) ob( pr a ≈ = pr ba)pr a) ob( ob( pr ba) ob( + pr ba) ob() ob( pr a) ob( pr 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 M 2m 1 0,500 0,978 2 0250, 0,956 5 0,312.101 0,732 10 0,977.103 0,787.10 20 0,954.106 0,834.104 30 0,930.109 0,815.107 50 0,888.1015 0,777.1013 10 0,789.1030 0,690.1028 0 MÆc dï????? tiÕn tíi o kh¸ nhanh theo hµm mò nhng vÉn kh«ng tiÕn nhanh b»ng 2m. 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 (MR) (®î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 SS Thùc
ra trong thøc tÕ thuËt to¸n MR thùc hiÖn tèt h¬n thuËt to¸n SS. 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 montecarlo ®Þnh híng “cã “ H×nh 4.9 ThuËt to¸n kiÓm tra tÝnh nguyªn tè Millerrabin víi sè nguyªn lÎ n 1. ViÕt n1=2km, trong ®ã m lµ mét sè lÎ 2. Chän sè nguyªn ngÉu nhiªn a, 1 ≤ a ≤ (n1 ) 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 k1 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µ a m ≡ 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 ,…,a2k1m. 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 ≤ k1 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ã A 2km ≡ 1 (mod 1) V× n1 = 2km. Khi ®ã a2k1m 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 (x1) (x+1) V× n lµ mét sè nguyªn tè nªn hoÆc n (x1)(tøc lµ x≡ 1 modun) hoÆc n(x+1) (tøc lµ x≡ 1 modun) Ta ®∙ cã a 2k1m ≡ 1(mod n) bëi vËy ta ph¶i cã: a 2k 1m ≡ 1(mod n) Khi ®ã a2k2m 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 MR. 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)=(p1)(q1) 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:
P218426p+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 montecarlo 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µ 11/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µ 40392=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(x1)(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(X1,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ã : ab1=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 wr , 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× Ab1=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 ≤ n1 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) s 5. ViÕt ab1=2 r, 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 2 10. v=v mod n 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.W r≡ 1 (mod n) (bíc 7) 2.W2r≡ 1 ( mod n ) víi gi¸ trÞ t nµo ®ã , 0 ≤ t ≤ s1 (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.