Một lược đồ thủy vân thuận nghịch khóa công khai cho cơ sở dữ liệu dựa trên kỹ thuật mở rộng các thuộc tính kiểu thực

n bƣớc 3 
 Trƣờng hợp 2: nếu trích tin, chuyển đến bƣớc 4 
 Bƣớc 3: Khôi phục p từ p’ 
 Trƣờng hợp 1: nếu D(p’)=5 thì p=p’ 
 Trƣờng hợp 2: nếu D(p)=4 thì p=p’ div 2 
 Chuyển xuống bƣớc 5 
 Bƣớc 4: trích bít b và khôi phục p từ p’ 
 b=p’ mod 2 
 p= p’ div 2 
 Bƣớc 5: Khôi phục giá trị X=t.A bằng cách ghép các thành phần n, s và p: 
 X=Ghep(n,s,p) 
 Nhận xét 2 (tính đúng đắn của thuật toán khôi phục): Tính đúng đắn của thuật toán khôi phục có thể dễ dàng 
chứng minh bằng cách sử dụng tính chất của thuật toán nhúng tin phát biểu trong nhận xét 1. 
 Một số ví dụ minh họa thuật toán nhúng tin và thuật toán khôi phục 
 Ví dụ 1: X=21.365 thì n=21, s=0, p=365, không nhúng tin, p’=p=365 và X’=X=21.365. 
 Ví dụ 2: X=30.017 thì n=30, s=1, p=17, không nhúng tin, p’=2*p=34 và X’=30.034. 
 Ví dụ 3: X=25.28 và b=1 thì n=25, s=0, p=28, nhúng tin, p’=2*p+b=57 và X’=25.57. 
 Ví dụ 4: X=18 và b=1 thì n=18, s=0, p=0, nhúng tin, p’=2*p+b=1 và X’=18.1. 
C. Phương pháp nhúng tin trên cơ sở dữ liệu quan hệ 
1. Thuật toán nhúng 
 Đầu vào cơ sở dữ liệu quan hệ R= (P, , ,... , , ,... ) trong đó P là thuộc tính khóa, , ,... 
 các thuộc tính giá trị thực, , ,... các thuộc tính kiểu khác, số bộ (bản ghi) trong bảng dữ liệu, W=( , 
 ,... ) là dãy bít thủy vân 
 Đầu ra là cơ sở dữ liệu R’ chứa W 
 Bƣớc 1: Xác định khả năng nhúng (số bít tối đa có thể nhúng) trên cơ sở dữ liệu R 
402 MỘT LƢỢC ĐỒ THỦY VÂN THUẬN NGHỊCH KHÓA CÔNG KHAI CHO CƠ SỞ DỮ LIỆU DỰA TRÊN KỸ THUẬT... 
 Ký hiệu t. là giá trị thuộc tính của bộ thứ t, là phần phân của t. . Nếu đuôi D( ) thuộc tập N, thì theo 
mục A, ta có thể nhúng 1 bít thủy vân trên giá trị t. . Khi đó ta gọi t. là khả nhúng. 
 Gọi là số giá trị khả nhúng trong số các giá trị t. với t=1,..., , khi đó: ∑ là khả năng nhúng trên 
cơ sở dữ liệu R 
 Bƣớc 2: Điều chỉnh dãy bít thủy vân W theo khả năng nhúng 
 Nếu số bít thủy vân nhỏ hơn hoặc bằng thì giữ nguyên W, trái lại ta ngắt bỏ bít cuối của W. Nói cách 
khác, W chỉ còn bít đầu tiên: W=( , ,... ). Nhƣ vậy sau khi điều chỉnh, dãy W có độ dài : 
W=( , ,... ) 
 Bƣớc 3: Nhúng W vào cơ sở dữ liệu R 
 Chọn giá trị khả nhúng bất kỳ của R, gọi các giá trị này là , ,... . Nhúng mỗi bít vào để đƣợc 
theo thuật toán B1 
 Bƣớc 4: Tạo cơ sở dữ liệu thủy vân R’ 
 R’ đƣợc tạo từ R sau khi thay các giá trị bằng 
2. Thuật toán khôi phục W và R 
 Đầu vào là cơ sở dữ liệu thủy vân R’. Ngoài ra biết tập các giá trị X’= , ,... } là các giá trị thủy vân 
