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
r1 = q2 r2 +r3
.
.
rm -2 = qm -1 rm -1 +rm
rm -1 = qm rm
0 < r2 < r1
0 < r3 < r2
0 < rm -1 < 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ã
vµ
B©y giê ta tÝnh
ri-2 ≡ ti-2 r1 (mod r0)
ri-1 ≡ ti-1 r1 (mod r0)
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.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
n0 = n
b0 = b
t0 = 0
t=1
q = n0 /b0
r = n0 - q×b0
While r > 0 do
temp = t0 -q×t
if temp ≥ 0 then temp = temp mod n
if temp < 0 then temp = n - ((- temp) mod n)
t0 = t
t = temp
n0 = b 0
b0 = r
q = n0 /b0
r = n0 - q×b0
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
73 × 28 mod 75 = 19
28 = 1 × 19 + 9
3 × 28 mod 75 = 9
19 = 2 × 9 + 1
67 × 28 mod 75 = 1
9=9×1
b−íc 6
b−íc 12
b−íc 16
b−íc 12
b−íc 16
b−íc 12
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)
π(3) = (3,0)
π(6) = (1,0)
π(9) = (4,0)
π(12) =(2,0)
π(1) = (1,1)
π(4) = (4,1)
π(7) = (2,1)
π(10) =(0,1)
π(13) =(3,1)
π(2) = (2,2)
π(5) = (0,2)
π(8) = (3,2)
π(11) =(1,2)
π(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
i i
i=1 i
M
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
≡ a
i
(mod
i
y
i
(mod
m
j
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
trong ®ã Mi = M/mi vµ yi =
i =1
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
23 mod 13 =8
26 mod 13 =12
29 mod 13 =5
21 mod 13 =2
24 mod 13 =3
27 mod 13 =11
210 mod 13 =10
22 mod 13 =4
25 mod 13 =6
28 mod 13 =9
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.
2.
3.
4.
z=1
for i = l-1 down to 0 do
z = z2 mod n
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
9
0
97262 × 9726 = 2659
26592 = 5634
8
1
56342 × 9726 = 9167
7
1
91672 × 9726 = 4958
6
1
5
0
4
0
49582 × 9726 = 7783
77832 = 6298
62982 = 4629
3
1
46292 × 9726 = 10185
2
1
1
0
101852 × 9726 = 105
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 ®U 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,
2
(±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
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× ap1
≡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.
Gi¶ sö p lµ mét sè nguyªn tè. Khi ®ã
a
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
- Xem thêm -