Cơ sở mật mã học - Chương 10: Các mã xác thực

	hoặc l2(n3-n2)³l(k(n-1)2+n-1)
Cuối cùng,chia hai vế cho l(n-1) ta có :
	ln2³k(n-1)+1
Đây chính là giới hạn cần tìm.
	 Kết quả sau thiết lập sự tồn tại của một lớp vô hạn các mảng trực giao đạt được giới hạn nêu trên với đấu ‘’=’’.
Định lí 10.10.
	 Giả sử p là một số nguyên tố và d³2 là một số nguyên.Khi đó tồn tại một mảng trực giao 0A(p.(pd-1)/(p-1).pd-2
 Chứng minh:
 Kí hiệu (ZP)d là không gian véc tơ chứa tất cả bộ d trên ZP.Ta sẽ xây dựng A (là một 0A(p,(pd-1)/(p-1),pd-2) trong đó các hàng và các cột được lập chỉ số theo các véc tơ trong (ZP)d.Các phần tử của A sẽ là các phần tử của ZP.Tập hợp các hàng được xác định là R=(Zp)d):tập các cột là :
 C = {(c1...cd)Î(Zp)d: $j,0£j£d-1 ,c1=...=cj=0,cj+1=1}
R chứa tất cả các véc tơ trong (ZP)d,bởi vậy ½R½=pd.C chứa tất cả các véc tơ khác không có toạ độ khác 0 đầu tiên bằng 1.Nhận thấy rằng:
	½C½=
và không có hai véc tơ nào trong C là các bội vô hướng của nhau.
 Bây giờ vưói mỗi véc tơ r’ ÎR và mỗi c’ÎC ta định nghĩa:
	A(r’.c’)=r’.c’
Trong đó “.”kí hiệu tích trong hai véc tơ (được rút gọn theo mod p).
 Ta sẽ chứng minh A là mảng trực giao mong muốn.Cho b’,c’ÎC là hai cột khác nhau và cho x,yÎZP.Ta sẽ tính số hàng r’ để A(r’,b’)=x và A(r’,b’)=y.Kí hiệu r’=(r1,r2....rd).b’=(b1,b2....bd) và c’=(c1,c2....cd).Hai phương trình r’.b’=x và r’.c’=y có thể được viết thành hai phương trình tuyến tính trong ZP
	 b1.r1+...+bd.rd=x
	 c1.r1+...+cd.rd=y.
Đây là hai phương trình tuyến tính với d ẩn r1...rd.Vì các bội b’và c’ không phải là các bội vô hướng của nhau nên hai phương trình trên là độc lập tuyến tính.Bởi vậy hệ này có không gian nghiệm (d-2) chiều.Nghĩa là số các nghiệm (số các hàng trong đó x nằm ở cột b’ và y ở cột c’)bằng pd-2 theo mong muốn.
 Ta sẽ làm một ví dụ nhỏ minh hoạ cách xây dựng này:
Ví dụ 10.3
 Giả sử lấy p=2,d=3,khi đó ta sẽ xây dựng một 0A(2,7,2).Ta có :
	 R={000,001,010,011,100,101,110,111}
 và	C={001,010,011,100,101,110,111}
Ta nhận được kết quả là mảng trực giao như trên hình 10.6
 Hình 10.6.Một 0A(2,7,2).
10.3.3Đặc trưng của mã xác thực .
 Cho tới giờ ta đã nghiên cứu các mã xác thực nhận được từ các mảng trực giao.Ta cũng đã xem xét các điều kiện tồn tại cần thiết về việc xây dựng các mảng trực giao .Vấn đề ở đây là liệu có các phương pháp khác tốt hơn các mảng trực giao không?Tuy nhiên hai định lí đặc trưng sẽ cho biết rằng nếu chỉ giới hạn mối quan tâm tới các mã xác thực có xác suất lừa bịp nhỏ tới mức co thể thì vấn đề trên không cần phải đặt ra nữa.
 Trước tiên ta sẽ chứng minh một định lí đảo một phần của định lí 10.5.
Định lí 10.11.
 Giả sử (S,A,K,E)là một mã xác thực trong đó ½R½=n và Pd0=Pd1=1/n.Khi đó ½K½³n2.Hơn nữa ½K½=n2 khi và chỉ khi có một mảng trực giao 0A(n.k.l) trong đó ½S½=k và pK(K)=1/n2 với mọi khoá KÎK .
 Chứng minh:
 Cố định hai trạng thái nguồn tuỳ ý s và s’ ,s=s’ và xét phương trình (10.6).Với mỗi cặp được sắp (a,a’) của các nhãn xác thực ta xác định :
	Ka,a’={KÎK :eK(s)=a,eK(s’)=a’}.
Khi đó ½K½>0 với mọi cặp (a,a’).Cũng thấy rằng các tập Ka,a’ này rời nhau (có n2 tập).Bởi vậy K³n2.
 Bây giờ giả sử rằng ½K½=n2 .Khi đó trị ½Ka,a’½=1,với mọi cặp (a,a’) và từ phương trình (10.6) ,cho ta thấy rằng pK(K)=1/n2 với mọi khoá KÎK.
 Vấn đề còn lại là phải chứng tỏ ma trận xác thực sẽ tạo nên ma trận trực giao 0A(n,k,l) .Xét các cột lấy chỉ số theo các trạng thái nguồn s và s’.Vì ½Ka,a’½=1 với mọi (a,a’) nên mỗi cặp được sắp xuất hiện dúng một lần trong hai cột này.Vì s,s’ là tuỳ ý nên mỗi cặp được sắp xuất hiện đúng một lần trong hai cột bất kì.
	 Đặc trưng sau đây có khó hơn một chút chúng ta chỉ phát biểu mà không chứng minh .
Định lí 10.2
 Giả sử (S,A,K,E) là một mã xác thực ,trong đó ½A½=n và Pd0=Pd1=1/n.Khi đó ½K½³k(n-1)+1.Hơn nữa ½K½=k(n-1)+1 khi và chỉ khi có một mảng trực giao 0A(n,k,l),ở đây ½S½=k,l=(k(n-1)+1)/n2 và pK(K)=1/(k(n-1)+1) với mọi khoá KÎK.
Nhận xét.Chú ý rằng định lí 10.10 tạo ra một lớp vô hạn các mảng trực giao đạt được giới hạn ở định lí 10.12 với dấu “=”.
10.4.các giới hạn entropy
	 Trong phần này chúng ta dùng kĩ thuật entropy để nhận được các giới hạn về các xác suất lừa bịp .Trước tiên ta sẽ xét các giới hạn đối với Pd0.
 Định lí 10.13
	 Giả sử (S,R.K,E) là một mã xác thực .Khi đó 
	LogPd0³H(K½M)-H(K)
Chứng minh:
 Từ phương trình (10.1) ta có :
	Pd0³ max{payoff(s,a):sÎS,aÎR}
Vì giá trị cực của payoff(s,a) phải lớn hơn trung bình các trọng số của chúng nên ta nhận được:
	Pd0³åsÎS,aÎRpM(s,a)payoff(s,a)
Như vậy thoe bất đẳng thức Jensen(dịnh lí (2.5) ta có :
	LogPd0³logåsÎS,aÎRpM(s,a)payoff(s,a)
	³åsÎS,aÎRpM(s,a)log payoff(s,a)
Theo phần 10.2:
	PM(s,a)=ps(s)x payoff(s,a)
Ta thấy rằng:
	Log Pd0³åsÎS,aÎRps(s)payoff(s,a) log payoff(s,a)
Bây giờ ta thấy rằng payoff(s,a)=pR(a½s)(tức là xác suất để a là nhãn xác thực với điều kiện s là trạng thái nguồn ).Bởi vậy:
	LogPd0 ³ åsÎS,aÎRps(s).pR(a½s) logpR(a½s) =-H(A½S)
Theo định nghĩa của entropy có điều kiện .Ta sẽ hoàn chỉnh chứng minh định lí bằng cách chỉ ra rằng: -H(A½S)=H(K½M)-H(K).Điều kiện này được rút ra từ các đồng nhất thức cơ bản của entropy.Một mặt ta có :
	H(K,A,S)=H(A½K,S)+H(A½S)+H(S)
Mặt khác ta tính:
	H(K,A,S)=H(A½K,S)+H(K,S)=H(S)+H(K)
ậ đây ta có sử dụng điều kiện H(A½K,S)=0 vì khoá và trạng thái nguồn sẽ xác định nhãn xác thực một cách duy nhất .Ta cũng dùng đẳng thức H(A½S)=H(K)+H(S) vì nguồn và khoá là các biến cố độc lập.
	So sánh hai biểu thức biểu thị H(K,S,A) ta có:
	-H(A,S)=H(K½A,S)-H(K)
Tuy nhiên thông báo m=(s,a) được xác định gồm một trạng thái nguồn và một trạng thái nhãn xác thực(nghĩa là M=SxA).Bởi vậy:
	H(K½A,S)=H(K½M)
Định lí được chứng minh.
 Sau đây ta sẽ chỉ đưa ra mà không chứng minh giới hạn tương tự cho Pd1.
Định lí 10.4
	 Giả sử rằng (S,A,K,E) là một mã xác thực .Khi đó 
	LogPd1³H(K½M2)-H(K½M)
	Cần phải xác định giới hạn entropy theo biến ngẫu nhiên M2.Giả sử ta xác thực hai trạng thái nguồn khác nhau dùng cùng một khoá K.Theo cách này ta nhận được một cặp được sắp các banr tin (m1,m2)ÎMxM.Để xác định phân bố xác suất trên MxM,cần phải xác định xác suất trên SxS với điều kiện psxs(s,s)=0 với mọi sÎS(nghĩa là không cho phép lặp lại trạng thái nguồn ).Các phân bố xác suất trên K và SxS sẽ dẫn đến phân bố xác suất trên MxM tương tự như phân bố xác suất trên K và S sẽ tạo nên một phân bố xác suất trên M Dể minh hoạ cho hai giới hạn trên ,xét cấu trúc mảng trực giao cơ bản và chỉ ra rằng cả hai giới hạn trong định lí 10.13 và 10.14 đều đạt được với dấu bằng.Trước hết ta dễ thấy rằng:
	H(K)=logln2
Vì mỗi một trong ln2 quy tắc xác thực đều được chọn đồng xác suất.Tiếp theo ta sẽ quay lại việc tính toán H(K½M).Nừu đã quan sát được một bản tin m=(s,a) nào đó thì điều này sẽ giới hạn các khóa sẽ nằm trong tập con có lực lượng ln.Mỗi khoá trong ln khóa này sẽ có tập con như nhau .Vì thế H(K½m)=logln với bản tin n bất kì .Khi đó ta có :
	H(K½M)=åmÎMpM(m)H(K½m)
	 =åÎMpM(m)logln
	 =log ln
Như vậy ta có:
	H(K½M)-H(K)=logln-logln2=-logn=logPd0
Như vậy giới hạn thoả mãn với dấu “=”.
	 Nừu ta quan sát được hai bản tin (được tạo ra theo cùng một khoá và các trạng thái nguồn khác nhau )thì số các khoá có thể giảm xuống còn l.Lập luận tương tự như trên ta thấy rằng H(K½M2)=logl.Khi đó:
	H(K½M)-H(K)=logl-logln
	 =-logn=-Pd1
Như vậy giới hạn này được thoả mãn với dấu “=”.
10.5.các chú giải và tài liệu dẫn
	 Các mã xác thực được phát minh vào năm 1974 bởi Gilbert.Mac-Williams và Sloane [GMS 74ư.Nhiếu phần lí thuyết về các mã xác thực đã được Simones phát triển,ông đã chứng minh nhiều kết quả cơ bản trong lĩnh vực này.Hai bài tổng quan hữa ích của Simones là [Si92] và [Si88].Massey cũng trình bày một tổng quan khá hay khác trong [Ma86].Các mối liên hệ giữa các mảng trực giao và các mã xác thực đã là mối quan tâm của nhiều nhà nghiên cứu..Cách trình bày ở đây dựa vào ba bài báo của Stinson[St 88],[St 90]và [St 92].Các mảng trực giao đã được nghiên cứu trong hơn 45 năm bởi các nhà nghiên cứu trong lĩnh vực thống kê và trong lí thuyết thiết kế tổ hợp.Ví dụ,giới hạn trong định lí 10.9 lần đầu tiên được chứng minh bởi Placket và Berman vào 1945 trong [PB 45].Nhiều kết quả thú vị về các mảng trực giao có thể tìm được trong nhiều giáo trình khác nhau về lí thuyết thiết kế tổ hợp(chẳng hạn như trong [BJL 8] của Beth,Jungickel và Lenz).
 Cuối cùng việc sử dụng kĩ thuật entropy trong việc nghiên cứu các mã xác thực do Simone đưa ra .Giới hạn của định lí 10.13 đã được Simone chứng minh trước tiên trong [Si 85];một cánh chứng minh của định lí 10.14 có thể tìm được trong [Wa 90] của Walker.
BàI TậP
10.1.Hãy tính Pd0 và Pd1 của mã xác thực được biểu thị trong ma trận sau :
Khoá
1
2
3
4
1
1
1
2
3
2
1
2
3
1
3
2
1
3
1
4
2
3
1
2
5
3
2
1
3
6
3
3
2
1
Các phân bố xác suất trên S và K như sau:
	Ps(1)=ps(4)=1/6 ,ps(2)=ps(3)=1/3
	pK(1)=pK(6)=1/4, pK(2)=pK(3)=pK(4)=pK(5)=1/8.
 Nêu các chiến lược thay thế và giả mạo tối ưu .
	10.2.Ta đã biết cấu trúc đối với một mảng trực giao 0A(p,p,1)khi p là số nguyên tố.Hãy chứng tỏ rằng luôn có thể mở rộng 0A(p,p,1)thêm một cột nữa để tạo thành 0A(p,p+1,1).Hãy minh hạo cấu trúc của bạn trong trường hợp p=5.
10.3.Giả sử A là một cấu trúc 0A(n1,k,l1) trên tập kí hiệu {1,...,n1} và giả sử B là một 0A(n2,k,l2) trên tập kí hiệu {1,...,n2}Ta xây dựng C là một 0A(n1,n2,k,l1l2) trên tập kí hiệu {1...n1}x{1...n2} như sau :với mỗi hàng r1=(x1...xk) của A và với mỗi hàng s1={y1...yk} của B ta xác định một hàng t1 của C là:
	t1=((x1,y1),...,(xk,yk)).
Hãy chứng manh rằng C thực sự là một 0A(n1n2,k,l1l2).
10.4.Hãy xây dựng một mảng trực giao 0A(3,13,3).
10.5Hãy viết một chương trình máy tính để tính H(K),H(K½M) và H(K½M2)cho mã xác thực ở bài toán 10.1Phân bố xác suất trên cavcs dãy của hai nguồn là :
Hãy so sánh giới hạn entropy của Pd0 và Pd1 với các giá trị mà bạn tính được trong bài tập 10.1.
Chỉ dẫn:Để tính pK(k½m) hãy dùng công thức Bayes:
 pK(k½m) = 
	 Ta đã biết cách tính pM(m).Để tính pM(m½k) hãy viết m=(s,a) và nhận xét thấy rằng :pM(m½k)=pS(s) nếu eK(s)=a và pM(m½k)=0 trong trường hợp ngược lại .