- 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. - 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ộ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.. - đợc sử dụng khi nghiên cứu các mã xác thực.. - 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. - A là tập hợp các nhãn xác thực có thể. - 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. - 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.. - đổ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.. - 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ó nhng 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.. - Giả sử K=R=Z. - Để 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. - 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. - (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’.. - đợ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. - 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.. - Pd 0 =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. - 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. - M p M (s,a).p M (10.2) Phân bố xác suất p M nh sau:. - 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 K (2)=p K (3)=1/4 Hình 10.4 Ma trận xác thực. - Việc tính toán Pd 1 trong ví dụ 10.2 dễ hiểu nhng khá dài dòng .Trên. - bỏ nhau.Giả sử định nghĩa. - 10.3.Các giới hạn tổ hợp. - Rất qoan trọng .Ta xem xét một số vấn đề cấn qoan tâm trong mã xác thực. - 2.số các trạng thái nguồn phải đủ lớn để có thể truyền các thông tin cần thiết bằng cách gán một nhãn xác thực vào một trạng thái nguồn. - Trong phần này sẽ xác địinh giới hạn dới đối với các xác suất lừa bịp và chúng đợc tính theo các tham số của mã.Hãy nhớ lại rằng ta đã định nghĩa mã xác thực là một bộ bốn (S,R,K,E).Trong phần này ta sẽ ký hiệu R =l. - Giả sử cố định một trạng thái nguồn s ∈ S.Khi đó có thể tính. - Bởi vậy với mỗi s ∈ S,tồn tại một nhãn xác thực a(s) sao cho : Payoff(s,a(s. - Giả sử (S,R,K,E) là một mã xác thực .Khi đó Pd 0 ≥ 1/l trong đó l. - Giả sử (S,R,K,E) là một mã xác thực .Khi đó Pd 1 >=1/l trong đó L. - Giả sử (S,R,K,E) là một mã xác thực trong đó l. - Các phơng trình (10.4)và (10.5) boa hàm phơng trình (10.6).Ngợc lại , phơng trình (10.6) kéo theo các phơng trình (10.4) và(10.5).. - Giả sử (S,R,K,e) là một mã xác thực ,trong đó l. - K /l 2 (10.7) Với mọi s,s. - 10.3.1.Các mạng trực giao. - Trong phần này ta xét các mối liên quan gia các mã xác thực và các cấu trúc tổ hợp đợc gọi là các mảng trực giao.Trớc tiên ta sẽ. - Trong hình 10.5 ta đa ra một mảng trực giao 0A(3.3.1) nhận đ- ợc từ ma trận xác thực ở hình 10.3.. - Có thể dùng một mảng trực giao bất kì 0A(n,k, λ ) để xây dựng một mã xác thực có Pd 0 =Pd 1 =1/n nh đợc nêu trong định lí sau:. - Định lí 10.5.. - Giả sử có một mảng trực giao 0A(n,k, λ ).Khi đó cùng tồn tại một mã xác thực (S,A,K,E).trong đó S =k. - Hãy dùng mỗi hàng của mảng trực giao làm một quy tắc xác thực với xác suất nh nhau bằng 1/( λ n 2 ).Mối liên hệ tơng ứng gia mảng trực giao và mã xác thực đợc cho ở bảng dới đây.Vì phơng trình (10.7) đợc thoả mãn nên ta có thể áp dụng hệ quả 10.4 để thu. - đợc một mã xác thực có các tính chất đã nêu.. - Mảng trực giao Mã xác thực. - Hàng Quy tắc xác thực. - Kí hiệu Nhãn xác thực. - 10.3.2.Phơng pháp xây dựng và các giới hạn đối với các 0A Giả sử ta xây dựng một mã xác thực từ một 0A(n,k, λ ).Tham số n sẽ xác định số các nhãn (tức là độ an toàn của mã).Tham số k xác định số các trạng thái nguồn mà mã có thể thích ứng.Tham số λ chỉ quan hệ tới số khoá (là λ n 2 ).Dĩ nhiên trờng hợp λ =1là trờng hợp mong muốn nhất tuy nhiên ta sẽ thấy rằng đôi khi cần phải dùng các mảng trực giao có λ lớn hơn.Giả sử ta muốn xây dựng một mã xác thực ới tập nguồn xác định S và có một mức an toàn ε xác định (tức là để Pd 0 <ε và Pd 1 <ε).Khi đó mảng trực giao thích hợp phải thoả mãn các điều kiện sau:. - Định lí 10.6.. - Giả sử tồn tại một 0A(n,k, λ ) .Khi đó k ≥ n+1. - Định lí 10.7. - Giả sử p là một số nguyên tố.Khi đó tồn tại một mảng trực giao 0A(p.p.1).. - i=(a-b)(x-y) 4 mod p j=a-y.x mod p Bởi vậy ta có một mảng trực giao.. - Nhận xét rằng một 0A(n,n,1) bất kì có thể mở rộng thêm một cột để tạo thành 0A(n,n+1,1)(xem các bài tập ).Vì thế dùng định lí 10.7 có thể nhận đợc vô hạn các 0A đạt đợc giới hạn của định lí 10.6 với dấu bằng.. - Định lí 10.6 cho biết rằng λ >1 nếu k>n+1.Ta sẽ chứng minh một kết quả tổng quát hơn khi đặt giới hạn dới của λ nh một hàm của n và k.Tuy nhiên,trớc tiên cần đa ra một bất đẳng thức quan trọng sẽ dùng trong chứng minh.. - Giả sử b 1 ....b m là các số thực.Khi đó:. - Định lí 10.9.. - Giả sử tồn tại một 0A(n,k,λ).Khi đó. - áp dụng bổ đề (10.8) ta có:. - Đị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.(p d -1)/(p-1).p d-2. - Ta sẽ chứng minh A là mảng trực giao mong muốn.Cho b’,c. - 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 trng 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 trng 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.. - đị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à Pd 0 =Pd 1 =1/n.Khi đó K. - n 2 .Hơn nữa K =n 2 khi và chỉ khi có một mảng trực giao 0A(n.k.l) trong đó S =k và p K (K)=1/n 2 với mọi khoá K ∈ K. - ơ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. - =1,với mọi cặp (a,a’) và từ phơng trình (10.6) ,cho ta thấy rằng p K (K)=1/n 2 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ì K a,a. - Định lí 10.2. - Giả sử (S,A,K,E) là một mã xác thực ,trong đó A =n và Pd 0 =Pd 1 =1/n.Khi đó 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. - Định lí 10.13. - Giả sử (S,R.K,E) là một mã xác thực .Khi đó LogPd 0 ≥ H(K M)-H(K). - Từ phơng trình (10.1) ta có. - ậ đâ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.. - Định lí 10.4. - Giả sử rằng (S,A,K,E) là một mã xác thực .Khi đó LogPd 1 ≥ H(K M 2 )-H(K M). - Cần phải xác định giới hạn entropy theo biến ngẫu nhiên M 2 .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 (m 1, m 2 )∈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 p sxs (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:. - Vì mỗi một trong λn 2 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 λ n.Mỗi khoá trong λ n khóa này sẽ có tập con nh nhau .Vì thế H(K m)=log λ n với bản tin n bất kì .Khi đó ta có. - 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]. - 10.1.Hãy tính Pd 0 và Pd 1 của mã xác thực đợc biểu thị trong ma trận sau. - 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(n 1 ,k,λ 1 ) trên tập kí hiệu {1,...,n 1 } và giả sử B là một 0A(n 2 ,k, λ 2 ) trên tập kí hiệu {1,...,n 2 }Ta xây dựng C là một 0A(n 1 ,n 2 ,k, λ 1 λ 2 ) trên tập kí hiệu {1...n 1 }x{1...n 2 } nh sau :với mỗi hàng r 1 =(x 1 ...x k ) của A và với mỗi hàng s 1 ={y 1 ...y k } của B ta xác định một hàng t 1 của C là:. - 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 M 2 )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à
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt