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.
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)}
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)
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.
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)
[ ]
n
§Çu vµo: n vµ B
1. a=2
2. For j=2 to B do
a = aj mod n
3. d = UCLN(a-1,n)
4. 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)
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 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: