Giáo trình Số học thuật toán - Chương 6: Vài ứng dụng vào lý thuyết mật mã

cÆp c¸ thÓ hoÆc tõng nhãm nhá c¸ thÓ vÉn cã kh¶ 
n¨ng sö dông kho¸ mËt m· ®ang dïng ®Ó t¹o nh÷ng kho¸ mËt m· chung, bÝ mËt ®èi 
víi c¸c c¸ thÓ cßn l¹i cña hÖ thèng. 
Gi¶ sö p lµ mét sè nguyªn tè lín vµ a lµ mét sè nguyªn, nguyªn tè cïng nhau víi p. 
Mçi c¸ thÓ trong hÖ thèng chän mét sè k nguyªn tè cïng nhau víi p-1 lµm kho¸ cho 
m×nh. Khi hai c¸ thÓ víi c¸c kho¸ k1, k2 muèn lËp mét kho¸ chung ®Ó trao ®æi th«ng 
tin, c¸ thÓ thø nhÊt göi cho c¸ thÓ thø hai sè nguyªn y1 tÝnh theo c«ng thøc: 
y a p y pk1 11 0≡ < <(mod ), 
C¸ thÓ thø hai sÏ t×m ra kho¸ chung k b»ng c¸ch tÝnh 
 k y1≡ ≡ < <k k ka p k p2 1 2 0(mod ), 
T−¬ng tù c¸ thÓ thø hai göi cho c¸ thÓ thø nhÊt sè nguyªn y2 
y a p y pk2 22 0≡ < <(mod ), 
vµ c¸ thÓ thø nhÊt t×m ra kho¸ chung k theo c«ng thøc 
 k y2≡ ≡k k ka p2 1 2 (mod ) 
 105
