H×nh 14. Phn tÝch modulus cña rabin víi mét ch­¬ng tr×nh con gi¶i m· cho tr­íc



tải về 154.86 Kb.
Chuyển đổi dữ liệu31.07.2016
Kích154.86 Kb.
#11639
H×nh 4.14. Ph©n tÝch modulus cña rabin víi mét ch­¬ng tr×nh con gi¶i m· cho tr­íc.


  1. Chän mét sè ngÉu nhiªn r , 1 r  n-1

  2. TÝnh y = r2 - B2/4 mod n

  3. Gäi ch­¬ng tr×nh con A(y) ®Ó t×m b¶n gi¶i m· x

  4. TÝnh x1 = x+B/2

  5. If x1   r (mod n) then quit (kh«ng thµnh c«ng)

Else UCLN(x1+r,n)=p hoÆc q (thµnh c«ng)

Bëi vËy gi¸ trÞ x sÏ thu ®­îc ë b­íc 3. TiÕp theo xÐt b­íc 4. NhËn thÊy r»ng x12 = r2 (mod n). §iÒu ®ã dÉn tíi x1  r (mod n) hoÆc x1  wr (mod n), trong ®ã w lµ mét trong c¸c c¨n bËc hai kh«ng tÇm th­êng cña 1 modulo n. Trong tr­êng hîp thø hai ta cã :


n(x1-r )(x1+r)
song n kh«ng ph¶i lµ ­íc cña mét thõa sè nµo ë vÕ ph¶i. Bëi vËy, viÖc tÝnh UCLN(x1 +r,n)(hoÆc UCLN(x1-r, n)) ph¶i dÉn tíi hoÆc p hoÆc q, vµ nh­ vËy phÐp ph©n tÝch n ®­îc hoµn thµnh.
Ta sÏ tÝnh x¸c suÊt thµnh c«ng cña thuËt to¸n nµy trªn tÊt c¶ (n-1) phÐp chän ngÉu nhiªn r. Víi hai thÆng d­ kh¸c kh«ng r1 vµ r2 , ®Þnh nghÜa:

r1 ~ r2  r12  r22 (mod n)


DÔ dµng thÊy r»ng r ~ r víi mäi r, r1 ~ r2 còng cã nghÜa lµ r2 ~ r1; r1 ~ r2 vµ r2 ~ r3 th× r1 ~ r3 . §iÒu ®ã cho ta thÊy r»ng quan hÖ ~ lµ mét quan hÖ t­¬ng ®­¬ng. C¸c líp t­¬ng ®­¬ng cña Zn\{0} ®Òu cã bèn phÇn tö, líp t­¬ng ®­¬ng chøa r lµ tËp
[r] = {r, wr (mod n)}
trong ®ã w lµ c¨n bËc hai kh«ng tÇm th­êng cña 1 modulo n.
Trong thuËt to¸n ®­îc tr×nh bµy ë h×nh 4.14, hai gi¸ trÞ r bÊt kú trong cïng mét líp t­¬ng ®­¬ng sÏ dÉn tíi cïng mét gi¸ trÞ y. B©y giê xÐt gi¸ trÞ x thu ®­îc tõ ch­¬ng tr×nh con A khi ®· biÕt y. Ta cã:

[y]={y, wy}



NÕu r=y th× thuËt to¸n kh«ng thµnh c«ng; trong khi nÕu r=wy th× thuËt to¸n sÏ thµnh c«ng. V× r ®­îc chän ngÉu nhiªn, nªn mét gi¸ trÞ bÊt kú trong bèn gi¸ trÞ cã thÓ ®Òu cïng kh¶ n¨ng. Ta kÕt luËn r»ng x¸c suÊt thµnh c«ng cña thuËt to¸n lµ 1/2.

§iÒu thó vÞ lµ hÖ mËt rabin lµ an toµn ®èi víi ph­¬ng ph¸p tÊn c«ng b¶n râ chän läc, mh­mg hÖ nµy l¹i hoµn toµn kh«ng an toµn®èi víi ph­¬ng ph¸p tÊn c«ng b¶m m· chän läc. ThuËt to¸n ë h×nh 4.14, phÇn dïng ®Ó chøng minh sù an toµn ®èi víi phÐp tÊn c«ng b¶n râ chän läc còng cã thÓ ®­îc dïng ®Ó ph¸ hÖ mËt Rabin khi thùc hiÖn tÊn c«ng b¶n m· chän läc!. Trong ph­¬ng ph¸p tÊn c«ng b¶n m· chän läc, ch­¬ng tr×nh con A ®­îc thay b»ng thuËt to¸n gi¶i m· cña Bob.


4.8. C¸c thuËt to¸n ph©n tÝch thõa sè.

§· cã mét khèi l­îng khæng lå c¸c t×a liÖu vÒ c¸c thuËt to¸n ph©n tÝch thõa sè vµ viÖc nghiªn cøu kü l­ìng sÏ ®ßi hái ph¶i cã mét cuèn s¸ch dµy h¬n quyÓn s¸ch nµy. ë ®©y chØ cè g¾ng ®­a ra mét c¸i nh×n kh¸i qu¸t bao gåm viÖc th¶o luËn s¬ l­îc vÒ c¸c thuËt to¸n ph©n tichs thõa sè tèt nhÊt hiÖn thêi vµ c¸ch sö dông chóng trong thùc tÕ. Ba thuËt to¸n hiÖu qu¶ nhÊt trªn c¸c sè thËt lín lµ sµng bËc hai, thuËt to¸n ®­êng cong elliptic vµ sµng tr­êng sè. C¸c thuËt to¸n næi tiÕng kh¸c (nh÷ng thuËt to¸n to¸n cã tr­íc) bao gåm ph­¬ng ph¸p  vµ thuËt to¸n p-1 cña Pollard, thuËt to¸n p+1 cña Williams, thuËt to¸n liªn ph©n sè vµ dÜ nhiªn c¶ nh÷ng phÐp chia thö.

Trong toµn bé phÇn nµy, xchóng ta cá×ng sè nguyªn n cÇn ph©n tÝch ra thõa sè lµ mét sè lÎ. PhÐp chia thö bao gåm viÖc chia n


cho tõng sè nguyªn lÎ cho tíi . NÕu n < 1012 th× ®©y lµ mét
ph­¬ng ph¸p ph©n tÝch thõa sè hîp lý mét c¸ch hoµn h¶o, tuy nhiªn víi n lín h¬n nãi chung ta ph¶i dïng c¸c kü thuËt tinh tÕ h¬n.

4.8.1. Ph­¬ng ph¸p p-1


ThuËt to¸n p-1 cña Pollar (®­a ra vµo n¨m 1947) lµ mét thÝ dô vÒ mét thuËt to¸n ®¬n gi¶n ®¬n khi ®­îc ¸p dông víi c¸c sè nguyªn lín. ThuËt to¸n nµy (tr×nh bµy trªn h×nh 4.15) cã hai ®Çu vµo: sè nguyªn lÎ n cÇn ®­îc ph©n tÝch vµ mét cËn B. Cã thÓ m« t¶ thuËt to¸n nh­ sau:
H×nh 4.15. ThuËt to¸n ph©n tÝch thõa sè p-1.

§Çu vµo: n vµ B



  1. a=2

  2. For j=2 to B do

a = aj mod n

  1. d = UCLN(a-1,n)

  2. if 1 < d < n then

d lµ mét thõa sè cña n

else


kh«ng t×m ®­îc thõa sè cña n

(kh«ng thµnh c«ng)


Gi¶ sö p lµ ­íc mhuyªn tè cña n vµ q  B , víi mçi mò nguyªn tè p(p-1). Khi ®ã

(p-1)B!

ë cuèi vßng lÆp for (b­íc 2)

a  2B! (mod n)

nªn a  2B! (mod p)

v× pn. nªn theo ®Þnh ý Fermat ta cã :

       135979  115979

Trong tr­êng hîp nµy, phÐp ph©n tÝch sÏ thµnh c«ng do 135978 chØ gåm c¸c thõa sè nguyªn tè nhá:


V× thÕ

135978 = 2  3 131  173


nÕu lÊy B  173 th× ch¾c ch¨n r»ng 135978B! nh­ mong muèn.
Trong thuËt to¸n cã (B-1) luü thõa theo modulo, mçi luü cÇn nhiÒu nhÊt lµ 2log2B phÐp nh©n modulo dïng thuËt to¸n b×nh ph­¬ng vµ nh©n. ViÖc tÝnh ­íc chung lín nhÊt cã thÓ thùc hiÖn trong thêi gian O((log n)3) b»ng thuËt to¸n Euclide. Bëi vËy, ®é phøc t¹p cña thuËt to¸n lµ O(B logB (log n)2 +(log n)3). NÕu B lµ O((log n)i) víi mét sè nguyªn i x¸c ®Þnh nµo ®ã th× thuËt to¸n thùc sù lµ thuËt to¸n thêi gian ®a thøc, tuy nhiªn víi phÐp chän B nh­ vËy, x¸c suÊt thµnh c«ng sÏ rÊt nhá. MÆt kh¸c, nÕu t¨ng kÝch th­íc cña B lªn thËt lín (ch¼ng h¹n tíi ?????????????? ) th× thuËt to¸n sÏ thµnh c«ng nh­ng nã sÏ kh«ng thùc hiÖn nhanh h¬n phÐp chia thö.
Nh­ vËy, ®iÓm bÊt lîi cña thuËt to¸n nµy lµ nã yªu cÇu n ph¶i cã ­íc nguyªn tè p sao cho (p-1) chØ c¸c thõa sè nguyªn tè bÐ. Ta cã thÓ dÔ dµng x©y dùng ®­îc hÖ mËt RSA víi modulus n= pq h¹n chÕ ®­îc viÖc ph©n tÝch theo ph­¬ng ph¸p nµy. Tr­íc tiªn t×m mét sè nguyªn tè lín p1 sao cho p= 2p1+1 còng lµ mét sè nguyªn tè vµ mét sè nguyªn tè lín q1 sao cho q= 2q1+1 còng lµ mét sè nguyªn tè (nhê dïng mét trong c¸c thuËt to¸n kiÓm tra tÝnh nguyªn tè Monte-Carlo nªu trong phÇn 4.5). Khi ®ã modulo cña RSA n= pq sÏ chèng ®­îc c¸ch ph©n tÝch theo ph­¬ng ph¸p p-1.
ThuËt to¸n ®­êng cong elliptic m¹nh h¬n (®­îc Lenstra x©y dùng vµo nh÷ng n¨m 1980) trªn thùc tÕ lµ sù tæng qu¸t ho¸ cña ph­¬ng ph¸p p-1. Ta sÏ kh«ng th¶o luËn vÒ lý thuyÕt ë ®©y mµ chØ nhÊn m¹nh r»ng, thµnh c«ng cña ph­¬ng ph¸p ®­êng cong elliptic tuú thuéc vµo t×nh huèng t­¬ng tù : mét sè nguyªn “gÇn víi” p chØ cã c¸c thõa sè nguyªn tè bÐ. Trong khi ph­¬ng ph¸p p-1 phô thuéc vµo quan hÖ trong Zp th× ph­¬ng ph¸p ®­êng cong elliptic phô thuéc vµo c¸c nhãm x¸c ®Þnh trªn c¸c ®­êng cong elliptic theo modulo n.
4.8.2. ThuËt to¸n Dixon vµ sµng bËc hai
ThuËt to¸n Dixon ®­îc x©y dùng trªn ý t­ëng ®¬n gi¶n mµ ta ®· thÊy trong hÖ mËt Rabin. ý t­ëng ®ã lµ: nÕu t×m ®­îc x  y (mod n) sao cho x2y2 (mod n) th× UCLN(x-y,n) lµ ­íc kh«ng tÇm th­êng cña n.
Ph­¬ng ph¸p nµy sö dông c¬ së nh©n tö lµ mét tËp b chøa c¸c sè nguyªn tè bÐ. Tr­íc tiªn ta nhËn ®­îc mét vµi sè nguyªn x sao cho tÊt c¶ c¸c thõa sè nguyªn tècña x2 (mod n) n»m trong c¬ së b (c¸ch thùc hiÖn ®iÒu nµy sÏ ®­îc th¶o luËn sau). ý t­ëng thùc hiªn ë ®©y lµ lÊy tÝch cña mét vµi gi¸ trÜ sao cho mçi sè nguyªn tè trong c¬ së ®­îc sö dông mét sè ch½n lÇn. §iÒu nµy dÉn ®Õn mét ®ång d­ thøc d¹ng mong muèn x2  y2 (mod n) mµ ta hy väng sÏ ®­a ®Õn viÖc ph©n tÝch n.
Ta sÏ minh ho¹ b»ng mét vÝ dô ®· ®­îc dù tÝnh kü l­ìng.
VÝ dô 4.15

