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.
-
Chän mét sè ngÉu nhiªn r , 1 r n-1
-
TÝnh y = r2 - B2/4 mod n
-
Gäi ch¬ng tr×nh con A(y) ®Ó t×m b¶n gi¶i m· x
-
TÝnh x1 = x+B/2
-
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, mhmg 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
-
a=2
-
For j=2 to B do
a = aj mod n
-
d = UCLN(a-1,n)
-
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× pn. 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 135978B! 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 nhng 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 x2y2 (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 20449429442773700011)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
-
H·y dïng thuËt to¸n Euclide mì réng ®Ó tÝnh c¸c phÇn tö nghÞch ®¶o rau:
-
17-1 mod 101
-
357-1 mod 1234
-
3125-1 mod 9987
-
Gi¶i hÖ ph¬ng tr×nh ®ång d sau:
x 12 (mod 25)
x 9 (mod 26)
x 23 (mod 27)
-
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.
-
Ta nghiªn cøu mét sè tÝnh chÊt cña c¸c c¨n nguyªn thuû
-
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)
-
H·y dïng ph¬ng ph¸p nµy ®Ó t×m c¨n nguyªn thuû nhá nhÊt theo modulo 97.
-
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
-
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.
-
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.
-
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 cha ®ñ ®Ó ®¶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 A0, B 1,) vµ råi m· ho¸ tõng ký tù cña b¶n râ.
-
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.
-
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
-
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
-
TÝnh c1 = b1-1 mod b2
-
TÝnh c2 = (c1b1- 1)/b2
-
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.
-
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).
-
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.
-
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:
-
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.
-
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:
-
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)
nhng
a(n-1)/2 1 (mod p2p3ps)
nªn
a(n-1)/2 -1 9mod n)
-
NÕu n lµ mét sè hîp sè lÎ, chøng minh r»ng : G(n) (n-1) /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.
-
Gi¶ sö ta cã thuËt to¸n Las-Vegas víi x¸c suÊt sai .
-
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-)
-
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-)
-
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 vµ 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:
-
X¸c ®Þnh 4 c¨n bËc hai cña modulo n, trong ®ã n =pq.
-
TÝnh phÐp m· y = ek(32767)
-
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?.
Chia sẻ với bạn bè của bạn: |