Xem mẫu
- Ch−¬ng 4
HÖ mËt RSA v vÊn ®Ò ph©n tÝch thõa sè
4.1. Giíi thiÖu vÒ hÖ mËt kho¸ c«ng khai
Trong m« h×nh mËt m cæ ®iÓn tr−íc ®©y m hiÖn nay ®ang ®−îc nghiªn
cøu Alice (ng−êi göi) v Bob (ng−êi nhËn) chän mét c¸ch bÝ mËt kho¸ K. Sau
®ã dïng K ®Ó t¹o luËt m ho¸ ekv luËt gi¶i m dk. Trong hÖ mËt n y dk hoÆc
gièng nh− ek hoÆc dÔ d ng nhËn ®−îc tõ nã (vÝ dô trong hÖ DES qu¸ tr×nh gi¶i
m ho n to n t−¬ng tù nh− qu¸ tr×nh m nh−ng thñ tôc kho¸ ng−îc l¹i). C¸c
hÖ mËt thuéc lo¹i n y ®−îc gäi l hÖ mËt kho¸ bÝ mËt, nÕu ®Ó lé ek th× l m cho
hÖ thèng mÊt an to n.
Nh−îc ®iÓm cña hÖ mËt n y l nã yªu cÇu ph¶i cã th«ng tin tr−íc vÒ
kho¸ K gi÷a Alice v Bob qua mét kªnh an to n tr−íc khi göi mét b¶n m bÊt
kú. Trªn thùc tÕ ®iÒu n y rÊt khã ®¶m b¶o. Ch¼ng h¹n khi Alice v Bob ë c¸ch
xa nhau v hä chØ cã thÓ liªn l¹c víi nhau b»ng th− tÝn ®iÖn tö (Email). Trong
t×nh huèng ®ã Alice v Bob kh«ng thÓ t¹o mét kªnh b¶o mËt víi gi¸ ph¶i
ch¨ng.
ý t−ëng x©y dùng mét hÖ mËt kho¸ c«ng khai (hay kho¸ dïng chung) l
t×m mét hÖ mËt kh«ng cã kh¶ n¨ng tÝnh to¸n ®Ó x¸c ®Þnh dkkhi biÕt ek. NÕu
thùc hiÖn ®−îc nh− vËy th× quy t¾c m ek cã thÓ ®−îc c«ng khai b»ng c¸ch
c«ng bè nã trong mét danh b¹ (bëi vËy nªn cã thuËt ng÷ hÖ mËt kho¸ c«ng
khai). ¦u ®iÓm cña hÖ mËt kho¸ c«ng khai l ë chç Alice (hoÆc bÊt k× mét ai)
cã thÓ göi mét b¶n tin ® m cho Bob (m kh«ng cÇn th«ng tin tr−íc vÒ kho¸
mËt) b»ng c¸ch dïng luËt m c«ng khai ek. Ng−êi nhËn A sÏ l ng−êi duy nhÊt
cã thÓ gi¶i ®−îc b¶n m n y b»ng c¸ch sö dông luËt gi¶i m bÝ mËt dk cña
m×nh.
Cã thÓ h×nh dung hÖ mËt n y t−¬ng tù nh− sau. Alice ®Æt mét vËt v o
mét hép kim lo¹i v råi kho¸ nã l¹i b»ng mét kho¸ sè do Bob ®Ó l¹i. ChØ cã
Bob l ng−êi duy nhÊt cã thÓ më ®−îc hép v× chØ cã anh ta míi biÕt tæ hîp m
cña kho¸ sè cña m×nh.
- ý t−ëng vÒ mét hÖ mËt kho¸ c«ng khai ® ®ùoc Diffie v Hellman ®−a
ra v o n¨m 1976. Cßn viÖc hiÖn thùc ho¸ nã th× do Rivesrt, Shamir v
Adleman ®−a ra ®Çu tiªn v o n¨m 1977, hä ® t¹o nªn hÖ mËt næi tiÕng RSA
(sÏ ®−îc nghiªn cøu trong ch−¬ng n y). KÓ tõ ®ã mét sè hÖ ®−îc c«ng bè, ®é
mËt cña chóng dùa trªn c¸c b i to¸n tÝnh to¸n kh¸c nhau. Sau ®©y l c¸c hÖ
mËt kho¸ c«ng khai quan träng :
+ HÖ mËt RSA:
§é b¶o mËt cña hÖ RSA dùa trªn ®é khã cña viÖc ph©n tÝch ra thõa sè
nguyªn tè c¸c sè nguyªn lín. HÖ n y sÏ ®−îc m« t¶ trong phÇn 4.3.
+ HÖ mËt xÕp ba l« Merkle - Hellman:
HÖ n y v c¸c hÖ liªn quan dùa trªn tÝnh khã gi¶i cña b i to¸n tæng c¸c
tËp con (b i to¸n n y l b i to¸n NP ®Çy ®ñ – l mét líp kh¸ lín c¸c b i to¸n
kh«ng cã thuËt gi¶i ®−îc biÕt trong thêi gian ®a thøc). Tuy nhiªn tÊt c¶ c¸c hÖ
mËt xÕp ba l« kh¸c nhau ®Òu ® bÞ chøng tá l kh«ng mËt (ngo¹i trõ hÖ mËt
Chor – Rivest sÏ ®−îc nªu d−íi ®©y). HÖ mËt n y ®−îc xÐt ë ch−¬ng 5.
+ HÖ mËt McEliece:
HÖ n y dùa trªn lý thuyÕt m ®¹i sè v vÉn cßn ®−îc coi l an to n. HÖ
mËt McEliece dùa trªn b i to¸n gi¶i m cho c¸c m tuyÕn tÝnh (còng l mét b i
to¸n NP ®Çy ®ñ). HÖ mËt McEliece ®−îc tr×nh b y ë ch−¬ng 5.
+ HÖ mËt Elgamal:
HÖ mËt Elgamal dùa trªn tÝnh khã gi¶i cña b i to¸n logarithm rêi r¹c
trªn c¸c tr−êng h÷u h¹n (xem trong ch−¬ng 5).
+ HÖ mËt Chor - Rivest:
HÖ mËt Chor - Rivest còng ®−îc xem nh− mét lo¹i hÖ mËt xÕp ba l«.
Tuy nhiªn nã vÉn ®−îc coi l an to n.
+ HÖ mËt trªn c¸c ®−êng cong Elliptic
C¸c hÖ mËt n y l biÕn t−íng c¶u c¸c hÖ mËt kh¸c (ch¼ng h¹n nh− hÖ
mËt Elgamal) , chóng l m viÖc trªn c¸c ®−êng cong Elliptic chø kh«ng ph¶i l
trªn c¸c tr−êng h÷u h¹n. HÖ mËt n y ®¶m b¶o ®é mËt víi kho¸ sè nhá h¬n c¸c
hÖ mËt kho¸ c«ng khai kh¸c (xem ch−¬ng 5).
Mét chó ý quan träng l mét hÖ mËt kho¸ c«ng khai kh«ng bao giê cã
thÓ ®¶m b¶o ®−îc ®é mËt tuyÖt ®èi (an to n v« ®iÒu kiÖn). Së dÜ nh− vËy v× ®èi
ph−¬ng khi nghiªn cøu mét b¶n m y cã thÓ m lÇn l−ît c¸c b¶n râ b»ng luËt
m c«ng khai ek cho tíi khi anh ta t×m ®−îc b¶n râ duy nhÊt x ®¶m b¶o y = ek
- (x). B¶n râ n y chÝnh l kÕt qu¶ gi¶i m cña y. Bëi vËy ta chØ nghiªn cøu ®é
mËt vÒ mÆt tÝnh to¸n cña c¸c hÖ mËt n y.
Mét kh¸i niÖm cã Ých khi nghiªn cøu hÖ mËt kho¸ c«ng khai l kh¸i
niÖm vÒ h m cöa sËp mét chiÒu. Ta ®Þnh nghÜa kh¸i niÖm n y mét c¸ch kh«ng
h×nh thøc.
H m m kho¸ c«ng khai ek cña Bob ph¶i l mét h m dÔ tÝnh to¸n. Song
viÖc t×m h m ng−îc (h m gi¶i m ) ph¶i rÊt khã kh¨n (®èi víi bÊt kú ai kh«ng
ph¶i l Bob). §Æc tÝnh dÔ tÝnh to¸n nh−ng khã tÝnh to¸n h m ng−îc th−êng
®−îc gäi l ®Æc tÝnh mét chiÒu. Bëi vËy ®iÒu kiÖn c©n thiÕt l ek ph¶i l h m
mét chiÒu.
C¸c h m mét chiÒu ®ãng vai trß quan träng trong mËt m häc: chóng rÊt
quan trong c¸c hÖ mËt kho¸ c«ng khai v trong nhiÒu lÜnh vùc kh¸c. §¸ng tiÕc
l mÆc dï cã rts nhiÒu h m ®−îc coi l h m mét chiÒu nh−ng cho tíi nay vÉn
kh«ng tån t¹i mét h m n o cã thÓ chøng minh ®−îc l h m mét chiÒu.
Sau ®©y l mét vÝ dô vÒ mét h m ®−îc coi l h m mét chiÒu. Gi¶ sö n l
tÝch cña hai sè nguyªn tè lín p v q, gi¶ sö b l mét sè nguyªn d−¬ng. Khi ®ã
ta x¸c ®Þnh ¸nh x¹ f : Zn Zn l
f(x) = xb mod n
(víi b v n ® ®−îc chän thÝch hîp th× ®©y chÝnh l h m m RSA, sau n y sÏ
cßn nãi nhiÒu vÒ nã).
§Ó x©y dùng mét hÖ mËt kho¸ c«ng khai th× viÖc t×m ®−îc mét h m mét
chiÒu vÉn ch−a ®ñ. Ta kh«ng muèn ek l h m mét chiÒu ®èi víi Bob v× anh ta
ph¶i cã kh¶ n¨ng gi¶i m c¸c b¶n tin nhËn ®−îc mét c¸ch hiÖu qu¶. §iÒu cÇn
thiÕt l Bob ph¶i cã mét cöa sËp chøa th«ng tin bÝ mËt cho phÐp dÔ d ng t×m
h m ng−îc cña ek. Nh− vËy Bob cã thÓ gi¶i m mét c¸ch h÷u hiÖu v× anh ta cã
mét hiÓu biÕt tuyÖt mËt n o ®ã vÒ K. Bëi vËy mét h m ®−îc gäi l cöa sËp mét
chiÒu nÕu nã l h m mét chiÒu v nã trë nªn dÔ tÝnh ng−îc nÕu biÕt mét cöa
sËp mhÊt ®Þnh.
Ta sÏ xÐt c¸ch t×m mét cöa sËp ®èi víi h m f nªu ë trªn trong phÇn 4.3.
C¸c t×m n y sÏ dÉn ®Õn hÖ mËt RSA.
- 4.2. mét sè vÊn ®Ò s©u h¬n vÒ lý thuyÕt sè
Tr−íc khi m« t¶ hÖ mËt RSA l m viÖc ra sao cÇn ph¶i xem xÐt mét sè
yÕu tè liªn quan ®Õn lý thuyÕt sè v sè häc modulo. Hai kÕt qu¶ cÇn biÕt l
thuËt to¸n Euclide v ®Þnh lý phÇn d− China.
4.2.1 ThuËt to¸n Euclide
Trong ch−¬ng 1 ® xÐt Zn l mét v nh víi sè nguyªn d−¬ng bÊt kú n. Ta
còng ® chøng tá r»ng phÇn tö b ∈ Zn cã phÇn tö nghÞch ®¶o (phÇn tö ng−îc
cña phÐp nh©n) khi v chØ khi −CLN(b,n) = 1 v c¸c sè nguyªn d−¬ng nhá h¬n
n v nguyªn tè cïng nhau víi n b»ng φ (n).
TËp c¸c thÆng d− theo modulo n v nguyªn tè cïng nhau víi n ®−îc ký
hiÖu l Zn* .Kh«ng khã kh¨n cã thÓ thÊy r»ng Zn* sÏ t¹o nªn mét nhãm Abel
®èi víi phÐp nh©n. Ta còng biÕt r»ng, phÐp nh©n theo modulo n l giao ho¸n v
kÕt hîp v phÇn tö ®¬n vÞ l 1. Mét phÇn tö bÊt kú trong Zn*®Òu cã nghÞch ®¶o
béi (còng n»m trong Zn*). Cuèi cïng Zn* l ®ãng ®èi víi phÐp nh©n v× xy l
nguyªn tè cïng nhau víi n khi x v y nguyªn tè cïng nhau víi n. (H y chøng
minh ®iÒu n y!)
Cho tíi b©y giê ta chØ biÕt r»ng mét phÇn tö b bÊt k× ∈ Zn* ®Òu cã nghÞch
®¶o b-1 song viÖc tÝnh nã vÉn ch−a nãi ®Õn. Mét thuËt to¸n nh− vËy ®−îc gäi l
thuËt to¸n Euclide më réng.
Tr−íc tiªn ta sÏ m« t¶ thuËt to¸n Euclide, th«ng th−êng thuËt to¸n n y
®−îc dïng ®Ó tÝnh −íc sè chung lín nhÊt (−CLN) cña hai sè nguyªn d−¬ng r0
v r1 víi r0 > r1.ThuËt to¸n Euclide bao gåm viÖc thùc hiÖn c¸c phÐp to¸n nh−
sau:
r0 = q1 r1 +r2 0 < r2 < r1
r1 = q2 r2 +r3 0 < r3 < r2
.
.
rm -2 = qm -1 rm -1 +rm 0 < rm -1 < rm
rm -1 = qm rm
Khi ®ã dÔ d ng chøng tá ®−îc r»ng
−CLN(r0 , r1 ) = −CLN(r1 , r2 ) = . . . −CLN(rm-1 , rm ) = rm
- Bëi vËy −CLN(r0 , r1 ) = rm
V× thuËt to¸n Euclide tÝnh c¸c −CLN nªn cã thÓ ¸p dông nã ®Ó x¸c ®Þnh
xem liÖu mét sè nguyªn d−¬ng b < n cã nghÞch ®¶o theo modulo n kh«ng b»ng
c¸ch b¾t ®Çu víi r0 = n v r1 = b. Tuy nhiªn thuËt to¸n n y kh«ng cho phÐp tÝnh
gi¸ trÞ cña phÇn tö nghÞch ®¶o (nÕu nã tån t¹i).
B©y giê gi¶ sö ®Þnh nghÜa mét d y sè t0 , t1 ,.... ,tm theo c¸c c«ng thøc
truy to¸n sau (trong ®ã c¸c gi¸ trÞ qj ® ®−îc x¸c ®Þnh ë trªn)
t0 = 0
t1 = 1
tj = tj-2- qj-1 tj-1 mod r0 nÕu j ≥ 2
Ta cã kÕt qu¶ quan träng sau
§Þnh lý 4.1.
Víi 0 ≤ j ≤ m, ta cã rj ≡ tjr1 (mod r0), trong ®ã c¸c gi¸ trÞ qj v rj ®−îc
x¸c ®Þnh theo thuËt to¸n Euclide cßn c¸c gi¸ trÞ tj ®−îc x¸c ®Þnh theo c«ng
thøc truy to¸n ë trªn.
Chøng minh:
Ta chøng minh b»ng c¸ch quy n¹p theo j. §Þnh lý hiÓn nhiªn ®óng víi j
= 0 v j = 1. Gi¶ sö ®Þnh lý còng ®óng víi j = i-1 v j = i-2, trong ®ã i ≥ 2; sau
®©y ta sÏ chøng tá ®Þnh lý ®óng víi j = i. Theo quy n¹p ta cã
ri-2 ≡ ti-2 r1 (mod r0)
v ri-1 ≡ ti-1 r1 (mod r0)
B©y giê ta tÝnh
ri = ri-2 - qi-1 ri-1
≡ ti-2 r1 - qi-1 ti-1 r1 (mod r0)
≡ (ti-2 - qi-1 ti-1)r1 (mod r0)
≡ ti r1 (mod r0)
Bëi vËy theo quy n¹p ®Þnh lý l ®óng.
HÖ qu¶ rót ra trùc tiÕp tõ ®Þnh lý trªn.
HÖ qu¶ 4.2:
- Gi¶ sö −CLN (r0,r1) = 1, khi ®ã tm = r1-1 mod r0.
H×n 2.1 ThuËt to¸n Euclide më réng:
1. n0 = n
2. b0 = b
3. t0 = 0
4. t=1
5. q = n0 /b0
6. r = n0 - q×b0
7. While r > 0 do
8. temp = t0 -q×t
9. if temp ≥ 0 then temp = temp mod n
10. if temp < 0 then temp = n - ((- temp) mod n)
11. t0 = t
12. t = temp
13. n0 = b 0
14. b0 = r
15. q = n0 /b0
16. r = n0 - q×b0
17. if b0 ≠ 1 then b kh«ng cã nghÞch ®¶o theo
modulo n
-1
else b = t mod n .
XÐt thÊy d y c¸c sè t0, t1, . . . , tm cã thÓ ®−îc tÝnh to¸n trong thuËt to¸n
Euclide ®ång thêi nh− c¸c gi¸ trÞ qj v rj. H×nh 4.1 tr×nh b y thuËt to¸n Euclide
më réng ®Ó tÝnh nghÞch ®¶o cña b theo modulo n (nÕu nã tån t¹i). Trong thuËt
to¸n n y kh«ng ph¶i dïng m¶ng (array) ®Ó ghi c¸c gi¸ trÞ qj, rj v tj v× chØ cÇn
nhí hai gi¸ trÞ cuèi cïng trong mçi d y n y ë mét ®iÓm bÊt k× trong thuËt to¸n.
Trong b−íc 10 cña thuËt to¸n ta ® viÕt biÓu thøc cho biÕn temp theo
c¸ch ®Ó phÐp rót gän theo modulo n ®−îc thùc hiÖn ®èi víi sè d−¬ng. (Tr−íc
®©y ® biÕt r»ng viÖc rót gän theo modulo cña c¸c sè ©m sÏ dÉn ®Õn c¸c kÕt
qu¶ ©m ë nhiªï ng«n ng÷ m¸y tÝnh; cßn ë ®©y ta muèn kÕt thóc víi kÕt qu¶
d−¬ng). ë b−íc 12 lu«n cã tb ≡ r (mod n) (kÕt qu¶ n y ® ®−îc chøng minh ë
®Þnh lý 4.1).
- Sau ®©y l mét vÝ dô nhá ®Ó minh ho¹
VÝ dô 4.1.
Gi¶ sö ta cÇn tÝnh 28-1 mod 75. ThuËt to¸n Euclide më réng thùc hiÖn
nh− sau:
75 = 2 × 28 +29 b−íc 6
73 × 28 mod 75 = 19 b−íc 12
28 = 1 × 19 + 9 b−íc 16
3 × 28 mod 75 = 9 b−íc 12
19 = 2 × 9 + 1 b−íc 16
67 × 28 mod 75 = 1 b−íc 12
9=9×1 b−íc 16
V× thÕ 28-1 mod 75 = 67.
4.2.2. §Þnh lý phÇn d− China
§Þnh lý n y thùc sù l mét ph−¬ng ph¸p gi¶i c¸c hÖ ph−¬ng tr×nh
®ång d−. Gi¶ sö m1, . . . , mr l c¸c sè nguyªn tè cïng nhau tõng ®«i mét (tøc
−CLN(mi,mj)=1 nÕu j≠i). Gi¶ sö a1,. . ., ar l c¸c sè nguyªn xÐt hÖ ph−¬ng tr×nh
®ång d− sau:
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
.
.
x ≡ ar (mod mr)
§Þnh lý phÇn d− China kh¼ng ®Þnh r»ng hÖ n y cã nghiÖm duy nhÊt
theo modulo M = m1×m2×. . . ×mr. Ta sÏ chøng minh kÕt qu¶ ®ã trong phÇn
n y v còng m« t¶ mét thuËt to¸n h÷u hiÖu ®Ó gi¶i hÖ ®ång d− thøc d¹ng trªn.
§Ó thuËn tiÖn, xÐt h m π : ZM Zm1× . . .×Zmr. H m n y ®−îc ®Þnh
nghÜa nh− sau:
π(x) = (x mod m1, . . . , x mod mr )
- VÝ dô 4.2
Gi¶ sö r = 2, m1 = 5 v m2 = 3, bëi vËy M = 15. Khi ®ã h m π cã gi¸ trÞ
sau
π(0) = (0,0) π(1) = (1,1) π(2) = (2,2)
π(3) = (3,0) π(4) = (4,1) π(5) = (0,2)
π(6) = (1,0) π(7) = (2,1) π(8) = (3,2)
π(9) = (4,0) π(10) =(0,1) π(11) =(1,2)
π(12) =(2,0) π(13) =(3,1) π(14) =(4,2)
ViÖc chøng minh ®Þnh lý phÇn d− China t−¬ng ®−¬ng víi viÖc chøng
minh r»ng h m π l mét song ¸nh. §iÒu n y cã thÓ dÔ d ng thÊy ®−îc ë vÝ dô
4.2. Trong thùc tÕ cã thÓ ®−a ra mét c«ng thøc t−êng minh tæng qu¸t cho h m
ng−îc π-1.
Víi 1 ≤ i ≤ r, ®Þnh nghÜa:
Mi = M/mi
Khi ®ã, dÔ d ng thÊy r»ng
−CLN(Mi,mi) = 1
víi 1 ≤ i ≤ r. TiÕp theo, víi 1 ≤ i ≤ r, ®Þnh nghÜa
yi = Mi-1 mod mi
(phÇn tö nghÞch ®¶o n y tån t¹i do −CLN(Mi,mi) = 1 v cã thÓ t×m ®−îc b»ng
thuËt to¸n Euclide). CÇn ®Ó ý r»ng
Miyi ≡ 1 (mod mi)
víi 1 ≤ i ≤ r.
B©y giê ta ®Þnh nghÜa h m ρ: Zm1 × . . . × Zmr ZM nh− sau
( )r
ρ a ,...a r = ∑ a M y mod
1
M
i=1 i i i
Ta sÏ chøng tá r»ng ρ = π-1 , tøc l nã cho mét c«ng thøc t−êng minh ®Ó gi¶i
hÖ ®ång d− thøc ban ®Çu.
KÝ hiÖu X = ρ(a1, . . . ,ar) v cho 1 ≤ j ≤ r. XÐt sè h¹ng aiMiyi trong tæng
trªn khi rót gän theo modulo mj. NÕu i = j th×
aiMiyi ≡ ai (mod mi)
- v× Miyi ≡ 1 (mod mi)
MÆt kh¸c, nÕu i ≠ j th×
aiMiyi ≡ 0(mod mj)
do mi Mi trong tr−êng hîp n y. Bëi vËy chóng ta cã
X ≡ ∑ a iM i y i (mod m j )
≡ a i (mod m j )
Do ®iÒu n y ®óng ®èi víi mäi j, 1 ≤ j ≤ r, nªn X l nghiÖm cña hÖ ph−¬ng tr×nh
®ång d−.
Tíi lóc n y cÇn ph¶i chøng tá r»ng nghiÖm X l duy nhÊt theo modulo
M v ®iÒu n y cã thÓ ®−îc chøng tá b»ng c¸ch tÝnh to¸n ®¬n gi¶n. π l h m
tõ mét miÒn cã lùc l−îng M sang mét miÒn cã lùc l−îng M. Ta võa míi chøng
tá r»ng π l mét to n ¸nh. Bëi vËy π ph¶i còng l mét ®¬n ¸nh (tøc l phÐp
t−¬ng øng 1 - 1) do miÒn x¸c ®Þnh v miÒn gi¸ trÞ cã cïng lùc l−îng. §iÒu ®ã
kÐo theo π l mét song ¸nh v π-1 = p. Còng cÇn chó ý l π-1 l mét h m tuyÕn
tÝnh cña c¸c biÕn a1,. . ., ar.
Sau ®©y l mét vÝ dô lín h¬n ®Ó minh ho¹
VÝ dô 4.3
Gi¶ sö r = 3, m1 = 7, m2 = 11 v m3 = 13. Khi ®ã M = 1001. Ta tÝnh M1
= 143, M2 = 91 v M3 = 77 v sau ®ã tÝnh y1 = 5, y2 = 4 v y3 = 12. Khi ®ã h m
π-1: Z7×Z11×Z13 Z1001 cã d¹ng:
π-1(a1,a2,a3) = 715a1 +364a2 + 924a3 mod 1001
VÝ dô, nÕu x ≡ 5 (mod 7), x ≡ 3 (mod 11) v x ≡ 10 (mod 13) th× c«ng thøc
trªn sÏ cho ta biÕt r»ng
x = 715 × 5 + 364 × 3 + 924 × 10 mod 1001
= 13907 mod 1001
= 894 mod 1001
§iÒu n y cã thÓ kiÓm tra ®−îc b»ng c¸ch rót gän 894 theo modulo 7, 11
v 13.
§Ó tham kh¶o sau n y, ta sÏ ghi c¸c kÕt qu¶ ë phÇn n y d−íi d¹ng mét
®Þnh lý
- §Þnh lý 4.3 (§Þnh lý phÇn d− China)
Gi¶ sö m1, . . . ,mr l c¸c sè nguyªn d−¬ng nguyªn tè cïng nhau tõng ®«i
mét v cho a1, . . ., ar l c¸c sè nguyªn. Khi ®ã, hÖ r ®ång d− thøc x ≡ ai (mod
mi) (1 ≤ i ≤ r ) sÏ cã mét nghiÖm duy nhÊt theo modulo M = m1× . . . × mr ®−îc
cho theo c«ng thøc
r
x = ∑ a i M i y i mod M
i =1
trong ®ã Mi = M/mi v yi = Mi-1 mod mi, víi 1 ≤ i ≤ r.
4.2.3. C¸c kiÕn thøc cÇn thiÕt kh¸c
Sau ®©y sÏ nh¾c tíi mét kÕt qu¶ kh¸c trong lý thuyÕt nhãm s¬ cÊp: ®Þnh
lý Lagrange. §Þnh lý n y cã liªn quan ®Õn c¸ch ®Ò cËp vÒ hÖ mËt RSA. Víi
mét nhãm nh©n h÷u h¹n G, ta ®Þnh nghÜa cÊp cña mét phÇn tö g ∈ G l sè
nguyªn d−¬ng m bÐ nhÊt sao cho gm = 1. Ta cã kÕt qu¶ sau ®©y (kh«ng chøng
minh ).
§Þnh lý 4.4 (Lagrange )
Gi¶ sö G l mét nhãm cÊp n v g ∈ G. Khi ®ã cÊp cña g l −íc cña n.
Víi môc ®Ých ®−a ra, hÖ qu¶ sau rÊt quan träng.
HÖ qu¶ 4.5
NÕu b ∈ Zn* th× bφ(n) ≡ 1 (mod n)
Chøng minh: Zn* l nhãm nh©n cÊp φ(n).
HÖ qu¶ 4.6 (Ferma)
Gi¶ sö p l sè nguyªn tè v b ∈ Zp. Khi ®ã bp ≡ b (mod p).
Chøng minh:
NÕu p l sè nguyªn tè th× φ(n) = p-1. Bëi vËy, víi b≡0(mod p),
kÕt qu¶ trªn ®−îc rót ra tõ hÖ qu¶ 4.5. Víi b ≡ 0 (mod p), kÕt qu¶ trªn
vÉn ®óng do 0p ≡ 0 (mod 0).
Cho tíi giê ta ® biÕt r»ng, nÕu p l sè nguyªn tè th× Zp* l mét nhãm
cÊp p-1 v mét phÇn tö bÊt k× trong Zp* sÏ cã bËc l −íc cña p-1. Tuy nhiªn,
nÕu p l sè nguyªn tè th× nhãm Zp* l nhãm cyclic: tån t¹i mét phÇn tö α ∈ Zp*
- cã cÊp b»ng p-1. Ta kh«ng chøng minh kÕt qu¶ quan träng n y nh−ng sÏ ghi
l¹i ®Ó tham kh¶o sau n y.
§Þnh lý 4.7.
NÕu p l sè nguyªn tè th× Zp* l nhãm cyclic.
Mét phÇn tö α cã cÊp p-1 ®−îc gäi l phÇn tö nguyªn thuû modulo p.
XÐt thÊy α l phÇn tö nguyªn thuû khi v chØ khi:
{αi : 0 ≤ i ≤ p-2} = Zp*
B©y giê gi¶ sö p – nguyªn tè v α - phÇn tö nguyªn thuû modulo p. Mét phÇn
tö bÊt k× β ∈ Zp* cã thÓ ®−îc viÕt nh− sau: β = αi, trong ®ã 0 ≤ i ≤ p-2 (theo
mét c¸ch duy nhÊt ). Kh«ng khã kh¨n cã thÓ chøng tá r»ng cÊp cña β = αi l :
p -1
UCLN(p - 1, i)
Nh− vËy b¶n th©n β l phÇn tö nguyªn thuû khi v chØ khi −CLN (p-1,i) = 1.
§iÒu ®ã dÉn ®Õn l sè c¸c phÇn tö nguyªn thuû theo modulo p = φ(p-1).
VÝ dô 4.4:
Gi¶ sö p=13. B»ng c¸ch tÝnh c¸c luü thõa liªn tiÕp cña 2 ta cã thÓ thÊy
r»ng 2 l phÇn tö nguyªn thuû theo modulo 13:
20 mod 13 =1 21 mod 13 =2 22 mod 13 =4
23 mod 13 =8 24 mod 13 =3 25 mod 13 =6
26 mod 13 =12 27 mod 13 =11 28 mod 13 =9
29 mod 13 =5 210 mod 13 =10 211 mod 13 =7
PhÇn tö 2i l nguyªn thuû khi v chØ khi −CLN(i,12) = 1; nghÜa l khi v chØ
khi i = 1, 5, 7 hoÆc 11. Bëi vËy c¸c phÇn tö nguyªn thuû theo modulo 13 l 2,
6, 7 v 11.
4.3. hÖ mËt RSA
B©y giê chóng ta cã thÓ m« t¶ hÖ mËt RSA. HÖ mËt n y sö dông c¸c tÝnh
to¸n trong Zn, trong ®ã n l tÝch cña 2 sè nguyªn tè ph©n biÖt p v q. Ta nhËn
thÊy r»ng φ(n) = (p-1)(q-1).
- M« t¶ h×nh thøc cña hÖ mËt ®−îc cho trong h×nh 4.2 . Ta h y kiÓm tra
xem c¸c phÐp m v gi¶i m cã ph¶i l c¸c phÐp to¸n nghÞch ®¶o cña nhau hay
kh«ng. V×
ab ≡ 1 (mod φ(n))
nªn ta cã ab = t φ(n) + 1
víi mét sè nguyªn t ≥ 1 n o ®ã. Gi¶ sö x ∈ Zp*; khi ®ã ta cã:
(xb)a ≡ xtφ(n)+1 (mod n)
≡ (xφ(n))t x (mod n)
≡ 1t x (mod n)
≡ x (mod n)
H×nh 4.2: HÖ mËt RSA
Cho n = p.q trong ®ã p v q l c¸c sè nguyªn tè. §Æt P = C = Zn
v ®Þnh nghÜa
K = {(n,p,q,a,b): n = p.q, p,q l c¸c sè nguyªn tè, ab ≡ 1(mod φ(n))}
Víi K = (n,p,q,a,b) ta x¸c ®Þnh
eK (x) = xb mod n
v dK (y) = ya mod n
(x,y) ∈ Zn. C¸c gi¸ trÞ n v b ®−îc c«ng khai , c¸c gi¸ trÞ p,q,a ®−îc gi÷
bÝ mËt.
®óng nh− mong muèn. Xem nh− mét b i tËp, b¹n ®äc h y chøng tá r»ng (xb)a
≡ x (mod n) nÕu x ∈ Zn\ Zp*.
Sau ®©y l mét vÝ dô nhá (tÊt nhiªn l kh«ng mËt ) vÒ hÖ mËt RSA.
VÝ dô 4.5:
Gi¶ sö Bob chän p = 101 v q = 113. Khi ®ã n = 11413 v φ(n) =
100×112 = 11200. V× 11200 = 26527, nªn cã thÓ dïng mét sè nguyªn b nh−
mét sè mò m ho¸ khi v chØ khi b kh«ng chia hÕt cho 2, 5 hoÆc 7. (V× thÕ
trong thùc tÕ Bob sÏ kh«ng ph©n tÝch φ(n), anh ta sÏ kiÓm tra ®iÒu kiÖn
−CLN(φ(n),b) = 1 b»ng thuËt to¸n Euclide. Gi¶ sö Bob chän b = 3533, khi ®ã
theo thuËt to¸n Euclide më réng:
b-1 = 6597 mod 11200
- Bëi vËy sè mò mËt ®Ó gi¶i m cña Bob l a = 6597.
Bob sÏ c«ng bè n = 11413 v b = 3533 trong mét danh b¹. B©y giê, gi¶
sö Alice muèn göi b¶n râ 9726 tíi Bob. C« ta tÝnh
97263533 mod 11413 = 5761
råi göi b¶n m 5761 trªn kªnh. Khi ®ã Bob nhËn ®−îc b¶n m 5761, anh ta sö
dông sè mò a mËt ®Ó tÝnh:
57616597 mod 11413 = 9762
(cho tíi lóc n y, c¸c phÐp m v gi¶i m cho hÖ mËt ® kh¸ phøc t¹p, tuy nhiªn
ta sÏ th¶o luËn vÒ c¸c thuËt to¸n h÷u hiÖu cho c¸c phÐp to¸n n y ë phÇn sau).
§é mËt cña hÖ RSA ®−îc dùa trªn gi¶ thiÕt l h m m ek(x)= xb mod n
l h m mét chiÒu. Bëi vËy th¸m m sÏ kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n ®Ó
gi¶i m mét b¶n m . Cöa sËp cho phÐp Bob gi¶i m ®−îc chÝnh l th«ng tin vÒ
phÐp ph©n tÝch thõa sè n (n = pq). V× Bob biÕt ph©n tÝch n y, anh ta cã thÓ tÝnh
φ(n) = (p-1)(q-1) v råi tÝnh sè mò gi¶i m a b»ng c¸ch sö dông thuËt to¸n
Euclide më réng. Sau n y chóng ta sÏ cßn tiÕp tôc nãi thªm vÒ vÊn dÒ n y.
4.4. Thùc hiÖn hÖ mËt RSA
Cã nhiÒu khÝa c¹nh cÇn th¶o luËn vÒ hÖ mËt RSA bao gåm c¸c chi tiÕt
vÒ viÖc thiÕt lËp hÖ mËt, tÝnh hiÖu qu¶ cña phÐp m v gi¶i m v ®é mËt cña
hÖ. §Ó thiÕt lËp hÖ thèng, Bob sÏ tu©n theo c¸c b−íc ®−îc nªu trong h×nh 4.3.
H×nh 4.3 ThiÕt lËp hÖ mËt RSA
1. Bob t¹o hai sè nguyªn tè lín p v q
2. Bob tÝnh n = p.q v φ(n) = (p-1)(q-1)
3. Bob chän mét sè ngÉu nhiªn b (0< b < φ(n)) sao cho
−CLN(b,φ(n)) = 1
4. Bob tÝnh a = b-1 mod φ(n) b»ng c¸ch dïng thuËt to¸n Euclide
5. Bob c«ng bè n v b trong mét danh b¹ v chóng l m kho¸ c«ng
khai.
- ViÖc Bob tiÕn h nh c¸c b−íc n y nh− thÕ n o sÏ cßn ®−îc tiÕp tôc th¶o luËn
trong ch−¬ng n y.
C¸ch tÊn c«ng dÔ thÊy nhÊt hÖ mËt n y l th¸m m cè g¾ng ph©n tÝch n
ra c¸c thõa sè nguyªn tè. NÕu thùc hiÖn ®−îc viÖc n y th× cã thÓ dÔ d ng tÝnh
®−îc φ(n) = (p-1)(q-1) råi tÝnh sè mò a tõ b nh− Bob l m (ng−êi ta pháng ®o¸n
r»ng, viÖc ph¸ hÖ mËt RSA l t−¬ng ®−¬ng ®a thøc víi viÖc ph©n tÝch n, tuy
nhiªn ®iÒu n y vÉn cßn ch−a ®−îc chøng minh. Hai b i to¸n ®−îc gäi l t−¬ng
®−¬ng ®a thøc nÕu tån t¹i mét thuËt to¸n thêi gian ®a thøc cho b i to¸n n y sÏ
suy ra ®−îc sù tån t¹i mét thuËt to¸n thêi gian ®a thøc cho b i to¸n kia).
V× thÕ hÖ mËt RSA ®−îc coi l mËt th× nhÊt thiÕt n = pq ph¶i l mét sè
®ñ lín ®Ó viÖc ph©n tÝch nã kh«ng cã kh¶ n¨ng vÒ mÆt tÝnh to¸n. C¸c thuËt to¸n
ph©n tÝch hiÖn thêi cã kh¶ n¨ng ph©n tÝch c¸c sè cã 130 ch÷ sè thËp ph©n (chi
tiÕt h¬n vÒ b i to¸n ph©n tÝch thõa sè nguyªn tè xem trong phÇn 4.8). V× vËy
®Ó ®¶m b¶o an to n nªn chän c¸c sè p v q chõng 100 ch÷ sè, khi ®ã n sÏ cã
tíi 200 ch÷ sè. Mét v i ¸p dông phÇn cøng cña RSA sö dông m« ®un cã ®é d i
512 bit. Tuy nhiªn mét m« ®un 512 bit t−¬ng øng víi mét sè cã 154 ch÷ sè
thËp ph©n (v× sè c¸c bit trong biÓu diÔn nhÞ ph©n cña mét sè nguyªn b¨ng
log210 lÇn cña c¸c ch÷ sè thËp ph©n) v× vËy kh«ng ®ñ ®¶m b¶o an to n l©u d i.
B©y giê t¹m thêi g¸c l¹i vÊn ®Ò t×m c¸c sè nguyªn tè cã 100 ch÷ sè ®Ó xem xÐt
viÖc thùc hiÖn c¸c phÐp to¸n sè häc trong m v gi¶i m . PhÐp m (hoÆc gi¶i
m ) sÏ xoay quanh phÐp lÊy luü thõa theo modulo n. V× n l mét sè rÊt lín
nªn ta ph¶i sö dông sè häc lÊy chÝnh x¸c nhiÒu lÇn (multi – precision) ®Ó thùc
hiÖn c¸c tÝnh to¸n trong Zn v thêi gian tÝnh to¸n cÇn thiÕt sÏ phô thuéc v o sè
c¸c bÝt trong biÓu diÔn nhÞ ph©n cña n.
Gi¶ sö n cã k bit trong biÓu diÔn nhÞ ph©n, tøc l k = log2 n + 1. Sö
dông kÜ thuËt sè häc ë bËc trung häc, dÔ d ng thÊy r»ng mét phÐp céng hai sè
nguyªn k bit cã thÓ thùc hiÖn trong thêi gian O(k) v mét phÐp nh©n cã thÓ
thùc hiÖn trong thêi gian O(k2). Còng vËy, phÐp rót gän mét sè nguyªn theo
modulo n (sè n y cã nhiÒu nhÊt l 2K bÝt )cã thÓ thùc hiÖn trong thêi gian
O(k2) (®Ó thùc hiÖn phÐp chia v phÐp t×m phÇn d−). B©y giê gi¶ sö r»ng
x,y∈Zn (ë ®©y xem r»ng 0 ≤ x,y ≤ n-1). Khi ®ã cã thÓ tÝnh xy mod n tr−íc tiªn
b»ng viÖc tÝnh tÝch xy (l mét sè nguyªn 2k bÝt), råi rót gän cho modulo n. Hai
b−íc n y cã thÓ thùc hiÖn trong thêi gian O(k2). Ta gäi phÐp tÝnh n y l nh©n
modulo.
B©y giê xÐt phÐp lÊy luü thõa theo modulo (tøc l tÝnh h m d¹ng xc mod
n). Nh− nhËn xÐt ë trªn, c¶ hai phÐp m v gi¶i m trong RSA ®Òu l c¸c phÐp
- luü thõa theo modulo. ViÖc tÝnh xc mod n cã thÓ thùc hiÖn b»ng c-1 phÐp nh©n
modulo, tuy nhiªn khi c lín th× c¸ch tÝnh n y rÊt cång kÒnh. Chó ý r»ng c lín
cì nh− φ(n) -1 (l mét sè lín cÊp luü thõa so víi k).
Sö dông biÖn ph¸p "b×nh ph−¬ng v nh©n" ® biÕt sÏ l m gi¶m sè phÐp
nh©n modulo cÇn thiÕt, ®Ó tÝnh x mod n nhiÒu nhÊt l 2l, trong ®ã l l sè c¸c
bit trong biÔu diÔn nhÞ ph©n cña c. V× l ≤ k nªn cã thÓ coi xc mod n ®−îc thùc
hiÖn trong thêi gian O(k3). V× thÕ c¸c phÐp m v gi¶i m ®−îc thùc hiÖn theo
thêi gian ®a thøc (nh− mét h m cña k l sè c¸c bÝt trong mét b¶n râ (hoÆc b¶n
m ).
Trong thuËt to¸n “ b×nh ph−¬ng v nh©n”, ta coi r»ng sè mò b ®−îc biÓu
thÞ ë d¹ng nhÞ ph©n nh− sau:
l -1
b = ∑ bi 2i 2
i =0
Trong ®ã bi = 0 hoÆc 1, 0 ≤ i ≤ l-1. ThuËt to¸n ®Ó tÝnh z = xb mod n ®−îc m« t¶
ë h×nh 4.4.
H×nh 2.5 ThuËt to¸n b×nh ph−¬ng v nh©n ®Ó tÝnh xb mod n
1. z=1
2. for i = l-1 down to 0 do
3. z = z2 mod n
4. if bi = 1 then z = z.x mod n
DÔ d ng tÝnh ®−îc sè c¸c phÐp nh©n modulo thùc hiÖn bëi thuËt to¸n
trªn. Lu«n lu«n ph¶i thùc hiÖn l phÐp b×nh ph−¬ng (ë b−íc 3). Sè phÐp nh©n
trong b−íc 4 b»ng sè c¸c bit "1" trong biÓu diÔn nhÞ ph©n cña b (sè n y thuéc
kho¶ng tõ 0 tíi l). Bëi vËy tæng sè phÐp nh©n modulo cÇn thùc hiÖn n»m trong
kho¶ng tõ l tíi 2l.
Ta sÏ minh ho¹ c¸ch sö dông thuËt to¸n trªn b»ng c¸ch quay trë l¹i vÝ dô
4.5.
VÝ dô 4.5 (tiÕp):
- Ta cã n = 11413 v sè mò m ho¸ c«ng khai b = 3533. Alice sÏ m ho¸ b¶n râ
9726 b»ng c¸ch tÝnh 97263533 mod 11413 theo thuËt to¸n “b×nh ph−¬ng v
nh©n” nh− sau:
i bi z
11 1 12× 9726 = 9726
10 1 97262 × 9726 = 2659
9 0 26592 = 5634
8 1 56342 × 9726 = 9167
7 1 91672 × 9726 = 4958
6 1 49582 × 9726 = 7783
5 0 77832 = 6298
4 0 62982 = 4629
3 1 46292 × 9726 = 10185
2 1 101852 × 9726 = 105
1 0 1052 = 11025
0 1 110252 × 9726 = 5761
Nh− vËy b¶n m l 5761.
CÇn ph¶i nhÊn m¹nh r»ng, nh÷ng øng dông phÇn cøng hiÖu qu¶ nhÊt
hiÖn thêi cña RSA chØ ®¹t ®−îc tèc ®é m ho¸ chõng 600Kb/s (sö dông c¸c m«
®un 512 bÝt) so víi DES cã tèc ®é 1 Gb/s. Nãi c¸ch kh¸c RSA chËm h¬n
kho¶ng 1500 lÇn so víi DES.
§Õn ®©y, ta chØ míi xÐt ®−îc c¸c phÐp m ho¸ v gi¶i m cho RSA. §Ó
thiÕt lËp hÖ mËt RSA, ta cßn ph¶i xÐt viÖc t¹o c¸c sè nguyªn tè p v q (b−íc 1),
b−íc n y sÏ ®−îc nghiªn cøu ë phÇn sau. B−íc 2 kh¸ ®¬n gi¶n v ®−îc thùc
hiÖn trong thêi gian O((log n)2). C¸c b−íc 3 v 4 xoay quanh thuËt to¸n
Euclide, v× thÕ sÏ xÐt qua vÒ ®é phøc t¹p cña thuËt to¸n n y.
Gi¶ sö ta ph¶i tÝnh −CLN cña r0 v r1, trong ®ã r0 > r1 . Trong mçi b−íc
lÆp ®Òu ph¶i tÝnh th−¬ng v phÇn d−, ®iÒu n y cã thÓ thùc hiÖn ®−îc trong thêi
gian O((log r0)2). NÕu t×m ®−îc giíi h¹n trªn cho sè phÐp lÆp th× ta sÏ cã ®−îc
giíi h¹n cho ®é phøc t¹p cña thuËt to¸n. KÕt qu¶ n y ® ®−îc nªu trong ®Þnh lý
LamÐ. §Þnh lý kh¼ng ®Þnh r»ng nÕu s l sè c¸c phÐp lÆp th× f3+2 ≤ r0 , trong ®ã
fi l sè Fibonacci thø i . V×
- 1 + 5
fi =
2
Nªn ®iÒu ®ã kÐo theo s l O(log r0).
§iÒu n y chøng tá r»ng thêi gian ch¹y cña thuËt to¸n Euclide l O((log
n)3) (trªn thùc tÕ, b»ng c¸c ph©n tÝch chi tiÕt h¬n, cã thÓ chøng tá r»ng thêi
gian ch¹y chØ l O((log n)2).
4.5. 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Ët to¸n cho r»ng n l sè nguyªn tè trong khi thùc tÕ n l hîp 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 ®−î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 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 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 tr−ng 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 tr−ng 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 modulo 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) nh−ng 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.
C¸c thÆng d− bËc hai theo modulo 11 l 1,3,4,5 v 9. CÇn ®Ó ý r»ng,
(±1) =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
2
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)
V× b 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 mét sè nguyª n tè lÎ. Víi mét sè nguyª n bÊt kú a ≥ 0 ,
a
ta dÞnh nghÜa ký hiÖu Legendre nh− sau :
p
0 nÕu a ≡ 0 (mod p)
a
= 1 nÕu a l thÆng d− bËc hai theo modulo p
p
- 1 nÕu a 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.
a
Gi¶ sö p l mét sè nguyªn tè. Khi ®ã p
≡ a(p-1)/2 (mod 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.
a
r
nguon tai.lieu . vn
