Số hóa bởi Trung tâm Học liệu
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
HOÀNG THỊ THÚY DIỆU PHƢƠNG PHÁP THỦY VÂN DỄ VỠ
KHÓA CÔNG KHAI ỨNG DỤNG TRONG
BÀI TOÁN CHỐNG GIẢ MẠO VĂN BẰNG

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Thái Nguyên - 2014


suốt quá trình hoàn thành luận văn.
Và cuối cùng tôi xin gửi lời cảm ơn tới các đồng nghiệp, gia đình và bạn
bè những ngƣời đã ủng hộ, động viên tạo mọi điều kiện giúp đỡ để tôi có
đƣợc kết quả nhƣ ngày hôm nay.

Thái Nguyên, tháng 7 năm 2014
Học viên Hoàng Thị Thuý Diệu

Số hóa bởi Trung tâm Học liệu

MỤC LỤC

TRANG PHỤ BÌA……………………………………………………………i
LỜI CAM ĐOAN ii
LỜI CẢM ƠN iii
MỤC LỤC iv
DANH MỤC CÁC BẢNG vii
DANH MỤC CÁC HÌNH viii
MỞ ĐẦU 1
Chƣơng 1 3
TỔNG QUAN VỀ CÁC KỸ THUẬT GIẤU TIN 3
1.1. Khái niệm giấu tin 3
1.2. Lịch sử giấu tin 4
1.3. Phân loại các kỹ thuật giấu tin 6
1.4. Ứng dụng của kỹ thuật giấu tin 6
1.5. Một số hƣớng tiếp cận giấu tin trong ảnh 8
1.5.1. Giấu tin trên miền không gian ảnh 8

2.3.2. Đặc tính của hàm băm 31
2.3.3. Tính chất của hàm băm 32
2.3.4. Một số hàm băm phổ biến 33
2.3.5. Tiêu chuẩn của một hàm băm tốt 35
2.3.6. Ứng dụng của hàm băm 36
2.4. Hệ mật mã khóa công khai 36
2.4.1. Mã khóa công khai 37
2.4.2. Sơ đồ mã khóa công khai 37
2.4.3. Các đặc trƣng của khóa công khai 38
2.4.4. Ứng dụng khóa công khai 38

Số hóa bởi Trung tâm Học liệu

2.4.5. Tính an toàn của các sơ đồ khóa công khai 39
2.5. Hệ mã hóa RSA 39
2.5.1. Tạo khóa cho RSA 40
2.5.2. Sử dụng RSA 40
2.5.3. Ví dụ RSA 40
2.5.4. Sơ đồ chữ ký số RSA 41
2.6. Quản lý và phân phối khóa 42
2.7. Lƣợc đồ thủy vân dễ vỡ khóa công khai trên ảnh nhị phân 43
2.7.1. Thuật toán nhúng dấu thủy vân 44
2.7.2. Thuật toán xác thực tính toàn vẹn 44
2.7.3. Tấn công tính chẵn lẻ 45
2.8. Lƣợc đồ thủy vân dễ vỡ khóa công khai trên ảnh mầu 46
2.8.1. Nhúng tin trên ảnh mầu bằng kỹ thuật chèn bit thấp 46
2.8.2. Thuật toán nhúng thủy vân 48
2.8.3. Thuật toán xác thực 49
Chƣơng 3 51
ỨNG DỤNG THỦY VÂN DỄ VỠ KHOÁ CÔNG KHAI TRONG 51

Hình 1.8. Thí dụ minh hoạ trƣờng hợp thay đổi hai bit 25
Hình 2.1. Mô hình thủy vân số 29
Hình 2.2. Phân loại thủy vân theo mục đích ứng dụng 30
Hình 2.3. Sơ đồ mã khóa công khai 38
Hình 2.4. Mô hình thuật toán nhúng thủy vân 44
Hình 2.5. Mô hình xác thực tính toàn vẹn 45
Hình 3.1. Sơ đồ thủy vân ảnh bằng 52
Hình 3.2. Sơ đồ xác thực và định vị vùng giả mạo 53
Hình 3.3. Ảnh bằng gốc Error! Bookmark not defined.
Hình 3.4. Ảnh bằng thủy vân 55
Hình 3.5 Ảnh bằng giả 56
Hình 3.6. Ảnh định vị vùng giả mạo 57

