i
Số hóa bởi Trung tâm Học liệu ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
DƢƠNG THỊ LAN HƢƠNG
XÁC THỰC SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU QUAN HỆ BẰNG
KỸ THUẬT THỦY VÂN SỐ DỰA VÀO HỆ MẬT MÃ KHÓA CÔNG KHAI
Chuyên ngành: Khoa học máy tính
Mã số: 60 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS.TS BÙI THẾ HỒNG
Thái Nguyên, 2014
ii
Số hóa bởi Trung tâm Học liệu LỜI CAM ĐOAN
Tôi xin cam đoan: luận văn “Xác thực sự toàn vẹn của cơ sở dữ liệu
quan hệ bằng kỹ thuật thủy vân số dựa vào hệ mật mã khóa công khai” là
công trình nghiên cứu của cá nhân tôi, các nội dung nghiên cứu và trình bày
trong luận văn trung thực, rõ ràng.
Tác giả luận văn
Dƣơng Thị Lan Hƣơng
iii
Số hóa bởi Trung tâm Học liệu LỜI CẢM ƠN
1.1.2. Các yêu cầu cơ bản của thuỷ vân trên cơ sở dữ liệu quan hệ 9
1.1.3. Những tấn công trên hệ thuỷ vân cơ sở dữ liệu quan hệ 11
1.1.4. Các ứng dụng chủ yếu của thuỷ vân cơ sở dữ liệu quan hệ 13
1.2. Các kỹ thuật thủy vân số cho các cơ sở dữ liệu quan hệ 14
1.2.1. Kỹ thuật thủy vân số làm thay đổi dữ liệu trong CSDL quan hệ 15
1.2.2. Các kỹ thuật thủy vân số không làm thay đổi dữ liệu trong CSDL 25
1.3. Nhận xét về các lƣợc đồ thủy vân 27
1.4. Kết luận 31
CHƢƠNG II. XÁC THỰC SỰ TOÀN VẸN CỦA CƠ SỞ DỮ LIỆU
QUAN HỆ BẰNG KĨ THUẬT THỦY VÂN DỰA VÀO HỆ MẬT MÃ
KHÓA CÔNG KHAI
2.1. Giới thiệu 32
2.2. Kỹ thuật thủy vân số với cơ chế xác thực công khai 33
2.2.1. Ý tƣởng của kỹ thuật thủy vân số với cơ chế xác thực công khai 33
v
Số hóa bởi Trung tâm Học liệu 2.2.2. Tạo ra mã xác thực 36
2.2.3. Quá trình xác thực tính toàn vẹn của dữ liệu 38
2.2.4. So sánh giữa hai thủy vân 41
2.3. Kết luận 42
CHƢƠNG III. XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM
3.1. Xây dựng chƣơng trình 43
3.1.1. Bài toán thực nghiệm 43
3.1.2. Thiết kế chƣơng trình 43
3.2. Thử nghiệm chƣơng trình 51
3.3. Đánh giá kết quả thử nghiệm 52
KẾT LUẬN VÀ KIẾN NGHỊ 60
TÀI LIỆU THAM KHẢO 61
DANH MỤC CÁC BẢNG
Bảng 2.1: Giải thích các ký hiệu sử dụng trong lƣợc đồ thủy vân 33
Bảng 3.1: Thông tin kết quả học tập của sinh viên 49
Bảng 3.2: Kết quả thử nghiệm 58
viii
Số hóa bởi Trung tâm Học liệu DANH MỤC CÁC HÌNH
Hình 1.1. Sơ đồ mô tả lƣợc đồ thủy vân cơ sở dữ liệu quan hệ 6
Hình 3.1 Giao diện chính của chƣơng trình 44
Hình 3.2 Giao diện chính của chƣơng trình 45
Hình 3.3: Giao diện kết quả tạo cặp khóa 46
Hình 3.4: Giao diện minh họa các bƣớc tạo ra mã xác thực 46
Hình 3.5: Giao diện minh họa các bƣớc lấy thủy vân WM’’ 47
Hình 3.6: Giao diện thông báo kết quả kiểm tra dữ liệu 48
Hình 3.7: Giao diện kết quả kiểm tra dữ liệu 48
Hình 3.8: CSDL thử nghiệm trong SQL 2012 50
Hình 3.9: Thủy vân số gốc đƣợc dùng trong thử nghiệm 51
Hình 3.10: Giao diện kết quả sau khi chạy với mô hình thử nghiệm 1 52
Hình 3.11: a) Thủy vân gốc; b) Thủy vân thu đƣợc sau khi không thay đổi dữ
liệu theo thử nghiệm 1 53
Hình 3.12: Giao diện thông báo kết quả sau khi chạy với mô hình thử nghiệm 2
53
Hình 3.13: Giao diện kết quả sau khi chạy với mô hình thử nghiệm 2 54
Hình 3.14: a) Thủy vân gốc; b) Thủy vân thu đƣợc sau khi thay đổi dữ liệu theo
thử nghiệm 2 55
Hình 3.15: Giao diện thông báo kết quả sau khi chạy với mô hình thử nghiệm 3
Mục tiêu của đề tài là: Nghiên cứu tổng quan về thủy vân cơ sở dữ liệu
quan hệ nhƣ các khái niệm, định nghĩa cơ bản liên quan đến CSDL quan hệ,
các mô hình dữ liệu, cụ thể là mô hình thực thể kết hợp và mô hình dữ liệu
quan hệ. Nghiên cứu tổng quan về kỹ thuật thủy vân số nói chung nhƣ khái
niệm thủy vân số, quy trình thực hiện thủy vân số. Từ đó nghiên cứu chi tiết
một kỹ thuật thủy vân số cho cơ sở dữ liệu quan hệ để xác thực tính toàn vẹn
của cơ sở dữ liệu. Cuối cùng là viết chƣơng trình demo để thử nghiệm kỹ
thuật đã nghiên cứu và đánh giá.
2
Số hóa bởi Trung tâm Học liệu Ngoài phần mở đầu và phần kết luận, luận văn bao gồm ba chƣơng nhƣ
sau:
Chƣơng I. Tổng quan thủy vân số
Trình bày những kiến thức cơ bản liên quan đến thủy vân số nhƣ: Khái
niệm thủy vân số, khái niệm thủy vân cơ sở dữ liệu quan hệ, khóa thủy vân,
lƣợc đồ thủy vân, các ứng dụng của thủy vân số, Đồng thời cũng trình bày
các kỹ thuật thủy vân số cho các cơ sở dữ liệu, đƣợc chia ra làm hai nhóm kỹ
thuật, đó là: Các kỹ thuật thủy vân số làm thay đổi dữ liệu và các kỹ thuật
thủy vân số không làm thay đổi dữ liệu trong CSDL quan hệ. Đồng thời cũng
đƣa ra một số nhận xét về các lƣợc đồ thủy vân.
Chƣơng II. Xác thực sự toàn vẹn của cơ sở dữ liệu quan hệ bằng kỹ thuật
thủy vân dựa vào hệ mật mã khóa công khai
Trình bày chi tiết một kỹ thuật thủy vân số. Đó là kỹ thuật thủy vân số
với cơ chế xác thực công khai. Kỹ thuật này bao gồm hai giai đoạn: giai đoạn
tạo mã xác thực (dành cho chủ sở hữu CSDL) và giai đoạn xác thực tính toàn
vẹn của dữ liệu (dành cho ngƣời sử dụng CSDL).
Chƣơng III. Xây dựng chƣơng trình thử nghiệm
Trình bày bài toán, dữ liệu thử nghiệm và các mô hình thử nghiệm.
Số hóa bởi Trung tâm Học liệu hoặc các tiện ích điện tử) cho phép ngƣời sử dụng tìm kiếm và truy cập cơ sở
dữ liệu từ xa. Mặc dù xu hƣớng này là hữu ích cho ngƣời dùng cuối nhƣng nó
cũng bộc lộ một mối nguy hiểm cho những nhà cung cấp dữ liệu trƣớc những
kẻ trộm cắp dữ liệu. Do đó, những ngƣời cung cấp dữ liệu đòi hỏi phải có
công nghệ nhận dạng đƣợc những bản sao các cơ sở dữ liệu của họ bị đánh
cắp.
Thủy vân cơ sở dữ liệu quan hệ là một kỹ thuật nhúng một số thông tin
nào đó (đƣợc gọi là thông tin thủy vân W) vào cơ sở dữ liệu quan hệ nhằm
mục đích bảo vệ bản quyền hoặc đảm bảo sự toàn vẹn cho cơ sở dữ liệu này.
Thủy vân có thể ở dạng ẩn hoặc hiện và có thể là bền vững hoặc dễ vỡ.
Khóa thủy vân
Để chủ sở hữu cơ sở dữ liệu có thể giữ bí mật cho thông tin thủy vân W
và là ngƣời duy nhất có thể tìm lại đƣợc thông tin này thì cần phải trộn W với
một dữ liệu đƣợc gọi là khóa do chính chủ cơ sở dữ liệu lựa chọn. Thông tin
thứ hai này đƣợc gọi là khóa thủy vân.
Khóa thủy vân là một lƣợng dữ liệu do chủ sở hữu cơ sở dữ liệu lựa chọn
và nhằm mục đích xác định thủy vân trong lƣợc đồ thủy vân. Ký hiệu là K.
Khóa K sẽ đƣợc kết hợp với thủy vân W để nhúng vào cơ sở dữ liệu.
Khóa thủy vân chính là mấu chốt của lƣợc đồ thủy vân cơ sở dữ liệu có sử
dụng khóa thủy vân.
Khóa thủy vân sẽ đƣợc nhúng vào trong cơ sở dữ liệu quan hệ
bằng nhiều cách. Thông thƣờng khóa thủy vân sẽ đƣợc nhúng với dữ liệu
trong cơ sở dữ liệu quan hệ rồi đƣa vào trong thuật toán sử dụng. Điều quan
trọng ở đây chính là việc giấu khóa thủy vân vào trong thuật toán nhƣ thế nào
để không bị phát hiện đồng thời có thể chứng minh đƣợc đây chính là cơ sở
5
Số hóa bởi Trung tâm Học liệu
.A
y
) băm khóa K cùng với các giá trị thuộc tính của bộ r
i
của cơ sở dữ liệu,
trong đó || là phép ghép nối. Trong thực tế, hai hàm băm thông dụng nhất là
MD5 và SHA [4]. Trong phần thử nghiệm, luận văn dùng hàm băm MD5.
Lƣợc đồ thủy vân
Lƣợc đồ thủy vân cơ sở dữ liệu quan hệ bao gồm 2 phần: nhúng thủy
vân và phát hiện thủy vân [2]. Khi nhúng thủy vân, một khóa thủy vân K do
6
Số hóa bởi Trung tâm Học liệu chủ sở hữu cơ sở dữ liệu tự chọn sẽ đƣợc sử dụng để nhúng thủy vân W vào
cơ sở dữ liệu gốc. Sau khi nhúng thủy vân, các cơ sở dữ liệu sẽ đƣợc đƣa vào
môi trƣờng Internet. Để xác minh quyền sở hữu của một cơ sở dữ liệu đáng
ngờ, cần phải lấy đƣợc thủy vân đã nhúng trong CSDL này. Nếu thủy vân lấy
ra trùng với thủy vân đã nhúng, điều này chứng tỏ đây là CSDL của chủ sở
hữu. Tuy nhiên, nếu thủy vân lấy ra khác với thủy vân đã nhúng thì CSDL
của chủ sở hữu đã bị thay đổi. Hình 1.1 là sơ đồ mô tả lƣợc đồ thủy vân cơ sở
dữ liệu quan hệ [2]. Hình 1.1. Sơ đồ mô tả lƣợc đồ thủy vân cơ sở dữ liệu quan hệ
Phát hiện
thủy vân
Cơ sở dữ
liệu nghi ngờ
Thông tin thủy vân (W)
một đối tƣợng đa phƣơng tiện có đặc thù là không thay đổi. Nhƣng các
bộ của một quan hệ lại cấu thành một tập hợp, do vậy không cần phải
áp đặt một thứ tự nào giữa các đối tƣợng này.
Các phần khác nhau của một đối tƣợng đa phƣơng tiện không thể bị cắt
bỏ hoặc thay thế một cách tuỳ ý mà không gây ra những thay đổi về
cảm quan trong đối tƣợng. Ngƣợc lại, việc thêm, bớt, và cập nhật các
bộ của một bảng quan hệ lại là những phép toán chuẩn trong cơ sở dữ
liệu. Do đó, sẽ rất khó để phát hiện những xâm hại đơn giản nhƣ xóa bỏ
một số bộ hoặc thay thế chúng bằng các bộ của các quan hệ khác.
8
Số hóa bởi Trung tâm Học liệu Do có những khác nhau nhƣ đã nêu trên đây mà các kỹ thuật đƣợc phát
triển cho các dữ liệu đa phƣơng tiện không thể đƣợc sử dụng trực tiếp để thuỷ
vân các dữ liệu quan hệ.
Thật vậy, giả sử ánh xạ một quan hệ thành một bức ảnh bằng cách xem
mỗi giá trị thuộc tính nhƣ một điểm ảnh. Nhƣng không may là “bức ảnh”
đƣợc định nghĩa nhƣ vậy sẽ thiếu rất nhiều tính chất của một bức ảnh thật. Ví
dụ, các điểm ảnh nằm cạnh nhau trong một bức ảnh thật thƣờng có quan hệ
mật thiết với nhau và quan hệ này là cơ sở cho nhiều kỹ thuật thuỷ vân ảnh
tĩnh. Các kỹ thuật thuỷ vân trên miền biến đổi của ảnh thƣờng thực hiện theo
quy trình: trƣớc hết áp dụng một phép biến đổi (cosine rời rạc - DCT, sóng
nhỏ - DWT, . . .) miền giá trị của bức ảnh, sau đó nhúng thuỷ vân vào miền đã
biến đổi rồi biến đổi ngƣợc trở lại. Cách làm này trải các tín hiệu thuỷ vân
nhƣ phủ một màn nhiễu trên toàn bộ bức ảnh. Áp dụng trực tiếp các kỹ thuật
này cho một quan hệ sẽ làm sai lệch giá trị của tất cả các thuộc tính. Điều đó
có thể sẽ không đƣợc chấp nhận. Hơn nữa, một thuỷ vân nhƣ vậy có thể
không tồn tại đƣợc ngay cả trƣớc những cập nhật nhỏ đối với quan hệ.
Các kỹ thuật thủy vân văn bản thƣờng lợi dụng các tính chất đặc biệt của
Để đơn giản trong khi biện luận, phần này sử dụng ba nhân vật điển
hình vẫn thƣờng đƣợc dùng trong các ví dụ về mật mã, giấu tin và thủy vân.
Đó là một cô gái tên là Alice và bạn trai của cô tên là Bob. Hai ngƣời này
thƣờng hay gửi thƣ cho nhau và ở giữa là một anh chàng tên là Mallory
thƣờng xuyên làm phiền họ.
10
Số hóa bởi Trung tâm Học liệu Giả dụ, Alice là chủ nhân của quan hệ R chứa bộ, trong đó cô đã
đánh dấu bộ. Hệ thống thủy vân cần phải thỏa mãn những tính chất sau
đây:
Khả năng có thể phát hiện (Detectability)
Alice cần phải có khả năng phát hiện thủy vân của cô bằng cách xem
xét bộ từ cơ sở dữ liệu nghi ngờ. Rõ ràng là nếu mẫu bít của cô (thủy vân)
có mặt ở tất cả bộ thì cô có lý do xác đáng để nghi ngờ có sự sao chép trái
phép. Tuy nhiên, Alice cũng có thể ngờ vực ngay cả khi mẫu của cô chỉ có
mặt ở ít nhất là bộ ( ), trong đó phụ thuộc vào và một giá trị cho
trƣớc, đƣợc gọi là mức ý nghĩa của phép thử. Giá trị của đƣợc xác định sao
cho xác suất để Alice sẽ tìm thấy mẫu bit của cô trong ít nhất bộ từ bộ là
nhỏ hơn .
Tính bền vững (Robustness)
Các thủy vân cần phải bền vững trƣớc những tấn công nhằm xóa bỏ
chúng. Ví thể với tƣ cách là kẻ tấn công, Mallory thay đổi bộ trong quan hệ
R của Alice. Chúng ta nói rằng thủy vân là an toàn đối với tấn công này nếu
kẻ tấn công không thể phá hủy các dấu hiệu thủy vân ở ít nhất bộ, trong đó
phụ thuộc vào và nhƣ đã nói ở trên.
Cập nhật phần tăng thêm (Incremental Updatability)
Sau khi có quan hệ R đã thủy vân, Alice có thể cập nhật R khi cần thiết
mà không làm hỏng thủy vân. Khi Alice thêm/ bớt các bộ hoặc sửa đổi các giá
Số hóa bởi Trung tâm Học liệu Tức là các phép toán cập nhật thông thƣờng nhƣ xóa, sửa, bổ sung các
bộ trong cơ sở dữ liệu quan hệ.
Các kỹ thuật thuỷ vân cần đảm bảo rằng ngƣời chủ cơ sở dữ liệu không
bị mất thuỷ vân ngay trong dữ liệu bị kẻ khác ăn trộm, thậm chí đối với những
cập nhật của tên trộm đó.
Tấn công có chủ đích
Mallory có thể biết dữ liệu anh ta ăn trộm có chứa thủy vân, nhƣng anh
ta có thể cố xóa thủy vân này hoặc thử dùng các phƣơng tiện khác để đòi
quyền sở hữu trái phép.
Hệ thống đánh dấu cần phải bảo vệ Alice trƣớc những tấn công gây hại
của Mallory.
Nghĩa là các cơ sở dữ liệu có thể bị những kẻ xấu ăn trộm, tấn công
nhằm mục đích đòi quyền sở hữu trái phép hay phá huỷ dữ liệu, phá huỷ thuỷ
vân, Do đó, hệ thống thuỷ vân cần phải bảo vệ ngƣời chủ cơ sở dữ liệu
trƣớc những tấn công gây hại của kẻ trộm.
Một số tấn công gây hại nhƣ :
Tấn công vào các bít: Cách tấn công gây hại đơn giản nhất là cố gắng phá
huỷ thuỷ vân bằng cách cập nhật một số bít. Nếu tên trộm Mallory có thể
thay đổi tất cả các bít, thì anh ta có thể dễ dàng phá huỷ thuỷ vân. Tuy
nhiên, việc này cũng làm cho dữ liệu của anh ta không còn sử dụng đƣợc
nữa. Do đó, tác hại của một tấn công cần phải đƣợc xem xét trên cơ sở mối
quan hệ giữa số bít mà Mallory và Alice thay đổi, vì mỗi thay đổi có thể
đƣợc coi nhƣ một sai sót. Càng có nhiều sai sót càng làm cho dữ liệu kém
hữu dụng.
13
Số hóa bởi Trung tâm Học liệu
dụng bất hợp pháp thì ta có thể dùng bộ dò thủy vân số để phát hiện.
o Chống sao chép bất hợp pháp: Các sản phẩm có chứa thủy vân số biểu
hiện cho việc sản phẩm này không đƣợc sao chép, vì nếu sao chép sẽ
phạm luật. Nhà sản xuất trang bị các phƣơng tiện dùng để sao chép (nhƣ
CD writer…) đều có khả năng phát hiện xem thủy vân số có chứa trong
sản phẩm số hay không, nếu có thì sẽ từ chối không sao chép. Một số
phần mềm cũng có chức năng này, ví dụ nhƣ phần mềm xem phim của
hãng DivX sẽ từ chối chiếu các bộ phim chứa thủy vân số.
o Theo dõi quá trình sử dụng: Thủy vân số có thể đƣợc dùng để theo dõi
quá trình sử dụng của các sản phẩm số. Mỗi bản sao của sản phẩm số
đƣợc chứa bằng một thủy vân số duy nhất dùng để xác định ngƣời sử
dụng là ai. Nếu có sự sao chép bất hợp pháp, ta có thể truy ra ngƣời vi
phạm nhờ vào thủy vân số đƣợc chứa bên trong sản phẩm số đó.
o Chống giả mạo: Thủy vân số có thể đƣợc dùng để chống sự giả mạo. Nếu
có bất cứ sự thay đổi nào về nội dung của các sản phẩm số thì thủy vân số
này sẽ bị hủy đi. Do đó rất khó làm giả sản phẩm số có chứa thủy vân số.
o Theo dõi truyền thông: Các công ty truyền thông và quảng cáo có thể
dùng kỹ thuật thủy vân số để quản lý xem có bao nhiêu khách hàng đã
dùng dịch vụ cung cấp.
o Truyền tin bí mật: Bởi vì thủy vân số là một dạng đặc biệt của việc che
dấu dữ liệu nên ngƣời ta có thể dùng để truyền các thông tin bí mật.
1.2. Các kỹ thuật thủy vân số cho các cơ sở dữ liệu quan hệ
Trong phần trên, luận văn đã trình bày một cách tổng quan về thủy vân số
nói chung. Phần này, luận văn sẽ tập trung trình chi tiết các kỹ thuật thủy vân
15
Số hóa bởi Trung tâm Học liệu số cho các cơ sở dữ liệu quan hệ đã đƣợc đề xuất từ trƣớc tới nay. Các kỹ
thuật đƣợc trình bày ở đây sẽ đƣợc phân loại dựa trên các yếu tố sau: (i) Các
diễn số lƣợng các bản ghi đƣợc đánh dấu (đƣợc nhúng thủy vân số), số lƣợng
các thuộc tính đƣợc đánh dấu, số lƣợng các bít ít ý nghĩa đƣợc đánh dấu trong
thuộc tính, và cuối cùng là khóa bí mật. Trong [6], hàm mã hóa MAC
PrKHKH .
, r.P là khóa chính của bản ghi r và || mô tả toán tử ghép,
đƣợc dùng để xác định các vị trí bít trong thuộc tính đƣợc chọn. Hàm HASH
PrKH .
đƣợc dùng để xác định các giá trị bít đƣợc nhúng tại các vị trí đó.
Vì các hàm MAC và HASH là hàm một chiều nên việc lựa chọn của chúng sẽ
có xung đột thấp. Trong [3], [4], các tác giả dùng bộ sinh dãy ngẫu nhiên (nhƣ
bộ ghi dịch chuyển hồi tiếp tuyến tính) thay thế cho HASH và MAC để xác
định các giá trị bít và các vị trí của các bít đƣợc đánh dấu. Tính bảo mật và
tính bền vững của lƣợc đồ này phụ thuộc vào các tham số ở trên do ngƣời sở
hữu cơ sở dữ liệu cung cấp. Trong thực thế, thuật toán dò thủy vân số của
lƣợc đồ này là không chắc chắn (chƣa chắc đã dò đƣợc thủy vân số đƣợc
nhúng) theo xác suất. Bảng dữ liệu đƣợc cho là vi phạm bản quyền nếu mẫu
đối sánh xuất hiện ít nhất bản ghi, ở đây phụ thuộc vào số lƣợng các bản
ghi đƣợc dùng để đánh dấu và giá trị đƣợc chọn trƣớc, đƣợc gọi là mức độ
ý nghĩa của kiểm tra. Qua thực thế thấy rằng thành công của giai đoạn dò thủy
vân số trong lƣợc đồ này phụ thuộc vào thứ tự của các thuộc tính. Nếu thứ tự
của các thuộc tính đƣợc thay đổi, hầu nhƣ không thể dò đƣợc thủy vân số
đƣợc nhúng trong cơ sở dữ liệu. Mặc dù cái chính trong lƣợc đồ này đó là các
bảng dữ liệu phải có khóa chính, giá trị của khóa không đƣợc thay đổi, nhƣng
họ cũng đề nghị một thay đổi không sử dụng khóa chính. Li et al. [Li et al.,
2003] đƣa 3 lƣợc đồ khác nhau để tạo ra khóa chính ảo cho một bảng dữ liệu
không dùng khóa chính.
Trong [7], Lafaye đã phân tích bảo mật cho thuật toán AHK. Tác giả đã
phân tích tính bảo mật và tính bền vững trong hai tính huống: (i) Đa khóa
17
rút từ phần phân số.
Copyright: Tài liệu đại học ©