Gi¶ sö n=15770708441(gi¸ trÞ n nµy ®· dïng trong vÝ dô 4.14). Gi¶ sö b = {2,3,5,7,11,13}. XÐt ba ®ång thøc sau:


83409341562  3  7 (mod n)

120449429442  1  7  13 (mod n)

27737000112 =2  3  13 (mod n)
NÕu lÊy tÝch cña ba ®ång d­ thøc trªn:
(8340934156  20449429442773700011)2 (2 3 7 13)2 (mod n)
Rót gän c¸c biÓu thøc bªn trong c¸c dÊu ngÆc theo modulo n, ta cã:

95034357852  5462 (mod n)

Sau ®ã tÝnh:

UCLN(9503435785-546, 15770708441)=115759


Ta thÊy 115759 lµ mét thõa sè cña n.
Gi¶ sö B = {p1, . . . .pB}lµ mét c¬ së nh©n tö. Gi¶ sö c lín h¬n B mét chót (ch¼ng h¹n C=B+10) vµ gi¶ sö ta ®· cã C ®ång d­ thøc:

xj2  p11j  p22j  . . . pBBj(mod n)


víi 1 j  C. Víi mçi j xÐt vÐctor :
aj = (1j mod 2, 2j mod 2, . . ., Bj mod 2)  (Z2)B
NÕu cã thÓ t×m ®­îc mét tËp con c¸c aj sao cho tæng theo modulo 2 lµ vector (0,. . ., 0) th× tÝch cña c¸c xj t­¬ng øng sÏ sö dông mçi nh©n tö trong B mét sè ch½n lÇn.

Ta sÏ minh ho¹ b»ng c¸ch trë l¹i vÝ dô 4.15. Trong tr­êng hîp nµy nÕu C < B, vÉn t×m ®­îc sù phô thuéc tuyÕn tÝnh.


VÝ dô 4.15 (tiÕp)
Cho 3 vector a1, a2, a3 :
a1 =(0, 1, 0, 1, 0, 0)

a2 =(1, 0, 0, 1, 0, 1)

a3 = (1, 1, 0, 0, 0, 1)
DÔ dµng thÊy r»ng:
a1 +a2 + a3 = (0, 0, 0, 0, 0, 0) mod 2
§©y lµ lý do cho thÊy ®ång d­ thøc (thiÕt lËp theo tÝch) sÏ ph©n tÝch thµnh c«ng ®­îc n.

NhËn thÊy r»ng, bµi to¸n t×m mét tËp con C vector a1, a2, . . ., aC sao cho tæng theo modulo 2 lµ mét vector toµn chøa sè 0 chÝnh lµ bµi to¸n t×m sù phô thuéc tuyÕn tÝnh (trªn Z2) cña c¸c vector nµy. Víi C > B, sù phô thuéc tuyÕn tÝnh nµy nhÊt ®Þnh ph¶i tån t¹i vµ ta cã thÓ dÔ dµng t×m ®­îc b»ng ph­¬ng ph¸p lo¹i trõ Gaux. Lý do gi¶i thÝch t¹i sao lÊy C > B+1 lµ do kh«ng cã g× b¶o ®¶m ®Ó mét ®ång d­ thøc cho tr­íc bÊt kú sÏ t¹o ®­îc ph©n tÝch n. Kho¶ng 50% thuËt to¸n cho ra x  y (mod n). Tuy nhiªn nÕu C > B+1 th× cã thÓ nhËn ®­îc mét vµi ®ång d­ thøc nh­ vËy. (N¶y sinh tõ c¸c phô thuéc tuyÕn tÝnh kh¸c cña c¸c aj). Hy väng lµ Ýt nhÊt mét trong c¸c ®ång d­ thøc kÕt qu¶ sÏ dÉn ®Õn viÖc ph©n tÝch n.

VÊn ®Ò cßn l¹i lµ ph¶i lµm thÕ nµo ®Ó nhËn ®­îc c¸c sè nguyªn xj mµ c¸c gi¸ trÞ xj2 mod n cã thÓ ph©n tÝch hoµn toµn trªn c¬ së b. Mét vµi ph­¬ng ph¸p cã thÓ thùc hiÖn ®­îc ®iÒu ®ã. BiÖn ph¸p sµng


bËc hai do Pomerance ®­a ra dïng c¸c sè nguyªn d¹ng xj=j +
,j=1,2...... Tªn “sµng bËc hai” lÊy tõ thñ tôc sµng (kh«ng m« t¶ ë ®©y) dïng ®Ó x¸c ®Þnh c¸c xj ph©n tÝch ®­îc trªn b.
ë ®©y dÜ nhiªn lµ mét sù tho¶ hiÖp: nÕu B =  B  lµ mét sè lín th× thÝch hîp h¬n c¶ lµ nªn ph©n tÝch sè nguyªn xj trªn b. Tuy nhiªn khi B cµng lín th× ta cµng ph¶i gom nhiÒu ®ång d­ thøc h¬n tr­íc khi cã thÓ t×m ®­îc mét quan hÖ phô thuéc. Lùa chän tèi ­u cho B xÊp xØ b»ng
??????????????????

vµ ®iÒu nµy dÉn ®Õn thêi gian thùc hiÖn cì


??????????????????????????
Sµng tr­êng sè lµ thuËt to¸n ph©n tÝch míi h¬n (tõ cuèi nh÷ng n¨m 80) ThuËt to¸n nµy còng ph©n tÝch n b»ng c¸ch x©y dùng mét ®ång d­ thøc x2  y2 (mod n), song nã ®­îc thùc hiÖn b»ng c¸c tÝnh to¸n trªn vµnh c¸c sè ®¹i sè.
4.8.3.C¸c thuËt to¸n ph©n tÝch trªn thùc tÕ.

Thêi gian ch¹y tiÖm cËn cña c¸c thuËt to¸n sµng bËc hai, ®­¬ng cong elliptic vµ sµng tr­êng sè nh­ sau:




Sµng bËc hai O?????????????//

§­êng cong elliptic ??????????????



Sµng tr­êng sè ?????????????????

trong ®ã O(1) lµ hµm cña n, hµm nµy tiÕn tíi 0 khi n  vµ p lµ thõa sè nguyªn tè nhá nhÊt cña n.


T

rong tr­êng hîp xÊu nhÊt p  ?????????, thêi gian ch¹y tiÖm cËn cña c¸c thuËt to¸n ®­êng cong elliptic vµ sµng bËc hai c¬ b¶n nh­ nhau. Tuy nhiªn trong tr­êng hîp nµy, ph­¬ng ph¸p sµng bËc hai nãi chung tréi h¬n ph­¬ng ph¸p ®­êng cong elliptic. Ph­¬ng ph¸p ®­¬ng cong elliptic hiÖu qu¶ h¬n nÕu c¸c thõa sè nguyªn tè cña n cã kÝch th­íc kh¸c nhau. Mét sè rÊt lín ®· ®­îc ph©n tÝch b»ng ph­¬ng ph¸p ®­êng cong elliptic lµ tham sè Fermat (22048-1) (®­îc Brent thùc hiÖn n¨m 1988) .
§Ó ph©n tÝch c¸c modulo RSA (trong ®ã n=pq, p vµ q lµ c¸c sè nguyªn tè cã cïng kÝch th­íc), sµng bËc hai lµ mét thuËt to¸n thµnh c«ng nhÊt hiÖn nay. Sau ®©y lµ mét sè kÕt qu¶ quan träng. Vµo n¨m 1983, thuËt to¸n sµng bËc hai ®· ph©n tÝch thµnh c«ng mét sè cã 69 ch÷ sè, sè nµy lµ mét thõa sè cña 2251-1 (do Davis, Holdredye vµ Simmons thùc hiÖn). Qu¸ tr×nh nµy tiÕp tôc trong nh÷ng n¨m 80 vµ ®Õn n¨m 1989 ®· cã thÓ ph©n tÝch ®­îc c¸c sè cã tíi 106 ch÷ sè theo ph­¬ng ph¸p nµy( do Lenstra vµ Manasse thùc hiÖn) nhê ph©n bè c¸c phÐp tÝnh cho hµng tr¨m tr¹m lµm viÖc t¸ch biÖt (ng­êi ta gäi ph­¬ng ph¸p nµy lµ “ph©n tÝch thõa sè b»ng th­ ®iÖn tö”).
GÇn ®©y h¬n, 4/1994 Atkins, Graff, Lenstra vµ Leyland ®· ph©n tÝch ®­îc mét sè 129 ch÷ sè (®­îc gäi lµ RSA-129) nhê sö dông sµng bËc hai (c¸c sè RSA-100, RSA-110,....,RSA-500 lµ mét danh s¸ch c¸c modulo RSA ®­îc c«ng bè trªn internet nh­ lµ sù th¸ch ®è cho c¸c thuËt to¸n ph©n tÝch. Mçi mét sè RSA-d lµ mét sè d ch÷ sè, sè nµy lµ tÝch cña hai sè nguyªn tè cã kÝch th­íc xÊp xØ nhau). ViÖc ph©n tÝch sè RSA-129 cÇn hµng tr¨m tÝnh to¸n víi m¸y tÝnh 5000 MIPS (triÖu lÖnh/s) ®­îc thùc hiÖn bëi 600 nhµ nghiªn cøu trªn toµn thÕ giíi.

