Nghiên cứu phương pháp phát hiện thiết bị thu làm “lộ” khoá bí mật

BÁO CÁO TỐT NGHIỆPĐề tài: Nghiên cứu phương pháp phát hiện thiết bị thu làm “lộ” khoá bí mật GV hướng dẫn: PGS.TS Trịnh Nhật Tiến Sinh viên: Đỗ Thị Loan Mã SV: 10409 Lớp: CT 7011Chương 1: CÁC KHÁI NIỆM CƠ BẢN1.1 Một số khái niệm  + Trung tâm quảng bá (Center, Broadcast Center), nhà cung cấp dữ liệu (NCCDL-Data Provider): Trung tâm có các kênh phát thông tin quảng bá tới các thiết bị thu dữ liệu. + Thiết bị thu dữ liệu (TBTDL - User): thu dữ liệu phát ra từ NCCDL và dùng các khoá bí mật của nó để giải mã dữ liệu thu được. + Thông điệp hay bản tin (Message): là thông tin hay đoạn thông tin được NCCDL gửi đến TBTDL qua các kênh quảng bá.2 + Khoá thời gian tồn tại ít (Short-lived key-session key): là khóa được duy trì trong một phiên truyền dữ liệu gọi tắt là khoá phiên. + Khoá thời gian tồn tại dài (long- lived key): là khoá tồn tại trong thời gian dài của hệ thống, gọi tắt là khoá thời gian dài hay khoá “dài”. + Bộ khoá nhái: là bộ khoá mà kẻ gian đã (dùng phương pháp nào đó,ví dụ thám khoá) thu được từ tập khoá của một số TBTDL. + Thiết bị thu bất hợp pháp (Traitor): là TBTDL làm rò rỉ khoá hay TBTDL sử dụng bộ khoá nhái để giải mã bản tin nhận được từ NCCDL.31.1.1 Các ký hiệu sử dụng:N: Tập tất cả các TBTDL, |N|=n.u1,..., un : ký hiệu các TBTDL.R: Tập các TBTDL bất hợp pháp, |R|=r.P: Tập các TBTDL hợp pháp, P=N-R.K: Khoá phiên.L: Khoá “d ài”.M: Thông điệp hay bản tin.CM: Bản mã của thông điệp M.tM: Bản tin thử nghiệm. Lu tập các khoá “dài” của TBTDL ui, i=1, 2,, n.|Lu |: số lượng các khoá “dài” của TBTDL ui.Si: Tập các TBTDL dùng chung một khoá “dài” Li.Si,j = Si – Sj: chứa các TBTDL thuộc phần bù của tập Si so với tập Sj.Các TBTDL trong tập Si,j dùng chung khoá “dài” Li,j.41.1.2 Vấn đề mã hoá1.1.2.1 Khái niệm hệ mã hoáMã hóa là quá trình chuyển những thông tin nhận biết được thành những thông tin “khó” nhận biết được1.1.2.2 Phân loại mã hoáCác hệ thống mã hoá trong máy tính thuộc một trong hai loại: + Mã hoá với khoá đối xứng (Symmetric-key Encryption)  + Mã hoá với khoá công khai (Public-key Encryption) 51.1.3 Khái niệm “phủ” Cho một họ các tập con khác rỗng S = { S1, S2, ..., Sw}, Sj N, j=1,, w.Cho tập khác rỗng P N; phủ của tập P là tập Si , Si ,, Si ,{i1,i2,..., it} {1,..., w} và thoả mãn điều kiện:P = Si ∩ Si =Φ, ij ≠ ikKích thước của một phủ là số lượng các tập con tạo nên phủ đó.Ví dụ ở đây, kích thước của phủ P là t.61.2 Khái niệm “Khung phủ tập con” ( Subset Cover Framework – SCF)  Trong SCF, có giải thuật xác định các tập con S1, S2, ..., Sw N, = N. Mỗi tập Si có khoá “dài” Li. Mỗi u € Si đều tính được Li từ tập khoá Lu của mình. Tập P phải được phân hoạch thành các tập con rời rạc Si , Si ,, Si sao cho: P =  Các khoá “dài” tương ứng với các tập Si ,Si ., Si là Li , Li , ..., Li . SCF sử dụng hai giải thuật mã hoá E và F: + Giải thuật E: {0,1}*→{0,1}*, mã hoá khóa phiên K, lần lượt  với từng khoá “dài” Li , Li , ..., Li , nhận được các bản mã: E(K, Li ),  E(K, Li ), ..., E(K, Li ). + Giải thuật F : {0,1}*→ {0,1}*, mã hoá thông điệp M sử dụng khóa phiên K, nhận được bản mã: FK(M).71.3 Giải pháp lưu vết thiết bị thua) Bài toán lưu vết NCCDL truyền thông điệp M tới TBTDL (|N| = n). Mỗi TBTDL ui có một tập khoá “dài” (bí mật) Lu (i = 1, 2,..., n).Trong tập N có tập R các TBTDL làm lộ khoá bí mật và tập P các TBTDL hợp pháp. P, R thoả mãn: P R = N, P ∩ R = Φ Yêu cầu NCCDL xác định được định danh các TBTDL thuộc R và phân hoạch P thành các tập con chứa các TBTDL hợp pháp.b) Giải pháp lưu vết Sử dụng “khung phủ tập con” để phát hiện R* Thuật toán lưu vết TBTDL làm lộ khoá bí mật:Xác định định danh của TBTDL làm lộ khoá bí mật dựa trên sự phân hoạch tập TBTDL thành các tập con.8 1.4 Cây nhị phâna. Khái niệm câyCây là đồ thị đơn, vô hướng, liên thông và không có chu trình.b. Khái niệm cây nhị phânCây nhị phân (hình 1.2) là cây có hai dạng nút: Nút ngoài: nút lá, không có con. Nút trong: có chính xác hai con là con trái và con phải.9GốcNút cha của vNút vCon phải của vCon trái của vNút aNút bNút c Hình 1.2: Cây nhị phân 10Cây nhị phân đầy đủ (hình 1.3) là cây nhị phân, trong đó tất cả các lá có cùng khoảng cách tới gốc.Số lượng các lá trong cây nhị phân đầy đủ (có chiều cao k) là h = 2k.G ốcNút aNút bNút c11Cha chung thấp nhất của hai nút (kể cả lá) a, b (hình 1.4) là nút giao nhau giữa đường đi từ a tới gốc và từ b tới gốc.Cây con t là đồ thị con của T và thỏa mãn các tính chất của một cây.Hình 1.4: Cha chung thấp nhất của a và b GốcCha chung thấp nhất của a và bNút aNút b12c. Tính chất cây nhị phân1) Cây nhị phân có r lá, thì có chiều cao ít nhất là 2) Thuộc tính rẽ nhánh Một cây nhị phân luôn có thể chia thành hai nhánh trái và phải ( hình 1.5).Thuộc tính này được gọi là thuộc tính rẽ nhánh của cây nhị phân [3].13Chương 2: PHƯƠNG PHÁP DÒ TÌM THIẾT BỊ THU BẰNG “KHUNG PHỦ TẬP CON”2.1 Khái niệm lưu vết TBTDL bất hợp pháp Khi NCCDL biết ở ngoài chợ đã bán chìa khoá nhái hay trên Internet cho tải về miễn phí, thì NCCDL này biết là khoá hay một phần của bộ khoá đã bị rò rỉ. Bằng cách nào đó NCCDL này tìm ra được thiết bị thu nào đã làm rò rỉ khoá để trừng phạt thiết bị thu đó (bằng cách không cho thu dữ liệu mặc dù thiết bị đó có khoá thật, vô hiệu hoá khoá đã bị rò rỉ).14Phương pháp lưu vết của NCCDL đối với một TBTDL _TN:Phần mềm(PM)TBTDL Thi nghiemP = {Si ,,Si }RNCCDLPhat quang ba CtMHinh 1: Mô hình phát hiện TBTDL làm rò rỉ khoá “dài”152.2 Giải thuật lưu vết sử dụng tập con2.2.1 Giải thuật lưu vết sử dụng tập con.)Ý tưởng:  Tìm TBTDL bất hợp pháp bằng cách phân hoạch tập các TBTDL thành tập P và R.  Đầu tiên, giải thuật được thực hiện với P = {S1}, R =Φ . Sau khi thực hiện K lần. Tập P và R được lưu vào CSDL của NCCDL . Tại lần k+1, NCCDL thu mua bộ khoá nhái, đưa vào dùng trong TBTDL_TN Nếu TBTDL_TN giải mã bản tin thử nghiệm tM với xác suất η 1 Phần mềm chia Si thành hai tập bằng nhau, bổ sung hai tập này vào P, loại bỏ Si khỏi tập P.Tiếp tục thực hiện phương pháp phát hiện với phân hoạch P mới, cho đến khi TBTDL_TN giải mã tM với xác suất nhỏ hơn 1, thì lưu P, R mới vào CSDL của NCCDL và kết thúc lưu vết đối với TBTDL_TN này.172.2.2 Hàm tìm tập con chứa TBTDL làm rò rỉ khoáHàm Tim_j tìm tập con chứa TBTDL làm rò rỉ khoá, giống như phương pháp tìm kiếm nhị phân, để tìm giá trị j tương ứng khoá “dài” Li. Đó là khoá nằm trong bộ khoá nhái, mà TBTDL_TN đang thí nghiệm.Hàm Tim_j dùng phương pháp mã hoá khoá phiên giả KP (K Pseudo) để tìm ra chỉ số j, qua sự chênh lệch xác suất giải mã tM của TBTDL_TN, giữa hai lần mã hoá kề nhau. Khoá phiên giả KP có cùng độ dài với khoá phiên K.Đặt pj (j=0,..., m) là xác suất giải mã bản tin tM của TBTDL_TN khi NCCDL mã hoá j lần với khóa phiên giả KP và (m - j) lần với khóa đúng K.182.3 Ví dụ về giải thuật lưu vết Để dễ hình dung phương pháp phát hiện TBTDL bất hợp pháp, ta lấy ví dụ với tập n = 8 TBTDL là {u1, u2, u3, u4, u5, u6, u7, u8}. Giả sử đây là lần đầu NCCDL thực hiện tìm kiếm TBTDL bất hợp pháp. Các nút (kể cả lá) được gán nhãn L1, L2,..., L15.Giải thuật SCF duy trì các tập con S1, S2,..., S15.Trong đó Si là tập các lá (tương ứng với các TBTDL) của cây nhị phân con gốc Vi (i...