nhận đƣợc trong thuật toán nhúng. 
 Đầu ra là dãy bít thủy vân W=( , ,... ) và cơ sở dữ liệu gốc R. 
 Bƣớc 1: Từ dãy X’ trích dãy bít thủy vân W và khôi phục dãy giá trị X= , ,... } theo thuật toán III.B.2 
 Bƣớc 2: Khôi phục cơ sở dữ liêu gốc R: R đƣợc tạo từ R’ sau khi thay các giá trị bằng 
 Nhận xét 3 (về khả năng nhúng): ở trên đã chỉ ra số bít có thể nhúng đƣợc vào thuộc tính bằng số các giá trị 
khả nhúng trong số giá trị t. với i =1,.., . Ngoài ra, t. đƣợc gọi là khả nhúng nếu phần phân của nó có đuôi 
thuộc tập N. Do tập N có 7 chữ số, trong khi tập đầy đủ các đuôi là 10, vì vậy nếu các đuôi xuất hiện đều nhau thì số 
giá trị khả biến xấp xỉ bằng 70% tổng số giá trị. Nhƣ vậy có thể thấy khả năng nhúng tin của phƣơng pháp đề xuất bằng 
70% số giá trị của các thuộc tính kiểu số thực trong cơ sở dữ liệu, và có thể biểu diễn theo công thức sau: 
 IV. LƯỢC ĐỒ THỦY VÂN THUẬN NGHỊCH DỄ VỠ KHÓA CÔNG KHAI 
 Dựa vào phƣơng pháp đề xuất ở trên chúng tôi xây dựng một lƣợc đồ thủy vân thuận nghịch dễ vỡ khóa công 
 khai áp dụng cho việc xác thực tính toàn vẹn của cơ sở dữ liệu nhƣ sau: 
 Giả sử cơ sở dữ liệu quan hệ có bảng R=R(P, , ,... , , ,... ) trong đó P là thuộc tính khóa là 
 các thuộc tính số thực, là các thuộc tính kiểu khác. Dữ liệu thủy vân đƣợc nhúng vào phần phân của giá trị các 
 thuộc tính kiểu số thực , ,... . 
A. Thuật toán nhúng thủy vân 
 Thuật toán tạo và nhúng dấu thủy vân trên cơ sở dữ liệu gốc R để đƣợc cơ sở dữ liệu thủy vân R thực hiện 
theo sơ đồ sau: 
 Khóa bí mật K1 
 Cơ sở dữ Hàm băm mã đại Mã hóa Dấu thủy Nhúng tin Cơ sở dữ liệu 
 liệu gốc R SHA2 diện HR RSA vân W thuận nghịch thủy vân R’ 
 Hình 1. Sơ đồ nhúng thủy vân thuận nghịch dễ vỡ khóa công khai cho cơ sở dữ liệu 
 Trên Hình 1, thuật toán sử dụng hàm băm SHA2-348 (ký hiệu SHA2) để xác định mã đại diện cho cơ sở dữ 
liệu R. Khi đó, mã đại diện R có độ dài 348 bít và đƣợc mã hóa bằng hệ mật mã RSA thông qua khóa bí mật 1 để 
nhận đƣợc dấu thủy vân 𝑊. Dấu thủy vân 𝑊 đƣợc nhúng vào cơ sở dữ liệu gốc bằng thuật toán đề xuất để nhận đƣợc 
cơ sở dữ liệu thủy vân R’. Cơ sở dữ liệu thủy vân đƣợc dùng để trao đổi trên các kênh truyền công khai. 
 Chi tiết thuật toán đƣợc thể hiện qua các bƣớc sau: 
 Đầu vào là cơ sở dữ liệu gốc R 
Lê Quang Hòa, Đỗ Văn Tuấn, Nguyễn Huy Đức, Phạm Văn Ất 403 
 Đầu ra là cơ sở dữ liệu thủy vân R’ 
 Bƣớc 1: Xác định mã đại diện HR 
 HR=SHA2(R) 
 Bƣớc 2: Mã hóa HR bằng mật mã RSA dùng khóa bí mật K1 
 W=MaHoaRSA(HR, K1) 
 Bƣớc 3: Nhúng W vào cơ sở dữ liệu R theo thuật toán III.C.1 đƣợc cơ sở dữ liệu thủy vân R’ 
B. Thuật toán xác thực tính toàn vẹn và khôi phục cơ sở dữ liệu gốc 
 Cơ sở dữ liệu thủy vân R’ đƣợc chuyển đến ngƣời nhận qua môi trƣờng công khai và có thể bị biến đổi thành 