Sµng tr­êng sè lµ mét thuËt to¸n míi nhÊt trong ba thuËt to¸n to¸n. Nã cã vÎ cã tiÒm n¨ng lín do thêi gian ch¹y tiÖm cËn cña nã nhanh h¬pn c¶ hai thuËt to¸n trªn. ThuËt to¸n nµy hiÖn vÉn cßn trong thêi k× nghiªn cøu, tuy nhiªn ng­êi ta ®· dù ®o¸n lµ sµng tr­êng sè ph¶i chøng tá lµ nhanh h¬n víi c¸c sè cã trªn 125-130 ch÷ sè. N¨m 1990, Lenstra, Manase vµ Pollaid ®· dïng sµng tr­êng sè ®Ó ph©n tÝch (2512 - 1) thµnh ba sè nguyªn tè cã 7, 49 vµ 99 ch÷ sè.






4.9. chó gi¶i vµ tai liªu dÉn
ý t­ëng vÒ mËt m· kho¸ c«ng khai ®· ®­îc Diffie vµ Hellman nªu ra vµo 1976. MÆc dï [HD 76A] lµ tµi liÖu ®­îc trÝch dÉn nhiÒu nhÊt nh÷ng bµi b¸o Héi nghÞ [DH 76] thùc tÕ ®· xuÊt hiÖn sím h¬n mét chót. HÖ mËt RSA ®­îc Rivest, Shamis vµ Adleman [RSA 78] ph¸t minh. HÖ mËt Rabin ®­îc m« t¶ trong [RA 79]: mét hÖ t­¬ng tù víi phÐp gi¶i m· kh«ng mËp mê ®· ®­îc Willians t×m ra trong [Wi 80]. B¹n ®äc nÕu tham kh¶o [Di 92] lµ mét bµi b¸o tæng qu¸t vµ mÆt m· kho¸ c«ng khai cña Diffie.
PhÐp thö Solovay- Stassen lÇn ®Çu tiªn m« t¶ trong [SS 77]. PhÐp thö Miller- Rabin ®­îc nªu trong[Mi 76] vµ [Ra 80]. Th¶o luËn cña chóng ta vÒ c¸c x¸c suÊt sai dùa trªn c¸c nhËp xÐt cña Brassard vµ Bratly [BB 88A, 8.6] (còng cã thÓ trong[BBCGP 88]. C¸c cËn tèi nhÊt hiÖn thêi vÒ x¸c suÊt sai cña thuËt to¸n Miller- Rabin cã thÓ t×m thÊy trong [DLP 93].
Néi dung cña phÇn 4.6 dùa trªn quan ®iÓm cña Salomaa [SA 90, c¸c trang 143-154]. PhÐp ph©n tÝch n víi sè mò gi¶i m· cho tr­íc ®­îc nªu trong [DE 84]: c¸c kÕt qu¶ vÒ th«ng tin riªng bÞ lé bëi RSA lÊy tõ [GMT 82].
Nh­ ®· nãi trªn, ®· cã rÊt nguån tµi liÖu vÒ c¸c thuËt to¸n ph©n tÝch. Pomerance [Po 90]lµ tæng qu¸t vÒ phÕp ph©n tÝch. Lenstra vµ Lenstra [LL 90] lµ mét b¸o c¸o hay lµ vÒ c¸c thuËt to¸n lý thuyÕt nãi chung. Bressoud [Br 89] lµ mét gi¸o tr×nh s¬ cÊp vÒ phÐp ph©n tÝch thõa sè vµ phÐp kiÓm tra tÝnh nguyªn tè. C¸c gi¸o trinh vÒ mËt m· cã chó träng tíi lý thuyÕt sè lµ c¸c s¸ch cña Koblitz [Ko 87] vµ cña Kranakis [Kr 86]. Cßn s¸ch cña Lenstra vµ Lenstra [LL 93] lµ mét chuyªn th¶o tèt vÒ sµng tr­êng sè.
C¸c bµi tËp 4.7- 4.9 cho mét sè vÝ dô vÒ trôc trÆc trong giao thøc (protocol). VÒ vÊn ®Ò nµy cã thÓ xem mét bµi b¸o rÊt hay cña Moore [Mo 92].



Bµi tËp


    1. H·y dïng thuËt to¸n Euclide mì réng ®Ó tÝnh c¸c phÇn tö nghÞch ®¶o rau:

  1. 17-1 mod 101

  2. 357-1 mod 1234

  3. 3125-1 mod 9987

    1. Gi¶i hÖ ph­¬ng tr×nh ®ång d­ sau:

x  12 (mod 25)

x  9 (mod 26)

x  23 (mod 27)


    1. Gi¶i hÖ ph­¬ng tr×nh ®ång d­ sau

13x  4 (mod 99)

15x  56 (mod 101)

gîi ý: tr­íc tiªn h·y dïng thuËt to¸n Euclide mì r«ng råi ¸p dông ®Þnh lý phÇn d­ cña China.


    1. Ta nghiªn cøu mét sè tÝnh chÊt cña c¸c c¨n nguyªn thuû

  1. 97 lµ mét sè nguyen tè. H·y chøng minh r»ng x  0 lµ mét c¨n nguyªn thuû theo modulo 97 khi vµ chØ khi

x32  1 (mod 97) vµ x48  1 (mod 97)

  1. H·y dïng ph­¬ng ph¸p nµy ®Ó t×m c¨n nguyªn thuû nhá nhÊt theo modulo 97.

  2. Gi¶ sö p lµ mét sè nguyªn tè vµ p-1 cã phÇn tÝch ra c¸c mò nguyªn tè sau :



ë ®©y pi lµ c¸c sè nguyªn tè kh¸c nhau. H·y chøng minh tá r»ng x  0 lµ mét c¨n nguyªn thuû theo modulo p khi vµ chØ khi



x(p-1)/pi  1 (mod p ) víi 1  i  n

    1. Gi¶ sö n =pq, p vµ aq lµ c¸c sè nguyªn tè lÎ ph©n biÖt vad ab  1 (mod (p-1)(q-1)). PhÐp to¸n m· ho¸ RSA lµ

e(x) = xb mod n

vµ phÐp to¸n gi¶i m· lµ d(y) = ya mod n.



Ta ®· chøng tá r»ng d(e(x)) = 1 nÕu x  Zn *. H·y chøng tá r»ng kh¼ng ®Þnh trªn lµ ®óng ®èi víi bÊt kú x  Zn.
ChØ dÉn: H·y dïng kÕt qu¶ : x1  x1 (mod pq) khi vµ chØ khi x1  x1 (mod p) vµ x1  x1(mod q). §iÒu nµy rót ra tõ ®Þnh lý phÇn d­ China.


    1. Hai vÝ dô vÒ b¶n m· RSA ®­îc nªu ë c¸c b¶ng 4.1 vµ b¶ng 4.2. NhiÖm vô cña b¹n lµ ph¶i gi¶i m· chóng. C¸c tham sè c«ng khai cña hÖ thèng lµ n =18923 vµ b = 1261 (b¶ng 4.1) vµ n = 31313, b = 4913 (víi b¶ng 4.2). PhÐp gi¶i m¶ c¸o thÓ thùc hiÖn nh­ sau. Tr­íc hÕt hü ph©n tÝch n (®iÒu nµy kh¸ dÓ v× n qu¸ nhá). Sau ®ã tÝnh sè mò a tõ (n) vµ cuèi cïng sÏ gi¶i m· b¶n m·. H·y dïng thuËt to¸n b×nh ph­¬ng vµ nh©n ®Ó lÊy luü thõa theo modulo n.


B¶ng 4.1 B¶n m· RSA





12423

11524

7243

7459

14303

6127

10964

16399

9792

13692

14407

18817

18830

13556

3159

16647

5300

13951

91

8986

8007

13167

10022

17213

2264

9553

18194

3830

2664

13998

12501

18873

13236

5300

13951

8850

12129

6091

18110

3332

15061

12347

7817

7946

11675

13924

13892

18031

2620

6276

8500

201

8850

11178

16477

10161

3533

13842

7537

12259

18110

44

2364

15570

3460

9886

8687

4481

11231

7547

11383

17910

12867

13203

5102

4742

5053

15407

2976

9330

12192

56

2471

14334

841

13995

13297

8186

2430

9741

11675

242

6686

738

13874

8186

7913

6246

14301

1144

9056

15967

7328

13203

796

195

9872

16979

15404

14130

9105

2001

9792

14251

1498

11296

1105

4502

16979

1105

56

4118

11302

5988

3363

15827

6928

4191

4277

10617

874

13211

1182

3090

18110

44

2364

15570

3460

9886

9988

3798

1158

9872

16979

15404

6127

9872

3652

14838

7437

2540

1367

2512

14407

5053

1521

297

10935

17137

2186

9433

13293

7555

13618

13000

6490

5310

18676

4782

11375

446

4165

11634

3846

14611

2364

6789

11634

4493

4063

4576

17955

7965

11748

14616

11453

17666

925

56

4118

18031

9522

14838

7437

3880

11476

8305

5102

2999

18628

14326

9175

9061

650

18110

8720

15404

2951

722

15334

841

15610

2443

11056

2186

§Ó chuyÓn b¶n râ trë vÒ v¨n b¶n tiÕng Anh th«ng th­êng, b¹n cÇn ph¶i c¸c ký tù ®· ®­îc “m· ho¸” thµnh c¸c phÇn tö trong Zn nh­ thÕ nµo. Mçi phÇn tö cña Zn sÏ biÓu thÞ ba ký tù nh­ trong c¸c vÝ dô sau:

DOG  3  262 + 14  26 +6 = 2398

CAT  2  262 + 0  26 + 19 = 1371

ZZ  25  262 + 25  26 + 25 = 17575

B­íc cuèi cïng trong ch­¬ng tr×nh cña b¹n lµ lµm ng­îc l¹i qu¸ tr×nh trªn.



B¶n râ ®Çu lÊy trong cuèn “The diary of Samuel M¶chbankls” cña Robertson Davies, 1947. B¶n râ thø hai lÊy tõ cuèn “Lake Wobegon Days” cña Garrison Keillor, 1985.


    1. Bµi tËp nµy m« t¶ c¸i ®­îc gäi lµ sù trôc trÆc vÒ thñ tôc. §©y lµ mét vÝ dô vÒ mét b¶n mµ cã thÓ bÞ ®èi ph­¬ng gi¶i mµ kh«ng cÇn ph¶i x¸c ®Þnh kho¸ nÕu dïng thiªó thËn träng hÖ mËt ( v× ®èi ph­¬ng kh«ng ph¶i x¸c ®Þnh



B¶ng 4.2 B¶n m· RSA


6340

8309

14010

8936

27358

25023

16481

25809

23316

7135

24996

30596

27570

26486

30388

9395

27584

14999

4517

12146

29421

26439

1606

17881

25774

7647

23901

7372

25774

18436

12056

13547

7908

8635

2149

1908

22076

7372

8686

1307

4082

11803

5314

107

7359

22470

7372

22827

15698

30317

4685

14696

30388

8671

29956

15705

1417

26905

25809

28347

26277

7879

20240

21519

12437

1108

27106

18743

24144

10685

25234

30155

23055

8267

9917

7994

9694

2149

10042

27705

15930

29748

8635

23645

11738

24591

20240

27212

27486

9741

2149

29329

2149

5501

14015

30155

18154

22319

27705

20321

23254

13624

3249

5443

2149

16975

16087

146000

27705

19386

7325

26277

19554

23614

7553

4734

8091

23973

14015

107

3183

17347

25234

4595

21498

6360

19837

8463

6000

31280

29413

2066

369

23204

8425

7792

25973

4477

30989















Kho¸ nªn nÕu gäi lµ th¸m m· th× kh«ng ®­îc chÝnh x¸c l¾m). Tinh thÇn ë ®©y lµ dïng hÖ mËt “ an toµn toµn” vÉn ch­a ®ñ ®Ó ®¶m b¶o liªn l¹c an toµn toµn.


Gi¶ sö Bob cã mét hÖ mËt RSA cã modulo n lín ®Ó viÖc ph©n tÝch n kh«ng thÓ thùc hiªn trong mét thêi gian chÊp nhËn ®­îc. Gi¶ sö Alice göi mét thong b¸o cho Bob b»ng c¸ch biÓu thÞ mét ký tù b»ng mét sè nguyªn trong kho¶ng 0- 25 (ch¼ng h¹n A0, B 1,) vµ råi m· ho¸ tõng ký tù cña b¶n râ.


  1. H·y m« t¶ c¸ch Oscar cã thÓ gi¶i m· dÔ dµng c¸c b¶n m· ®­îc m· nh­ c¸ch trªn.

  2. Minh ho¹ c¸ch tÊn c«ng qua viÖc gi¶i m· b¶n m· sau (b¶n nµy ®· ®­îc m· b»ng hÖ mËt RSA víi n = 18721 vµ b = 25) mµ kh«ng cÇn ph¶i ph©n tÝch n:

365,0,4845,14930,2608,2608,0




    1. Bµi tËp nµy m« t¶ mét vÝ dô kh¸c vÒ sù trôc trÆc thñ tôc (theo Simons)trong RSA ®­îc gäi lµ trôc trÆc thñ tôc modulo chung. Gi¶ sö Bob cã hÖ m©t RSA víi modulo n, sè mò ho¸ b1 cßn Charlie cã hÖ m©t RSA víi cïng modulo n, sè mò ho¸ b2. Gi¶ sö UCLN(b1,b2) =1. B©y giê ta h·y xÐt t×nh h×nh x¶y ra nÕu Alice m· ho¸ cïng mét b¶n râ x ®Ó göi cho c¶ Bob vµ Charlie. Nh­ vËy, Alice sÏ tÝnh y1 =xb1 mod n vµ y2 =xb2 mod n vµ råi göi y1 cho Bob vµ göi y2 cho Charlie. Gi¶ sö Oscar thu ®­îc y1 vµ y2 vµ thùc hiÖn c¸c tÝnh to¸n ®­îc nÕu ë h×nh 4.16 sau.


H×nh 4.16. trôc trÆc thñ tôc modulo chung.

§Çu vµo : n, b1, b2, y1, y2



  1. TÝnh c1 = b1-1 mod b2

  2. TÝnh c2 = (c1b1- 1)/b2

  3. TÝnh x1 = y1c1 (y2c2)-1 mod n



a) H·y chøng tá r»ng gi¸ trÞ x1 tÝnh ®­îc ë b­íc 3 cña h×nh 4.16 thùc tÕ lµ b¶n râ x cña Alice. Bëi vËy, Oscar cã thÓ gi¶i m· ®­îc th«ng b¸o mµ Alice ®· göi, ngay c¶ khi b¶n râ ®­îc göi qua hÖ mËt ®­îc coi lµ an toµn.

b) Minh ho¹ c¸ch tÊn c«ng qua viÖc tÝnh x theo ph­¬ng ph¸p nµy nÕu n = 18721,b1 = 945, b2 = 7717, y1 = 12677 vµ y2 = 14702.

4.9 §©y l¹i lµ mét vÝ dô kh¸c vÒ sù trôc trÆc thñ tôc xoay quanh hÖ mËt RSA. Gi¶ sö cã ba ng­êi dïng trong m¹ng lµ Bob, Bar vµ Bert, hä ®Òu cã sè mò m· ho¸ b =3. C¸c modulo t­¬ng øng n1, n2, n3. Gi¶ sö Alice m· ho¸ cïng mét b¶n râ x ®Ó göi cho Bob, Bar vµ Bert. Khi ®ã Alice tÝnh

yi = x3 mod ni , 1 i  3

H·y m« t¶ c¸ch tnhs x cña Oscar khi anh ta ®· biÕt y1, y2, y3, mµ kh«ng cÇn ph¶i ph©n tÝch bÊt cø ni nµo.


    1. B¶n râ x ®­îc gäi lµ cè ®Þnh nÕu ek(x) = x. H·y chøng tá r»ng ®èi víi hÖ mËt RSA, sè c¸c b¶n râ cè ®Þnh x  Zn* b»ng

