1 ページ
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, TRUYỀN VÀ BẢO MẬT Đạ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, 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. Nguyễn Văn Khang – Khoa Tin học, ĐHSP Huế 4. Douglas R. Stinson. Cryptography Theory and practice. CRC nguyenvankhang@dhsphue.edu.vn 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. Truyền và bảo mật thông tin 22 Phần I. Thông tin và truyền thông tin Chương I. MỞ ĐẦU ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 1
2 ページ
Thông tin Thông tin Thông tin là một khái niệm trừu tượng, khó định nghĩa chính Thông tin là cái được truyền từ đối tượng này đến đối tượng xác. Hai định nghĩa về thông tin tiêu biểu: khác để báo một “điều” gì đó. Thông tin chỉ có ý nghĩa khi Thông tin là sự cảm hiểu của con người về thế giới xung quanh “điều” đó bên nhận chưa biết. thông qua sự tiếp xúc với nó. Thông tin xuất hiện dưới nhiều dạng âm thanh , hình ảnh, ... Thông tin là một hệ thống những tin báo và mệnh lệnh giúp loại Những dạng này chỉ là “vỏ bọc” vật chất chứa thông tin. “Vỏ trừ sự không chắc chắn (uncertainty) trong trạng thái của nơi bọc” là phần “xác”, thông tin là phần “hồn”. nhận tin. Nói ngắn gọn, thông tin là cái mà loại trừ sự không Ngữ nghĩa của thông tin chỉ có thể hiểu được khi bên nhận chắc chắn. hiểu được cách biểu diễn ngữ nghĩa của bên phát. Định nghĩa đầu chưa nói lên được bản chất của thông tin. Một trong những phương tiện để diễn đạt thông tin là ngôn Định nghĩa thứ hai nói rõ hơn về bản chất của thông tin và ngữ . được dùng để định lượng thông tin trong kỹ thuật. 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 55 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 66 Mô hình quá trình truyền tin Mô hình quá trình truyền tin Lý thuyết thông tin nghiên cứu quá trình xử lý Kênh truyền có thể được hiểu dưới hai nghĩa: tín hiệu như sau: Dưới nghĩa vật lý: kênh truyền là một hệ thống truyền Đầu vào (input): nhận tín hiệu từ một lĩnh vực tín hiệu (dây dẫn, mạch, sóng, ...) và gây nhiễu tùy cụ thể, tức là tín hiệu xuất hiện theo các ký thao chất lượng của hệ thống. hiệu (symbol) từ một tập hợp cho trước và Dưới nghĩa toán học: kênh truyền là các phân phối theo phân phối xác suất đã biết. xác suất xác định trên lớp các tín hiệu đang xét ở Tín hiệu được truyền đi trên kênh truyền đầu nhận tín hiệu (output). (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 77 Truyền và bảo mật thông tin 88 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 2
3 ページ
Mô hình quá trình truyền tin Mô hình quá trình truyền tin Nguồn tin (information source): Là một tập hợp Các tín hiệu như điện tín, các lệnh điều khiển…là rời rạc theo các tin mà hệ thống truyền tin dùng để lập các 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) bảng tin hay thông báo (message) để truyền và kênh tin được gọi là kênh rời rạc (discrete channel). tin. Các hệ thống liên tục có nhiều nhược điểm như cồng kềnh, Các tín hiệu như âm thanh, hình ảnh.. Là các 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 hàm liên tục theo thời gian, nguồn tin như thế phục được những nhược điểm trên của các hệ thống liên tục gọi là nguồn liên tục (continuous source), các và đặ c biệt đang ngày càng được phát triển và hoàn thiện tin đó được gọi là tin liên tục (continuous dần. information) và kênh tin được gọi là kênh liên Æ Rời rạc hóa các kênh liên tục tục (continuous channel). TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 99 Truyền và bảo mật thông tin 1010 Mô hình quá trình truyền tin Mô hình quá trình truyền tin Rời rạc hóa: Thường một trong hai loại: Nguồn tin liên tục sau khi được lấy mẫu và Rời rạc hoá theo trục thời gian, còn được gọi lượng tử hoá sẽ trở thành nguồn rời rạc . là lấy mẫu (sampling) và rời rạc hoá theo biên Chúng ta học chủ yếu các nguồn rời rạc. độ , 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 1111 Truyền và bảo mật thông tin 1212 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 3
4 ページ
Mô hình quá trình truyền tin Lượng tin biết và chưa biết Lý thuyết thông tin được xét ở đây theo quan Một biến ngẫu nhiên (BNN) X luôn mang một lượng điểm của Shannon. Đối tượng nghiên cứu là tin nào đó. một hệ thống liên lạc truyền tin Nếu X chưa xảy ra thì X có một lượng tin chưa biết. (communication system) như sơ đồ dưới đây: 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 1313 Truyền và bảo mật thông tin 1414 Lượng tin biết và chưa biết 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 Ta thử xét một trường hợp sau: nếu người – không có đầu hình”. Tuy nhiên người tổ chức chơi có thể “ăn gian” bằng chơi lấy ngẫu nhiên 1 đồng tiền và sau đó thực cách sử dụng 2 đồng tiền “Thật- Giả” khác nhau sau: hiện việc tung đồng tiền đó 2 lần. Qua 2 lần Đồng tiền loại 1 (hay đồng tiền thật): đồng chất có 1 mặt tung đồng tiền, ta đếm được số đầu hình xuất có đầu hình. Đồng tiền loại 2 (hay đồng tiền giả ): đồng chất, mỗi mặt hiện. đều có 1 đầu hình. Dựa vào số đầu hình xuất hiện, ta có thể phán Mặc dù người tổ chức chơi có thể “ăn gian” nhưng đoán được người tổ chức chơi đã lấy được quá trình trao đổi 2 đồng tiền cho nhau là ngẫu nhiêu đồng tiền nào. Truyền và bảo mật thông tin 1515 Truyền và bảo mật thông tin 1616 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 4
5 ページ
Lượng tin biết và chưa biết Lượng tin biết và chưa biết Chẳng hạn: Nếu số đầu hình đếm được sau 2 Dưới đây là một số bảng phân phối của bài lần tưng là 1 thì đồng tiền đã lấy được là đồng toán trên: tiền thật. Ngược lại nếu số đầu hình đếm được Gọi BNN X về loại đồng tiền (X=1 hoặc 2). là 2 thì đồng tiền đã lấy được có thể là thật Khi đó phân phối của X có dạng: 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. TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 1717 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 1818 Lượng tin biết và chưa biết Bài tập Đặt BNN Y là BNN về số đầu hình đếm được Tìm phân phối của Y? sau 2 lần tung. Khi đó ta có thể xác định được Tính XS X=1 khi Y=2? 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: Nhớ lại: Định lý Bayes Nếu p(y) > 0 thì: TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 1919 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2020 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 5
6 ページ
Định lý cơ sở của kỹ thuật truyền tin Minh họa kỹ thuật giảm nhiễu Trong “ A New Basic of Information Theory Giả sử, một thông báo được truyền cần (1954)”, Feinstein đã đưa ra định lý sau: “Trên truyền được mã hóa thành dãy số nhị phân một kênh truyền có nhiễu, người ta luôn có thể (0,1). Giả sử 1 bit truyền trên kênh nhiễu với thực hiện một phương pháp truyền sao cho đạt xác suất ¼ được sai số nhỏ hơn sai số cho phép (nhỏ bất Người ta có thể làm giảm sai lầm khi nhận tin kỳ) cho trước đối với kênh truyền.” 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 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2121 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2222 Minh họa kỹ thuật giảm nhiễu Minh họa kỹ thuật giảm nhiễu Sơ đồ truyền tin: 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) TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2323 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2424 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 6
7 ページ
Chi phí phải trả cho kỹ thuật giảm Minh họa kỹ thuật giảm nhiễu 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. TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2525 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2626 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 độ Chương II. 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 ĐỘ ĐO LƯỢNG TIN 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) TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2727 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 7
8 ページ
II.1. Entropy Entropy của một sự kiện Khái niệm entropy 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 Entropy là một đại lượng toán học dùng để đo được đo bởi hàm số h(p) với p ⊆ [0,1]. Hàm h(p) lượng tin không chắc (hay lượng ngẫu nhiên) được gọi là Entropy nếu nó thoả 2 tiên đề toán học của một sự kiện hay của phân phối ngẫu nhiên sau: cho trước. 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). TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 2929 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3030 Tiên đề 3 Tính chất của Entropy Entropy của một phân phối phân phối Xét biến ngẫu nhiên X có phân phối: Nếu một chọn lựa được chia làm 2, Entropy X | x1 x2 x3 … xM gốc phải bằng tổng của các Entropy thành P | p1 p2 p3 … pM Nếu gọi A là sự kiện X=x, (i=1,2,3,..) thì Entropy của A là: phần, ví dụ: i i i 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). Khi đó yêu cầu Tổng quát: TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3131 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3232 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 8
9 ページ
Định lý hàm Entropy Định nghĩa Entropy Chỉ có hàm H dạng sau mới thỏa mản tính chất hàm Entropy của BNN X Entropy n H(X) = −C∑p logp Entropy của một sự kiện: h(p)=-log(p). i i i=1 (Sử dụng C=1 ) Cơ số logarit tương ứng với đơn vị tính, thông dụng Bổ đề: h(p)=-Clog(p). 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ì ∑n H (X ) = − p log p i 2 i Khi đó: h(p)=-log2(p) và i=1 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3333 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3434 Ví dụ Bài toán về cây tìm kiếm nhị phân Xét BNN X co phân bố như sau: 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: (quy ước viết log thay cho log2) TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3535 TruyTruyềền và bn và bảảo mo mậật thông tint thông tin 3636 ThiNganHang.com Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 9
コメント (0)
まだコメントはありません。最初のコメントを書きましょう！