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
Phạm Thị Thu Hường
BẢO VỆ BẢN QUYỀN CƠ SỞ DỮ LIỆU
BẰNG THUỶ VÂN ẢNH SỐ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ CHUYÊN NGÀNH KHOA HỌC MÁY TÍNH
1.2.2 Tính bền vững (Robustness) 11
1.2.3 Cập nhật phần tăng thêm (Incremental Updatability) 12
1.2.4 Không dễ cảm nhận được (Imperceptibility) 12
1.2.5 Hệ thống mù ( Blind System) 12
1.3 Những tấn công trên hệ thuỷ vân cơ sở dữ liệu quan hệ 13
1.3.1 Cập nhật thông thường 13
1.3.2 Tấn công có chủ đích 13
1.4 Các ứng dụng chủ yếu của thuỷ vân cơ sở dữ liệu quan hệ 15
1.4.1 Bảo vệ bản quyền hoặc chứng minh quyền sở hữu 15
1.4.2 Nhận thực thông tin (Authentication) 15
1.5 Các kỹ thuật thủy vân cơ sở dữ liệu quan hệ 16
Chương 2 THỦY VÂN SỬ DỤNG CÁC BIT LSB 17
2.1 Chuẩn bị thuật toán 17
2.1.1 Đặt vấn đề 17
2.1.2 Các bít ít ý nghĩa nhất 18
2.1.3 Mã chứng thực thông điệp 19
2.2 Các thuật toán 19
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
2
2.2.1 Mô hình thuỷ vân 20
2.2.2 Thuật toán nhúng thuỷ vân 20
2.2.3 Thuật toán phát hiện thuỷ vân 24
2.2.4 Một số lưu ý 26
2.2.5 Các quan hệ không có các khóa chính 27
2.3 Phân tích đánh giá thuật toán 28
2.3.1 Xác suất nhị thức tích luỹ 28
2.3.2 Hàm ngưỡng 29
Chương 3 THỦY VÂN SỬ DỤNG CÁC BIT Ý NGHĨA NHẤT 31
Thực sự, qua nghiên cứu và thử nghiệm tôi thấy việc phát triển và cài
đặt các kỹ thuật thủy vân cơ sở dữ liệu rất phức tạp và rất khó để thỏa mãn
được những yêu cầu khắt khe của lĩnh vực bảo vệ bản quyền đối với loại dữ
liệu này. Những kết quả được trình bày trong báo cáo này là những tìm hiểu
và nghiên cứu bước đầu của tôi trong lĩnh vực mới này. Chắc chắn là trong
báo cáo này còn có nhiều khiếm khuyết. Tôi mong rằng sẽ nhận được những ý
kiến góp ý xác đáng giúp tôi có được kết quả tốt hơn.
Trong thời gian tới, tôi hy vọng sẽ có cơ hội tiếp tục thực hiện hướng
nghiên cứu mới này và có thể đạt được những kết quả sâu hơn và tốt hơn.
II. Mục đích nghiên cứu
Tìm hiểu các kỹ thuật thuỷ vân bảo vệ bản quyền cơ sở dữ liệu quan hệ.
Cài đặt thử nghiệm thủy vân trên cơ sở dữ liệu quan hệ dựa vào các bit
LSB và MSB.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
2
III. Nhiệm vụ nghiên cứu
Hiểu rõ cơ sở lý luận và toán học của các kỹ thuật giấu tin và các kỹ
thuật thuỷ vân.
Phát triển các chương trình cài đặt lược đồ thuỷ vân bảo vệ bản quyền
cơ sở dữ liệu quan hệ.
IV. Phạm vi nghiên cứu
Nghiên cứu, đánh giá các kỹ thuật thuỷ vân.
Các công cụ lập trình và phần mềm dùng để cài đặt các lược đồ nhúng
và giải thuỷ vân.
V. Phương pháp nghiên cứu
Sưu tầm tìm hiểu các tài liệu, các kết quả nghiên cứu về giấu tin và
thuỷ vân.
Đánh giá các kỹ thuật thuỷ vân đã biết
Tính năng an toàn và bảo mật thông tin của kỹ thuật giấu tin được thể
hiện ở hai khía cạnh. Một là bảo vệ cho dữ liệu đem giấu và hai là bảo vệ cho
chính đối tượng được sử dụng để giấu tin. Tương ứng với hai khía cạnh đó
chúng ta có hai khuynh hướng kỹ thuật rõ ràng đó là giấu tin mật
(Steganography) mà chúng ta đã tìm hiểu trong các chương trước) và thuỷ vân
số (Watermarking).
Trong kỹ thuật giấu tin mật, thông tin cần giấu được gọi là thông điệp
(Message) còn trong kỹ thuật thuỷ vân số thì được gọi là thuỷ vân
(Watermark). Thuỷ vân có thể là một chuỗi các kí tự, hay một hình ảnh, logo
nào đó.
Nói đến thuỷ vân số là nói đến kỹ thuật giấu tin nhắm đến những ứng
dụng bảo đảm an toàn dữ liệu cho đối tượng được sử dụng để giấu tin như:
bảo vệ bản quyền, chống xuyên tạc, nhận thực thông tin, điều khiển sao chép
v.v…Có thể thấy rõ là phần ứng dụng của thủy vân rất lớn, mỗi ứng dụng lại
có những yêu cầu riêng và tính chất riêng, do đó các kỹ thuật thuỷ vân cũng
có những tính năng khác biệt tương ứng: Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
5
Thuỷ vân hiện
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
6
1.1 Một số khái niệm cơ bản
1.1.1 Thuỷ vân là gì ?
Từ “thuỷ vân” có xuất xứ từ kỹ thuật đánh dấu nước thời xưa. Đây là
kỹ thuật đánh dấu chìm một hình ảnh, một logo, hay một dữ liệu nào đó lên
trên giấy nhằm mục đích trang trí và phân biệt được xuất xứ của sản phẩm
giấy. Như vậy, thông tin cần giấu được gọi là thuỷ vân (Watermark).
Thuỷ vân có thể là một chuỗi các ký tự, hay một hình ảnh, logo nào đó.
Thuỷ vân mô tả thông tin có thể được dùng để chứng minh quyền sở hữu hoặc
chống xuyên tạc.
Có hai loại thuỷ vân, đó là : thuỷ vân bền vững và thuỷ dễ vỡ.
Thuỷ vân bền vững (Robust watermark): là thuỷ vân tồn tại bền vững
cùng với dữ liệu, không dễ dàng bị phá huỷ trước những biến đổi, tấn công
lên dữ liệu. Các kỹ thuật này thường được dùng trong các ứng dụng bảo vệ
bản quyền, chứng minh quyền sở hữu.
Thuỷ vân dễ vỡ (Fragile watermark): là thuỷ vân dễ bị biến đổi trước
những biến đổi hay tấn công lên dữ liệu. Các kỹ thuật này thường được
dùng trong các ứng dụng nhận thực thông tin, đảm bảo tính toàn vẹn dữ
liệu.
Các kỹ thuật thuỷ vân ngay từ khi mới ra đời đã nhận được sự quan tâm rất
lớn của các nhà khoa học. Các kỹ thuật thuỷ vân này đã được nghiên cứu và
áp dụng trong nhiều môi trường dữ liệu khác nhau như: dữ liệu đa phương
tiện (image, text, audio, video, . . .), hay các phẩm phần mềm, và gần đây là
những nghiên cứu trên môi trường cơ sở dữ liệu quan hệ. Trong các môi
trường dữ liệu đó thì dữ liệu đa phương tiện (đặc biệtt là image) được nghiên
cứu và áp dụng sớm nhất và là môi trường chiếm tỷ lệ chủ yếu. Tuy nhiên,
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
8
Thuỷ vân cơ sở dữ liệu quan hệ là phương pháp nhúng một lượng thông
tin nào đó vào trong dữ liệu quan hệ. Thuỷ vân cơ sở dữ liệu quan hệ là thuỷ
vân ẩn, bền vững.
Một thuỷ vân có thể được áp dụng cho bất kỳ một cơ sở dữ liệu quan hệ
nào có các thuộc tính mang một đặc điểm là những thay đổi nhỏ tại một số giá
trị của chúng không làm ảnh hưởng đến các ứng dụng.
Ví dụ, dữ liệu khí tượng được sử dụng để xây dựng các mô hình dự báo
thời tiết. Độ chính xác của vectơ gió và nhiệt độ tương ứng trong dữ liệu này
được đo chính xác đến 1.8 m/s và 0.5
o
C. Các sai số được đưa vào do thuỷ
vân có thể dễ dàng được hạn chế trong sự cho phép của các dữ liệu này. Hay
một ví dụ khác đáng chú ý là các nhà xuất bản sách khi in các bảng toán học (
như các bảng logarit và lịch thiên văn ) thường cố ý đưa vào một số lỗi nhỏ để
có thể dễ dàng nhận dạng các bản sao bị ăn cắp.
Đối với hầu hết các cơ sở dữ liệu quan hệ trong đó có chứa các tham số
thì những sai lệch do hệ thống thuỷ vân gây ra có thể được điều chỉnh sao cho
chúng nằm trong miền dung sai của độ đo.
1.1.3 Sự cần thiết của các kỹ thuật thuỷ vân CSDL quan hệ
Hiện nay, có khá nhiều tài liệu về thuỷ vân các dữ liệu đa phương tiện.
Hầu hết các kỹ thuật này ban đầu được phát triển cho các bức ảnh tĩnh và sau
đó được mở rộng cho video và audio. Cho dù có khá nhiều điều có thể học hỏi
được từ các kết quả đã đạt được về thuỷ vân dữ liệu đa phương tiện nhưng
cho đến nay vẫn còn rất nhiều thách thức kỹ thuật mới đối với lĩnh vực thuỷ
vân cơ sở dữ liệu quan hệ bởi vì các dữ liệu quan hệ và các dữ liệu đa phương
tiện khác nhau ở khá nhiều khía cạnh quan trọng. Những khác biệt đó bao
gồm:
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
10
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 văn bản đã được format. Thủy vân thường được nhúng vào văn bản bằng
cách thay đổi khoảng cách giữa các từ và các dòng văn bản. Một số kỹ thuật
dựa vào việc nhấn mạnh một vài câu trong văn bản. Nhìn chung, các kỹ thuật
này có thể sử dụng để thủy vân các quan hệ chỉ chứa các thuộc tính kiểu văn
bản, còn đối với các quan hệ chứa các thuộc tính kiểu đơn giản thì rất khó áp
dụng.
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ệ
Chúng ta có thể thấy rằng thủy vân các dữ liệu quan hệ có những thách
thức kỹ thuật đáng kể và có các ứng dụng thực tế có ý nghĩa xứng đáng được
quan tâm thích đáng từ phía cộng đồng những người nghiên cứu cơ sở dữ
liệu. Cần phải xác định một hệ thống thủy vân và kèm theo đó là phát triển
các kỹ thuật nhất định. Những kỹ thuật này chắc chắn là sẽ dựa phần lớn vào
các nguyên tắc thủy vân đang tồn tại. Tuy nhiên, chúng cũng sẽ đòi hỏi phải
có những mở rộng và các sáng kiến mới.
Để minh họa cho sự khả thi của một lược đồ thủy vân cơ sở dữ liệu
quan hệ, chúng tôi trình bày một kỹ thuật hữu hiệu thỏa mãn những tiêu
chuẩn của một hệ thống thủy vân. Kỹ thuật này chỉ đánh dấu các thuộc tính
kiểu số và giả thiết là các thuộc tính được đánh dấu có thể chấp nhận những
thay đổi nhỏ ở một số giá trị. Ý tưởng cơ bản là đảm bảo tại một số vị trí bit
của một số thuộc tính trong một số bộ có chứa các giá trị nhất định. Các bộ,
Tuy nhiên, B cũng có thể ngờ vực ngay cả khi mẫu của B 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
để B sẽ tìm thấy mẫu bit của B trong ít nhất
bộ từ
bộ là nhỏ hơn
.
1.2.2 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, A thay đổi
liệu gốc và cả thuỷ vân gốc. Một hệ thống thủy vân như vậy được gọ là hệ
thống mù. Tính chất này rất quan trọng vì nó cho phép có thể phát hiện thuỷ
vân trong bản sao của quan hệ cơ sở dữ liệu cho dù quan hệ gốc đã được cập
nhật.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
13
1.3 Những tấn công trên hệ thuỷ vân cơ sở dữ liệu quan hệ
Vì các quan hệ cơ sở dữ liệu luôn được cập nhật nên các thuỷ vân được
giấu trong một quan hệ có thể bị mất do những cập nhật thông thường cũng
như các tấn công có chủ đích.
1.3.1 Cập nhật thông thường
Giả sử A lấy trộm dữ liệu của B mà không nhận ra nó đã được thủy
vân. Sau đó, A có thể cập nhật dữ liệu đã ăn trộm khi anh ta sử dụng nó.
Kỹ thuật đánh dấu cần đảm bảo rằng B không bị mất thủy vân của cô
ngay trong các dữ liệu bị ăn trộm, thậm chí đối với cả những cập nhật của A.
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 đó.
1.3.2 Tấn công có chủ đích
A 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ệ B trước những tấn công gây hại của
A.
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,
thủy vân của B và đòi quyền sở hữu.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
15
Tấn công ngược lại: A có thể phát động một cuộc tấn công ngược lại để
đòi chủ quyền nếu anh ta có thể khám phá thành công một thủy vân bịa
đặt. Cái thủy vân mà A công bố thực ra chỉ là một xuất hiện ngẫu nhiên mà
thôi.
1.4 Các ứng dụng chủ yếu của thuỷ vân cơ sở dữ liệu quan hệ
1.4.1 Bảo vệ bản quyền hoặc chứng minh quyền sở hữu
Ngày nay, việc bảo vệ bản quyền hoặc chứng minh quyền sở hữu
(Copyright Protection or Proving Ownership) đối với các nguồn cơ sở dữ liệu
quan hệ ở bên ngoài là một vấn đề quan trọng trong các môi trường ứng dụng
dựa vào Internet và trong nhiều ứng dụng phân phối dữ liệu. Đâ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 đó (hay còn gọi là thuỷ
vân) mang ý nghĩa quyền sở hữu sẽ được nhúng vào trong dữ liệu quan hệ.
Thuỷ vân đó chỉ một mình người chủ sở hữu hợp pháp cơ sở dữ liệu đó có và
được dùng làm minh chứng cho bản quyền sản phẩm.
1.4.2 Nhận thực thông tin (Authentication)
Một tập thông tin sẽ được giấu trong cơ sở dữ liệu quan hệ. Sau đó, các
thông tin này sẽ được sử dụng để nhận biết xem dữ liệu gốc có bị thay đổi hay
không. Bằng kỹ thuật thuỷ vân, người ta có thể lấy thông tin đã giấu vào trong
dữ liệu quan hệ đó ra. Nếu thông tin lấy ra trùng với thông tin ban đầu đem
giấu thì chứng tỏ dữ liệu gốc không bị thay đổi. Ngược lại, thông tin lấy ra và
thông tin ban đầu có sự khác biệt thì chứng tỏ dữ liệu đã bị thay đổi, xuyên
tạc. 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.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
)
trong đó, P là thuộc tính khóa chính (mục 2.2.5 sẽ trình bày các mở rộng cho
trường hợp thủy vân một quan hệ không có một thuộc tính khóa chính)
Để đơn giản, có thể giả thiết là tất cả thuộc tính A
0
, . . . , A
- 1
đều có
thể là ứng cử viên đề thủy vân. Chúng đều là các thuộc tính kiểu số và các
giá trị của chúng có một tính chất là những thay đổi ở
bits ít ý nghĩa nhất
của chúng đều không cảm nhận được.
là một tham số điều khiển dùng để xác định số các bộ cần đánh dấu.
Số các bộ cần đánh dấu được ước tính bằng công thức:
/
thường được cân đối với
để xác định phạm vi của các thay đổi được phép
tiến hành đối với các giá trị của một thuộc tính. Nếu có ít bộ được đánh dấu
Số các bộ được đánh dấu
mức ý nghĩa của phép thử để phát hiện một thủy vân
Số lượng tối thiểu các bộ được đánh dấu một cách đúng
đắn cần có để có thể phát hiện được thủy vân
Hình 1: Các ký hiệu
2.1.2 Các bít ít ý nghĩa nhất
Các bít ít ý nghĩa nhất (LSB – Least Significant Bits) là các bít ở bên phải
nhất của một chuỗi bít.
Ví dụ, trong chuỗi bít 1110 thì bít ít ý nghĩa nhất là 0; với số bít ít ý nghĩa
nhất là 3 thì số bít ít ý nghĩa nhất trong chuỗi bít 1000101 là 101.
Kỹ thuật thủy vân dựa vào các bit ít ý nghĩa nhất có sử dụng đến một loại mã
được gọi là mã chứng thực thông điệp.
Số hóa bởi Trung tâm Học liệu - Đại học Thái Nguyên
19
2.1.3 Mã chứng thực thông điệp
Cho hàm băm một chiều H thao tác trên một thông điệp đầu vào có độ dài tùy
ý M và cho trở lại một giá trị băm có độ dài cố định h:
h = H(M)
Hàm này có các đặc trưng sau:
i) với M đã cho, có thể dễ dàng tính được h,
ii) với h đã cho, khó có thể tính được M sao cho H(M) = h, và
iii) với M đã cho, khó có thể tìm được một thông điệp khác M
thuộc tính trong một bộ, các vị trí bít trong một thuộc tính và các giá trị bít
nhất định này đều phải được xác định một cách chính xác và logic dưới sự
kiểm soát của một khoá bí mật K của chủ nhân quan hệ. Mẫu bít này sẽ hình
thành ra thuỷ vân. Chỉ duy nhất chủ nhân của khoá bí mật mới có thể tìm lại
được thuỷ vân với xác suất cao.
2.2.1 Mô hình thuỷ vân
Hình 2: Mô hình thuỷ vân sử dụng các bít ít ý nghĩa nhất
2.2.2 Thuật toán nhúng thuỷ vân
Thuật toán này có sử dụng mã chứng thực thông điệp MAC đã nói đến trong
phần 2.1.3 ở trên, F(r.P) = H(K o H(K o r.P))
Input: Khoá bí mật K chỉ có chủ cơ sở dữ liệu biết, và các tham số
,
,
cũng được chủ cơ sở dữ liệu xác định.
Output: Bộ dữ liệu được thuỷ vân.
// Khóa bí mật K, chỉ có chủ cơ sở dữ liệu biết.
Kênh tấn
công
Phát hiện
thuỷ vân
Nhúng
thuỷ vân
Khoá bí mật, K
Dữ liệu, R
Dữ liệu được
// đánh dấu thuộc tính A
i
4) bit_index j = F(r.P ) mod
// đánh dấu bit thứ j
5) r.A
i
= mark(r.P, r. A
i
, j) // gọi thủ tục mark
6) mark(primary_key pk, number
, bit index j) return number // thủ tục mark
7) first_hash = H(K pk)
8) if (first_hash is even) then
9) set the j
th
least significant bit of
to 0
10) else
11) set the j
th
least significant bit of v to 1
12) return v
Hình 3: Thuật toán nhúng thủy vân
Hình 3 là mô tả của thuật toán nhúng thủy vân bao gồm các dòng lệnh:
Dòng 2 xác định xem bộ đang xét có được chọn để đánh dấu không. Vì
thuộc tính đã chọn thì sẽ không đánh dấu giá trị này và giữ nguyên hiện
trạng của nó.
Có thể viết thuật toán trên đây bằng một cách khác đơn giản hơn và gọi nó là
thuật tóan đánh dấu như sau:
Cho hàm MAC:
F(r.P ) = H(K
H(K
r.P ))
và các tham số K, e, m và v được chọn ngẫu nhiên và giữ bí mật với các
giả thiết sau đây:
“K” là khóa bí mật
Copyright: Tài liệu đại học ©