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

huộ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. 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 được                           1.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 sau: Mã hoá với khoá đối xứng (Symmetric-key Encryption) Mã hoá với khoá công khai (Public-key Encryption) 1.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 i k Kí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. 1.2 KHÁI NIỆM “KHUNG PHỦ TẬP CON” Giới thiệu “khung phủ tập con” ( Subset Cover Framework – SCF) được dùng trong phương pháp phát hiện thiết bị thu làm lộ khoá bí mật. 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. Lưu ý:  Các TBTDL u  Si sử dụng chung khoá “dài” Li, j = 1, 2,..., m 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). 1.3 CÂY NHỊ PHÂN a. Khái niệm cây Câ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ân Cây nhị phân 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.          Cây nhị phân đầy đủ 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. Cha chung thấp nhất của hai nút (kể cả lá) a, b là nút giao nhau giữa đường đi từ a tới gốc và từ b tới gốc. c. Tính chất cây nhị phân 1) 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  Chươ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 hoặc trên Internet cho tải về miễn phí, thì NCCDL này biết là bộ khoá hoặc một phần của bộ khoá đã bị rò rỉ. Bằng cách nào NCCDL tìm ra được thiết bị thu đã 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ỉ).       Để xác định TBTDL làm rò rỉ khóa, NCCDL tạo ra TBTDL, làm thí nghiệm “ tại gia” với các bộ khoá nhái (họ mua về). NCCDL phát bản tin thử nghiệm, theo dõi những phản ứng của TBTDL thí nghiệm này, để truy tìm TBTDL đã làm rò rỉ khoá “dài “ ra bên ngoài. Chú ý rằng NCCDL đó có toàn bộ cấu trúc cây mô tả n TBTDL với giả thiết n= |N| = 2k. Để thực hiện mục tiêu đó, NCCDL dùng phần mềm (PM) để tìm tập R các TBTDL làm lộ khoá, phân hoạch tập P các TBTDL hợp pháp thành các tập con  Si, Si,…, Si, có các khoá “dài” tương ứng Li, Li, ..., Li. Khi phát dữ liệu thật, NCCDL dùng SCF để phát quảng bá thông điệp M tới các TBTDL. NCCDL dùng các khoá “dài” Li, Li, ..., Li để mã hoá khoá phiên K. Do đó chỉ có các TBTDL hợp pháp thuộc một trong các tập Si, Si,…, Si mới giải mã được khoá phiên K, sau đó dùng K để giải mã đúng thông điệp M. Các TBTDL bất hợp pháp (TBTDL dùng bộ khoá nhái hay TBTDL làm lộ khoá) sẽ không giải mã được K, và do đó không thể giải mã chính xác thông điệp M. Phương pháp lưu vết của NCCDL đối với một TBTDL _TN:    NCCDL phát thử nghiệm thông điệp tM, PM quan sát xác suất giải mã của TBTDL _TN để xác định tập R chứa các TBTDL làm lộ khoá “dài”, và phân hoạch tập P các TBTDL  hợp pháp thành P = { Si, Si,…, Si}.   Tìm được P, R thì PM lưu P, R vào cơ sở dữ liệu (CSDL) của NCCDL để phục vụ cho lần tìm kiếm tiếp theo. Giải pháp này giả thiết TBTDL _TN không thể phát hiện được nó đang bị thử nghiệm, tức là nó không thể tự động tắt máy khi đang thu dữ liệu thử nghiệm từ NCCDL. Trên thực tế có nhiều giải pháp phát hiện TBTDL làm lộ khoá “dài”, ở đây trình bày phương pháp phát hiện TBTDL làm rò rỉ khoá “dài” dựa trên phương pháp tìm kiếm nhị phân và dùng giải thuật SCF để phát tin thử nghiệm tM tới các TBTDL _TN. Phần mềm (PM) TBTDL  thí nghiệm P = { Si, …, Si} R Phát Quảng bá Ctm NCCDL Hinh 1: Mô hình phát hiện TBTDL làm rò rỉ khoá “dài” 2.2 GIẢI  THUẬT  LƯU VẾT  SỬ  DỤNG  TẬP  CON (SUBSET TRACING) 2.2.1 Giải thuật lưu vết sử dụng tập con. Ý tưởng của giải thuật lưu vết TBTDL làm rò rỉ khoá sử dụng tập con là: 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. Trong đó P = {Si, Si,…, Si} gồm các tập con chứa TBTDL hợp pháp, R là tập các TBTDL bất hợp pháp. Đầu tiên, thuật toán được thực hiện với P = {S1}, S1 là tập các TBTDL, R = Æ. Sau khi thực hiện k lần, sẽ được phân hoạch P = {Si, Si,…, Si} và tập R các TBTDL bất hợp pháp. 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, thử dùng trong TBTDL_TN. PM dùng hàm Tim_j để tìm tập con chứa TBTDL làm lộ khoá dài. Kết hợp với P, R trước đó trong CSDL của NCCDL để xác định P, R mới Mỗi pha thực hiện Tim_j với tập P = {Si, Si,…, Si} và R. Nếu TBTDL_TN giải mã bản tin thử nghiệm tM với xác suất  < 1 thì kết thúc, P và R giữ nguyên, yên tâm vì bộ khoá nhái không có tác dụng. Ngược lại, tức là TBTDL_TN giải mã tM với xác suất =1. Điều đó chứng tỏ bộ khoá nhái có chìa khoá “dài” Li, nhờ nó mà TBTDL_TN đã giải mã được khoá phiên K. Khoá “dài” Li. chắc chắn phải do TBTDL nào đó trong tập Si, đã làm lộ ra ngoài. Vì vậy thực hiện thủ tục Tim_j để tìm chỉ số j sao cho Si có chứa TBTDL làm lộ khoá “dài” Li.       Nếu Sichỉ chứa một TBTDL thì R = R  Si, và loại bỏ Sikhỏi tập P. Ngược lại, tức là | Si| > 1, khi đó PM chia Si thành hai tập bằng nhau, bổ sung hai tập này vào P, loại bỏ Sikhỏ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. Phương pháp phát hiện ở đây chỉ có tính chính xác tương đối, vì một số TBTDL chỉ làm lộ một phần của bộ khoá, không thể phát hiện được chính xác TBTDL nào đã làm lộ toàn bộ bộ khoá. Do đó không thể đưa chúng vào tập R các TBTDL bất hợp pháp. Mục đích chính của phương pháp lưu vết này là lưu lại định danh của những TBTDL làm rò rỉ khoá, và trừng trị những TBTDL bất hợp pháp. Nghĩa là danh sách các TBTDL làm rò rỉ khoá sẽ được lưu trong CSDL, và P được phân hoạch thành các tập con chứa các TBTDL hợp pháp để khi NCCDL phát thông điệp M, những TBTDL bất hợp pháp chỉ giải mã được  M’ ≠ M. 2.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, khi đó bản mã như sau: .   Như vậy, nếu TBTDL_TN giải mã đúng bản tin tM, thì p0 = 1, pm = 0: p0 là xác suất giải mã bản tin tM (mã hoá m lần với khoá đúng K): p1 là xác suất giải mã bản tin tM (mã hoá 1 lần với khoá giả KP,     (m - 1) lần với khoá đúng K): ... pj-1 là xác suất giải mã bản tin tM (mã hoá (j - 1) lần với khoá giả KP, (m – j + 1) lần với khoá đúng K): pj  là xác suất giải mã bản tin tM (mã hoá j lần với khoá giả KP,   (m - j) lần với khoá đúng K): ... pm là xác suất giải mã bản tin tM (mã hoá m lần với khoá giả KP): Định lý 2.1 Nếu | pj-1 – pj |> 0 thì TBTDL_TN dùng khóa “dài” Li của tập Si (tức là có ít nhất một TBTDL trong Si đã làm rò rỉ khóa “dài” Li) Định lý 2.1 được phát biểu lại như sau: Nếu | pj-1 – pj | >  thì TBTDL_TN dùng khóa “dài” Li của tập Si. 2.3 VÍ DỤ VỀ GIẢI THUẬT LƯU VẾT Ta lấy ví dụ với tập n = 8 TBTDL là {u1, u2, u3, u4, u5, u6, u7, u8}. NCCDL biểu diễn 8 TBTDL thành cây nhị phân T. Các lá của T tương ứng với các TBTDL. 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, Si có khoá “dài” Li tương ứng với nhãn tại nút vi, i=1,…, 15. S1 = {u1, u2, u3, u4, u5, u6, u7, u8}, S2 = {u1, u2, u3, u4}, S3 = {u5, u6, u7, u8}, S4 = {u1, u2}, S5 = {u3, u4}, S6 = {u5, u6}, S7 = {u7, u8}, S8 = {u1}, S9 = {u2}, S10 = {u3}, S11 = {u4}, S12 = {u5}, S13 = {u6}, S14 = {u7}, S15 = {u8}. Gốc V1 L1   V2  V3  V4  V5   V6 V15   V8   V9 V10 V12 V14 U7 L14 L13 U6 L 12 U5  L11 U4 L10 U3    L9 L8 U1 U2 L2 V13 L3 L4 L5 L6 L7  V11   V7 L15 U8 Bộ khoá “dài” của TBTDL ui là tập các nhãn từ lá tương ứng với nó tới gốc. Cụ thể: Lu = {L8, L4, L2, L1}, Lu = {L9, L4, L2, L1}, Lu = {L10, L5, L2, L1}, Lu = {L11, L5, L2, L1}, Lu = {L12, L6, L3, L1}, Lu = {L13, L6, L3, L1} Lu = {L14, L7, L3, L1}, Lu = {L15, L7, L3, L1}.         Giả sử đây là lần đầu NCCDL thực hiện lưu vết TBTDL làm rò rỉ khoá.          NCCDL thu mua được bộ khoá nhái, đưa bộ khoá này vào dùng trong TBTDL_TN để phát hiện TBTDL làm rò rỉ khoá “dài”. Quá trình thực hiện lưu vết như sau: Khởi tạo: P º {S1} = {u1, u2, u3, u4, u5, u6, u7, u8}, R = Æ. Bước 1: PM thực hiện thủ tục Lưu_vet(P), P = {S1}. +  NCCDL phát thử nghiệm bản tin tM (tM tuỳ ý) thông qua bản mã: Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L1, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. +  If TBTDL_TN giải mã được tM với xác suất p < 1 then Begin          P = {S1}; R = Æ; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; + Else (Tức là: TBTDL_TN giải mã được tM với xác suất p = 1).  Chứng tỏ rằng: S1 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L1. (TBTDL_TN có khoá L1). Công việc tiếp theo: Xác định TBTDL Î S1 đã làm rò rỉ L1. Nếu |S1| = 1 thì chính TBTDL duy nhất của S1 làm rò rỉ L1. Nhưng vì S1 gồm 8 TBTDL, nên phải chia S1 thành hai tập con, được S2 và S3 để xác định tiếp TBTDL của S2 hay S3 làm rò rỉ L1. S2 = {u1, u2, u3, u4}, S3 = {u5, u6, u7, u8}, Chuyển sang bước 2. Bước 2: PM thực hiện thủ tục Luu_vet(P), P = {S2, S3}. + NCCDL phát thử nghiệm bản tin tM (tM tuỳ ý) thông qua bản mã: Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L2, L3, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. + If  TBTDL_TN  giải mã được tM với xác suất p < 1 then Begin  P = {S2, S3}; R = Æ; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; + Else (Tức là: TBTDL_TN giải mã được tM với xác suất p = 1. Chứng tỏ rằng TBTDL_TN đã có L2 hoặc L3). Như vậy S2 đã làm rò rỉ L2, hoặc S3 đã làm rò rỉ L3. PM thực hiện thủ tục Tim_j(P) để xác định rõ TBTDL nào đã làm rò rỉ khoá L2 hoặc L3, P = {S2, S3}: Khởi tạo: [a, b] là [0, 2]           //Trong đó 2 là số lượng tập con của P = {S2, S3} = {Si, Si}. Do a ≠ b - 1 (0 ≠ 2 - 1) → c =  =  = 1 NCCDL phát thử nghiệm bản tin tM với c = 1 lần dùng khoá giả KP, thông qua bản mã: If |pa - pc| >  then Begin b := c (= 1); pb := pc;  End; Do a = b - 1 (0 = 1 - 1) → S3 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L2 (tức là TBTDL_TN có khoá “dài” L2).          (B2.1) Else Begin a := c (=1); pa := pc; End; Do a = b – 1 (1 = 2 - 1) → S3 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L3 (tức là TBTDL_TN có khoá “dài” L3).                 (B2.2) Bước 3: Giả sử S2 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L2  (từ B2.1) Nếu |S2| = 1 thì chính TBTDL duy nhất đã làm rò rỉ khoá L2. Nhưng vì S2 chứa 4 TBTDL là {u1, u2, u3, u4}, nên PM chia S2 thành 2 tập con S4 và S5 để xác định tiếp S4  hay S5 làm rò rỉ khoá. S4 = {u1, u2}, S5 = {u3, u4}, S3 = {u5, u6, u7, u8}. PM thực hiện thủ tục Luu_vet(P), P = {S4, S5, S3} = {Si, Si, Si}. + NCCDL phát thử nghiệm bản tin tM thông qua bản mã Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L4, L5, L3, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. +  If  TBTDL_TN  giải mã được tM với xác suất p < 1 then Begin  P = { S4, S5, S3}; R = Æ; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; + Else (Tức là: TBTDL_TN giải mã được tM với xác suất p = 1. Chứng tỏ rằng TBTDL_TN đã có ít nhất một trong các khoá “dài” L4, L5, L3). Như vậy S4 đã làm rò rỉ L4, hoặc S5 làm rò rỉ L5, hoặc S3 làm rò rỉ L3.  PM thực hiện thủ tục Tim_j(P) để xác định rõ TBTDL nào đã làm rò rỉ khoá L4 hoặc L5  hoặc L3, P = { S4, S5, S3}: Khởi tạo: [a,b] là [0,3] //Trong đó 3 là số lượng tập con trong P. Do a ≠ b - 1 (0 ≠ 3 - 1) → c =  =  = 1 NCCDL phát thử nghiệm bản tin tM với c = 1 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p1). If |pa - pc| >  then Begin b := c (= 1); pb := pc (= p1);  End; Do a = b - 1 (0 = 1 - 1) → S4 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L4 (tức là TBTDL_TN có khoá “dài” L4).              (B3.1)  Else Begin a := c (= 1); pa := pc (= p1); End; Do a ≠ b – 1 (1 ≠ 3 - 1) → c: =  =  = 2 NCCDL phát thử nghiệm bản tin tM với c = 2 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p2). If |pa - pc| > (Tức là |p1 – p2| > ) then Begin b := c (= 2); pb := pc (= p2);  End; Do a = b – 1 (1 = 2 - 1) → S5 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L5 (tức là TBTDL_TN có khoá “dài” L5).       (B3.2)  Else Begin a := c (= 2); pa := pc (= p2); End; Do a = b - 1 (2 = 3 - 1) → S3 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L3 (tức là TBTDL_TN có khoá “dài” L3).      (B3.3) Bước 4: Giả sử S4 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L4 (từ B3.1) Do S4 chứa 2 TBTDL là {u1, u2} nên PM chia S4 thành hai tập con S8 và S9. P = {S8, S9, S5, S3}. Trong đó: S8  = {u1}, S9 = {u2}, S5 = {u3, u4}, S3 = {u5, u6 u7, u8}. PM thực hiện thủ tục Luu_vet(P), P = {S8, S9, S5, S3} + NCCDL phát thử nghiệm bản tin tM thông qua bản mã Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L8, L9, L5, L3, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. +  If  TBTDL_TN giải mã được tM với xác suất p < 1 then Begin  P = { S8, S9, S5, S3}; R = Æ; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; + Else, (Tức là: TBTDL_TN giải mã được tM với xác suất p = 1. Chứng tỏ rằng TBTDL_TN đã có ít nhất một trong các khoá “dài” L8, L9, L5, L3). Như vậy S8 đã làm rò rỉ L8, hoặc S9 làm rò rỉ L9, hoặc S5 làm rò rỉ L5, hoặc S3 làm rò rỉ L3.  PM thực hiện thủ tục Tim_j(P) để xác định rõ TBTDL nào đã làm rò rỉ khoá L8 hoặc L9  hoặc L5  hoặc L3, P = {S8, S9, S5, S3} như sau: Khởi tạo: [a, b] là [0, 4] //Trong đó 4 là số lượng tập con trong       P = {S8, S9, S5, S3}. Do a ≠ b - 1 (0 ≠ 4 - 1) → c :=  =  = 2 NCCDL phát thử nghiệm bản tin tM với c = 2 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p2). If |pa - pc| >  (Tức là |p0 – p2| > ) then Begin b := c (= 2); pb := pc (= p2);  End Do a ≠ b - 1 (0 ≠ 2 - 1) → c :=  =  = 1 NCCDL phát thử nghiệm bản tin tM với c = 1 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p1). If |pa - pc| >  (Tức là |1 – p1| > ) then Begin b := c (= 1); Pb := pc (= p1); End Do a = b - 1 (0 = 1 - 1) → S8 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L8 (tức là TBTDL_TN có khoá “dài” L8).       (B4.1) Else Begin a := c (= 1); pa := pc (= p1); End;         Do a = b – 1 (1 = 2 - 1) → S9 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L9 (tức là TBTDL_TN có khoá “dài” L9).       (B4.2)  Else Begin a := c (= 2); pa := pc (= p2); End; Do a = b - 1 (2 = 3 - 1) → S3 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L3 (tức là TBTDL_TN có khoá “dài” L3).      (B4.3) Bước 5: Giả sử S8 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L8 (từ B4.1) Do S8 chỉ gồm một TBTDL là {u1} nên: R = R  {u1} = {u1}. P = {S9, S5, S3} Bước 6: PM thực hiện thủ tục Luu_vet(P), P = {S9, S5, S3}. Trong đ ó: S9  = {u2}, S5 = {u3, u4}, S3 = { u5, u6, u7, u8}. + NCCDL phát thử nghiệm bản tin tM (tM tuỳ ý), thông qua bản mã Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L9, L5, L3, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. +  If  TBTDL_TN  không thể giải mã được tM với xác suất p = 1 then Begin  P = {S9, S5, S3}; R = {u1}; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; + Else, (Tức là: TBTDL_TN giải mã được tM với xác suất p = 1. Chứng tỏ rằng TBTDL_TN đã có ít nhất một trong các khoá “dài” L9, L5, L3). Như vậy S9 rò rỉ L9, hoặc S5 rò rỉ L5, hoặc S3 rò rỉ L3.  PM thực hiện thủ tục Tim_j(P) để xác định rõ TBTDL nào đã làm rò rỉ khoá L9 hoặc L5  hoặc L3, P = {S9, S5, S3}: Khởi tạo: [a,b] là [0,3] //Trong đó 3 là số lượng tập con trong P Do a ≠ b - 1 (0 ≠ 3 - 1) → c :=  =  = 1 NCCDL phát thử nghiệm bản tin tM với c = 1 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p1). If |pa - pc| >  then Begin b := c (= 1); pb := pc (= p1);  End; Do a = b - 1 (0 = 1 - 1) → S9 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L9 (tức là TBTDL_TN có khoá “dài” L9).       (B6.1) Else Begin a := c (= 1); pa := pc (= p1); End; Do a ≠ b - 1 (0 ≠ 3 - 1) → c :=  =  = 2 NCCDL phát thử nghiệm bản tin tM (tM tuỳ ý) với c = 2 lần dùng khoá giả KP, thông qua bản mã: PM tính pc (p2). If |pa - pc| >  (Tức là |p1 – p2| > ) then Begin b := c (= 2); Pb := pc (= p2); End Do a = b - 1 (1 = 2 - 1) → S5 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L5 (tức là TBTDL_TN có khoá “dài” L5).       (B6.2) Else Begin a := c (= 2); pa := pc (= p2); End;         Do a = b - 1 (2 = 3 - 1) → S3 chứa ít nhất một TBTDL làm rò rỉ khoá “dài” L3 (tức là TBTDL_TN có khoá “dài” L3).       (B6.3) Bước 7: Giả sử S3  chứa TBTDL làm rò rỉ khoá (từ B6.3). Do S3  có bốn  TBTDL là  {u5, u6, u7, u8} nên chia S3 thành hai tập con  S6 và S7  P = {S6, S7, S9, S5) Trong đó: S6 = {u5, u6}, S7 = {u7, u8}, S9 = {u2}, S5 = {u3, u4}.                PM thực hiện thủ tục Luu_vet(P), P = {S6, S7, S9, S5}. + NCCDL phát thử nghiệm bản tin tM (tM tuỳ ý), thông qua bản mã Trong đó phần đầu là bản mã của khoá phiên K, được mã hoá bằng khoá “dài” L6, L7, L9, L5, phần thân là bản mã của tM, được mã hoá bằng khoá phiên K. Tạm dừng:  Giả sử TBTDL_TN giải mã được tM với xác suất p < 1, theo thuật toán: Begin:   P ={S6, S7, S9, S5)}; R = {u1}; Lưu P, R vào CSDL của NCCDL; Kết thúc; End; CHƯƠNG 3: ỨNG DỤNG TRONG THỰC TẾ 3.1 TRUYỀN HÌNH INTERNET (INTERNET PROTOCOL TELEVISION - IPTV) 3.1.1 Khái niệm truyền hình Internet Truyền hình Internet (IPTV) là một hệ thống truyền hình kỹ thuật số, trong đó các dịch vụ được cung cấp cho người dùng qua giao thức IP. Truyền hình Internet cung cấp các dịch vụ: +  Dịch vụ quảng bá:  Truyền hình quảng bá (Broadcast TV); kênh âm thanh(Audio Channel); truyền hình trực tuyến (Time-Shift TV). +  Dịch vụ theo yêu cầu: Xem phim theo yêu cầu (Video on Demand - MOD);  nghe nhạc theo yêu cầu (Music on Demand - MOD); truyền hình theo yêu cầu (TV on Demand - TVOD); +  Dịch vụ tương tác: Thông tin tương tác (Interactive Infomation); truyền hình tương tác (Interactive TV); phỏng vấn trực tuyến; trò chơi trực tuyến (Game Online); duyệt Web; Email; Truyền hình thương mại (TV - Commerce). +  Truyền hình cá nhân hoá:             Người dùng chọn các nội dung theo sở thích, nhu cầu. Trong đó: +  Truyền hình quảng bá:  Các nội dung truyền hình được quảng bá theo lịch trình thời gian cố định như truyền hình truyền thống. Người dùng có thể chọn kênh truyền hình công cộng (public), kênh truyền hình trả tiền (pay TV), kênh truyền hình được ưa thích, kênh về mua sắm, kênh về thời trang… + Truyền hình theo yêu cầu: Phát nội dung chương trình truyền hình theo yêu cầu của người dùng. Nội dung là các bộ phim, đoạn phim,… được lưu trên máy chủ của NCCDL. Dịch vụ này có thể được sử dụng trong một thời gian giới hạn (ví dụ vài ngày). Các chức năng thường giống với chức năng của máy ghi hình hay đầu DVD: phát hình (play), dừng hình (pause), tua hình (fast forward), v.v… +  Quản lý chương trình: Cung cấp cho người dùng các thông tin về các chương trình IPTV đang và sắp phát, người d ùng có thể tìm kiếm thông tin từ NCCDL. +  Dịch vụ thông tin: Tin tức thời sự, tin thể thao, dự báo thời tiết, thông tin về các chuyến bay, các sự kiện trong khu vực. +  Truyền hình tương tác: Cho phép người dùng tương tác với các chương trình truyền hình, hoặc khởi tạo các ứng dụng liên kết đến các chương trình đang hoạt động. Người dùng được tham dự vào các trò chơi truyền hình, bình chọn qua truyền hình, phản hồi của người xem truyền hình… +  Ứng dụng tương tác: Sự tương tác không chỉ liên kết đến chương trình truyền hình truyền thống. Ví dụ: đấu giá, mua sắm. dịch vụ ngân hàng… +  Ứng dụng băng rộng: Các ứng dụng dùng cho người tiêu dùng và doanh nghiệp cũng có thể được thực hiên thông qua hạ tầng IPTV/VOD, như hội nghị truyền hình, đào tạo từ xa, giám sát an ninh. +  Pay-per –View (PPV): Người dùng trả tiền để xem một phần chương trình truyền hình, ví dụ: trả tiền để xem một sự kiện thể thao hay để nghe một bản nhạc. + Trò chơi theo yêu cầu: (Game on Demand): Dịch vụ này sẽ cung cấp nhiều loại trò chơi (tuỳ chọn) đến thuê bao từ một danh sách có sẵn. +  Âm nhạc theo yêu cầu (Music on Demand): Các thuê bao có thể xem những clip ca nhạc theo yêu cầu, giống như dịch vụ VOD. +  Truyền hình của hôm trước (TV of Yesterday, TVOY): Dịch vụ này cho phép thuê bao xem phim truyền hình đã được phát những ngày trước. +  Karaoke theo yêu cầu (Karaoke on Demand): Các thuê bao có thể chọn và xem các bài Karaoke qua Set-top Box (STB) trên TV. Từ danh sách các bài karaoke đã được giới thiệu, thuê bao có thể mua một hoặc nhiều bài hát cùng lúc. 3.1.2 Sơ đồ kiến trúc mạng IPTV +  TV,  máy tính:             Thiết bị hiển thị nội dung thu được từ NCCDL. +  Set-top Box (STB): Thiết bị đầu cuối phía khách hàng, cho phép thu, giải mã và hiển thị nội dung trên màn hình TV. +  Mạng truy nhập (băng rộng): Hạ tầng mạng IP băng rộng để truyền dữ liệu từ nhà cung cấp dịch vụ IPTV đến khách hàng. +  Hệ thống nguồn tín liệu: Thu, nhận và xử lý các dữ liệu chương trình từ các nguồn khác nhau như vệ tinh, truyền hình mặt đất và các nguồn khác để chuyển sang hệ thống quản lý nội dung. +  Hệ thống quản lý nội dung: Thu, điều chế và giải mã nội dung hình ảnh và âm thanh từ các nguồn khác nhau và sử dụng các thiết bị mã hoá (encoder) để chuyển đổi nội dung này thành các luồng IP (multicast) ở khuôn dạng mã hoá mong muốn. Đầu vào của hệ thống này là các chương trình truyền hình quảng bá, các kênh truyền hình mua bản quyền thu từ vệ tinh, các kênh truyền hình cáp, các phim từ các nguồn khác như tự sản xuất, từ các thiết bị VCD/DVD player, v.v... +  Hệ thống quản lý thuê bao: Cung cấp khả năng quản lý thuê bao, nội dung, báo cáo, và quản lý STB. Hệ thống này xác định định danh thuê bao. Hệ thống hiển thị danh sách các dịch vụ, mà thuê bao đó thể sử dụng và trợ giúp lựa chọn dịch vụ này sau khi đã xác thực. Hệ thống cũng lưu lại thông tin của tất cả các dịch vụ và các thông tin dịch vụ tương ứng với từng thuê bao. +  Hệ thống phân phối nội dung: Gồm cụm máy chủ VOD và hệ thống quản lý VOD tương ứng, lưu trữ các nội dung đã được mã hoá và thiết lập các lịch phân phối nội dung phù hợp với yêu cầu dịch vụ của các thuê bao. Máy chủ VOD sẽ lưu nội dung thực và cung cấp cho thuê bao khi nó nhận được sự xác thực định danh từ Middleware. Nó cho phép các thuê bao đặt và xem những bộ phim và chương trình theo yêu cầu. +  Hệ thống quản lý bản quyền số: Dùng để bảo vệ nội dung các khoá giải mã của các thuê bao, mã hoá nội dung VOD, tích hợp với tính năng bảo mật tại STB ở phía thuê bao. Nội dung trên những máy chủ nội dung sẽ được mã hoá bằng hệ thóng này. +  Hệ thống quản lý mạng và tính cước: Hệ thống này quản lý và tính cước dịch vụ truy cập của thuê bao IPTV. 3.2 TRUYỀN HÌNH DI ĐỘNG     (MOBILE TELEVISION – MOBILETV) 3.2.1 Khái niệm truyền hình di động Truyền hình di động (Mobile TV) cho phép người dùng xem truyền hình trên điện thoại di động. Truyền hình di động cung cấp các dịch vụ: +  Dịch vụ quảng bá:     Truyền hình quảng bá, âm thanh quảng bá, truyền hình trực tiếp. +  Dịch vụ theo yêu cầu: Xem phim theo yêu cầu, nghe nhạc theo yêu cầu, truyền hình theo  yêu cầu. +  Dịch vụ tương tác: Truyền hình tương tác, đấu giá, mua sắm, thanh toán hoá đơn. 3.2.2 Sơ đồ kiến trúc mạng Mobile TV +  Bộ quản lý dịch vụ (Broadcast Service Manager): Đóng gói dữ liệu, mã hoá dữ liệu, sinh danh sách dịch vụ và các hướng dẫn sử dụng các dịch vụ... +  Bộ đóng gói quảng bá (Broadcast Encapsulator): Là một cổng đóng gói và mã hoá dữ