Xem mẫu
- 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- 2
2. TÝnh y = r B /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 1-r )(x1+r)
(x
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] . NÕu n < 10 12 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
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)
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 theo ®Þnh ý Fermat ta cã :
n.
≡ ≡
≡
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 nh mong
B!
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:
8340934156 2 ≡ 3 × 7 (mod n)
12044942944 2 ≡ 1 × 7 × 13 (mod n)
2773700011 2 =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ã:
9503435785 2 ≡ 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 ≡ p1 1j × p2 2j × . . .× pB Bj(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 +n [ ]
,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 x j
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.
Trong 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è
[ n]
- 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
4.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
a) 17 mod 101
-1
b) 357 mod 1234
-1
c) 3125 mod 9987
4.2. Gi¶i hÖ ph¬ng tr×nh ®ång d sau:
x ≡ 12 (mod 25)
x ≡ 9 (mod 26)
x ≡ 23 (mod 27)
4.3. 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.
4.4. Ta nghiªn cøu mét sè tÝnh chÊt cña c¸c c¨n nguyªn thuû
a) 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)
b) H·y dïng ph¬ng ph¸p nµy ®Ó t×m c¨n nguyªn thuû
nhá nhÊt theo modulo 97.
c) 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 :
n e
1
p − 1= ∏ p
i =1 i
- ë ®©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)/p ≡ 1 (mod p ) víi 1 ≤ i ≤ n
i
4.5. 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.
4.6. 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.
4.7. 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 2735 25023 16481 25809
8
23316 7135 24996 30596 2757 26486 30388 9395
0
27584 14999 4517 12146 2942 26439 1606 17881
1
25774 7647 23901 7372 2577 18436 12056 13547
4
7908 8635 2149 1908 2207 7372 8686 1307
6
4082 11803 5314 107 7359 22470 7372 22827
15698 30317 4685 14696 3038 8671 29956 15705
8
1417 26905 25809 28347 2627 7879 20240 21519
7
12437 1108 27106 18743 2414 10685 25234 30155
4
23055 8267 9917 7994 9694 2149 10042 27705
15930 29748 8635 23645 1173 24591 20240 27212
8
27486 9741 2149 29329 2149 5501 14015 30155
18154 22319 27705 20321 2325 13624 3249 5443
4
2149 16975 16087 14600 2770 19386 7325 26277
0 5
19554 23614 7553 4734 8091 23973 14015 107
3183 17347 25234 4595 2149 6360 19837 8463
8
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 A↔0, B ↔1,…) vµ råi m· ho¸ tõng ký tù cña
b¶n râ.
a) 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.
b) 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
4.8. 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 =xb mod n vµ y2 =xb mod n vµ råi göi y1 cho Bob
1 2
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
1. TÝnh c1 = b1 mod b2
2. TÝnh c2 = (c1b1- 1)/b2
c c -1
3. TÝnh x1 = y1 (y2 ) mod n
1 2
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,b 1 = 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.
4.10. 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).
4.11. 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.
4.12. 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:
- 610 20964 1234567
, ,
987 1987 111111.11
4.13. 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.
4.14. 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:
{ ∈
a
≡
a)
n
≠ | | ≤ | | ≤
≥ ≡
≡ ≡ … 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 p2p3…ps)
nªn
a(n-1)/2 ≡ -1 9mod n)
b) NÕu n lµ mét sè hîp sè lÎ, chøng minh r»ng : | G(n) | ≤ (n-
1) /2
c) 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.
4.15. Gi¶ sö ta cã thuËt to¸n Las-Vegas víi x¸c suÊt sai ε.
a) 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-ε)
b) Sè phÐp thö trung b×nh ®Ó ®¹t thµnh c«ng lµ :
- ∞
∑
n=1 (n × pn)
.
H·y chøng tá r»ng gi¸ trÞ nµy b»ng 1/(1-ε)
c) 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µ:
log 2δ
log 2ε
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:
a) X¸c ®Þnh 4 c¨n bËc hai cña modulo n, trong ®ã n
=pq.
b) TÝnh phÐp m· y = ek(32767)
c) 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?.
nguon tai.lieu . vn