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 ậ ữ ạ ạ ồ ể
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 eộ ắ ự k : 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=eẽk(s) và g i b n tin (s,a)cho Bob.Khiử ả
nh n đ c (s,a) Bob tính a’=eậ ượ K(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
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à Pdế ượ ố ư ấ ượ ệ 0(tr ng h pườ ợ
gi m o)và Pdả ạ 1(tr ng h p thay th ) .Đ tình Pdườ ợ ế ể 0 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à pệ ươ ứ s 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=Z3xZ3
V i m i (i,j)ớ ỗ ∈ K và m i ỗs
∈
S ta xác đ nh ị
ek(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 eậ ạ ằ ấ ả ị k(s)).V i m i khoá Kớ ỗ ∈K và v iớ
m iỗ s
∈
S
ta đ t nhãn xác th c eặ ự k(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
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 pấS 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 Kệ0 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 Pdậ ự ở ậ ẫ ớ 0=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 :ề ế ằ
K0∈{(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 Kẽ ừ ị ỉ 0=(1,1) ,xác su t đ Kấ ể 0 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 Pdấ ừ ị ướ 0.Cũng nh trên Kư0 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:ự ạ ở ậ
Pd0 =max{payoff(s,a): s∈S.a∈R} (10.1)
Chú ý r ng Pdằ0 không ph thu c vào phân b xác su t pụ ộ ố ấ S
Vi c tính Pdệ1 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 :ạ ơ ộ ừ
PS = 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 Pdờ ả ế ể ể ấ ừ ị 1?Rõ
ràng là đây ta ta ph i tính trung bình các giá tr c a l ng pở ả ị ủ ượ S theo
các xác su t pấM(s,a) quan sát các b n tin trên kênh.Nghĩa là Pdả1 đ cượ
tính b ng :ằ
Pd1 =∑(S,a)∈M pM(s,a).pM(10.2)
Phân b xác su t pố ấ M nh sau:ư
PM(s,a) =ps(s)x pK(as)
=pS(s)x∑(K∈K; ek(s)=a) pK(K)
=pS(s)xpayoff(s,a)
Trong ví d 10.1:ụ