UCLN(b-1, p-1)  UCLN(b-1, p-1)



ChØ dÉn: xÐt hÖ hai ph­¬ng tr×nh ®ång d­:

eK (x1)  x (mod p), eK(x2)  x (mod p).




    1. Gi¶ sö A lµ mét thuËt to¸n tÊt ®Þnh cã ®Çu vµo lµ mét RSA modulo n vµ b¶n m· y. A sÏ hoÆc gi¶i m· y hoÆc kh«ng cã lêi gi¶i. Gi¶ sö r»ng cã   n b¶n m· mµ cã thÓ gi¶i, hay chØ râ c¸ch dïng A lµm mét ch­¬ng con trong thuËt to¸n gi¶i m· Las Vegas cã x¸c suÊt kh«ng thµnh c«ng lµ .


ChØ dÉn: sö dung tÝnh chÊt nh©n cña RSA lµ

eK (x1) eK(x2) = eK(x1x2)

trong ®ã tÊt c¶ c¸c phÐp to¸n sè häc lµ theo modulo n.


    1. ViÕt mét ch­¬ng tr×nh ®Ó ®¸nh gi¸ c¸c ký hiÖu Jacobi b»ng c¸ch dïng bèn tÝnh chÊt ®­îc nªu ë phÇn 4.5. Ch­¬ng tr×nh kh«ng thùc hiÖn viÖc ph©n tÝch thõa sè trõ viÖc ph©n ra c¸c luü thõa bËc hai. H·y kiÓm tra ch­¬ng tr×nh cña b¹n qua viÖc tÝnh c¸c ký hiÖu Jacobi sau:





    1. H·y viÕt mét ch­¬ng tr×nh tÝnh sè c¸c sè gi¶ nguyªn tè Euler theo c¸c c¬ së 837, 851 vµ 1189.




    1. Môc ®Ých cña bµi tËp nµy lµ ph¶i chøng tá r»ng: x¸c suÊt cña kiÓm tra tÝnh nguyªn tè Solovay- Strassen nhiÒu nhÊt lµ 1/2 . Gi¶ sö Zn* lµ nhãm c¸c phÇn tö kh¶ nghÞch theo modulo n. Ta ®Þnh nghÜa:






  1.           kh«ng bËc hai theo modulo p1. (Chó ý r»ng, a nh­ vËy tån t¹i theo ®Þnh lý phÇn d­ China). H·y chøng minh r»ng:

 -1 (mod n)

nh­ng

a(n-1)/2  1 (mod p2p3ps)



nªn

a(n-1)/2  -1 9mod n)

  1. NÕu n lµ mét sè hîp sè lÎ, chøng minh r»ng :  G(n)   (n-1) /2

  2. Tæng hîp c¸c kÕt qu¶ trªn, h·y chøng minh r»ng x¸c suÊt sai cña phÐp kiÓm tra tÝnh nguyªn tè Solovay- Strassen nhiÒu nhÊt lµ 1/2.

    1. Gi¶ sö ta cã thuËt to¸n Las-Vegas víi x¸c suÊt sai .

  1. H·y chøng minh r»ng, x¸c suÊt thµnh c«ng lÇn ®Çu sau phÐp thö thø n lµ :

Pn = n-1 (1-)

  1. Sè phÐp thö trung b×nh ®Ó ®¹t thµnh c«ng lµ :


.

(n  pn)


H·y chøng tá r»ng gi¸ trÞ nµy b»ng 1/(1-)

  1. Gi¶ sö  lµ mét sè d­¬ng thùc nhá h¬n 1. H·y chøng tá r»ng sè c¸c phÐp lÆp cÇn thiÕt ®Ó gi¶m x¸c suÊt sai tèi ®a  lµ:



4.16. Gi¶ sö thiÕu trÇn träng, Bob ®· ®Ó lé sè mò gi¶i m· cña m×nh lµ a = 14039 trong hÖ mËt RSA víi khoa c«ng khai n = 36581 vµ b = 4679. ¸p dông dông thuËt to¸n s¸c suÊt ®Ó ph©n tÝch n theo th«ng tin ®­îc biÕt nµy. H·y kiÓm tra thuËt toan cña b¹n víi c¸c phÐp chän ngÉu nhiªn w = 9983 vµ w = 13461. H·y chØ ra tÊt c¶ c¸c tÝnh to¸n .


4.17. H·y chøng minh c¸c ph­¬ng tr×nh 4.1 vµ 4.2 cã liªn quan ®Õn c¸c hµm half parity.
4.18. gi¶ sö p = 199, q = 211 vµ b = 1357 trong hÖ mËt Rabin. H·y thùc hiÖn tÝnh to¸n sau:


  1. X¸c ®Þnh 4 c¨n bËc hai cña modulo n, trong ®ã n =pq.

  2. TÝnh phÐp m· y = ek(32767)

  3. X¸c ®Þnh 4 b¶n gi¶ m· cã thÓ cña b¶n m· y ®· cho.

4.19. H·y ph©n tÝch ra thõa sè c¸c sè 262063 vµ 9420457 b»ng ph­¬ng ph¸p p-1. Trong mçi tr­êng hîp, ®Ó thµnh c«ng ph¶i chän B l¬n nh­ thÕ nµo?.

tải về 154.86 Kb.

Chia sẻ với bạn bè của bạn:




Cơ sở dữ liệu được bảo vệ bởi bản quyền ©hocday.com 2024
được sử dụng cho việc quản lý

    Quê hương