R*. Do đó, ngƣời nhận có đƣợc R* và cần xác minh xem đây có đúng là cơ sở dữ liệu thủy vân R’ hay không. Thuật 
toán xác thực đƣợc mô tả theo sơ đồ dƣới đây: 
 Dấu thủy Giải mã mã đại 
 vân W* RSA diện HR* 
 Cơ sở dữ liệu cần Trích dấu thủy vân và So sánh 0/1 
 xác minh R* khôi phục cơ sở dữ liệu 
 Hàm băm 
 Cơ sở dữ liệu mã đại 
 SHA2 
 khôi phục ̃ diện ̃ 
 Hình 2. Sơ đồ xác thực tính toàn vẹn thủy vân thuận nghịch dễ vỡ khóa công khai cho cơ sở dữ liệu 
 Trên hình 2 đầu tiên trích dấu thủy vân W* và khôi phục cơ sở dữ liệu ̃ từ R* bằng thuật toán đề xuất. Dấu thủy 
vân đƣợc giải mã RSA với khóa công khai K2 để nhận đƣợc mã đại diện HR*. Mặt khác, từ cơ sở dữ liệu vừa khôi phục 
sử dụng hàm băm SHA2 để lấy mã đại diện ̃ . Ta so sánh ̃ và HR* nếu chúng giống nhau kết luận R’* là cơ sở dữ 
liệu thủy vân và R* chính là cơ sở dữ liệu gốc. Ngƣợc lại kết luận cơ sở dữ liệu R’ đã bị tấn công trên đƣờng truyền. 
 Chi tiết thuật toán đƣợc thể hiện qua các bƣớc sau: 
 Đầu vào cơ sở dữ liệu cần xác thực R* 
 Đầu ra là kết quả xác thực xem R* có đúng là R’ hay không. Nếu đúng thì khôi phục cơ sở dữ liệu gốc R. 
 Bƣớc 1: Trích dấu thủy vân W* và khôi phục cơ sở dữ liệu ̃ từ R* 
 Bƣớc 2: Xác định mã đại diện theo hai cách 
 HR*=GiaiMaRSA(W*,K2) 
 ̃ =SHA2(R*) 
 Bƣớc 3: Xác thực tính toàn vẹn 
 Nếu ̃ =HR* thì dữ liệu toàn vẹn, có nghĩa là R*=R’ và ̃ =R 
 Ngƣợc lại dữ liệu không toàn vẹn, cơ sở dữ liệu đã bị tấn công(R* R’). 
C. Về tính đúng đắn của mô hình đề xuất 
 Do dấu thủy vân là đại diện của toàn bộ cơ sở dữ liệu và đƣợc xác định bởi hàm băm nên chỉ cần một sự thay 
đổi nhỏ dù chỉ một giá trị thuộc tính của bản ghi nào đó thì mã đại diện cũng bị biến đổi (tính chất của hàm băm). Vì 
vậy, mô hình thủy vân đề xuất có khả năng phát hiện mọi sự tấn công trái phép trên cơ sở dữ liệu đã thủy vân. Điều này 
phù hợp với kết quả thực nghiệm. 
 V. THỬ NGHIỆM 
 Để thử nghiệm khả năng phát hiện các dạng tấn công lên cơ sở dữ liệu thủy vân R’, chúng tôi sử dụng cơ sở dữ 
liệu gốc R có một bảng dữ liệu gồm bốn thuộc tính thực và 5000 bản ghi. Sau mỗi lần tấn công, thuật toán tính các giá 
trị đại diện HR* và ̃ , chúng đều là các dãy 384 bít. Để so sánh sự khác nhau giữa HR* và ̃ , chúng tôi sử dụng độ 
sai khác bình phƣơng trung bình: 
 ∑ ̃ 
 ̃ 
 Nếu ( ̃ ) thì có thể kết luận R’ không bị tấn công (R*=R’), trái lại thì kết luận bị tấn công 
(R* R’). 
 Kết quả thử nghiệm trình bày trong bảng dƣới đây cho thấy mọi sự thay đổi dù nhỏ đối với cơ sở dữ liệu thủy 
vân đều đƣợc phát hiện. 
404 MỘT LƢỢC ĐỒ THỦY VÂN THUẬN NGHỊCH KHÓA CÔNG KHAI CHO CƠ SỞ DỮ LIỆU DỰA TRÊN KỸ THUẬT... 
 Bảng 2. Thử nghiệm sự khác nhau giữa HR* và ̃ 
 TT Các phép tấn công ̃ 
 1 Sửa 1 bản ghi 0.486979 
 2 Sửa 5 bản ghi 0.458333 
 3 Sửa 10 bản ghi 0.515625 
 4 Sửa 15 bản ghi 0.486979 
 5 Thêm 1 bản ghi 0.492186 
 6 Thêm 5 bản ghi 0.518229 
 7 Thêm 10 bản ghi 0.476563 
 8 Xóa 1 bản ghi 0.473958 
 9 Xóa 5 bản ghi 0.481771 
 10 Xóa 10 bản ghi 0.481771 
 VI. KẾT LUẬN 
 Dựa theo ý tƣởng mở rộng hiệu trên phần phân của Farfura [10] và bằng cách áp dụng bản đồ định vị các vị trí 
khả nhúng, chúng tôi đã đề xuất một phƣơng pháp thủy vân thuận nghịch cho cơ sở dữ liệu có các thuộc tính kiểu thực. 
Tính đúng đắn của phƣơng pháp đã đƣợc chứng minh bằng các phân tích lý thuyết. Phƣơng pháp này có khả năng 
nhúng khá cao, bằng khoảng 70% số giá trị của thuộc tính kiểu số thực trong cơ sở dữ liệu. 
 Sử dụng phƣơng pháp để xuất, kết hợp hàm băm và một hệ mật mã khóa công khai, chúng tôi đã xây dựng một 
lƣợc đồ thủy vân thuận nghịch cho cơ sở dữ liệu. Lƣợc đồ này có tính dễ vỡ, có khả năng phát hiện mọi sự thay đổi dù 
nhỏ trên cơ sở dữ liệu thủy vân đƣợc gửi trên mạng. Do đó ngƣời nhận có thể kiểm chứng tính toàn vẹn của cơ sở dữ liệu 
mình nhận đƣợc. Trong trƣờng hợp toàn vẹn ngƣời nhận có thể khôi phục cơ sở dữ liệu gốc từ cơ sở dữ liệu thủy vân. 
 TÀI LIỆU THAM KHẢO 
[1] A.Khan, A.Siddiqua, S.Munib, and S.A.Malik, “A Recent Survey of Reversible Watermarking Techniques”, Information 
 Sciences, 2014, pp.251-272. 
[2] A.M.Alattar, “Reversible Watermarking Using the Difference Expansion of A Generalized Integer Transform”, IEEE 
 Transactions on Image Processing, 2004, Vol.18, pp.1147-1156. 
[3] C.C. Lin, and F.F. Shiu, “DTC-based Reversible Data Hiding Scheme”, Journal of software, 2010, Vol.5, NO.2, pp.214-224. 
[4] C.C.Chang, C.C.Lin, C.S.Tseng, and W.L.Tai, “Reversible hiding in DCT-based compressed images”, Information Sciences, 
 July 2007, Vol. 177, Issue 13, pp. 2768-2786. 
[5] C.C.Lee, H.C.Wu, C.S.Tsai, and Y.P.Chu, “Adaptive lossless steganographic scheme with centralized difference expansion”, 
 Patterm Recognition, 2008, pp.2097-2106. 
[6] C.C.Lin, W.L.Tai, and C.C.Chang, “Multilevel reversible data hiding based on histogram modification of difference images”, 
 Pattern Recognition 41, 2008, pp.3582-3591. 
[7] D.Coltuc and J-M.Chassery, “Very Fast Watermarking by Reversible Contrast Mapping”, IEEE Signal processing letters, 2007, 
 Vol. 14, No. 4, pp.255-258. 
[8] Đỗ Văn Tuấn, Nguyễn Kim Sao, Nguyễn Thanh Toàn, Phạm Văn Ất (2014) “Một sơ đồ nhúng tin thuận nghịch mới trên ảnh 
 JPEG”. Chuyên san Các công trình nghiên cứu, phát triển và ứng dụng Công nghệ Thông tin và Truyền thông, Tạp chí Công 
 nghệ Thông tin và Truyền thông, tháng 12/2014, tr. 41-52. 
[9] Đỗ Văn Tuấn, Trần Đăng Hiên, Phạm Đức Long, Phạm Văn Ất (2015) “Một lược đồ thủy vân thuận nghịch mới sử dụng mở 
 rộng hiệu đối với các véc-tơ điểm ảnh”. Chuyên san Công nghệ thông tin và Truyền thông, Tạp chí Khoa học và Kỹ thuật, Học 
 viện Kỹ thuật Quân sự, tháng 4/2015, tr. 17-31. 
