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

1


Chương 1: CÁC KHÁI NIỆM CƠ BẢN
1.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 hoặc
đoạn thông tin được NCCDL gửi đến TBTDL qua các
kênh quảng bá.


+ 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.

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:
+ 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ủ”

j

⊆
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 ,
⊆ {1,..., w} và thoả mãn điều kiện:
{i1,i2,..., it}
P =  Si Sij ∩ Sik =Φ,∀ ij ≠ ik
1 2
Kích thước của một phủ là số lượng các tập con tạo
nên phủt đó.
Ví dụ ở đây, kích thước của phủ P là t.
t

j

j=
1


i =1

j


1.3 Giải pháp lưu vết thiết bị thu
a) Bài toán lưu vết
NCCDL truyền thông điệp M tới TBTDL (|N| = n). Mỗi
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.


1.4 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 (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.



Cha 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.
Gốc

Cha chung thấp
nhất của a và b

Nút a
Nút b
• Hình 1.4: Cha chung thấp nhất của a và b


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
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].


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à khoá hoặc 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 đó

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 PM chia Sij
j
j
thành hai tập bằng nhau, bổ sung hai tập này vào P, loại bỏ Sijkhỏ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.


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ư


Gốc

L1
v3
L3

v2
L2
v4
L4
v8
L8
u1

v6

v5
L5

L6

v9 v10

v11 v12

L9
u2

L11

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ã:
<[1, E(K, L1)], FK(tM)>
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ã:
<[2, 3, E(K, L2), E(K, L3)], FK(tM)>
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


Do a = b - 1 (0 = 1 - 1) → S2 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)