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êngK 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 lu cùng với số liệu:KHOá ĐƯẻc dùng để
tạo và kiểm tra dấu xác thực đợc lu một cách tách bạch trong
mộtvùngan 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

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 gia 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 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
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
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

(s)).Với mỗi khoá KK 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à p
k
(K)=1/9 đối
với mọi KK. 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

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 sS và aR 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=e
K
(s))
=
K

K
(ek(s) = a)
p
K
(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): sS.aR} (10.1)
Chú ý rằng Pd

xác thực có giá trị a trong cột s và giá trị a trong cột svà 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);sS,ss,aR}
Đạ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 :
Pd
1
=
(S,a)

M
p
M
(s,a).p
M

chung Pd
1
phụ thuộc vào p
S
).
Trong ví dụ sau đây sẽ xét việc tính Pd
0
và Pd
1
.
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à
p
K
(1)=1/2 ; p
K
(2)=p
K
(3)=1/4
Hình 10.4 Ma trận xác thực
Khoa 1 2 3 4
1 1 1 1 2
2 2 2 1 2
3 1 2 2 1
Các giá trị payoff(s,a) nh sau :
Payoff(1,1) =3/4 Payoff(1,1) =1/4

0
1/2
0
1/2
1
1/2
0
1/2
1
1/2
(3,1)
(3,2)
2/3
1
1/3
0
2/3
0
1/3
1
0
1
1
0
(4,1)
(4,2)
1
2/3
0
1/3

1
=7/8
Việc tính toán Pd
1
trong ví dụ 10.2 dễ hiểu nhng khá dài dòng .Trên
thực tế có thể đơn giản hóa việc tính Pd
2
dựa trên nhận xét là ta đã
thực hiện việc chia cho đại lợng payoff(s,a) khi tính P
s,a
và sau đó
Lại nhân với payoff(s,a) khi tính Pd
1
.Dĩ nhiên là hai phép tính này loại
bỏ nhau.Giả sử định nghĩa :
q
s,a
=max{
AassSsKp
asekasekKK
K


==
',',':)(
'Ư})'(,)(:{
}
Với mọi s,a. Khi đó có công thức đơn giản hơn sau:
10.3.Các giới hạn tổ hợp
Ta đã thấy ràng độ an toàn của một mã xác định đợc đo bằng

(K

K :ek(s)=a}
p
K
(K)
=
K

K
p
K
(K)
=1
Bởi vậy với mỗi sS,tồn tại một nhãn xác thực a(s) sao cho :
Payoff(s,a(s))1/l.
Dễ dàng rút ra định lý sau:
Đinh lý 10.1
Giả sử (S,R,K,E) là một mã xác thực .Khi đó Pd
0

1/l trong đó
l=

R

.Ngoài ra Pd
0
=1/l khi và chỉ khi :