[10] Farfoura, Mahmoud E., et al. "A blind reversible method for watermarking relational databases based on a time-stamping 
 protocol." Expert Systems with Applications 39.3 (2012): 3185-3196. 
[11] G. Gupta, J. Pieprzyk. “Reversible and blind database watermarking using difference expansion,” Proceedings of eForensics, 
 Jan. 2008, pp. 1–6. 
[12] G.Xuan, C.Yang, Y.Zhen, Y.Q.Shi, and S.Ni, “Reversible data hiding using integer wavelet transform and companding 
 technique”, Proc. IWDW, 2004, pp.115-124. 
[13] H. Khataeimaragheh, H. Rashidi (2010) “A Novel Watermarking Scheme for Detecting and Recovering Distortions in 
 Database Tables”. International Journal of Database Management Systems, Vol.2, No.3, August 2010, pp.1-11. 
[14] J.Tian, “Reversible data embedding using a difference expansion”, IEEE Trans. Circuits Syst. Video Technol, 2003, pp. 890–
 896. 
[15] K.Y. Mohammad, and A.J.Ahmed, “Reversible Watermarking Using Modifiled Difference Expansion”, International Journal 
 of Computing & Information Sciences, 2006, Vol.4, No.3, pp.134-142. 
[16] Li.Y, Swarup.V, Jajodia.S., (December 2003). “A robust watermarking scheme for relational data”, in Proc. The 13th 
 Workshop on Information Technology and Engineering, pp 195–200. 
[17] Li.Y, Swarup.V, Jajodia.S., (October 2003). “Constructing a virtual primary key for fingerprinting relational data”. ACM 
 Workshop on Digital Rights Management, pp 133–141. 
Lê Quang Hòa, Đỗ Văn Tuấn, Nguyễn Huy Đức, Phạm Văn Ất 405 
[18] M.Goljan, J.J.Fridrich, and R.Du, “Distortion-free data embedding for images”, 4th Information Hiding Workshop, LNCS, 
 2001, Vol.2137, pp. 27– 41. 
[19] M.Khodaei, and K.Faez, “Reversible Data Hiding By Using Modified Difference Expansion”, 2nd International Confference 
 on Signal Processing Systems, 2010, pp.31-34. 
[20] M.Nosrati, R. Karimi, and M. Hariri, “Reversible Data Hiding, Principles, Techniques, and Recent Studies”, Journal World 
 Applied Programming, 2012, pp.349-353. 
[21] R. Agrawal, J. Kiernan (2002) “Watermarking Relational Databases”, Proceedings of the 28th VLDB Conference, Hong Kong, 
 China, 2002. 
[22] W.Zhang, B.Chen, and N.Yu, “Improving Various Reversible Data Hiding Schemes Via Optimal Codes for Binary Covers”, 
 IEEE Transaction on Image Processing, June 2012, pp. 2991 – 3003. 
 A PUBLIC REVESIBLE WATERMAKING SCHEME FOR DATABASE 
 USING EXTENDING REAL ATTRIBUTES 
 Le Quang Hoa, Do Van Tuan, Nguyen Huy Duc, Pham Van At 
ABSTRACT— Watermaking is considered a useful tool to protect the database on the unsafe exchange environment. The traditional 
watermaking scheme only allows get watwermark without the ability to restore the database. Therefore, the recipient does not get 
original data but merely an approximation. To overcome this disadvantage, recently there exists schemes that be able to restore the 
original data, called the reversible watermaking schemes. Difference expansion is considered an effective technique for building 
reversible watermaking scheme, however it has the drawback to make the data change largely. Fafoura and et.al recently proposed 
using difference expansion on fraction part of real attributes, thereby reducing the change and improve the quality of watermaking. 
However by the theoretical analysis and testing, we pointed out in a number of cases this scheme can not extract the watermark as 
well as restore the original data correctly. In this paper we propose a solution to overcome the drawbacks mentioned above by 
using a location map to distinguish cases where the method can embed by extending fraction part and the case does not allow 
embedding. Then based on this new information embedding method, we propose a public key fragile reversible watermaking scheme 
on the relational database. This scheme has the advantage that the receiver easily check the integrity of the watermaking database 
and get the correct restoring the original database. So the recipient does not have to use approximate database (watermaking), but 
can use the original database.