Truyền và bảo mật thông tin

Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 1 TRUYỀN VÀ BẢO MẬT THÔNG TIN Nguyễn Văn Khang – Khoa Tin học, ĐHSP Huế nguyenvankhang@dhsphue.edu.vn Truyền và bảo mật thông tin 2 Tài liệu tham khảo 1. Phan Đình Diệu. Lý thuyết mật mã và An toàn thông tin, Đại học Quốc Gia Hà Nội 2. Nguyễn Hữu Tuân, Giáo trình An toàn và bảo mật thông tin, Trường đại học Hàng hải- Hải Phòng 3. TS. Lê Quy ết Thắng, ThS. Phan Tấn Tài, Ks. Dương Văn Hiếu, Giáo trình lý thuyết thông tin. 4. Douglas R. Stinson. Cryptography Theory and practice. CRC Press. 1995. 5. David J.C. Mackey, Information Theory, Infernce, and Learning Algorithms, CamBridge 6. University Express-2003. 7. G.J.ChaiTin, Algorithmic Information Theory, CamBridge University Express-1992. 8. Sanford Goldman, Information Theory. Thông tin và truyền thông tin Phần I. MỞ ĐẦU Chương I. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 2 Truyền và bảo mật thông tin 5 Thông tin „ Thông tin là một khái niệm trừu tượng, khó định nghĩa chính xác. Hai định nghĩa về thông tin tiêu biểu: „ Thông tin là sự cảm hiểu của con người về thế giới xung quanh thông qua sự tiếp xúc với nó. „ Thông tin là một hệ thống những tin báo và mệnh lệnh giúp loại trừ sự không chắc chắn (uncertainty) trong trạng thái của nơi nhận tin. Nói ngắn gọn, thông tin là cái mà loại trừ sự không chắc chắn. „ Định nghĩa đầu chưa nói lên được bản chất của thông tin. „ Định nghĩa thứ hai nói rõ hơn về bản chất của thông tin và được dùng để định lượng thông tin trong kỹ thuật. Truyền và bảo mật thông tin 6 Thông tin „ Thông tin là cái được truyền từ đối tượng này đến đối tượng khác để báo một “điều” gì đó. Thông tin chỉ có ý nghĩa khi “điều” đó bên nhận chưa biết. „ Thông tin xuất hiện dưới nhiều dạng âm thanh , hình ảnh, ... Những dạng này chỉ là “vỏ bọc” vật chất chứa thông tin. “Vỏ bọc” là phần “xác”, thông tin là phần “hồn”. „ Ngữ nghĩa của thông tin chỉ có thể hiểu được khi bên nhận hiểu được cách biểu diễn ngữ nghĩa của bên phát. „ Một trong những phương tiện để diễn đạt thông tin là ngôn ngữ . „ Có hai trạng thái của thông tin: truyền và lưu trữ . Môi trường truyền/lưu trữ được gọi chung là môi trường chứa tin hay kênh tin. Truyền và bảo mật thông tin 7 Mô hình quá trình truyền tin „ Lý thuyết thông tin nghiên cứu quá trình xử lý tín hiệu như sau: „ Đầu vào (input): nhận tín hiệu từ một lĩnh vực cụ thể, tức là tín hiệu xuất hiện theo các ký hiệu (symbol) từ một tập hợp cho trước và theo phân phối xác suất đã biết. „ Tín hiệu được truyền đi trên kênh truyền (channel) và có thể bị nhiễu cũng theo một phân phối xác suất nào đó. Truyền và bảo mật thông tin 8 Mô hình quá trình truyền tin „ Kênh truyền có thể được hiểu dưới hai nghĩa: „ Dưới nghĩa vật lý: kênh truyền là một hệ thống truyền tín hiệu (dây dẫn, mạch, sóng, ...) và gây nhiễu tùy thao chất lượng của hệ thống. „ Dưới nghĩa toán học: kênh truyền là các phân phối xác suất xác định trên lớp các tín hiệu đang xét ở đầu nhận tín hiệu (output). Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 3 Truyền và bảo mật thông tin 9 Mô hình quá trình truyền tin „ Nguồn tin (information source): Là một tập hợp các tin mà hệ thống truyền tin dùng để lập các bảng tin hay thông báo (message) để truyền tin. „ Các tín hiệu như âm thanh, hình ảnh.. Là các hàm liên tục theo thời gian, nguồn tin như thế gọi là nguồn liên tục (continuous source), các tin đó được gọi là tin liên tục (continuous information) và kênh tin được gọi là kênh liên tục (continuous channel). Truyền và bảo mật thông tin 10 Mô hình quá trình truyền tin „ Các tín hiệu như điện tín, các lệnh điều khiểnlà rời rạc theo thời gian, nguồn tin như thế gọi là nguồn rời rạc (discrete source), các tin đó được gọi là tin rời rạc (discrete information) và kênh tin được gọi là kênh rời rạc (discrete channel). „ Các hệ thống liên tục có nhiều nhược điểm như cồng kềnh, không hiệu quả , và chi phí cao. „ Các hệ thống truyền tin rời rạc có nhiều ưu điểm hơn, khắc phục được những nhược điểm trên của các hệ thống liên tục và đặ c biệt đang ngày càng được phát triển và hoàn thiện dần. Æ Rời rạc hóa các kênh liên tục Truyền và bảo mật thông tin 11 Mô hình quá trình truyền tin „ Rời rạc hóa: Thường một trong hai loại: „ Rời rạc hoá theo trục thời gian, còn được gọi là lấy mẫu (sampling) và rời rạc hoá theo biên độ , còn được gọi là lượng tử hoá (quantize). Lấy mẫu Lượng tử hóa Truyền và bảo mật thông tin 12 Mô hình quá trình truyền tin „ Nguồn tin liên tục sau khi được lấy mẫu và lượng tử hoá sẽ trở thành nguồn rời rạc . „ Chúng ta học chủ yếu các nguồn rời rạc. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 4 Truyền và bảo mật thông tin 13 Mô hình quá trình truyền tin „ Lý thuyết thông tin được xét ở đây theo quan điểm của Shannon. Đối tượng nghiên cứu là một hệ thống liên lạc truyền tin (communication system) như sơ đồ dưới đây: „ Truyền và bảo mật thông tin 14 Lượng tin biết và chưa biết „ Một biến ngẫu nhiên (BNN) X luôn mang một lượng tin nào đó. „ Nếu X chưa xảy ra thì X có một lượng tin chưa biết. „ Nếu X đã xảy ra thì lượng tin về biến X coi như đã biết hoàn toàn. „ Nếu biết thông tin của một BNN X thông qua BNN Y đã xảy ra thì ta có thể nói: chúng ta chỉ biết một phần lượng thông tin của X đó trên cơ sở biết Y. Truyền và bảo mật thông tin 15 Lượng tin biết và chưa biết „ Ta xét ví dụ trò chơi tung một đồng tiền “có đầu hình – không có đầu hình”. „ Tuy nhiên người tổ chức chơi có thể “ăn gian” bằng cách sử dụng 2 đồng tiền “Thật- Giả” khác nhau sau: „ Đồng tiền loại 1 (hay đồng tiền thật): đồng chất có 1 mặt có đầu hình. „ Đồng tiền loại 2 (hay đồng tiền giả ): đồng chất, mỗi mặt đều có 1 đầu hình. „ Mặc dù người tổ chức chơi có thể “ăn gian” nhưng quá trình trao đổi 2 đồng tiền cho nhau là ngẫu nhiêu Truyền và bảo mật thông tin 16 Lượng tin biết và chưa biết „ Ta thử xét một trường hợp sau: nếu người chơi lấy ngẫu nhiên 1 đồng tiền và sau đó thực hiện việc tung đồng tiền đó 2 lần. Qua 2 lần tung đồng tiền, ta đếm được số đầu hình xuất hiện. „ Dựa vào số đầu hình xuất hiện, ta có thể phán đoán được người tổ chức chơi đã lấy được đồng tiền nào. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 5 Truyền và bảo mật thông tin 17 Lượng tin biết và chưa biết „ Chẳng hạn: Nếu số đầu hình đếm được sau 2 lần tưng là 1 thì đồng tiền đã lấy được là đồng tiền thật. Ngược lại nếu số đầu hình đếm được là 2 thì đồng tiền đã lấy được có thể là thật hay cũng có thể là giả. Như vậy, ta đã nhận được một phần thông tin về loại đồng tiền qua số đầu hình đếm được sau 2 lần tung. Truyền và bảo mật thông tin 18 Lượng tin biết và chưa biết „ Dưới đây là một số bảng phân phối của bài toán trên: „ Gọi BNN X về loại đồng tiền (X=1 hoặc 2). „ Khi đó phân phối của X có dạng: Truyền và bảo mật thông tin 19 Lượng tin biết và chưa biết „ Đặt BNN Y là BNN về số đầu hình đếm được sau 2 lần tung. Khi đó ta có thể xác định được phân phối của Y với điều kiện xảy ra của X trong 2 trường hợp sau: Truyền và bảo mật thông tin 20 Bài tập Tìm phân phối của Y? Tính XS X=1 khi Y=2? Nhớ lại: „ Định lý Bayes „ Nếu p(y) > 0 thì: Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 6 Truyền và bảo mật thông tin 21 Định lý cơ sở của kỹ thuật truyền tin „ Trong “ A New Basic of Information Theory (1954)”, Feinstein đã đưa ra định lý sau: “Trên một kênh truyền có nhiễu, người ta luôn có thể thực hiện một phương pháp truyền sao cho đạt được sai số nhỏ hơn sai số cho phép (nhỏ bất kỳ) cho trước đối với kênh truyền.” Truyền và bảo mật thông tin 22 Minh họa kỹ thuật giảm nhiễu „ Giả sử, một thông báo được truyền cần truyền được mã hóa thành dãy số nhị phân (0,1). Giả sử 1 bit truyền trên kênh nhiễu với xác suất ¼ „ Người ta có thể làm giảm sai lầm khi nhận tin bằng cách truyền lặp lại 1 bit với số lẻ lần Ví dụ: truyền lặp lại 3 cho 1 bit cần truyền Truyền và bảo mật thông tin 23 Minh họa kỹ thuật giảm nhiễu „ Sơ đồ truyền tin: Truyền và bảo mật thông tin 24 Minh họa kỹ thuật giảm nhiễu „ Chứng minh, với cách truyền này sai số nhỏ hơn ¼: „ Giả sử Xi xác định giá trị đúng hay sai của bit thứ i: „ Xi =1 nếu bit thứ i nhận được là sai và „ Xi =0 nếu bit thứ i nhận được là đúng. „ Theo giả thiết ban đầu của kênh truyền thì phân phối xác suất của Xi có dạng Bernoulli b(1/4): Xi 1 0 P 3/4 1/4 „ Gọi Y ={X1 + X2 + X3 } là tổng số bit nhận sai sau 3 lần truyền lặp cho 1 bit =>này Y tuân theo phân phối Nhị thức B(p,n), với p=1/4 (xác suất truyền sai một bit) và q =3/4 (xác suất truyền đúng 1 bit) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 7 Truyền và bảo mật thông tin 25 Minh họa kỹ thuật giảm nhiễu Truyền và bảo mật thông tin 26 Chi phí phải trả cho kỹ thuật giảm nhiễu „ Theo cách thức lặp lại như trên, ta có thể giảm sai lầm bao nhiêu cũng được (lặp càng nhiều thì sai càng ít), nhưng thời gian truyền cũng tăng lên và chi phí truyền cũng sẽ tăng theo. Truyền và bảo mật thông tin 27 Khái niệm về dung lượng kênh truyền „ Cần phải xác định một thông số cho truyền tin để đảm bảo sai số chấp nhận được và đồng thời tốc độ truyền cũng không quá chậm. „ Khái niệm “dung lượng” cho phép xác định tốc độ truyền tối đa của mỗi kênh truyền. Do đó, dựa vào dung lượng kênh truyền, người ta có thể chỉ ra tốc độ truyền tin đồng thời với một phương pháp truyền có sai số cho phép. „ Quá trình truyền tin cần có quá trình sinh mã bằng thiết bị sinh mã (Coding device/ Encoder) và quá trình giải mã nhờ thiết bị giải mã (Decoding device/ Decoder) ĐỘ ĐO LƯỢNG TIN Chương II. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 8 Truyền và bảo mật thông tin 29 II.1. Entropy „ Khái niệm entropy „ Entropy là một đại lượng toán học dùng để đo lượng tin không chắc (hay lượng ngẫu nhiên) của một sự kiện hay của phân phối ngẫu nhiên cho trước. Truyền và bảo mật thông tin 30 Entropy của một sự kiện „ Giả sử có một sự kiện A có xác suất xuất hiện là p. Khi đó, ta nói A có một lượng tin không chắc chắn được đo bởi hàm số h(p) với p ⊆ [0,1]. Hàm h(p) được gọi là Entropy nếu nó thoả 2 tiên đề toán học sau: „ Tiên đề 1: h(p) là hàm liên tục không âm và đơn điệu giảm. „ Tiên đề 2: nếu A và B là hai sự kiện độc lập nhau, có xác suất xuất hiện lần lượt là pA và pB. Khi đó, p(A,B) = pA.pB nhưng h(A,B) = h(pA) + h(pB). Truyền và bảo mật thông tin 31 Entropy của một phân phối „ Xét biến ngẫu nhiên X có phân phối: X | x1 x2 x3 xM P | p1 p2 p3 pM „ Nếu gọi Ai là sự kiện X=xi, (i=1,2,3,..) thì Entropy của Ai là: h(Ai)= h(pi) „ Gọi Y=h(X) là hàm ngẫu nhiên của X và nhận các giá trị là dãy các Entropy của các sự kiện X=xi,tức là Y=h(X)={h(p1), h(p2), , h(pn)}. „ Entropy của X chính là kỳ vọng toán học của Y=h(X) có dạng: „ H(X)=H(p1, p2, p3, ,pn) = p1h(p1)+p2h(p2)++pnh(pn). „ Tổng quát: Truyền và bảo mật thông tin 32 Tiên đề 3 Tính chất của Entropy phân phối „ Nếu một chọn lựa được chia làm 2, Entropy gốc phải bằng tổng của các Entropy thành phần, ví dụ: „ Khi đó yêu cầu Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 9 Truyền và bảo mật thông tin 33 Định lý hàm Entropy „ Chỉ có hàm H dạng sau mới thỏa mản tính chất hàm Entropy „ Bổ đề: h(p)=-Clog(p). i n i i ppCXH ∑ = −= 1 log)( Truyền và bảo mật thông tin 34 Định nghĩa Entropy „ Entropy của BNN X „ Entropy của một sự kiện: h(p)=-log(p). (Sử dụng C=1 ) „ Cơ số logarit tương ứng với đơn vị tính, thông dụng „ Cơ số 2 thì đơn vị tính là bit. „ Cơ số 3 thì đơn vị tính là trits. „ Cơ số e thì đơn vị tính là nats. „ Cơ số 10 thì đơn vị tính Hartleys. „ Nếu ta tính đơn vị bit thì „ Khi đó: h(p)=-log2(p) và i n i i ppXH 2 1 log)( ∑ = −= Truyền và bảo mật thông tin 35 Ví dụ „ Xét BNN X co phân bố như sau: „ (quy ước viết log thay cho log2) Truyền và bảo mật thông tin 36 Bài toán về cây tìm kiếm nhị phân „ Giả sử, tìm 1 trong 5 người có tên biết trước sẽ xuất hiện theo phân phối sau: „ Sơ đồ dùng câu hỏi đúng/sai xác định tên: Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 10 Truyền và bảo mật thông tin 37 Bài toán về cây tìm kiếm nhị phân „ Theo sơ đồ trên: „ Để tìm x1, x2, x3 với xác suất tương ứng là 0.2, 0.3, 0.2 ta chỉ cần tốn 2 câu hỏi. „ Để tìm x4, x5 với xác suất tương ứng 0.15, 0.15 thì ta cần 3 câu hỏi. „ Vậy: „ Số câu hỏi trung bình là: 2 x (0,2+0,3+0,2) + 3 x (0,15+0,15) = 2.3 „ Mặt khác: Entropy của X: H(X)= H(0.2, 0.3, 0.2, 0.15, 0.15)=2.27. „ Vì số câu hỏi trung bình trong trường hợp này xấp xỉ H(X) nên đây là số câu hỏi trung bình tối ưu Truyền và bảo mật thông tin 38 Bài tập Truyền và bảo mật thông tin 39 II.2. Các tính chất của Entropy „ Các tính chất cơ bản Truyền và bảo mật thông tin 40 Các tính chất cơ bản Minh họa tính chất 1: „ Trong trường hợp BNN X có phân bố đều „ Vậy H(X)=-log(1/M)=logM là hàm đơn điệu tăng Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 11 Truyền và bảo mật thông tin 41 Các tính chất cơ bản của Entropy „ Minh họa tính chất 2: „ Trong trường hợp 2 biến ngẫu nhiên X, Y độc lập có phân phối đều với BNN X có M sự kiện và BNN Y có L sự kiện. „ Gọi f(M), f(L) lần lượt là Entropy của X, của Y. Theo tính chất 2 của Entropy ta có „ f(ML)=f(M)+f(L) Truyền và bảo mật thông tin 42 Các tính chất cơ bản của Entropy Minh họa tính chất 3: Xét con xúc sắc 6 mặt với phân bố XS: Nếu ta gom sự kiện x1,x2,x3 thành sự kiện x123 (XS 55%) và x5, x6 thành x56 (XS 20%), ta có bảnh phân bố X*: Kiểm tra: H(X) =H(p1+p2+p3, p4 , p5+p6) (BT cho SV) Truyền và bảo mật thông tin 43 Định lý cực đại của entropy „ Định lý: H(p1, p2, ,pM)≤ log(M) Trong đó: đẳng thức xảy ra khi và chỉ khi p1== pM= 1/M „ Chứng minh „ Bổ đề: cho 2 bộ {p1, p2, ,pM} và {q1, q2,,qM} là các bộ số dương bất kỳ và Khi đó ta có Đẳng thức xảy ra khi pi=qi với∀i=1,..,M. Truyền và bảo mật thông tin 44 Định lý cực đại của entropy „ Chứng minh bổ đề „ Theo toán học ta có thể chứng minh ln(x)≤ x-1 với x>0 và đẳng thức đúng khi x=1. „ Đặt x= qi/pi Suy ra ln(qi/pi)≤ qi/pi –1 (và đẳng thức đúng khi qi=pi với mọi i). Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 12 Truyền và bảo mật thông tin 45 Định lý cực đại của entropy „ Mặt khác lnx = log2x / log2e (2) „ Từ (1) và (2)=> „ Đẳng thức xảy ra khi pi=qi với mọi i Truyền và bảo mật thông tin 46 Định lý cực đại của entropy „ Chứng minh định lý „ Lấy qi=1/M, từ bổ đề ta có: „ Đẳng thức xãy ra khi pi=1/M với mọi i đpcm Truyền và bảo mật thông tin 47 II.3. Entropy của nhiều biến Định nghĩa: Giả sử X và Y là 2 biến ngẫu nhiên cho trước với pịj = p(X=xi,Y=yj) (∀ i=1,..,M và j=1,,L). „ Khi đó, Entropy H(X,Y) có dạng: „ Tổng quát Truyền và bảo mật thông tin 48 Ví dụ Entropy của nhiều biến „ Cho 2 BNN X và Y độc lập nhau và có các phân phối: „ Lập phân phối của P(X,Y) „ H(X,Y) =H(0.125, 0.25, 0.125, 0.125, 0.25, 0.125)=2.5 (Bit) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 13 Truyền và bảo mật thông tin 49 Entropy có điều kiện „ Entropy của Y với điều kiện X=xi (i=1,..,M) được định nghĩa là: „ Entropy của Y với điều kiện X xảy ra được định nghĩa là: Truyền và bảo mật thông tin 50 Ví dụ Entropy có điều kiện „ Xét biến ngẫu nhiên X và biến ngẫu nhiên Y có tương quan nhau, các phân phối: „ Entropy của Y/X=1 và Y/X=2 như sau : „ H(Y/X=1)=H(0.25, 0.5 , 0.25)= -0.25 log0.25 –0.5log0.5-0.25 log0.25 =0.5 + 0.5 + 0.5= 1.5 (Bit) „ H(Y/X=2)= H(0; 0; 1)= 0 (Bit) „ Entropy của Y khi X xảy ra: H(Y/X)=P(X=1) H(Y/X=1)+ P(X=2) H(Y/X=2)=(0.5x1.5) + (0.5x0)=0.75 (Bit). Truyền và bảo mật thông tin 51 Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập Định lý 1: H(X,Y)≤ H(X)+H(Y) và đẳng thức xảy ra khi X, Y độc lập Hệ quả: „ H(X1, , Xn) ≤ H(X1)++H(Xn) „ H(X1,Xn; Y1,,Yn) ≤ H(X1,Xn)+ H(Y1,,Yn) Truyền và bảo mật thông tin 52 Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập Chứng minh định lý 1: „ Ta có Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 14 Truyền và bảo mật thông tin 53 Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độc lập „ Đặt qij =p(xi)p(yj)=> qij >=p(xi, yj) „ Đẳng thức xảy ra khi p(xi, yj)=pij =qij =p(xi)p(yj) hay X , Y độc lập nhau (theo bổ đề định lý cực đại). „ Mặt khác „ Từ (1) và (2) => H(X,Y)≤ H(X)+H(Y) và đẳng thức xảy ra khi X, Y độc lập (đpcm) Truyền và bảo mật thông tin 54 Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y tương quan Định lý 2: H(X,Y)=H(X)+H(Y/X)=H(Y)+H(X/Y). Định lý 3: H(Y/X)≤ H(Y) và Dấu đẳng thức xảy ra khi và chỉ khi X và Y độc lập nhau. Truyền và bảo mật thông tin 55 Chứng minh định lý 2 Tương tự ta có: H(X,Y)=H(Y)+H(X/Y) Truyền và bảo mật thông tin 56 Chứng minh định lý 3 Từ định lý 1: H(X,Y)≤ H(X)+H(Y) Từ định lý 2: H(X,Y)=H(X)+H(Y/X) ⇒H(X)+H(Y/X)≤ H(X)+ H(Y) ⇒H(Y/X) ≤ H(Y). Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 15 Truyền và bảo mật thông tin 57 Bài tập Truyền và bảo mật thông tin 58 II.4. Đo lượng tin (mesure of information) „ Ta xét ví dụ trò chơi tung một đồng tiền “có đầu hình – không có đầu hình”. „ Tuy nhiên người tổ chức chơi có thể “ăn gian” bằng cách sử dụng 2 đồng tiền “Thật- Giả” khác nhau sau: „ Đồng tiền loại 1 (hay đồng tiền thật): đồng chất có 1 mặt có đầu hình. „ Đồng tiền loại 2 (hay đồng tiền giả ): đồng chất, mỗi mặt đều có 1 đầu hình. „ Mặc dù người tổ chức chơi có thể “ăn gian” nhưng quá trình trao đổi 2 đồng tiền cho nhau là ngẫu nhiêu Truyền và bảo mật thông tin 59 Các bảng phân phối của bài toán trên: „ Gọi BNN X về loại đồng tiền (X=1 hoặc 2). „ Đặt BNN Y là BNN về số đầu hình đếm được sau 2 lần tung „ Khi đó ta có các bảng phân phối: „ Ta có thể tính dễ dàng phân phối của Y như sau: Truyền và bảo mật thông tin 60 Nhận xét dựa theo entropy Từ các bảng phân phối trên, ta có: „ Entropy của Y: H(Y) = H(0.125, 0.25, 0.625) = 1.3 (bit) „ Entropy của Y khi biết X H(Y/X=1) = H(0.25, 0.5 , 0.25)= 1.5 (bit) H(Y/X=2)= H(0, 0, 1)= 0 H(Y/X)= p(X=1)H(Y/X=1)+ p(X=2)H(Y/X=2) = 0.75 (bit) „ Vậy, H(Y) > H(Y/X) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 16 Truyền và bảo mật thông tin 61 Định nghĩa lượng tin Định nghĩa: Lượng tin (hay thông lượng) của X khi Y xảy ra là lượng chênh lệch giữa lượng không chắc chắn của X và lượng không chắc chắn của X khi Y xảy ra có quan hệ với X. „ Ký hiệu: I(X/Y) = H(X)-H(X/Y) là lượng tin đã biết về X khi Y đã xảy ra. „ Chú ý: ta luôn có I(X/Y) = I(Y/X) „ Ta có thể hiểu khái niệm này như sau: „ X và Y là 2 biến ngẫu nhiên nên chúng có 2 lượng tin không chắc chắn. Nếu X và Y độc lập, thì X xảy ra không ảnh hưởng tới Y nên ta vẫn không biết gì thêm về X và X giữ nguyên lượng không chắc chắn của nó. Trong trường hợp này lượng tin về X khi Y xảy ra là bằng 0. „ Nếu Y có tương quan với X thì khi Y xảy ra ta biết hoàn toàn về Y và một phần thông tin về X. Phần thông tin đó chính là lượng tin đã biết về X nhưng vẫn chưa biết hết về X. Bài toán ở đây là tính lượng tin đã biết về X khi Y xảy ra. Truyền và bảo mật thông tin 62 Ví dụ lượng tin „ Xét lại ví dụ trên, ta có lượng tin về X khi biết Y là „ I(X/Y)= I(Y/X)= H(Y) – H(Y/X) = 1.3 – 0.75=0.55 (bit). Truyền và bảo mật thông tin 63 Bài tập „ Thực hiện một phép thử con xúc sắc đồng chất đồng thời với một đồng tiền cũng đồng chất. Trong đó, con xúc sắc có các mặt điểm từ 1 đến 6, đồng tiền một mặt có đầu hình và mặt kia không có đầu hình. Trước tiên thử con xúc sắc, nếu số điểm ≤ 4 thì tung đồng tiền một lần, ngược lại thì tung đồng tiền hai lần. Tính lượng tin về số điểm con xúc sắc khi biết thông tin về số đầu hình đếm được. Truyền và bảo mật thông tin 64 Bài tập „ Có hai chiếc hộp đựng bi, hộp thứ nhất chứa hai bi đỏ, một bi vàng, một bi xanh. Hộp thứ hai chứa một bi vàng và một bi xanh. Lấy ngẫu nhiên một viên bi trong hộp thứ nhất bỏ vào hộp thứ hai, sau đó lấy ngẫu nhiên một viên bi từ hộp thứ hai. Hãy tính lượng tin về màu viên bi bốc được trong hộp thứ nhất khi biết thông tin về màu sắc viên bi bốc được trong hộp thứ hai. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 17 Truyền và bảo mật thông tin 65 Bài tập „ An và Bình hẹn gặp nhau. Nếu trời không mưa thì khã năng An đến điểm hẹn là 90% còn Bình là 60%. Nếu trời mưa thì khã năng An đến điểm hẹn là 30% còn Bình là 40%. Giả sử thời tiết chổ An và Bình là như nhau và xác suất mưa sẽ là 60%. Hãy tìm lượng tin về thời tiết khi biết số lượng người đến điểm hẹn SINH Mà TÁCH ĐƯỢC Chương III. Truyền và bảo mật thông tin 67 III.1. Khái niệm về mã tách được Đặt vấn đề bài toán sinh m㠄 Giả sử nguồn tin X xuất hiện và được ghi lại thông qua một thiết bị đặc biệt. Chẳng hạn như ảnh được ghi lại bằng máy ảnh, âm thanh được ghi lại bằng máy ghi âm, Qua kênh truyền, những thông tin này cần phải được mã hóa cho phù hợp. Để có thể mã hóa người ta cần một bảng chữ cái gồm các chữ cái quy định trước (chẳng hạn bảng chữ cái la tinh, bảng mã nhị phân, ). Mỗi giá trị của X sau đó được mã dưới dạng một dãy hữu hạn các chữ cái và ta gọi dãy hữu hạn các chữ cái gán cho một giá trị của x là một từ mã. Truyền và bảo mật thông tin 68 III.1. Khái niệm về mã tách được „ Ta xét BNN X={x1, x2, ,xn} có phân phối {p1, p2, , pn} được quan sát liên tục và độc lập. „ Dãy các giá trị nhận được gọi là thông báo (Message) có dạng xi1xi2xim. „ Tập hợp A={a1, a2, , aD} là tập hợp ký tự mã (Code Characters) hay là bảng chữ cái (Code Alphabet) dùng để sinh mã. „ Một giá trị xi∈ X được gán bởi một dãy hữu hạn các ký tự mã được gọi là từ mã (Code word). „ Tập hợp gồm tất cả các từ mã gán cho tất cả các giá trị của X được gọi là bộ mã hay bảng mã (Code). „ Các từ mã phải khác nhau từng đôi một. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 18 Truyền và bảo mật thông tin 69 III.1. Khái niệm về mã tách được „ Bộ mã được gọi là tách được (Decypherable Coding) nếu như từ một dãy các ký tự mã nhận được liên tục (được mã hóa từ bộ mã này), ta luôn luôn giải mã được với kết quả duy nhất là dãy các giá trị gốc của X. Truyền và bảo mật thông tin 70 Khái niệm về bảng mã không tách được „ Bảng mã không tách được là bảng mã mà khi mã hóa thông báo Msg ta sẽ nhận được một dãy các từ mã ws, và khi giải mã dãy các từ mã ws thì ta có thể nhận được nhiều thông báo Msg khác nhau. „ Ví dụ: Xét biến ngẫu nhiên X={x1, x2, x3, x4} có bảng mã W={w1=0, w2=1, w3=01, w4=10}. „ Giả sử thông báo nguồn có nội dung: x2x3x4x3x2x1. Khi đó dãy mã tương ứng viết từW: 101100110. „ Nếu giải mã từ trái qua phải: x2x1x2x2x1x1x2x2x1. „ Nếu giải mã từ phải qua trái, ưu tiên độ dài lớn : x2x3x4x3x4 „ Nếu giải mã từ trái qua phải, ưu tiên độ dài lớn x4x2x4x3x4 Truyền và bảo mật thông tin 71 Ví dụ bảng mã tách được „ Xét biến ngẫu nhiên X={x1, x2} có bảng mã tương ứng W={w1=0, w2=01}. Phương pháp giải mã được sử dụng như sau: chỉ giải mã khi nào đã nhận được đoạn mã với độ dài bằng độ dài của từ mã dài nhất. „ Giả sử dãy mã nhận được là: 0010000101001. „ Sử dụng phương pháp giải mã trên ta nhận được duy nhất dãy thông báo gốc: x1x2x1x1x1x2x2x1x2. „ Nhận xét: Bảng mã tách được là bảng mã mà trong đó không tồn lại từ mã này là mã khóa từ mã khác, tuy nhiên vẫn có thể tồn tại từ mã này là tiền tố (phần đầu) của từ mã kia. Truyền và bảo mật thông tin 72 Giải thuật kiểm tra tính tách được của bảng mã (Sardinas, Patterson và Abramson) „ Bước khởi tạo: Gán tập hợp S0=W. „ Bước 1: xác định tập hợp S1 từ S0: „ - Khởi tạo S1={} „ - Với∀ wi, wj∈ S0, ta xét: nếu wi=wjA (wj là tiền tố của wi) hoặc wj=wi A (wi là tiền tố của wj) thì thêm A (phần hậu tố) vào S1. „ Bước k: xác định tập hợp Sk (k≥2) từ tập hợp S0 và Sk-1: „ - Khởi tạo: Sk={} „ - Với∀ wi∈ S0 và ∀ vj∈Sk-1, ta xét: nếu wi=vjA (vj là tiền tố của wi) hoặc vj=wi A thì thêm A vào Sk. „ Điều kiện để dừng vòng lặp: „ Nếu Sk={} thì dừng và kết luận bảng mã tách được (k≥1). „ Nếu tồn tại từ mã wi trong Sk hay Sk ∩S0 ≠ ∅ thì dừng và kết luận bảng mã không tách được. „ Nếu Sk=St<k thì dừng và kết luận bảng mã tách được (k≥1). Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 19 Truyền và bảo mật thông tin 73 Bảng mã prefix „ Bảng mã prefix là bảng mã không tồn tại từ mã này là tiền tố của từ mã khác. „ Ví dụ 1: Bảng mã W={w1=10; w2=101; w3=100} không phải bảng mã prefix vì w1 là tiền tố của w2 và w3. „ Ví dụ 2: Bảng mã W={w1=0, w2=100, w3=101, w4=11} là bảng mã prefix vì không tồn tại từ mã này là tiền tố của từ mã khác. „ Bảng mã prefix luôn là bảng mã tách được Truyền và bảo mật thông tin 74 III.2. Quan hệ giữa mã tách được và độ dài mã Định lý Kraft „ Gọi X={x1, x2,, xM} là biến ngẫu nhiên chứa các giá trị cần truyền có phân phối là P={p1, p2, , pM}. „ A={a1, a2,,aD} là bộ ký tự sinh mã có D chữ cái (D được gọi là cơ số sinh mã). „ Giá trị xi được mã hóa thành từ mã wi có độ dài là ni. „ Đặt N={n1, n2,,nM} là tập hợp độ dài các từ mã. „ Phát biểu định lý Kraft: Điều kiện cần và đủ để tồn tại bảng mã prefix với độ dài N={n1, n2,,nM} là: Truyền và bảo mật thông tin 75 Minh họa định lý Kraft „ Ví dụ 1: Bộ mã W={w1, w2, w3} với M=3; n1=1; n2=2; n3=3; D=2: Î Tồn tại bảng mã prefix „ Ví dụ 2: Bộ mã W={w1, w2, w3} với M=3; n1=1; n2=1; n3=2; D=2: Î Không tồn tại bảng mã prefix Truyền và bảo mật thông tin 76 Cây bậc D cỡ k. Định nghĩa: Cây bậc D cỡ k là cây có hệ thống nút, cạnh thỏa điều kiện: „ Từ 1 nút có số cạnh đi ra không vượt quá D hay một nút có không quá D nút con. „ Nút cuối cùng (Nút lá) cách nút gốc không vượt quá k cạnh. Cây bậc D=2 cở k=3 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 20 Truyền và bảo mật thông tin 77 Sinh mã cho các nút của cây bậc D cỡ K „ Để đơn giản hóa: mỗi nút (trừ nút gốc) được ký hiệu bởi dãy ký hiệu của nút cha làm tiền tố + một ký tự bổ sung lấy từ tập hợp {0, 1, 2, , D-1} thay cho bảng chữ cái A={a1, a2, , aD}. Truyền và bảo mật thông tin 78 Sinh mã cho các nút của cây bậc D cỡ K Tính chất: „ Các nút (trừ nút gốc) của cây đều được mã hóa từ bảng chữ cái {0, 1, 2,, D-1} „ Mỗi nút (đã mã hóa) có mã của nút kề trước là tiền tố. „ Tổng số các nút lá bằng Dk Truyền và bảo mật thông tin 79 Thủ tục tạo mã prefix: „ Xét N={n1, n2, ,nM} và cơ số sinh mã là D: „ Bước 1: Ta xếp thứ tự n1≤ n2 ≤ ≤ nM, xây dựng cây bậc D cỡ k=nM và sinh mã cho các nút . „ Bước 2: Chọn nút bất kỳ trên cây có độ dài n1 gán cho từ mã w1 và xóa tất cả các nút kề sau nó. „ Bước 3: Lặp lại các bước 2 đối với việc chọn các từ mã còn lại w2, , wM ứng với n2, , nM. => Bảng mã W={w1, w2, , wM} là bảng mã prefix. Truyền và bảo mật thông tin 80 Ví dụ tạo mã prefix: „ Xét bảng mã thỏa M=3, D=2, n1=1, n2=2, n3=3. + Kiểm tra: + Sinh mã cho nút + Chọn mã: • Chọn w1=0 , cắt bỏ các nút con của nút w1. • Chọn w2=10, cắt bỏ các nút con của nút w2. • Chọn w3=111 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 21 Truyền và bảo mật thông tin 81 III.3. Tính tối ưu của độ dài mã Định lý Shannon )Nếu mã tách được không tối ưu thì độ dài của nó sẽ lớn hơn nhiều so với cận dưới, còn nếu mã tách được tối ưu thì độ dài trung bình của nó gần với cận dưới. Truyền và bảo mật thông tin 82 Bảng mã tối ưu tuyệt đối/ tương đối „ Bảng mã được gọi là tối ưu tuyệt đối khi „ Bảng mã tối ưu tương đối khi: Truyền và bảo mật thông tin 83 Bảng mã tối ưu tuyệt đối/ tương đối Ví dụ: xét biến ngẫu nhiên X={x1, x2, x3, x4} „ Có phân phối: P={1/2, 1/4, 1/8, 1/8} „ Có bảng mã W={w1=0,w2=10,w3=110, w4=111} „ Độ dài trung bình từ mã: „ Entropy của X: H(X)= H(0.5, 0.25, 0.125, 0.125) = 0.5 +0.5 + 0.375 + 0.375 =1.75 „ Log2D=1. „ Ta có: =>Bảng mã tối ưu tuyệt đối Truyền và bảo mật thông tin 84 Điều kiện nhận biết một bảng mã tối ưu „ Định lý (với D=2): „ Xác suất pi càng lớn thì độ dài ni của từ mã wi càng nhỏ. „ Giả sử p1≥ p2 ≥ ≥ pM thì 2 từ mã tương ứng với 2 giá trị có xác suất nhỏ nhất có độ dài mã bằng nhau: nM-1 =nM. „ Trong các từ mã có độ dài bằng nhau và cùng bằng nM (dài nhất) thì tồn tại ít nhất 2 từ mã có M-1 ký tự đầu giống nhau và ký tự thứ M khác nhau. „ Ví dụ, xét bảng mã: W={w1=0, w2=100, w3=101, w4=1101, w5=1110} Bảng mã trên không phải là bảng mã tối ưu vì 2 từ mã w4, w5 có độ dài lớn nhất =4 ký tự nhưng 3 ký tự đầu khác nhau. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 22 Truyền và bảo mật thông tin 85 Phương pháp sinh mã Huffman Định lý Huffman „ Giả sử X có phân phối xác suất với thứ tự giảm dần sau: X | x1 x2 xM P | p1≥ p2 ≥ ≥ pM „ Giả sử bảng mã của X là W={w1, w2, , wM-1, wM}. „ Đặt xM-1,M={xM-1, xM} có xác suất là pM-1,M=pM-1+pM. và X* = { x1, x2,, xM- 1,M} có phân phối sau: X* | x1 x2 xM-2 xM-1,M P | p1 p2 pM-2 pM-1,M „ Giả sửW* ={w*1, w*2, , w*M-2, w*M-1,M} là bảng mã tối ưu của X*. Khi mã nhận được theo quy tắc sau là mã tối ưu cho X đó: „ wi=w*i với 1 ≤ i ≤ M-2 „ wM-1=w*M-1,M + “0”. „ wM =w*M-1,M + “1”. Truyền và bảo mật thông tin 86 Phương pháp sinh mã Huffman Phương pháp sinh mã Huffman với D=2: „ Giả sử X có phân phối xác suất với thứ tự giảm dần sau: X | x1 x2 xM P | p1≥ p2 ≥ ≥ pM „ Khởi tạo: Đặt M0=M „ Bước 1: „ Đặt xMo-1, Mo={xMo-1,xMo } „ Sắp xếp lại theo thứ tự giảm dần XS ta được dãy phân phối mới có M0- 1 phần tử p1, p2,pMo-2, PMo-1, Mo „ Bước 2: „ Lưu vết: wMo-1 = wMo-1, Mo + “0” wMo = wMo-1, Mo + “1” „ Giảm M0: M0=M0-1, nếu M0<=2 thì kết thúc, nếu không quay lại bước 1 Truyền và bảo mật thông tin 87 Ví dụ phương pháp sinh mã Huffman „ Hãy mã hoá nguồn S = {x1, x2, x3, x4, x5, x6} với các xác suất pi lần lượt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05 Bài tập: tínhvà so sánh: và Truyền và bảo mật thông tin 88 Bài tập „ Lập bảng mã nhị phân Huffman cho các phân phối sau: „ Lập bảng mã nhị phân Huffman dùng để mã hóa đoạn văn bản: “thoi the thi thoi thi the thoi thi thoi the” Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 23 KÊNH TRUYỀN Chương IV. Truyền và bảo mật thông tin 90 IV.1. Kênh truyền rời rạc không nhớ Khái niệm kênh truyền rời rạc không nhớ „ Kênh truyền rời rạc: truyền tuần tự các ký tự độc lập nhau (hay truyền từng ký tự một), „ “Không nhớ” ở đây là chỉ xét mối quan hệ giữa ký tự truyền và ký tự nhận được tương ứng, không xét đến mối quan hệ giữa ký tự nhận được với ký tự nhận được trước đó. Truyền và bảo mật thông tin 91 Mô hình vật lý Các qui ước: „ - X: là biến ngẫu nhiên có giá trị cần truyền ở đầu truyền. „ - Y: là biến ngẫu nhiên chứa giá trị có thể nhận được ở đầu nhận. „ - ΓX: là bảng chữ cái sinh mã ở đầu truyền. „ - ΓY: là bảng chữ cái giải mã ở đầu nhận. „ - X, Y, ΓX, ΓY: đều hữu hạn và rời rạc. „ - Truyền rời rạc từng ký tự và nhận cũng rời rạc từng ký tự. „ - Ký tự nhận sau không phụ thuộc vào ký tự nhận trước. Truyền và bảo mật thông tin 92 Mô hình toán học „ Ta gọi: „ ΓX={x1, x2, , xM} là bộ ký tự sinh mã ở đầu truyền (input). „ ΓY={y1, y2,,yL} là bộ ký tự giải mã ở đầu nhận (output). „ Biến ngẫu nhiên X lấy giá trị (đã mã hóa) trên ΓX và có phân phối p(X=xi)=p(xi) với i=1,..,M. „ Biến ngẫu nhiên Y lấy giá trị (giải mã) trên ΓY và có phân phối xác suất có điều kiện: „ P(Y=yj|X=xi)=p(yj/xi)=pij với j=1,..,L. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 24 Truyền và bảo mật thông tin 93 Mô hình toán học „ Gọi A=[pij] là ma trận truyền tin hay mô hình truyền tin của kênh truyền rời rạc không nhớ. „ Với i=1,,M , j=1,,L và pij = p(Y=yj/X=xi) = p(yj/xi) là XS nhận được giá trị yj khi đã truyền giá trị xi. „ Tính phân phối đầu nhận: Truyền và bảo mật thông tin 94 Mô hình toán học „ Tính phân phối đầu nhận: „ Vậy p(yj)= P’X.Aj (1) „ Tổng quát: P’Y = P’X.A (2) „ Trong đó „ - Aj là cột thứ j của A „ - P’X = [p(x1), p(x2),., p(xM)]. „ - P’Y = [p(y1), p(y2),., p(yM)]. Truyền và bảo mật thông tin 95 Ví dụ xác định phân phối đầu nhận „ Cho ma trận truyền tin: „ Xác suất truyền: p(x1)=0.5 và p(x2)=p(x3)= 0.25. „ Ta tìm phân phối của Y : „ Ta có: P’X =(0.5, 0.25, 0.25) „ Áp dụng công thức (1) ở trên ta được: „ p(y1) = P’x .A1 = 0.5*0.5+ 0.25*0.3+0.25*0.2 =0.375 „ p(y2) = P’x.A2 = 0.5*0.2+ 0.25*0.5+0.25*0.3= 0.3 „ p(y3) = P’x .A3 = 0.325 ⇒ P’Y =(0.375, 0.3, 0.325) Truyền và bảo mật thông tin 96 Lượng tin trên kênh truyền Xét ma trận truyền tin như trên „ Ta có: „ P’X =(0.5, 0.25, 0.25) „ P’Y =(0.375, 0.3, 0.325) „ Tính các Entropy: „ H(Y) = H(0.375, 0.3, 0.325) = 1.58 (bit) „ H(Y/X=x1) = H(0.5, 0.2, 0.3)= 1.49 (bit) „ H(Y/X=x2) = H(0.3, 0.5, 0.2)= 1.49 (bit) „ H(Y/X=x3) = H(0.2, 0.3, 0.5)= 1.49 (bit) „ H(Y/X)=p(x1).H(Y/X=x1)+p(x2).H(Y/X=x2)+p(x3).H(Y/X=x3) = 1.49 (bit) „ Lượng thông tin truyền trên kênh: I (X/Y)= I (Y/X)= H(Y) - H(Y/X) = 0,09 (bit) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 25 Truyền và bảo mật thông tin 97 Định nghĩa dung lượng kênh truyền „ Dựa vào ma trận truyền tin A, ta có thể dễ dàng tính lượng tin trên kênh truyền. „ I(X/Y)= H(X)-H(Y/X) = H(Y)-H(X/Y) = I(Y/X) „ Ta có I(X/Y)= H(Y)-H(Y/X), trong đó: „ H(Y)= H(P’X .A) phụ thuộc vào PX. „ H(Y/X) phụ thuộc vào PX „ Vậy: I(Y/X) phụ thuộc hoàn toàn vào PX và do đó I(Y/X) có thể đạt Max với PX xác định nào đó. „ Ta định nghĩa dung lượng kênh truyền (bit) là Truyền và bảo mật thông tin 98 IV.2. Các dạng kênh truyền Kênh truyền không mất tin „ Mô hình: từ tập hợp các giá trị có thể nhận được ở đầu nhận Y={y1, y2, , yL} được phân thành M nhóm Bi tương ứng với các giá trị xi ở đầu truyền và xác suất để truyền xi với điều kiện đã nhận yj là p(X= xi/Y=yj∈Bi)=1 ( với M < L ). Truyền và bảo mật thông tin 99 Kênh truyền không mất tin „ Đặc trưng: H(X/Y)=0 Æ biết Y thì biết X =>I(X/Y)=H(X)=> C=log2M Truyền và bảo mật thông tin 100 Kênh truyền xác định „ Mô hình: từ tập hợp các giá trị có thể truyền ở đầu truyền được phân thành L nhóm Bj tương ứng với các giá trị có thể nhận được yj ở đầu nhận và xác suất để nhận yj với điều kiện đã truyền xi là p(Y=yj /X=xi ∈Bj )=1 (M>L). Đặc trưng: H(Y/X)=0. Có nghĩa là lượng tin chưa biết về Y khi truyền X bằng 0 hay khi truyền X thì ta biết sẽ nhận được Y. =>C=log2L Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 26 Truyền và bảo mật thông tin 101 Kênh truyền không nhiễu „ Mô hình: là sự kết hợp của kênh truyền xác định và kênh truyền không mất thông tin, truyền nào sẽ nhận được đúng ký tự đó. Đầu truyền Đầu nhận x1 Æ x1 x2 Æ x2 xM Æ xM „ Đặc trưng: H(X/Y)=H(Y/X)=0 „ Dung lượng: C=log2L=log2M Truyền và bảo mật thông tin 102 Kênh truyền không sử dụng được. „ Mô hình: Là kênh truyền mà giá trị đầu nhận luôn độc lập với giá trị đầu truyền, với mọi phân bố xác suất đầu truyền. „ Đặc trưng: H(X/Y) =H(X); H(Y/X)= H(Y) „ Dung lượng: C=0 „ Ví dụ Truyền và bảo mật thông tin 103 Kênh truyền đối xứng „ Mô hình: là kênh truyền mà ma trận truyền tin có đặc điểm sau: „ Mỗi dòng của ma trận A là một hoán vị của phân phối P={p’1, p’2, , p’L} „ Mỗi cột của ma trận A là một hoán vị của Q={q’1, q’2, , q’M} „ Ví dụ: Truyền và bảo mật thông tin 104 Dung lượng kênh truyền đối xứng „ Xác định C=Max(I(X/Y))=Max(H(Y)-H(Y/X)) „ H(Y/X)= Æ j L j ji M i iii M i i ppxYHxxYHxYHx 'log'),()/()/( 111 ∑∑∑ === −=== Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 27 Truyền và bảo mật thông tin 105 Kênh truyền đối xứng „ Chú ý: trường hợp kênh 1 bit với nhiễu β „ Ma trận truyền tin: „ Dung lượng: „ C =1+(1-β)log(1-β)+βlogβ = 1- H(β, 1-β) 0.5 1 β C 1 Truyền và bảo mật thông tin 106 IV.3. Lược đồ giải mã Đặt vấn đề bài toán giải m㠄 Phân tích yêu cầu giải mã: „ Khi truyền giá trị xi, ta sẽ nhận được yj. Đối với kênh truyền không nhiễu thì yj chính là xi. Đối với kênh truyền có nhiễu thì yj có thể khác xi. Do đó ta cần tìm cách giải mã yj về giá trị xi khi kênh truyền có nhiễu. „ Phép phân hoạch các giá trị ở đầu nhận: „ Phép phân hoạch tập các giá trị ở đầu nhập yj∈ Y là phép phân chia tập Y thành các tập con Bi sao cho: Truyền và bảo mật thông tin 107 Ví dụ bài toán giải m㠄 Cho tập các từ mã truyền X và tập các dãy n bit nhận được Y như sau „ X={0000, 0101, 1110, 1011} „ Y={0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, „ 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} „ Giả sử ta có thể phân hoạch tập Y thành các tập con Bi như sau: „ B1={0000, 1000, 0001, 0010} „ B2={0101, 1101, 0100, 0111} „ B3={1110, 0110, 1111, 1100} „ B4={1011, 0011, 1010, 1001} „ Giả sử nhận yj = 0011 thì giải mã về x4 = 1011 vì yj∈ B4. Truyền và bảo mật thông tin 108 Sơ đồ truyền tin „ Nguồn phát tín hiệu (hay thông báo) với vận tốc R (tín hiệu/giây). „ Tín hiệu được mã hóa từ bộ ký tự mã. „ Tín hiệu mã hóa được truyền trên kênh với vận tốc V (ký tự/giây) „ Tín hiệu truyền trên kênh có thể bị nhiễu với xác suất P(e). „ Trước khi nhận, tín hiệu mã hóa được giải mã theo một phương thức tối ưu và độ chính xác cao nhất có thể có. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 28 Truyền và bảo mật thông tin 109 Sơ đồ truyền tin „ Bài toán đặt ra ở đây: tìm giải pháp tạo mã sao cho sai số đầu nhận có xác suất nhỏ hơn ε bất kỳ „ (ε < P(e)) đồng thời với đồng bộ hóa: vận tốc phát thông báo ở nguồn R và vận tốc truyền tải ≤ V Truyền và bảo mật thông tin 110 Ví dụ „ Giả sử kênh truyền từng bit với V=1 bit/s, nguồn phát thông báo với tốc độ R=2/5 bit/s (R<V). „ Xét từng khoảng n = 5 giây. „ Tập hợp các tín hiệu khác nhau là 2nR = 4. „ Giả sử 4 tín hiệu là m1, m2, m3, m4. „ Số bit được phát ra là nR=2 bit và một tín hiệu dạng mi được kết cấu bởi một dãy các bit. „ Quá trình mã hóa các tín hiệu m1, m2, m3, m4 cần chú ý là: mỗi mi cần được mã hóa với số bit tối đa là nV=5 bit. Trong 5bit dùng 2 bit mã hóa tín hiệu và 3 bit sửa lỗi Truyền và bảo mật thông tin 111 Các khái niệm cơ bản: „ Từ mã: là dãy n ký tự truyền hay dãy n ký tự nhận đúng. „ Bộ mã (S,n): là tập hợp gồm S từ mã với độ dài mỗi từ mã đều bằng n và được ký hiệu là x(1), , x(s). „ Lược đồ giải mã: là một hàm gán cho một dãy n ký tự nhận được yj một từ mã của bộ mã W ={w1, w2, , ws}. Ký hiệu: g(yj) = wi „ Lược đồ giải mã tối ưu: là lược đồ giải mã sao cho tổng xác suất truyền sai là nhỏ nhất hay tổng xác suất truyền đúng là lớn nhất. Nghĩa là: khi nhận yj thì ta giải mã về w*I sao cho: P(wi*/yj) = Max{P(wk/yj)} ∀wk∈W Truyền và bảo mật thông tin 112 Các dạng sai số cơ bản Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 29 Truyền và bảo mật thông tin 113 Phương pháp xây dựng lượt đồ giải mã tối ưu „ Theo công thức Bayes: Ta có: P(wk/yj) = (p(wk).p(yj/wk)) / p(yj) với (∀wk∈W) „ Từ định nghĩa lược đồ giải mã tối ưu: ⇒ tìm wk sao cho P(wk/yj) → Max ⇔ p(wk).p(yj/wk) → Max. Phương pháp xây dựng lược đồ tối ưu „ Bước 0: Khởi tạo các Bi = φ (∀i) „ Bước lặp: xét với mọi yj∈Y + Tính: p(w1).p(yj/w1) ; p(w2).p(yj/w2); ; p(wM).p(yj/wM) + So sánh các giá trị tính trên và chọn giá trị w*i sao cho p(w*i).p(yj/w*i)= Max {p(wk).p(yj/wk)} (∀wk∈W) + Bi = Bi + {yj} và g(yj) = w*i. Truyền và bảo mật thông tin 114 Minh họa xây dựng lược đồ giải mã tối ưu „ Cho ma trận truyền tin A và xác suất ở đầu truyền như sau: „ Với p(x1)=1/2; p(x2)=p(x3)=1/4. „ Hãy xây dựng lược đồ giải mã tối ưu. Truyền và bảo mật thông tin 115 Minh họa xây dựng lược đồ giải mã tối ưu Xây dựng lược đồ giải mã tối ưu: „ Bước 0: B1={}; B2={}; B3={}; „ Bước 1: Xét y1, ta tính: p(x1).p(y1/x1)= 1/2.1/2 = ¼; p(x2).p(y1/x2)=1/4.1/3=1/12 p(x3).p(y1/x3)= 1/4.1/6 = 1/24 Do p(x1).p(y1/x1) lớn nhấtÆ B1=B1 +{y1} => B1={y1}. „ Bước 2: xét y2, ta tính: p(x1).p(y2/x1)= 1/2 . 1/3 = 1/6; p(x2).p(y2/x2)= 1/4 . 1/6 = 1/24 p(x3).p(y2/x3)= 1/4 . 1/2 = 1/8 Do p(x1).p(y2/x1) lớn nhấtÆ B1=B1 +{y2} => B1={y1, y2}. „ Bước 3: Xét y3, ta tính: p(x1).p(y3/x1)= 1/2 . 1/6 = 1/12 ; p(x2).p(y3/x2)= 1/4 . 1/2 = 1/8 p(x3).p(y3/x3)= 1/4 . 1/3 = 1/12 Do p(x2).p(y3/x2) lớn nhấtÆ B2=B2 +{y3} => B2={y3}. „ Kết quả: Phân hoạch: B1={y1, y2}, B2={y3} và B3={}. Truyền và bảo mật thông tin 116 Minh họa xây dựng lược đồ giải mã tối ưu „ Lược đồ giải mã tối ưu „ Tính các xác suất truyền sai: „ Xác suất truyền sai từ mã x1: p(e/x1)=∑p(Y=yj ∉B1/X=x1)=p(y3/x1) =1/6 „ Xác suất truyền sai từ mã x2: p(e/x2)= ∑ p(Y=yj ∉B2/X=x2) = p(y1/x2) + p(y2/x2) =1/3+1/6=1/2 „ Xác suất truyền sai từ mã x3: p(e/x3)= ∑ p(Y=yj ∉B3/X=x3) = p(y1/x3) + p(y2/x3) + p(y3/x3) =1/6+1/3+1/2=1 „ Xác suất truyền sai trung bình:p(e)= ∑p(X=xi)p(e/xi) =p(x1).p(e/x1) + p(x2).p(e/x2) + p(x3).p(e/x3) = 1/2.1/6 + 1/4.1/2 + 1/4.1 = 11/24 „ Xác suất truyền sai lớn nhất:pm(e) = Max{ p(e/x1), p(e/x2), p(e/x3)} = 1 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 30 Truyền và bảo mật thông tin 117 Bài tập Truyền và bảo mật thông tin 118 Bài tập SỬA LỖI Chương V. Truyền và bảo mật thông tin 120 V.1. Số học modulo „ Định nghĩa: Giả sử a và b là các số nguyên và m là một số nguyên dương. Khi đó ta viết a ≡ b (mod m) nếu a-b chia hết cho m . Mệnh đề a ≡ b (mod m) được gọi là "a đồng dư với b theo modulo m". Số nguyên m được gọi là mudulus „ Giả sử a = q1m + r1 và b = q2m + r2 (0 ≤ r1 ≤ m-1 và 0 ≤ r2 ≤ m-1). „ =>a ≡ b (mod m) Ù r1 = r2 . „ a ≡ b (mod m) Ù a mod m = b mod m. „ Nếu thay a bằng a mod m thì ta nói rằng a được rút gọn theo modulo m. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 31 Truyền và bảo mật thông tin 121 Số học modulo „ Số học đồng dư modulo m: Zm là tập (0, , m- 1) với hai phép toán là + và ×. „ Việc cộng và nhân trong Zm được thực hiện giống như cộng và nhân các số nguyên ngoại trừ một điểm là các kết quả được rút gọn theo modulo m. „ VD: 11 × 5 trong Z26 ? „ 11 x 5=55; 55 =2* 26+ 3, „ vậy 11 x 5 = 3 trong Z26 Truyền và bảo mật thông tin 122 Số học modulo - các tính chất 1. Phép cộng là đóng: với ∀ a, b ∈ Zm, a+b ∈ Zm 2. Phép cộng là giao hoán, tức là với ∀ a,b ∈ Zm, a+b = b+a 3. Phép cộng là kết hợp, tức là với ∀ a,b,c ∈ Zm, (a+b)+c = a+(b+c) 4. 0 là phần tử trung hòa của phép cộng, có nghĩa là với ∀ a ∈ Zm, a+0 = 0+a = a 5. Phần tử nghịch đảo của phép cộng của phần tử bất kì (a ∈ Zm ) là m-a, nghĩa là a+(m-a) = (m-a)+a = 0 với ∀a ∈ Zm . Truyền và bảo mật thông tin 123 Số học modulo - các tính chất 6. Phép nhân là đóng , tức là với ∀ a,b ∈ Zm , ab ∈ Zm . 7. Phép nhân là giao hoán , nghĩa là với ∀ a,b ∈ Zm , ab = ba 8. Phép nhân là kết hợp, nghĩa là với ∀ a,b,c ∈ Zm , (ab)c = a(cb) 9. 1 là phần tử trung hòa của phép nhân, tức là với bất kỳ a ∈ Zm, a×1 = 1×a = a 10. Phép nhân có tính chất phân phối đối với phép cộng, tức là đối với ∀ a,b,c ∈ Zm , (a+b)c = (ac)+(bc) và a(b+c) = (ab) + (ac) Truyền và bảo mật thông tin 124 Một số lưu ý „ a (mod N)= (a+N) (mod N) Ví dụ: -4 (mod 26)=-4+26 (mod 26)=22 (mod 26) „ Các tính chất phép mod „ (a+b) mod N=(a mod N + b mod N) mod N „ ab mod N=(a mod N)(b mod N) mod N „ Ví dụ: „ (36 +46) mod 26 = (10+20) mod 26=4 „ 310 mod 26= =(33x33x33x3) mod 26 =(27 mod 26)3 .3 mod 26=3 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 32 Truyền và bảo mật thông tin 125 Các phép toán Modulo 2 „ Các phép toán trong Modulo 2 (+,-): „ 0 + 1 = 1 + 0 = 1; „ 0 – 1 = 1 – 0 = 1; „ 1 + 1 = 0 „ 1 – 1 = 0; „ Phép cộng và trừ giống nhau, thường được ký hiệu Truyền và bảo mật thông tin 126 V.2. Mguyên lý khoảng cách nhỏ nhất hamming Khoảng cách Hamming „ Định nghĩa: cho v1 và v2 là 2 dãy nhị phân dài n bit, ta gọi khoảng cách Hamming giữa 2 dãy v1,v2 là số bit tương ứng khác nhau. Ký hiệu: d(v1, v2). „ Ví dụ: v1=10101010 v2=10101111 „ Ta nhận thấy rằng bit thứ 6 và bit thứ 8 giữa giữa v1 và v2 là khác nhau nên số bit tương ứng khác nhau giữa v1 và v2 là 2. Do đó, ta nói khoảng cách Hamming giữa v1 và v2 là 2 hay d(v1, v2) = 2 Truyền và bảo mật thông tin 127 Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu „ Xét kênh truyền đối xứng nhị phân. Giả sử ta truyền các dãy từ mã nhị phân có độ dài n bits với xác suất truyền sai 1 bit là β. „ Gọi W = {w1, w2,,ws} là tập s từ mã truyền, độ dài mỗi từ mã đều bằng n bit. „ V = {v1, v2,., vn} là tập các dãy n bit nhận được ở cuối kênh với W có phân phối đều, xác suất để nhận vj khi truyền wi là p(vj/wi) = pij. Truyền và bảo mật thông tin 128 Kênh truyền đối xứng nhị phân và lược đồ giải mã tối ưu „ Theo lược đồ giải mã tối ưu ta có: khi nhận vj thì giải mã về w*i sao cho: p(w*i/vj) = Max{P(wk/vj)} (∀wi∈W) „ Ta có: P(wk/vj) = (p(wk).p(vj/wk)])/p(vj) với (∀wk∈W) ⇒ p(wk/vj) → Max ⇔ p(wk).p(vj/wk) → Max. „ Do W có phân phối đều nên: p(wk/vj) → Max ⇔ p(vj/wk) → Max „ Vậy: để tìm w*i sao cho P(w*i/vj) = Max{P(wk/vj)} ta chỉ cần tìm w*i sao cho P(vj/ w*i) = Max{P(vj/ wk)} (chỉ dựa vào ma trân truyền tin A) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 33 Truyền và bảo mật thông tin 129 Quan hệ giữa xác suất giải mã và khoảng cách Hamming „ Giả sử nhận được v: „ Xét 2 từ mã w1 và w2 cần chọn để giải mã cho v, độ dài từ mã là n: „ Gọi d1=d(v, w1), d2=d(v,w2). „ Xác suất đế nhận v khi truyền w1: p(v/w1)= β d1(1− β)n-d1 „ Xác suất đế nhận v khi truyền w2: p(v/w2)= β d2(1− β)n-d2 „ Nếu nhiễu 0 1 „ Do đó: P(v/w1)>p(v/w2) ⇔ d1 <d2 „ Nhận xét: xác suất giải mã càng lớn thì khoảng cách Hamming càng nhỏ. Truyền và bảo mật thông tin 130 Nguyên lý Hamming Định lý: trên kênh truyền đối xứng nhị phân với S từ mã ở đầu truyền có độ dài n bit, lược đồ giải mã tối ưu có thể thay thế bằng lược đồ giải mã theo khoảng cách Hamming với nguyên lý: nếu nhận được v, ta sẽ giải ra w*I sao cho d(v,w*i)=Min d(v,wk) (với∀wk∈W). Ví dụ: xét bộ mã W={w1=00000, w2=10011, w3=11100, w4=01111} . Giả sử nhận được dãy v=01011. „ Ta có: d(v,w1)=3; d(v,w2)=2; d(v,w3)=4; d(v,w4)=1. „ Vậy v được giải về w4 vì khoảng cách Hamming giữa v và w4 là nhỏ nhất. Truyền và bảo mật thông tin 131 Bài tập „ 1. Cho bộ mã W={w1=000000, w2=101010, w3=111000, w4=111111} và nhận được dãy v=010111, khi đó giải mã về từ mã nào? Vì sao? „ 2. Cho bộ mã W={w1=000000, w2=010101, w3=000111, w4=111111} và Nhận được dãy v=010111, khi đó giải mã về từ mã nào? Vì sao? Truyền và bảo mật thông tin 132 V.3. Bổ đề về tự sửa lỗi và cận Hamming „ Đặt vấn đề: một từ mã w dài n bit khi được truyền tuần tự từng bit có thể sai e bit. Vấn đề đặt ra là khoáng cách (Hamming) giữa các từ mã và sai số e quan hệ với nhau như thế nào để có thể phân biệt tốt nhất đồng thời tất cả các từ mã? Bổ đề sau xác định quan hệ này. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 34 Truyền và bảo mật thông tin 133 Các dạng lỗi Giả sử ta truyền từ mã n bit wi∈W ( 1 ≤ i ≤ s) và nhận được dãy n bit vj ( 1≤ j ≤ 2n). Các loại lỗi có thể phát hiện sau: „ Lỗi có thể tự điều chỉnh: Trong trường hợp này tồn tại duy nhất từ mã w*i sao cho d(vj, w*i)= Min d(vj, wk) với∀wk ∈W. => vj được giải mã về w*i „ Lỗi chỉ phát hiện không điều chỉnh được: Trong trường hợp này tồn tại từ mã w*i và w**i sao cho d(vj, w*i)= d(vj, w**i)=Min d(vj, wk) với∀wk∈W => vj không thể giải mã chính xác. „ Lỗi không phát hiện được: giải mã ra w*i nhưng khác với wi đã truyền. Truyền và bảo mật thông tin 134 Bổ đề: Xét bộ mã W={w1, w2, , ws} gồm có s từ mã nhị phân dài n bit và 1 số nguyên dương e. 1. Nếu d(wi, wj) ≥ 2e+1 (với ∀ i≠j ) Khi đó: tất cả các dãy nhận được v có số bit lỗi ≤ e thì v có thể tự điều chỉnh (hay tự sửa lỗi). 2. Nếu d(wi, wj) ≥ 2e (với ∀ i≠j ) Khi đó: tất cả các dãy nhận được v có số bit lỗi < e thì v có thể tự điều chỉnh. Tất cả các dãy nhận được có số bit lỗi = e thì ta chỉ phát hiện là v có lỗi và không thể tự điều chỉnh được. 3. Ngược lại; Nếu v có số chữ số bit lỗi ≤ e và có thể tự điều chỉnh thì d(wi, wj)≥ 2e+1 (với ∀ i≠j ). Nếu v có số chữ số bit lỗi ≤ e-1 tự điều chỉnh được và tất cả các tín hiệu với số chữ số bit lỗi ≤ e được phát hiện thì khoảng cách giữa các từ mã luôn thỏa: d(wi,wj) ≥ 2e (với∀ i≠j ). Truyền và bảo mật thông tin 135 Chứng minh 1. Giả sử: d(wi, wj) ≥ 2e+1 với∀ i≠j . Nếu w và w’ có cùng khoảng cách đối với dãy v thì d(v,w)=d(v,w’)≥ e+1. Vậy , nếu d(v, w*) ≤ e thì v có thể được giải mã ra w*. 2. Nếu d(wi,wj)≥ 2e với ∀ i≠j, có khả năng có v, w và w’ với số chữ số lỗi là: d(v,w)=d(v,w’)=e (d(v,w)+ d(v,w’) ≥ d(w,w’)≥ 2e). Có thể phát hiện ra các từ mã gần v, nhưng do tồn tại cùng lúc nhiều từ mã gần nhất với v dẫn đến không giải mã được. 3. Tương tự. Truyền và bảo mật thông tin 136 Cận Hamming „ Đặt vấn đề: trong tổng số 2n dãy nhị nhân dài n bit có thể chọn ra bao nhiêu dãy để tạo thành một bộ mã có thể tự điều chỉnh được e bit lỗi. Định lý cận Hamming cho chúng ta xác định số từ mã có độ dài n bit với giả thiết: có khả năng tự sửa được e bit lỗi (điều kiện cần tự sửa lỗi). „ Định lý: Nếu bộ mã W có s từ mã có độ dài n bit có thể tự sửa được e bit lỗi thì „ Ghi chú: Cn = n!/(i!*(n-i)!); s là số từ mã Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 35 Truyền và bảo mật thông tin 137 Chứng minh „ Xét từ mã nhị phân wi có độ dài n bit và có khả năng tự sửa được e bit lỗi. „ Số dãy vj sai khác với wi từ 0 đến e bit là : „ Với s từ mã, tổng số dãy vj có thể tự sửa lỗi là: „ (2n là tổng số dãy nhị phân dài n bits)Î Truyền và bảo mật thông tin 138 Bài tập „ Cho n=7 và e=2, hãy áp dụng định lý cận Hamming cho biêt số từ mã tối đa của bộ mã W. „ Truyền và bảo mật thông tin 139 V.4. Mã kiểm tra chẵn lẻ „ Bộ mã kiểm tra chẵn lẻ là bộ mã gồm s=2k từ mã, trong đó mỗi từ mã có dạng sau: (Ghi chú: trong một số trường hợp sinh mã theo phương pháp kiểm tra chẵn lẻ, thứ tự các bit kiểm tra và các bit thông tin có thể xen kẻ nhau hay theo một thứ tự khác. Ở đây, ta chọn thứ tự các bit kiểm tra chẵn lẻ và các bit thông tin như trên để dễ tính toán nhưng vẫn mất tính tổng quát. Truyền và bảo mật thông tin 140 Mã kiểm tra chẵn lẻ „ Mỗi đoạn mã thông tin có duy nhất một đoạn mã kiểm tra và được xác định bởi hệ phương trình tuyến tính nhị phân sau: „ Gọi A=[aij] =Am x n , aij∈{0,1}, i= 1..m , j= 1..n . Ma trận A được gọi là ma trận kiểm tra chẵn lẻ có hạng là m (hay Rank(A) = m). „ Lưu ý: ở đây sử dụng phép tính + trong Z2 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 36 Truyền và bảo mật thông tin 141 Mã kiểm tra chẵn lẻ „ Cho w’=r1r2rn là một từ mã, w là ma trận viết theo cột, khi đó A.w=0: a11 a12 a1n a21 a22 a2n am1 am2 amn r1 r2 rn X = 0 0 0 Hay: Truyền và bảo mật thông tin 142 Phương pháp kiểm tra chẵn lẻ „ Gọi w’=r1r2rn là từ mã truyền (hay dãy n bit truyền) và v’=r1r2rn là dãy n bit nhận được. „ Qui ước: v’, w’ (lần lượt là chuyển vị của v và w) được viết theo dòng. Còn v, w được viết theo cột. „ Nếu A.v = 0 thì v = w, ta gọi v là chẵn (trường hợp nhận đúng) „ Nếu A.v ≠ 0 thì v ≠ w, ta gọi v là lẻ (trường hợp nhận sai). „ Ta gọi z = v-w là bộ lỗi giữa v và w. Nghĩa là tại các vị trí z = {0} thì bit nhận được tương ứng là bit đúng và tại các vị trí z = {1} thì bit nhận được tương ứng là bit sai (hay bit lỗi). „ Ta gọi C = A.z là bộ sửa lỗi (hay bộ điều chỉnh lỗi). „ Ta có C = A.z = A.(v-w) = A.v-A.w = A.v⇒ C = A.v = A.z „ Tính chất của bộ sửa lỗi: dãy n bit nhận được v và bộ lỗi tương ứng có cùng bộ điều chỉnh. Truyền và bảo mật thông tin 143 Phương pháp sinh mã kiểm tra chẵn lẻ „ Giả sử: cho trước ma trận kiểm tra chẵn lẻ A với Rank(A) = m. Tìm bộ mã chẵn lẻW={w1, w2, w3,,ws} „ Bước 0: Xác định các giá trị n, m, k, s „ Độ dài của từ mã n= số cột của ma trận A. „ Số bit kiểm tra m= số dòng của ma trận A. „ Số bit thông tin: k = n-m. „ Số từ mã s=2k „ Bước i: Tìm các từ mã thứ i (1≤ i ≤ s): „ Gọi kpi là triển khai nhị phân k bit của số i „ Từ mã cần tìm là: w’i=r1r2..rmkpi „ Giải hệ phương trình A.wi=0 để tìm m bit kiểm tra ứng với k bit thông tin (kpi) đã biết => từ mã wi Truyền và bảo mật thông tin 144 Ví dụ sinh mã kiểm tra chẵn lẻ „ Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: „ Bước 0: „ n=6 (= số cột của ma trận A) „ m=3 (= số dòng của ma trận A) „ Số bit thông tin k = n – m = 3 „ => Số từ mã s=2k=8. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 37 Truyền và bảo mật thông tin 145 Ví dụ sinh mã kiểm tra chẵn lẻ Bước i: Tìm từ mã thứ i (1≤ i ≤ s): „ w’0=r1r2r3000 (000 là triển khai nhị phân k=3 bit của số i=0) „ w’1=r1r2r3001 (001 là triển khai nhị phân k=3 bit của số i=1) „ w’2=r1r2r3010 „ w’3=r1r2r3011 „ w’4=r1r2r3100 „ w’5=r1r2r3101 „ w’6=r1r2r3110 „ w’7=r1r2r3111 Truyền và bảo mật thông tin 146 Ví dụ sinh mã kiểm tra chẵn lẻ Giải hệ phương trình A.w1=0 Truyền và bảo mật thông tin 147 Ví dụ sinh mã kiểm tra chẵn lẻ Giải hệ phương trình A.w2=0 Truyền và bảo mật thông tin 148 Ví dụ sinh mã kiểm tra chẵn lẻ „ Giải tương tự cho các trường hợp còn lại ta có: w’0=000000, w’3=110011, w’4=110100, w’5=111101, w’6=001110, w’7=000111. ⇒W={000000, 001001, 111010, 110011, 110100, 111101, 001110, 000111} Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 38 Truyền và bảo mật thông tin 149 Quan hệ giữa độ dài mã n, số bit kiểm tra m và số lỗi tự sửa e „ Điều kiện cần (Cận Hamming): Điều kiện cần để bộ mã chẵn lẻ có độ dài n bit có thể tự sửa được e bit lỗi với k bit thông tin và m bit kiểm tra là: „ Điều kiện đủ ( ĐK Vasharmov-Gilbert-Sacks): Điều kiện đủ để bộ mã kiểm tra chẵn lẻ có độ dài n bit với m bit kiểm tra chẵn lẻ có thể tự sửa được e bit lỗi là: Truyền và bảo mật thông tin 150 Ví dụ tìm m nhỏ nhất từ n và e „ Giả sử biết trước n=7 và e=1. Tìm số bit kiểm tra tối thiểu cần thiết của bộ mã chẵn lẻ. „ Theo định lý điều kiện cần (Cận Hamming): „ m = 1 ⇒ (*) sai. „ m = 2 ⇒ (*) sai. „ m ≥ 3 ⇒ (*) đúng. „ Vậy số bit kiểm tra tối thiểu cần thiết là m = 3. Truyền và bảo mật thông tin 151 Ví dụ tìm e lớn nhất từ m và n „ Giả sử cho trước m=3, k=2. Tìm số bit lỗi lớn nhất có thể tự sửa e? „ Theo định lý điều kiện đủ (ĐK Vassharmov-Gilbert- Sacks): Vậy số bit lỗi lớn nhất có thể tự sửa là e = 1. Truyền và bảo mật thông tin 152 Bài tập „ 1. Xây dựng bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: „ 2. Tìm bộ mã kiểm tra chẵn lẻ được sinh từ ma trận kiểm tra A như sau: „ 3. Xét bộ mã kiểm tra chẵn lẻ độ dài 15 bit có thể tự sửa được 1 bit lỗi trên đường truyền, hãy cho biết số bit kiểm tra chẵn lẻ tối thiểu? „ 4. Xét bộ mã kiểm tra chẵn lẻ độ dài 8 bit với 4 bit kiểm tra chẵn lẻ. Hãy cho biết số lỗi tự sửa tối đa của bộ mã? Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 39 Truyền và bảo mật thông tin 153 V.5. Phương pháp sinh mã kiểm tra chẵn lẻ nhanh Đặt vấn đề: „ Như chúng ta đã biết, phương pháp sinh mã kiểm tra chẵn lẻ giúp ta sinh bộ mã kiểm tra chẵn lẻ với số từ mã tương ứng là s=2k „ Với phương pháp này, ta phải xác định từng từ mã một (bằng cách giải hệ phương trình tuyến tính nhị phân). „ Giả sử: k=10 ta phải xác định s=210=1024 từ mã,Điều này sẽ mất nhiều thời gian nếu k càng lớn. ÆVấn đề đặt ra ở đây là tìm ra một phương pháp sinh bộ mã kiểm tra chẵn lẻ nhanh hơn về mặt thời gian. Phương pháp sinh mã kiểm tra chẵn lẻ dựa theo lý thuyết nhóm sẽ giải quyết vấn đề này. Truyền và bảo mật thông tin 154 Nhóm cộng tính „ Nhóm G được gọi là một nhóm cộng tính nếu G có các tính chất: -∀ a, b ∈ G ⇒ a+b∈ G ( tính chất cộng). -∀ a, b, c ∈ G ⇒ a + (b + c)= (a + b) + c ( tc kết hợp). -∃ ∅ ∈ G sao cho ∅ + a = a + ∅ = a, ∀a∈ G -∀ a ∈ G ∃ -a∈G : a + (-a)=∅ „ Nhóm G là nhóm hoán vị (nhóm Aben) nếu ∀a,b∈ G=> a + b = b + a. „ Ví dụ: - Tập hợp các số nguyên với phép + thông thường là nhóm Aben. - Tập hợp các số nhị phân có độ dài n bit cùng với phép + trong Modulo 2 tạo thành nhóm Aben. Truyền và bảo mật thông tin 155 Tính chất của bộ mã chẵn lẻ „ Tính tương đương của bộ mã nhóm cộng tính và bộ từ mã kiểm tra chẵn lẻ được thể hiện qua 2 định lý sau: „ Định lý 1: tập hợp các từ mã trong bộ mã kiểm tra chẵn lẻ là một nhóm cộng tính. Truyền và bảo mật thông tin 156 Tính chất của bộ mã chẵn lẻ „ Định lý 2: Nếu tập hợp W là tập các dãy nhị phân với độ dài các dãy cùng bằng n và W là một nhóm Aben với phép cộng Modulo 2 thì W có thể xem như một bộ mã kiểm tra chẵn lẻ được sinh ra từ ma trận A có dạng như sau: Trong đó: - Ma trận A có m dòng và n cột. - Im : là ma trận đơn vị cấp m. - k: là số dãy nhị phân (hay từ mã) độc lập tuyến tính lớn nhất. - n: là độ dài của từ mã và m = n-k: - bij: được xác định bằng cách dựa vào hệ phương trình tuyến tính (*) và k từ mã độc lập tuyến tính như sau: w’i=r1r2r3rm rm+1rm+2rn. ) , ∀i =1..k Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 40 Truyền và bảo mật thông tin 157 Phương pháp sinh mã kiểm tra chẵn lẻ nhanh „ Bước khởi tạo: xác định các giá trị n, m, k, s. „ Bước 1: sinh k từ mã độc lập tuyến tính (đltt). „ Bước 2: cộng tổ hợp các từ mã: + Cộng các tổ hợp của 2 từ mã từ k mã đltt => có từ mã. + Cộng các tổ hợp của 3 từ mã từ k mã đltt => có Ck3 từ mã. + Cộng các tổ hợp của k từ mã từ k từ mã đltt => có từ mã. Bước 3: Cộng s-1 từ mã đã tìm được để tìm từ mã cuối cùng => = 1 từ mã. Tổng số từ mã s= = 2k từ mã. Truyền và bảo mật thông tin 158 Phương pháp sinh mã kiểm tra chẵn lẻ nhanh „ Có thể sinh k từ mã độc lập tuyến tính bằng cách: „ Lấy k dãy nhị phân k bit chỉ chứa 1 số 1: L1= 000..001 L2= 000..010 Lk-1= 010..000 Lk= 100..000 „ Từ đó đi tìm các từ mã dạng r1r2..rmLi Truyền và bảo mật thông tin 159 Ví dụ sinh mã kiểm tra chẵn lẻ nhanh „ Tìm bộ mã nhóm khi biết trước ma trận kiểm tra: „ Bước khởi tạo: n = 6, m = 3, k = 3, s = 2k = 8. „ Bước 1: Sinh k = 3 từ độc lập truyến tính: w’1=001001, w’2=111010, w’3=110100 „ Bước 2: Cộng tổ hợp các từ mã. + Cộng các tổ hợp 2 từ mã đltt: w’4=w’1+w’2=110011; w’5=w’1+w’3=111101; w’6=w’2+w’3=001110 + Cộng các tổ hợp 3 từ mã đltt: w’7=w’1+w’2+w’3=000111 „ Bước 3: xác định từ mã cuối cùng: w’0=w’1+w’2+w’3+w’4+w’5+w’6+w’7=000000 Truyền và bảo mật thông tin 160 V.6. Lược đồ sửa lỗi tối ưu Đặt vấn đề „ Trong một hệ thống liên lạc truyền tin, bên cạnh các yêu cầu thiết bị (như nguồn phát, bộ mã hóa, ênh truyền, bộ giải mã,) đảm bảo tốt cho việc truyền và nhận dữ liệu thì còn có các khía cạnh khác như phương pháp mã hóa và giải mã sao cho tối ưu là phần rất quan trọng trong hệ thống. „ Vấn đề luôn được đặt ra ở đây là làm thế nào để chỉ ra một phương pháp giải mã tối ưu, có nghĩa hệ thống phải có khả năng phát hiện và sửa lỗi một cách chính xác nhất có thể có khi nhiễu xảy. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 41 Truyền và bảo mật thông tin 161 Định nghĩa Hiệp hợp „ Gọi W={w1, w2, ,ws} là bộ mã kiểm tra chẵn lẻ. „ V ={v1, v2, , } là tập hợp các dãy n bit có thể nhận được ở cuối kênh. „ Ta gọi một hiệp hợp của W trong V là tập hợp có dạng z + W (z là bộ lỗi) Truyền và bảo mật thông tin 162 Ví dụ Hiệp hợp „ Xét bộ mã : W={w0=0000, w1=0101, w2=1110, w3=1011}. „ Các bộ lỗi một bit khác nhau có thể có là z={1000, 0100, 0010, 0001}. ÆCác hiệp hợp ứng với các bộ lỗi 1 bit: w0 w1 w2 w3 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 (với z1=1000) Hiệp hợp 2 0100 0001 1010 1111 (với z2=0100) Hiệp hợp 3 0010 0111 1100 1001 (với z3=0010) Hiệp hợp 4 0001 0100 1111 1010 (với z4=0001) Trong đó: hiệp hợp i = wi + zi Truyền và bảo mật thông tin 163 Lược đồ sửa lỗi theo các hiệp hợp „ Bước 1: Lập bảng các hiệp hợp ứng với các bộ lỗi cần thiết - Dòng đầu tiên viết các từ mã wi∈W. - Các dòng tiếp theo ứng với cột w0 = 0000 viết các bộ lỗi z (các bộ lỗi 1 bit, 2 bit,). - Các dòng ở cột thứ i được xác định bởi z + wi „ Bước 2: Quá trình giải mã :Khi nhận v, ta xác định cột thứ i chứa v và giải mã về wi tương ứng. Truyền và bảo mật thông tin 164 Ví dụ lược đồ sửa lỗi theo các hiệp hợp „ Xét ví dụ trước, W={w0=0000, w1=0101, w2=1110, w3=1011}. „ Lập bảng hiệp hợp w0 w1 w2 w3 0000 0101 1110 1011 Hiệp hợp 1 1000 1101 0110 0011 Hiệp hợp 2 0100 0001 1010 1111 Hiệp hợp 3 0010 0111 1100 1001 Hiệp hợp 4 0001 0100 1111 1010 „ Quá trình giải mã: + Giả sử nhận v = 0111. Tra trên bảng các Hiệp hợp ta có v ở cột 1Æ v được giải mã về w1 = 0101. + Giả sử nhận v = 1010. Tra trên bảng các Hiệp hợp ta có v ở cột 2 và cột 3 Æ giải mã không chính xác Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 42 Truyền và bảo mật thông tin 165 Lược đồ sửa lỗi thông qua bộ lỗi Dựa vào tính chất của bộ sửa lỗi ta có dùng lược đồ giải mã gồm 2 bước sau: „ Bước 1: Lập bảng sửa lỗi: Bộ lỗi (Z) – Bộ sửa lỗi (C=A*Z). „ Bước 2: Quá trình sửa lỗi - Khi nhận được dãy n bit v ∈V, ta xác định bộ điều lỗi C cho v với C=A.v - Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C. - Giải mã w=v+z . Truyền và bảo mật thông tin 166 Ví dụ lược đồ sửa lỗi thông qua bộ lỗi „ Bộ mã tương ứng được xác định là: w0=00000, w1=11101 Truyền và bảo mật thông tin 167 Ví dụ lược đồ sửa lỗi thông qua bộ lỗi „ Bước 1: Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 1) + Bộ 0 lỗi + Bộ lối 1 bit „ Bước 2: Quá trình sửa lỗi + Giả sử nhận v= 11100, tính C = A.v = 1110 + Tra bảng sửa lỗi để tìm bộ lỗi ứng với C, ta có z0 = 00001 + Giải mã w = v + z0 = 11100 + 00001 = 11101 = w1 (Ghi chú: z’, C’ là các chuyển vị của z, C) Bộ điều chỉnh (C’=A.z)Bộ lỗi (z’) 111000001 000100010 001000100 010001000 100010000 000000000 Truyền và bảo mật thông tin 168 Ví dụ lược đồ sửa lỗi thông qua bộ lỗi Lược đồ sửa lỗi 2 bit : „ Lập bảng sửa lỗi: Bộ lỗi- Bộ điều chỉnh (e = 2) Bộ lỗi (z’) Bộ điều chỉnh (C’=A.z) Bộ lỗi 2 bit (4 Bộ ) (Tất cả các bộ 2 lỗi còn lại có trùng bộ điều chỉnh 1 lỗi hoặc trùng nhau) „ Quá trình sửa lỗi Giả sử nhận v=11011, tính C = A.v = 0011 Tra bảng sửa lỗi để tìm bộ lỗi z0 ứng với C, ta có z0 = 00110 - Giải mã w = v + z0 =11011 + 00110 =11101 = w1 111100011 001100110 010101010 100110010 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 43 Truyền và bảo mật thông tin 169 Xác suất truyền đúng „ Gọi Ni là số bộ lỗi ứng với i lỗi có thể tự sửa, khi đó xác suất truyền đúng và tự điều chỉnh sẽ là: „ Ví dụ: xét trường hợp các ví dụ trên với n= 5 và tự sửa e = 2 bit lỗi. Áp dụng công thức trên ta có: Truyền và bảo mật thông tin 170 Bài tập „ 1. Cho ma trận kiểm tra chẵn lẻ sau: - Xây dựng bộ mã kiểm tra chẵn lẻ. - Minh họa lược đồ sửa lỗi thông qua bộ điều chỉnh trong các trường hợp lỗi 1 bit. Tính xác suất truyền đúng cho các trường hợp có thể tự sửa được. Truyền và bảo mật thông tin 171 V.6. Mã Hamming „ Mã Hamming là một dạng mã nhóm (mã kiểm tra chẵn lẻ) được xác định từ ma trận kiểm tra chẵn lẻ A có dạng sau: - Cột thứ j của ma trận A là biểu diễn nhị phân m bit (m là số bit kiểm tra chẵn lẻ) của số j theo qui ước biểu diễn nhị phân của số j được viết theo thứ tự từ dưới lên trên (viết theo cột), tương đương với viết từ trái sang phải (viết theo dòng). - Các bit ở vị trí 2i ( i = 0, 1, 2, ) được chọn làm bit kiểm tra. Truyền và bảo mật thông tin 172 Ví dụ ma trận kiểm tra Hamming „ Biểu diễn nhị phân của số j = 3 có m = 3 bit như sau: „ Viết theo dòng: 011 (viết từ trái sang phải) „ Viết theo cột (viết từ dưới lên) : „ Ví dụ 2: ma trận kiểm tra chẵn lẻ với n=6, m=3 có thể viết như sau: Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 44 Truyền và bảo mật thông tin 173 Ví dụ ma trận kiểm tra Hamming „ Từ mã Hamming có dạng: w=r1r2r3r4r5r6. Trong đó, r1r2r4 (vị trí 2i, i=0,1,2 ) là các bit kiểm tra và r3r5r6 là các bit thông tin Truyền và bảo mật thông tin 174 Tính chất mã Hamming „ Nếu cho trước số bit (m) và số bit lỗi tự sửa (e) thì số bit tối đa của bộ mã Hamming (n) có thể được ước lượng từ bất đẳng thức sau: Truyền và bảo mật thông tin 175 Ví dụ minh họa „ Tìm bộ mã Hamming với n = 6 và m =3 „ Ta có thể viết ngay ma trận kiểm tra chẵn lẻ cho bộ mã Hamming „ Từ A ⇒ k = n – m = 3. „ Các bit ở các vị trí 1, 2, 4 được chọn làm các bit kiểm tra. „ Số từ mã của bộ mã Hamming là s = 2k= 8 w’0=r1r20r400 w’1=r1r20r401 w’2=r1r20r410 .. w’7=r1r21r411 Giải các hệ phương trình: A.w1=0, A.w2=0, A.w3=0 W’={000000, 010101, 100110, 110011, 111000, 101101, 011110, 001011} Truyền và bảo mật thông tin 176 Ví dụ minh họa Chú ý, có thể sử dụng phương pháp sinh mã nhanh: „ Số từ mã của bộ mã Hamming là s = 2k= 8 „ Tìm k từ mã độc lập tuyến tính có dạng: w’1=r1r20r401 w’2=r1r20r410 w’3=r1r21r400 „ Giải các hệ phương trình: A.w1=0, A.w2=0, A.w3=0 để tìm w’1, w’2, w’3 „ Các từ mã còn lại được xác định theo phương pháp sinh mã nhanh. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 45 Truyền và bảo mật thông tin 177 Bài tập 1. Viết ma trận kiểm tra chẵn lẻ cho bộ mã Hamming với n = 15. 2. Từ kết quả bài tập 1, hãy tìm k từ mã Hamming độc lập tuyến tính tương ứng. 3. Xét bộ mã Hamming với số bit kiểm tra cho trước là m, khi đó: - Độ dài mã tối thiểu là bao nhiêu? - Độ dài mã tối đa là bao nhiêu? Truyền và bảo mật thông tin 178 V.7. Thanh ghi lùi từng bước „ Biểu diễn vật lý của thanh ghi lùi từng bước(LTB): - Fm-1, Fm-2, , F1, F0 : các bit lưu trữ dữ liệu nhị phân. - am-1, am-2, , a1, a0 : các công tắc (switch) dùng để đóng (=1) hay mở ( =0). ⊕ là bộ làm tính cộng mudulo 2 sau mỗi xung đồng hồ với dữ liệu do các bit của thanh ghi gửi về. „ Quá trình dịch chuyển lùi: sau mỗi xung đồng hồ thì dữ liệu trong bit Fi sẽ được chuyển về lưu trữ ở bit Fi-1 Truyền và bảo mật thông tin 179 Biểu diễn toán học của thanh ghi LTB „ Gọi x = (x0, x1, , xm-2, xm-1) là giá trị các bit của thanh ghi tại thời điểm trước khi có nhịp xung đồng hồ. x’ = (x’0, x’1, , x’m-2, x’m-1) là giá trị các bit của thanh ghi sau khi có nhịp xung đồng hồ. „ Khi đó ta có: x’0=x1 x’1=x2 x’2=x3 x’m-2=xm-1 x’m-1=a0x0 + a1x1 + + am-1xm-1. Truyền và bảo mật thông tin 180 Biểu diễn toán học của thanh ghi LTB „ Hay viết theo dạng ma trận ta có x’ = T.x „ Trong đó: - T: Ma trận vuông cấp m. - Dòng cuối của ma trận:là các hệ số: a0, a1, , am-1. - Gốc trên bên phải: là ma trận đơn vị cấp m-1. „ T được gọi là ma trận đặc trưng của thanh ghi lùi từng bước. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 46 Truyền và bảo mật thông tin 181 Biểu diễn toán học của thanh ghi LTB „ Quá trình dịch chuyển lùi từng bước của thanh ghi: „ Gọi: „ Giá trị của thanh ghi sau 1 xung đồng hồ là x(1)=T.x(0) „ Giá trị của thanh ghi sau 2 xung đồng hồ là x(2)=T.x(1)=T2.x(0) „ Giá trị của thanh ghi sau 3 xung đồng hồ là x(3)=T.x(2)=T3.x(0) Truyền và bảo mật thông tin 182 Ví dụ thanh ghi lui từng bước „ Cho thanh ghi lui từng bước sau: „ Ta có: m=4, a0=1, a1=0, a2=1, a3=0. ÆMa trận đặc trưng của thanh ghi: Truyền và bảo mật thông tin 183 Chu kỳ của thanh ghi „ Chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặp lại trạng thái ban đầu. Nghĩa là nếu x(0) ≠0 và∃ n>0 sao cho x(n)= x(0) thì ta nói n là chu kỳ của thanh ghi. „ Bởi vì số trạng thái của x(i) là hữu hạn (2m) nên thanh ghi có chu kỳ „ Lưu ý: viết x(i)=3 (011) tương ứng Truyền và bảo mật thông tin 184 Ví dụ tìm chu kỳ của thanh ghi „ Ta có: m=4, a0=1, a1=0, a2=1, a3=0. „ Nếu khởi tạo x(0)=0001, khi đó: => Chu kỳ=6 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 47 Truyền và bảo mật thông tin 185 Ví dụ tìm chu kỳ của thanh ghi „ Tương tự: + Khi chọn x(0) = 3 thi ta cũng có chu kỳ n = 6. + Khi chọn x(0)= 6 thì ta có chu kỳ n = 3. + Khi chọn x(0)= 0 thì ta có chu kỳ n = 1. Truyền và bảo mật thông tin 186 Bài tập „ Tìm các chu kỳ của thanh ghi lui từng bước như hình sau: Truyền và bảo mật thông tin 187 Đa thức đặc trưng của thanh ghi LTB „ Định nghĩa: đa thức đặc trưng của thanh ghi lui từng bước có ma trận đặc trưng là T là đa thức có dạng gm(x)=a0 + a1x+ a2x2+ +am-1xm-1 + xm với a0, a1, a2,, am-1 là các công tắc của thanh ghi và m là số bit của thanh ghi „ Ví dụ a0 = 1, a1= 0, a2 = 1, a3 = 0 ÆĐa thức đặc trưng của thanh ghi là: gm(x)=1 + x2 + x4 Truyền và bảo mật thông tin 188 Quan hệ giữa chu kỳ n, đa thức đăc trưng và đa thức (xn + 1) „ Đa thức (xn+ 1)>= gm(x) luôn chia hết cho đa thức đặc trưng của thanh ghi gm(x) „ Ví dụ: xét lại thanh ghi lui từng bước như như ví dụ trước có gm(x)=1+x2+x4, chu kỳ n=6 thực hiện phép chia (x6 + 1):(x4+x2+1) (phép toán Modulo 2) x6 + 1 x2x 6 + x4+x2 x4+x2 +1 +1 x4+x2+1 x4+x2+1 0 Chú ý: Hai phép toán và là như nhau Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 48 Truyền và bảo mật thông tin 189 Thủ tục sinh thanh ghi lùi từng bước Sinh thanh ghi lùi từng bước với số bit là m và có chu kỳ n: „ Bước 1: xác định đa thức đặc trưng của thanh ghi - Tìm 2 đa thức gm(x)=a0 + a1x+ a2x2+ +am-1xm-1 + xm và hk(x)=h0 + h1x+ h2x2+ +hk-1xk-1 + xk sao cho (xn + 1) = gm(x)* hk(x). - Nếu∃ (xn + 1) = gm(x)* hk(x) thì ta chọn gm(x) làm đa thức đặc trưng và thực hiện bước 2. Ngược lại: không tồn tại thanh ghi theo yêu cầu. „ Bước 2: xác định thanh ghi từ đa thức đặc trưng gm(x)=a0 + a1x+ a2x2+ +am-1xm-1 + xm Truyền và bảo mật thông tin 190 Ví dụ sinh thanh ghi lùi từng bước „ Thiết kế thanh ghi có m=4 bit và chu kỳ n=7 „ Bước 1: Xác định đa thức đặc trưng của thanh ghi „ Ta có (x7 + 1)=(1 + x2 + x3)(1 + x2 + x3 + x4) „ Do m=4 nên chọn g4(x) = (1 + x2 + x3 + x4) làm đa thức đặc trưng của thanh ghi. Truyền và bảo mật thông tin 191 Tìm gm(x) Giải pt: x7+ 1=(x4+a3x3+a2x2+a1x+a0)(x3+h2x2+h1x+h0 ) h2 +a3 = 0 h1+a3h2+a2 = 0 h0+a3h1+a2h2+a1 = 0 a3h0+a2h1+a1h2+a0 =0 a2h0+a1h1+a0h2 =0 a1h0+a0h1 =0 a0h0 =1 a3 =1, a2=1, a1=0, a0=1, h2 =1, h1=0, h0=1 Truyền và bảo mật thông tin 192 V.8. Mã xoay vòng „ Định nghĩa mã xoay vòng „ Mã xoay vòng là mã kiểm tra chẵn lẻ được sinh ra từ ma trận kiểm tra chẵn lẻ ứng với chu kỳ n của thanh ghi lùi từng bước có dạng như: A=[x(0)| Tx(0)|T2x(0) ||Tn-1x(0) ] „ Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 49 Truyền và bảo mật thông tin 193 Ví dụ 1 „ Từ thanh ghi : m=4, a0=1, a1=0, a2=1, a3=0 đã xét, có chu kỳ n=6: „ Khởi tạo x(0)=1 ta có: A=[x(0) x(1) x(2) x(3) x(4) x(5)] „ Ta có n=6, m=3, k=2 ⇒ s = 2k = 22 = 4 từ mã. Truyền và bảo mật thông tin 194 Phương pháp sinh nhanh bộ mã xoay vòng „ Bước 1: sinh mã xoay vòng đầu tiên Sinh mã xoay vòng đầu tiên có dạng w1=a0a1a2am-11000..00 „ Bước 2: sinh k -1 từ mã độc lập tuyến tính còn lại: w2= 0a0a1a2am-11000 (dịch vòng w1 sang phải 1 bit). wk= 00000a0a1a2am-11 (dịch vòng wk-1 sang phải 1 bit). „ Bước 3: xác định các từ mã còn lại của bộ mã Các từ mã còn lại gồm (2k – k từ mã) được xác định bằng cách cộng tổ hợp của 2, 3, , k từ mã từ k từ mã độc lập tuyến tính ở trên. k-1 bit 0 Truyền và bảo mật thông tin 195 Một số đa thức đặc trưng Bảo mật thông tin Phần II. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 50 Giới thiệu về bảo mật thông tin Chương I. Truyền và bảo mật thông tin 198 I.1. An toàn thông tin „ Từ xưa „ An toàn bảo mật thông tin đảm bảo bằng „ Giao thức, cơ chế „ Các điều luật „ Thông tin ngày nay phần lớn được lưu và vận chuyển trên các phương tiện điện tử Æ phương tiện bảo mật: mật mã học Truyền và bảo mật thông tin 199 Các phương pháp bảo vệ an toàn thông tin Các phương pháp bảo vệ an toàn thông tin „Bảo vệ an toàn thông tin bằng các biện pháp hành chính. „Bảo vệ an toàn thông tin bằng các biện pháp kỹ thuật (phần cứng). „Bảo vệ an toàn thông tin bằng các biện pháp thuật toán (phần mềm). Biện pháp hiệu quả nhất và kinh tế nhất hiện nay trên mạng truyền tin và mạng máy tính là biện pháp thuật toán. Truyền và bảo mật thông tin 200 Nội dung an toàn thông tin „ Tính bí mật: tính kín đáo riêng tư của thông tin „ Tính xác thực của thông tin, bao gồm xác thực đối tác( bài toán nhận danh), xác thực thông tin trao đổi. „ Tính trách nhiệm: đảm bảo người gửi thông tin không thể thoái thác trách nhiệm về thông tin mà mình đã gửi. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 51 Truyền và bảo mật thông tin 201 I.2. Mật mã học (cryptology) Bao gồm: „ Mật mã học (cryptography): là khoa học nghiên cứu cách ghi bí mật và xác thực thông tin. „ Thám mã(cryptanalysis): là khoa học nghiên cứu cách phá mã hoặc tạo mã giả. Truyền và bảo mật thông tin 202 I.3. Khái niệm hệ mã mật (CryptoSystem) „ Định nghĩa 1.1 „ Một hệ mật là một bộ 5 (P,C,K,E,D) thoả mãn các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là một tập hữu hạn các bản mã có thể. 3. K (không gian khoá) là tập hữu hạn các khoá có thể. 4. Đối với mỗi k∈ K có một quy tắc mã ek: P → C và một quy tắc giải mã tương ứng dk ∈ D. Mỗi ek: P → C và dk: C → P là những hàm mà: dk(ek (x)) = x với mọi bản rõ x ∈ P. Truyền và bảo mật thông tin 203 I.4. Mô hình truyền tin cơ bản „ Thông điệp X là bản rõ (Plaintext), được mã hóa với khóa K1 Æ văn bản mã hóa Y (Ciphertext) „ Quá trình giải mã chuyển YÆX sử dụng khóa K2 Truyền và bảo mật thông tin 204 I.5. Luật Kirchoff (1835 - 1903) „ Theo luật Kirchoff (1835 - 1903)(một nguyên tắc cơ bản trong mã hóa) thì: toàn bộ cơ chế mã/giải mã trừ khoá là không bí mật đối với kẻ địch. „ Khi đối phương không biết được hệ mã mật đang sử dụng thuật toán mã hóa gi ̀ thì việ̣c thám mã sẽ rất khó khăn. Nhưng chúng ta không thể tin vào độ an toàn của mật mã chỉ dựa vào giả thiết không chắc chắn đối phương không biết thuật toán đang sử dụng. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 52 Truyền và bảo mật thông tin 205 I.6. Phân loại các thuật toán mật mã học Phân loại theo khóa và ứng dụng 1. Hệ mật đối xứng (hay còn gọi là mật mã khóa bí mật): là những hệ mật dung chung một khoá cả trong quá trình mã hoá dữ liệu và giải mã dữ liệu. Do đó khoá phải được giữ bí mật tuyệt đối. 2. Hệ mật mã bất đối xứng (hay còn gọi là mật mã khóa công khai) : Hay còn gọi là hệ mật mã công khai, các hệ mật này dùng một khoá để mã hoá sau đó dùng một khoá khác để giải mã. Các khoá này tạo nên từng cặp chuyển đổi ngược nhau và không có khoá nào có thể suy được từ khoá kia. Khoá dùng để mã hoá có thể công khai nhưng khoá dùng để giải mã phải giữ bí mật. Truyền và bảo mật thông tin 206 I.6. Phân loạ i các thuật toán mật mã học Phân loại theo khóa và ứng dụng: 3. Các thuật toán tạo chữ ký điện tử (Digital Signature Algorithms). Thông thường mỗi hệ chữ ký điện tử có cùng cơ sở lý thuyết với một hệ mã mật khóa công khai nhưng với cách áp dụng khác nhau. 4. Các hàm băm (Hash functions). Các hàm băm là các thuật toán mã hóa không khóa hoặc có khóa va ̀ thường được sử dụng trong các hê ̣ chữ ký điện tử hoăc các hệ mã khóa công khai, mã hóa mật khẩu Truyền và bảo mật thông tin 207 I.6. Phân loại các thuật toán mật mã học Phân loại theo cách xử lý dữ liệu vào: 1. Các thuật toán mã hóa khối (DES , AES ) xử lý bản rõ dưới các đơn vị cơ bản là các khối có kích thước giống nhau. 2. Các thuật toán mã hóa dòng coi bản rõ là một luồng bit, byte liên tục. Truyền và bảo mật thông tin 208 I.6. Phân loại các thuật toán mật mã học Phân loại theo thời gian ra đời: 1. Mật mã cổ điển (là hệ mật mã ra đời trước năm 1970) 2. Mật mã hiện đại (ra đời sau năm 1970) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 53 Truyền và bảo mật thông tin 209 „ Có hai quan điểm : Độ an toàn tính toán và độ an toàn không điều kiện „ Độ an toàn tính toán „ Liên quan đến nỗ lực tính toán để phá một hệ mật „ Hệ mật an toàn về tính toán: thuật toán phá tốt nhất cần ít nhất N phép toán, N rất lớn, thực tế không có hệ mật nào thỏa mãn „ Trên thực tế nếu có một phương pháp tốt nhất phá được hệ mật này nhưng yêu cầu thời gian lớn đến mức không chấp nhận được „ Có thể quy về bài toán khó I.7. Quan điểm về độ an toàn của hệ mật Truyền và bảo mật thông tin 210 „ Độ an toàn không điều kiện „ Hệ mật an toàn không điều kiện nếu nó không thể bị phá ngay cả khi không hạn chế khả năng tính toán ⇒ Độ an toàn không điều kiện của một hệ mật không thể nghiên cứu theo độ phức tạp tính toán mà sẽ dùng lí thuyết xác suất I.7. Quan điểm về độ an toàn của hệ mật Truyền và bảo mật thông tin 211 „ Một số kiến thức cơ bản về lí thuyết xác suất „ Định nghĩa 1: X và Y là các biến ngẫu nhiên „ p(x): xác suất (xs) để X nhận giá trị x „ p(y): xs để Y nhận giá trị y „ p(x, y): xs đồng thời để X nhận giá trị x và Y nhận giá trị y. „ p(x| y): xs để X nhận giá trị x với điều kiện (đk) Y nhận giá trị y. I.9. Quan điểm về độ an toàn của hệ mật Truyền và bảo mật thông tin 212 I.9. Quan điểm về độ an toàn của hệ mật „ X và Y được gọi là độc lập nếu p(x, y) = p(x).p(y), với | x є X và | y є Y. „ Quan hệ giữa xs đồng thời và xs có điều kiện được biểu thị theo công thức sau: p(x,y) = p(x).p(y|x) = p(y).p(x|y) „ Định lý Bayes „ Nếu p(y) > 0 thì: Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 54 Truyền và bảo mật thông tin 213 „ Hệ quả 1 „ X và Y là các biến độc lập khi và chỉ khi: p(x|y) = p(x) với mọi x, y. „ Độ mật hoàn thiện „ Định ngĩa: Một hệ mật có độ mật hoàn thiện nếu: pP(x|y) = pP(x), với mọi x thuộc P, y thuộc C „ Trong đó: pP(x): sx tiên nghiệm để bản rõ xuất hiện ÆÝ nghĩa: đối phương có bản mã cũng không thu nhận thông tin gì về bản rõ I.7. Quan điểm về độ an toàn của hệ mật Truyền và bảo mật thông tin 214 „ Định lý Shannon: Giả sử (P, C, K, E, D) là một hệ mật, khi đo ́ hệ mật đạt đươc độ mật hoàn thiện khi và chỉ khi |K| ≥ |C|. Trong trường hơp |K| = |C| = |P|, hệ mật đạt độ mật hoàn thiện khi và chỉ khi mỗi khoá K được dùng với xác suất bằng nhau, bằng 1/|K| và với mỗi x ∈ P, mỗi y ∈ C có một khoá K duy nhất sao cho eK(x) = y. „ Æ Để có độ mật hoàn thiện cần có khóa rất dàiÆ chuyển giao khóa khó khăn Æ trong thực tế không có độ an toàn không điều kiện mà chỉ an toàn thực tế, tức là tùy thuộc thông tin và thời gian cần bảo mật I.7. Quan điểm về độ an toàn của hệ mật CÁC HỆ Mà KHÓA BÍ MẬT Chương II. Truyền và bảo mật thông tin 216 II.1. Các hệ mã cổ điển 1. Hệ mã đẩy 2. Hệ mã thế vị 3. Hệ mã Affine 4. Hệ mã Vigenere 5. Hệ mã Hill 6. Hệ mã hoán vị 7. Các hệ mã dòng Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 55 Truyền và bảo mật thông tin 217 II.1.1. Hệ mã đẩy (Shift Cipher) „ Giả sử không gian bản rõ P là các thông điệp tạo ra từ bảng chữ cái A, số phần tử của A: |A|=N „ Không gian bản mã C≡P „ Để mã hóa: đánh số thứ tự chữ cái 0..N-1 „ Không gian khóa K=ZN „ Mã hóa: Ek(x) = (x + k) mod N. „ Giải mã: Dk(y) = (y – k) mod N. Truyền và bảo mật thông tin 218 II.1.1. Hệ mã đẩy (shift Cipher) „ Ví du : với k=3 (hoàng đế La Mã Julius Caesar đã sử dụng), k ́ý tự A được thay bằng D, B thay bằng E , ... , W thay bằng Z , ... , X thay bằng A , Y thay bằng B, Z thay bằng C. „ Xâu “ANGLES” sẽ được mã hóa thành “DQJOHV” „ Bài tập: Với k=5, C=QFRGFNYFU, tìm P? „ Cho C=QEHECUYEHI thông điệp là tiếng việt không dấu 252423221312113210 ZYXWNMLDCBA Truyền và bảo mật thông tin 219 II.1.1. Hệ mã đẩy (Shift Cipher) „ Sử dụng thay thế đơn âm nênÆ phụ thuộc tần suất của xuất hiện của ngôn ngữ tự nhiên(một số chữ cái xuất hiện nhiều hơn các chữ khác) Æ người thám mã có thể sử dụng phương pháp thử các ký tự xuất hiện nhiều. „ Không gian khóa là N nhỏ (bảng chữ tiếng anh N=26) Æ có thể thám mã bằng phương pháp vét cạn các khóa Truyền và bảo mật thông tin 220 II.1.2. Hệ mã thế vị „ Cho P =C = Z26; „ K chứa mọi hoán vị có thể của 26 kí hiệu 0,1, . . . ,25 „ Với mỗi phép hoán vị π ∈K , ta định nghĩa: eπ(x) = π(x) và dπ(y) = π-1(y) trong đó π-1 là hoán vị ngược của π. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 56 Truyền và bảo mật thông tin 221 Ví dụ mã thế vị „ Ví dụ một phép hoán vị π: „ Ta có: eπ(D)=A, eπ(J)=Q TBWQZGOPHAYNX MLKJIHGFEDCBA IDJKEUMVCRLFS ZYXWVUTSRQPON Truyền và bảo mật thông tin 222 Ví dụ mã thế vị „ Hàm giải mã là phép hoán vị ngược: „ dπ(A)=D, dπ(Q)=J tPWXZEHOVYRLD MLKJIHGFEDCBA iCAKSUMNQJFGB ZYXWVUTSRQPON Truyền và bảo mật thông tin 223 Không gian khóa mã thế vị „ Số các hoán vị này là 26!, lớn hơn 4 ×1026 là một số rất lớn. Bởi vậy, phép tìm khoá vét cạn không thể thực hiện được, thậm chí bằng máy tính. „ Tuy nhiên, mã thế vị có thể dễ dàng bị thám bằng các phương pháp dò thử theo tần suất ký tự. Truyền và bảo mật thông tin 224 II.1.3. Hệ mã Affine Các định nghĩa „ Giả sử a ∈ Zm, phần tử đảo ứng với phép nhân của a là phần tử a-1∈ Zm sao cho aa-1= a-1a=1 (mod m) „ Định lý về sự tồn tại của phần tử nghịch đảo : Nếu UCLN(a, m) = 1 thì tồn tại duy nhất 1 số b ∈Zm là phân tử nghịch đảo cua a, nghĩa là thỏa mản a.b = (a*b) mod m = 1. „ Tập các số nguyên trong Zm là nguyên tố cùng nhau với m gọi là Zm* „ Số lượng các số nguyên trong Zm là nguyên tố cùng nhau với m ký hiệu là φ(m) (gọi là hàm Euler) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 57 Truyền và bảo mật thông tin 225 Hệ mã Affine „ Không gian bản rõ và bản mã là hình thành từ bảng chữ cái A. Giả sử |A|=N, khi đó không gian khóa được xác định: „ K={(a,b): a, b ∈ ZN, UCLN(a, N)=1} „ Số khóa có thể sử dụng φ(N) *N „ Mã hóa: „ Đánh thứ tự chữ cái 0, 1, .. N-1 „ ek(x)=(a*x+b) mod N (ký tự thứ x chuyển thành ký tự thứ (a*x+b) mod N ) „ Giải mã: „ dk(y)=a-1(y-b) mod N Truyền và bảo mật thông tin 226 Ví dụ hệ mã Affine „ Xét tập chữ cái tiếng Anh (Z26) „ Giả sử K = (7,3). „ Bản rõ: HOT „ Hàm lập mã: ek(x)=7x+3 „ Các số tương ứnglà 7, 14 và 19. Bây giờ sẽ mã hoá: „ Ek(H)= (7 × 7 +3) mod 26 =0 „ Ek(O)=(7 × 14 + 3) mod 26=23 „ Ek(T)=(7 × 19 +3) mod 26 =6 „ =>Bản mã: AXG Truyền và bảo mật thông tin 227 Ví dụ hệ mã Affine „ Giải mã ? „ Bản mã: AXG (tương ứng 0, 23, 6) „ Ta có: 7-1 = 15 (vì 7*15 mod 26=1) =>Hàm giải mã: dk(y)=15(y-3) =15y-45=15y+7 „ (15*0+7) mod 26=7 „ (15*23+7) mod 26=326 mod 26=14 „ (15*6+7) mod 26=19 Truyền và bảo mật thông tin 228 Bài tập „ Mối quan hệ giữa các hệ mã đẩy, mã thế vị và mã Affine? Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 58 Truyền và bảo mật thông tin 229 II.1.4. Mật mã Vigenère „ Lấy tên của nhà mật mã học người Pháp Blaise de Vigenère (1523-1596) „ Thông điệp sử dụng bảng chữ cái A. Các ký tự được đánh số 0, 1, ... N-1, với N =|A| „ Không gian khóa K được xác định: „ Với mỗi số nguyên dương M , khóa có độ dài M là một xâu ký tự có độ dài M , K=k1k2kM. „ Để mã hóa một bản rõ P: chia P ra làm các đoạn có độ dài M, chẳng hạn X=x1x2, xM, khi đó: „ Ek(X) = (x1 + k1, x2 + k2 , , xM + kM ) mod N „ Dk(Y) = (y1 - k1, y2 - k2, , yM - kM) mod N Truyền và bảo mật thông tin 230 Mật mã Vigenère Ví dụ „ A là bảng chữ cái tiếng AnhÆ N=26 „ K=“CIPHER”, „ Bản rõ P=“THISCRYPTOSYSTEMISNOTSECURE” „ Ta có: „ K = 2 8 15 7 4 17, „ P = 19 7 8 18 2 17 | 24 15 19 14 18 23 | 18 19 4 12 8 18 | 13 14 19 18 4 2 | 20 17 4. „ Từ đó: „ C = 21 15 23 25 6 8 | 0 23 8 21 22 14 | 20 1 19 19 12 9 | 15 22 8 25 8 19 | 22 25 19 „ C= “VPXZGIAXIVWOUBTTMJPWIZITWZT” Truyền và bảo mật thông tin 231 Bài tập „ Với tập các ký tự tiếng Anh, cho K=KHOA „ Bản mã c=FPSTMOIOXNHRSUVMKAWNR „ Tìm bản rõ p? Truyền và bảo mật thông tin 232 II.1.5. Hệ mã Hill „ Do Lester S.Hill đưa ra năm 1929 „ Không gian bản rõ và bản mã là bảng chữ cái A. Các chữ cái được đánh số từ 0 đến N-1 (N=|A|) „ Với mỗi số nguyên M, khóa là một ma trận vuông kích thước M, điều kiện là tồn tại ma trận nghịch đảo của K trên ZN. „ Để mã hóa, chia bản rõ thành các xâu có độ dài M. „ Mã hóa: C=P*K „ Giải mã: P=C*K-1 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 59 Truyền và bảo mật thông tin 233 Hệ mã Hill Ví dụ: cho hệ ma Hill có M = 2 (khóa là các ma trận vuông cấp 2) và bảng chữ cái là bảng chữ cái tiếng Anh (N = 26). Cho khóa: K= „ Hay mã hóa xâu P = “HELP” và giải mã ? „ Chia P ra làm P1=“HE” (7,4) và P2=“LP” (11,15) „ Với P1 = (7 4) ta có C1 = P1 * K = (7 4) = (7*3+4*2 7*3+4*5 )= (3 15) = (D P) „ Với P2 = (11 15) ta có C2 = (11,15) =(11 4) = (L E) ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 52 33 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 52 33 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 52 33 Truyền và bảo mật thông tin 234 Hệ mã Hill => Bản mã thu được: C = “DPLE”. Để giải mã, cần tính ma trận nghịch đảo K-1 trên Z26 „ Với K= định thức: det(K) = (k11*k22 – k21*k12) mod N Điều kiện det(K)-1 tồn tại, khi đó: K-1= det(K)-1 * ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 2221 1211 kk kk ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − − 1121 1222 kk kk Truyền và bảo mật thông tin 235 Hệ mã Hill Áp dụng: det(K) = (15 - 6) mod 26 = 9. -> det(K)-1 =3 (vì 9*3=1 (mod 26) ) => K-1= 3* = = Quá trình giải mã như khi mã hóa, sử dụng công thức P=C*K-1 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 324 235 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 3*324*3 23*35*3 ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 920 1715 Truyền và bảo mật thông tin 236 II.1.6. Mã hoán vị „ Ý tưởng của MHV là giữ các ký tự của bản rõ không thay đổi nhưng sẽ thay đổi vị trí của chúng bằng cách sắp xếp lại các ký tự này „ Giả sử không gian bản rõ P là các thông điệp tạo ra từ bảng chữ cái A, số phần tử của A: |A|=N „ Không gian bản mã C≡P „ Cho m là một số nguyên dương xác định nào đó „ Cho K gồm tất cả các hoán vị của {1, . . ., m}. Đối một khoá π ( tức là một hoán vị) ta xác định: „ eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m)) „ dπ(x1, . . . , xm ) = (yπ -1(1), . . . , yπ -1(m)) trong đó π-1 là hoán vị ngược của π Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 60 Truyền và bảo mật thông tin 237 Ví dụ mã hoán vị „ Giải sử m=6 và khóa là hoán vị π =(3, 5, 1, 6, 4, 2): „ Bản rõ SHESELLSSEASHELLSBYTHESEASHORE „ Chia 6 nhóm: SHESEL | LSSEAS | HELLSB | YTHESE | ASHORE „ Mỗi nhóm 6 chữ cái được sắp xếp lại theo phép hoán vị π, ta có: EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS ÆBản mã: EESLSHSALSESLSHBLEHSYEETHRAEOS „ Để giả mã, ta làm tương tự, dùng hoán vị ngược π-1: 246153 654321 425163 654321 Truyền và bảo mật thông tin 238 II.1.7. Các hệ mã dòng „ Trong các hệ mật nghiên cứu ở trên, các phần tử liên tiếp của bản rõ đều được mã hoá bằng cùng một khoá k. Tức xâu bản mã y nhận được có dạng: y = y1y2. . . = ek(x1) ek(x2 ) . . . „ Các hệ mật thuộc dạng này thường được gọi là các mã khối. „ Một quan điểm sử dụng khác là mật mã dòng. Ý tưởng cơ bản ở đây là tạo ra một dòng khoá z = z1z2 . . . và dùng nó để mã hoá một xâu bản rõ x = x1x2 . . . theo quy tắc: y = y1y2. . . = ez1(x1)ez2(x2). . . Truyền và bảo mật thông tin 239 Hoạt động hệ mã dòng „ Giả sử k ∈K là khoá và x = x1x2 là xâu bản rõ. Hàm fi được dùng để tạo zi (zi là phần tử thứ i của dòng khoá) trong đó fi là một hàm của khoá k và i-1 ký tự đầu tiên của bản rõ: zi = fi (k, x1 ,, xi -1 ) „ Phần tử zi của dòng khoá được dùng để mã xi tạo ra yi = eiz(xi). Bởi vậy, để mã hoá xâu bản rõ x1 x2 . . . ta phải tính liên tiếp: z1, y1, z2 , y2 ... „ Việc giải mã xâu bản mã y1y2 có thể được thực hiện bằng cách tính liên tiếp: z1, x1, z2 , x2 ... Truyền và bảo mật thông tin 240 Định nghĩa hệ mã dòng Mật mã dòng là một bộ (P,C,K,L,F,E,D) thoả mãn được các điều kiện sau: 1. P là một tập hữu hạn các bản rõ có thể. 2. C là tập hữu hạn các bản mã có thể. 3. K là tập hữu hạn các khoá có thể (không gian khoá) 4. L là tập hữu hạn các bộ chữ của dòng khoá. 5. F = (f1 f2...) là bộ tạo dòng khoá. Với i ≥ 1 fi : K × P i -1→ L 6. Với mỗi z ∈L có một quy tắc mã ez ∈ E và một quy tắc giải mã tương ứng dz ∈D , ez : P →C và dz : C →P là các hàm thoả mãn dz(ez(x))= x với mọi bản rõ x ∈ P. Ta có thể coi mã khối là một trường hợp đặc biệt của mã dòng trong đó dùng khoá không đổi: Zi = K với mọi i ≥1. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 61 Truyền và bảo mật thông tin 241 Một số dạng đặc biệt của hệ mã dòng „ Mã dòng được gọi là đồng bộ (synchronous) nếu dòng khoá không phụ thuộc vào xâu bản rõ, tức là nếu dòng khoá đựợc tạo ra chỉ là hàm của khoá k. Khi đó ta coi k là một “hạt giống" để mở rộng thành dòng khoá z1z2 „ Một hệ mã dòng được gọi là tuần hoàn (periodic) với chu kỳ d nếu zi+d= zi với số nguyên i ≥ 1. Truyền và bảo mật thông tin 242 Ví dụ phương pháp sinh chuổi khóa 1. Mã Vigenère với độ dài từ khoá m có thể coi là mã dòng tuần hoàn với chu kỳ m. Trong trường hợp này, khoá là K = (k1, . . . km ). Bản thân K sẽ tạo m phần tử đầu tiên của dòng khoá: zi = ki, 1 ≤ i ≤ m. Sau đó dòng khoá sẽ tự lặp lại. „ Các hàm mã và giải mã được dùng giống như các hàm mã và giải mã được dùng trong mã đẩy: ez(x) = x+z và dz(y) = y- z „ Các mã dòng thường được mô tả trong bảng chữ nhị phân: P=C=L=Z2. Æ hàm mã và giải mã chỉ là phép cộng Modulo 2: „ ez(x) = x +z mod 2 và dz(x) = y + z mod 2 Truyền và bảo mật thông tin 243 Ví dụ phương pháp sinh chuổi khóa 2. Ví dụ phương pháp sinh chuổi khóa (đồng bộ): „ Giả sử bắt đầu với (k1, . . , km ) và zi = ki, với 1 ≤ i ≤ m; với i>m: m-1 zi+m = ∑ cj zi+j mod 2 j=0 „ trong đó c0, .., cm-1 ∈ Z2 là các hằng số cho trước. • Ở đây khoá K gồm 2m giá trị k1, . . , km, c0, . . , cm-1. • Véc tơ khởi đầu bất kì (k1, . . , km) khác dãy toàn số 0 tạo nên một dòng khoá có chu kỳ 2m -1 Æ một khoá ngắn sẽ tạo nên một dòng khoá có chu kỳ rất lớnÆ hạn chế việc thám mã Truyền và bảo mật thông tin 244 Ví dụ Giả sử m=4 và chuổi khóa được sinh theo quy tắc: zi+4=(zi+zi+1) mod 2 „ Nếu dòng khoá bắt đầu khác vector (0,0,0,0) Æ dòng khoá có chu kỳ 15. „ Ví dụ bắt đầu bằng véc tơ (1,0,0,0), dòng khoá sẽ là: 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 62 Truyền và bảo mật thông tin 245 Thanh ghi hồi tiếp tuyến tính Thanh ghi hồi tiếp tuyến tính (linear feedback shift register - LFSR) để tạo dòng khoá bằng phần cứng: „ Dùng một bộ ghi dịch có m tầng. „ Véc tơ (k1,.., km) dùng để khởi tạo cho thanh ghi dịch. „ Ở mỗi đơn vị thời gian, các phép toán sau sẽ được thực hiện đồng thời: 1. k1 được tính ra dùng làm bit tiếp theo của dòng khoá. 2. k2,.., km sẽ được dịch một tầng về phía trái. 3. Giá trị mới của km sẽ được tính bằng: m-1 ∑ cjkj+1 j=0 + k2 k3 k4k1 Hình -LFSR cho chuổi khóa zi+4=zi+zi+1 mod 2 Truyền và bảo mật thông tin 246 Mã khóa tự sinh - Autokey „ Cho P = C = K = L = Z26 „ Cho z1 = k và zi = xi-1 (i ≥ 2) „ Với 0 ≤ z ≤ 25 ta xác định: ez(x) = x + z mod 26 dz(y) = y - z mod 26 (x,y ∈ Z26 ) Truyền và bảo mật thông tin 247 Mã khóa tự sinh - Autokey „ Ví dụ: Giả sử khoá là k = 8 và bản rõ là “rendezvous”. Trước tiên ta biến đổi bản rõ thành dãy các số nguyên: 17 4 13 3 4 25 21 14 20 18 „ Dòng khoá như sau: 8 17 4 13 3 4 25 21 14 20 „ Bây giờ ta cộng các phần tử tương ứng rồi rút gọn theo modulo 26: 25 21 17 16 7 3 20 9 8 12 „ Bản mã ở dạng ký tự là: ZVRQHDUJIM „ Để giải mã biến đổi xâu kí tự thành dãy số: 25 21 17 16 7 3 20 9 8 12 Sau đó tính: „ x1 = d8(25) = (25 – 8) mod 26 = 17 „ x2 = d17(21) = (21 – 17) mod 26 = 4 „ Cứ tiếp tục như vậy cho các ký tự tiếp theo. „ Lưu ý: Mã dùng khoá tự sinh là không an toàn do chỉ có 26 khoá. Truyền và bảo mật thông tin 248 II.2. Các hệ mã chuẩn „ II.2.1. Hệ DES „ II.2.2. Các chuẩn mã dữ liệu nâng cao Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 63 Truyền và bảo mật thông tin 249 II.2.1. Hệ DES „ Hệ DES (Data Encryption Standard – chuẩn mã hóa dữ liệu) „ Ban đầu được IBM phát triển „ Lần đầu tiên DES được công bố trong Hồ sơ Liên bang vào ngày 17.3.1975. „ Sau nhiều cuộc tranh luận công khai, DES đã được chấp nhận chọn làm chuẩn cho các ứng dụng vào 5.1.1977. „ Được áp dụng rộng rãi trên toàn thế giới „ Được trộn bởi các phép thế và hoán vị Truyền và bảo mật thông tin 250 Đặc tả DES „ DES mã hoá một xâu bit x của bản rõ độ dài 64 bit bằng một khoá 56 bit. Bản mã nhận được cũng là một xâu bit có độ dài 64. „ Thuật toán tiến hành theo 3 bước: „ B1: Với bản rõ cho trước x, một xâu bit x0 sẽ được xây dựng bằng cách hoán vị các bit của x theo phép hoán vị cố định ban đầu IP. Ta viết: x0 = IP(x) = L0R0, trong đó L0 gồm 32 bit đầu và R0 là 32 bit cuối. Truyền và bảo mật thông tin 251 Thuật toán DES „ B2: Sau đó tính toán 16 lần lặp theo một hàm xác định. Ta sẽ tính LiRi, 1≤ i ≤ 16 theo quy tắc sau: Li = Ri-1; Ri = Li-1 ⊕ f(Ri-1, ki) „ Trong đó: „ ⊕ là phép cộng modulo 2 (loại trừ) của hai xâu bit „ f là một hàm sẽ được mô tả ở sau „ k1, k2, , k16 là các xâu bit có độ dài 48 được tính như 1 hàm của khóa k (ki chính là một phép chọn hoán vị bit trong k). Truyền và bảo mật thông tin 252 Thuật toán DES „ Một vòng của phép mã hóa được mô tả như sau: „ B3: Áp dụng phép hoán vị ngược IP-1 cho xâu bit R16L16, ta thu được bản mã y. Tức là y = IP-1(R16L16) . Hãy chú ý thứ tự đã đảo của L16 và R16 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 64 Truyền và bảo mật thông tin 253 Thuật toán DES „ Mô tả hàm f: „ Hàm f có 2 biến vào: „ Xâu bit A có độ dài 32 „ Xâu bit J có độ dài 48 „ Đầu ra của f là xâu bit có độ dài 32. „ Các bước thực hiện: „ B1: Biến thứ nhất A được mở rộng thành một xâu bit độ dài 48 theo một hàm mở rộng cố định E. E(A) gồm 32 bit của A (được hoán vị theo cách cố định) với 16 bit xuất hiện hai lần. „ B2: Tính E(A) ⊕ J và viết kết quả thành một chuỗi 8 xâu 6 bit là B1B2B3B4B5B6B7B8. Truyền và bảo mật thông tin 254 Thuật toán DES „ B3: Bước tiếp theo dùng 8 bảng S1S2,,S8 ( được gọi là các hộp S ). Với mỗi Si là một bảng 4×16 cố định có các hàng là các số nguyên từ 0 đến 15. Với xâu bit có độ dài 6 (kí hiệu Bi = b1 b2 b3 b4 b5 b6), ta tính Sj(Bj) như sau: „ Hai bit b1b6 xác định biểu diễn nhị phân hàng r của Sj (0≤ r ≤ 3) „ Bốn bit (b2 b3 b4 b5) xác định biểu diễn nhị phân của cột c của Sj (0≤ c ≤ 15). „ Khi đó Sj(Bj) sẽ xác định phần tử Sj(r, c) ; phần tử này viết dưới dạng nhị phân là một xâu bit có độ dài 4 „ Bằng cách tương tự tính các Cj = Sj(Bj) , (1 ≤ j ≤ 8). Truyền và bảo mật thông tin 255 Thuật toán DES „ B4: Xâu bit C = C1 C2 C8 có độ dài 32 được hoán vị theo phép hoán vị cố định P. Xâu kết quả là P(C) được xác định là f(A, J). P Truyền và bảo mật thông tin 256 Thuật toán DES „ Phép hoán vị ban đầu IP: „ Bảng này có ý nghĩa là bit thứ 58 của x là bit đầu tiên của IP(x); bit thứ 50 của x là bit thứ 2 của IP(x) Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 65 Truyền và bảo mật thông tin 257 Thuật toán DES „ Phép hoán vị ngược IP-1: Truyền và bảo mật thông tin 258 Thuật toán DES „ Hàm mở rộng E được xác định theo bảng sau: Truyền và bảo mật thông tin 259 Thuật toán DES „ Tám hộp S: Truyền và bảo mật thông tin 260 Thuật toán DES Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 66 Truyền và bảo mật thông tin 261 Thuật toán DES Truyền và bảo mật thông tin 262 Thuật toán DES „ Phép hoán vị P: Truyền và bảo mật thông tin 263 Thuật toán DES „ Mô tả tính bảng khóa từ khóa k. „ Trên thực tế k là một xâu bit độ dài 64, trong đó có 56 bit khóa và 8 bit kiểm tra tính chẵn lẻ nhằm phát hiện sai. „ Các bit ở các vị trí 8, 16, , 64 được xác định sao cho mỗi byte chứa một số lẻ các số “1”. Bởi vậy, một sai sót đơn lẻ có thể phát hiện được trong mỗi nhóm 8 bit. „ Các bit kiểm tra bị bỏ qua trong quá trình tính bảng khóa. Truyền và bảo mật thông tin 264 Thuật toán DES Các bước tính bảng khóa DES: „ Với một khoá k 64 bit cho trước, ta loại bỏ các bit kiểm tra tính chẵn lẻ và hoán vị các bit còn lại của k theo phép hoán vị cố định PC-1. Ta viết: PC-1(k) = C0D0 „ Với i thay đổi từ 1 đến 16: Ci = LSi(Ci-1) Di = LSi(Di-1) Với LSi là phép chuyển chu trình sang trái 1 hoặc 2 vị trí tùy vào i: „ Đẩy 1 vị trí nếu i=1,2,9 hoặc 16 „ Đẩy 2 vị trí đối với các trường hợp còn lại Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 67 Truyền và bảo mật thông tin 265 Thuật toán DES Truyền và bảo mật thông tin 266 Thuật toán DES „ Các hoán vị PC-1 và PC-2: Truyền và bảo mật thông tin 267 Giải mã DES Ta thấy rằng trong quá trình mã hoá tại vòng i: „ Li=Ri-1 „ Ri=Li-1 xor f(Ri-1,Ki) ( Với f(Ri-1,Ki)=P(E(Ri) xor Ki)) Tức là ta cũng có: „ Ri-1 =Li „ Li-1=Ri xor f(Li,Ki) ÆGiải mã từng khối dữ liệu 64 bit trải qua 16 vòng như quá trình mã hoá tuy nhiên có sự thay đổi nhỏ: „ Đầu vào là bản mã, đầu ra là bản rõ „ Các khoá được sinh ra ngược với quá trình mã hoá, tức là sử dụng lần lượt K16, K15,, K2, K1. Do ở vòng 16, trước khi khối qua hộp IP-1 L16, R16 được hoán đổi nên ở vòng 1 của quá trình giải mã ta cũng phải đổi chỗ hai nửa sau khi khối 64 bit được qua hộp IP, Truyền và bảo mật thông tin 268 Một ví dụ về DES „ Sau đây là một ví dụ về phép mã DES. Giả sử ta mã bản rõ (ở dạng mã hexa - hệ đếm 16): 0 1 2 3 4 5 6 7 8 9 A B C D E F „ Bằng cách dùng khoá 1 2 3 4 5 7 7 9 9 B B C D F F 1 „ Khoá ở dạng nhị phân ( không chứa các bít kiểm tra) là 0001001001101001010110111100100110110111101101111 1111000 „ Sử dụng IP, ta thu được L0 và R0 (ở dạng nhị phân) như sau: L0 = 1100110000000000110010011111111 L1 =R0 = 11110000101010101111000010101010 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 68 Truyền và bảo mật thông tin 269 Một ví dụ về DES E(R0) = 011110100001010101010101011110100001010101010101 K1 = 000110110000001011101111111111000111000001110010 E(R0) ⊕ K1 = 011000010001011110111010100001100110010100100111 S-box outputs = 01011100100000101011010110010111 f(R0,K1) = 00100011010010101010100110111011 L2 = R1 = 11101111010010100110010101000100 E(R1) = 011101011110101001010100001100001010101000001001 K2 = 011110011010111011011001110110111100100111100101 E(R1) ⊕K2 = 000011000100010010001101111010110110001111101100 S-box outputs = 11111000110100000011101010101110 f(R1,K2) = 00111100101010111000011110100011 L3 = R2 = 11001100000000010111011100001001 Truyền và bảo mật thông tin 270 Một ví dụ về DES „ Cuối cùng áp dụng IP-1 vào L16,R16 ta nhận được bản mã hexa là: 8 5 E 8 1 3 5 4 0 F 0 A B 4 0 5 E(R15) = 001000000110101000000100000110100100000110101000 K16 = 110010110011110110001011000011100001011111110101 E(R15) ⊕ K16 = 111010110101011110001111000101000101011001011101 S-box outputs 10100111100000110010010000101001 f(R15,K16) = 11001000110000000100111110011000 R16 = 00001010010011001101100110010101 Truyền và bảo mật thông tin 271 Tranh luận về DES „ Khi DES được đề xuất như một chuẩn mật mã, đã có rất nhiều ý kiến phê phán. „ Một lý do phản đối DES có liên quan đến các hộp S. „ Các hộp S - chứa đựng thành phần phi tuyến của hệ mật là yếu tố quan trong nhất đối với độ mật của hệ thống. „ Tuy nhiên tiêu chuẩn xây dựng các hộp S không được biết đầy đủ. Một số người đã gợi ý là các hộp S phải chứa các "cửa sập" được dấu kín, cho phép Cục An ninh Quốc gia Mỹ (NSA) giải mã được các thông báo nhưng vẫn giữ được mức độ an toàn của DES. Dĩ nhiên ta không thể bác bỏ được khẳng định này, tuy nhiên không có một chứng cớ nào được đưa ra để chứng tỏ rằng trong thực tế có các cửa sập như vậy. Truyền và bảo mật thông tin 272 Tranh luận về DES „ Phản đối xác đáng nhất về DES chính là kích thước của không gian khoá: 256 là quá nhỏ để đảm bảo an toàn thực sự. Nhiều thiết bi chuyên dụng đã được đề xuất nhằm phục vụ cho việc tấn công với bản rõ đã biết. Phép tấn công này chủ yếu thực hiện tìm khoá theo phương pháp vét cạn. „ 1977, Diffie và Hellman đã gợi ý rằng có thể xây dựng một chíp VLSI (mạch tích hợp mật độ lớn) có khả năng kiểm tra được 106khoá/giây. Ætìm toàn bộ khóa trong khoảng 1 ngày. Ước tính chi phí để tạo một máy như vậy khoảng 2.107$. Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 69 Truyền và bảo mật thông tin 273 Tranh luận về DES „ 1993, Michael Wiener đã đưa ra một thiết kế rất cụ thể về máy tìm khoá. Máy này xây dựng trên một chíp tìm khoá, có khả năng thực hiện đồng thời 16 phép mã và tốc độ tới 5×107 khoá/giây. Giá của một khung máy vào khoảng 100.000$ và