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

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

0
147
lượt xem
54
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  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. Gi¶   sö   p   lµ   mét   sè   nguyªn   tè.   Khi   ®ã  a    p ≡  a(p­1)/2  (mod p).    a    r
  6.  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×            ≡  
  7.  a    n 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 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 
  9. 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
  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:        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
  12. 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 2­m 1 0,500 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 
  13. 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µ  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 
  14. 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ã                                              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ã                                          a 2k­1m  ≡  ­1(mod n) bëi vËy ta ph¶i cã:                                            a 2k­ 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µ ¼.   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:
  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 .
  17. 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; 
  18. 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.
  19. 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 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î
  20. 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 ≤  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.
Đồng bộ tài khoản