Số hóa bởi Trung tâm Học liệu

1
MỞ ĐẦU

Một trong những thành tựu quan trọng của những thập niên cuối thế kỷ
XX, đầu thế kỷ XXI là sự ra đời, phát triển của mạng Internet. Mọi ngƣời đều
có thể kết nối vào Internet để tìm kiếm thông tin một cách dễ dàng thông qua
nhà cung cấp dịch vụ Internet. Ngƣời dùng có thể đọc thông tin mới nhất, tra
cứu các thƣ viên số, tìm thông tin lĩnh vực mình quan tâm. Bên cạnh đó, các
nhà cung cấp sản phẩm cũng sẵn sàng cung cấp dữ liệu của mình cho ngƣời
dùng thông qua mạng.
Tuy nhiên việc phân phối một cách phổ biến các tài nguyên trên mạng
hiện nay luôn gặp phải vấn nạn sao chép và sử dụng không hợp pháp. Kỹ
thuật thủy vân hiện đang đƣợc xem là một trong những giải pháp quan trọng
trong việc bảo vệ bản quyền và xác thực tính toàn vẹn của dữ liệu số.
Theo mục đích sử dụng của lƣợc đồ thủy vân đƣợc chia thành hai nhóm

Học viên thực hiện Hoàng Thị Thúy Diệu

Số hóa bởi Trung tâm Học liệu

3
Chƣơng 1
TỔNG QUAN VỀ CÁC KỸ THUẬT GIẤU TIN

Chương này trình bày một số khái niệm và phân tích khả năng ứng dụng
của kỹ thuật giấu tin. Ngoài ra, trong Chương còn trình bày ba thuật toán giấu tin
trên ảnh nhị phân Wu-Lee[8], CPT[6] và THA [7] thường được đề cập trong các
tài liệu. Các thuật toán này là cơ sở để xây dựng lược đồ thủy vân dễ vỡ trình bày
trong Chương 2.
1.1. Khái niệm giấu tin
Giấu tin là một kỹ thuật giấu một lƣợng thông tin số nào đó vào một
đối tƣợng dữ liệu khác.
Kỹ thuật giấu tin nhằm hai mục đích: một là bảo mật cho dữ liệu đƣợc
đem giấu, hai là bảo vệ cho chính đối tƣợng đƣợc giấu tin ở trong. Hai mục
đích khác nhau này dẫn đến hai kỹ thuật chủ yếu của giấu tin. Hƣớng thứ nhất
là giấu tin mật, nhằm tập trung vào các kỹ thuật giấu tin sao cho ngƣời khác
khó phát hiện đƣợc đối tƣợng có chứa thông tin mật bên trong. Hƣớng thứ hai
là thủy vân số, hƣớng thủy vân số có miền ứng dụng lớn hơn nên đƣợc quan
tâm nghiên cứu nhiều hơn và thực tế đã có rất nhiều kỹ thuật đƣợc đề xuất.
Mô hình giấu tin và giải mã thông tin


5
đƣợc áp dụng để che giấu thông tin sử dụng trong chiến tranh. Về sau, rất
nhiều kỹ thuật giấu tin trên giấy đã đƣợc phát triển sử dụng các tia cực tím.
Giải pháp giấu thông tin mật vào các bức ảnh đƣợc khám phá và phát triển
đầu tiên vào những năm 1860, do nhiếp ảnh gia Dragon ngƣời Pháp thực hiện.
Ngày nay, giấu thông tin trong ảnh chiếm tỷ lệ lớn trong các chƣơng
trình ứng dụng, các phần mềm, hệ thống giấu tin trong dữ liệu đa phƣơng tiện
bởi lƣợng thông tin đƣợc trao đổi bằng ảnh là rất lớn. Hơn nữa, giấu thông tin
trong ảnh cũng đóng vai trò hết sức quan trọng trong hầu hết các ứng dụng
bảo vệ an toàn thông tin nhƣ: nhận 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 thông tin mật v.v. Vì
thế mà vấn đề này đã nhận đƣợc sự quan tâm rất lớn của các cá nhân, tổ chức,
trƣờng đại học và viện nghiên cứu trong và ngoài nƣớc.
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à mắt ngƣời không thể phát hiện đƣợc bên trong bức ảnh đó có chứa
thông tin gì. Và ngày nay, khi ảnh số đã đƣợc sử dụng phổ biến thì giấu thông
tin trong ảnh đã đem lại rất 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ụ nhƣ đối với các nƣớc phát triển chữ ký tay
đã đƣợc số hoá và đƣợc lƣu trữ giống nhƣ là 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. Thêm vào đó, lại có rất nhiều loại thông tin quan trọng cần
đƣợc bảo mật, chúng rất dễ bị lấy trộm và bị thay đổi bởi các phần mềm
chuyên dụng. Việc nhận 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 và 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, bởi sau khi giấu
thông tin thì chất lƣợng ảnh gần nhƣ không thay đổi, đặc biệt đối với ảnh màu
hay ảnh đa mức xám.