Ta l−u ý r»ng, trong c¸ch lËp kho¸ chung trªn ®©y, c¸c c¸ thÓ thø nhÊt vµ thø hai 
kh«ng cÇn biÕt kho¸ mËt m· cña nhau, mµ chØ sö dông kho¸ mËt riªng cña m×nh. 
MÆt kh¸c, c¸c c¸ thÓ cßn l¹i cña mét hÖ thèng còng kh«ng thÓ t×m ra kho¸ chung k 
®ã trong mét thêi gian chÊp nhËn ®−îc, v× ®Ó lµm viÖc ®ã, hä ph¶i tÝnh logarit 
modulo p. 
Trªn ®©y lµ c¸ch lËp kho¸ chung cña hai c¸ thÓ. Hoµn toµn t−¬ng tù nh− vËy, tõng 
nhãm c¸c thÓ cã thÓ lËp kho¸ chung. 
§4. C¸c hÖ mËt m· kho¸ c«ng khai. 
Trong tÊt c¶ c¸c hÖ mËt m· tr×nh bµy trªn ®©y, c¸c kho¸ lËp m· ®Òu ph¶i ®−îc gi÷ bÝ 
mËt, v× nÕu kho¸ lËp m· bÞ lé th× ng−êi ta cã thÓ t×m ra kho¸ gi¶i m· trong mét thêi 
gian t−¬ng ®èi ng¾n. Nh− vËy nÕu trong mét hÖ thèng cã nhiÒu cÆp c¸ thÓ hoÆc nhiÒu 
nhãm c¸ thÓ cÇn trao ®æi th«ng tin mËt víi nhau, sè kho¸ mËt m· chung cÇn gi÷ bÝ 
mËt lµ rÊt lín, vµ nh− vËy, khã cã thÓ b¶o ®¶m ®−îc. HÖ m· mµ chóng ta nghiªn cøu 
d−íi ®©y ®−îc lËp theo mét nguyªn t¾c hoµn toµn míi, trong ®ã viÖc biÕt kho¸ lËp 
m· kh«ng cho phÐp t×m ra kho¸ gi¶i m· trong mét thêi gian chÊp nhËn ®−îc. V× thÕ, 
mçi c¸ thÓ chØ cÇn gi÷ bÝ mËt kho¸ gi¶i m· cña riªng m×nh, trong khi kho¸ lËp m· 
®−îc th«ng b¸o c«ng khai. Trong tr−êng hîp mét trong c¸c c¸ thÓ bÞ lé kho¸ gi¶i m· 
cña m×nh, bÝ mËt cña c¸c c¸ thÓ cßn l¹i kh«ng hÒ bÞ ¶nh h−ëng. LÝ do cña viÖc cã thÓ 
x©y dùng nh÷ng hÖ m· nh− vËy chÝnh lµ ®iÒu ta ®· nãi ®Õn khi xÐt c¸c hÖ m· mò: ®é 
phøc t¹p cña thuËt to¸n t×m logarit modulo p lµ qu¸ lín. 
Tr−íc hÕt, ta nãi s¬ qua vÒ nguyªn t¾c cña c¸c hÖ m· kho¸ c«ng khai. Gi¶ sö trong 
hÖ thèng ®ang xÐt cã n c¸ thÓ cïng trao ®æi c¸c th«ng tin mËt. Mçi c¸c thÓ chän cho 
m×nh mét kho¸ lËp m· k vµ mét c«ng thøc m· ho¸ E(k), ®−îc th«ng b¸o c«ng khai. 
Nh− vËy cã n kho¸ lËp m· c«ng khai k1, k2,...,kn. Khi c¸ thÓ thø i muèn göi th«ng b¸o 
cho c¸ thÓ thø j, còng nh− tr−íc ®©y, mçi ch÷ trong th«ng b¸o ®−îc chuyÓn thµnh sè, 
nhãm thµnh tõng khèi víi ®é dµi nµo ®ã. Sau ®ã, mçi khèi P trong v¨n b¶n ®−îc m· 
ho¸ b»ng kho¸ lËp m· E(kj) cña c¸ thÓ thø j (®· th«ng b¸o c«ng khai), vµ göi ®i d−íi 
d¹ng C=E(kj)(P). §Ó gi¶i m· th«ng b¸o nµy, c¸ thÓ thø j chØ cÇn dïng kho¸ gi¶i m· 
(bÝ mËt riªng cho m×nh) Dk j 
Dk j (C)= Dk j E P Pk j ( ) = , 
bëi v× Dk j vµ Ek j lµ c¸c kho¸ gi¶i m· vµ lËp m· cña cïng c¸ thÓ thø j. C¸c c¸ thÓ 
trong hÖ thèng, nÕu nhËn ®−îc v¨n b¶n mËt, còng kh«ng thÓ nµo gi¶i m·, v× viÖc biÕt 
kho¸ lËp m· Ek j kh«ng cho phÐp t×m ra kho¸ gi¶i m· Dk j . 
§Ó cô thÓ ho¸ nguyªn t¾c võa tr×nh bµy, ta xÐt vÝ dô trªn hÖ m· kho¸ c«ng khai ®−îc 
t×m thÊy ®Çu tiªn n¨m 1978 bëi Rivest, Shamir vµ Adleman (xem[ RSA]) (th−êng 
®−îc gäi lµ hÖ m· RSA). 
HÖ RSA ®−îc x©y dùng trªn c¬ së m· mò, trong ®ã kho¸ lµ cÆp (e,n), gåm sè mò e 
vµ modun n. Sè n ®−îc dïng ë ®©y lµ tÝch cña hai sè nguyªn tè rÊt lín nµo ®ã, n=pq, 
 106
