intTypePromotion=1
zunia.vn Tuyển sinh 2023 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

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

Thêm vào BST
Báo xấu
112
lượt xem 22
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 41', 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 41

  1. 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 
  2. ®î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 
  3. 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  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.
  4. 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)
  5.  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.
  6.  a    p   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.  a Gi¶ sö n lµ mét sè nguyªn d¬ng lΠvµ ph©n     r 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.
  7.  a    n Gi¶ sö n > 1 lµ mét sè lÎ. NÕu n lµ mét  sè nguyªn tè th×            ≡   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 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 ≤  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.
  8.        1. Chän mét sè nguyªn ngÉu nhiªn a, 1 ≤  a ≤  n­1   2. NÕu          ≡  a(n­1)/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  m   1  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 
  9. 4. Gi¶  sö m vµ  n lµ c¸c sè nguyªn lÎ, khi  ®ã:    n      −      u ≡ n ≡ 3 m od4)        m nÕ 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.  7411  9283    = −        theo tÝnh chÊt 4  9283  7411  Nãi chung, b»ng c¸ch ¸p dông 4 tÝnh chÊt  trªn, cã thÓ tÝnh to¸nkÝ   1872 =   −            theo tÝnh chÊt 1 m   7411 hiÖu Jacobi     trong thêi gian ®a thøc. C¸c  4  n  2   117             theo tÝnh  . =   −  phÐp tÝnh sè häc dïng ë ®©y      7411  7411  chÊt 3 chØ lµ rót gän theo modulo vµ ph©n tÝch ra c¸c   117  luü thõa cña thuËt to¸n ®îc biÓu diÔn díi d¹ng  =  −                         theo   7411 nhÞ ph©n th× viÖc ph©n tÝch ra c¸c luü thõa  tÝnh chÊt 2 cña hai sè chÝnh lµ viÖc x¸c ®Þnh sè c¸c sè 0   7411 =  −                        theo tÝnh  tiÕp sau. Bëi vËy, ®é phøc t¹p cña thuËt to¸n   117  ®îc x¸c ®Þnh bëi sè c¸c phÐp rót gän theo  chÊt 4 modulo cÇn tiÕn hµnh. Kh«ng khã kh¨n l¾m cã   40  =   −                         theo  thÓ chøng tá r»ng, cÇn thùc hiÖn nhiÒu nhÊt   177 lµ. 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
  10. 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 .
  11. §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(a|  b) =  ????       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 ????/
  12. pr ba)pr a) ob(   ob( pr b) ob( 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 Mob(   2 pr ba)pr a) ob( 1 pr 0,500 ob(b) 0,978 2 0250, 0,956 5 0,312.10­1 0,732 10 0,977.10­3 0,787.10­ 20 0,954.10­6 0,834.10­4 30 0,930.10­9 0,815.10­7 50 0,888.10­15 0,777.10­13 10 0,789.10­30 0,690.10­28 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 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è 
  13. ” 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 , 
  14. 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ã                                              A 2km  ≡  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è”.
  15.      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µ 1/4.   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Öm cñ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:
  16.             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 
  17. 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.
  18.        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
  19. 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×                                   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) s 5. ViÕt ab­1=2 r, r Lî r 6. TÝnh v=w  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
  20. 10.           v=v2 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.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ý 
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2