Số hóa bởi Trung tâm Học liệu

7
đối thủ mà thay vào đó các thuật toán quan tâm đến tính ẩn và tính an toàn đối
với dữ liệu cần giấu. Do đó, các thuật toán giấu tin có độ bảo mật cao sẽ đƣợc
sử dụng trong các ứng dụng giấu tin mật.
Bảo vệ bản quyền tác giả: Đây là ứng dụng cơ bản nhất của kỹ thuật
thủy vân số. Một thông tin nào đó mang ý nghĩa bản quyền đƣợc sở hữu bởi
tác giả gọi là thủy vân, thông tin này sẽ đƣợc nhúng vào trong các sản phẩm
multimedia, và đó là minh chứng cho bản quyền của tác giả nhằm bảo vệ các
sản phầm chống lại các hành vi lấy cắp hoặc làm nhái. Yêu cầu kỹ thuật đối
với ứng dụng này là thủy vân phải tồn tại bền vững cùng với sản phẩm, khi
muốn bỏ thủy 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: Một tập các thông tin sẽ đƣợc giấu trong dữ liệu
nguồn và thông tin sẽ đƣợc sử dụng để nhận biết xem dữ liệu nguồn có bị
thay đổi hay không. Với kiểu ứng dụng này các thủy vân nên đƣợc ẩn để tránh
đƣợc sự tò mò của đối phƣơng, hơn nữa việc làm giả các thủy vân hợp lệ hay
xuyên tạc thông tin nguồn cũng cần đƣợc 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. Yêu cầu chung đối với ứng dụng này là khả năng giấu thông tin
cao và thủy vân không cần bền vững.
Giấu vân tay hay dán nhãn: Thủy vân số 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 của một thông tin nào
đó. Ví dụ nhƣ các vân khác nhau sẽ đƣợc nhúng vào các bản sao 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
thì yêu cầu là đảm bảo độ an toàn cao cho các thủy vân tránh sự xoá giấu vết
trong khi phân phối.
Kiểm soát sao chép: Các thủy vân trong những trƣờng hợp này đƣợc
sử dụng để kiểm soát việc sao chép thông tin. Các thiết bị phát hiện ra thủy
vân thƣờng đƣợc gắn sẵn vào trong các hệ thống đọc/ghi. Ví dụ nhƣ hệ thống


thông quen thuộc.

Số hóa bởi Trung tâm Học liệu