sao cho (e,φ (n))=1, trong ®ã φ (n) lµ hµm Euler. §Ó m· ho¸ mét th«ng b¸o, tr−íc 
tiªn ta chuyÓn c¸c ch÷ c¸i thµnh c¸c sè t−¬ng øng vµ nhãm thµnh c¸c khèi víi ®é dµi 
lín nhÊt cã thÓ (tuú thuéc kh¶ n¨ng tÝnh to¸n) víi mét sè ch½n ch÷ sè. §Ó m· ho¸ 
mét khèi P trong v¨n b¶n, ta lËp khèi C trong v¨n b¶n mËt b»ng c«ng thøc: 
E(P) ≡ C≡ Pe(mod n), 0<C<n. 
Qu¸ tr×nh gi¶i m· ®ßi hái ph¶i biÕt ®−îc mét nghÞch ®¶o d cña e modulo φ (n). 
NghÞch ®¶o nµy tån t¹i theo ®iÒu kiÖn (e, φ (n) )=1. 
Muèn gi¶i m· mét khèi C trong v¨n b¶n mËt, ta tÝnh 
D(C) ≡ Cd≡ (Pe)d≡ Ped≡ P k nφ( ) +1 ≡ ( )( )P Pn kφ ≡ P(mod n). 
trong ®ã ed=kφ (n)+1 ®èi víi sè nguyªn k nµo ®ã, v× ed≡ 1(mod φ (n)), vµ do ®Þnh lÝ 
Euler ta cã: P pnφ ( ) (mod )≡ 1 , khi (P,n)=1 (chó ý r»ng, x¸c suÊt ®Ó P vµ n kh«ng 
nguyªn tè cïng nhau lµ hÕt søc nhá, xem bµi tËp 6.7). CÆp (d,n) nh− vËy ®−îc gäi lµ 
kho¸ gi¶i m·. 
§Ó minh ho¹, ta xÐt mét vÝ dô ®¬n gi¶n, lÊy n=53.61=3233 vµ e=17. Trong tr−êng 
hîp ®ã ta cã (e, φ (n))=(17,52.63)=1. Gi¶ sö ta cÇn m· ho¸ th«ng b¸o sau: 
§A G¦I TI£N 
Tr−íc tiªn ta chuyÓn c¸c ch÷ c¸i trong v¨n b¶n thµnh c¸c sè t−¬ng øng vµ nhãm 
chóng thµnh tõng khèi 4 ch÷ sè. Ta cã: 
0701 1026 1224 1209 1628 
Ta m· ho¸ c¸c khèi nhê c«ng thøc 
C≡ P17(mod 3233) 
Ta l¹i dïng ph−¬ng ph¸p b×nh ph−¬ng liªn tiÕp. Ch¼ng h¹n, ®èi víi khèi ®Çu tiªn, ta 
nhËn ®−îc: 
(701)17 ≡ 140(mod 3233) 
M· ho¸ toµn bé v¨n b¶n, ta ®−îc v¨n b¶n mËt sau ®©y: 
140 721 1814 1819 361 
Khi nhËn ®−îc v¨n b¶n mËt nµy, ®Ó gi¶i m·, ta ph¶i t×m mét nghÞch ®¶o d cña e 
modulo φ (3233). Ta cã φ (53.61)=52.60=3120. Dïng thuËt to¸n Euclid më réng, ta 
tÝnh ®−îc d=2753. Nh− vËy, ®Ó gi¶i m· khèi C ta dïng c«ng thøc 
P≡ C2753(mod 3233), 0≤P ≤3233 
Cã thÓ thö l¹i: 
C2753≡ (P17)2753≡ P(P3120)15≡ P(mod 3233) 
ë ®©y ta dïng ®Þnh lÝ Euler ®Ó nhËn ®−îc Pφ ( )3253 ≡ P3120≡ 1(mod 3233), khi 
(P,3233)=1 (®iÒu nµy ®óng víi mäi khèi trong th«ng b¸o cña chóng ta) 
 107
