Vietebooks Nguyễn Hoàng Cương
Trang 1
Ch−¬ng 10
C¸C M∙ X¸C THùC
10.1 Má §ÇU
Ta ®· dµnh nhiÒu thêi gian ®Ó nghiªn cøu c¸c hÖ mËt ®−îc dïng ®Ó
®¶m b¶o ®é mËt .M· x¸c thùc sÏ cung cÊp ph−¬ng ph¸p b¶o ®¶m t×nh
toµn vÑn cña b¶n tin,mghÜa lµ b¶n tin ph¶i kh«ng bÞ can thiÖp mét c¸ch
bÊt hùp ph¸p vµ nã thùc sù ®−îc göi ®i tõ mµy ph¸t.
Môc ®Ých cña ch−¬ng nµy lµ ph¶i cã ®−îc kh¶ n¨ng x¸ thùc ngay c¶
khi cã mét ®èi ph−¬ng tÝch cùc-Oscar lµ ng−êi cã thÓ quan s¸t c¸c b¶n
tin trong kªnh.Môc ®Ých nµy cã thÓ ®¹t ®−îc b»ng c¸ch thiÕt lËp mét
‘’khoa riªng’’K b»ng c¸ch ®Ó Alice vµ Bob chungchung mét kho¸ bÝ
mËt tr−íc hki mçi b¶n tin ®−îc göi ®i.
Trong ch−¬ng nµy ta sÏ nghiªn cøu ®¶m b¶o xacs thùc chø kh«ng
ph¶i c¸c m· ®¶m b¶o ®é mËt.Trong m· nµy,kho¸ sÏ ®−îc dïng dÓ tÝnh
mét m· x¸c thùc cho phÐp Bob kiÓm tra ®−îc tÝnh x¸c thùc cña th«ng
b¸o mµ anh ta nhËn ®−îc.Mét øng dông kh¸c cña m· x¸c thùc lµ ®Ó
kiÓm tra xem c¸c sè liÖu trong mét file lín cã bÞ can thiÖp vµo mét
c¸ch hîp ph¸p hay kh«ng.Nh·n x¸c thùc sÏ ®−îc l−u cïng víi sè
liÖu:KHO¸ §¦Îc dïng ®Ó t¹o vµ kiÓm tra dÊu x¸c thùc ®−îc l−u mét
c¸ch t¸ch b¹ch trong mét’’vïng’’an toµn.
Ta còng sÏ chØ ra r»ng,vÒ nhiÒu khÝa c¹nh m· x¸c thùc còng t−¬ng tù
nh− mét s¬ ®å ch÷ kÝ hoÆc t−¬ng tù nh− mét maw x¸c thùc th«ng
b¸o(MAC).Sù kh¸c biÖt chÝnh lµ sù an toµn cña mét maw x¸c thùc lµ
kh«ng ®iÒu kiÖn biªn,trong khi ®ã c¸c s¬ ®å ch÷ kÝ vµ MAC l¹i ®−îc
nghiªn cøu theo quan ®iÓm ®é an toµn tÝnh to¸n.Còng vËy,khi mét
maw x¸c thùc (hoÆc MAC) ®−îc dïng,mét b¶n tin chØ cã thÓ ®−îc
kiÓm tra bëi ng−êi nhËn hîp ph¸p.Trong khi ®ã baats cø mçi ai còng
cã thÓ x¸c minh ®−îc ch÷ kÝ b»ng c¸ch dïng mét thuËt to¸n x¸c minh
c«ng khai.
B©y giê ta sÏ ®−a ra mét ®Þnh nghia h×nh thøc cho thuËt ng÷ ®−îc sö
dông khi nghiªn cøu c¸c m· x¸c thùc.
§Þnh nghÜa 10.1
Mét m· x¸c thùc lµ mét bé 4(S,R,K,C)tho¶ m·n c¸c ®iÒu kiÖn
sau :
1. S lµ tËp h÷u h¹n c¸c tr¹ng th¸i nguån cã thÓ
Vietebooks Nguyễn Hoàng Cương
Trang 2
2. A lµ tËp hîp c¸c nh·n x¸c thùc cã thÓ
3. K lµ mét tËp h÷u h¹n c¸c kho¸ cã thÓ (kh«ng gian kho¸)
4. Víi mçi k
∈
K cã mét quy t¾c x¸c thùc ek : S
→
R
TËp b¶n tin ®−îc x¸c ®Þnh b»ng M=S
→
R
NhËn xÐt:
Chó ý mét tr¹ng th¸i nguån t−¬ng ®−¬ng víi mét b¶n râ.Mét b¶n tin
gåm mét b¶n râ víi mét nh·n x¸c thùc kÌm theo,mét c¸ch chÝnh x¸c h¬n cã
thÓ coi ®ã lµ lµ mét b¶n tin ®· ®−îc x¸c nhËn.Mét quy t¾c x¸c thùc kh«ng
nhÊt thiÕt ph¶i lµ hµm ®¬n ¸nh.
§Îª ph¸t mét th«ng b¸o (®· ®−îc kÝ).Alice vµ Bob ph¶i tu©n theo giao thøc
sau.Tr−íc tiªn hä ph¶i chén mét kho¸ ngÉu nhiªn K∈K.§iÒu nµy ®−îc thuwc
hiÖn mét c¸ch bÝ mËt nh− trong hÖ mËt kho¸ bi mËt.Sau ®ã gi¶ sö r»ng Alice
muèn göi mét tr¹ng th¸i nguån s∈S cho Bob trong mét kªnh kh«ng an
toµn>Alice sÏ tÝnh a=ek(s) vµ göi b¶n tin (s,a)cho Bob.Khi nhËn ®−îc (s,a)
Bob tÝnh a’=eK(s).NÕu a=a’ th× Bob chÊp nhËn b¶n tin lµ x¸c thùc,ng−îc l¹i
Bob sÏ lo¹i bá nã.
Ta sÏ nghiªn cøu hai kiÓu tÊn c«ng kh¸c nhau mµ Oscar cã thÓ tiÕn
hµnh.Trong c¶ hai lo¹i nµy,Oscar sÏ lµ’’kÎ x©m nhËp vµo gi−a cuéc’’.C¸c
phÐp tÊn c«ng nµy ®−îc m« t¶ nh− sau:
Gi¶ m¹o
Oscar ®−a ra mét b¶n tin (s,a) vµo kªnh vµ hi väng nã sÏ ®−îc chÊp
nhËn .Ph−¬ng ph¸p nµy ®−îc m« t¶ trong h×nh 10.1.
Thay thÕ
Oscar quan s¸t mét b¶n tin trong (s,a)kªnh ,sau ®ã anh ta biÕn ®æi nã
thµnh(s’,a’),trong ®ã s’=s vµ hi väng ®−îc Bob chÊp nhËn nh− mét b¶n tin
x¸c thùc .Bëi vËy anh ta tin sÏ l¸i ®−îc Bob ®i tíi tr¹ng th¸i nguån míi
nµy.Ph−¬ng ph¸p nµy ®−îc m« t¶ nh− h×nh 10.2.
.
Oscar
H×nh 10.1. ViÖc gi¶ m¹o bëi Oscar
Oscar (s,a) Bob
H×nh 10.2 . PhÐp thay thÕ cña Oscar.
Alice (s,a) Oscar (s’,a’) Bob
Vietebooks Nguyễn Hoàng Cương
Trang 3
G¾n víi mçi ph¬ng ph¸p nµy lµ mét x¸c xuÊt lõa bÞp,lµ x¸c suÊt ®Ó
Oscar thµnh c«ng trong viÖc lõa Bob nÕu anh ta (Oscar) tu©n thñ mét
chiÕn l−îc tèi −u .C¸c x¸c suÊt nµy ®−îc kÝ hiÖu lµ Pd0(tr−êng hîp gi¶
m¹o)vµ Pd1(tr−êng hîp thay thÕ) .§Ó t×nh Pd0 vµ Pd1ta cÇn ph¶i x¸c
®Þnh c¸c ph©n bè x¸c suÊt trªn S vµK.C¸c x¸c suÊt nµy ®−îc kÝ hiÖu
t−¬ng øng lµ ps vµ pk .
Gi¶ sö r»ng Oscar ®½ biÕt m· x¸c thùc vµ hai ph©n bè x¸c suÊt
nµy.ChØ cã mét th«ng tin mµ Alice vµ Bob cã nh−ng mµ Oscar kh«ng
®−îc biÕt lµ gi¸ trÞ cña kho¸ K .§iÒu nµy t−¬ng tù víi c¸ch mµ chóng ta
®· nghiªn cøu ®é an toµn kh«ng ®iÒu kiÖn cña c¸c hÖ mËt kho¸ bÝ mËt.
10.2.TÝnh x¸c suÊt lõa bÞp
Trong phÇn nµy sÏ xÐt ®Õn viÖc tÝnh c¸c x¸c suÊt lõa bÞp.Ta b¾t ®Çu
vÒ mét m· x¸c thùc.
VÝ dô 10.1
Gi¶ sö K=R=Z
vµ K=Z
3xZ3
Víi mçi (i,j)∈ K vµ mçi s
∈
S ta x¸c ®Þnh
e
k(s) =i.s+j mod 3
§Ó thuËn tiÖn cho viÖc nghiªn cøu ta dïng ma trËn x¸c thùc (ma trËn
nµy t¹o b»ng tÊt c¶ c¸c gi¸ trÞ ek(s)).Víi mçi kho¸ K∈K vµ víi mçi s
∈
S
ta ®Æt nh·n x¸c thùc ek(s) vµo hµng K vµ cét s cña mét ma trËn M kÝch
th−íc K xS .M¶ng M ®−îc m« t¶ trªn h×nh 10.3.
H×nh 10.3.Ma trËn x¸c thùc
Kho¸ 0 1 2
(0,0) 0 0 0
(0,1) 1 1 1
(0,2) 2 2 2
(1,0) 0 1 2
(1,1) 1 2 0
(1,2) 2 0 1
(2,0) 0 1 2
(2,1) 1 0 2
(2,2) 2 1 0
Vietebooks Nguyễn Hoàng Cương
Trang 4
Gi¶ sö r»ng kho¸ ®−îc chän mét c¸ch ngÉu nhiªn,tøc lµ pk(K)=1/9
®èi víi mäi K∈K. Ta kh«ng ph¶i x¸c ®Þnh ph©n bè x¸c suÊt pS v× trong
thÝ dô nµy nã khong cã ý nghÜa g×.
Tr−íc tiªn xÐt c¸ch tÊn c«ng gi¶ m¹o,Oscar sÏ chän ra mét tr¹ng
th¸i nguån s vµ cè g¾ng pháng ddoand\s mét nh·n x¸c thùc ‘’®óng’’.KÝ
hiÖu K0 lµ kho¸ ®ang sö dông (mµ Oscar kh«ng biÕt).ãc¶ sÏ thµnh c«ng
trong viÖc ®¸nh lõa Bob nÕu anh ta pháng ®o¸n a0=eK0(s).Tuy nhiªn víi
bÊt k× s∈S vµ a∈R dÔ dµng thÊy r»ng ,chØ cã ®óng 3(chø kh«ng ph¶i lµ
9)quy t¾c x¸c thùc K∈K sao cho ek(s) =a.(Nãi c¸ch kh¸c mçi kÝ hiÖu
chØ xuÊt hiÖn 3 lÇn trong mçi cét cña ma trËn x¸c thùc ).Bëi vËy dÉn tíi
Pd0=1/3.
Ph©n tÝch phÐp thay thÕ cã phøc t¹p h¬n mét chót.Gi¶ sö Oscar ®·
quan s¸t ®−îc trªn kªnh 1 b¶n tin (0.0).Nhê ®ã anh ta ®· biÕt mét
th«ng tin nµo ®ã vÒ kho¸:anh ta biÕt r»ng :
K
0∈{(0,0),(1,0),(2,0)}
B©y giê ,gi¶ sö Oscar thay b¶n tin (0,0) b»ng b¶n tin (1,1).Khi ®ã
anh ta sÏ lõa bÞp thµnh c«ng khi vµ chØ khi K0=(1,1) ,x¸c suÊt ®Ó K0 lµ
kho¸ b»ng 1/3 v× kho¸ n»m trong tËp {(0,0),(1,0),(2,0)}.
Cã thÓ thùc hiÖn mét ph©n tÝch t−¬ng tù ®èi víi bÊt k× mét phÐp thay
thÕ nµo mµ Oscar tiÕn hµnh.Nãi chung nÕu Oscar quan s¸t mét b¶n tin
(s,a) vµ thÊy nã b»ng mét b¶n tin bÊt k× (s’,a’) trong ®ã s’=s th× anh ta
sÏ ®¸nh lõa ®−îc Bob víi x¸c suÊt 1/3.Ta cã thÓ thÊy râ ®iÒu nµy nh−
sau .ViÖc quan s¸t ®−îc (s,a) sÏ h¹n chÕ khãa vµ mét trong ba kh¶
n¨ng.Trong khi ®ã víi mét phÐp chän (s’,a’) chØ cã mét kho¸ chø
kh«ng ph¶i ba kho¸ cã thÓ )theo quy t¾c a lµ nh·n x¸c thùc cña s’.
B©y giê ta sÏ th¶o luËn c¸ch tÝnh to¸n tæng qu¸t cho c¸c x¸c
suÊt lõa bÞp.Tr−íc tiªn ta h·y x¸t Pd0.Còng nh− trªn K0 lµ kho¸ ®−îc
chän bëi Alice vµ Bob.Víi s∈S vµ a∈R ta x¸c ®Þnh payoff(s,a)lµ x¸c
suÊt ®Ó Bob chÊp nhËn b¶n tin (s,a) lµ b¶n tin x¸c thùc .DÔ dµng thÊy
r»ng :
Payoff(s,a) = prob(a=eK(s))
=∑ K∈K (ek(s) = a) pK(K)
NghÜa lµ payoff(s,a) ®−îc tÝnh b»ng c¸ch chän c¸c hµng cña ma trËn
x¸c thùc cã phÇn tö a n»m trong cét s vµ lÊy tæng x¸c suÊt cña c¸c kho¸
K t−¬ng øng.
§Ó c¬ héi thµnh c«ng lµ lín nhÊt.Oscar phØa chän (s,a) sao cho
payoff(s,a) lµ cùc ®¹i .Bëi vËy:
Pd
0 =max{payoff(s,a): s∈S.a∈R} (10.1)
Chó ý r»ng Pd0 kh«ng phô thuéc vµo ph©n bè x¸c suÊt pS
Vietebooks Nguyễn Hoàng Cương
Trang 5
ViÖc tÝnh Pd1 cã khã h¬n mét chót vµ nã cã thÓ phô thuéc vµo
pS.Tr−íc tiªn ta sÏ xÐt bµi to¸n sau:Gi¶ sö Oscar quan s¸t ®−îc th«ng
b¸o (s,a) trong kªnh.Oscar sÏ thay (s,a) b»ng mét b¶n tin (s’,a’) nµo ®ã
,trong ®ã s’≠s.Khi ®ã,víi s,s’∈S ,s≠s’ vµ a,a’∈R ta ®Þnh nghÜa
payoff(s’,a’;s,a) lµ x¸c suÊt ®Ó phÐp thay thÕ (s,a) b»ng (s’,a’) thµnh
c«ng(®Ó ®¸nh lõa Bob) .Khi ®ã cã thÓ tÝnh nh− sau :
Payoff(s’,a’;s,a) =prob(a’=eKo(s’)⏐a=eKo(s))
= ))((
))()'('(
seaprob
seaseaprob
K
KK
=
=
Λ
=
Tö sè cña ph©n sè nµy ®−îc tÝnh b»ng c¸ch chän c¸c hµng cña ma trËn
x¸c thùc cã gi¸ trÞ a trong cét s vµ gi¸ trÞ a’ trong cét s’vµ lÊy tæng c¸c
x¸c suÊt cña c¸c kho¸ t−¬ng øng.V× Oscar muèn t¨ng cùc ®¹i c¬ héi
®¸nh lõa Bob nªn anh ta tÝnh :
P
S = max{payoff(s’,a’;s,a);s’∈S,s≠s’,a∈R}
§¹i l−îng p,kÝ hiÖu ®Ó Oscar ®¸nh lõa Bob b»ng mét phÐp thay thÕ khi
®· quan s¸t ®−îc b¶n tin (s,a) trªn kªnh.
B©y giê ph¶i lµm thÕ nµo ®Ó tÝnh ®Ó tinhs x¸c suÊt lõa bÞp Pd1?Râ
rµng lµ ë ®©y ta ta ph¶i tÝnh trung b×nh c¸c gi¸ trÞ cña l−îng pS theo c¸c
x¸c suÊt pM(s,a) quan s¸t c¸c b¶n tin trªn kªnh.NghÜa lµ Pd1 ®−îc tÝnh
b»ng :
Pd
1 =∑(S,a)∈M pM(s,a).pM (10.2)
Ph©n bè x¸c suÊt pM nh− sau:
P
M(s,a) =ps(s)x pK(a⏐s)
=p
S(s)x∑(K∈K; ek(s)=a) pK(K)
=p
S(s)xpayoff(s,a)
Trong vÝ dô 10.1:
Payoff(s,a) =1/3
Víi ∀s’,a’,s,a,s≠s’ .Bëi vËy Pd1=1/3 ®èi víi mäi ph©n tè x¸c suÊt pS
(nãi chung Pd1 phô thuéc vµo pS).
Trong vÝ dô sau ®©y sÏ xÐt viÖc tÝnh Pd0 vµ Pd1 .
VÝ dô 10.2:
XÐt ma trËn trªn h×nh 10.4Gi¶ sö c¸c ph©n bè x¸c suÊt trªn S vµ K lµ:
P
S(i)=1/4
1≤ i ≤ 4 vµ
pK(1)=1/2 ; pK(2)=pK(3)=1/4