9
Mỗi cách biến đổi sẽ có những thuận lợi riêng, tuỳ từng trƣờng hợp mà
chúng ta chọn phép biến đổi nào cho phù hợp. Sau khi khảo sát, biến đổi xong
các tín hiệu và hệ thống rời rạc trong miền các biến số mới này, nếu cần thiết
có thể dùng các biến đổi ngƣợc để đƣa chúng trở lại miền biến số độc lập.
Phƣơng pháp khảo sát gián tiếp sẽ làm đơn giản rất nhiều các công việc
gặp phải khi dùng phƣơng pháp khảo sát trực tiếp trong miền biến số độc lập
tự nhiên. Hệ thống rời rạc cần khảo sát chính là miền không gian các điểm
ảnh. Có một số phƣơng pháp biến đổi đƣợc sử dụng rất phổ biến nhƣ: Furier,
Cosine rời rạc (DCT), Wavelet rời rạc (DWT)… Đây là những phép biến đổi
đƣợc sử dụng nhiều trong các kỹ thuật xử lý ảnh và âm thanh. Trong giấu tin,
đặc biệt trong kỹ thuật thủy vân tiếp cận theo miền tần số, các phép biến đổi
từ miền biến số tự nhiên của ảnh sang miền tần số nhƣ biến đổi Furier, biến
đổi cosin rời rạc, Wavelet đƣợc sử dụng phổ biến.
1.6. Cấu trúc tệp ảnh bitmap
Tệp ảnh bitmap là một trong những định dạng ảnh thông dụng đƣợc hỗ
trợ bởi hầu hết các hệ điều hành và thiết bị điện tử. Theo [3], tệp ảnh bitmap
đƣợc chia thành 4 phần nhƣ sau:

Trong đó:
 Bitmap File Header gồm 14 byte
 Bitmap Info gồm 40 byte
 Color palette - Bảng màu (đối với ảnh 24 bít không có bảng mầu)
 Bitmap Data

Số hóa bởi Trung tâm Học liệu

Number of bytes in Bitmap Info
40
5 - 8
Width of bitmap
In pixels
9 - 12
Height of bitmap
In pixels
13 - 14
Number of color planes
1
15 - 16
Number of bits per pixels
1, 4, 8 hoặc 24
17 - 20
Type of compression

21 - 24
Size of image
In bytes
25 - 28
Horizontal resolution

29 - 32
Vertical resolution

33 - 36
Number of colors In color Palette
Ảnh 24 bít – 0
Ảnh 8 bít - nếu 0 thì

5
Blue color value
0 – 255
1
6
Green color value
0 – 255
1
7
Red color value
0 – 255
1
8
Reserved
0
1
9
… Ghi chú:
- Mỗi entry gồm 4 byte và chứa một mầu trong bảng mầu
- Ảnh 24 bít không có bảng mầu
1.6.4. Bitmap Data
 Với ảnh 8 mầu
Mỗi byte chứa chỉ số mầu (tính từ 0) của một điểm ảnh. Các điểm ảnh
đƣợc lƣu trữ trên file theo từng hàng từ dƣới lên trên. Các điểm ảnh mỗi hàng
đƣợc chứa từ trái sang phải.
 Với ảnh 24 mầu