B©y giê ta chØ ra r»ng, hÖ m· RSA tho¶ m·n c¸c nguyªn t¾c cña hÖ m· kho¸ c«ng 
khai nãi ë ®Çu tiÕt nµy. Tr−íc tiªn, ta chó ý r»ng, mçi c¸ thÓ ph¶i chän hai sè nguyªn 
tè lín p vµ q, cì chõng 100 ch÷ sè thËp ph©n. §iÒu nµy cã thÓ lµ trong Ýt phót nhê 
mét m¸y tÝnh. Khi c¸c sè nguyªn tè p vµ q ®· ®−îc chän, sè mò dïng ®Ó m· ho¸ e sÏ 
®−îc lÊy sao cho (e, φ (qp))=1. Nãi chung nªn chän e lµ sè nguyªn tè tuú ý lín h¬n 
q vµ p. Sè e ®−îc chän nhÊt thiÕt ph¶i tho¶ m·n 2e>n=pq. NÕu ®iÒu kiÖn nµy kh«ng 
®−îc tho¶ m·n, ta cã C=Pe<n, vµ nh− vËy ®Ó t×m ra P, ta chØ viÖc tÝnh c¨n bËc e cña 
C. Khi ®iÒu kiÖn 2e>n ®−îc tho¶ m·n, mäi khèi P kh¸c 0 vµ 1 ®Òu ®−îc m· ho¸ b»ng 
c¸ch n©ng lªn luü thõa vµ lÊy ®ång d− theo modulo n. 
Ta cÇn ph¶i chøng tá r»ng, viÖc biÕt kho¸ lËp m· (c«ng khai) (e,n) kh«ng ®Én ®Õn 
viÖc t×m ®−îc kho¸ gi¶i m· (d,n). 
Chó ý r»ng, ®Ó t×m nghÞch ®¶o d cña e modulo φ (n), tr−íc tiªn ph¶i t×m ®−îc φ (n). 
ViÖc t×m φ (n) kh«ng dÔ h¬n so víi ph©n tÝch n, bëi v×, mét khi biÕt φ (n) vµ n, ta sÏ 
ph©n tÝch ®−îc n=pq. 
ThËt vËy, ta cã: 
p+q=n-φ (n)+1 
p-q= ( ) ( )p q qp p q n+ − = + −2 24 4 
Tõ c¸c c«ng thøc ®ã t×m ®−îc q vµ p. 
NÕu ta chän c¸c sè p vµ q kho¶ng 100 ch÷ sè thËp ph©n, th× n sÏ cã kho¶ng 200 ch÷ 
sè thËp ph©n. §Ó ph©n tÝch mét sè nguyªn cì lín nh− thÕ, víi c¸c thuËt to¸n nhanh 
nhÊt hiÖn nay vµ víi nh÷ng m¸y tÝnh hiÖn ®¹i nhÊt, ta mÊt kho¶ng 3,8 tû n¨m! 
Cã mét vµi ®iÒu cÇn l−u ý khi chän c¸c sè p vµ q ®Ó tr¸nh r¬i vµo tr−êng hîp tÝch pq 
bÞ ph©n tÝch nhanh nhê nh÷ng thuËt to¸n ®Æc biÖt: q vµ p cÇn chän sao cho p-1 vµ q-1 
chØ cã c¸c thõa sè nguyªn tè lín, (p-1,q-1) ph¶i nhá, q vµ p ph¶i cã sè ch÷ sè trong 
khai triÓn thËp ph©n kh¸c nhau kh«ng nhiÒu. 
Cã thÓ n¶y ra c©u hái: trong mét hÖ thèng nhiÒu c¸ thÓ tham gia, c¸c kho¸ lËp m· ®· 
l¹i ®−îc c«ng khai, lµm sao cã thÓ tr¸nh ®−îc tr−êng hîp mét c¸ thÓ nµy “m¹o danh” 
mét c¸ thÓ kh¸c ®Ó göi th«ng b¸o cho mét c¸ thÓ thø ba? Nãi c¸ch kh¸c lµm sao cã 
thÓ “kÝ tªn” d−íi c¸c th«ng b¸o mËt? VÊn ®Ò nµy ®−îc gi¶i quyÕt ®¬n gi¶n nh− sau: 
Gi¶ sö “«ng I” cÇn kÝ tªn d−íi th«ng b¸o göi “«ng J”. Khi ®ã, tr−íc tiªn, «ng I tÝnh 
S≡ Dki (I) ≡ Idi (mod ni). 
Chó ý r»ng chØ cã «ng I lµm ®−îc viÖc nµy, v× trong c«ng thøc sö dông kho¸ gi¶i m· 
cña «ng I. Sau ®ã, I sÏ göi cho J th«ng b¸o 
C≡ E S S nk e jj j( ) (mod )= , 
trong ®ã (ej,nj) lµ kho¸ lËp m· cña J. 
Khi nhËn ®−îc, ®Ó gi¶ m·, J tr−íc tiªn dïng kho¸ gi¶i m· riªng cña m×nh ®Ó nhËn ra 
S: 
 108
