Luận văn Thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hoá áp dụng thuật toán tìm kiếm theo mẫu

Tài liệu Luận văn Thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hoá áp dụng thuật toán tìm kiếm theo mẫu: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên – 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU Chuyên ngành: Khoa học máy tính Mã số: 604801 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS BÙI THẾ HỒNG Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU Chuyên ngành: Khoa học máy tính Mã số: 604801 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN...

pdf69 trang | Chia sẻ: hunglv | Lượt xem: 1233 | Lượt tải: 0download
Bạn đang xem trước 20 trang mẫu tài liệu Luận văn Thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hoá áp dụng thuật toán tìm kiếm theo mẫu, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên – 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU Chuyên ngành: Khoa học máy tính Mã số: 604801 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS BÙI THẾ HỒNG Thái Nguyên - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ĐẠI HỌC THÁI NGUYÊN KHOA CÔNG NGHỆ THÔNG TIN NGUYỄN THỊ HẠNH THỦY VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU Chuyên ngành: Khoa học máy tính Mã số: 604801 TÓM TẮT LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC TS BÙI THẾ HỒNG Thái Nguyên – 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Công trình được hoàn thành tại: ....................................................................... ................................................................................................... ....................... Người hướng dẫn khoa học: .................................................................................... (Ghi rõ họ tên, chức danh khoa học, học vị) Phản biện 1:........................................................................................ Phản biện 2:......................................................................................... Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn họp tại: Vào hồi...... giờ...... ngày....... tháng........ năm 20... Có thể tìm hiểu luận văn tại trung tâm học liệu Đại học Thái Nguyên Và thư viện Trường/Khoa:……………………………. (Ghi tên thư viện đơn vị) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO [1]. “Nghiên cứu và Phát triển Kỹ thuật Thuỷ vân Cơ sở Dữ liệu Quan hệ”, Báo cáo kết quả nghiên cứu của đề tài cơ sở 2008, 12/2008, Phòng CSDL & LT. [2]. Bùi Thế Hồng, Nguyễn Thị Thu Hằng, Lƣu Thị Bích Hƣơng, “Thủy vân cơ sở dữ liệu quan hệ”, Tạp chí Khoa học & Công nghệ, ĐH Thái Nguyên, 2009. [3]. Vũ Ba Đình, “Giấu thông tin trong cơ sở dữ liệu không gian”, Tạp chí nghiên cứu khoa học kỹ thuật và công nghệ Quân sự, số 4, 30-37 [4]. R. Agrawal, J. Kiernan, “Watermarking Relational Databases” in Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002. [5]. R. Agrawal, P. J. Haas, and J. Kiernan. “Watermarking relational data: framework, algorithms and analysis*”. The VLDB Journal (2003). [6]. R. Sion, M. Atallah, S. Prabhakar.“Watermarking Relational Databases” CERIAS TR 2002-28*. Center for Education and Research in Information Assurance, Computer Sciences, Purdue University, 2002. [7]. R. Sion, M. Atallah, and S. Prabhakar. “Rights Protection for Relational Data”. IEEE Transactions on Knowledge and Data Engineering, 16(6), June 2004. [8]. R. Sion, “Proving ownership over categorical data”. ICDE 2004. [9]. M. Shehab, E. Bertino, A. Ghafoor. “Watermarking Relational Databases using Optimization Based Techniques”. CERIAS Tech Report 2006-41. [10]. www.watermarkingworld.org. [11]. W. Bender, D. Gruhl, N. Morimoto, A. Lu, “Techniques for data Hiding” IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996. [12]. Stefan Katzenbeisser and Fabien A.P.Petitcolas, “Information Hiding Techniques for Steganography and Digital Watermarking”.Artech House Boston London. [13]. Michael Arnold, Martin Schmucker and Stephen D. Wolthusen, “Techniques and Applications of Digital Watermarking and Content Protection”. Artech House Boston London.  1  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI CAM ĐOAN Tôi xin cam đoan : Luận văn “Nghiên cứu và phát triển kỹ thuật thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hóa áp dụng thuật toán tìm kiếm theo mẫu” là công trình nghiên cứu riêng của tôi. Các số liệu trong luận văn được sử dụng trung thực. Kết quả nghiên cứu được trình bày trong luận văn này chưa từng được công bố tại bất kỳ công trình nào khác. Tôi xin chân thành cám ơn các Thầy trong Viện Công nghệ thông tin Việt Nam đã truyền đạt cho tôi kiến thức trong suốt những năm học ở trường. Tôi xin chân thành cảm ơn TS. Bùi Thế Hồng đã tận tình hướng dẫn tôi hoàn thành tốt luận văn này. Thái Nguyên, ngày 10 tháng 11 năm 2009 Tác giả luận văn Nguyễn Thị Hạnh  2  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên MỤC LỤC BẢNG CÁC TỪ VIẾT TẮT ........................................................................ 4 DANH MỤC CÁC HÌNH VẼ ...................................................................... 5 LỜI MỞ ĐẦU Chƣơng 1-TỔNG QUAN VỀ KỸ THUẬT GIẤU TIN VÀ THUỶ VÂN 11 1.1. Kỹ thuật giấu tin và những vấn đề cơ bản về kỹ thuật giấu tin ........ 12 1.1.1. Khái niệm giấu tin .......................................................................... 12 1.1.2. Phân loại các kỹ thuật giấu tin ........................................................ 14 1.1.3. Mục đích của giấu tin ..................................................................... 15 1.1.4. Môi trường giấu tin ......................................................................... 17 1.2. Cơ sở lý thuyết về thuỷ vân ................................................................. 21 1.2.1. Khái niệm thuỷ vân và nhúng thuỷ vân ........................................... 21 1.2.2. Lịch sử phát triển của thuỷ vân ....................................................... 21 1.2.3. Mô hình hệ thống tổng quát quá trình nhúng và thuỷ vân ............... 22 1.2.4. Một số ứng dụng của thuỷ vân ........................................................ 24 Chƣơng 2-THUỶ VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU 25 2.1. Giới thiệu về thuỷ vân cơ sở dữ liệu .................................................. 25 2.2. Mô hình chi tiết hệ thống thuỷ vân cơ sở dữ liệu ............................... 27 2.3. Phân hoạch dữ liệu .............................................................................. 29 2.4. Nhúng thuỷ vân ................................................................................... 32 2.4.1 Mã hoá bít đơn .............................................................................. 32 2.4.2. Thuật toán tìm kiếm theo mẫu ....................................................... 37 2.4.3. Thuật toán nhúng thuỷ vân ........................................................... 39  3  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.5. Đánh giá ngƣỡng giải mã .................................................................... 40 2.6. Phát hiện thuỷ vân ............................................................................... 43 2.7. Kiểu tấn công ....................................................................................... 45 Chƣơng 3 – CÀI ĐẶT LƢỢC ĐỒ THUỶ VÂN CƠ SỞ DỮ LIỆU QUAN HỆ BẰNG KỸ THUẬT TỐI ƢU THUẬT TOÁN TÌM KIẾM THEO MẪU ............................................................................................... 47 3.1. Giới thiệu về kỹ thuật tìm kiếm theo mẫu .......................................... 47 3.2. Mô tả ứng dụng ................................................................................... 48 3.2.1. Cơ sở của ứng dụng ........................................................................ 48 3.2.2. Giả thiết .......................................................................................... 48 3.2.3. Một số kết quả thực nghiệm đạt được ............................................. 49 PHỤ LỤC.............................................................................................. …..58 KẾT LUẬN ............................................................................................... ..59 TÀI LIỆU THAM KHẢO ………………………………………………...60  4  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên BẢNG CÁC TỪ VIẾT TẮT Kí hiệu Từ Tiếng Anh Giải thích HVS Human Vision System Hệ thống thị giác của con người HAS Human Auditory System Hệ thống thính giác của con người PS Pattern Search Tìm kiếm theo mẫu GA Genetic Algorithm Thuật toán di truyền MAC Message Authetication Code Mã xác thực thông tin MD5 Message Digest algorithm 5 Hàm băm  5  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên DANH MỤC CÁC HÌNH VẼ Trang Hình 1.1. Sơ đồ biểu diễn quá trình giấu tin ....................................... ……21 Hình 1.2. Sơ đồ biểu diễn quá trình giải mã tin .................................. ……21 Hình 1.3. Sơ đồ phân loại kỹ thuật giấu tin ......................................... ……21 Hình 1.4. Sơ đồ nhúng thuỷ vân ......................................................... ……21 Hình 1.5. Sơ đồ khôi phục thuỷ vân ........................................................... 21 Hình 2.1. Các thời kỳ mã hoá và giải mã thuỷ vân ..................................... 26 Hình 2.2. Bảng biểu diễn các ký hiệu sử dụng trong thuật toán …………31 Hình 2.3: Phân phối của tập iiS  trên trục số………………………….36 Hình 2.4. Biểu diễn Sigmoid(α,τ ) tại τ = 0 và α = {1, 2, 8}……………..39 Hình 2.5. Lược đồ ngưỡng giải mã………………………………………..42 Hình 3.1. Bảng thống kê kết quả thực nghiệm ……………………………  6  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên LỜI MỞ ĐẦU Trong thực tế việc chứng minh quyền sở hữu đối với các cơ sở dữ liệu quan hệ sau khi đã phân phối hoặc chuyển giao đang là một vấn đề quan trọng trong các môi trường ứng dụng dựa trên Internet và trong nhiều ứng dụng phân phối sản phẩm. Trong những năm gần đây, công nghệ thông tin phát triển với tốc độ chóng mặt về cả phần cứng và phần mềm, đặc biệt là tốc độ phát triển của Internet và các công nghệ có liên quan đã đưa đến một tiểm năng chưa từng có đối với việc truy nhập và phân phối lại các sản phẩm kỹ thuật số. Sự phát triển của công nghệ đa phương tiện với khả năng sao chép mô phỏng đã mở ra nhiều hướng mới cho sự phát triển kỹ thuật thuỷ vân, đặt biệt là lĩnh vực bảo mật cơ sở dữ liệu. Thuỷ vân cơ sở dữ liệu cũng không nằm ngoài quy luật phát triển đó. Ban đầu, thuỷ vân được sử dụng để nhúng vào các sản phẩm đa phương tiện như âm thanh, hình ảnh …Nhưng hiện nay, thuỷ vân đã được ứng dụng vào một lĩnh vực hết sức mới mẻ có liên quan đến quyền sở hữu trí tuệ. Đó là lĩnh vực thuỷ vân cơ sở dữ liệu quan hệ, đây là một trong những lĩnh vực quan trọng và có ứng dụng nhiều trong cuộc sống. Thuỷ vân đã được sử dụng với mong muốn có thể cho phép chứng minh được tác giả và nguồn gốc của cơ sở dữ liệu để từ đó chứng minh dữ liệu là chuẩn xác. Xuất phát từ thực tế đó, luận văn lựa chọn đề tài: “Nghiên cứu và phát triển kỹ thuật thủy vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu hóa áp dụng thuật toán tìm kiếm theo mẫu”.  7  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Tính cấp thiết của đề tài - Ngày nay, Internet đã và đang phát triển với tốc độ nhanh, cùng với sự phát triển đó thì các công nghệ và các ứng dụng được phân tán trên Internet rất nhiều. Chính vì vậy, việc chứng minh quyền sở hữu đối với các cơ sở dữ liệu quan hệ sau khi đã phân phối hoặc chuyển giao đang là một vấn đề rất quan trọng trong các môi trường ứng dụng dựa trên internet và trong nhiều ứng dụng phân phối sản phẩm. - Trong một bối cảnh như vậy, việc thực thi quyền sở hữu dữ liệu là một yêu cầu quan trọng đòi hỏi các giải pháp đồng bộ, bao gồm các khía cạnh về kỹ thuật, về tổ chức, và cả luật pháp. Mặc dù chúng ta vẫn chưa có được những giải pháp toàn diện như vậy nhưng trong các năm gần đây, các kỹ thuật thuỷ vân đã đóng một vai trò quyết định nhằm giải quyết vấn đề về quyền sở hữu này. - Cho đến nay, mới chỉ có một vài cách tiếp cận đối với bài toán thuỷ vân dữ liệu quan hệ. Tuy nhiên, những kỹ thuật này không bền vững đối với các tấn công thuỷ vân.  8  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Mục tiêu nghiên cứu Mục tiêu chung Nghiên cứu kỹ thuật thuỷ vân cơ sở dữ liệu dựa trên kỹ thuật tối ưu hóa để mã hoá và giải mã thuỷ vân. Trong đó tập trung nghiên cứu kỹ thuật phân hoạch dữ liệu không phụ thuộc vào các bộ được đánh dấu để định vị các phân hoạch, và nghiên cứu kỹ thuật phát hiện thủy vân dựa vào một ngưỡng tối ưu. Mục tiêu cụ thể Nghiên cứu kỹ thuật thuỷ vân cơ sở dữ liệu quan hệ có áp dụng kỹ thuật tối ưu hoá như một bài toán tối ưu hoá có ràng buộc. Đồng thời trình bày kỹ thuật hữu hiệu để giải bài toán tối ưu này bằng thuật toán tìm kiếm theo mẫu và xử lý các ràng buộc của chúng. Ý nghĩa khoa học và ý nghĩa thực tiễn của đề tài Ý nghĩa khoa học của đề tài - Đưa ra cơ sở khoa học của việc lựa chọn kỹ thuật tối ưu để mã hoá và giải mã thuỷ vân trong đó sử dụng kỹ thuật tìm kiếm theo mẫu để giải quyết bài toán. Ý nghĩa thực tiễn - Kết quả của đề tài có ý nghĩa rất lớn đối với Ngành công nghệ thông tin trong việc chứng minh quyền sở hữu đối với các cơ sở dữ liệu quan hệ sau khi đã phân phối hoặc chuyển giao đang là một vấn đề rất quan trọng trong các môi trường ứng dụng dựa trên internet và trong nhiều ứng dụng phân phối sản phẩm.  9  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nhiệm vụ nghiên cứu - Nghiên cứu, hiểu rõ và trình bày về kỹ thuật tối ưu để mã hoá và giải mã thuỷ vân. - Nghiên cứu và sử dụng công cụ để mô tả kỹ thuật tìm kiếm theo mẫu Phƣơng pháp nghiên cứu - Nghiên cứu lý thuyết cơ sở về thuỷ vân cơ sở dữ liệu - Nghiên cứu ứng dụng và mô tả chi tiết về kỹ thuật tìm kiếm theo mẫu. Phạm vi nghiên cứu - Phạm vi nghiên cứu kỹ thuật thuỷ vân cơ sở dữ liệu quan hệ và mô tả kỹ thuật tối ưu trong đó áp dụng kỹ thuật tìm kiếm theo mẫu Các kết quả nghiên cứu dự kiến cần đạt đƣợc  Kết quả về học thuật: Nghiên cứu kỹ thuật thuỷ vân cơ sở dữ liệu  Kết quả về phát triển ứng dụng: Áp dụng kỹ thuật tìm kiếm theo mẫu để mô tả và phát triển ứng dụng trong thực tế Kết cấu của luận văn Bố cục của luận văn bao gồm phần mở đầu, phần kết luận và ba chương. Nội dung các chương được tổ chức như sau: Chương 1: Tổng quan về kỹ thuật giấu tin và thuỷ vân Chương này trình bày một số khái niệm về kỹ thuật giấu tin, các vấn đề cơ bản của kỹ thuật giấu tin. Đồng thời cũng trình bày khái niệm cơ bản về thuỷ vân, và đặc biệt đưa ra sơ đồ chi tiết về thuỷ vân.  10  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chương 2: Thuỷ vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu áp dụng thuật toán tìm kiếm theo mẫu Chương này trình bày quá trình mã hoá, giải mã thuỷ vân cơ sở dữ liệu quan hệ bằng kỹ thuật tối ưu áp dụng thuật toán tìm kiếm theo mẫu. Chương 3: Phát triển ứng dụng thuỷ vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu áp dụng thuật toán tìm kiếm theo mẫu Chương này trình bày ứng dụng của kỹ thuật tối ưu, kỹ thuật tìm kiếm theo mẫu trong quá trình nhúng thuỷ vân. Cùng với một số kết quả cài đặt của ứng dụng.  11  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chƣơng 1- TỔNG QUAN VỀ KỸ THUẬT GIẤU TIN VÀ THUỶ VÂN Cuộc cách mạng thông tin kỹ thuật số đã đem lại những thay đổi sâu sắc trong xã hội và trong cuộc sống. Những thuận lợi thông tin kỹ thuật số mang lại cũng đề ra những thách thức và cơ hội mới cho quá trình đổi mới. Sự ra đời những phần mềm có tính năng mạnh, các thiết bị mới như máy ảnh kỹ thuật số, máy quét chất lượng cao, máy in, máy ghi âm kỹ thuật số, v.v…, đã với tới thế giới tiêu dùng rộng lớn để sáng tạo, xử lý và thưởng thức các dữ liệu đa phương tiện. Mạng Internet toàn cầu đã biến thành một xã hội ảo nơi diễn ra quá trình trao đổi thông tin trong mọi lĩnh vực chính trị, quân sự, quốc phòng, kinh tế, thương mại… Và chính trong môi trường mở và tiện nghi như thế xuất hiện những vấn nạn, tiêu cực đang rất cần đến các giải pháp hữu hiệu cho vấn đề an toàn thông tin như nạn ăn cắp bản quyền, nạn xuyên tạc thông tin, truy nhập thông tin trái phép v.v.. Đi tìm giải pháp cho những vấn đề này không chỉ giúp ta hiểu thêm về công nghệ phức tạp đang phát triển rất nhanh này mà còn đưa ra những cơ hội kinh tế mới cần khám phá. Một trong các giải pháp nhiều triển vọng là giấu tin, được nghiên cứu phát triển trong khoảng 10 năm gần đây. Để hiểu rõ về nguồn gốc của thuỷ vân, trước tiên chúng ta tìm hiểu phương pháp giấu thông tin, thuỷ vân là một thành phần của phương pháp giấu tin.  12  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.1. Kỹ thuật giấu tin và những vấn đề cơ bản về kỹ thuật giấu tin 1.1.1. Khái niệm về giấu tin Từ trước đến nay, nhiều phương pháp bảo vệ thông tin đã được đưa ra, trong đó giải pháp dùng mật mã được ứng dụng rộng rãi nhất. Thông tin ban đầu được mã hoá, sau đó sẽ được giải mã nhờ khoá của hệ mã. Đã có nhiều hệ mã phức tạp được sử dụng như DES, RSA, NAPSACK..., rất hiệu quả và phổ biến. Một phương pháp mới khác đã và đang được nghiên cứu và ứng dụng mạnh mẽ ở nhiều nước trên thế giới, đó là phương pháp giấu tin. Giấu thông tin là kỹ thuật nhúng một lượng thông tin số nào đó vào trong một đối tượng dữ liệu số khác. Một trong những yêu cầu cơ bản của giấu tin là đảm bảo tính chất ẩn của thông tin được giấu đồng thời không làm ảnh hưởng đến chất lượng của dữ liệu gốc. Sự khác biệt chủ yếu giữa mã hoá thông tin và giấu thông tin là mã hoá làm cho các thông tin thể hiện là có được mã hoá hay không, còn với giấu thông tin thì người ta sẽ khó biết được là có thông tin giấu bên trong.  13  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 1.1. Sơ đồ biểu diễn quá trình giấu tin Hình 1.2. Sơ đồ biểu diễn quá trình giải mã Hai sơ đồ trên hình 1.1 và 1.2 biểu diễn quá trình giấu tin và quá trình giải tin. Phân phối Thông tin giấu Bộ nhúng thông tin Phương tiện chứa đã được giấu tin Phương tiện chứa (audio, ảnh, video ) Khoá Thông tin giấu Bộ giải mã tin Phương tiện chứa đã được giấu tin Phương tiện chứa (audio, ảnh, video ) Khoá Kiểm định  14  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 1.1.2. Phân loại các kỹ thuật giấu tin Do kỹ thuật giấu thông tin số mới được hình thành trong thời gian gần đây nên xu hướng phát triển chưa ổn định. Nhiều phương pháp mới, theo nhiều khía cạnh khác nhau đang và chắc chắn sẽ được đề xuất, bởi vậy một định nghĩa chính xác, một sự đánh giá phân loại rõ ràng chưa thể có được. Sơ đồ phân loại sau đây được Fabien A. P. Petitcolas đề xuất năm 1999. Hình 1.3. Phân loại kỹ thuật giấu tin Giấu thông tin (Information hiding) Giấu tin bí mật (steganography) Nhúng thuỷ vân (Watermarking) Thuỷ vân bền vững (Robust Copyright marking) Thuỷ vân “dễ vỡ” (Fragile Watermarking) Thuỷ vân ẩn (Imperceptible watermarking) Thuỷ vân hiện (Visible watermarking)  15  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Dựa trên việc thống kê sắp xếp khoảng 100 công trình đã công bố trên một số tạp chí, cùng với thông tin về tên và tóm tắt nội dung của khoảng 200 công trình đã công bố trên Internet, có thể chia lĩnh vực giấu tin ra làm hai hướng lớn, đó là thuỷ vân và giấu tin bí mật. Nếu như thủy vân liên quan đến ứng dụng giấu các mẩu tin ngắn nhưng đòi hỏi độ bền vững lớn của thông tin cần giấu (trước các biến đổi thông thường của tệp dữ liệu môi trường) thì giấu tin bí mật lại liên quan tới ứng dụng che giấu các bản tin đòi hỏi độ bí mật và dung lượng càng lớn càng tốt. Đối với từng hướng lớn này, quá trình phân loại theo các tiêu chí khác có thể tiếp tục được thực hiện, ví dụ dựa theo ảnh hưởng các tác động từ bên ngoài có thể chia thuỷ vân thành hai loại, một loại bền vững với các tác động sao chép trái phép, loại thứ hai lại cần tính chất hoàn toàn đối lập: dễ bị phá huỷ trước các tác động nói trên. Cũng có thể chia thuỷ vân theo đặc tính, một loại cần được che giấu để chỉ có một số người tiếp xúc với nó có thể thấy được thông tin, loại thứ hai đối lập, cần được mọi người nhìn thấy. Các thành tựu đạt được trong lĩnh vực nghiên cứu này đã bắt đầu được áp dụng hiệu quả cho mục đích bảo vệ bản quyền, chống sao chép, phân tán trái phép các sản phẩm trong môi trường số hoá và nhiều mục đích khác. Nhiều phương pháp giấu thông tin khác nhau đã được đề xuất, mỗi phương pháp có những ưu điểm, nhược điểm riêng và thích hợp cho một nhóm ứng dụng nào đó. [3],[11],[12] 1.1.3. Mục đích của giấu tin Bảo mật thông tin bằng giấu tin có hai khía cạnh. Một là bảo mật cho dữ liệu được giấu, ví dụ giấu tin mật: thông tin mật được giấu kỹ trong một đối tượng khác sao cho người khác không phát hiện được. Hai là bảo mật chính đối tượng được dùng để giấu dữ liệu vào, chẳng hạn ứng dụng bảo vệ  16  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên bản quyền, phát hiện xuyên tạc thông tin ... Một số ứng dụng đang được triển khai: - Bảo vệ bản quyền tác giả (copyright protection): Đây là ứng dụng cơ bản nhất của kỹ thuật thuỷ vân. Một thông tin nào đó mang ý nghĩa quyền sở hữu tác giả (người ta gọi nó là thuỷ vân - watermark) sẽ được nhúng vào trong các sản phẩm, thuỷ vân đó chỉ người chủ sở hữu hợp pháp các sản phẩm đó có và được dùng làm minh chứng cho bản quyền sản phẩm. Giả sử có một thành phẩm dữ liệu dạng đa phương tiện như ảnh, âm thanh, video cần được lưu thông trên mạng. Để bảo vệ các sản phẩm chống lại hành vi lấy cắp hoặc làm nhái cần phải có một kỹ thuật để “dán tem bản quyền” vào sản phẩm này. Việc dán tem hay chính là việc nhúng thuỷ vân cần phải đảm bảo không để lại một ảnh hưởng lớn nào đến việc cảm nhận sản phẩm. Yêu cầu kỹ thuật đối với ứng dụng này là thuỷ vân phải tồn tại bền vững cùng với sản phẩm, muốn bỏ thuỷ vân này mà không được phép của người chủ sở hữu thì chỉ còn cách là phá huỷ sản phẩm. - Xác thực thông tin và phát hiện xuyên tạc thông tin (authentication and tamper detection): Một tập thông tin sẽ được giấu trong phương tiện chứa, sau đó được sử dụng để nhận biết dữ liệu trên phương tiện gốc có bị thay đổi hay không. Các thuỷ vân nên được ẩn để tránh sự tò mò của đối phương, hơn nữa việc làm giả các thuỷ vân hợp lệ hay xuyên tạc thông tin nguồn cũng cần xem xét.Trong các ứng dụng thực tế, người ta mong muốn tìm được vị trí bị xuyên tạc cũng như phân biệt được các thay đổi (ví dụ như phân biệt một đối tượng đa phương tiện chứa thông tin giấu đã bị thay đổi, xuyên tạc nội dung hay chỉ bị nén mất dữ liệu).Yêu cầu chung đối với ứng dụng này là khả năng giấu thông tin cao và thuỷ vân không cần bền vững.  17  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - Dấu vân tay hay dán nhãn (fingerprinting and labeling): Thuỷ vân trong những ứng dụng này được sử dụng để nhận diện người gửi hay người nhận một thông tin nào đó. Ví dụ các vân khác nhau sẽ được nhúng vào các bản copy khác nhau của thông tin gốc trước khi chuyển cho nhiều người. Với những ứng dụng này, yêu cầu là đảm bảo độ an toàn cao cho các thuỷ vân, tránh khả năng xoá dấu vết trong khi phân phối. - Điều khiển truy cập (copy control): Các thiết bị phát hiện thuỷ vân (ở đây sử dụng phương pháp phát hiện thuỷ vân đã giấu mà không cần thông tin gốc) được gắn sẵn vào trong các hệ thống đọc ghi, tùy thuộc vào việc có thủy vân hay không để điều khiển (cho phép/cấm) truy cập. Ví dụ hệ thống quản lí sao chép DVD đã được ứng dụng ở Nhật. - Giấu tin bí mật (steganography): Các thông tin giấu được trong những trường hợp này càng nhiều càng tốt. Việc giải mã để nhận được thông tin cũng không cần phương tiện chứa gốc.[3],[11],[12] 1.1.4. Môi trƣờng giấu tin Kỹ thuật giấu tin đã được nghiên cứu và áp dụng trong nhiều môi trường dữ liệu khác nhau như trong dữ liệu đa phương tiện (văn bản, hình ảnh, âm thanh, phim ), trong sản phẩm phần mềm và gần đây là những nghiên cứu trên lĩnh vực cơ sở dữ liệu quan hệ. Trong các dữ liệu đó, dữ liệu đa phương tiện là môi trường chiếm tỉ lệ chủ yếu trong các kỹ thuật giấu tin. a. Giấu tin trong ảnh (image) Giấu thông tin trong ảnh, hiện nay, là một bộ phận chiếm tỉ lệ lớn nhất trong các chương trình ứng dụng, các phần mềm, hệ thống giấu tin trong đa phương tiện do lượng thông tin được trao đổi bằng ảnh là rất lớn và hơn nữa  18  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên giấu thông tin trong ảnh cũng đóng vai trò quan trọng trong hầu hết các ứng dụng bảo vệ an toàn thông tin như: xác thực thông tin, xác định xuyên tạc thông tin, bảo vệ bản quyền tác giả, điều khiển truy cập, giấu tin bí mật... Do đó vấn đề này đã nhận được sự quan tâm lớn của các cá nhân, tổ chức, trường đại học, và viện nghiên cứu trên thế giới. Thông tin sẽ được giấu cùng với dữ liệu ảnh nhưng chất lượng ảnh ít thay đổi và không ai biết được đằng sau ảnh đó mang những thông tin có ý nghĩa. Ngày nay, khi ảnh số đã được sử dụng phổ biến, giấu thông tin trong ảnh đã đem lại nhiều những ứng dụng quan trọng trên nhiều lĩnh vực trong đời sống xã hội. Ví dụ đối với các nước phát triển, chữ kí tay đã được số hoá và lưu trữ sử dụng như hồ sơ cá nhân của các dịch vụ ngân hàng và tài chính, nó được dùng để xác thực trong các thẻ tín dụng của người tiêu dùng. Phần mềm WinWord của MicroSoft cũng cho phép người dùng lưu trữ chữ kí trong ảnh nhị phân rồi gắn vào vị trí nào đó trong file văn bản để đảm bảo tính an toàn của thông tin. Tài liệu sau đó được truyền trực tiếp qua máy fax hoặc lưu truyền trên mạng. Theo đó, việc xác thực chữ kí, xác thực thông tin đã trở thành một vấn đề quan trọng khi việc ăn cắp thông tin hay xuyên tạc thông tin bởi các tin tặc đang trở thành một vấn nạn đối với bất kì quốc gia nào, tổ chức nào. Hơn nữa có nhiều loại thông tin quan trọng cần được bảo mật như những thông tin về an ninh, thông tin về bảo hiểm hay các thông tin về tài chính, các thông tin này được số hoá và lưu trữ trong hệ thống máy tính hay trên mạng. Chúng dễ bị lấy cắp và bị thay đổi bởi các phần mềm chuyên dụng. Việc xác thực cũng như phát hiện thông tin xuyên tạc đã trở nên vô cùng quan trọng, cấp thiết. Một đặc điểm của giấu thông tin trong ảnh là thông tin được giấu trong ảnh một cách vô hình, tương tự cách truyền thông  19  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên tin mật cho nhau mà người khác không thể biết được bởi sau khi giấu thông tin chất lượng ảnh gần như không thay đổi đặc biệt đối với ảnh mầu hay ảnh xám. Ví dụ về vụ việc ngày 11-9 gây chấn động nước Mĩ và toàn thế giới, chính tên trùm khủng bố quốc tế Osma BinLaDen đã dùng cách thức giấu thông tin trong ảnh để liên lạc với đồng bọn, và hắn đã qua mặt được cục tình báo trung ương Mĩ CIA và các cơ quan an ninh quốc tế. Chắc chắn sau vụ việc này, việc nghiên cứu các vấn đề liên quan đến giấu thông tin trong ảnh sẽ rất được quan tâm. b. Giấu tin trong âm thanh(audio) Giấu thông tin trong âm thanh mang những đặc điểm riêng khác với giấu thông tin trong các đối tượng đa phương tiện khác. Một trong những yêu cầu cơ bản của giấu tin là đảm bảo tính chất ẩn của thông tin được giấu đồng thời không làm ảnh hưởng đến chất lượng của dữ liệu gốc. Để đảm bảo yêu cầu này, kỹ thuật giấu thông tin trong ảnh phụ thuộc vào hệ thống thị giác của con người - HVS còn kỹ thuật giấu thông tin trong âm thanh lại phụ thuộc vào hệ thống thính giác - HAS. Một vấn đề khó khăn là hệ thống thính giác của con người nghe được các tín hiệu ở các dải tần rộng và công suất lớn nên đã gây khó khăn đối với các phương pháp giấu tin trong âm thanh. Nhưng hệ thống thính giác của con người lại kém trong việc phát hiện sự khác biệt các dải tần và công suất, điều này có nghĩa là các âm thanh to, cao tần có thể che giấu được các âm thanh nhỏ thấp một cách dễ dàng. Các mô hình phân tích tâm lí đã chỉ ra điểm yếu trên và thông tin này sẽ giúp ích cho việc chọn các âm thanh thích hợp cho việc giấu tin. Vấn đề khó khăn thứ hai đối với giấu thông tin trong âm thanh là kênh truyền tin. Kênh truyền hay băng thông chậm sẽ ảnh hưởng đến chất lượng thông tin sau khi giấu. Ví dụ để nhúng  20  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên một đoạn java applet vào một đoạn âm thanh (16 bit, 44.100 Hz) có chiều dài bình thường thì các phương pháp nói chung cũng cần ít nhất là 20 bit/s. Giấu thông tin trong âm thanh đòi hỏi yêu cầu cao về tính đồng bộ và tính an toàn của thông tin. Các phương pháp giấu thông tin trong âm thanh đều lợi dụng điểm yếu trong hệ thống thính giác của con người. c. Giấu tin trong phim (video) Cũng giống như giấu thông tin trong ảnh hay trong âm thanh, giấu tin trong phim cũng được quan tâm và được phát triển mạnh mẽ cho nhiều ứng dụng như điều khiển truy cập thông tin, xác thực thông tin và bảo vệ bản quyền tác giả. Ví dụ các hệ thống chương trình trả tiền xem theo đoạn với các đoạn phim (pay per view application). Các kỹ thuật giấu tin trong phim cũng được phát triển mạnh mẽ và cũng theo hai khuynh hướng là thuỷ vân số và giấu thông tin. Nhưng phần này chỉ quan tâm tới các kỹ thuật giấu tin trong phim. Một phương pháp giấu tin trong phim được Cox đưa ra là phương pháp phân bố đều. Ý tưởng cơ bản của phương pháp là phân phối thông tin giấu dàn trải theo tần số của dữ liệu gốc. Nhiều nhà nghiên cứu đã dùng những hàm cosin riêng và các hệ số truyền sóng riêng để giấu tin. Trong các thuật toán đầu tiên thường các kỹ thuật cho phép giấu các ảnh vào trong phim nhưng thời gian gần đây các kỹ thuật cho phép giấu cả âm thanh và hình ảnh vào phim. Ví dụ Swanson đã sử dụng phương pháp giấu theo khối, phương pháp này đã giấu được hai bít vào khối 8*8. Hay gần đây nhất là phương pháp của Mukherjee là kỹ thuật giấu âm thanh vào phim sử dụng cấu trúc lưới đa chiều... Giấu tin là một công nghệ mới phức tạp, đang được các nhà khoa học tập trung nghiên cứu ở nhiều nước trên thế giới như Đức, Mỹ, ý, Canada,  21  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nhật Bản…Tuy nhiên, những kết quả thực nghiệm cho thấy để có thể ứng dụng thực tế thì lĩnh vực này cần phải có thêm thời gian để nghiên cứu thẩm định nhưng các nhà khoa học cũng khẳng định rằng đây là một công nghệ mới đầy hứa hẹn cho vấn đề an toàn và bảo mật thông tin. Công việc hiện nay của các nhà khoa học là đang tập trung xây dựng một hệ thống lí thuyết chính xác cho vấn đề giấu tin, đây là một mảnh đất mới cho các nhà khoa học khám phá. Một trong những kỹ thuật quan trọng của giấu tin đang được rất nhiều các nhà khoa học quan tâm và phát triển nhất, đó là kỹ thuật thuỷ vân (watermark). [3], [11], [12] 1.2. Cơ sở lý thuyết về thuỷ vân 1.2.1. Khái niệm thuỷ vân và nhúng thuỷ vân - Thuỷ vân là một tín hiệu bảo mật và không nhận biết, được nhúng vào dữ liệu gốc để truyền dữ liệu đã nhúng đi.[9] - Nhúng thủy vân (watermarking) là một trong những kỹ thuật giấu dữ liệu hiện đại, là quá trình chèn thông tin vào dữ liệu đa phương tiện nhưng bảo đảm không nhận biết được, nghĩa là chỉ làm thay đổi nhỏ dữ liệu gốc. Thông thường người ta chỉ đề cập đến nhúng thủy vân số. Một tập các dữ liệu số thứ cấp - gọi là mã đánh dấu bản quyền hay thủy vân (watermark), được nhúng vào dữ liệu số sơ cấp - gọi là dữ liệu bao phủ (ví dụ như văn bản, hình ảnh, âm thanh và phim số, ...). Dữ liệu sau quá trình nhúng được gọi là dữ liệu nhúng.[10], [12], [13] 1.2.2. Lịch sử phát triển của thuỷ vân Tanaka (1990), Caronni và Tirkel (1993) lần lượt đưa ra những ấn bản đầu tiên về nhúng thủy vân nhưng chưa nhận được sự quan tâm đúng mức.  22  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Đến năm 1995, chủ đề này mới bắt đầu được quan tâm và từ đó, nhúng thủy vân số đã phát triển tốc độ nhanh với nhiều hướng nghiên cứu và phương pháp thực hiện khác nhau. Nhúng thủy vân được ứng dụng trong nhiều lĩnh vực như bảo vệ quyền sở hữu, điều khiển việc sao chép, xác nhận giấy tờ, hay truyền đạt thông tin khác, …trong đó ứng dụng phổ biến là cung cấp bằng chứng về bản quyền tác giả của các dữ liệu số bằng cách nhúng các thông tin bản quyền. 1.2.3. Mô hình hệ thống tổng quát quá trình nhúng và khôi phục thuỷ vân Hình 1.4. Sơ đồ nhúng thuỷ vân Thuỷ vân Dữ liệu nhúng Dữ liệu bao phủ Mã cá nhân / công cộng Quyết định thuỷ vân Dữ liệu nhúng Thuỷ vân Mã cá nhân / công cộng  23  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hình 1.5. Sơ đồ khôi phục thuỷ vân Tất cả các phương pháp nhúng thủy vân đều có chung các khối sau: một hệ thống nhúng thủy vân và một hệ thống khôi phục thủy vân. [9], [10], [12], [13] Hình 1.4. trình bày quá trình nhúng thủy vân tổng quát. Đầu vào là thủy vân, dữ liệu cần nhúng và mã cá nhân hay công cộng. Thủy vân có thể ở bất kì dạng nào như chữ số, văn bản hay hình ảnh. Khoá có thể được dùng để tăng cường tính bảo mật, nghĩa là ngăn chặn những người không có bản quyền khôi phục hay phá hủy thủy vân. Các hệ thống thực tế dùng ít nhất là một khoá, thậm chí kết hợp nhiều khoá. Đầu ra là dữ liệu đã được nhúng thủy vân. Quá trình khôi phục thủy vân tổng quát được cho ở hình 1.5. Đầu vào là dữ liệu đã nhúng thủy vân, khoá và dữ liệu gốc (có thể có hoặc không tuỳ thuộc vào phương pháp). Đầu ra hoặc là thủy vân khôi phục được hoặc đại lượng nào đó chỉ ra mối tương quan giữa nó và thủy vân cho trước ở đầu vào. Phụ thuộc vào mục đích và ứng dụng mà các yêu cầu của hệ thống nhúng thủy vân được đặt ra. Với các hệ thống thực tế, chúng đòi hỏi các yêu cầu sau: − Tính không nhận biết: các điều chỉnh gây ra do nhúng thủy vân phải thấp hơn ngưỡng cảm thụ, nghĩa là các mẫu dùng trong nhúng thủy vân chỉ được phép thay đổi nhỏ. − Tính bền vững: đây là một yêu cầu nòng cốt của nhúng thủy vân. − Khôi phục thủy vân cần hoặc không cần dữ liệu gốc. − Trích thủy vân hay kiểm chứng sự tồn tại của thủy vân.  24  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên − Các khoá và bảo mật thủy vân. 1.2.4. Một số ứng dụng của thuỷ vân Một ứng dụng phổ biến của kỹ thuật thuỷ vân là đưa ra một bằng chứng về quyền sở hữu đối với dữ liệu số bằng cách nhúng dấu hiệu mang tính bản quyền vào phim hoặc các sản phẩm ảnh số. Ngoài ra, còn có những ứng dụng khác : - Tự động điều khiển và tự hiệu chỉnh sao chép tài liệu trên Web. Ví dụ một robot tìm web để đánh dấu vào tài liệu và từ đó nhận dạng sản phẩm bất hợp pháp. - Tự động kiểm tra việc truyền nhận sóng vô tuyến. Ví dụ một robot có thể “nghe” một trạm thu phát sóng radio và tìm kiếm những dấu hiệu để biểu thị một phần cụ thể của bản nhạc hoặc lời quảng cáo vừa được phát ra. - Việc mở rộng dữ liệu- để thêm thông tin mang lại lợi ích một cách công khai. - Ứng dụng trong lấy dấu vân tay (cho phép nhận dạng dữ liệu đã phân tán).  25  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chƣơng 2- THUỶ VÂN CƠ SỞ DỮ LIỆU QUAN HỆ DỰA TRÊN KỸ THUẬT TỐI ƢU HOÁ ÁP DỤNG THUẬT TOÁN TÌM KIẾM THEO MẪU 2.1. Giới thiệu về thuỷ vân cơ sở dữ liệu (database watermarking) Tốc độ phát triển nhanh của Internet và các công nghệ có liên quan đã đưa đến một tiềm năng chưa từng có đối với việc truy cập và phân phối lại các sản phẩm kỹ thuật số. Trong bối cảnh như vậy, việc thực thi quyền sở hữu dữ liệu là một yêu cầu quan trọng đòi hỏi các giải pháp đồng bộ, bao gồm các khía cạnh về kỹ thuật, về tổ chức, và cả luật pháp. Mặc dù vẫn chưa có được những giải pháp toàn diện như vậy nhưng trong các năm gần đây, các kỹ thuật thuỷ vân đã đóng vai trò quyết định nhằm giải quyết vấn đề về quyền sở hữu này. Những kỹ thuật như vậy cho phép người chủ dữ liệu có thể nhúng một thuỷ vân ẩn vào dữ liệu. Một thuỷ vân thường mô tả những thông tin có thể được dùng để chứng minh quyền sở hữu dữ liệu, chẳng hạn như tên chủ sở hữu, nguồn gốc, hoặc người tiếp nhận nội dung này. Việc nhúng thông tin an toàn đòi hỏi thuỷ vân được nhúng trong dữ liệu không thể bị làm giả mạo hoặc bị tẩy xoá một cách dễ dàng. Nhúng ẩn có nghĩa là thuỷ vân không thể nhìn thấy được trong dữ liệu. Hơn nữa, việc phát hiện thuỷ vân được thực hiện theo phương pháp mù, tức là không đòi hỏi dữ liệu gốc cũng như thuỷ vân gốc. Đã có một số kỹ thuật thuỷ vân được phát triển để nhúng thủy vân phim, âm thanh, ảnh và dữ liệu văn bản.  26  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Trái lại, vấn đề thuỷ vân dữ liệu quan hệ đã không nhận được sự chú ý thích đáng. Tuy nhiên, có nhiều ngữ cảnh ứng dụng trong đó dữ liệu trở nên một tài sản quan trọng, vì vậy vấn đề về quyền sở hữu phải được thực thi một cách cẩn thận. Ví dụ dữ liệu về thời tiết, dữ liệu về thị trường chứng khoán, dữ liệu về hành vi của khách hàng, dữ liệu y học và khoa học. Việc nhúng thuỷ vân vào dữ liệu quan hệ có thể thực hiện được bởi trong thực tế, các dữ liệu thật có thể chấp nhận một dung sai nhỏ mà vẫn không ảnh hưởng đáng kể đến giá trị sử dụng của chúng. Cho đến nay, mới có một vài cách tiếp cận đối với bài toán thuỷ vân dữ liệu quan hệ được đề xuất. Tuy nhiên, những kỹ thuật này không bền vững đối với các tấn công thủy vân. Đề tài này trình bày một kỹ thuật thuỷ vân cơ sở dữ liệu quan hệ có độ bền vững cao so với các kỹ thuật khác. Kỹ thuật này bền vững đối với các tấn công xoá, sửa và chèn các bản ghi. [1], [2], [8],[9]  27  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.2. Mô hình chi tiết hệ thống thuỷ vân cơ sở dữ liệu Kỹ thuật tối ưu gồm hai quá trình, quá trình mã hoá và giải mã thuỷ vân. Sơ đồ khối tóm tắt các thành phần chính của mô hình hệ thống thuỷ vân như sau: Hình 2.1: Các thời kỳ mã hoá và giải mã thuỷ vân. Một bộ dữ liệu D được biến đổi thành bộ dữ liệu đã thuỷ vân DW bằng cách dùng hàm mã hoá thuỷ vân, đầu vào khoá bí mật KS chỉ được người chủ sở hữu biết, và một thuỷ vân W. Thuỷ vân làm thay đổi dữ liệu. Tuy nhiên, những thay đổi này được kiểm soát bằng cách sử dụng tập các ràng buộc thích hợp tham chiếu đến tập G. Các ràng buộc này giới hạn lượng thay đổi để có thể thực hiện trên dữ liệu. Quá trình mã hoá thuỷ vân gồm ba bước chính sau: T* KS W’ D W G Dw D’w  1',.....,' mo SS  1,....., mo SS Phân hoạch dữ liệu Phân hoạch dữ liệu Nhúng thuỷ vân Đánh giá ngƣỡng tối ƣu Kênh truyền Giải mã ngƣỡng Bầu chọn theo đa số  28  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bước 1: Phân hoạch dữ liệu: dùng khoá bí mật KS , bộ dữ liệu D được chia thành m phần {So , . . . , Sm-1 } không giao nhau. Bước 2: Nhúng thuỷ vân: Một bít thuỷ vân được nhúng vào mỗi phần bằng cách thay đổi các thống kê phân hoạch trong khi vẫn thỏa mãn các ràng buộc sử dụng trong bộ G. Sự thay đổi này được thực hiện bằng cách giải bài toán tối ưu hoá có ràng buộc. Bước 3: Đánh giá ngưỡng tối ưu: các thống kê bit nhúng được sử dụng để tính toán ngưỡng tối ưu T* - ngưỡng làm cực tiểu hoá khả năng ( xác suất ) xảy ra lỗi giải mã. Bộ dữ liệu đã nhúng thuỷ vân DW được chuyển đi qua các kênh truyền và do đó có thể chịu những tấn công có chủ đích hoặc không có chủ đích nhằm phá huỷ thông tin thuỷ vân. Chú ý rằng những tấn công có chủ đích có thể được thực hiện mà không cần bất cứ sự hiểu biết gì về khoá bí mật KS hoặc bộ dữ liệu D. Giải mã thuỷ vân là quá trình lấy ra thuỷ vân đã nhúng từ bộ dữ liệu đã nhúng thuỷ vân DW, sử dụng khoá bí mật KS và ngưỡng tối ưu T*. Thuật toán giải mã này không rõ ràng bởi bộ dữ liệu gốc D không yêu cầu giải mã thành công thuỷ vân đã nhúng. Quá trình giải mã thuỷ vân được chia thành ba bước chính sau: Bước 1: Phân hoạch bộ dữ liệu: sử dụng thuật toán phân hoạch dữ liệu đã dùng trong phần mã hoá trên, sinh ra các phân vùng dữ liệu. Bước 2: Giải mã ngưỡng: Các thống kê của mỗi phân vùng được đánh giá và bit đã nhúng được giải mã bằng cách dùng lược đồ giải mã ngưỡng dựa trên ngưỡng tối ưu T*.  29  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Bước 3: Bầu chọn theo đa số: Các bit thuỷ vân được giải mã sử dụng kỹ thuật bầu chọn theo đa số. Tiếp theo sẽ trình bày chi tiết các kỹ thuật, các thuật toán cho quá trình mã hoá và giải mã thuỷ vân.[9] 2.3. Phân hoạch dữ liệu Thuật toán phân hoạch dữ liệu phân chia bộ dữ liệu thành các phần, các tập hợp con dựa vào khoá bí mật KS . Bộ dữ liệu D là một cơ sở dữ liệu quan hệ với lược đồ ),...,,( 10 AAPD trong đó P là thuộc tính khoá chính, 10 ,..., AA là  thuộc tính dùng để nhúng thuỷ vân và D là số bản ghi trong D . Bộ dữ liệu D được chia thành m phần không giao nhau  10 ,..., mSS , sao cho mỗi phần iS chứa trung bình m D bản ghi từ bộ dữ liệu D . Các phần không giao nhau, tức là, với hai phần bất kỳ iS và jS mà ji  thì  ji SS  . Với mỗi bản ghi Dr  , thuật toán phân hoạch dữ liệu tính toán mã xác thực thông tin ( MAC ) để đảm bảo an toàn và mã này được cho bởi hàm ))||.(||( SS KPrHKH , trong đó Pr. là khoá chính của bản ghi r ,  H là hàm băm an toàn và || là toán tử nối. Sử dụng MAC đã tính, các bản ghi được đưa vào các phân vùng. Với bản ghi r , phân vùng tương ứng được tính như sau: mKPrHKHrpartition SS mod))||.(||()(  Sử dụng đặc tính này của hàm băm để phân phối các bản ghi đồng đều vào các phân vùng, kỹ thuật phân hoạch này chia trung bình m D vào mỗi phân  30  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên vùng. Hơn nữa, kẻ tấn công không thể đoán được các bản ghi đã được đưa vào phân vùng nào nếu không biết rõ về khoá bí mật SK và số phân vùng dữ liệu đã phân hoạch m được giữ bí mật. Không nhất thiết phải giữ bí mật m . Tuy nhiên, việc giữ bí mật có thể gây khó khăn hơn cho kẻ tấn công muốn tái lập các phần đó. Thuật toán phân hoạch dữ liệu được mô tả như sau: Thuật toán: get_partitions Đầu vào: bộ dữ liệu D , khoá bí mật SK , số phân vùng m Đầu ra: Các phân vùng dữ liệu 10 ,..., mSS 1. 10 ,..., mSS  {} 2. for each bản ghi Dr  3. mKPrHKHrpartition SS mod))||.(||()(  4. chèn r vào )(rpartitionS 5. return 10 ,..., mSS Mặc dù hầu hết các dữ liệu quan hệ đều có khóa chính, kỹ thuật này có thể được mở rộng để xử lý trường hợp khi dữ liệu quan hệ không có khoá chính. Giả sử quan hệ thuộc tính đơn,  bit ý nghĩa nhất ( MSB ) của dữ liệu có thể được dùng để thay thế cho khoá chính. Việc sử dụng MSB cho việc nhúng thủy vân sẽ không làm thay đổi  bit ý nghĩa nhất này. Tuy nhiên, nếu quá nhiều bản ghi chia sẻ cùng  bít MSB có thể cho phép kẻ tấn công suy  31  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên luận được thông tin về sự phân phối trong các phần dữ liệu. Trường hợp quan hệ đa thuộc tính, sử dụng các thuộc tính nhận biết thay vì sử dụng khoá chính; ví dụ dữ liệu y học, ta có thể sử dụng tên đầy đủ của bệnh nhân, địa chỉ bệnh nhân, ngày tháng năm sinh của bệnh nhân. Ký hiệu Ý nghĩa m Số phân vùng  Kích thước nhỏ nhất của một phân vùng W Chuỗi bit thuỷ vân {bl-1,…,b0} l Chiều dài của chuỗi bit thuỷ vân Xmax Các thống kê nhúng thuỷ vân cực đại Xmin Các thống kê nhúng thuỷ vân cực tiểu Si Phân vùng dữ liệu thứ i |Si|, n Độ dài của vector Si Ks Khoá bí mật T* Ngưỡng giải mã tối ưu Gi Ràng buộc thứ i i Vector thao tác trong R n Hình 2.2. Bảng biểu diễn các ký hiệu sử dụng trong thuật toán  32  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2.4. Nhúng thuỷ vân Thuật toán nhúng thuỷ vân bằng cách mã hoá bit có thể coi như một bài toán tối ưu có ràng buộc. Ở đây, thuật toán tìm kiếm theo mẫu được sử dụng để giải bài toán tối ưu. Việc sử dụng thuật toán tối ưu được quyết định tuỳ thuộc thời điểm ứng dụng và các yêu cầu tính toán. Để đơn giản, giả sử các bản ghi trong phân vùng iS chứa thuộc tính số đơn. Trong trường hợp này, mỗi phần iS có thể được biểu diễn bằng một véctơ dữ liệu số n inii ssS  ],...,[ 1 . 2.4.1 Mã hoá bít đơn Cho bít thuỷ vân ib , và véctơ dữ liệu số n inii ssS  ],...,[ 1 . Thuật toán mã hoá bít ánh xạ vectơ dữ liệu iS thành vectơ dữ liệu mới ii W i SS  , trong đó n inii  ],...,[ 1 là vectơ thao tác. Các thao tác bị hạn chế bởi các ràng buộc trong bộ   ipii ggG ,...,1 . Việc mã hoá này dựa trên hàm mã hoá tối ưu gọi là hàm giấu được định nghĩa như sau: Hàm giấu  : n , với  là tập hợp các tham số bí mật do người chủ sở hữu dữ liệu đưa ra. Tập hợp  có thể được xem như là một phần của khoá bí mật. Chú ý rằng khi hàm giấu được áp dụng cho iiS  thì chỉ vectơ thao tác i là biến, trong khi iS và  là các hằng số. Để mã hoá bit ib vào trong tập iS , thuật toán mã hoá bít sẽ làm tối ưu hóa hàm hàm giấu )( iiS  . Bài toán tối ưu hóa sẽ là bài toán cực đại hoặc cực tiểu hàm giấu tùy thuộc vào bit ib :  33  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Nếu bít ib =1 thì thuật toán mã hoá bit thực hiện giải bài toán cực đại hoá: i max )( iiS  thoả mãn ràng buộc iG Nếu bít ib =0 thì bài toán đơn giản được chuyển thành bài toán cực tiểu hóa. Giải pháp cho bài toán tối ưu hoá sinh ra vectơ thao tác * i để *)( iiS  tối ưu. Khi đó, bộ dữ liệu mới *ii W i SS  . Việc cực đại hoá cho ib =1 và cực tiểu hoá cho ib =0, đảm bảo rằng các giá trị của hàm *)( iiS  sinh ra trong cả hai trường hợp được đặt ở vị trí có khoảng cách lớn nhất và do đó làm cho bít được chèn bền vững hơn đối với các tấn công, đặc biệt là các tấn công thay đổi dữ liệu. Thuật toán mã hoá bít đơn được mô tả như sau: Thuật toán: encode_single_ bit Đầu vào: Tập dữ liệu Si, Bit bi, Tập ràng buộc Gi, Tập tham số bí mật  , Các tập thống kê Xmax, Xmin Đầu ra: Tập dữ liệu * iiS  1. If ( )( iS then return Si 2. If (b==1) then 3. Maximize ( )( iiS  ) thỏa mãn ràng buộc Gi 4. Chèn *)( iiS  vào Xmax  34  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5. else 6. Minimize ( )( iiS  ) thỏa mãn ràng buộc Gi 7. Chèn *)( iiS  vào Xmin 8. return * iiS  Thuật toán mã hóa bít nhúng bít ib vào phần iS nếu iS . Giá trị của  là kích thước cực tiểu của phân vùng. Việc cực đại hoá và cực tiểu hoá trong thuật toán mã hoá bít làm tối ưu hoá hàm giấu *)( iiS  thoả mãn các ràng buộc trong iG . Các thống kê cực đại hoá và cực tiểu hoá được ghi lại cho mỗi bước mã hoá trong maxX , minX tương ứng như đã được chỉ ra trong các dòng 4 và 7 của thuật toán mã hoá. Các thống kê này được dùng để tính toán các tham số giải mã tối ưu. Tập hợp các ràng buộc iG biểu diễn giới hạn thay đổi cho phép có thể được thực hiện trên các phần tử của iS . Các ràng buộc mô tả không gian khả thi cho vectơ thao tác i với mỗi bước mã hoá bit tùy thuộc vào từng ứng dụng và dữ liệu. Các ràng buộc này tương tự với các ràng buộc được thực hiện trên các thuật toán nhúng thuỷ vân cho âm thanh, hình ảnh, và phim với yêu cầu chủ yếu là thuỷ vân không thể phát hiện được bằng hệ thống nghe nhìn của con người. Ví dụ: Các ràng buộc phạm vi có thể được dùng để kiểm soát sự thay đổi của ij , tức là:  35  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên maxmin ijijij  Kiểu ràng buộc khác có thể yêu cầu bộ dữ liệu đã thuỷ vân duy trì các thống kê nào đó. Ví dụ, trung bình bộ dữ liệu sinh ra bằng trung bình bộ dữ liệu gốc, khi đó ràng buộc có dạng: 0 1   n j ij Một vài ràng buộc khác có thể được tạo ra phụ thuộc vào các yêu cầu ứng dụng. Các ràng buộc này được xử lý bằng thuật toán mã hoá bít dùng các kỹ thuật tối ưu hoá có ràng buộc. Hàm giấu được sử dụng ở đây phụ thuộc vào các thống kê dữ liệu. Các giá trị trung bình và phương sai của bộ dữ liệu mới ii W i SS  tương ứng là )( iiS   và 2 )( iiS   ; gọi tắt là  và 2 . Hình 2.3: Phân phối của tập iiS  trên trục số và các đầu vào tail được khoanh tròn. Điểm tham chiếu :   cref , trong đó )1,0(c là một số thực bí mật, một phần của tập  . Các điểm dữ liệu trong iiS  ở trên ref như là các đầu vào “tail” được mô tả trong hình 2.3.  36  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Hàm giấu c được định nghĩa là số đầu vào tail đã chuẩn hoá bằng độ dài của iS , cũng như tail count được chuẩn hoá. Hàm này được tính như sau:    n j refsiic ijijn S 1 }{1 1 )( trong đó : n là độ dài của iS {}1 là hàm chỉ được định nghĩa như sau: Chú ý rằng tham chiếu ref phụ thuộc vào cả  và  , có nghĩa là nó không cố định và thay đổi theo các thống kê iiS  . Tail count )( iic S  được chuẩn hoá phụ thuộc vào phân phối của iiS  và tham chiếu động. Hàm mục tiêu )( iic S  là hàm phi tuyến và không khả vi, do đó bài toán tối ưu hoá trở nên gần với bài toán tối ưu hoá có ràng buộc phi tuyến. Các phương pháp tiếp cận truyền thống dựa vào độ dốc (gradient) không thể áp dụng được cho những bài toán như thế này. Có hai kỹ thuật để giải bài toán tối ưu hóa này là thuật toán di truyền và kỹ thuật tìm kiếm theo mẫu. Luận văn này sử dụng kỹ thuật tìm kiếm theo mẫu. Việc giải bài toán tối ưu hoá này không nhất thiết phải tìm ra lời giải toàn cục bởi vì việc tìm ra lời giải như thế này có thể đòi hỏi một lượng tính toán rất lớn. Mục đích chính ở đây  37  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên là tìm ra lời giải gần tối ưu đảm bảo các giá trị cực tiểu hoá hàm )( iic S  và cực đại hoá hàm )( iic S  cách xa nhau. Thuật toán di truyền được dùng định rõ tổng thể các lời giải tối ưu bằng thời điểm xử lý, trong khi tìm kiếm theo mẫu được dùng để cung cấp một lời giải tối ưu cục bộ không theo thời gian xử lý 2.4.2. Thuật toán tìm kiếm theo mẫu Thuật toán di truyền không tìm ra được tối ưu cục bộ, tuy nhiên thuật toán di truyền yêu cầu một số lượng lớn hàm đánh giá tập trung thành tối ưu toàn cục. Do vậy, giải thuật di truyền được sử dụng chỉ khi thời gian xử lý không yêu cầu chính xác và thuỷ vân được thực hiện độc lập. Kỹ thuật tìm kiếm theo mẫu cho phép thực hiện nhanh hơn. Các phương pháp tìm kiếm theo mẫu là một lớp các phương pháp tìm kiếm trực tiếp cho quá trình tối ưu hoá phi tuyến. Các phương pháp tìm kiếm theo mẫu này đã được sử dụng rộng rãi bởi tính đơn giản và tính thực tế của chúng. Tìm kiếm theo mẫu bắt đầu tại điểm ban đầu và thử hàm mục tiêu tại mẫu các điểm đã định trước xoay quanh điểm với mục tiêu tạo ra thế mới tốt hơn. Sự di chuyển này tương tự việc di chuyển thăm dò. Nếu thử thành công (tức là tạo ra một thế mới tốt hơn), do vậy quá trình này được lặp lại với mẫu xoay quanh điểm mới tốt nhất. Trái lại, kích cỡ của mẫu thử sẽ giảm và hàm mục tiêu được thử lại với điểm hiện tại này. Để cải thiện việc thực hiện việc tìm kiếm theo mẫu, hàm mục tiêu )( iic S  được xấp xỉ bằng các hàm sigmoid trơn như sau:  38  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên    n j ijijrefiic sSigmoid n S f 1 ),( )( 1 )(ˆ  trong đó )(),( xSigmoid  là hàm sigmoid (xích ma) với các tham số ),(  . )(),( xSigmoid  = )(1 1 1    xe Với 0 , }8,2,1{ , hàm )(),( xSigmoid  có dạng như sau: Hình 2.4. Biểu diễn Sigmoid(α,τ ) tại τ = 0 và α = {1, 2, 8}. Các ràng buộc có thể được xử lý nhờ các kỹ thuật trước đó. Tuy nhiên, việc tìm kiếm theo mẫu có thể xử lý các ràng buộc bằng cách hạn chế việc di chuyển thăm dò chỉ theo các hướng không gian khả thi; do đó đảm bảo giải pháp được sinh ra là khả thi. Hoạt động có hệ thống của việc tìm kiếm theo  39  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên mẫu và kích cỡ mẫu dễ thích nghi dẫn đến sự hội tụ đến các giải pháp tối ưu khả thi nhanh hơn. Tuy nhiên, việc tìm kiếm theo mẫu không đảm bảo tìm ra tối ưu toàn bộ. Vấn đề này có thể được khắc phục bằng cách bắt đầu thuật toán từ các điểm khả thi đầu tiên khác nhau. 2.4.3. Thuật toán nhúng thuỷ vân Thuỷ vân là một bộ l bít W=bl-1, . . . , b0 được nhúng vào các phần dữ liệu  10 ,..., mSS . Để việc nhúng thuỷ vân được nhiều lần trong bộ dữ liệu, độ dài thuỷ vân l được chọn sao cho: ml  . Thuật toán nhúng thuỷ vân sẽ nhúng bít ib vào phần kS sao cho ilk mod . Kỹ thuật này đảm bảo mỗi bít thuỷ vân được nhúng       l m lần trong bộ dữ liệu D . Thuật toán nhúng thuỷ vân được mô tả như sau: Thuật toán: embed_watermark Đầu vào: Tập dữ liệu D, Khóa bí mật K, Số phân vùng m, Thủy vân W={b0, …bi-1} Đầu ra: Tập dữ liệu đã nhúng thủy vân DW, Ngưỡng giải mã tối ưu T* 1. Dw, Xmax, Xmin  {} 2. S0, …,Sm-1  get_partitions(D, Ks, m) 3. for each Phân vùng Sk  40  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4. i  k mod l 5. Sk w  encode_single_bit (bi, Sk, c, Xmax, Xmin) 6. Chèn Sk w vào Dw 7. T*  get_optimal_thershold(Xmax, Xmin) 8. return Dw, T* Thuật toán nhúng thuỷ vân sẽ sinh ra các phần  10 ,..., mSS bằng cách gọi hàm partitionsget _ , sau đó với mỗi phần kS bít thuỷ vân ib được mã hoá bằng cách sử dụng thuật toán mã hoá bít đơn (encode_single_bit). Phần thay đổi sinh ra W kS được chèn vào bộ dữ liệu đã nhúng thuỷ vân. Các thống kê ),( minmax XX thu được sau mỗi bít nhúng và được sử dụng bằng thuật toán get_optimal_threshold để tính toán ngưỡng giải mã tối ưu. 2.5. Đánh giá ngƣỡng giải mã Trong phần trước, ta đã tìm hiểu kỹ thuật mã hoá bít. Nhúng bit thuỷ vân bi ở Si sinh ra W iS . Trong phần này, ta sẽ tìm hiểu kỹ thuật giải mã bít – kỹ thuật được dùng để lấy ra bít thuỷ vân đã nhúng ib từ phần W iS . Kỹ thuật giải mã bít dựa trên ngưỡng tối ưu T* để làm cực tiểu hoá xác suất lỗi giải mã. Với phần dữ liệu W iS , kỹ thuật giải mã bít sẽ tính toán hàm giấu )( WiS và so sánh với ngưỡng giải mã tối ưu T* để giải mã bít đã nhúng ib . Nếu )( WiS >T* bít giải mã là 1, ngược lại bít giải mã là 0.  41  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Ví dụ: sử dụng hàm giấu đã được mô tả ở phần trước, kỹ thuật giải mã tính toán tail count đã chuẩn hoá của W iS bằng cách tính giá trị tham chiếu ref và đếm số đầu vào trong W iS lớn hơn ref . Sau đó, tail count đã chuẩn hoá được so sánh với T* được thể hiện trong hình 2.5. Giá trị của ngưỡng T* nên được tính toán cẩn thận để làm cực tiểu hoá xác suất lỗi giải mã bít. Hình 2.5. Lược đồ ngưỡng giải mã Xác suất lỗi giải mã bít được định nghĩa là xác suất bit nhúng được giải mã sai. Ngưỡng giải mã tối ưu T* được chọn để làm cực tiểu hoá xác suất lỗi giải mã. Giai đoạn nhúng bít dựa trên việc cực tiểu hoá hoặc cực đại hoá hàm giấu tail count; các giá trị hàm giấu đã tối ưu hoá này sẽ được tính trong giai đoạn mã hoá để tính ngưỡng tối ưu T*. Các giá trị hàm giấu cực đại hoá tương ứng với ib =1 được lưu trong tập maxX . Tương tự, các giá trị hàm giấu cực tiểu hoá được lưu trữ trong minX . Gọi errP , 0P và 1P tương ứng là xác suất lỗi giải mã, xác suất bit mã hóa là 0 và xác suất bit mã hóa là 1. Cho eb , db , và )(xf tương ứng là bit mã hoá, bit giải mã, và hàm mật độ xác suất. Khi đó, errP được tính như sau: errP = )0,1()1,0(  eded bbPbbP  42  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên = 01 )0|1()1|0( PbbPPbbP eded  = 01 )0|()1|( PbTxPPbTxP ee  =     T e T e dxbxfPdxbxfP )0|()1|( 01 Để cực tiểu hoá xác suất lỗi giải mã ( errP ) đối với ngưỡng T, ta lấy đạo hàm cấp một của errP đối với T để xác định ngưỡng tối ưu T*, như sau:             T e T e err dxbxf T Pdxbxf T P T P )0|()1|( 01 )0|()1|( 01  ee bTfPbTfP Các hàm )0|( ebxf và )1|( ebxf được đánh giá từ các thống kê minX và maxX tương ứng. Qua các thực nghiệm về minX và maxX , ta thấy các phân phối )0|( ebxf và )1|( ebxf có thể được đánh giá như các phân phối Gaussian ),( 00 N và ),( 11 N . Tuy nhiên, phân tích sau đây có thể tiếp tục được sử dụng với các kiểu phân phối khác. 0P có thể được đánh giá bằng |||| || minmax min XX X  , 1P 01 P . Thay thế các biểu thức Gaussian cho )0|( ebxf và )1|( ebxf , thì đạo hàm cấp một của errP có dạng: ) 2 )( exp( 2 ) 2 )( exp( 2 2 0 2 0 0 0 2 1 2 1 1 1            TPTP T Perr  43  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Cho đạo hàm cấp một của errP bằng 0, ta sẽ được phương trình bậc 2, có thể tính giá trị ngưỡng tối ưu T* làm cực tiểu hoá errP . Đạo hàm cấp 2 của errP được đánh giá tại T* để đảm bảo điều kiện ( 0 *)( 2 2    T TPerr ) được thoả mãn. 0 2 ln** 2 21 2 0 2 1 2 0 2 0 2 1 01 10 2 1 2 0 2 01 2 102 2 1 2 0 2 1 2 0                   P TT Từ phân tích trên, việc chọn ngưỡng tối ưu T* dựa trên các thống kê thu được của thuật toán nhúng thuỷ vân. Ngưỡng tối ưu T* làm cực tiểu hoá xác suất lỗi giải mã và như thế nâng cao độ bền của thuỷ vân được nhúng do khả năng giải mã thành công tăng. Xác suất lỗi giải mã cũng phụ thuộc vào các ràng buộc. Nếu các ràng buộc chặt thì lượng thay đổi cho bộ dữ liệu D có thể không đủ đối với việc nhúng thuỷ vân. Tất cả xác suất lỗi giải mã thuỷ vân được làm giảm đi bằng cách nhúng thuỷ vân nhiều lần trong bộ dữ liệu đó, về cơ bản nó là sự lặp lại mã sửa sai. 2.6. Phát hiện thuỷ vân Thuật toán phát hiện thuỷ vân sẽ lấy ra thuỷ vân đã nhúng nhờ các tham số bí mật gồm có: KS, m,  , c, T. Thuật toán này bắt đầu bằng việc sinh các phần dữ liệu  10 ,..., mSS dựa vào bộ dữ liệu đã thuỷ vân WD , khoá bí mật SK , và số phần dữ liệu đã phân hoạch m là đầu vào của thuật toán phân hoạch dữ liệu (get_partitions). Mỗi phần sẽ mã hoá một bít thuỷ vân đơn. Để lấy ra bít đã nhúng, ta sử dụng lược đồ giải mã ngưỡng dựa vào ngưỡng tối ưu T làm cực tiểu hoá xác suất xảy ra  44  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên lỗi giải mã như đã trình bày trong mục 2.5. Nếu kích thước phân vùng dữ liệu nhỏ hơn  thì bít giải mã không được thực hiện, ngược lại nó được giải mã nhờ lược đồ giải mã ngưỡng. Vì thuỷ vân 01 ,..., bbW l được nhúng nhiều lần trong bộ dữ liệu, mỗi bít thuỷ vân được lấy ra nhiều lần ở nơi bít ib được lấy ra từ phần kS với ilk mod . Các bít lấy ra được giải mã nhờ kỹ thuật chọn theo đa số. Mỗi bít ib được lấy ra l m lần . Thuật toán phát hiện thuỷ vân như sau: Thuật toán: detect_watermark Đầu vào: Tập dữ liệu đã nhúng thủy vân *,,,,, TKcmD SW  , Độ dài thủy vân l Đầu ra: Thủy vân thu được WD 1. Đặt ones[0, …, l-1]  0 2. Đặt zeros[0, …, l-1]  0 3. S0, …, Sm-1  get_partitions(Dw, Ks, m) 4. for j=0, …, m-1 5. if jS 6. i  j mod l  45  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 7. value   cSi ,0, 8. if *Tvalue 9. ones[i]  ones[i] + 1 10. else 11. zeros[i]  zeros[i] + 1 12. for j=0 , …, l-1 13. if ones[j] > zeros[j] 14. WD|j|  1 15. else if ones[j] < zeros[j] 16. WD|j|  0 17. else 18. WD|j|  x 19. return WD Trường hợp quan hệ đa thuộc tính bền vững thuỷ vân được tăng lên do nhúng thuỷ vân trong nhiều thuộc tính. 2.7. Kiểu tấn công Ở đây giả thiết rằng kẻ tấn công không thể tìm được tập dữ liệu gốc và không biết được gì về thông tin bí mật được sử dụng trong quá trình nhúng thuỷ vân. Thông tin bí mật bao gồm khoá mật Ks, số lượng phân hoạch m, hằng số c, các tham số tối ưu và ngưỡng T*. Vì vậy kẻ tấn công sẽ không có  46  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên khả năng tạo ra các phân vùng dữ liệu và do đó không thể chọn lọc tấn công bit thuỷ vân cụ thể. Một số kiểu tấn công điển hình: - Xoá ngẫu nhiên một vài bản ghi từ cơ sở dữ liệu cũ, tạo ra một cơ sở dữ liệu mới để công bố. - Sửa đổi một vài bản ghi bên trong cơ sở dữ liệu để gây ra lỗi ở các bit thuỷ vân được nhúng, dẫn đến quá trình giải mã sai. - Chèn một vài bản ghi vào cơ sở dữ liệu gây ra sai lệch dữ liệu nhằm phá hủy các bit thuỷ vân đã nhúng. Để mô phỏng một số kiểu tấn công, chương trình sử dụng một tập dữ liệu thuỷ vân “an toàn”. Một tập dữ liệu thuỷ vân là “an toàn” nếu có thể khôi phục bit thuỷ vân sau quá trình giải mã, cùng sử dụng chung khoá bí mật với quá trình mã hóa. Với tập dữ liệu này, chúng ta tiến hành thao tác trên dữ liệu để phù hợp với từng mô hình tấn công.  47  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Chƣơng 3 - CÀI ĐẶT LƢỢC ĐỒ THUỶ VÂN CƠ SỞ DỮ LIỆU QUAN HỆ BẰNG KỸ THUẬT TỐI ƢU TÌM KIẾM THEO MẪU 3.1. Giới thiệu về kỹ thuật tìm kiếm theo mẫu Tìm kiếm theo mẫu (hay còn gọi là tìm kiếm trực tiếp) là một phương pháp giải các bài toán tối ưu, không yêu cầu nhiều thông tin về độ dốc của hàm mục tiêu. Trái ngược với phương pháp tối ưu truyền thống sử dụng thông tin về độ dốc hoặc là phát sinh lớn hơn để tìm ra một điểm tối ưu. Thuật toán tìm kiếm theo mẫu xác định một tập các điểm xung quanh điểm hiện tại, tìm ra một điểm tại giá trị của hàm mục tiêu thấp hơn giá trị của của điểm hiện tại. Phương pháp tìm kiếm trực tiếp có thể được sử dụng để giải các bài toán với hàm mục tiêu không khả vi hoặc hàm liên tục. Một thuật toán tìm kiếm theo mẫu xác định một chuỗi các điểm để tìm ra mật độ càng dày với điểm gốc. Tại mỗi bước, thuật toán tìm kiếm một tập các điểm gọi là một mắt lưới, xung quanh điểm hiện tại - điểm đã tính tại bước trước của thuật toán. Thuật toán tạo ra mắt lưới bằng cách thêm điểm hiện tại vào một bội số vô hướng của một tập các vector cố định gọi là một mẫu. Nếu thuật toán tìm ra một điểm trong mắt lưới để tận dụng hàm mục tiêu tại điểm hiện tại, điểm mới trở thành điểm hiện tại tại bước tiếp của thuật toán.  48  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3.2. Mô tả ứng dụng 3.2.1. Cơ sở của ứng dụng Quá trình xây dựng ứng dụng này được tiến hành dựa trên các sự kiện sau: Một người dùng có ý định công bố kết quả nghiên cứu của anh ta và chắc chắn rằng anh ta có quyền tác giả đối với việc công bố dữ liệu đó, anh ta đã nhúng thuỷ vân vào dữ liệu trước khi công bố chúng. Đôi khi, người dùng nghi ngờ rằng dữ liệu của anh ta đã bị thay đổi và công bố đó là kết quả của một người nào khác. Để chứng minh quyền sở hữu dữ liệu, anh ta cố gắng khôi phục thuỷ vân đã nhúng vào tập dữ liệu bằng cách áp dụng kỹ thuật giải mã. Trong quá trình xây dựng ứng dụng, luận văn đã giải thích tất cả các bước từ phân hoạch dữ liệu đến nhúng thuỷ vân rồi giải mã chúng. Luận văn cũng giải thích kiểu tấn công và khám phá dữ liệu để chứng minh rằng quyền sở hữu dữ liệu đã được tìm hiểu kỹ lưỡng. 3.2.2. Giả thiết Xây dựng ứng dụng dựa trên giả định sau: + Kẻ tấn công không am hiểu về tập dữ liệu đã được thủy vân. Thậm chí nếu kẻ tấn công đó nhận ra rằng dữ liệu đã được nhúng thuỷ vân và cũng không biết được kỹ thuật đã được sử dụng. + Kẻ tấn công không biết được về khoá chính trong tập dữ liệu. + Kỹ thuật thuỷ vân có khả năng kiểm soát các bản ghi với nhiều thuộc tính. Tuy nhiên trong quá trình kiểm thử, dữ liệu chứa chỉ chứa một bản ghi với một thuộc tính số đơn.  49  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3.2.3. Một số kết quả thực nghiệm đạt đƣợc a. Tham số đầu vào áp dụng thực nghiệm Bộ dữ liệu thực nghiệm trong luận văn này là bộ dữ liệu tự tạo được giả định là số liệu điện sinh hoạt của một vùng nào đó, bộ dữ liệu này bao gồm 8000 bộ. Để cho đơn giản trong quá trình cài đặt, giả sử bộ dữ liệu chỉ bao gồm 2 trường, một trường là khoá chính của quan hệ, một trường là trường được chọn để nhúng thuỷ vân. Các thông số dùng cho quá trình thí nghiệm bao gồm: + Hàm băm: MD5 + Khoá bí mật: KS = 89 + Số phân vùng: m = 20 + Tham số bí mật c = 0.75 + Chuỗi bit đem nhúng (watermark): 10111 + Kích cỡ nhỏ nhất của 1 phân vùng:  =10 dữ liệu được thiết kế chứa trong file định dạng Excel với tên là Data.xls Tác giả dùng Matlab 7.04 làm môi trường cài đặt ứng dụng. Thí nghiệm được chạy trên hệ thống có cấu hình Intel Pentium IV 2 Ghz, 512 MB Ram.  50  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên b. Kết quả thực nghiệm Sau nhiều lần chạy thử nghiệm tác giả nhận thấy, tốc độ giải mã thuỷ vân nhanh hơn gấp nhiều lần tốc độ nhúng thuỷ vân. Thử nghiệm với các tấn công kết quả như sau: Thực hiện tấn công mỗi kiểu tấn công 20 lần, mỗi lần tác động trên các số lượng bản ghi khác nhau, kết quả thống kê như bản dưới đây:  51  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên Kiểu tấn công Số bản ghi bị tác động 100 200 300 500 600 1000 1500 2000 2500 3000 4000 5000 6000 7000 750 0 Xoá Thành công (lần) 20 20 18 20 18 14 14 13 8 4 3 1 0 0 0 Thất bại (lần) 0 0 2 0 2 6 6 7 12 16 17 19 20 20 20 Chèn Thành công (lần) 20 20 20 17 10 0 0 0 0 0 0 0 0 0 0 Thất bại (lần) 0 0 0 3 10 20 20 20 20 20 20 20 20 20 20 Sửa Thành công (lần) 20 20 20 18 19 17 19 18 18 18 16 12 11 11 12 Thất bại (lần) 0 0 0 2 1 3 1 2 2 2 4 8 9 9 8 Hình 3.1 Bảng thống kê kết quả thử nghiệm  52  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên  Nhận xét: Căn cứ vào bảng đã thống kê các tấn công sau các quá trình thực nghiệm tác giả có nhận xét như sau: + Tỉ lệ thành công của kiểu tấn công thay đổi dữ liệu là cao nhất. Khi thay đổi các thông số đầu vào như khoảng cho phép dữ liệu thay đổi là 0.05, số lượng bộ bị thay đổi là 7500 (trên tổng số 8000 bộ) tương đương với trên 90% tổng số bộ bị thay đổi thì tỉ lệ thành công khi giải mã thuỷ vân vẫn là trên 60% (khoảng 63%). + Tỉ lệ thành công của kiểu tấn công chèn thay đổi dữ liệu là cao nhất. Khi thay đổi các thông số đầu vào như khoảng cho phép dữ liệu thay đổi là 0.05, số lượng bộ bị thay đổi là 7500 (trên tổng số 8000 bộ) tương đương với trên 90% tổng số bộ bị thay đổi thì tỉ lệ thành công khi giải mã thuỷ vân vẫn là trên 60% (khoảng 63%). + Tỉ lệ giải mã thuỷ vân thành công của kiểu tấn công xoá bộ kém hơn so với kiểu tấn công thay đổi dữ liệu. i) Với số lượng bộ cho phép xoá đi là 50% tổng số bộ thì tỉ lệ giải mã thành công là trên 100%. ii) Với 90% tổng số bộ bị xoá thì tỉ lệ giải mã thành công là trên 15%. + Tỉ lệ giải mã thuỷ vân thành công của kiểu tấn công chèn thêm bộ vào cơ sở dữ liệu là thấp nhất. i) Nếu chèn thêm trung bình khoảng 7.5% đến 8% tổng số bộ vào cơ sở dữ liệu thì tỉ lệ giải mã thành công là 50%  53  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ii) Nếu chèn thêm trên 10% (khoảng 12%) số lượng bộ mới vào cơ sở dữ liệu thì tỉ lệ giải mã thành công là 0% Các thông số trên cũng có thể bị thay đổi nếu thay đổi các thông số đầu vào như: Tăng hoặc giảm khoảng thay đổi cho phép trên dữ liệu khi nhúng thuỷ vân; độ ngẫu nhiên của việc tấn công (phá hoại); số lượng phân vùng đi kèm với độ lớn của dữ liệu (tổng số bộ).  54  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên KẾT LUẬN Thuỷ vân cơ sở dữ liệu là một trong kỹ thuật quan trọng để chứng minh quyền sở hữu đối với cơ sở dữ liệu sau khi được phân tán trên Internet. Đầu tiên, hình thành cơ chế thuỷ vân cơ sở dữ liệu quan hệ giống một bài toán tối ưu có ràng buộc, đây là kỹ thuật đã khắc phục được những điểm yếu trong các kỹ thuật thuỷ vân đã được đề xuất trước đây. Với nội dung này, luận văn đã tìm hiểu một số vấn đề: Tổng quan về kỹ thuật giấu tin và thuỷ vân, phương pháp thuỷ vân cơ sở dữ liệu quan hệ dựa vào kỹ thuật tìm kiếm theo mẫu và ứng dụng của chúng. Cụ thể luận văn đã đạt được các kết quả sau: - Trình bày tổng quan về kỹ thuật giấu tin và thuỷ vân - Trình bày cơ sở lý thuyết về thuỷ vân cơ sở dữ liệu quan hệ dựa trên kỹ thuật tối ưu áp dụng thuật toán tìm kiếm theo mẫu. - Mô tả ứng dụng của kỹ thuật tìm kiếm theo mẫu trong quá trình nhúng thuỷ vân. Hướng phát triển của đề tài Tiếp tục nghiên cứu một số kỹ thuật khác áp dụng đối với thuỷ vân cơ sở dữ liệu quan hệ.  55  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên PHỤ LỤC 1. Mã xác thực thông tin (MAC) Trong phân hoạch dữ liệu, mã xác thực thông tin (MAC) được sử dụng để xác định nguồn gốc của thông tin Hình 3.1. Sơ đồ hoạt động của MAC Người gửi thông điệp thực hiện thông qua một thuật toán MAC để sinh ra một thẻ dữ liệu MAC. Sau đó, thông điệp và thẻ MAC được gửi tới người nhận. Người nhận lần lượt tiến hành chia thông điệp để truyền thông qua một thuật toán tương tự MAC sử dụng một khoá tương tự, kết quả được một thẻ dữ liệu MAC thứ hai. Khi đó, người nhận so sánh thẻ MAC đầu tiên nhận Người gửi Người nhận Thông điệp Thuật toán MAC MAC Cách giải quyết: nếu giống nhau thì khi đó là tin cậy và toàn vẹn còn ngược lại là sai Thông điệp Thông điệp MAC Thuật toán MAC MAC MAC Khoá K =? Khoá K  56  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên được trong quá trình truyền trước đó với thẻ MAC sinh ra thứ hai. Nếu thấy giống nhau, người nhận có thể cho rằng là an toàn, tính toàn vẹn của thông điệp không bị xâm phạm và thông điệp không bị thay đổi trong quá trình truyền nhận Xác thực bằng MAC M || | C M C So sánh K K Nơi gửi thông tin Mã xác thực (MAC) Nơi nhận thông tin Trong đó: M: Thông tin gốc K: Khoá bí mật dùng chung giữa bên gửi và bên nhận ||: Nối mã xác thực vào thông tin gốc C: Hàm tạo mã xác thực Hình 3.2. Mô tả quá trình xác thực thông tin bằng MAC  57  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2. Hàm băm Khái niệm hàm băm Hàm băm (hash function) là giải thuật nhằm sinh ra các giá trị băm tương ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối tượng trong lập trình hướng đối tượng, v.v...). Giá trị băm đóng vai trò gần như một khóa để phân biệt các khối dữ liệu, tuy nhiên, người ta chấp nhận hiện tượng trùng khóa hay còn gọi là đụng độ và cố gắng cải thiện giải thuật để giảm thiểu sự đụng độ đó. Hàm băm thường được dùng trong bảng băm nhằm giảm chi phí tính toán khi tìm một khối dữ liệu trong một tập hợp (nhờ việc so sánh các giá trị băm nhanh hơn việc so sánh những khối dữ liệu có kích thước lớn). Vì tính thông dụng của bảng băm, ngày nay, đa số ngôn ngữ lập trình đều cung cấp thư viện ứng dụng bảng băm, trong đó có các vấn đề như: tập hợp (collection), danh sách (list), bảng(table), ánh xạ (mapping), từ điển (dictionary)). Thông thường, các lập trình viên chỉ cần viết hàm băm cho các đối tượng nhằm tích hợp với thư viện bảng băm đã được xây dựng sẵn. Một hàm băm tốt phải thỏa mãn các điều kiện sau: * Tính toán nhanh. * Các khoá được phân bố đều trong bảng. * Ít xảy ra đụng độ. * Xử lý được các loại khóa có kiểu dữ liệu khác nhau. Tính chất của hàm băm Hai tính chất quan trọng của hàm băm là: - Tính một chiều: không thể suy ra dữ liệu ban đầu từ kết quả.  58  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - Tính duy nhất: xác suất để có sự đụng độ (hash collision), tức là hai thông điệp khác nhau có cùng một kết quả băm, là nhỏ. Ứng dụng Các hàm băm được ứng dụng trong nhiều lĩnh vực, chúng thường được thiết kế phù hợp với từng ứng dụng. Ví dụ, các hàm băm mật mã học giả thiết sự tồn tại của một đối phương - người có thể cố tình tìm các dữ liệu vào với cùng một giá trị băm. Một hàm băm tốt là một phép biến đổi "một chiều", nghĩa là không có một phương pháp cụ thể để tính toán được dữ liệu vào nào đó tương ứng với giá trị băm mong muốn, khi đó việc giả mạo sẽ rất khó khăn. Bảng băm, một ứng dụng quan trọng của các hàm băm, cho phép tra cứu nhanh một bản ghi dữ liệu nếu cho trước khóa của bản ghi đó (Lưu ý: các khóa này thường không bí mật như trong mật mã học, nhưng cả hai đều được dùng để "mở khóa" hoặc để truy nhập thông tin.) Ví dụ, các khóa trong một từ điển điện tử Anh-Anh có thể là các từ tiếng Anh, các bản ghi tương ứng với chúng chứa các định nghĩa. Trong trường hợp này, hàm băm phải ánh xạ các xâu chữ cái tới các chỉ mục của mảng nội bộ của bảng băm. Các hàm băm dành cho việc phát hiện và sửa lỗi tập trung phân biệt các trường hợp mà dữ liệu đã bị làm nhiễu bởi các quá trình ngẫu nhiên. Khi các hàm băm được dùng cho các giá trị tổng kiểm, giá trị băm tương đối nhỏ có thể được dùng để kiểm chứng rằng một file dữ liệu có kích thước tùy ý chưa bị sửa đổi. Hàm băm được dùng để phát hiện lỗi truyền dữ liệu. Tại nơi gửi, hàm băm được tính cho dữ liệu được gửi, giá trị băm này được gửi cùng dữ liệu. Tại đầu nhận, hàm băm lại được tính lần nữa, nếu các giá trị băm không  59  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên trùng nhau thì lỗi đã xảy ra ở đâu đó trong quá trình truyền. Việc này được gọi là kiểm tra dư thừa (redundancy check). Các hàm băm còn được ứng dụng trong việc nhận dạng âm thanh, chẳng hạn như xác định xem một file MP3 có khớp với một file trong danh sách một loạt các file khác hay không. Do vậy hàm băm được dùng để phát hiện và chống xâm nhập; bảo vệ tính toàn vẹn của thông điệp được gửi qua mạng; tạo khóa từ mật khẩu, và tạo chữ kí điện tử. Hàm băm một chiều: - Biến đổi thông tin gốc có độ dài bất kỳ thành khối thông tin có độ dài cố định gọi là mã băm - Chỉ có thể dùng hàm băm để tạo ra các mã băm từ thông tin gốc mà không làm ngược lại gọi là hàm băm một chiều. Hoạt động cơ bản của hàm băm Hình 3.3. Biểu diễn hàm băm  60  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên SHA-1 và MD5 là hai thuật toán băm thông dụng nhất và được sử dụng trong rất nhiều hệ thống bảo mật. MD5 (Message-Digest algorithm 5) là một hàm băm để mã hóa với giá trị băm là 128bit. Từng được xem là một chuẩn trên Internet, MD5 đã được sử dụng rộng rãi trong các chương trình an ninh mạng, và cũng thường được dùng để kiểm tra tính nguyên vẹn của tập tin. MD5 được Ronald Rivest thiết kế vào năm 1991 để thay thế cho hàm băm trước đó, MD4 (cũng do ông thiết kế, trước đó nữa là MD2). MD5 có hai ứng dụng quan trọng: - MD5 được sử dụng rộng rãi trong thế giới phần mềm để đảm bảo rằng tập tin tải về không bị hỏng. Người sử dụng có thể so sánh giữa thông số kiểm tra phần mềm bằng MD5 được công bố với thông số kiểm tra phần mềm tải về bằng MD5. Hệ điều hành Unix sử dụng MD5 để kiểm tra các gói mà nó phân phối, trong khi hệ điều hành Windows sử dụng phần mềm của hãng thứ ba. - MD5 được dùng để mã hóa mật khẩu. Mục đích của việc mã hóa này là biến đổi một chuổi mật khẩu thành một đoạn mã khác, sao cho từ đoạn mã đó không thể nào lần trở lại mật khẩu. Có nghĩa là việc giải mã là không thể hoặc phải mất một khoãng thời gian vô tận (đủ để làm nản lòng các hacker). Thuật giải MD5 biến đổi một thông điệp có chiều dài bất kì thành một khối có kích thước cố định 128 bits. Thông điệp đưa vào sẽ được cắt thành các khối 512 bits. Thông điệp được đưa vào bộ đệm để chiều dài của nó sẻ chia hết cho 512. Bộ đệm hoạt động như sau:  61  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên - Trước tiên nó sẽ chèn bit 1 vào cuối thông điệp. - Tiếp đó là hàng loạt bit Zero cho tới khi chiều dài của nó nhỏ hơn bội số của 512 một khoảng 64 bit . - Phần còn lại sẻ được lấp đầy bởi một số nguyên 64 bit biểu diển chiều dài ban đầu của thông điệp.  62  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên TÀI LIỆU THAM KHẢO [1]. “Nghiên cứu và Phát triển Kỹ thuật Thuỷ vân Cơ sở Dữ liệu Quan hệ”, Báo cáo kết quả nghiên cứu của đề tài cơ sở 2008, 12/2008, Phòng CSDL & LT. [2]. Bùi Thế Hồng, Nguyễn Thị Thu Hằng, Lƣu Thị Bích Hƣơng, “Thủy vân cơ sở dữ liệu quan hệ”, Tạp chí Khoa học & Công nghệ, ĐH Thái Nguyên, 2009. [3]. Vũ Ba Đình, “Giấu thông tin trong cơ sở dữ liệu không gian”, Tạp chí nghiên cứu khoa học kỹ thuật và công nghệ Quân sự, số 4, 30-37 [4]. R. Agrawal, J. Kiernan, “Watermarking Relational Databases” in Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002. [5]. R. Agrawal, P. J. Haas, and J. Kiernan. “Watermarking relational data: framework, algorithms and analysis*”. The VLDB Journal (2003). [6]. R. Sion, M. Atallah, S. Prabhakar.“Watermarking Relational Databases” CERIAS TR 2002-28*. Center for Education and Research in Information Assurance, Computer Sciences, Purdue University, 2002. [7]. R. Sion, M. Atallah, and S. Prabhakar. “Rights Protection for Relational Data”. IEEE Transactions on Knowledge and Data Engineering, 16(6), June 2004. [8]. R. Sion, “Proving ownership over categorical data”. ICDE 2004. [9]. M. Shehab, E. Bertino, A. Ghafoor. “Watermarking Relational Databases using Optimization Based Techniques”. CERIAS Tech Report 2006-41. [10]. www.watermarkingworld.org.  63  Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên [11]. W. Bender, D. Gruhl, N. Morimoto, A. Lu, “Techniques for data Hiding” IBM SYSTEMS JOURNAL, VOL 35, NOS 3&4, 1996. [12]. Stefan Katzenbeisser and Fabien A.P.Petitcolas, “Information Hiding Techniques for Steganography and Digital Watermarking”.Artech House Boston London. [13]. Michael Arnold, Martin Schmucker and Stephen D. Wolthusen, “Techniques and Applications of Digital Watermarking and Content Protection”. Artech House Boston London.

Các file đính kèm theo tài liệu này:

  • pdf21LV09_CNTT_KHMTNguyenThiHanh.pdf
Tài liệu liên quan