Mỗi nhóm 3 byte biểu diễn mầu của một điểm ảnh (byte 1 – Red, byte


Với
Định nghĩa 1.3: Ma trận W kích thƣớc đƣợc gọi là ma trận trọng số
cấp r với nếu mọi W thoả mãn điều kiện:

Thí dụ minh hoạ về ma trận trọng số cấp 3 (r = 3) với ma trận W nhƣ sau:
362
174
765
231
W

Nhƣng với ma trận
1 3 2
5 6 7
W'
171
2 6 3
lại không phải là ma trận trọng số cấp 3 vì
trong ma trận W' không tồn tại phần tử (i,j) để W'
i,j
= 4, mà
3
4 1,2, ,2 1
,
vậy
'3
,
W | 1 4, 1 3 1,2, ,2 1
ij

 Tóm tắt thuật toán
Input:

Số hóa bởi Trung tâm Học liệu

14
là kích thƣớc của ma trận gồm m hàng và n cột, giá trị m, n đƣợc
giữ bí mật.
F
mxn
là ma trận nhị phân và là ma trận môi trƣờng để giấu tin.
K
mxn
là ma trận nhị phân khoá và giá trị của ma trận K phải đƣợc giữ bí
mật.
b là bit nhị phân cần giấu (b = 0 hoặc b = 1).
Output:
Nếu thuật toán thực hiện thành công, kết quả thu đƣợc là ma trận G đƣợc
biến đổi tối đa một phần tử từ ma trận F và G thoả mãn hai bất biến sau:
+ 0 < SUM(G K) < SUM(K) (1.1)
+ SUM(G K) mod 2 = b (1.2)
Theo đầu ra của thuật toán, khi nhận đƣợc G để kiểm tra ma trận G có
giấu thông tin hay không chúng ta sẽ cần kiểm tra G có thoả mãn bất biến
(1.1) hay không. Với bất biến (1.2) quá trình giải mã thông tin giấu trong ma
trận G có thể dễ dàng xác định đƣợc G chứa giá trị bit đã giấu bằng 0 hay
bằng 1 theo (1.3)
b =SUM(G K) mod 2 (1.3)
 Nội dung thuật toán
Bƣớc 1: đặt s = SUM(F K)
Bƣớc 2: if 0 < s <SUM(K) then

i,j
=1
- F
i,j
= NOT (F
i,j
)
- G = F
1.8.2. Phân tích thuật toán
Thuật toán sử dụng K nhằm làm tăng độ bảo mật cho thuật toán giấu tin.
Nếu trƣớc đây chỉ biết kích thƣớc khối là mxn thì đối phƣơng đã có thể dễ
dàng giải mã đƣợc tin mật thông qua ảnh chứa tin, nhƣng với thuật toán của
Wu-Lee ngoài giá trị m,n các thuật toán thám mã còn phải xác định giá trị cụ
thể của ma trận K. Do vậy, để tìm đƣợc ma trận khóa K khi đã biết m, n các
thuật toán thám mã phải duyệt trƣờng hợp khác nhau.
Theo định nghĩa phép toán , và bất biến (1.2) nên nội dung thuật toán
Wu-Lee sẽ biến đổi F thành G sao cho SUM(G K) cùng tính chẵn lẻ với b.
Do vậy, nếu b không cùng tính chẵn lẻ với SUM(G K) thì thuật toán sẽ
thực hiện đảo giá trị của phần tử F
i,j
ứng với K
i,j
= 1 để đạt đƣợc bất biến (1.2).
Nhƣ vậy, khoá K đƣợc xem nhƣ một mặt nạ, tạo ra khung nhìn cho thuật toán.
Điều kiện 0 <SUM(F K)< SUM(K) quy định, nếu mọi vị trí (i,j) của F
tại các vị trí K
i,j
= 1 mà F
i,j
đều bằng không hoặc đều bằng một thì không nên

G1 G2

0
1
0
1
0
1
Dữ liệu cần giấu: b
1
b
2
b
3
=011
0
0
0
1
0
1

1
0
1
1
0

0
0
1
0
1
0

0
1
0
1
1
0
0
1
0

0
0
0
0
1
1
1
0
1 0
0
0
0
1
0

F3 F4


2
vào F3. Trong trƣờng hợp này, ta thấy
SUM(F3 K) mod 2 = 1 = b
2
nên không cần biến đổi F3 và G3 bằng F3.
- Với F4, 0< SUM(F4 K) = 4 <SUM(K) nên thuật toán sẽ thực hiện
giấu bit b
3
= 1 vào khối F4 bằng cách biến đổi F4 thành G4 thoả mãn tính chất
(2) và (3). Do SUM(F4 K) = SUM(K) -1 nên chúng ta chọn ngẫu nhiên

Số hóa bởi Trung tâm Học liệu

17
phần tử (i,j) mà F4
(i,j)
= 1 mà K
i,j
= 1 và thay đổi F4
(i,j)
= 0. Giả sử ta chọn
phần tử (3,3) kết quả sẽ thu đƣợc nhƣ G4.
1.8.4. Một số nhận xét về thuật toán Wu-Lee
Thứ nhất: ảnh môi trƣờng để thực hiện giấu thông tin cũng phải đƣợc
chọn kỹ càng. Nếu một ảnh có quá nhiều điểm trắng (hoặc đen) thì tỉ lệ bit
giấu đƣợc sẽ rất thấp.
Thứ hai: Vì trong mỗi ma trận điểm ảnh F thuật toán chỉ biến đổi tối đa
là một phần tử (từ 1 thành 0 hoặc từ 0 thành 1), do vậy nếu chọn m, n đủ lớn
thì sự thay đổi này khó có thể nhận biết bằng mắt thƣờng nhƣng khả năng
giấu của thuật toán lại giảm đáng kể.
0
1
0
1
F=
1
0
1
0

K=
1
1
0
0

b =
0

0
1
1
0