D Ck j ( ) ≡ D E Sk kj j( ( )) ≡ S 
§Ó x¸c minh S ®Ých thùc lµ ch÷ kÝ cña I, J chØ cßn viÖc ¸p dông vµo S kho¸ lËp m· 
c«ng khai cña I: 
E S E D I Ik k ki i i( ) ( )≡ ≡ 
Chó ý c¸ch lµ nh− trªn thÝch hîp khi nj>ni, v× khi ®ã ta lu«n cã S<nj. NÕu ng−îc l¹i, I 
ph¶i t¸ch S thµnh tõng khèi cã ®é dµi bÐ h¬n nj vµ m· ho¸ tõng khèi råi míi chuyÓn. 
Nh− vËy, mét mÆt J x¸c ®Þnh ®−îc ®ã ®óng lµ th«ng b¸o do I göi ®Õn, mÆt kh¸c I 
còng kh«ng thÓ tõ chèi viÖc m×nh lµ chñ nh©n cña th«ng b¸o ®ã, v× ngoµi I ra, kh«ng 
ai cã kho¸ m· Dki ®Ó m¹o “ch÷ kÝ” cña I. 
Trªn ®©y lµ hÖ mËt m· kho¸ c«ng khai xuÊt hiÖn ®Çu tiªn. Tõ ®ã ®Õn nay, cã nhiÒu 
hÖ mËt m· kho¸ c«ng khai míi ra ®êi. Tuy vËy, nguyªn t¾c chung cña cac hÖ m· ®ã 
lµ sö dông nh÷ng “thuËt to¸n mét chiÒu”, tøc lµ nh÷ng thuËt to¸n cho phÐp t×m ra 
mét ®¹i l−îng nµo dã t−¬ng ®èi nhanh, nh−ng viÖc t×m “nghÞch ®¶o” (theo mét nghÜa 
nµo ®ã) cña nã ®ßi hái thêi gian qu¸ lín. §éc gi¶ nµo quan t©m ®Õn vÊn ®Ò nµy cã 
thÓ t×m ®äc trong nh÷ng tµi liÖu chuyªn vÒ lÝ thuyÕt mËt m·. Trong ch−¬ng tiÕp theo, 
ta sÏ quay vÒ víi lÝ thuyÕt mËt m· kho¸ c«ng khai khi nghiªn cøu c¸c ®−êng cong 
elliptic. 
Cïng víi sù ph¸t triÓn cña mËt m· kho¸ c«ng khai, cã lÏ sÏ ®Õn lóc bªn c¹nh ®Þa chØ 
vµ ®iÖn tho¹i cña mçi c¬ quan, c«ng ty, cßn ghi thªm kho¸ lËp m· cña hä! 
 109
Bµi tËp vµ tÝnh to¸n thùc hµnh ch−¬ng 6. 
I. Bµi tËp 
6.1. BiÕt r»ng th«ng b¸o sau ®©y ®· ®−îc m· ho¸ b»ng m· Ceasar (víi kho¸ k nµo ®ã 
trong kho¶ng 1-29), h·y t×m kho¸ vµ gi¶i m·: 
S¤EMR IEIEH USSOT SLU¥I EI¤HE ITSA¢ U¥IEI ¤LU¥I ES¤YB SOS¤E 
MRDEI EI¤X¢ EI¤BS ORMCE SXS¤L GDES¤ MBSO¡ ¤MTMR 
6.2. Dïng m· khèi ®Ó m· ho¸ c©u 
CO C¤NG MAI S¡T CO NGAY N£N KIM 
víi kho¸ ma trËn lµ 
24 22
11 10



 
6.3. Gi¶i m· c©u sau ®©y, biÕt r»ng nã ®−îc m· ho¸ b»ng khèi víi ma trËn 
8 4
17 11



 
OD O¢ XC ¥¥ EP Y¥ NR EY 
6.4. Cã thÓ lËp m· khèi theo c¸ch