Vietebooks Nguyễn Hoàng Cương
Trang 1
ch−¬ng 8
ph©n phèi vµ tho¶ thuËn vÒ kho¸
8.1 Giíi thiÖu:
Chóng ta ®· thÊy r»ng, hÖ thèng m· kho¸ c«ng khai cã −u ®iÓm h¬n hÖ
thèng m· kho¸ riªng ë chç kh«ng cÇn cã kªnh an toµn ®Ó trao ®æi kho¸ mËt. Tuy
nhiªn, ®¸ng tiÕc lµ hÇu hÕt c¸c hÖ thèng m· kho¸ c«ng khai ®Òu chËm h¬n hÖ m·
kho¸ riªng, ch¼ng h¹n nh− DES. V× thÕ thùc tÕ c¸c hÖ m· kho¸ riªng th−êng ®−îc
dïng ®Ó m· c¸c bøc ®iÖn dµi. Nh−ng khi ®ã chóng ta l¹i trë vÒ vÊn ®Ò trao ®æi
kho¸ mËt.
Trong ch−¬ng nµy, chóng ta sÏ th¶o luËn vµi biÖn ph¸p thiÕt lËp c¸c kho¸
mËt. Ta ph©n biÖt gi÷a ph©n phèi kho¸ vµ tho¶ thuËn vÓ kho¸. Ph©n phèi kho¸
®−îc ®Þnh nghÜa lµ c¬ chÕ mét nhãm chän kho¸ mËt vµ sau ®ã truyÒn nã ®Õn c¸c
nhãm kh¸c. Cßn tho¶ thuËn kho¸ lµ giao thøc ®Ó hai nhãm (hoÆc nhiÒu h¬n) liªn
kÕt víi nhau cïng thiÕt lËp mét kho¸ mËt b»ng c¸ch liªn l¹c trªn kªnh c«ng khai.
Trong s¬ ®å tho¶ thuËn kho¸, gi¸ trÞ kho¸ ®−îc x¸c ®Þnh nh− hµm cña c¸c ®Çu
vµo do c¶ hai nhãm cung cÊp.
Gi¶ sö, ta cã mét m¹ng kh«ng an toµn gåm n ng−êi sö dông. Trong mét sè
s¬ ®å, ta cã ng−êi uû quyÒn ®−îc tÝn nhiÖm (TA) ®Ó ®¸p øng nh÷ng viÖc nh− x¸c
minh danh tÝnh cña ng−êi sö dông, chän vµ göi kho¸ ®Õn ng−êi sö dông ... Do
m¹ng kh«ng an toµn nªn cÇn ®−îc b¶o vÖ tr−íc c¸c ®èi ph−¬ng. §èi ph−¬ng
(Oscar) cã thÓ lµ ng−êi bÞ ®éng, cã nghÜa lµ hµnh ®éng cña anh ta chØ h¹n chÕ ë
møc nghe trém bøc ®iÖn truyÒn trªn kªnh. Song mÆt kh¸c, anh ta cã thÓ lµ ng−êi
chñ ®éng. Mét ®èi ph−¬ng chñ ®éng cã thÓ lµm nhiÒu hµnh vi xÊu ch¼ng h¹n:
1. Thay ®æi bøc ®iÖn mµ anh ta nhËn thÊy lµ ®ang ®−îc truyÒn trªn m¹ng.
2. CÊt bøc ®iÖn ®Ó dïng l¹i sau nµy.
3. Cè g¾ng gi¶ d¹ng lµm nh÷ng ng−êi sö dông kh¸c nhau trªn m¹ng.
Môc tiªu cña ®èi ph−¬ng chñ ®éng cã thÓ lµ mét trong nh÷ng c¸i nªu sau ®©y:
1. Lõa U vµ V chÊp nhËn kho¸ “kh«ng hîp lª” nh− kho¸ hîp lÖ (kho¸ kh«ng hîp
lÖ cã thÓ lµ kho¸ cò ®· hÕt h¹n sö dông, hoÆc kho¸ do ®èi ph−¬ng chän).
2. Lµm U hoÆc V tin r»ng, hä cã thÓ trao ®æi kho¸ víi ng−êi kia khi hä kh«ng cã
kho¸.
Môc tiªu cña ph©n phèi kho¸ vµ giao thøc tho¶ thuËn kho¸ lµ, t¹i thêi ®iÓm
kÕt thóc thñ tôc, hai nhãm ®Òu cã cïng kho¸ K song kh«ng nhãm kh¸c nµo biÕt
®−îc (trõ kh¶ n¨ng TA). Ch¾c ch¾n, viÖc thiÕt kÕ giao thøc cã kiÓu an toµn nµy
khã kh¨n h¬n nhiÒu tr−íc ®èi ph−¬ng chñ ®éng.
Tr−íc hÕt ta xem xÐt ý t−ëng vÒ sù ph©n phèi kho¸ tr−íc trong môc 8.2. Víi
mçi cÆp ng−êi sö dông {U,V}, TA chän mét kho¸ ngÉu nhiªn KU,V=KV,U vµ
truyÒn “ngoµi d¶i” ®Õn U vµ V trªn kªnh an toµn. (NghÜa lµ, viÖc truyÒn kho¸
kh«ng x¶y ra trªn m¹ng do m¹ng kh«ng an toµn ). BiÖn ph¸p nµy gäi lµ an toµn
kh«ng ®iÒu kiÖn song nã ®ßi hái mét kªnh an toµn gi÷a TA vµ nh÷ng ng−êi sö
Vietebooks Nguyễn Hoàng Cương
Trang 2
dông trªn m¹ng. Tuy nhiªn ®iÒu quan träng h¬n lµ mçi ng−êi ph¶i l−u n -1 kho¸
vµ TA cÇn truyÒn tæng céng
(
)
n
2kho¸ mét c¸ch an toµn (®«i khi bµi to¸n nµy ®−îc
gäi lµ bµi to¸n n2). ThËm chÝ víi mét sè m¹ng t−¬ng ®èi nhá, gi¸ ®Ó gi¶i quyÕt
vÊn ®Ò nµy lµ kh¸ ®¾t vµ nh− vËy gi¶i ph¸p hoµn toµn kh«ng thùc tÕ.
Trong phÇn 8.2.1, chóng ta th¶o luËn mét s¬ ®å ph©n phèi tr−íc kho¸ an
toµn kh«ng ®iÒu kiÖn kh¸ thó vÞ do Blom ®−a ra. S¬ ®å cho phÐp gi¶m l−îng
th«ng tin mËt mµ ng−êi sö dông cÇn cÊt gi÷ trªn m¹ng. Môc 8.2.2 còng ®−a ra
mét s¬ ®å ph©n phèi tr−íc kho¸ an toµn vÒ mÆt tÝnh to¸n dùa trªn bµi to¸n
logarithm rêi r¹c.
Mét biÖn ph¸p thùc tÕ h¬n lµ TA ph©n phèi kho¸ trùc tiÕp. Trong s¬ ®ß nh−
vËy, TA lµm viÖc nh− mét ng−êi chñ kho¸ (key server). TA chia kho¸ mËt KU
cho mçi ng−êi sö dông U trªn m¹ng. Khi U muèn liªn l¹c víi V, c« ta yªu cÇu
TA cung cÊp kho¸ cho phiªn lµm viÖc (session key). TA t¹o ra kho¸ session K vµ
göi nã d−íi d¹ng m· ho¸ cho U vµ V ®Ó gi¶i m·. HÖ thèng m· Kerboros m« t¶
trong môc 8.3 lµ dùa trªn biÖn ph¸p nµy.
NÕu nh− c¶m thÊy vÊn ®Ò ph©n phèi kho¸ th«ng qua TA kh«ng thùc tÕ
hoÆc kh«ng mong muèn th× biÖn ph¸p chung lµ dïng giao thøc tho¶ thuËn kho¸.
Trong giao thøc tho¶ thuËn kho¸, U vµ V kÕt hîp chän mét kho¸ b»ng c¸ch liªn
l¹c víi nhau trªn kªnh c«ng khai. ý t−ëng ®¸ng chó ý nµy do Martin vµ Diffie ®−a
ra ®éc lËp víi Merkle. ë ®©y m« t¶ vµi giao th−c tho¶ thuËn kho¸ phæ th«ng h¬n.
Giao thøc ®Çu tiªn cña Diffie vµ Hellman ®−îc c¶i tiÕn ®Ó øng phã víi c¸c ®èi
ph−¬ng tÝch cùc ®−îc nªu trong phÇn 8.4.1. Hai giao thøc ®¸ng quan t©m n÷a
còng ®−îc xem xÐt: s¬ ®å MTI nªn trong 8.4.2 vµ s¬ ®å Girault nªu trong môc
8.4.3
8.2 Ph©n phèi kho¸ tr−íc
theo ph−¬ng ph¸p c¬ b¶n, TA t¹o ra ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
n kho¸ vµ ®−a mçi khoa cho duy
nhÊt mét cÆp ng−êi sö dông trong m¹ng cã n ng−êi sö dông. Nh− ®· nªu ë trªn,
ta cÇn mét kªnh an toµn gi÷a TA vµ mçi ng−êi sö dông ®Ó truyÒn ®i c¸c kho¸
nµy. §©y lµ mét c¶i tiÕn quan träng v× sè kªnh an toµn cÇn thiÕt gi¶m tõ ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
2
n
xuèng cßn n. Song nÕu n lín, gi¶i ph¸p nµy còng kh«ng thùc tÕ c¶ vÒ l−îng th«ng
tin cÇn truyÒn ®i an toµn lÉn l−îng th«ng tin mµ mçi ng−êi sö dông ph¶i cÊt gi÷
an toµn (nghÜa lµ c¸c kho¸ mËt cña n-1 ng−êi sö dông kh¸c).
nh− vËy, ®iÒu cÇn quan t©m lµ cè g¾ng gi¶m ®−îc l−îng th«ng tin cÇn truyÒn ®i
vµ cÊt gi÷ trong khi vÉn cho phÐp mçi cÆp ng−êi sö dông U vµ V cã kh¶ n¨ng tÝnh
to¸n kho¸ mËt KU,V. Mét s¬ ®å −u viÖt h¬n tho¶ m·n yªu cÇu nµy lµ s¬ ®å ph©n
phèi kho¸ tr−íc cña Blom.
8.2.1 S¬ ®å Blom.
Vietebooks Nguyễn Hoàng Cương
Trang 3
Nh− trªn, gi¶ thiÕt r»ng cã mét m¹ng g«m n ng−êi sö dông. §Ó thuËn tiÖn,
gi¶ sö r»ng c¸c kho¸ ®−îc chän trªn tr−êng sè h÷u h¹n ZP, p ≥ n lµ sè nguyªn tè.
Cho k lµ sè nguyªn, 1 < k < n -2. Gi¸ trÞ k ®Ó h¹n chÕ kÝch th−íc lín nhÊt mµ s¬
®å vÉn duy tr× ®−îc mËt ®é. Trong s¬ ®å Blom, TA sÏ truyÒn ®i k +1 phÇn tö cña
ZP cho mçi ng−êi sö dông trªn kªnh an toµn (so víi n -1 trong s¬ ®å ph©n phèi
tr−íc c¬ b¶n). Mçi cÆp ng−êi sö dông U vµ V sÏ cã kh¶ n¨ng tÝnh kho¸ KU,V =
KV,U nh− tr−íc ®©y. §iÒu kiÖn an toµn nh− sau: tËp bÊt k× gåm nhiÒu nhÊt k ng−êi
sö dông kh«ng liªn kÕt tõ {U, V} ph¶i kh«ng cã kh¶ n¨ng x¸c ®Þnh bÊt k× th«ng
tin nµo vÒ KU,V. (chó ý r»ng, ta ®ang xÐt sù an toµn kh«ng ®iÒu kiÖn).
Tr−íc hÕt, xÐt tr−êng hîp ®Æc biÖt cña s¬ ®å Blom khi k =1. ë ®©y TA sÏ
truyÒn ®i 2 phÇn tö cña ZP cho mçi ng−êi sö dông trªn kªnh an toµn vµ ng−êi sö
dông riªng W sÏ kh«ng thÓ x¸c ®Þnh ®−îc bÊt k× th«ng tin nµo vÒ KU,V nÕu
W≠U,V. S¬ ®å Blom ®−îc ®−a ra trong h×nh 8.1. Ta sÏ minh ho¹ s¬ ®å Blom víi
k = 1 trong vÝ dô sau:
H×nh 8.1: S¬ ®å ph©n phèi kho¸ cña Blom (k =1)
1. Sè nguyªn tè p c«ng khai, cßn víi mçi ng−êi sö dông U, phÇn tö rU ∈ ZP lµ
c«ng khai. PhÇn tö rU ph¶i kh¸c biÖt.
2. Ta chän 3 phÇn tö ngÉu nhiªn a, b, c ∈ ZP (kh«ng cÇn kh¸c biÖt) vµ thiÕt lËp
®a thøc
Vietebooks Nguyễn Hoàng Cương
Trang 4
8.3.Kerboros
trong c¸c ph−¬ng ph¸p ph©n phèi tr−íc kho¸ xem xÐt trong c¸c phÇn tr−íc
®ã, mçi cÆp ng−êi sö dông cÇn tÝnh mét kho¸ cè ®Þnh. NÕu dïng cïng mét kho¸
trong mét thêi gian dµi sÏ dÔ bÞ tæn th−¬ng, v× thÕ ng−êi ta th−êng thÝch dïng
ph−¬ng ph¸p trùc tiÕp trong ®ã kho¸ cña phiªn lamµ viÖc míi chØ ®−îc t¹o ra mçi
khi hai ng−íi sö dông muèn liªn l¹c víi nhau (gäi lµ tÝnh t−¬i míi cña kho¸).
NÕu dïng ph©n phèi kho¸ trùc tiÕp th× ng−êi sö dông m¹ng kh«ng cÇn ph¶i
l−u c¸c kho¸ khi muèn liªn l¹c víi nh÷ng ng−êi sö dông kh¸c (Tuy nhiªn mçi
ng−êi ®Òu ®−îc chia sÎ kho¸ víi TA). Kho¸ cña phiªn lµm viÖc (khãa session) sÏ
®−îc truyÒn ®i theo yªu cÇu cña TA. §ã lµ sù ®¸p øng cña TA ®Ó ®¶m b¶o kho¸
t−¬i.
Korobos lµ hÖ thèng dÞch vô khãa phæ cËp dùa trªn m· kho¸ riªng. Trong
phÇn nµy sÏ ®−a ra mét tæng quan vÒ giao thøc ph¸t hµnh kho¸ session trong
Korobos. Mçi ng−êi sö dông U sÏ chia sÎ kho¸ DES mËt KU cho TA. Trong phiªn
b¶n gÇn ®©y nhÊt cña Korobos (version 5), mäi th«ng b¸o cÇn truyÒn ®−îc m·
ho¸ theo chÕ ®é xÝch khèi (CBC) nh− m« t¶ trong 3.4.1
Nh− trong môc 8.2.2, ID(U) chØ th«ng tin ®Þnh danh c«ng khai cho U. Khi
cã yªu cÇu kho¸ session göi ®Õn TA, TA sÏ t¹o ra mét kho¸ session míi ngÉu
nhiªn K. Còng vËy, TA sÏ ghi l¹i thêi gian khi cã yªu cÇu T vµ chØ ra thêi gian
(thêi gian tån t¹i) L ®Ó K cã hiÖu lùc. §iÒu ®ã cã nghÜa lµ kho¸ K chØ cã hiÖu lùc
tõ T ®Õn T+L. TÊt c¶ th«ng tin nµy ®Òu ®−îc m· ho¸ vµ ®−îc truyªn«ng d©n ®Õn
U vµ V. Tr−íc khi ®i ®Õn c¸c chi tiÕt h¬n n÷a, ta sÏ ®−a ra giao thøc trong h×nh
8.4. th«ng tin ®−îc truyÒn ®i trong giao thøc ®−îc minh ho¹ nh− sau:
H×nh 8.4: TruyÒn kho¸ session trong Korobos.
1.
Ta sÏ gi¶i thÝch ®iÒu s¾p söa x¶y ra trong c¸c b−íc cña giao thøc. MÆc dï
kh«ng cã chøng minh h×nh thøc r»ng Kerobos lµ an toµn tr−íc ®èi thñ tÝch cùc,
song Ýt nhÊt ta còng cã thÓ ®−a ra lÝ do nµo ®ã vÒ c¸c ®Æc ®iÓm cña giao thøc.
Nh− nªu ë trªn, TA t¹o ra K, T vµ L trong b−íc 2. Trong b−íc 3, th«ng tin
nµy cïng víi ID(V) ®−îc m· ho¸ b»ng kho¸ KU (®−îc U vµ TA chia sÎ) ®Ó t¹o
lËp m1. C¶ hai bøc ®iÖn ®· m· ho¸ nµy ®−îc göi ®Õn U.
U cã thÓ dïng kho¸ cña m×nh gi¶i m· m1, nhËn ®−îc K, T vµ L. C« sÏ x¸c
minh xem thêi gian hiÖn t¹i cã n»m trong kho¶ng T ®Õn T + L hay kh«ng. C«
còng kiÓm tra kho¸ session K ®−îc ph¸t ra cho liªn l¹c gi÷a c« vµ V b»ng c¸ch
x¸c minh th«ng tin ID(V) ®· gi¶i m· tõ m2.
TiÕp theo, U sÏ lµm trÔ thêi gian m2 vµ m3 ®Õn V. Còng nh− vËy, U sÏ dïng
kho¸ session K míi ®Ó m· T vµ ID(U) vµ göi kÕt qu¶ m3 ®Õn V.
Khi V nhËn ®−îc m3 vµ m3 tõ U, V gii m· m2 thu ®−îc T, K, L vµ ID(U).
Khi ®ã, anh ta sÏ dïng kho¸ session míi K ®Ó gi¶i m· m3 vµ x¸c minh xem T vµ
Vietebooks Nguyễn Hoàng Cương
Trang 5
ID(U) nhËn ®−îc tõ m2 vµ m3 cã nh− nhau kh«ng. §iÒu nµy ®¶m b¶o cho V r»ng
kho¸ session ®−îc m· b»ng m2 còng lµ kho¸ ®· dïng ®Ó m· m3. Khi ®ã V dïng K
®Ó m· T+1 vµ göi kÕt qu¶ m4 trë vÒ U.
Khi U nhËn ®−îc m4, c« dïng K gi¶i m· nã vµ x¸c minh xem kÕt qu¶ cã
b»ng T+1 kh«ng. C«ng ®o¹n nµy ®¶m b¶o cho U r»ng kho¸ session K ®· ®−îc
truyÒn thµnh c«ng ®Õn V v× K ®· ®−îc dïng ®Ó t¹o ra m4.
§iÒu quan träng cÇn l−u ý lµ c¸c chøc n¨ng kh¸c nhau cña c¸c th«ng b¸o
dïng trong giao thøc, m1 vµ m2 dïng ®Ó b¶o ®¶m an toµn trong viÖc truyÒn kho¸
session. Cßn m3 vµ m4 dïng ®Ó kh¼ng ®Þnh kho¸, nghÜa lµ cho phÐp U vµ V cã thÓ
thuyÕt phôc nhau r»ng hä së h÷u cïng mét kho¸ session K. Trong hÇu hÕt c¸c s¬
®å ph©n phèi kho¸, sù kh¼ng ®Þnh kho¸ ®ùoc coi nh− mét ®Æc tÝnh. Th−êng th× nã
®−îc thùc hiÖn t−¬ng tù kiÓu Kerobos, U dïng K ®Ó m· ID(U) vµ T dïng ®Ó m·
trong m2. T−¬ng tù, V dïng K ®Ó m· T+1.
Môc ®Ých cña thêi gian hÖ thèng T vµ thêi h¹n L ®Ó ng¨n ®èi ph−¬ng tÝch
cùc khái “l−u” th«ng b¸o cò nh»m t¸i truyÒn l¹i sau nµy (®©y ®−îc gäi lµ tÊn
c«ng kiÓu ch¬i l¹i - relay attack). Ph−¬ng ph¸p nµy hiÖu qu¶ v× c¸c kho¸ kh«ng
®−îc chÊp nhËn lµ hîp lÖ mét khi chóng qu¸ h¹n.
Mét trong h¹n chÕ cña Kerobos lµ mäi ng−êi sö dông trong m¹ng ®Òu ph¶i
cã ®ång hå ®ång bé víi nhau v× cÇn cã thêi gian hiÖn t¹i ®Ó x¸c ®Þnh kho¸
session K cho tr−íc lµ hîp lÖ. Thùc tÕ, rÊt khã cã ®−îc sù ®ång bé hoµn h¶o nªn
ph¶i cho phÐp cã kho¶ng thay ®æi nµo ®ã vÒ thêi gian.
H×nh 8.5: Trao ®æi kho¸ Diffie - Hellman
8.4 Trao ®æi kho¸ Diffie - Hellman
NÕu ta kh«ng muèn dïng dÞch vô kho¸ trùc tiÕp th× buéc ph¶i dïng giao
thøc tho¶ thuËn kho¸ ®Ó trao ®«Ø kho¸ mËt. Tr−íc hÕt, giao thøc tho¶ thuËn kho¸
næi tiÕng nhÊt lµ giao thøc trao ®æi kho¸ Diffie - Hellman. Gi¶ sö r»ng, p lµ sè
nguyªn tè, α lµ phÇn tö nguyªn thuû cña ZP vµ chóng ®Òu lµ nh÷ng tham sè c«ng
khai. Giao thøc trao ®æi kho¸ Diffie - Hellman ®−îc ®−a ra trong môc 8.5.
Cuèi giao thøc, U vµ V tÝnh ra cïng mét kho¸:
Giao thøc nµy còng t−¬ng tù víi s¬ ®å ph©n phèi kho¸ tr−íc cña Diffie -
Hellman ®· m« t¶ tr−íc ®©y. Sù kh¸c nhau ë chç c¸c sè mò aU, aV cña U vµ V
®Òu ®−îc chän l¹i mçi lÇn thùc hiÖn giao thøc thay v× cè ®Þnh. Còng nh− vËy,
trong giao thøc nµy, c¶ U lÉn V ®Òu ®−îc ®¶m b¶o kho¸ t−¬i v× kho¸ session phô
thuéc vµo c¶ hai sè mò ngÉu nhiªn aU vµ aV.
8.4.1 Giao thøc tr¹m tíi tr¹m.
Trao ®æi kho¸ Diffie - Hellman ®−îc ®Ò xuÊt nh− s¬ ®å sau: