›
›

Bài giảng Truyền và bảo mật thông tin - Nguyễn Văn Khang

pdf 98 trang phuongnguyen 1570
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Truyền và bảo mật thông tin - Nguyễn Văn Khang", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_truyen_va_bao_mat_thong_tin_nguyen_van_khang.pdf

Nội dung text: Bài giảng Truyền và bảo mật thông tin - Nguyễn Văn Khang

  1. Tài liệuthamkhảo 1. Phan Đình Diệu. Lý thuyếtmật mã và An toàn thông tin, ĐạihọcQuốc Gia Hà Nội TRUYỀN VÀ BẢO MẬT 2. NguyễnHữu Tuân, Giáo trình An toàn và bảomật thông tin, Trường đạihọc Hàng hải- Hải Phòng THÔNG TIN 3. TS. Lê Quy ếtThắ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ễnVă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 2 PhầnI. Thông tin và truyềnthôngtin Chương I. MỞ ĐẦU 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ệmtrừutượng, khó định nghĩachính „ Thông tin là cái đượctruyềntừđốitượng này đến đốitượng xác. Hai định nghĩavề thông tin tiêu biểu: khác để báo một“điều”gìđó. Thông tin chỉ có ý nghĩakhi „ Thông tin là sự cảmhiểucủa con ngườivề thế giới xung quanh “điều” đó bên nhậnchưabiết. thông qua sự tiếpxúcvới nó. „ Thông tin xuấthiệndướinhiềudạng âm thanh , hình ảnh, „ Thông tin là mộthệ 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ậtchấtchứathôngtin. “Vỏ trừ sự không chắcchắn (uncertainty) trong trạng thái củanơi bọc” là phần “xác”, thông tin là phần“hồn”. nhận tin. Nói ngắngọn, thông tin là cái mà loạitrừ sự không „ Ngữ nghĩa của thông tin chỉ có thể hiểu được khi bên nhận chắcchắn. hiểu đượccáchbiểudiễnngữ nghĩacủa bên phát. „ Định nghĩa đầuchưanóilên đượcbảnchấtcủa thông tin. „ Một trong những phương tiện để diễn đạt thông tin là ngôn „ Định nghĩathứ hai nói rõ hơnvề bảnchấtcủ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ưutrữ . Môi trường truyền/lưutrữđượcgọi chung là môi trường chứa tin hay kênh tin. Truyền và bảo mật thông tin 5 Truyềnnvàb và bảoom mật thông tin 6 Mô hình quá trình truyềntin Mô hình quá trình truyềntin „ Lý thuyết thông tin nghiên cứu quá trình xử lý „ Kênh truyềncóthểđượchiểudướihainghĩa: tín hiệunhư sau: „ Dướinghĩavật lý: kênh truyềnlàmộthệ thống truyền „ Đầu vào (input): nhận tín hiệutừ mộtlĩnh vực tín hiệu (dây dẫn, mạch, sóng, ) và gây nhiễutùy cụ thể, tức là tín hiệuxuấthiện theo các ký thao chấtlượng củahệ thống. hiệu (symbol) từ mộttậphợpchotrướcvà „ Dướinghĩatoánhọc: kênh truyềnlàcácphânphối theo phân phốixácsuất đãbiết. xác suấtxácđịnh trên lớp các tín hiệu đang xét ở „ Tín hiệu đượctruyền đi trên kênh truyền đầunhận tín hiệu(output). (channel) và có thể bị nhiễucũng theo một phân phốixácsuất nào đó. Truyền và bảo mật thông tin 7 Truyền và bảo mật thông tin 8 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ềntin Mô hình quá trình truyềntin „ Nguồn tin (information source): Là mộttậphợp „ Các tín hiệunhưđiện tín, các lệnh điềukhiển là rờirạc theo thời gian, nguồntin như thế gọilànguồnrờirạc (discrete các tin mà hệ thống truyền tin dùng để lậpcác source), các tin đó đượcgọilàtin rờirạc (discrete information) bảng tin hay thông báo (message) để truyền và kênh tin đượcgọilàkênh rờirạc (discrete channel). tin. „ Các hệ thống liên tục có nhiềunhược điểmnhư cồng kềnh, không hiệuquả , và chi phí cao. „ Các tín hiệunhư âm thanh, hình ảnh Là các „ Các hệ thống truyềntin rờirạc có nhiều ưu điểmhơn, khắc hàm liên tụctheothời gian, nguồntin như thế phục đượcnhững nhược điểmtrêncủacáchệ thống liên tục gọilànguồn liên tục (continuous source), các và đặ c biệt đang ngày càng được phát triểnvàhoànthiện tin đó đượcgọilàtin liên tục (continuous dần. information) và kênh tin đượcgọilàkênh liên Æ Rờirạc hóa các kênh liên tục tục (continuous channel). Truyềnnvàb và bảoom mật thông tin 9 Truyền và bảo mật thông tin 10 Mô hình quá trình truyềntin Mô hình quá trình truyềntin „ Rờirạc hóa: Thường mộttronghailoại: „ Nguồn tin liên tụcsaukhi đượclấymẫuvà „ Rờirạc hoá theo trụcthời gian, còn đượcgọi lượng tử hoá sẽ trở thành nguồnrờirạc . là lấymẫu (sampling) và rờirạc hoá theo biên „ Chúng ta họcchủ yếu các nguồnrờirạc. độ , còn đượcgọilàlượng tử hoá (quantize). Lấymẫu Lượng tử hóa Truyền và bảo mật thông tin 11 Truyền và bảo mật thông tin 12 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ềntin Lượng tin biếtvàchưabiết „ Lý thuyết thông tin đượcxétởđây theo quan „ Mộtbiếnngẫu nhiên (BNN) X luôn mang mộtlượng điểmcủa Shannon. Đốitượng nghiên cứulà tin nào đó. mộthệ thống liên lạctruyềntin „ NếuX chưaxảyrathìX cómộtlượng tin chưabiết. „ NếuX đãxảyrathìlượng tin về biếnX coinhưđã (communication system) như sơđồdưới đây: biết hoàn toàn. „ „ Nếubiết thông tin củamột BNN X thông qua BNN Y đãxảy ra thì ta có thể nói: chúng ta chỉ biếtmộtphần lượng thông tin củaX đótrêncơ sở biếtY. Truyền và bảo mật thông tin 13 Truyền và bảo mật thông tin 14 Lượng tin biếtvàchưabiết Lượng tin biếtvàchưabiết „ Ta xét ví dụ trò chơitungmột đồng tiền“cóđầuhình „ Ta thử xét mộttrường hợpsau: nếungười – không có đầuhình”. chơilấyngẫu nhiên 1 đồng tiềnvàsauđóthực „ Tuy nhiên ngườitổ chứcchơicóthể “ăn gian” bằng cách sử dụng 2 đồng tiền“Thật- Giả” khác nhau sau: hiệnviệc tung đồng tiền đó2 lần. Qua 2 lần „ Đồng tiềnloại1 (hay đồng tiềnthật): đồng chấtcó1 mặt tung đồng tiền, ta đếm đượcsốđầuhìnhxuất có đầu hình. „ Đồng tiềnloại2 (hay đồng tiềngiả ): đồng chất, mỗimặt hiện. đềucó1 đầu hình. „ Dựavàosốđầuhìnhxuấthiện, ta có thể phán „ Mặcdùngườitổ chứcchơicóthể “ăn gian” nhưng quá trình trao đổi2 đồng tiềnchonhaulàngẫunhiêu đoán đượcngườitổ chứcchơi đãlấy được đồng tiền nào. Truyền và bảo mật thông tin 15 Truyền và bảo mật thông tin 16 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 4
  5. Lượng tin biếtvàchưabiết Lượng tin biếtvàchưabiết „ Chẳng hạn: Nếusốđầuhìnhđếm được sau 2 „ Dưới đây là mộtsố bảng phân phốicủa bài lầntưng là 1 thì đồng tiền đãlấy đượclàđồng toán trên: tiềnthật. Ngượclạinếusốđầuhìnhđếm được „ Gọi BNN X về loại đồng tiền (X=1 hoặc2). là 2 thì đồng tiền đãlấy đượccóthể là thật „ Khi đóphânphốicủaX códạng: hay cũng có thể là giả. Như vậy, ta đãnhận đượcmộtphần thông tin về loại đồng tiềnqua sốđầuhìnhđếm đượcsau2 lần tung. Truyềnnvàb và bảoom mật thông tin 17 Truyềnnvàb và bảoom mật thông tin 18 Lượng tin biếtvàchưabiết Bài tập „ Đặt BNN Y là BNN về sốđầuhìnhđếm được Tìm phân phốicủaY? sau 2 lần tung. Khi đótacóthể xác định được Tính XS X=1 khi Y=2? phân phốicủaY với điềukiệnxảyracủaX trong 2 trường hợp sau: Nhớ lại: „ Định lý Bayes „ Nếu p(y) > 0 thì: Truyềnnvàb và bảoom mật thông tin 19 Truyềnnvàb và bảoom mật thông tin 20 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 5
  6. Định lý cơ sở củakỹ thuậttruyềntin Minh họakỹ thuậtgiảm nhiễu „ Trong “ A New Basic of Information Theory „ Giả sử, một thông báo đượctruyềncần (1954)”, Feinstein đã đưarađịnh lý sau: “Trên truyền được mã hóa thành dãy số nhị phân một kênh truyềncónhiễu, ngườitaluôncóthể (0,1). Giả sử 1 bit truyềntrênkênhnhiễuvới thựchiệnmộtphương pháp truyềnsaochođạt xác suất¼ đượcsaisố nhỏ hơnsaisố cho phép (nhỏ bất „ Ngườitacóthể làm giảmsailầmkhinhậntin kỳ) cho trước đốivớikênhtruyền.” bằng cách truyềnlặplại 1 bit vớisố lẻ lầnVí dụ: truyềnlặplại 3 cho 1 bit cầntruyền Truyềnnvàb và bảoom mật thông tin 21 Truyềnnvàb và bảoom mật thông tin 22 Minh họakỹ thuậtgiảm nhiễu Minh họakỹ thuậtgiảm nhiễu „ Chứng minh, vớicáchtruyềnnàysaisố nhỏ hơn¼: „ Sơđồtruyềntin: „ 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 đượclàsaivà „ Xi =0 nếu bit thứ i nhận đượclàđúng. „ Theo giả thiết ban đầucủa kênh truyền thì phân phốixácsuấtcủaXi có dạng Bernoulli b(1/4): Xi 1 0 P 3/4 1/4 „ GọiY ={X1 + X2 + X3 } là tổng số bit nhậnsaisau3 lầntruyền lặp cho 1 bit =>này Y tuân theo phân phốiNhị thức B(p,n), với p=1/4 (xác suấttruyềnsaimột bit) và q =3/4 (xác suấttruyền đúng 1 bit) Truyềnnvàb và bảoom mật thông tin 23 Truyềnnvàb và bảoom mật thông tin 24 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 6
  7. Chi phí phảitrả cho kỹ thuậtgiảm Minh họakỹ thuậtgiảm nhiễu nhiễu „ Theo cách thứclặplạinhư trên, ta có thể giảm sai lầm bao nhiêu cũng được(lặpcàngnhiều thì sai càng ít), nhưng thờigiantruyềncũng tănglênvàchi phítruyềncũng sẽ tăng theo. Truyềnnvàb và bảoom mật thông tin 25 Truyềnnvàb và bảoom mật thông tin 26 Khái niệmvề dung lượng kênh truyền „ Cầnphảixácđịnh một thông số cho truyềntin để đảmbảosaisố chấpnhận đượcvàđồng thờitốc độ truyềncũng không quá chậm. Chương II. „ Khái niệm “dung lượng” cho phép xác định tốc độ truyềntối đacủamỗi kênh truyền. Do đó, dựavào dung lượng kênh truyền, ngườitacóthể chỉ ra tốc độ ĐỘ ĐO LƯỢNG TIN truyềntin đồng thờivớimộtphương pháp truyềncó sai số cho phép. „ Quá trình truyềntin cầncóquátrìnhsinhmãbằng thiếtbị sinh mã (Coding device/ Encoder) và quá trình giảimãnhờ thiếtbị giải mã (Decoding device/ Decoder) Truyềnnvàb và bảoom mật thông tin 27 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 7
  8. II.1. Entropy Entropy củamộtsự kiện „ Khái niệm entropy „ Giả sử có mộtsự kiệnA cóxácsuấtxuấthiệnlàp. Khi đó, ta nói A có mộtlượng tin không chắcchắn „ Entropy là một đạilượng toán học dùng để đo được đobởihàmsố h(p) vớip ⊆ [0,1]. Hàm h(p) lượng tin không chắc(hay lượng ngẫu nhiên) đượcgọilàEntropy nếunóthoả 2 tiên đề toán học củamộtsự kiệnhay của phân phốingẫ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ếuA vàB làhaisự kiện độclập nhau, có xác suấtxuấthiệnlầnlượtlàpA và pB. Khi đó, p(A,B) = pA.pB nhưng h(A,B) = h(pA) + h(pB). Truyềnnvàb và bảoom mật thông tin 29 Truyềnnvàb và bảoom mật thông tin 30 Tiên đề 3 Tính chấtcủa Entropy Entropy củamộtphânphối phân phối „ Xét biếnngẫu nhiên X có phân phối: „ Nếumộtchọnlựa được chia làm 2, Entropy X | x x x x 1 2 3 M gốcphảibằng tổng của các Entropy thành P | p p p p 1 2 3 M phần, ví dụ: „ NếugọiAi là sự kiệnX=xi, (i=1,2,3, ) thì Entropy củaAi là: h(Ai)= h(pi) „ Gọi Y=h(X) là hàm ngẫunhiêncủaX vànhận các giá trị là dãy các Entropy củacácsự kiệnX=xi,tức là Y=h(X)={h(p1), h(p2), , h(pn)}. „ Entropy củaX chínhlàkỳ vọng toán họccủa Y=h(X) có dạng: „ H(X)=H(p1, p2, p3, ,pn) = p1h(p1)+p2h(p2)+ +pnh(pn). „ Khi đóyêucầu „ Tổng quát: Truyềnnvàb và bảoom mật thông tin 31 Truyềnnvàb và bảoom mật thông tin 32 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ớithỏamản tính chấthàm „ Entropy của BNN X Entropy n „ Entropy củamộtsự kiện: h(p)=-log(p). H (X ) = −C∑ pi logpi i=1 (Sử dụng C=1 ) „ Cơ số logarit tương ứng với đơnvị tính, thông dụng „ Bổđề: h(p)=-Clog(p). „ Cơ số 2 thì đơnvị tính là bit. „ Cơ số 3 thì đơnvị tính là trits. „ Cơ số e thì đơnvị tính là nats. „ Cơ số 10 thì đơnvị tính Hartleys. n „ Nếutatínhđơnvị bit thì H ( X ) = −∑ pi log 2 pi i=1 „ Khi đó: h(p)=-log2(p) và Truyềnnvàb và bảoom mật thông tin 33 Truyềnnvàb và bảoom mật thông tin 34 Ví dụ Bài toán về cây tìm kiếmnhị phân „ Xét BNN X co phân bố như sau: „ Giả sử, tìm 1 trong 5 ngườicótênbiếttrướcsẽ xuất hiện theo phân phốisau: „ Sơđồdùng câu hỏi đúng/sai xác định tên: „ (quy ướcviết log thay cho log2) Truyềnnvàb và bảoom mật thông tin 35 Truyềnnvàb và bảoom mật thông tin 36 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 9
  10. Bài toán về cây tìm kiếmnhị phân Bài tập „ Theo sơđồtrên: „ Để tìm x1, x2, x3 vớixácsuấttương ứng là 0.2, 0.3, 0.2 ta chỉ cầntốn2 câuhỏi. „ Để tìm x4, x5 vớixácsuấttương ứng 0.15, 0.15 thì ta cần3 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ợpnàyxấpxỉ H(X) nên đây là số câu hỏi trung bình tối ưu Truyềnnvàb và bảoom mật thông tin 37 Truyềnnvàb và bảoom mật thông tin 38 II.2. Các tính chấtcủa Entropy Các tính chấtcơ bản „ Các tính chấtcơ bản Minh họatínhchất1: „ 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ệutăng Truyềnnvàb và bảoom mật thông tin 39 Truyềnnvàb và bảoom mật thông tin 40 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 10
  11. Các tính chấtcơ bảncủa Entropy Các tính chấtcơ bảncủa Entropy „ Minh họatínhchất2: Minh họatínhchất3: Xét con xúc sắc6 mặtvới phân bố XS: „ Trong trường hợp2 biếnngẫu nhiên X, Y độc lậpcóphânphối đềuvới BNN X có M sự kiện và BNN Y có L sự kiện. „ Gọi f(M), f(L) lầnlượtlàEntropy của X, của Y. Nếutagomsự kiệnx1,x2,x3 thành sự kiệnx123 (XS 55%) và x5, x6 thành x56 (XS 20%), ta có bảnh Theo tính chất2 của Entropy ta có phân bố X*: „ f(ML)=f(M)+f(L) Kiểm tra: H(X) =H(p1+p2+p3, p4 , p5+p6) (BT cho SV) Truyềnnvàb và bảoom mật thông tin 41 Truyềnnvàb và bảoom mật thông tin 42 Định lý cực đạicủaentropy Định lý cực đạicủaentropy „ Định lý: H(p1, p2, ,pM)≤ log(M) „ Chứng minh bổđề Trong đó: đẳng thứcxảy ra khi và chỉ khi p1= = pM= 1/M „ Theo toán họctacóthể chứng minh „ Chứng minh ln(x)≤ x-1 vớix>0 vàđẳng thức đúng khi x=1. „ Bổđề: cho 2 bộ {p1, p2, ,pM} và {q1, q2, ,qM} là các bộ số dương bấtkỳ và „ Đặtx= qi/pi Suy ra ln(qi/pi)≤ qi/pi –1 (và đẳng thức đúng khi qi=pi vớimọii). Khi đótacó Đẳng thứcxảyrakhipi=qi với ∀i=1, ,M. Truyềnnvàb và bảoom mật thông tin 43 Truyềnnvàb và bảoom mật thông tin 44 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 11
  12. Định lý cực đạicủaentropy Định lý cực đạicủaentropy „ Mặtkháclnx= log2x / log2e (2) „ Chứng minh định lý „ Từ (1) và (2)=> „ Lấyqi=1/M, từ bổđềta có: „ Đẳng thứcxảyrakhipi=qi vớimọii „ Đẳng thứcxãyrakhipi=1/M vớimọii đpcm Truyềnnvàb và bảoom mật thông tin 45 Truyềnnvàb và bảoom mật thông tin 46 II.3. Entropy của nhiềubiến Ví dụ Entropy của nhiềubiến Định nghĩa: Giả sử X và Y là 2 biếnngẫu nhiên cho trướcvớipịj „ Cho 2 BNN X và Y độclập nhau và có các phân phối: = p(X=xi,Y=yj) (∀ i=1, ,M và j=1, ,L). „ Khi đó, Entropy H(X,Y) có dạng: „ Lậpphânphốicủa P(X,Y) „ Tổng quát „ H(X,Y) =H(0.125, 0.25, 0.125, 0.125, 0.25, 0.125)=2.5 (Bit) Truyềnnvàb và bảoom mật thông tin 47 Truyềnnvàb và bảoom mật thông tin 48 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 12
  13. Entropy có điềukiện Ví dụ Entropy có điềukiện „ Xét biếnngẫu nhiên X và biếnngẫu nhiên Y có tương quan „ Entropy củaY với điềukiệnX=xi (i=1, ,M) nhau, các phân phối: được định nghĩalà: „ Entropy củaY với điềukiệnX xảyrađược „ 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 định nghĩalà: =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ềnnvàb và bảoom mật thông tin 49 Truyềnnvàb và bảoom mật thông tin 50 Quan hệ giữa H(X,Y) với H(X) và Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độclập H(Y) khi X, Y độclập Định lý 1: H(X,Y)≤ H(X)+H(Y) Chứng minh định lý 1: và đẳng thứcxảy ra khi X, Y độclập „ Ta có Hệ quả: „ H(X1, , Xn) ≤ H(X1)+ +H(Xn) „ H(X1, Xn; Y1, ,Yn) ≤ H(X1, Xn)+ H(Y1, ,Yn) Truyềnnvàb và bảoom mật thông tin 51 Truyềnnvàb và bảoom mật thông tin 52 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 13
  14. Quan hệ giữa H(X,Y) với H(X) và Quan hệ giữa H(X,Y) với H(X) và H(Y) khi X, Y độclập H(Y) khi X, Y tương quan „ Đặtq =p(x )p(y )=> q >=p(x , y ) ij i j ij i j Đị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ứcxảy ra khi và chỉ khi X và Y độclập nhau. „ Đẳng thứcxảy ra khi p(xi, yj)=pij =qij =p(xi)p(yj) hay X , Y độclậ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ứcxảyrakhiX, Y độclập (đpcm) Truyềnnvàb và bảoom mật thông tin 53 Truyềnnvàb và bảoom mật thông tin 54 Chứng minh định lý 2 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). Tương tự ta có: H(X,Y)=H(Y)+H(X/Y) Truyềnnvàb và bảoom mật thông tin 55 Truyềnnvàb và bảoom mật thông tin 56 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 14
  15. II.4. Đolượng tin (mesure of Bài tập information) „ Ta xét ví dụ trò chơitungmột đồng tiền“cóđầuhình – không có đầuhình”. „ Tuy nhiên ngườitổ chứcchơicóthể “ăn gian” bằng cách sử dụng 2 đồng tiền“Thật- Giả” khác nhau sau: „ Đồng tiềnloại1 (hay đồng tiềnthật): đồng chấtcó1 mặt có đầu hình. „ Đồng tiềnloại2 (hay đồng tiềngiả ): đồng chất, mỗimặt đềucó1 đầu hình. „ Mặcdùngườitổ chứcchơicóthể “ăn gian” nhưng quá trình trao đổi2 đồng tiềnchonhaulàngẫunhiêu Truyềnnvàb và bảoom mật thông tin 57 Truyềnnvàb và bảoom mật thông tin 58 Các bảng phân phốicủa bài toán trên: Nhận xét dựa theo entropy „ Gọi BNN X về loại đồng tiền (X=1 hoặc2). Từ các bảng phân phối trên, ta có: „ Đặt BNN Y là BNN về sốđầuhìnhđếm đượcsau2 lầntung „ Khi đótacócácbảng phân phối: „ Entropy của Y: H(Y) = H(0.125, 0.25, 0.625) = 1.3 (bit) „ Entropy củaY khibiếtX 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) „ Ta có thể tính dễ dàng phân phốicủaY như sau: „ Vậy, H(Y) > H(Y/X) Truyềnnvàb và bảoom mật thông tin 59 Truyềnnvàb và bảoom mật thông tin 60 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 15
  16. Định nghĩalượng tin Ví dụ lượng tin Định nghĩa: Lượng tin (hay thông lượng) của X khi Y xảyralà lượng chênh lệch giữalượng không chắcchắncủaX và „ Xét lạivídụ trên, ta có lượng tin về X khi biết lượng không chắcchắncủa X khi Y xảy ra có quan hệ vớiX. Y là „ Ký hiệu: I(X/Y) = H(X)-H(X/Y) là lượng tin đãbiếtvề X khi Y đãxảyra. „ I(X/Y)= I(Y/X)= H(Y) – H(Y/X) = 1.3 – „ Chú ý: ta luôn có I(X/Y) = I(Y/X) 0.75=0.55 (bit). „ Ta có thể hiểu khái niệm này như sau: „ X và Y là 2 biếnngẫu nhiên nên chúng có 2 lượng tin không chắcchắn. NếuX và Y độclập, thì X xảy ra không ảnh hưởng tới Y nên ta vẫn không biếtgìthêm về X và X giữ nguyên lượng không chắcchắncủa nó. Trong trường hợpnày lượng tin về X khi Y xảyralàbằng 0. „ Nếu Y có tương quan vớiX thìkhiY xảyratabiết hoàn toàn về Y và mộtphần thông tin về X. Phần thông tin đóchínhlàlượng tin đãbiếtvề X nhưng vẫn chưabiếthếtvề X. Bài toán ởđây là tính lượng tin đãbiếtvề X khi Y xảyra. Truyềnnvàb và bảoom mật thông tin 61 Truyềnnvàb và bảoom mật thông tin 62 Bài tập Bài tập „ Thựchiệnmột phép thử con xúc sắc đồng „ Có hai chiếchộp đựng bi, hộpthứ nhấtchứa chất đồng thờivớimột đồng tiềncũng đồng hai bi đỏ, một bi vàng, một bi xanh. Hộpthứ chất. Trong đó, con xúc sắccócácmặt điểm hai chứamột bi vàng và một bi xanh. Lấyngẫu từ 1 đến6, đồng tiềnmộtmặtcóđầuhìnhvà nhiên mộtviênbi tronghộpthứ nhấtbỏ vào mặt kia không có đầu hình. Trướctiênthử con hộpthứ hai, sau đólấyngẫu nhiên một viên bi xúc sắc, nếusốđiểm ≤ 4 thì tung đồng tiền từ hộpthứ hai. Hãy tính lượng tin về màu viên mộtlần, ngượclại thì tung đồng tiềnhailần. bi bốc đượctronghộpthứ nhất khi biết thông Tính lượng tin về sốđiểmcon xúcsắc khi biết tin về màu sắc viên bi bốc đượctronghộpthứ thông tin về sốđầuhìnhđếm được. hai. Truyềnnvàb và bảoom mật thông tin 63 Truyềnnvàb và bảoom mật thông tin 64 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 16
  17. Bài tập „ An và Bình hẹngặp nhau. Nếutrời không mưa thì khã năng An đến điểmhẹn là 90% còn Chương III. Bình là 60%. Nếutrờimưathìkhãnăng An đến điểmhẹnlà30% cònBìnhlà40%. Giả sử SINH Mà TÁCH ĐƯỢC thờitiếtchổ An và Bình là như nhau và xác suấtmưasẽ là 60%. Hãy tìm lượng tin về thời tiết khi biếtsố lượng người đến điểmhẹn Truyềnnvàb và bảoom mật thông tin 65 III.1. Khái niệmvề mã tách được III.1. Khái niệmvề mã tách được Đặtvấn đề bàitoánsinhm㠄 Ta xét BNN X={x1, x2, ,xn} có phân phối{p1, p2, , pn} được „ Giả sử nguồntin X xuấthiệnvàđược ghi lại thông qua một quan sát liên tụcvàđộclập. thiếtbịđặcbiệt. Chẳng hạnnhưảnh được ghi lạibằng máy „ Dãy các giá trị nhận đượcgọi là thông báo (Message) có dạng ảnh, âm thanh được ghi lạibằng máy ghi âm, Qua kênh xi1xi2 xim. truyền, những thông tin này cầnphải được mã hóa cho phù „ TậphợpA={a1, a2, , aD} là tậphợpkýtự mã (Code hợp. Để có thể mã hóa ngườitacầnmộtbảng chữ cái gồm Characters) hay là bảng chữ cái (Code Alphabet) dùng để các chữ cái quy định trước(chẳng hạnbảng chữ cái la tinh, sinh mã. bảng mã nhị phân, ). Mỗigiátrị của X sau đó đượcm㠄 Mộtgiátrị xi ∈ X được gán bởimột dãy hữuhạn các ký tự mã dướidạng một dãy hữuhạncácchữ cáivàtagọi dãy hữu đượcgọilàtừ mã (Code word). hạncácchữ cái gán cho mộtgiátrị củax làmộttừ mã. „ Tậphợpgồmtấtcả các từ mã gán cho tấtcả các giá trị củaX đượcgọilàbộ mã hay bảng mã (Code). „ Các từ mã phải khác nhau từng đôi một. Truyềnnvàb và bảoom mật thông tin 67 Truyềnnvàb và bảoom mật thông tin 68 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 17
  18. Khái niệmvề bảng mã không tách III.1. Khái niệmvề mã tách được được „ Bảng mã không tách đượclàbảng mã mà khi mã hóa thông „ Bộ mã đượcgọilàtáchđược (Decypherable báoMsgtasẽ nhận đượcmột dãy các từ mã ws, và khi giải Coding) nếunhư từ mộtdãycáckýtự mã mã dãy các từ mãwsthìtacóthể nhận được nhiều thông báo nhận được liên tục(được mã hóa từ bộ mã Msg khác nhau. „ Ví dụ: Xét biếnngẫu nhiên X={x , x , x , x } có bảng mã này), ta luôn luôn giảimãđượcvớikếtquả 1 2 3 4 W={w1=0, w2=1, w3=01, w4=10}. duy nhấtlàdãycácgiátrị gốccủa X. „ Giả sử thông báo nguồncónội dung: x2x3x4x3x2x1. Khi đó dãy mã tương ứng viếttừ W: 101100110. „ Nếugiảimãtừ trái qua phải: x2x1x2x2x1x1x2x2x1. „ Nếugiảimãtừ phải qua trái, ưutiênđộ dài lớn: x2x3x4x3x4 „ Nếugiảimãtừ trái qua phải, ưutiênđộ dài lớnx4x2x4x3x4 Truyềnnvàb và bảoom mật thông tin 69 Truyềnnvàb và bảoom mật thông tin 70 Giảithuậtkiểm tra tính tách đượccủabảng mã Ví dụ bảng mã tách được (Sardinas, Patterson và Abramson) „ Bướckhởitạo: Gán tậphợpS=W. „ Xét biếnngẫu nhiên X={x1, x2} có bảng mã tương ứng 0 W={w1=0, w2=01}. „ Bước 1: xác định tậphợpS1 từ S0: Phương pháp giảimã đượcsử dụng như sau: chỉ giảimãkhi „ -KhởitạoS1={} nào đãnhận được đoạnmãvới độ dài bằng độ dài củatừ m㠄 -Với ∀ wi, wj ∈ S0, ta xét: nếuwi=wjA(wj là tiềntố củawi) hoặcwj=wi dài nhất. A (wi là tiềntố củawj) thì thêm A (phầnhậutố) vào S1. „ „ Giả sử dãy mã nhận được là: 0010000101001. Bước k: xác định tậphợpSk (k≥2) từ tậphợpS0 và Sk-1: „ -Khởitạo: S ={} „ Sử dụng phương pháp giảimãtrêntanhận đượcduynhất k „ -Với ∀ w ∈ S và ∀ v ∈S , ta xét: nếuw=v A(v là tiềntố củaw) dãy thông báo gốc: i 0 j k-1 i j j i hoặcvj=wi A thì thêm A vào Sk. x1x2x1x1x1x2x2x1x2. „ Điềukiện để dừng vòng lặp: „ Nhận xét: Bảng mã tách đượclàbảng mã mà trong đó không „ NếuS={} thì dừng và kếtluậnbảng mã tách được(k≥1). tồnlạitừ mã này là mã khóa từ mã khác, tuy nhiên vẫncóthể k „ Nếutồntạitừ mã wi trong Sk hay Sk ∩S0 ≠ ∅ thì dừng và kếtluậnbảng tồntạitừ mã này là tiềntố (phần đầu) củatừ mã kia. mã không tách được. „ NếuSk=St<k thì dừng và kếtluậnbảng mã tách được(k≥1). Truyềnnvàb và bảoom mật thông tin 71 Truyềnnvàb và bảoom mật thông tin 72 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 18
  19. III.2. Quan hệ giữamãtáchđượcvà Bảng mã prefix độ dài m㠄 Bảng mã prefix là bảng mã không tồntạitừ mã này Định lý Kraft là tiềntố củatừ mã khác. „ GọiX={x1, x2, , xM} là biếnngẫu nhiên chứa các giá trị cần truyềncóphânphốilàP={p1, p2, , pM}. „ Ví dụ 1: Bảng mã W={w =10; w =101; w =100} 1 2 3 „ A={a1, a2, ,aD} là bộ ký tự sinh mã có D chữ cái (D đượcgọi không phảibảng mã prefix vì w1 là tiềntố củaw2 và là cơ số sinh mã). w3. „ Giá trị xi được mã hóa thành từ mã wi có độ dài là ni. „ ĐặtN={n, n , ,n } là tậphợp độ dài các từ mã. „ Ví dụ 2: Bảng mã W={w1=0, w2=100, w3=101, 1 2 M w4=11} là bảng mã prefix vì không tồntạitừ mã này „ Phát biểu định lý Kraft: Điềukiệncầnvàđủ để tồntạibảng mã prefix với độ dài N={n , n , ,n } là: là tiềntố củatừ mã khác. 1 2 M „ Bảng mã prefix luôn là bảng mã tách được Truyềnnvàb và bảoom mật thông tin 73 Truyềnnvàb và bảoom mật thông tin 74 Minh họa định lý Kraft Cây bậcD cỡ k. „ Ví dụ 1: Bộ mã W={w1, w2, w3} vớiM=3; n1=1; n2=2; Định nghĩa: Cây bậcD cỡ k là cây có hệ thống nút, n3=3; D=2: cạnh thỏa điềukiệ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. Î Tồntạibảng mã prefix „ Nút cuối cùng (Nút lá) cách nút gốc không vượtquák cạnh. „ Ví dụ 2: Bộ mã W={w1, w2, w3} vớiM=3; n1=1; n2=1; n3=2; D=2: Î Không tồntạibảng mã prefix Cây bậcD=2 cở k=3 Truyềnnvàb và bảoom mật thông tin 75 Truyềnnvàb và bảoom mật thông tin 76 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 19
  20. Sinh mã cho các nút củacâybậcD Sinh mã cho các nút củacâybậcD cỡ K cỡ K „ Để đơngiản hóa: mỗi nút (trừ nút gốc) đượckýhiệubởi dãy ký hiệucủa nút cha làm tiềntố + mộtkýtự bổ sung lấytừ tập Tính chất: hợp {0, 1, 2, , D-1} thay cho bảng chữ cái A={a , a , , a }. 1 2 D „ Các nút (trừ nút gốc) củacâyđều đượcmã 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ướclà tiềntố. k „ Tổng số các nút lá bằng D Truyềnnvàb và bảoom mật thông tin 77 Truyềnnvàb và bảoom mật thông tin 78 Thủ tụctạomãprefix: Ví dụ tạomãprefix: „ Xét N={n1, n2, ,nM} và cơ số sinh mã là D: „ Xét bảng mã thỏa M=3, D=2, n1=1, n2=2, n3=3. „ Bước 1: Ta xếpthứ tự n1≤ n2 ≤ ≤ nM, xây dựng cây + Kiểmtra: bậcD cỡ k=n và sinh mã cho các nút . M + Sinh mã cho nút „ Bước2: Chọnnútbấtkỳ trên cây có độ dài n1 gán cho từ mã w1 và xóa tấtcả các nút kề sau nó. + Chọnmã: „ Bước3: Lặplạicácbước2 đốivớiviệcchọncáctừ •Chọnw1=0 , cắtbỏ các nút mã còn lạiw2, , wM ứng vớin2, , nM. con củanútw1. => Bảng mã W={w1, w2, , wM} là bảng mã prefix. •Chọnw2=10, cắtbỏ các nút con củanútw2. •Chọnw3=111 Truyềnnvàb và bảoom mật thông tin 79 Truyềnnvàb và bảoom mật thông tin 80 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 20
  21. III.3. Tính tối ưucủa độ dài mã Bảng mã tối ưutuyệt đối/ tương đối Định lý Shannon „ Bảng mã đượcgọilàtối ưutuyệt đốikhi „ Bảng mã tối ưutương đốikhi: )Nếumãtáchđược không tối ưuthìđộ dài củanósẽ lớnhơn nhiềuso vớicậndưới, còn nếumãtáchđượctối ưuthìđộ dài trung bình củanógầnvớicậndưới. Truyềnnvàb và bảoom mật thông tin 81 Truyềnnvàb và bảoom mật thông tin 82 Điềukiệnnhậnbiếtmộtbảng mã tối Bảng mã tối ưutuyệt đối/ tương đối ưu Ví dụ: xét biếnngẫu nhiên X={x1, x2, x3, x4} „ Định lý (vớiD=2): „ Có phân phối: P={1/2, 1/4, 1/8, 1/8} „ Xác suấtpi càng lớnthìđộ dài ni củatừ mã wi càng nhỏ. „ Có bảng mã W={w1=0,w2=10,w3=110, w4=111} „ Giả sử p1≥ p2 ≥ ≥ pM thì 2 từ mã tương ứng với2 giátrị có xác suất nhỏ nhấtcóđộ dài mã bằng nhau: n =n . „ Độ dài trung bình từ mã: M-1 M „ Trong các từ mã có độ dài bằng nhau và cùng bằng nM (dài nhất) thì tồntạiítnhất2 từ mã có M-1 ký tựđầugiốngnhauvàkýtự thứ M khác nhau. „ Ví dụ, xét bảng mã: „ Entropy của X: H(X)= H(0.5, 0.25, 0.125, 0.125) = 0.5 +0.5 + W={w =0, w =100, w =101, w =1101, w =1110} 0.375 + 0.375 =1.75 1 2 3 4 5 Bảng mã trên không phảilàbảng mã tối ưuvì2 từ mã w4, w5 „ Log D=1. 2 có độ dài lớnnhất =4 ký tự nhưng 3 ký tựđầu khác nhau. „ Ta có: =>Bảng mã tối ưu tuyệt đối Truyềnnvàb và bảoom mật thông tin 83 Truyềnnvàb và bảoom mật thông tin 84 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 21
  22. Phương pháp sinh mã Huffman Phương pháp sinh mã Huffman Định lý Huffman Phương pháp sinh mã Huffman vớiD=2: „ Giả sử X có phân phốixácsuấtvớithứ tự giảmdần sau: „ Giả sử X có phân phốixácsuấtvớithứ tự giảmdần sau: X | x x x 1 2 M X | x x x P | p1≥ p2 ≥ ≥ pM 1 2 M „ Giả sử bảng mã củaX làW={w1, w2, , wM-1, wM}. P | p1≥ p2 ≥ ≥ pM „ ĐặtxM-1,M={xM-1, xM} có xác suấtlàpM-1,M=pM-1+pM. và X* = { x1, x2, , xM- „ Khởitạo: ĐặtM=M , } có phân phối sau: 0 1 M „ Bước1: X* | x1 x2 xM-2 xM-1,M „ ĐặtxMo-1, Mo={xMo-1,xMo } P | p p p p 1 2 M-2 M-1,M „ Sắpxếplại theo thứ tự giảmdầnXS tađược dãy phân phốimớicóM0- „ 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ã 1 phầntử p1,p2, pMo-2, PMo-1, Mo nhận được theo quy tắc sau là mã tối ưu cho X đó: „ Bước2: „ wi=w*i với 1 ≤ i ≤ M-2 „ Lưuvết: wMo-1 = wMo-1, Mo + “0” wMo = wMo-1, Mo + “1” „ wM-1=w*M-1,M + “0”. „ GiảmM0: M0=M0-1, nếuM0<=2 thì kết thúc, nếu không quay lạibước1 „ wM =w*M-1,M + “1”. Truyềnnvàb và bảoom mật thông tin 85 Truyềnnvàb và bảoom mật thông tin 86 Ví dụ phương pháp sinh mã Huffman Bài tập „ Hãy mã hoá nguồn S = {x , x , x , x , x , x } vớicácxácsuấtp 1 2 3 4 5 6 i „ Lậpbảng mã nhị phân Huffman cho các phân lầnlượt là 0,3; 0,25; 0,2; 0,12; 0,08; 0,05 phối sau: „ Lậpbảng mã nhị phân Huffman dùng để mã hóa đoạnvănbản: “thoi the thi thoi thi the thoi thi thoi the” Bài tập: tínhvà so sánh: và Truyềnnvàb và bảoom mật thông tin 87 Truyềnnvàb và bảoom mật thông tin 88 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 22
  23. IV.1. Kênh truyềnrờirạc không nhớ Khái niệm kênh truyềnrờirạc không nhớ Chương IV. „ Kênh truyềnrờirạc: truyềntuầntự các ký tự KÊNH TRUYỀN độclập nhau (hay truyềntừng ký tự một), „ “Không nhớ” ởđây là chỉ xét mốiquanhệ giữa ký tự truyềnvàkýtự nhận đượctương ứng, không xét đếnmối quan hệ giữakýtự nhận đượcvớikýtự nhận đượctrước đó. Truyềnnvàb và bảoom mật thông tin 90 Mô hình vậtlý Mô hình toán học „ Ta gọi: „ ΓX={x1, x2, , xM} là bộ ký tự sinh mã ởđầutruyền (input). „ ΓY={y1, y2, ,yL} là bộ ký tự giảimãởđầunhận (output). Các qui ước: „ BiếnngẫunhiênX lấygiátrị (đã mã hóa) trên ΓX và „ -X: làbiếnngẫu nhiên có giá trị cầntruyền ởđầutruyền. có phân phốip(X=x)=p(x ) với i=1, ,M. „ -Y: làbiếnngẫu nhiên chứagiátrị có thể nhận được ởđầunhận. i i „ - ΓX: là bảng chữ cái sinh mã ởđầutruyền. „ BiếnngẫunhiênY lấygiátrị (giải mã) trên ΓY và có „ - ΓY: là bảng chữ cái giảimãởđầunhận. phân phốixácsuấtcóđiềukiện: „ -X, Y, ΓX, ΓY: đềuhữuhạnvàrờirạc. „ -Truyềnrờirạctừng ký tự và nhậncũng rờirạctừng ký tự. „ P(Y=yj|X=xi)=p(yj/xi)=pij với j=1, ,L. „ -Kýtự nhận sau không phụ thuộc vào ký tự nhậntrước. Truyềnnvàb và bảoom mật thông tin 91 Truyềnnvàb và bảoom mật thông tin 92 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 23
  24. Mô hình toán học Mô hình toán học „ Tính phân phối đầunhận: „ GọiA=[pij] là ma trậntruyền tin hay mô hình truyềntin củakênhtruyềnrờirạ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 đượcgiátrị yj khi đãtruyền giá trị xi. „ Vậyp(yj)= P’X.Aj (1) „ Tính phân phối đầunhận: „ Tổng quát: P’Y = P’X.A (2) „ Trong đó „ -Aj là cộtthứ j củaA „ -P’X = [p(x1), p(x2), ., p(xM)]. „ -P’Y = [p(y1), p(y2), ., p(yM)]. Truyềnnvàb và bảoom mật thông tin 93 Truyềnnvàb và bảoom mật thông tin 94 Ví dụ xác định phân phối đầunhận Lượng tin trên kênh truyền „ Cho ma trận truyền tin: Xét ma trậntruyềntin 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) „ Xác suấttruyền: p(x1)=0.5 và p(x2)=p(x3)= 0.25. „ H(Y/X=x ) = H(0.5, 0.2, 0.3)= 1.49 (bit) „ Ta tìm phân phốicủa Y : 1 „ H(Y/X=x2) = H(0.3, 0.5, 0.2)= 1.49 (bit) „ Ta có: P’X =(0.5, 0.25, 0.25) „ H(Y/X=x ) = H(0.2, 0.3, 0.5)= 1.49 (bit) „ Áp dụng công thức(1) ở trên ta được: 3 „ H(Y/X)=p(x ).H(Y/X=x )+p(x ).H(Y/X=x )+p(x ).H(Y/X=x ) = „ p(y ) = P’ .A = 0.5*0.5+ 0.25*0.3+0.25*0.2 =0.375 1 1 2 2 3 3 1 x 1 1.49 (bit) „ p(y2) = P’x.A2 = 0.5*0.2+ 0.25*0.5+0.25*0.3= 0.3 „ Lượng thông tin truyền trên kênh: I (X/Y)= I (Y/X)= H(Y) - „ p(y3) = P’x .A3 = 0.325 H(Y/X) = 0,09 (bit) ⇒ P’Y =(0.375, 0.3, 0.325) Truyềnnvàb và bảoom mật thông tin 95 Truyềnnvàb và bảoom mật thông tin 96 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 24
  25. Định nghĩa dung lượng kênh truyền IV.2. Các dạng kênh truyền „ Dựa vào ma trậntruyền tin A, ta có thể dễ dàng tính Kênh truyềnkhôngmấttin 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) „ Mô hình: từ tậphợp các giá trị có thể nhận „ Ta có I(X/Y)= H(Y)-H(Y/X), trong đó: được ởđầunhậnY={y1, y2, , yL} đượcphân „ H(Y)= H(P’ .A) phụ thuộcvàoP . X X thành M nhóm Bi tương ứng với các giá trị xi ở „ H(Y/X) phụ thuộcvàoP X đầutruyềnvàxácsuất để truyềnx với điều „ Vậy: I(Y/X) phụ thuộc hoàn toàn vào PX và do đó i ∈ I(Y/X) có thểđạtMax vớiPX xác định nào đó. kiện đãnhậnyj là p(X= xi/Y=yj Bi)=1 ( vớiM „ Ta định nghĩa dung lượng kênh truyền(bit) là L). Đặctrưng: H(Y/X)=0. Có nghĩalà lượng tin chưabiếtvề Y khi truyềnX bằng 0 hay khi truyềnX thìtabiếtsẽ nhận đượcY. „ Đặctrưng: H(X/Y)=0 Æ biếtY thìbiếtX =>C=log2L =>I(X/Y)=H(X)=> C=log2M Truyềnnvàb và bảoom mật thông tin 99 Truyềnnvàb và bảoom mật thông tin 100 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 25
  26. Kênh truyền không nhiễu Kênh truyền không sử dụng được. „ Mô hình: là sự kếthợpcủa kênh truyềnxácđịnh và „ Mô hình: Là kênh truyềnmàgiátrịđầunhận kênh truyền không mất thông tin, truyềnnàosẽ nhận luôn độclậpvớigiátrịđầutruyền, vớimọi được đúng ký tựđó. phân bố xác suất đầutruyền. Đầutruyền Đầunhận „ Đặctrưng: H(X/Y) =H(X); H(Y/X)= H(Y) x1 Æ x1 x2 Æ x2 „ Dung lượng: C=0 „ Ví dụ xM Æ xM „ Đặctrưng: H(X/Y)=H(Y/X)=0 „ Dung lượng: C=log2L=log2M Truyềnnvàb và bảoom mật thông tin 101 Truyềnnvàb và bảoom mật thông tin 102 Kênh truyền đốixứng Dung lượng kênh truyền đốixứng „ Mô hình: là kênh truyềnmàma trậntruyềntin „ Xác định C=Max(I(X/Y))=Max(H(Y)-H(Y/X)) có đặc điểm sau: „ H(Y/X)= „ Mỗidòngcủama trậnA làmột hoán vị của phân M M L x H (Y / x ) = H (Y / x ) x = H (Y , x ) = − p' log p' phốiP={p’1, p’2, , p’L} ∑ i i i ∑ i i ∑ j j i=1 i=1 j=1 „ Mỗicộtcủama trậnA làmột hoán vị củaQ={q’1, q’2, , q’M} Æ „ Ví dụ: Truyềnnvàb và bảoom mật thông tin 103 Truyềnnvàb và bảoom mật thông tin 104 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 26
  27. Kênh truyền đốixứng IV.3. Lược đồ giảim㠄 Chú ý: trường hợp kênh 1 bit với nhiễu β Đặtvấn đề bài toán giảim㠄 Ma trậntruyềntin: „ Phân tích yêu cầugiảimã: „ Khi truyềngiátrị xi, ta sẽ nhận đượcyj. Đốivới kênh truyền không nhiễuthìyj chính là xi. Đốivớikênhtruyền có nhiễuthì yj có thể khác xi. Do đótacần tìm cách giảimãyj về giá trị xi khi kênh truyềncónhiễu. „ Dung lượng: „ Phép phân hoạch các giá trịởđầunhận: C „ C=1+(1-β)log(1-β)+βlogβ „ Phép phân hoạch tập các giá trịởđầunhậpyj ∈ Y là phép = 1- H(β, 1-β) 1 phân chia tập Y thành các tập con Bi sao cho: β 0.5 1 Truyềnnvàb và bảoom mật thông tin 105 Truyềnnvàb và bảoom mật thông tin 106 Ví dụ bài toán giảimã Sơđồtruyềntin „ Cho tậpcáctừ mã truyền X và tập các dãy n bit nhận đượcY „ Nguồn phát tín hiệu (hay thông báo) vớivậntốc R (tín hiệu/giây). như sau „ Tín hiệu được mã hóa từ bộ ký tự mã. „ Tín hiệu mã hóa đượctruyềntrênkênhvớivậntốcV (kýtự/giây) „ X={0000, 0101, 1110, 1011} „ Tín hiệutruyềntrênkênhcóthể bị nhiễuvớixácsuất P(e). „ Y={0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, „ Trước khi nhận, tín hiệu mã hóa đượcgiải mã theo mộtphương thứctối „ 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111} ưuvàđộ chính xác cao nhấtcóthể có. „ 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ậnyj = 0011 thì giảimãvề x4 = 1011 vì yj ∈ B4. Truyềnnvàb và bảoom mật thông tin 107 Truyềnnvàb và bảoom mật thông tin 108 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 27
  28. Sơđồtruyềntin Ví dụ „ Bài toán đặtraởđây: tìm giải pháp tạomãsao „ Giả sử kênh truyềntừng bit với V=1 bit/s, nguồn phát thông báo vớitốc độ R=2/5 bit/s (R<V). cho sai sốđầunhậncóxácsuấtnhỏ hơn ε bất „ Xét từng khoảng n = 5 giây. nR kỳ „ Tậphợpcáctínhiệukhácnhaulà2 = 4. „ (ε < P(e)) đồng thờivới đồng bộ hóa: vậntốc „ Giả sử 4 tín hiệulàm1, m2, m3, m4. phát thông báo ở nguồnR vàvậntốctruyền „ Số bit đượcphátralànR=2 bit vàmột tín hiệudạng m đượckếtcấubởimộtdãycácbit. tải ≤ V i „ Quá trình mã hóa các tín hiệum1, m2, m3, m4 cầnchú ý là: mỗimi cần đượcmãhóavớisố bit tối đalà nV=5 bit. Trong 5bit dùng 2 bit mã hóa tín hiệuvà3 bit sửalỗi Truyềnnvàb và bảoom mật thông tin 109 Truyềnnvàb và bảoom mật thông tin 110 Các khái niệmcơ bản: Các dạng sai số 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ậphợpgồmS từ mã với độ dài mỗitừ mã đềubằng n và đượckýhiệu là x(1), , x(s). „ Lược đồ giảimã:là một hàm gán cho một dãy n ký tự nhận đượcyj mộttừ mã củabộ mã W ={w1, w2, , ws}. Ký hiệu: g(yj) = wi „ Lược đồ giảimãtối ưu: là lược đồ giảimãsaochotổng xác suấttruyền sai là nhỏ nhất hay tổng xác suấttruyền đúng là lớnnhất. Nghĩa là: khi nhậnyj thì ta giảimãvề w*I sao cho: P(wi*/yj) = Max{P(wk/yj)} ∀wk ∈ W Truyềnnvàb và bảoom mật thông tin 111 Truyềnnvàb và bảoom mật thông tin 112 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 28
  29. Phương pháp xây dựng lượt đồ giải Minh họa xây dựng lược đồ giảimã mã tối ưu tối ưu „ Theo công thức Bayes: „ Cho ma trậntruyền tin A và xác suất ởđầu Ta có: P(wk/yj) = (p(wk).p(yj/wk)) / p(yj) với(∀wk ∈ W) „ Từđịnh nghĩalược đồ giảimãtối ưu: truyềnnhư sau: ⇒ 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ước0: KhởitạocácBi = φ (∀i) „ Bướclặp: xét vớimọiyj ∈Y + Tính: p(w ).p(y /w ) ; p(w ).p(y /w ); ; p(w ).p(y /w ) 1 j 1 2 j 2 M j M „ Vớip(x1)=1/2; p(x2)=p(x3)=1/4. + So sánh các giá trị tínhtrênvàchọngiátrị w*i sao cho p(w*i).p(yj/w*i)= Max {p(wk).p(yj/wk)} (∀wk ∈ W) „ Hãy xây dựng lược đồ giảimãtối ưu. + Bi = Bi + {yj} và g(yj) = w*i. Truyềnnvàb và bảoom mật thông tin 113 Truyềnnvàb và bảoom mật thông tin 114 Minh họa xây dựng lược đồ giảimã Minh họa xây dựng lược đồ giảimã tối ưu tối ưu Xây dựng lược đồ giảimãtối ưu: „ Lược đồ giảimã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 „ Tính các xác suấttruyềnsai: „ Xác suấttruyềnsaitừ mã x1: p(e/x1)=∑p(Y=yj ∉B1/X=x1)=p(y3/x1) =1/6 Do p(x1).p(y1/x1) lớnnhấtÆ B1=B1 +{y1} => B1={y1}. „ Xác suấttruyềnsaitừ mã x2: p(e/x2)= ∑ p(Y=yj ∉B2/X=x2) = p(y1/x2) + „ Bước2: xéty2, ta tính: p(y2/x2) =1/3+1/6=1/2 p(x1).p(y2/x1)= 1/2 . 1/3 = 1/6; p(x2).p(y2/x2)= 1/4 . 1/6 = 1/24 „ Xác suấttruyềnsaitừ mã x3: p(e/x3)= ∑ p(Y=yj ∉B3/X=x3) = p(y1/x3) + p(x3).p(y2/x3)= 1/4 . 1/2 = 1/8 p(y2/x3) + p(y3/x3) =1/6+1/3+1/2=1 Do p(x1).p(y2/x1) lớnnhấtÆ B1=B1 +{y2} => B1={y1, y2}. „ Xác suấttruyền sai trung bình:p(e)= ∑p(X=xi)p(e/xi) „ Bước3: Xéty3, ta tính: =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 = p(x1).p(y3/x1)= 1/2 . 1/6 = 1/12 ; p(x2).p(y3/x2)= 1/4 . 1/2 = 1/8 11/24 p(x3).p(y3/x3)= 1/4 . 1/3 = 1/12 „ Xác suấttruyềnsailớnnhất:pm(e) = Max{ p(e/x1), p(e/x2), p(e/x3)} = 1 Do p(x2).p(y3/x2) lớnnhất Æ B2=B2 +{y3} => B2={y3}. „ Kếtquả: Phân hoạch: B1={y1, y2}, B2={y3} và B3={}. Truyềnnvàb và bảoom mật thông tin 115 Truyềnnvàb và bảoom mật thông tin 116 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 29
  30. Bài tập Bài tập Truyềnnvàb và bảoom mật thông tin 117 Truyềnnvàb và bảoom mật thông tin 118 V.1. Số học modulo „ Định nghĩa: Giả sử a và b là các số nguyên và m là mộtsố nguyên dương. Khi đótaviếta ≡ b (mod m) Chương V. nếua-b chiahếtchom . Mệnh đề a ≡ b (mod m) đượcgọilà"a đồng dư với b theo modulo m". Số SỬA LỖI nguyên m đượcgọ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 đượcrút gọntheomodulo m. Truyền và bảo mật thông tin 120 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 30
  31. Số học modulo Số học modulo - các tính chất „ Số học đồng dư modulo m: Zm là tập(0, , m- 1. Phép cộng là đóng: với ∀ a, b ∈ Zm, a+b ∈ Zm 1) với hai phép toán là +và×. 2. Phép cộng là giao hoán, tứclàvới ∀ a,b ∈ Zm, a+b = b+a „ Việccộng và nhân trong Zm đượcthựchiện giống như cộng và nhân các số nguyên ngoại 3. Phép cộng là kếthợp, tứclàvới ∀ a,b,c ∈ Zm, trừ một điểmlàcáckếtquảđượcrútgọntheo (a+b)+c = a+(b+c) modulo m. 4. 0 là phầntử trung hòa của phép cộng, có nghĩalà với ∀ a ∈ Zm, a+0 = 0+a = a „ VD: 11 × 5 trong Z ? 26 5. Phầntử nghịch đảocủa phép cộng củaphầntử bất „ 11 x 5=55; 55 =2* 26+ 3, kì (a ∈ Zm ) là m-a, nghĩalàa+(m-a) = (m-a)+a= 0 với ∀a ∈ Zm . „ vậy 11 x 5 = 3 trong Z26 Truyền và bảo mật thông tin 121 Truyền và bảo mật thông tin 122 Số học modulo - các tính chất Mộtsố lưuý 6. Phép nhân là đóng , tứclàvới ∀ a,b ∈ Zm , ab ∈ Zm „ a (mod N)= (a+N) (mod N) . Ví dụ: -4 (mod 26)=-4+26 (mod 26)=22 (mod 26) 7. Phép nhân là giao hoán , nghĩalàvới ∀ a,b ∈ Zm , „ Các tính chấtphépmod ab = ba „ (a+b) mod N=(a mod N + b mod N) mod N 8. Phép nhân là kếthợp, nghĩalàvới ∀ a,b,c ∈ Zm , „ ab mod N=(a mod N)(b mod N) mod N (ab)c = a(cb) „ Ví dụ: 9. 1 là phầntử trung hòa của phép nhân, tứclàvới „ (36 +46) mod 26 = (10+20) mod 26=4 10 bấtkỳ a ∈ Zm, a×1 = 1×a = a „ 3 mod 26= 10. Phép nhân có tính chất phân phối đốivới phép =(33x33x33x3) mod 26 cộng, tứclàđốivới ∀ a,b,c ∈ Zm , (a+b)c = =(27 mod 26)3 .3 mod 26=3 (ac)+(bc) và a(b+c) = (ab) + (ac) Truyền và bảo mật thông tin 123 Truyền và bảo mật thông tin 124 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 31
  32. V.2. Mguyên lý khoảng cách nhỏ Các phép toán Modulo 2 nhất hamming Khoảng cách Hamming „ Các phép toán trong Modulo 2 (+,-): „ Định nghĩa: cho v1 và v2 là 2 dãy nhị phân dài n bit, ta gọi „ 0 + 1 = 1 + 0 = 1; khoảng cách Hamming giữa2 dãyv1,v2 là số bit tương ứng khác nhau. Ký hiệu: d(v1, v2). „ 0 – 1 = 1 – 0 = 1; „ Ví dụ: „ 1 + 1 = 0 v1=10101010 v2=10101111 „ 1 – 1 = 0; „ Ta nhậnthấyrằng bit thứ 6 và bit thứ 8 giữagiữav1 và v2 là „ Phép cộng và trừ giống nhau, thường đượcký khác nhau nên số bit tương ứng khác nhau giữav1 và v2 là 2. Do đó, ta nói khoảng cách Hamming giữav và v là 2 hay hiệu 1 2 d(v1, v2) = 2 Truyềnnvàb và bảoom mật thông tin 125 Truyềnnvàb và bảoom mật thông tin 126 Kênh truyền đốixứng nhị phân và Kênh truyền đốixứng nhị phân và lược đồ giảimãtối ưu lược đồ giảimãtối ưu „ Xét kênh truyền đốixứng nhị phân. Giả sử ta truyền „ Theo lược đồ giảimãtối ưutacó: khinhậnvj thì giảimãvề các dãy từ mã nhị phân có độ dài n bits vớixácsuất w*i sao cho: truyền sai 1 bit là β. 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 đềunên: „ GọiW = {w1, w2, ,ws} là tậps từ mã truyền, độ dài p(w /v ) → Max ⇔ p(v /w ) → Max mỗitừ mã đềubằng n bit. k j j k „ Vậy: để tìm w*i sao cho P(w*i/vj) = Max{P(wk/vj)} ta chỉ cần tìm „ V = {v1, v2, ., vn} là tập các dãy n bit nhận được ở w*i sao cho P(vj/ w*i) = Max{P(vj/ wk)} (chỉ dựa vào ma trân cuối kênh với W có phân phối đều, xác suất để nhận truyềntin A) vj khi truyềnwi là p(vj/wi) = pij. Truyềnnvàb và bảoom mật thông tin 127 Truyềnnvàb và bảoom mật thông tin 128 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 32
  33. Quan hệ giữaxácsuấtgiảimãvà khoảng cách Hamming Nguyên lý Hamming „ Giả sử nhận đượcv: Định lý: trên kênh truyền đốixứng nhị phân vớiS từ „ Xét 2 từ mã w1 và w2 cầnchọn để giải mã cho v, độ dài từ mã mã ởđầutruyềncóđộ dài n bit, lược đồ giảimãtối là n: ưucóthể thay thế bằng lược đồ giảimãtheokhoảng „ Gọid1=d(v, w1), d2=d(v,w2). cách Hamming với nguyên lý: nếunhận được v, ta sẽ d1 n-d1 „ Xác suất đế nhận v khi truyềnw1: p(v/w1)= β (1−β) giảiraw* sao cho d2 n-d2 I „ Xác suất đế nhận v khi truyềnw2: p(v/w2)= β (1−β) 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. „ Nếu nhiễu0 1 „ Vậyv đượcgiảivề w4 vì khoảng cách Hamming giữa „ Do đó: P(v/w )>p(v/w ) ⇔ d <d 1 2 1 2 v và w4 là nhỏ nhất. „ Nhận xét: xác suấtgiải mã càng lớnthìkhoảng cách Hamming càng nhỏ. Truyềnnvàb và bảoom mật thông tin 129 Truyềnnvàb và bảoom mật thông tin 130 V.3. Bổđềvề tự sửalỗivàcận Bài tập Hamming „ 1. Cho bộ mã W={w1=000000, w2=101010, „ Đặtvấn đề: mộttừ mã w dài n bit khi được w3=111000, w4=111111} và nhận được dãy truyềntuầntự từng bit có thể sai e bit. Vấn đề v=010111, khi đógiảimãvề từ mã nào? Vì đặt ra là khoáng cách (Hamming) giữacáctừ sao? mã và sai số e quan hệ với nhau như thế nào để có thể phân biệttốtnhất đồng thờitấtcả „ 2. Cho bộ mã W={w1=000000, w2=010101, các từ mã? Bổđềsau xác định quan hệ này. w3=000111, w4=111111} và Nhận được dãy v=010111, khi đógiảimãvề từ mã nào? Vì sao? Truyềnnvàb và bảoom mật thông tin 131 Truyềnnvàb và bảoom mật thông tin 132 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 33
  34. Các dạng lỗi Bổđề: Xét bộ mã W={w , w , , w } gồmcós từ mã nhị phân dài n bit và 1 số Giả sử ta truyềntừ mã n bit wi ∈ W ( 1 ≤ i ≤ s) và nhận được 1 2 s n nguyên dương e. dãy n bit vj ( 1≤ j ≤ 2 ). 1. Nếud(wi, wj) ≥ 2e+1 (với ∀ i≠j) Khiđó: tấtcả các dãy nhận được v có số Các loạilỗicóthể phát hiện sau: bit lỗi ≤ e thì v có thể tựđiềuchỉnh (hay tự sửalỗi). „ Lỗicóthể tựđiềuchỉnh: 2. Nếud(wi, wj) ≥ 2e (với ∀ i≠j) Khiđó: tấtcả các dãy nhận được v có số bit lỗi v đượcgiảimãvề w*i thì ta chỉ phát hiệnlàv cólỗi và không thể tựđiềuchỉnh được. i j k j 3. Ngượclại; „ Lỗichỉ phát hiện không điềuchỉnh được: Nếu v có số chữ số bit lỗi ≤ e và có thể tựđiềuchỉnh thì d(wi, wj)≥ 2e+1 (với Trong trường hợp này tồntạitừ mã w*i và w i sao cho ∀ i≠j). d(v , w* )= d(v , w )=Min d(v , w ) với ∀w ∈ W Nếu v có số chữ số bit lỗi ≤ e-1 tựđiềuchỉnh đượcvàtấtcả các tín hiệuvới j i j i j k k số chữ số bit lỗi ≤ e được phát hiện thì khoảng cách giữacáctừ mã luôn => v không thể giải mã chính xác. j thỏa: d(wi,wj) ≥ 2e (với ∀ i≠j). „ Lỗi không phát hiện được: giảimãraw*i nhưng khác vớiwi đãtruyền. Truyềnnvàb và bảoom mật thông tin 133 Truyềnnvàb và bảoom mật thông tin 134 Chứng minh Cận Hamming n 1. Giả sử: d(wi, wj) ≥ 2e+1 với ∀ i≠j. Nếuw vàw’có „ Đặtvấn đề: trong tổng số 2 dãy nhị nhân dài n bit có thể cùng khoảng cách đốivới dãy v thì d(v,w)=d(v,w’)≥ chọnrabaonhiêudãyđể tạo thành mộtbộ mã có thể tựđiều chỉnh đượce bit lỗi. Định lý cận Hamming cho chúng ta xác e+1. Vậy, nếud(v, w*) ≤ e thì v có thểđượcgiảimã định số từ mã có độ dài n bit vớigiả thiết: có khả năng tự sửa ra w*. được e bit lỗi(điềukiệncầntự sửalỗi). 2. Nếud(wi,wj)≥ 2e với ∀ i≠j, có khả năng có v, w và „ Định lý: Nếubộ mã W có s từ mã có độ dài n bit có thể tự sửa w’ vớisố chữ số lỗilà: được e bit lỗithì d(v,w)=d(v,w’)=e (d(v,w)+ d(v,w’) ≥ d(w,w’)≥ 2e). Có thể phát hiệnracáctừ mã gầnv, nhưng do tồntại cùng lúc nhiềutừ mã gầnnhấtvớiv dẫn đến không giảimãđược. 3. Tương tự. „ Ghi chú: Cn = n!/(i!*(n-i)!); s là số từ mã Truyềnnvàb và bảoom mật thông tin 135 Truyềnnvàb và bảoom mật thông tin 136 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 34
  35. Bài tập Chứng minh „ Xét từ mã nhị phân w có độ dài n bit và có khả năng tự sửa i „ Cho n=7 và e=2, hãy áp dụng định lý cận được e bit lỗi. Hamming cho biêt số từ mã tối đacủabộ m㠄 Số dãy vj sai khác vớiwi từ 0 đến e bit là : W. „ „ Vớis từ mã, tổng số dãy vj có thể tự sửalỗilà: n „ (2 là tổng số dãy nhị phân dài n bits)Î Truyềnnvàb và bảoom mật thông tin 137 Truyềnnvàb và bảoom mật thông tin 138 V.4. Mã kiểmtrachẵnlẻ Mã kiểmtrachẵnlẻ k „ Bộ mã kiểmtrachẵnlẻ là bộ mã gồms=2 từ mã, „ Mỗi đoạn mã thông tin có duy nhấtmột đoạnmãkiểmtravà trong đómỗitừ mã có dạng sau: đượcxácđịnh bởihệ phương trình tuyến tính nhị phân sau: (Ghi chú: trong mộtsố trường hợpsinhmãtheo phương pháp kiểmtrachẵnlẻ, thứ tự các bit kiểmtra và các bit thông tin có thể xen kẻ nhau hay theo một „ GọiA=[aij] =Am x n , aij ∈{0,1}, i= 1 m , j= 1 n . Ma trậnA được thứ tự khác. Ởđây, ta chọnthứ tự các bit kiểmtra gọilàma trậnkiểmtrachẵnlẻ có hạng là m (hay Rank(A) = chẵnlẻ và các bit thông tin như trên để dễ tính toán m). nhưng vẫnmất tính tổng quát. „ Lưuý: ởđây sử dụng phép tính + trong Z2 Truyềnnvàb và bảoom mật thông tin 139 Truyềnnvàb và bảoom mật thông tin 140 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 35
  36. Mã kiểmtrachẵnlẻ Phương pháp kiểmtrachẵnlẻ „ Gọi w’=r r r là từ mã truyền (hay dãy n bit truyền) và „ Cho w’=r r r là mộttừ mã, w là ma trậnviết 1 2 n 1 2 n v’=r1r2 rn là dãy n bit nhận được. theo cột, khi đó A.w=0: „ Qui ước: v’, w’ (lầnlượt là chuyểnvị của v và w) đượcviết r 0 theo dòng. Còn v, w đượcviết theo cột. a11 a12 a1n 1 „ Nếu A.v = 0 thì v = w, ta gọiv làchẵn(trường hợpnhận đúng) a a a r2 0 „ NếuA.v≠ 0 thì v ≠ w, ta gọiv làlẻ (trường hợpnhậnsai). 21 22 2n X = „ Ta gọiz = v-wlàbộ lỗigiữa v và w. Nghĩalàtạicácvị trí z = {0} thì bit nhận đượctương ứng là bit đúng và tạicácvị trí z = r 0 {1} thì bit nhận đượctương ứng là bit sai (hay bit lỗi). am1 am2 amn n „ Ta gọiC = A.zlàbộ sửalỗi(hay bộđiềuchỉnh lỗi). Hay: „ Ta có C = A.z = A.(v-w) = A.v-A.w = A.v ⇒ C = A.v = A.z „ Tính chấtcủabộ sửalỗi: dãy n bit nhận được v và bộ lỗi tương ứng có cùng bộđiềuchỉnh. Truyềnnvàb và bảoom mật thông tin 141 Truyềnnvàb và bảoom mật thông tin 142 Phương pháp sinh mã kiểmtrachẵn lẻ Ví dụ sinh mã kiểmtrachẵnlẻ „ Giả sử: cho trướcma trậnkiểmtrachẵnlẻ A với Rank(A) = m. „ Xây dựng bộ mã kiểmtrachẵnlẻđượcsinhtừ ma Tìm bộ mã chẵnlẻ W={w1, w2, w3, ,ws} trậnkiểmtraA như sau: „ Bước0: Xácđịnh các giá trị n, m, k, s „ Độ dài củatừ mã n= số cộtcủama trậnA. „ Số bit kiểm tra m= số dòng củama trậnA. „ Số bit thông tin: k = n-m. k „ Số từ mã s=2 „ Bướci: Tìmcáctừ mã thứ i (1≤ i ≤ s): „ Bước0: „ Gọikpi là triển khai nhị phân k bit củasố i „ n=6 (= số cộtcủama trậnA) „ Từ mã cần tìm là: w’i=r1r2 rmkpi „ m=3 (= số dòng củama trậnA) „ Giảihệ phương trình A.w =0 để tìm m bit kiểmtraứng với k bit thông tin i „ Số bit thông tin k = n – m = 3 (kpi) đãbiết => từ mã wi k „ => Số từ mã s=2 =8. Truyềnnvàb và bảoom mật thông tin 143 Truyềnnvàb và bảoom mật thông tin 144 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 36
  37. Ví dụ sinh mã kiểmtrachẵnlẻ Ví dụ sinh mã kiểmtrachẵnlẻ Bướci: Tìmtừ mã thứ i (1≤ i ≤ s): Giảihệ phương trình A.w1=0 „ w’0=r1r2r3000 (000 là triểnkhainhị phân k=3 bit của số i=0) „ w’1=r1r2r3001 (001 là triểnkhainhị phân k=3 bit củasố i=1) „ w’2=r1r2r3010 „ w’3=r1r2r3011 „ w’4=r1r2r3100 „ w’5=r1r2r3101 „ w’6=r1r2r3110 „ w’7=r1r2r3111 Truyềnnvàb và bảoom mật thông tin 145 Truyềnnvàb và bảoom mật thông tin 146 Ví dụ sinh mã kiểmtrachẵnlẻ Ví dụ sinh mã kiểmtrachẵnlẻ Giảihệ phương trình A.w2=0 „ Giảitương tự cho các trường hợpcònlạita 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ềnnvàb và bảoom mật thông tin 147 Truyềnnvàb và bảoom mật thông tin 148 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 37
  38. Quan hệ giữa độ dài mã n, số bit kiểmtram vàsố lỗitự sửae Ví dụ tìm m nhỏ nhấttừ n và e „ Điềukiệncần(Cận Hamming): „ Giả sử biếttrước n=7 và e=1. Tìm số bit kiểmtratốithiểucần Điềukiệncần để bộ mã chẵnlẻ có độ dài n bit có thể tự sửa thiếtcủabộ mã chẵnlẻ. được e bit lỗivới k bit thông tin và m bit kiểmtralà: „ Theo định lý điềukiệncần(Cận Hamming): „ Điềukiện đủ ( ĐK Vasharmov-Gilbert-Sacks): Điềukiện đủ để bộ mã kiểmtrachẵnlẻ có độ dài n bit vớim „ m = 1 ⇒ (*) sai. bit kiểmtrachẵnlẻ có thể tự sửa được e bit lỗilà: „ m = 2 ⇒ (*) sai. „ m ≥ 3 ⇒ (*) đúng. „ Vậysố bit kiểmtratốithiểucầnthiếtlàm = 3. Truyềnnvàb và bảoom mật thông tin 149 Truyềnnvàb và bảoom mật thông tin 150 Ví dụ tìm e lớnnhấttừ m và n Bài tập „ 1. Xây dựng bộ mã kiểmtrachẵnlẻđượcsinhtừ ma trậnkiểmtraA như „ Giả sử cho trước m=3, k=2. Tìm số bit lỗilớnnhấtcó sau: thể tự sửae? „ Theo định lý điềukiện đủ (ĐK Vassharmov-Gilbert- Sacks): „ 2. Tìm bộ mã kiểmtrachẵnlẻđượcsinhtừ ma trậnkiểmtraA như sau: „ 3. Xét bộ mã kiểmtrachẵnlẻđộdài 15 bit có thể tự sửa được1 bit lỗitrên đường truyền, hãy cho biếtsố bit kiểmtrachẵnlẻ tốithiểu? „ 4. Xét bộ mã kiểmtrachẵnlẻđộdài 8 bit với 4 bit kiểmtrachẵnlẻ. Hãy cho biếtsố lỗitự sửatối đacủabộ mã? Vậysố bit lỗilớnnhấtcóthể tự sửalàe = 1. Truyềnnvàb và bảoom mật thông tin 151 Truyềnnvàb và bảoom mật thông tin 152 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 38
  39. V.5. Phương pháp sinh mã kiểm tra chẵnlẻ nhanh Nhóm cộng tính Đặtvấn đề: „ Nhóm G đượcgọilàmột nhóm cộng tính nếu G có các tính „ Như chúng ta đãbiết, phương pháp sinh mã kiểmtrachẵnlẻ chất: giúp ta sinh bộ mã kiểmtrachẵnlẻ vớisố từ mã tương ứng là - ∀ a, b ∈ G ⇒ a+b ∈ G ( tính chấtcộng). s=2k - ∀ a, b, c ∈ G ⇒ a + (b + c)= (a + b) + c ( tc kếthợp). „ Vớiphương pháp này, ta phảixácđịnh từng từ mã một(bằng - ∃∅∈G sao cho ∅ + a = a + ∅ = a, ∀a∈ G cách giảihệ phương trình tuyến tính nhị phân). - ∀ a ∈ G ∃ -a∈G : a + (-a)=∅ 10 „ Giả sử: k=10 ta phảixácđịnh s=2 =1024 từ mã, Điềunày „ Nhóm G là nhóm hoán vị (nhóm Aben) nếu sẽ mất nhiềuthờigiannếu k càng lớn. ∀a,b ∈ G=> a + b = b + a. ÆVấn đề đặtraởđây là tìm ra mộtphương pháp sinh bộ mã kiểmtrachẵnlẻ nhanh hơnvề mặtthời gian. Phương pháp „ Ví dụ: sinh mã kiểmtrachẵnlẻ dựa theo lý thuyết nhóm sẽ giải -Tậphợpcácsố nguyên với phép + thông thường là nhóm quyếtvấn đề này. Aben. -Tậphợpcácsố 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ềnnvàb và bảoom mật thông tin 153 Truyềnnvàb và bảoom mật thông tin 154 Tính chấtcủabộ mã chẵnlẻ Tính chấtcủabộ mã chẵnlẻ „ Định lý 2: NếutậphợpW làtập các dãy nhị phân với độ dài các dãy cùng „ Tính tương đương củabộ mã nhóm cộng tính 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ộtbộ mã kiểmtrachẵnlẻđượcsinhratừ ma trận A có dạng như và bộ từ mã kiểmtrachẵnlẻđượcthể hiện sau: qua 2 định lý sau: „ Định lý 1: tậphợpcáctừ mã trong bộ mã Trong đó: -Ma trận A có m dòng và n cột. kiểmtrachẵnlẻ là mộtnhómcộng tính. -Im : là ma trận đơnvị cấpm. -k: làsố dãy nhị phân (hay từ mã) độclậptuyến tính lớnnhất. -n: làđộ dài củatừ mã và m = n-k: - bij: đượcxácđịnh bằng cách dựavàohệ phương trình tuyến tính (*) và k từ mã độclậptuyến tính như sau: w’i=r1r2r3 rm rm+1rm+2 rn. ) , ∀i =1 k Truyềnnvàb và bảoom mật thông tin 155 Truyềnnvàb và bảoom mật thông tin 156 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 39
  40. Phương pháp sinh mã kiểmtrachẵn Phương pháp sinh mã kiểmtrachẵn lẻ nhanh lẻ nhanh „ Bướckhởitạo: xác định các giá trị n, m, k, s. „ Có thể sinh k từ mã độclậptuyến tính bằng cách: „ Bước 1: sinh k từ mã độclậptuyến tính (đltt). „ Bước2: cộng tổ hợpcáctừ mã: „ Lấyk dãynhị phân k bit chỉ chứa1 số 1: + Cộng các tổ hợpcủa2 từ mã từ k mã đltt => có từ mã. L1= 000 001 + Cộng các tổ hợpcủa3 từ mã từ k mã đltt 3 L2= 000 010 => có Ck từ mã. + Cộng các tổ hợpcủak từ mã từ k từ mã đltt => có từ mã. Lk-1= 010 000 Bước 3: Cộng s-1 từ mã đã tìm được để tìm từ mã cuối cùng => = 1 từ mã. Lk= 100 000 Tổng số từ mã s= = 2k từ mã. „ Từđó đi tìm các từ mã dạng r1r2 rmLi Truyềnnvàb và bảoom mật thông tin 157 Truyềnnvàb và bảoom mật thông tin 158 Ví dụ sinh mã kiểmtrachẵnlẻ nhanh V.6. Lược đồ sửalỗitối ưu „ Tìm bộ mã nhóm khi biếttrướcma trậnkiểmtra: Đặtvấn đề „ Trong mộthệ thống liên lạctruyềntin, bêncạnh các yêu cầuthiếtbị (như nguồn phát, bộ mã hóa, ênh k „ Bước khởi tạo: n = 6, m = 3, k = 3, s = 2 = 8. truyền, bộ giải mã, ) đảmbảotốtchoviệctruyềnvà „ Bước 1: Sinh k = 3 từđộclậptruyến tính: w’1=001001, w’2=111010, w’3=110100 nhậndữ liệuthìcòncócáckhíacạnh khác như „ Bước2: Cộng tổ hợpcáctừ mã. phương pháp mã hóa và giảimãsaochotối ưulà + Cộng các tổ hợp2 từ mã đltt: phầnrất quan trọng trong hệ thống. 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ợp3 từ mã đltt: „ Vấn đề luôn được đặtraởđây là làm thế nào để chỉ w’7=w’1+w’2+w’3=000111 ra mộtphương pháp giảimãtối ưu, có nghĩahệ „ Bước3: xácđịnh từ mã cuối cùng: thống phảicókhả năng phát hiệnvàsửalỗimộtcách w’ =w’ +w’ +w’ +w’ +w’ +w’ +w’ =000000 0 1 2 3 4 5 6 7 chính xác nhấtcóthể có khi nhiễuxảy. Truyềnnvàb và bảoom mật thông tin 159 Truyềnnvàb và bảoom mật thông tin 160 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 40
  41. Định nghĩaHiệphợp Ví dụ Hiệphợp „ Xét bộ mã : W={w0=0000, w1=0101, w2=1110, w3=1011}. „ Các bộ lỗimột bit khác nhau có thể có là „ GọiW={w1, w2, ,ws} là bộ mã kiểmtrachẵn z={1000, 0100, 0010, 0001}. lẻ. ÆCác hiệphợp ứng vớicácbộ lỗi 1 bit: w0 w1 w2 w3 „ V ={v1, v2, , } là tậphợp các dãy n bit có thể 0000 0101 1110 1011 nhận được ở cuối kênh. Hiệphợp 1 1000 1101 0110 0011 (với z1=1000) Hiệphợp 2 0100 0001 1010 1111 (với z2=0100) „ Ta gọimộthiệphợpcủaW trongV làtậphợp Hiệphợp 3 0010 0111 1100 1001 (với z3=0010) Hiệphợp 4 0001 0100 1111 1010 (với z4=0001) có dạng z + W (z là bộ lỗi) Trong đó: hiệphợpi = wi + zi Truyềnnvàb và bảoom mật thông tin 161 Truyềnnvàb và bảoom mật thông tin 162 Ví dụ lược đồ sửalỗi theo các hiệp Lược đồ sửalỗi theo các hiệphợp hợp „ Xétvídụ trước, W={w0=0000, w1=0101, w2=1110, w3=1011}. „ Bước1: Lậpbảng các hiệphợp ứng vớicácbộ lỗi „ Lậpbảng hiệphợp w w w w cầnthiết 0 1 2 3 0000 0101 1110 1011 - Dòng đầutiênviếtcáctừ mã wi ∈ W. Hiệphợp 1 1000 1101 0110 0011 Hiệphợp 2 0100 0001 1010 1111 - Các dòng tiếptheoứng vớicộtw0 = 00 00 viếtcác Hiệphợp 3 0010 0111 1100 1001 bộ lỗiz (cácbộ lỗi 1 bit, 2 bit, ). Hiệphợp 4 0001 0100 1111 1010 „ Quá trình giảimã: - Các dòng ở cộtthứ i đượcxácđịnh bởiz + wi + Giả sử nhận v = 0111. Tra trên bảng các Hiệphợptacóv ở cột1Æ v đượcgiảimãvề w1 = 0101. „ Bước2: Quátrìnhgiảimã:Khinhận v, ta xác định + Giả sử nhận v = 1010. Tra trên bảng các Hiệphợptacóv ở cột 2 và cột 3 Æ giải mã không chính xác cộtthứ i chứav vàgiảimãvề wi tương ứng. Truyềnnvàb và bảoom mật thông tin 163 Truyềnnvàb và bảoom mật thông tin 164 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 41
  42. Ví dụ lược đồ sửalỗi thông qua bộ Lược đồ sửalỗi thông qua bộ lỗi lỗi Dựa vào tính chấtcủabộ sửalỗi ta có dùng lược đồ giảimãgồm2 bướcsau: „ Bước1: Lậpbảng sửalỗi: Bộ lỗi(Z) –Bộ sửalỗi (C=A*Z). „ Bước2: Quátrìnhsửalỗi - Khi nhận được dãy n bit v ∈V, ta xác định bộđiềulỗi C cho v vớiC=A.v „ Bộ mã tương ứng được xác định là: w =00000, w =11101 -Trabảng sửalỗi để tìm bộ lỗiz0 ứng vớiC. 0 1 -Giảimãw=v+z. Truyềnnvàb và bảoom mật thông tin 165 Truyềnnvàb và bảoom mật thông tin 166 Ví dụ lược đồ sửalỗi thông qua bộ Ví dụ lược đồ sửalỗi thông qua bộ lỗi lỗi „ Bước1: Lậpbảng sửalỗi: Bộ lỗi- Bộđiềuchỉnh (e = 1) Lược đồ sửalỗi2 bit : Bộ lỗi(z’) Bộđiềuchỉnh (C’=A.z) „ Lậpbảng sửalỗi: Bộ lỗi- Bộđiềuchỉnh (e = 2) + Bộ 0 lỗi 00000 0000 Bộ lỗi (z’) Bộđiềuchỉnh (C’=A.z) + Bộ lối1 bit 10000 1000 Bộ lỗi2 bit 10010 1001 01000 0100 01010 0101 00100 0010 00110 0011 00010 0001 (4 Bộ ) 00001 1110 00011 1111 (Tấtcả các bộ 2 lỗicònlại có trùng bộđiềuchỉnh 1 lỗihoặc trùng „ Bước 2: Quá trình sửalỗi nhau) + Giả sử nhận v= 11100, tính C = A.v = 1110 „ Quá trình sửalỗiGiả sử nhận v=11011, tính C = A.v = 0011 Tra + Tra bảng sửalỗi để tìm bộ lỗi ứng với C, ta có z0 = 00001 bảng sửalỗi để tìm bộ lỗiz0 ứng với C, ta có z0 = 00110 + Giải mã w = v + z0 = 11100 + 00001 = 11101 = w1 (Ghi chú: z’, C’ là các chuyểnvị củaz, C) -Giải mã w = v + z0 =11011 + 00110 =11101 = w1 Truyềnnvàb và bảoom mật thông tin 167 Truyềnnvàb và bảoom mật thông tin 168 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 42
  43. Xác suấttruyền đúng Bài tập „ GọiNi là số bộ lỗi ứng vớii lỗicóthể tự sửa, khi đó „ 1. Cho ma trận kiểm tra chẵn lẻ sau: xác suấttruyền đúng và tựđiềuchỉnh sẽ là: „ Ví dụ: xét trường hợpcácvídụ trên vớin= 5 vàtự sửa e = 2 bit lỗi. Áp dụng công thứctrêntacó: -Xâydựng bộ mã kiểmtrachẵnlẻ. -Minhhọalược đồ sửalỗi thông qua bộđiềuchỉnh trong các trường hợplỗi 1 bit. Tính xác suấttruyền đúng cho các trường hợpcóthể tự sửa được. Truyềnnvàb và bảoom mật thông tin 169 Truyềnnvàb và bảoom mật thông tin 170 V.6. Mã Hamming Ví dụ ma trậnkiểm tra Hamming „ Mã Hamming là mộtdạng mã nhóm (mã kiểmtra „ Biểudiễnnhị phân của „ Ví dụ 2: ma trậnkiểm chẵnlẻ) đượcxácđịnh từ ma trậnkiểmtrachẵnlẻ A số j = 3 có m = 3 bit như tra chẵnlẻ vớin=6, có dạng sau: sau: m=3 có thể viếtnhư -Cộtthứ j củama trậnA làbiểudiễnnhị phân m bit (m „ Viết theo dòng: 011 sau: là số bit kiểmtrachẵnlẻ) củasố j theo qui ướcbiểu diễnnhị phân củasố j đượcviết theo thứ tự từ dưới (viếttừ trái sang phải) lêntrên(viếttheocột), tương đương vớiviếttừ trái „ Viết theo cột(viếttừ sang phải(viết theo dòng). dướilên) : - Các bit ở vị trí 2i ( i = 0, 1, 2, ) đượcchọn làm bit kiểmtra. Truyềnnvàb và bảoom mật thông tin 171 Truyềnnvàb và bảoom mật thông tin 172 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 43
  44. Ví dụ ma trậnkiểm tra Hamming Tính chất mã Hamming „ Từ mã Hamming có dạng: w=r1r2r3r4r5r6. Trong „ Nếuchotrướcsố bit (m) và số bit lỗitự sửa i, đó, r1r2r4 (vị trí 2 i=0,1,2 ) là các bit kiểmtra (e) thì số bit tối đacủabộ mã Hamming (n) có và r3r5r6 là các bit thông tin thểđược ướclượng từ bất đẳng thứcsau: Truyềnnvàb và bảoom mật thông tin 173 Truyềnnvàb và bảoom mật thông tin 174 Ví dụ minh họa Ví dụ minh họa „ Tìm bộ mã Hamming với n = 6 và m =3 Chú ý, có thể sử dụng phương pháp sinh mã nhanh: „ Ta có thể viếtngayma trậnkiểmtrachẵnlẻ cho bộ mã Hamming k „ Số từ mã củabộ mã Hamming là s = 2 = 8 „ Tìm k từ mã độclậptuyếntínhcódạng: w’1=r1r20r401 w’2=r1r20r410 „ Từ A ⇒ k = n – m = 3. w’3=r1r21r400 „ Các bit ở các vị trí 1, 2, 4 đượcchọn làm các bit kiểmtra. k „ „ Số từ mã củabộ mã Hamming là s = 2 = 8 Giảicáchệ phương trình: A.w1=0, A.w2=0, A.w3=0 để tìm w’ w’ ,w’ w’0=r1r20r400 w’1=r1r20r401 w’2=r1r20r410 w’7=r1r21r411 1, 2 3 Giảicáchệ phương trình: A.w1=0, A.w2=0, A.w3=0 „ Các từ mã còn lại đượcxácđịnh theo phương pháp W’={000000, 010101, 100110, 110011, 111000, 101101, 011110, 001011} sinh mã nhanh. Truyềnnvàb và bảoom mật thông tin 175 Truyềnnvàb và bảoom mật thông tin 176 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 44
  45. Bài tập V.7. Thanh ghi lùi từng bước 1. Viếtma trậnkiểmtrachẵnlẻ cho bộ m㠄 Biểudiễnvậtlýcủa thanh ghi lùi từng bước(LTB): Hamming với n = 15. 2. Từ kếtquả bài tập 1, hãy tìm k từ mã Hamming độclậptuyến tính tương ứng. 3. Xét bộ mã Hamming vớisố bit kiểmtracho -F , F , , F , F : các bit lưutrữ dữ liệunhị phân. trướclàm, khiđó: m-1 m-2 1 0 -am-1, am-2, , a1, a0 : các công tắc (switch) dùng để đóng (=1) hay mở ( =0). - Độ dài mã tốithiểu là bao nhiêu? ⊕ là bộ làm tính cộng mudulo 2 sau mỗi xung đồng hồ vớidữ liệu do các bit của thanh ghi gửivề. - Độ dài mã tối đa là bao nhiêu? „ Quá trình dịch chuyểnlùi: saumỗi xung đồng hồ thì dữ liệu trong bit Fi sẽ đượcchuyểnvề lưutrữở bit Fi-1 Truyềnnvàb và bảoom mật thông tin 177 Truyềnnvàb và bảoom mật thông tin 178 Biểudiễntoánhọccủa thanh ghi Biểudiễntoánhọccủa thanh ghi LTB LTB „ Gọix = (x0, x1, , xm-2, xm-1) là giá trị các bit của thanh ghi tại „ Hay viết theo dạng ma trận thời điểmtrước khi có nhịp xung đồng hồ. ta có x’ = T.x x’ = (x’ , x’ , , x’ , x’ ) là giá trị các bit của thanh ghi sau 0 1 m-2 m-1 „ Trong đó: khi có nhịpxungđồng hồ. - T: Ma trận vuông cấpm. „ Khi đótacó: - Dòng cuốicủama trận:là x’ =x 0 1 các hệ số: a , a , , a . x’ =x 0 1 m-1 1 2 -Gốc trên bên phải: là ma trận x’ =x 2 3 đơnvị cấp m-1. „ T đượcgọilàma trận đặc x’ =x m-2 m-1 trưng của thanh ghi lùi từng x’ =a x + a x + + a x . m-1 0 0 1 1 m-1 m-1 bước. Truyềnnvàb và bảoom mật thông tin 179 Truyềnnvàb và bảoom mật thông tin 180 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 45
  46. Biểudiễntoánhọccủa thanh ghi LTB Ví dụ thanh ghi lui từng bước „ Quá trình dịch chuyểnlùitừng bướccủa thanh ghi: „ Cho thanh ghi lui từng bước sau: „ Gọi: „ Ta có: m=4, a0=1, a1=0, a2=1, a3=0. ÆMa trận đặctrưng của thanh ghi: (1) (0) „ Giá trị của thanh ghi sau 1 xung đồng hồ là x =T.x (2) (1) 2 (0) „ Giá trị của thanh ghi sau 2 xung đồng hồ là x =T.x =T .x (3) (2) 3 (0) „ Giá trị của thanh ghi sau 3 xung đồng hồ là x =T.x =T .x Truyềnnvàb và bảoom mật thông tin 181 Truyềnnvàb và bảoom mật thông tin 182 Chu kỳ của thanh ghi Ví dụ tìm chu kỳ của thanh ghi „ Chu kỳ của thanh ghi là số xung nhịp đồng hồ để thanh ghi lặplạitrạng thái ban đầu. Nghĩa là nếux(0) ≠0 và ∃ n>0 sao cho x(n)= x(0) thì ta „ Ta có: m=4, a0=1, a1=0, a2=1, a3=0. nói n là chu kỳ của thanh ghi. (0) „ Nếu khởi tạo x =0001, khi đó: (i) m „ Bởivìsố trạng thái củax là hữuhạn(2 ) nên thanh ghi có chu kỳ (i) „ Lưuý: viếtx =3 (011) tương ứng => Chu kỳ=6 Truyềnnvàb và bảoom mật thông tin 183 Truyềnnvàb và bảoom mật thông tin 184 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 46
  47. Ví dụ tìm chu kỳ của thanh ghi Bài tập „ Tương tự: „ Tìm các chu kỳ của thanh ghi lui từng bước + Khi chọnx(0) = 3 thi ta cũng có chu kỳ n = 6. như hình sau: + Khi chọnx(0)= 6 thìtacóchukỳ n = 3. + Khi chọnx(0)= 0 thìtacóchukỳ n = 1. Truyềnnvàb và bảoom mật thông tin 185 Truyềnnvàb và bảoom mật thông tin 186 Đathức đặctrưng của thanh ghi Quan hệ giữachukỳ n, đathức đăc LTB trưng và đathức(xn + 1) n „ Định nghĩa: đathức đặctrưng của thanh ghi lui từng bướccó „ Đathức(x+ 1)>= g (x) luôn chia hếtchođa ma trận đặctrưng là T là đathứccódạng m 2 m-1 m thức đặctrưng của thanh ghi gm(x) gm(x)=a0 + a1x+ a2x + +am-1x + x „ vớia0, a1, a2, , am-1 là các công tắccủa thanh ghi và m là số Ví dụ: xét lại thanh ghi lui từng bướcnhư như bit của thanh ghi 2 4 ví dụ trướccógm(x)=1+x +x , chu kỳ n=6 thực „ Ví dụ hiện phép chia (x6 + 1):(x4+x2+1) (phép toán Modulo 2) 6 4 2 a = 1, a = 0, a = 1, a = 0 x + 1 x +x +1 0 1 2 3 6 4 2 ÆĐathức đặctrưng của thanh ghi là: x + x +x x2 +1 4 2 2 4 x +x +1 gm(x)=1 + x + x x4+x2+1 0 Chú ý: Hai phép toán và là như nhau Truyềnnvàb và bảoom mật thông tin 187 Truyềnnvàb và bảoom mật thông tin 188 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 47
  48. Thủ tục sinh thanh ghi lùi từng bước Ví dụ sinh thanh ghi lùi từng bước Sinh thanh ghi lùi từng bướcvớisố bit là m và có chu kỳ n: „ Thiếtkế thanh ghi có m=4 bit và chu kỳ n=7 „ Bước 1: xác định đathức đặctrưng của thanh ghi 2 m-1 m „ Bước 1: Xác định đathức đặctrưng của thanh -Tìm2 đathứcgm(x)=a0 + a1x+ a2x + +am-1x + x 2 k-1 k và hk(x)=h0 + h1x+ h2x + +hk-1x + x sao cho ghi (xn + 1) = g (x)* h (x). 7 2 3 2 3 4 m k „ n Ta có (x + 1)=(1 + x + x )(1 + x + x + x ) -Nếu ∃ (x + 1) = gm(x)* hk(x) thì ta chọngm(x) làm đathức đặc 2 3 4 trưng và thựchiệnbước2. „ Do m=4 nên chọng4(x) = (1 + x + x + x ) làm Ngượclại: không tồntại thanh ghi theo yêu cầu. đathức đặctrưng của thanh ghi. „ Bước 2: xác định thanh ghi từđathức đặctrưng 2 m-1 m gm(x)=a0 + a1x+ a2x + +am-1x + x Truyềnnvàb và bảoom mật thông tin 189 Truyềnnvàb và bảoom mật thông tin 190 Tìm gm(x) V.8. Mã xoay vòng Giảipt: „ Định nghĩamãxoayvòng 7 4 3 2 3 2 x + 1=(x +a3x +a2x +a1x+a0)(x +h2x +h1x+h0 ) „ Mã xoay vòng là mã kiểmtrachẵnlẻđược h2 +a3 = 0 h1+a3h2+a2 = 0 sinh ra từ ma trậnkiểmtrachẵnlẻứng vớichu h0+a3h1+a2h2+a1 = 0 kỳ n của thanh ghi lùi từng bướccódạng như: a h +a h +a h +a =0 3 0 2 1 1 2 0 A=[x(0)| Tx(0)|T2x(0) | |Tn-1x(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ềnnvàb và bảoom mật thông tin 191 Truyềnnvàb và bảoom mật thông tin 192 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 48
  49. Phương pháp sinh nhanh bộ mã Ví dụ 1 xoay vòng „ Bước 1: sinh mã xoay vòng đầutiên „ Từ thanh ghi : m=4, a0=1, a1=0, a2=1, a3=0 đã xét, có chu kỳ n=6: Sinh mã xoay vòng đầutiêncódạng w1=a0a1a2 am-11000 00 (0) „ Khởi tạo x =1 ta có: k-1 bit 0 A=[x(0) x(1) x(2) x(3) x(4) x(5)] „ Bước 2: sinh k -1 từ mã độclậptuyến tính còn lại: w2= 0a0a1a2 am-1100 0 (dịch vòng w1 sang phải 1 bit). wk= 000 00a0a1a2 am-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ạicủabộ mã Các từ mã còn lạigồm(2k –k từ mã) đượcxácđịnh bằng k 2 cách cộng tổ hợpcủa 2, 3, , k từ mã từ k từ mã độclập „ Ta có n=6, m=3, k=2 ⇒ s = 2 = 2 = 4 từ mã. tuyến tính ở trên. Truyềnnvàb và bảoom mật thông tin 193 Truyềnnvàb và bảoom mật thông tin 194 Mộtsốđathức đặctrưng Phần II. Bảomật thông tin Truyềnnvàb và bảoom mật thông tin 195 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 49
  50. I.1. An toàn thông tin „ Từ xưa Chương I. „ An toàn bảomật thông tin đảmbảobằng Giớithiệuvề bảomật thông tin „ Giao thức, cơ chế „ Các điềuluật „ Thông tin ngày nay phầnlớn đượclưuvàvận chuyểntrêncácphương tiện điệntử Æ phương tiệnbảomật: mậtmãhọc Truyền và bảo mật thông tin 198 Các phương pháp bảovệ an toàn thông tin Nội dung an toàn thông tin Các phương pháp bảovệ an toàn thông tin „ Tính bí mật: tính kín đáo riêng tư củathôngtin „ Bảovệ an toàn thông tin bằng các biện pháp hành chính. „ Tính xác thựccủa thông tin, bao gồmxácthực đối tác( bài toán nhận danh), xác thực thông „ Bảovệ an toàn thông tin bằng các biện pháp kỹ thuật (phầncứng). tin trao đổi. „ Bảovệ an toàn thông tin bằng các biện pháp thuật „ Tính trách nhiệm: đảmbảongườigửi thông tin toán (phầnmềm). không thể thoái thác trách nhiệmvề thông tin Biệnpháphiệuquả nhấtvàkinhtế nhấthiện nay trên mà mình đãgửi. mạng truyềntin 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 199 Truyền và bảo mật thông tin 200 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 50
  51. I.3. Khái niệmhệ mã mật I.2. Mật mã học (cryptology) (CryptoSystem) Bao gồm: „ Định nghĩa1.1 „ Mậtmãhọc (cryptography): là khoa học „ Mộthệ mậtlàmộtbộ 5 (P,C,K,E,D) thoả mãn các nghiên cứucáchghibímậtvàxácthực thông điềukiệnsau: tin. 1. P là mộttậphữuhạncácbảnrõcóthể. 2. C là mộttậphữuhạncácbảnmãcóthể. „ Thám mã(cryptanalysis): là khoa học nghiên 3. K (không gian khoá) là tậphữuhạn các khoá có thể. cứu cách phá mã hoặctạomãgiả. 4. Đốivớimỗik∈ K có mộtquytắcmãek: P → C và một quy tắcgiảimãtương ứng dk ∈ D. Mỗiek: P → C và dk: C → P là những hàm mà: dk(ek (x)) = x vớimọibảnrõx ∈ P. Truyền và bảo mật thông tin 201 Truyền và bảo mật thông tin 202 I.4. Mô hình truyền tin cơ bản I.5. Luật Kirchoff (1835 - 1903) „ Theo luật Kirchoff (1835 - 1903)(một nguyên tắccơ bản trong mã hóa) thì: toàn bộ cơ chế mã/giảimãtrừ khoá là không bí mật đốivớikẻđịch. „ Khi đốiphương không biết đượchệ mã mật đang sử dụng thuật toán mã hóa gì thì việ̣cthámmãsẽ rất khó khăn. Nhưng chúng ta không thể tin vào độ an „ Thông điệpX làbản rõ (Plaintext), được mã hóa với toàn củamậtmãchỉ dựa vào giả thiết không chắc khóa K Æ vănbản mã hóa Y (Ciphertext) 1 chắn đốiphương không biếtthuậttoánđang sử „ Quá trình giảimãchuyểnYÆX sử dụng khóa K2 dụng. Truyền và bảo mật thông tin 203 Truyền và bảo mật thông tin 204 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 51
  52. I.6. Phân loại các thuậttoánmật mã I.6. Phân loạ i các thuậttoánmật mã học học Phân loại theo khóa và ứng dụng Phân loại theo khóa và ứng dụng: 1. Hệ mật đốixứng (hay còn gọilàmật mã khóa bí mật): là 3. Các thuậttoántạochữ ký điệntử (Digital Signature những hệ mật dung chung một khoá cả trong quá trình mã hoá dữ liệuvàgiảimãdữ liệu. Do đókhoáphải đượcgiữ bí Algorithms). Thông thường mỗihệ chữ ký điệntử mậttuyệt đối. có cùng cơ sở lý thuyếtvớimộthệ mã mậtkhóa 2. Hệ mậtmãbất đốixứng (hay còn gọilàmật mã khóa công công khai nhưng vớicáchápdụng khác nhau. khai) : Hay còn gọilàhệ mật mã công khai, các hệ mật này 4. Các hàm băm (Hash functions). Các hàm băm là các dùng mộtkhoáđể mã hoá sau đódùngmột khoá khác để thuật toán mã hóa không khóa hoặccókhóavà giải mã. Các khoá này tạo nên từng cặp chuyển đổingược thường đượcsử dụng trong các hệ chữ ký điệntử nhau và không có khoá nào có thể suy đượctừ khoá kia. Khoá dùng để mã hoá có thể công khai nhưng khoá dùng để hoăccáchệ mã khóa công khai, mã hóa mật giảimãphảigiữ bí mật. khẩu Truyền và bảo mật thông tin 205 Truyền và bảo mật thông tin 206 I.6. Phân loại các thuậttoánmật mã I.6. Phân loại các thuậttoánmật mã học học Phân loại theo cách xử lý dữ liệuvào: Phân loại theo thờigianrađời: 1. Các thuậttoánmãhóakhối (DES , AES ) 1. Mậtmãcổđiển(làhệ mậtmãrađờitrước xử lý bảnrõdướicácđơn vị cơ bản là các năm 1970) khốicókíchthướcgiống nhau. 2. Mậtmãhiện đại(rađờisaunăm 1970) 2. Các thuật toán mã hóa dòng coi bảnrõlàmột luồng bit, byte liên tục. Truyền và bảo mật thông tin 207 Truyền và bảo mật thông tin 208 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 52
  53. I.7. Quan điểmvềđộan toàn củahệ I.7. Quan điểmvềđộan toàn củahệ mật mật „ Có hai quan điểm: Độ an toàntính toánvà độ an toàn không „ Độ an toàn không điềukiện điềukiện „ Hệ mậtan toàn không điềukiệnnếunó không thể bị „ Độ an toàntính toán phá ngay cả khi không hạnchế khả năng tính toán „ Liên quan đếnnỗ lựctính toán để phá mộthệ mật ⇒ Độ an toàn không điềukiệncủamộthệ mật không „ Hệ mậtan toànvề tính toán: thuậttoánphá tốtnhấtcần ítnhấtN phéptoán, N rấtlớn, thựctế không có hệ mật thể nghiên cứutheođộ phứctạptính toánmà sẽ nàothỏamãn dùng lí thuyếtxácsuất „ Trên thựctế nếucó mộtphương pháptốtnhấtphá được hệ mậtnàynhưng yêu cầuthờigianlớn đếnmức không chấpnhận được „ Có thể quy về bàitoánkhó Truyền và bảo mật thông tin 209 Truyền và bảo mật thông tin 210 I.9. Quan điểmvềđộan toàn củahệ I.9. Quan điểmvềđộan toàn củahệ mật mật „ Mộtsố kiếnthứccơ bảnvề lí thuyếtxácsuất „ X và Y đượcgọilàđộclậpnếu „ Định nghĩa1: X và Y là các biếnngẫu nhiên p(x, y) = p(x).p(y), với| x є X và | y є Y. „ p(x): xác suất(xs) để X nhận giá trị x „ Quan hệ giữaxsđồng thờivàxscóđiềukiện được „ p(y): xs để Y nhận giá trị y biểuthị theo công thứcsau: „ p(x, y): xs đồng thời để X nhậngiátrị x và Y nhận p(x,y) = p(x).p(y|x) = p(y).p(x|y) giá trị y. „ Định lý Bayes „ p(x| y): xs để X nhậngiátrị x với điềukiện(đk) Y nhậngiátrị y. „ Nếu p(y) > 0 thì: Truyền và bảo mật thông tin 211 Truyền và bảo mật thông tin 212 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 53
  54. I.7. Quan điểmvềđộan toàn củahệ I.7. Quan điểmvềđộan toàn củahệ mật mật „ Hệ quả 1 „ Định lý Shannon: Giả sử (P, C, K, E, D) là mộthệ mật, khi đó hệ mật đạt đươc độ mậthoànthiệnkhi „ X và Y là các biến độclập khi và chỉ khi: và chỉ khi |K| ≥ |C|. Trong trường hơp |K| = |C| = |P|, p(x|y) = p(x) vớimọix, y. hệ mật đạt độ mật hoàn thiệnkhivàchỉ khi mỗi khoá K được dùng vớixácsuấtbằng nhau, bằng 1/|K| và „ Độ mật hoàn thiện vớimỗix ∈ P, mỗiy ∈ C có mộtkhoáK duynhất „ Định ngĩa: Mộthệ mậtcóđộ mật hoàn thiệnnếu: pP(x|y) = sao cho eK(x) = y. pP(x), vớimọi x thuộcP, y thuộcC „ Æ Để có độ mật hoàn thiệncầncókhóarấtdàiÆ „ Trong đó: pP(x): sx tiên nghiệm để bảnrõxuấthiện chuyểngiaokhóakhókhăn Æ trong thựctế không có độ an toàn không điềukiệnmàchỉ an toàn thực ÆÝ nghĩa: đốiphương có bảnmãcũng không tế, tứclàtùythuộc thông tin và thờigiancầnbảo thu nhậnthôngtin gìvề bảnrõ mật Truyền và bảo mật thông tin 213 Truyền và bảo mật thông tin 214 II.1. Các hệ mã cổđiển 1. Hệ mã đẩy Chương II. 2. Hệ mã thế vị CÁC HỆ Mà KHÓA BÍ MẬT 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 216 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 54
  55. II.1.1. Hệ mã đẩy (Shift Cipher) II.1.1. Hệ mã đẩy (shift Cipher) „ Giả sử không gian bản rõ P là các thông điệp A B C D L M N W X Y Z tạoratừ bảng chữ cái A, số phầntử của A: 0 1 2 3 11 12 13 22 23 24 25 |A|=N „ Ví du : với k=3 (hoàng đế La Mã Julius Caesar đãsử „ Không gian bảnmãC≡P dụng), ḱýtự A đượcthaybằng D, B thay bằng E , , W thay bằng Z , , X thay bằng A , Y thay bằng B, „ Để mã hóa: đánh số thứ tự chữ cái 0 N-1 Z thay bằng C. „ Không gian khóa K=ZN „ Xâu “ANGLES” sẽ được mã hóa thành “DQJOHV” „ Mã hóa: Ek(x) = (x + k) mod N. „ Bài tập: Với k=5, C=QFRGFNYFU, tìm P? „ Cho C=QEHECUYEHI thông điệplàtiếng việt không dấu „ Giảimã: Dk(y) = (y – k) mod N. Truyền và bảo mật thông tin 217 Truyền và bảo mật thông tin 218 II.1.1. Hệ mã đẩy (Shift Cipher) II.1.2. Hệ mã thế vị „ „ Sử dụng thay thếđơnâmnênÆ phụ thuộctầnsuất Cho P =C = Z26; củaxuấthiệncủa ngôn ngữ tự nhiên(mộtsố chữ cái „ K chứamọi hoán vị có thể của 26 kí hiệu 0,1, . xuấthiệnnhiềuhơncácchữ khác) Æ ngườithám . . ,25 mã có thể sử dụng phương pháp thử cáckýtự xuất hiệnnhiều. „ Vớimỗi phép hoán vị π∈K , ta định nghĩa: „ Không gian khóa là N nhỏ (bảng chữ tiếng anh eπ(x) = π(x) N=26) Æ có thể thám mã bằng phương pháp vét cạn và các khóa -1 dπ(y) = π (y) trong đó π-1 là hoán vị ngượccủa π. Truyền và bảo mật thông tin 219 Truyền và bảo mật thông tin 220 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 55
  56. Ví dụ mã thế vị Ví dụ mã thế vị „ Ví dụ một phép hoán vị π: „ Hàm giải mã là phép hoán vị ngược: „ d (A)=D, d (Q)=J „ Ta có: eπ(D)=A, eπ(J)=Q π π A B C D E F G H I J K L M A B C D E F G H I J K L M X N Y A H P O G Z Q W B T D L R Y V O H E Z X W P t N O P Q R S T U V W X Y Z N O P Q R S T U V W X Y Z S F L R C V M U E K J D I B G F J Q N M U S K A C i Truyền và bảo mật thông tin 221 Truyền và bảo mật thông tin 222 Không gian khóa mã thế vị II.1.3. Hệ mã Affine 26 Các định nghĩa „ Số các hoán vị này là 26!, lớnhơn4 ×10 là „ Giả sử a ∈ Zm, phầntửđảo ứng với phép nhân củaa làphần mộtsố rấtlớn. Bởivậy, phép tìm khoá vét cạn -1 tử a ∈ Zm sao cho không thể thựchiện được, thậmchíbằng máy aa-1= a-1a=1 (mod m) tính. „ Định lý về sự tồntạicủaphầntử nghịch đảo: Nếu UCLN(a, m) = 1 thì tồntại duy nhất1 số b ∈Zm là phân tử nghịch đảo „ Tuy nhiên, mã thế vị có thể dễ dàng bị thám cua a, nghĩa là thỏamản a.b = (a*b) mod m = 1. „ Tậpcácsố nguyên trong Z là nguyên tố cùng nhau vớim gọi bằng các phương pháp dò thử theo tầnsuất m là Z * ký tự. m „ Số lượng các số nguyên trong Zm là nguyên tố cùng nhau với m ký hiệulàφ(m) (gọi là hàm Euler) Truyền và bảo mật thông tin 223 Truyền và bảo mật thông tin 224 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 56
  57. Hệ mã Affine Ví dụ hệ mã Affine „ Không gian bảnrõvàbảnmãlàhìnhthànhtừ bảng „ Xét tậpchữ cái tiếng Anh (Z26) chữ cái A. Giả sử |A|=N, khi đó không gian khóa „ Giả sử K = (7,3). đượcxácđịnh: „ Bảnrõ: HOT „ K={(a,b): a, b ∈ ZN, UCLN(a, N)=1} „ Hàm lậpmã: ek(x)=7x+3 „ Số khóa có thể sử dụng φ(N) *N „ Các số tương ứnglà 7, 14 và 19. Bây giờ sẽ mã hoá: „ Mã hóa: „ Ek(H)= (7 × 7 +3) mod 26 =0 „ Đánh thứ tự chữ cái 0, 1, N-1 „ Ek(O)=(7 × 14 + 3) mod 26=23 „ ek(x)=(a*x+b) mod N (ký tự thứ x chuyển thành ký tự thứ (a*x+b) mod N ) „ Ek(T)=(7 × 19 +3) mod 26 =6 „ Giảimã: „ =>Bảnmã: AXG -1 „ dk(y)=a (y-b) mod N Truyền và bảo mật thông tin 225 Truyền và bảo mật thông tin 226 Ví dụ hệ mã Affine Bài tập „ Giảimã? „ Mối quan hệ giữa các hệ mã đẩy, mã thế vị và „ Bản mã: AXG (tương ứng 0, 23, 6) mã Affine? -1 „ Ta có: 7 = 15 (vì 7*15 mod 26=1) =>Hàm giảimã: 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 227 Truyền và bảo mật thông tin 228 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 57
  58. II.1.4. MậtmãVigenère MậtmãVigenère „ Lấytêncủanhàmậtmãhọcngười Pháp Blaise de Ví dụ Vigenère (1523-1596) „ A là bảng chữ cái tiếng Anh Æ N=26 „ Thông điệpsử dụng bảng chữ cái A. Các ký tựđược „ K=“CIPHER”, đánh số 0, 1, N-1, vớiN =|A| „ Bản rõ P=“THISCRYPTOSYSTEMISNOTSECURE” „ Không gian khóa K đượcxácđịnh: „ Ta có: „ Vớimỗisố nguyên dương M , khóa có độ dài M là „ K = 2 8 15 7 4 17, mộtxâuký tự có độ dài M , K=k1k2 kM. „ 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. „ Để mã hóa mộtbảnrõP: chiaP ralàmcácđoạncó „ Từđó: độ dài M, chẳng hạnX=x1x2, xM, khi đó: „ C = 21 15 23 25 6 8 | 0 23 8 21 22 14 | 20 1 19 19 12 9 | 15 22 8 25 8 „ Ek(X) = (x1 + k1, x2 + k2 , , xM + kM ) mod N 19 | 22 25 19 „ Dk(Y) = (y1 -k1, y2 -k2, , yM -kM) mod N „ C= “VPXZGIAXIVWOUBTTMJPWIZITWZT” Truyền và bảo mật thông tin 229 Truyền và bảo mật thông tin 230 Bài tập II.1.5. Hệ mã Hill „ Với tập các ký tự tiếng Anh, cho K=KHOA „ Do Lester S.Hill đưaranăm 1929 „ Không gian bảnrõvàbảnmãlàbảng chữ cái A. Các „ Bản mã c=FPSTMOIOXNHRSUVMKAWNR chữ cái được đánh số từ 0 đến N-1 (N=|A|) „ Tìm bản rõ p? „ Vớimỗisố nguyên M, khóa là mộtma trận vuông kích thướcM, điềukiệnlàtồntạima 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 -1 „ Giảimã: P=C*K Truyền và bảo mật thông tin 231 Truyền và bảo mật thông tin 232 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 58
  59. Hệ mã Hill Hệ mã Hill Ví dụ: cho hệ ma Hill có M = 2 (khóa là các ma trận vuông cấp => Bảnmãthuđược: C = “DPLE”. 2) và bảng chữ cái là bảng chữ cái tiếng Anh (N = 26). Cho -1 khóa: Để giảimã, cần tính ma trậnnghịch đảoK trên Z26 K= ⎛ 3 3⎞ ⎜ ⎟ „ ⎜ ⎟ Với K= k k ⎝ 2 5 ⎠ ⎛ 11 12 ⎞ ⎜ ⎟ „ Hay mã hóa xâu P = “HELP” và giảimã? định thức: det(K)⎝k21 k 22=⎠ (k11*k22 – k21*k12) mod N „ Chia P ra làm P1=“HE” (7,4) và P2=“LP” (11,15) Điều kiện det(K)-1 tồn tại, khi đó: ⎛ 3 3⎞ -1 -1 „ Với P1 = (7 4) ta có C1 = P1 * K = (7 4) ⎜ ⎟ K = det(K) * ⎜ 2 5 ⎟ k − k = (7*3+4*2 7*3+4*5 )= (3 15) = (D P) ⎝ ⎠ ⎛ 22 12 ⎞ ⎜ ⎟ ⎝− k21 k11 ⎠ ⎛ 3 3⎞ „ Với P2 = (11 15) ta có C2 = (11,15) ⎜ ⎟ =(11 4) = (L E) ⎝ 2 5⎠ Truyền và bảo mật thông tin 233 Truyền và bảo mật thông tin 234 Hệ mã Hill II.1.6. Mã hoán vị Áp dụng: „ Ý tưởng của MHV là giữ cáckýtự củabản rõ không thay đổi nhưng sẽ thay đổivị trí của chúng bằng cách sắpxếplạicác det(K) = (15 - 6) mod 26 = 9. -> det(K)-1 =3 ký tự này (vì 9*3=1 (mod 26) ) „ Giả sử không gian bản rõ P là các thông điệptạoratừ bảng chữ cái A, số phầntử của A: |A|=N ⎛ 5 23⎞ ⎛ 3*5 3*23⎞ ⎛15 17⎞ „ Không gian bảnmãC≡P -1 ⎜ ⎟ ⎜ ⎟ ⎜ ⎟ => K = 3* ⎜ ⎟ = ⎜ =⎟ ⎜ ⎟ „ Cho m là mộtsố nguyên dương xác định nào đó ⎝24 3 ⎠ ⎝3*24 3*3 ⎠ ⎝20 9 ⎠ „ Cho K gồmtấtcả các hoán vị của {1, . . ., m}. Đốimột khoá π ( tứclàmột hoán vị) ta xác định: Quá trình giảimãnhư khi mã hóa, sử dụng công thức „ eπ(x1, . . . , xm ) = (xπ(1), . . . , xπ(m)) -1 -1 -1 P=C*K „ dπ(x1, . . . , xm ) = (yπ (1), . . . , yπ (m)) trong đó π-1 là hoán vị ngượccủa π Truyền và bảo mật thông tin 235 Truyền và bảo mật thông tin 236 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 59
  60. Ví dụ mã hoán vị II.1.7. Các hệ mã dòng „ Giảisử m=6 và khóa là hoán vị π =(3, 5, 1, 6, 4, 2): „ Trong các hệ mậtnghiêncứu ở trên, các phầntử liên 1 2 3 4 5 6 tiếpcủabảnrõđều đượcmãhoábằng cùng một 3 5 1 6 4 2 khoá k. Tứcxâubảnmãy nhận đượccódạng: y = y1y2. . . = ek(x1) ek(x2 ) . . . „ Bảnrõ SHESELLSSEASHELLSBYTHESEASHORE „ Các hệ mậtthuộcdạng này thường đượcgọilàcác „ Chia 6 nhóm: SHESEL | LSSEAS | HELLSB | YTHESE | ASHORE mã khối. „ Mỗi nhóm 6 chữ cái đượcsắpxếplại theo phép hoán vị π, ta có: „ EESLSH | SALSES | LSHBLE | HSYEET | HRAEOS Một quan điểmsử dụng khác là mật mã dòng. Ý ÆBản mã: EESLSHSALSESLSHBLEHSYEETHRAEOS tưởng cơ bản ởđây là tạoramột dòng khoá z = z1z2 -1 . . . và dùng nó để mã hoá mộtxâubảnrõx = xx . . „ Để giả mã, ta làm tương tự, dùng hoán vị ngược π : 1 2 . theo quy tắc: y = y1y2. . . = ez1(x1)ez2(x2). . . 1 2 3 4 5 6 3 6 1 5 2 4 Truyền và bảo mật thông tin 237 Truyền và bảo mật thông tin 238 Hoạt động hệ mã dòng Định nghĩahệ mã dòng Mật mã dòng là mộtbộ (P,C,K,L,F,E,D) thoả mãn đượccácđiềukiện sau: „ Giả sử k ∈K là khoá và x = x1x2 làxâu bản rõ. Hàm 1. P là mộttậphữuhạncácbảnrõcóthể. fi được dùng để tạo zi (zi là phần tử thứ i của dòng 2. C là tậphữuhạncácbảnmãcóthể. khoá) trong đóf là một hàm của khoá k và i-1 ký tự i 3. K là tậphữuhạn các khoá có thể (không gian khoá) đầu tiên của bản rõ: 4. L là tậphữuhạncácbộ chữ của dòng khoá. zi = fi (k, x1 , , xi -1 ) 5. F = (f1 f2 ) là bộ tạo dòng khoá. Vớii ≥ 1 i -1 fi : K × P → L „ Phần tử zi của dòng khoá được dùng để mã xi tạo ra 6. Vớimỗiz ∈L có một quy tắcmãez ∈ E và một quy tắcgiảimãtương ứng yi = eiz(xi). Bởi vậy, để mã hoá xâu bản rõ x1 x2 . . . dz ∈D , ez : P →C và dz : C →P là các hàm thoả mãn dz(ez(x))= x vớimọibản rõ x ∈ P. ta phải tính liên tiếp: z1, y1, z2 , y2 Ta có thể coi mã khốilàmộttrường hợp đặcbiệtcủa mã dòng trong đó „ Việc giải mã xâu bản mã y y cóthể được thực 1 2 dùng khoá không đổi: Zi = K vớimọii ≥1. 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 239 Truyền và bảo mật thông tin 240 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 60
  61. Mộtsố dạng đặcbiệtcủahệ mã dòng Ví dụ phương pháp sinh chuổikhóa „ Mã dòng đượcgọilàđồng bộ (synchronous) nếu 1. Mã Vigenère với độ dài từ khoá m có thể coilàmãdòng dòng khoá không phụ thuộcvàoxâubảnrõ, tứclà tuần hoàn vớichukỳ m. Trong trường hợp này, khoá là K = (k , . . . k ). Bản thân K sẽ tạom phầntửđầutiêncủa dòng nếu dòng khoá đựợctạorachỉ là hàm của khoá k. 1 m khoá: z = k , 1 ≤ i ≤ m. Sau đó dòng khoá sẽ tự lặplại. Khi đótacoik làmột“hạtgiống" để mở rộng thành i i „ Các hàm mã và giảimãđược dùng giống như các hàm mã dòng khoá z z 1 2 và giảimãđược dùng trong mã đẩy: ez(x) = x+z và dz(y) = y- „ Mộthệ mã dòng đượcgọilàtuần hoàn (periodic) với z „ Các mã dòng thường đượcmôtả trong bảng chữ nhị phân: chu kỳ d nếuzi+d= zi vớisố nguyên i ≥ 1. P=C=L=Z2. Æ hàm mã và giảimã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 241 Truyền và bảo mật thông tin 242 Ví dụ phương pháp sinh chuổikhóa Ví dụ 2. Ví dụ phương pháp sinh chuổi khóa (đồng bộ): Giả sử m=4 và chuổikhóađược sinh theo quy „ Giả sử bắt đầuvới(k, . . , k ) và z = k , với1 ≤ i ≤ m; vớii>m: 1 m i i tắc: zi+4=(zi+zi+1) mod 2 m-1 „ Nếu dòng khoá bắt đầu khác vector (0,0,0,0) zi+m = ∑ cj zi+j mod 2 j=0 Æ dòng khoá có chu kỳ 15. „ trong đóc, , c ∈ Z là các hằng số cho trước. 0 m-1 2 „ Ví dụ bắt đầubằng véc tơ (1,0,0,0), dòng khoá • Ởđây khoá K gồm2m giátrị k , . . , k , c , . . , c . 1 m 0 m-1 sẽ là: •Véctơ khởi đầubấtkì(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ắnsẽ tạo nên 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 một dòng khoá có chu kỳ rấtlớn Æ hạnchế việc thám mã Truyền và bảo mật thông tin 243 Truyền và bảo mật thông tin 244 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 61
  62. Thanh ghi hồitiếptuyếntính Mã khóa tự sinh - Autokey Thanh ghi hồitiếptuyến tính (linear feedback shift register - LFSR) để tạo dòng khoá bằng phầncứng: „ Cho P = C = K = L = Z26 „ Dùng mộtbộ ghi dịch có m tầng. „ Cho z1 = k và zi = xi-1 (i ≥ 2) „ Véc tơ (k1, , km) dùng để khởitạo cho thanh ghi dịch. „ Ở mỗi đơnvị thời gian, các phép toán sau sẽđượcthựchiện „ Với0 ≤ z ≤ 25 ta xác định: đồng thời: e (x) = x + z mod 26 1. k1 đượctínhradùnglàmbit tiếp theo của dòng khoá. z 2. k2, , km sẽđượcdịch mộttầng về phía trái. dz(y) = y - z mod 26 3. Giá trị mớicủakm sẽđược tính bằng: m-1 + (x,y ∈ Z26 ) ∑ cjkj+1 j=0 k1 k2 k3 k4 Hình -LFSR cho chuổikhóazi+4=zi+zi+1 mod 2 Truyền và bảo mật thông tin 245 Truyền và bảo mật thông tin 246 Mã khóa tự sinh - Autokey II.2. Các hệ mã chuẩn „ Ví dụ: Giả sử khoá là k = 8 và bản rõ là “rendezvous”. Trướctiêntabiến đổi bản rõ thành dãy các số nguyên: „ II.2.1. Hệ DES 17 4 13 3 4 25 21 14 20 18 „ Dòng khoá như sau: „ II.2.2. Các chuẩnmãdữ liệu nâng cao 8 17 4 13 3 4 25 21 14 20 „ Bây giờ ta cộng các phầntử tương ứng rồirútgọn theo modulo 26: 25 21 17 16 7 3 20 9 8 12 „ Bảnmãở dạng ký tự là: ZVRQHDUJIM „ Để giảimã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ếptụcnhư vậychocácký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 247 Truyền và bảo mật thông tin 248 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 62
  63. II.2.1. Hệ DES Đặctả DES „ Hệ DES (Data Encryption Standard – chuẩnm㠄 DES mã hoá mộtxâubit x củabảnrõđộ dài hóa dữ liệu) 64 bit bằng một khoá 56 bit. Bảnmãnhận „ Ban đầu được IBM phát triển đượccũng là một xâu bit có độ dài 64. „ Lần đầutiênDES được công bố trong Hồ sơ Liên bang vào ngày 17.3.1975. „ Thuậttoántiến hành theo 3 bước: „ B1: Vớibảnrõchotrướcx, một xâu bit x sẽđượcxây „ Sau nhiềucuộc tranh luậncôngkhai, DES đã được 0 chấpnhậnchọnlàmchuẩnchocácứng dụng vào dựng bằng cách hoán vị các bit của x theo phép hoán vị cốđịnh ban đầuIP. Ta viết: x = IP(x) = L R , trong đóL 5.1.1977. 0 0 0 0 gồm 32 bit đầuvàR0 là 32 bit cuối. „ Đượcápdụng rộng rãi trên toàn thế giới „ Đượctrộnbởi các phép thế và hoán vị Truyền và bảo mật thông tin 249 Truyền và bảo mật thông tin 250 ThuậttoánDES ThuậttoánDES „ B2: Sau đó tính toán 16 lầnlặptheomộthàm „ Mộtvòngcủa phép mã hóa đượcmôtả như sau: 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ạitrừ) củahaixâubit „ f là một hàm sẽđượcmôtảởsau „ k1, k2, , k16 là các xâu bit có độ dài 48 được tính -1 „ B3: Áp dụng phép hoán vị ngượcIP cho xâu bit như 1 hàm của khóa k (ki chínhlàmột phép chọn hoán vị bit trong k). R16L16, ta thu đượcbảnmãy. Tứclà -1 y = IP (R16L16) . Hãy chú ý thứ tựđã đảocủaL16 và R16 Truyền và bảo mật thông tin 251 Truyền và bảo mật thông tin 252 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 63
  64. ThuậttoánDES ThuậttoánDES „ B3: Bướctiếp theo dùng 8 bảng S S , ,S ( đượcgọilà „ Mô tả hàm f: 1 2 8 các hộpS ). VớimỗiSi là mộtbảng 4×16 cốđịnh có các „ Hàm f có 2 biếnvào: hàng là các số nguyên từ 0 đến 15. Với xâu bit có độ dài 6 „ Xâu bit A có độ dài 32 (kí hiệuBi = b1 b2 b3 b4 b5 b6), ta tính Sj(Bj) như sau: „ Xâu bit J có độ dài 48 „ Hai bit b1b6 xác định biểudiễnnhị phân hàng r củaSj „ . Đầuracủa f là xâu bit có độ dài 32 (0≤ r ≤ 3) „ Các bướcthựchiện: „ Bốnbit (b2 b3 b4 b5) xác định biểudiễnnhị phân củacộtc „ B1: Biếnthứ nhấtA đượcmở rộng thành một xâu bit độ dài 48 củaSj (0≤ c ≤ 15). theo mộthàmmở rộng cốđịnh E. E(A) gồm 32 bit củaA (được hoán vị theo cách cốđịnh) với 16 bit xuấthiệnhailần. „ Khi đóSj(Bj) sẽ xác định phầntử Sj(r, c) ; phầntử này viết dướidạng nhị phân là một xâu bit có độ dài 4 „ B2: Tính E(A) ⊕ Jvàviếtkếtquả thành mộtchuỗi 8 xâu 6 bit là B1B2B3B4B5B6B7B8. „ 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 253 Truyền và bảo mật thông tin 254 ThuậttoánDES ThuậttoánDES „ Phép hoán vị ban đầuIP: P „ 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ếtquả là P(C) „ Bảng này có ý nghĩa là bit thứ 58 của x là bit đầu đượcxácđịnh là f(A, J). 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 255 Truyền và bảo mật thông tin 256 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 64
  65. ThuậttoánDES ThuậttoánDES -1 „ Phép hoán vị ngượcIP : „ Hàm mở rộng E đượcxácđịnh theo bảng sau: Truyền và bảo mật thông tin 257 Truyền và bảo mật thông tin 258 ThuậttoánDES ThuậttoánDES „ Tám hộpS: Truyền và bảo mật thông tin 259 Truyền và bảo mật thông tin 260 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 65
  66. ThuậttoánDES ThuậttoánDES „ Phép hoán vị P: Truyền và bảo mật thông tin 261 Truyền và bảo mật thông tin 262 ThuậttoánDES ThuậttoánDES „ Mô tả tính bảng khóa từ khóa k. Các bướctínhbảng khóa DES: „ Vớimột khoá k 64 bit cho trước, ta loạibỏ các bit „ Trên thựctế k là mộtxâubit độ dài 64, trong đócó kiểm tra tính chẵnlẻ và hoán vị các bit còn lạicủak 56 bit khóa và 8 bit kiểm tra tính chẵnlẻ nhằm theo phép hoán vị cốđịnh PC-1. Ta viết: PC-1(k) = phát hiệnsai. C0D0 „ Các bit ở các vị trí 8, 16, , 64 đượcxácđịnh sao „ Vớii thayđổitừ 1 đến16: cho mỗibyte chứamộtsố lẻ các số “1”. Bởivậy, Ci = LSi(Ci-1) mộtsaisótđơnlẻ có thể phát hiện được trong mỗi Di = LSi(Di-1) nhóm 8 bit. VớiLSi là phép chuyển chu trình sang trái 1 hoặc2 vị „ Các bit kiểmtrabị bỏ qua trong quá trình tính bảng trí tùy vào i: khóa. „ Đẩy1 vị trí nếu i=1,2,9 hoặc16 „ Đẩy2 vị trí đốivớicáctrường hợpcònlại Truyền và bảo mật thông tin 263 Truyền và bảo mật thông tin 264 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 66
  67. ThuậttoánDES ThuậttoánDES „ Các hoán vị PC-1 và PC-2: Truyền và bảo mật thông tin 265 Truyền và bảo mật thông tin 266 GiảimãDES Mộtvídụ về DES Ta thấyrằng trong quá trình mã hoá tại vòng i: „ Sau đây là mộtvídụ về phép mã DES. Giả sử ta mã bảnrõ(ở „ Li=Ri-1 dạng mã hexa - hệđếm16): „ R =L xor f(R ,K ) ( Vớif(R ,K )=P(E(R ) xor K )) i i-1 i-1 i i-1 i i i 0 1 2 3 4 5 6 7 8 9 A B C D E F Tức là ta cũng có: „ Bằng cách dùng khoá „ R =L i-1 i 1 2 3 4 5 7 7 9 9 B B C D F F 1 „ 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 „ Khoá ở dạng nhị phân ( không chứa các bít kiểm tra) là mã hoá tuy nhiên có sự thay đổi nhỏ: 0001001001101001010110111100100110110111101101111 „ Đầu vào là bản mã, đầu ra là bản rõ 1111000 „ Các khoá được sinh ra ngược với quá trình mã hoá, tức là sử „ Sử dụng IP, ta thu đượcL0 và R0 (ở dạng nhị phân) như sau: dụng lần lượt K16, K15, , K2, K1. L0 = 1100110000000000110010011111111 -1 Do ở vòng 16, trước khi khối qua hộp IP L16, R16 được hoán đổi L =R = 11110000101010101111000010101010 nên ở vòng 1 của quá trình giải mã ta cũng phải đổi chỗ hai 1 0 nửa sau khi khối 64 bit được qua hộp IP, Truyền và bảo mật thông tin 267 Truyền và bảo mật thông tin 268 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 67
  68. Mộtvídụ về DES Mộtvídụ về DES E(R0) = 011110100001010101010101011110100001010101010101 K1 = 000110110000001011101111111111000111000001110010 E(R15) = 001000000110101000000100000110100100000110101000 E(R0) ⊕ K1 = 011000010001011110111010100001100110010100100111 K = 110010110011110110001011000011100001011111110101 S-box outputs = 01011100100000101011010110010111 16 E(R15) ⊕ K16 = 111010110101011110001111000101000101011001011101 f(R0,K1) = 00100011010010101010100110111011 S-box outputs 10100111100000110010010000101001 L2 = R1 = 11101111010010100110010101000100 f(R15,K16) = 11001000110000000100111110011000 R16 = 00001010010011001101100110010101 E(R ) = 011101011110101001010100001100001010101000001001 -1 1 „ Cuốicùngápdụng IP vào L16,R16 ta nhận đượcbản K = 011110011010111011011001110110111100100111100101 2 mã hexa là: E(R1) ⊕K2 = 000011000100010010001101111010110110001111101100 S-box outputs = 11111000110100000011101010101110 8 5 E 8 1 3 5 4 0 F 0 A B 4 0 5 f(R1,K2) = 00111100101010111000011110100011 L3 = R2 = 11001100000000010111011100001001 Truyền và bảo mật thông tin 269 Truyền và bảo mật thông tin 270 Tranh luậnvề DES Tranh luậnvề DES „ Khi DES được đề xuấtnhư mộtchuẩnmậtmã, đãcórất nhiều „ Phản đốixácđáng nhấtvề DES chínhlàkíchthước ý kiến phê phán. của không gian khoá: 256 là quá nhỏđểđảmbảoan „ Một lý do phản đối DES có liên quan đếncáchộpS. toàn thựcsự. Nhiềuthiếtbi chuyêndụng đã được đề „ Các hộpS -chứa đựng thành phần phi tuyếncủahệ mậtlàyếutố xuấtnhằmphụcvụ cho việctấn công vớibảnrõđã quan trong nhất đốivới độ mậtcủahệ thống. biết. Phép tấn công này chủ yếuthựchiện tìm khoá „ Tuy nhiên tiêu chuẩnxâydựng các hộp S không đượcbiết đầy đủ. Một theo phương pháp vét cạn. số người đãgợiý làcáchộpS phảichứacác"cửasập" đượcdấu kín, cho phép Cục An ninh QuốcgiaMỹ (NSA) giảimãđược các thông báo „ 1977, Diffie và Hellman đãgợiý rằng có thể xây nhưng vẫngiữđượcmức độ an toàn của DES. Dĩ nhiên ta không thể dựng mộtchípVLSI (mạch tích hợpmật độ lớn) có bác bỏđượckhẳng định này, tuy nhiên không có mộtchứng cớ nào khả năng kiểmtrađược106khoá/giây. Ætìm toàn bộ được đưarađể chứng tỏ rằng trong thựctế có các cửasậpnhư vậy. khóa trong khoảng 1 ngày. Ước tính chi phí để tạo một máy như vậykhoảng 2.107$. Truyền và bảo mật thông tin 271 Truyền và bảo mật thông tin 272 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 68
  69. Tranh luậnvề DES DES trong thựctế „ 1993, Michael Wiener đã đưaramộtthiếtkế rấtcụ „ Có thể thựchiệnDES rấthữuhiệubằng cả thể về máy tìm khoá. Máy này xây dựng trên một phầncứng lẫnphầnmềm. chíp tìm khoá, có khả năng thựchiện đồng thời16 phépmãvàtốc độ tới5×107 khoá/giây. Giá củamột „ Các ứng dụng phầncứng hiệnthờicóthểđạt khung máy vào khoảng 100.000$ và nó có khả năng đượctốc độ mã hoá cực nhanh. Công ty tìm ra một khoá của DES trong khoảng 1,5 ngày. Một Digital Equipment đã thông báo tạihộinghị thiếtbị dùng 10 khung máy như vậycógiáchừng 106 CRUPTO'92 rằng họ sẽ chế tạomộtchípcó $ sẽ giảmthời gian tìm kiếm khoá trung bình xuống 50 ngàn tranzistor có thể mã hoá vớitốc độ 1 còn 3,5 giờ. Hiện nay, ngườitarútngắnthời gian tìm Gbít/s bằng cách dùng nhịpcótốc độ 250MHz. khóa còn khoảng hơn2h. Giá củachípnàyvàokhoảng 300$. Truyền và bảo mật thông tin 273 Truyền và bảo mật thông tin 274 DES trong thựctế Double DES và Triple DES „ Tớinăm 1991 đãcó45 ứng dụng phầncứng và chương trình „ DES bội hai cơ sở củaDES đượcUỷ ban tiêu ChuẩnquốcgiaMỹ (NBS) chấpthuận. „ Mã hóa: „ Một ứng dụng quan trọng của DES là trong giao dịch ngân C = DESK2[DESK1(M)] hàng Mỹ - (ABA) DES được dùng để mã hoá các sốđịnh danh „ Giảimã: cá nhân (PIN) và việc chuyển tài khoảnbằng máy thủ quỹ tự M = DES -1[DES -1(C)] động (ATM). DES cũng đượcHệ thống chi trả giữa các nhà K1 K2 56 băng củaNgânhànghối đoái (CHIPS) dùng để xác thựccác ¾ Có 2 sự lựachọncho 56 giao dụch vào khoảntrên1,5×1012 USA/tuần. DES còn được khóa K1 và 2 sự lựa sử dụng rộng rãi trong các tổ chức chính phủ. Chẳng hạnnhư chọn cho khóa K2. Bởivậy bộ năng lượng, Bộ Tư pháp và Hệ thống dự trữ liên bang. có 2112 sự lựachọncho cặp khóa (K1, K2) Truyền và bảo mật thông tin 275 Truyền và bảo mật thông tin 276 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 69
  70. II.2.2. Các chuẩnmãdữ liệunâng Double DES và Triple DES cao (AES) „ Nguồngốc AES (Advanced Encryption Standards) : „ DES bộiba „ Rõ ràng cầnphảithaythế DES, vì có những tấn công về mặtlýthuyếtcó thể bẻđượcnó. „ Mã hóa: „ Do đóViệnchuẩnquốc gia Hoa kỳ US NIST ra lờikêugọitìmkiếmchuẩn −1 C = DES {DES []DES ()M } mã mớivàonăm 1997. Sau đó có 15 đề cửđượcchấpnhận vào tháng 6 K1 K 2 K1 năm 1998. Và đượcrútgọncòn5 ứng cử viên vào tháng 6 năm 1999. Đến „ Giảimã: tháng 10 năm 2000, mã Rijndael đượcchọn làm chuẩn mã nâng cao và đượcxuấtbảnlàchuẩn FIPS PUB 197 vào 11/2001. M = DES−1 DES DES−1 ()C K1{ K2 [ K1 ]} „ Yêu cầucủaAES ¾ Với TDES việc tìm khóa „ Là mã khối đốixứng khoá riêng. „ Kích thướckhốidữ liệu 128 bit và độ dài khoá là tùy biến: 128, 192 hoặc vét cạnyêucầu 256 bit. khoảng: „ Chuẩnmãmớiphảimạnh và nhanh hơn Triple DES. Mã mớicócơ sở lí 112 = 23 thuyếtmạnh để thờigiansống củachuẩnkhoảng 20-30 năm(cộng thêm 2 5,1923.10 phép thờigianlưutrữ). tính TDES, bởivậy „ Khi đưa ra thành chuẩnyêucầucungcấp chi tiếtthiếtkế và đặctảđầy đủ. thựctế khócóthể thám Đảmbảorằng chuẩnmãmớicàiđặthiệuquả trên cả C và Java. mã thành công. Truyền và bảo mật thông tin 277 Truyền và bảo mật thông tin 278 Thảoluận chung về hệ mậtmãđối Các chuẩnmãdữ liệu nâng cao xứng „ Chuẩn mã nâng cao AES – Rijndael: có các „ Tính an toàn, phụ thuộc vào: đặctrưng sau: „ Không gian khóa phải đủ lớn để xác suất thành công khi tìm kiếmngẫunhiênlàrấtnhỏ „ Có 128/192/256 bit khoá và 128 bit khốidữ liệu. „ Vớicácphéptrộnthíchhợpcáchệ mã đốixứng „ Thiếtkếđể: có thể ra mộthệ mã mới có tính an toàn cao „ chống lạicáctấn công đãbiết „ Vấn đề bảomậtkhitruyền khóa cần đượcxử lý „ tốc độ nhanh và nén mã trên nhiềuCPU nghiêm túc: „ Đơngiản trong thiếtkế „ Sử dụng kênh an toàn „ Sử dụng nghi thức Truyền và bảo mật thông tin 279 Truyền và bảo mật thông tin 280 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 70
  71. Thảoluận chung về hệ mậtmãđối Thảoluận chung về hệ mậtmãđối xứng xứng „ Ví dụ, vớicáchệ mã giao hoán, có thể sử dụng nghi thức sau, giả sử A cầntruyềnthồndiệpw choB, mỗi „ Thám mã: bên sử dụng hệ mã riêng: „ Phương pháp thám mã tùy thuộcvàotừng hệ mã. „ A gửieA(w) cho B „ „ B gửieB(eA(w)) cho A Có thể kếthợp các đặctrưng thống kê và bản rõ „ A gửidA(eB(eA(w))=dA(eA(eB(w))= eB(w) cho B „ B giảimãdB(eBw) = w „ Về nguyên tắc, có thể bẻ khóa các hệ mã đối xứng vớithờigianvàphương pháp thích hợp „ Cài đặt: hầuhếtcóthể cài đặttương đốidễ vớitốc độ thực thi cao eB eA A B Truyền và bảo mật thông tin 281 Truyền và bảo mật thông tin 282 II.1. Tổng quan về các hệ mã khóa Chương III. Hệ mã khóa công khai công khai II.1. Tổng quan về các hệ mã khóa công khai „ Hệ thống bảomật đốixứng: dễ dàng xác định một II.2. Hệ mật Merkle – Hellman khóa khi biếtkhóakiaÆ không đảmbảobảomậtnếu xác suấtkhóagửibị lộ cao. II.3. Hệ mậtRSA „ Ý tưởng hệ mật mã công khai thuộcvề Diffie và II.4. Tổng kết Hellman(1975): Việcbiếtek không làm lộ dk: người thám mã biếtek (về nguyên tắccóthể biết hàm ngượccủaek –tứclàdk), tuy nhiên việc tính dk là bất trị, ít ra là đốivớihầuhết các khóa. Hàm ek như trên gọilàhàmmộtphía Truyền và bảo mật thông tin 283 Truyền và bảo mật thông tin 284 Truyền và bảo mật thông tin - Nguyễn Văn Khang - ĐHSP Huế 71