ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
š&›

Hoàng Thu Phương

MẬT MÃ TRỰC QUAN

Chuyên ngành: Bảo Đảm Toán Học Cho Máy Tính và Hệ Thống Tính Toán
Mã số: 60.46.35

LUẬN VĂN THẠC SĨ KHOA HỌC Người hướng dẫn khoa học: TS. Tôn Quốc Bình


1.1. Động lực nghiên cứu 8
1.2 Câu hỏi đặt ra và mục tiêu nghiên cứu 10

1.3. Dự kiến đóng góp 11

1.4. Quá trình nghiên cứu và cách tổ chức 12

CHƯƠNG 2. MẬT MÃ TRỰC QUAN 14
2.1. Lược đồ chia sẻ bí mật 14

2.1.1 Lược đồ chia sẻ bí mật là gì? 14

2.1.2. Lược đồ chia sẻ bí mật hoàn hảo 15

2.2 Mật mã trực quan 15
2.3. Mật mã trực quan dựa trên điểm ảnh 16

2.3.2. Mô hình mật mã trực quan 16

2.3.3. Cách giải hiệu quả đối với k và n nhỏ 19

2.3.4. Lược đồ tổng quát ngưỡng (k, k) 22

2.3.5. Lược đồ tổng quát ngưỡng (k, n) 25

2.3.6. Kỹ thuật mật mã trực quan không làm mở rộng điểm ảnh 29

2.4. Mật mã trực quan dựa trên phân đoạn 31

2.4.1. Giới thiệu 31


4.1. Quy trình thực hiện của hệ thống con mật mã trực quan 54

4.1.1. Giới thiệu về các phân đoạn hiển thị 54

4.1.2. Thuật toán mật mã trực quan dựa trên các phân đoạn 61

4.1.3. Chương trình thử nghiệm 63

4.2. Độ an toàn của thuật toán trong hệ thống con mật mã trực quan 66

KẾT LUẬN………………………………………………………………………68

TÀI LIỆU THAM KHẢO 70

PHỤ LỤC……………………………………………………………………… 71Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 5 -
MỞ ĐẦU

Ngày nay Internet đã có mặt ở hầu hết các lĩnh của đời sống xã hội, thông qua
Internet chúng ta có thể tìm kiếm, chia sẻ thông tin, gửi nhận thư điện tử, quảng cáo
các sản phẩm, dịch vụ, xử lý các giao dịch thương mại - một ứng dụng trên Internet mà
chúng ta thường gọi là thương mại điện tử bên cạnh lợi ích mà Internet nói chung và
ứng dụng thương mại điện tử nói riêng đem lại thì việc hiểu và đảm bảo an toàn cho
thông tin được trao đổi qua Internet và ứng dụng thương mại điện tử cũng là một yêu
cầu không chỉ đối với người quản trị hệ thống mà đối với ngay cả đối tượng là những

thống giao dịch thẻ tín dụng trên Internet.
Đây cũng chính là lí do tôi đi vào tìm hiểu và thực hiện luận văn với đề tài “Mật
mã trực quan” một khía cạnh của khoa học mật mã đã có rất nhiều ứng dụng quan
trọng trong việc xác thực thẻ tín dụng, đảm bảo an toàn cho hệ thống giao dịch thẻ tín
dụng qua mạng Internet.
Nội dung chính trình bày trong luận văn này gồm những mục chính sau đây:
Chương 1: Giới thiệu chung, phần này nhằm nêu rõ tính cần thiết của đề tài,
động lực nghiên cứu của đề tài.
Chương 2: Mật mã trực quan, giới thiệu về mật mã trực quan, tìm hiểu các
lược đồ, cũng như cách mã hóa với ảnh nhị phân, giới thiệu một kỹ thuật mã không
làm mở rộng điểm ảnh, giới thiệu về mật mã trực quan dựa trên các phân đoạn.
Chương 3: Ứng dụng của mật mã trực quan trong việc xác thực thẻ tín
dụng. Phần này giới thiệu về tình hình sử dụng thẻ tín dụng hiện nay, trình bày hai cơ
chế bảo mật của thẻ tín dụng đó là SSL, SET với những hạn chế của nó. Mật khẩu
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 7 -
dùng một lần. Ứng dụng của mật mã trực quan trong hệ thống xác thực thẻ tín dụng, đề
xuất kiến trúc hệ thống, quy trình thực hiện của hệ thống.
Chương 4: Chương trình demo thử nghiệm. Giới thiệu chương trình chi tiết,
giới thiệu về bảy và mười bốn phân đoạn hiển thị, quy trình thực hiện của hệ thống con
mật mã trực quan dựa trên các phân đoạn hiển thị, giao diện chính của chương trình.
Phân tích độ an toàn và tính khả thi của hệ thống thử nghiệm.
Phần kết luận. Thảo luận một số vấn đề, tự đánh giá kết quả đạt được và hướng
nghiên cứu tiếp theo.
Vì hạn chế về thời gian tìm hiểu, nên bản luận văn này khó tránh khỏi những sai
sót khiếm khuyết, tôi rất mong được sự chỉ bảo góp ý của các thầy cô giáo và các bạn.
Tôi xin chân thành cảm ơn.
ví số - digital wallet) tại máy tính cá nhân của họ. SSL được thiết lập trong trình duyệt,
do đó không cần một phần mềm đặc biệt nào.
Tuy nhiên, SET không phổ biến nhanh như nhiều người mong đợi do tính phức
tạp, thời gian phản hồi chậm, và sự cần thiết phải cài đặt ví số ở máy tính của khách
hàng. Nhiều ngân hàng ảo và cửa hàng điện tử duy trì giao thức SSL, thậm chí một số
cửa hàng điện tử, như Wal-Mart Online, đi theo cả hai giao thức SSL và SET. Ngoài
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 9 -
ra, theo một cuộc khảo sát do Forrest Research thực hiện, chỉ có 1% kế hoạch kinh
doanh điện tử di chuyển sang SET.
Xuất phát từ thực tế hai phương thức trên còn có nhiều hạn chế là một động lực
thúc đẩy việc tìm ra một giải pháp mới nhằm tăng độ an toàn cho các giao dịch qua
mạng. Một ý tưởng được đưa ra đó là sử dụng mật mã trực quan để xác thực thẻ tín
dụng, đảm bảo an toàn cho hệ thống giao dịch thẻ tín dụng qua mạng Internet.
Mật mã trực quan là một kỹ thuật mật mã cho phép thông tin trực quan (hình
ảnh, văn bản, v.v ) được mã hóa theo cách sao cho sự giải mã có thể được thực hiện
bởi hệ thống trực quan con người, không cần nhờ đến máy tính. Mật mã trực quan phát
triển từ ý tưởng chia sẻ bí mật, một ảnh gốc có ý nghĩa được phân thành nhiều mảnh
hình ảnh vô nghĩa – đây là một phương thức truyền dữ liệu bí mật qua mạng. Khi
chúng ta muốn có hình ảnh ban đầu, ta phải xếp chồng những hình ảnh vô nghĩa đó
theo một ngưỡng nhất định để có thể đọc được ảnh gốc thông qua hệ thống trực quan
của con người, nguyên lý và chi tiết của mật mã trực quan sẽ được trình bày trong
chương 2 của bản luận văn này.
Từ các vấn đề đã đề cập đã đưa tới một số ý tưởng dựa trên việc không thể xác
thực được chủ thẻ (“cardholder”) khi sử dụng SSL cho thẻ tín dụng Internet. Việc thiết
lập một cơ chế nhằm kết hợp giữa điện thoại di động và thư điện tử với chức năng xác
thực của chúng và tính năng kiểm tra nhận dạng của mật mã trực quan để giải quyết
vấn đề phổ dụng của thẻ tín dụng. Cơ chế gốc của SSL vẫn được giữ nguyên nhưng
thêm vào trong quá trình hoạt động của SSL điện thoại di động và thư điện tử như là

ưu điểm của SSL và những mục tiêu nêu trên để nâng cao tính bảo mật của việc chuyển
giao mã xác thực và để đạt được mục đích xác thực định danh khi sử dụng thẻ tín dụng
Internet bằng cách sử dụng điện thoại di động và hòm thư cá nhân, tất cả những điều
đó đều có thể giải quyết những vấn đề sau đây:
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 11 -
- Cơ chế của SSL có thể không xác định được danh tính của chủ thẻ
- Chủ thẻ không thể biết được thẻ tín dụng của họ đã bị chiếm đoạt.
1.3. Dự kiến đóng góp
Với cơ chế SSL truyền thống, khi khách hàng thanh toán trực tuyến bằng cách
sử dụng thẻ tín dụng của họ, giao dịch sẽ phải được hoàn thành sau khi họ cung cấp số
thẻ với định danh của họ. Đúng là nó rất nhanh và thuận tiện, chủ thẻ không nghĩ tới
việc thương nhân (merchant) có bảo mật các thông tin của thẻ hay là không. Do vậy
mà người dùng có thể phải đền bù cho những hóa đơn thẻ tín dụng của họ khi nó bị
người khác chiếm đoạt giả mạo. Qua cơ chế tôi đề cập trong bản luận văn này, máy
điện thoại di động cá nhân và hòm thư điện tử có thể là phương pháp hai chiều để định
danh chủ thẻ và mã xác thực sẽ được nhận thông qua hai kênh này. Có ba mức yêu cầu
của mã xác thực luôn xảy ra trong mọi giao dịch. Nếu người dùng gửi sai mã xác thực
tới các website thương mại, nơi phát hành thẻ có thể dò được lỗi và thông báo cho
người bán đó về việc từ chối giao dịch. Mặt khác, nếu phát hiện một mã xác thực đúng,
giao dịch sẽ được thực hiện.
Đối với hệ thống con mật mã trực quan trong hệ thống đề xuất để nhằm mục
đích phân chia mã xác thực trước khi nó được gửi đi, tôi đưa ra ý tưởng biểu diễn mã
xác thực này dưới dạng các phân đoạn hiển thị mà cụ thể ở đây là bảy phân đoạn hiển
thị và đề xuất thuật toán để phân chia thành hai ảnh chia sẻ, hai ảnh chia sẻ này không
cho bất cứ thông tin nào, ta chỉ có được thông tin mật chỉ khi chúng được ghép lại với
nhau. Thuật toán này sẽ được trình bày chi tiết và cụ thể trong chương 4 của bản luận
văn này
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 13 -

Hình 1. Quá trình nghiên cứu.
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 14 -
CHƯƠNG 2. MẬT MÃ TRỰC QUAN
2.1. Lược đồ chia sẻ bí mật
2.1.1 Lược đồ chia sẻ bí mật là gì?
Lược đồ chia sẻ bí mật được phát minh độc lập bởi Adi Shamir và Georger
Bakley vào năm 1979. Động cơ chia sẻ bí mật là quản lý khóa an toàn. Trong một vài
tình huống, thường có một khóa bí mật cung cấp truy cập cho nhiều tập tin quan trọng.
Nếu khóa như vậy bị mất thì tất cả các tập tin quan trọng trở nên không truy cập được.
Ý tưởng cơ bản của chia sẻ bí mật là chia khóa bí mật thành các phần và phân phối
những phần này cho những người khác nhau sao cho tập con nhất định của những
người này có thể tụ họp với nhau để phục hồi khóa.
Mô hình chung cho chia sẻ bí mật được gọi là lược đồ m trong số n (hoặc lược
đồ ngưỡng - (m, n)) với m, n nguyên. Trong lược đồ, có một người chia và n người
tham gia. Người chia sẽ chia bí mật thành n phần và cho mỗi người một phần để cho
tập hợp m phần lại sẽ khôi phục được bí mật, nhưng bất kỳ m-1 phần nào cũng không
tiết lộ chút thông tin bí mật. Các phần chia thường được gọi là các bóng. Sự lựa chọn
khác nhau cho các giá trị m và n phản ánh sự cần bằng giữa an toàn và tin cậy.
Định nghĩa theo toán học:
Cho tập hợp P={1, ,n}, các phần tử là những người tham gia.
2P biểu thị tập tất cả các tập con của P.
Q: những phần tử của tập đủ điều kiện
F: những phần tử của tập không đủ điều kiện.
Q
⊆
2P và F

k
từ GF(q).
2 1
1 2 1
( )
k
k
F x s m x m x m x
−
−
= + × + × + + ×

Một cách tự do lựa chọn khác biệt
(1 )
i
x i n
≤ ≤
. Đưa cho người i phần bí mật
( , ( ))
i i
x F x
với mọi
(1 )
i n
≤ ≤
.
2.2 Mật mã trực quan
Mật mã trực quan là một kỹ thuật mật mã cho phép thông tin trực quan (hình
ảnh, văn bản, v.v ) được mã hóa theo cách sao cho sự giải mã có thể được thực hiện
bởi hệ thống trực quan con người, không cần nhờ đến máy tính.

TH2:

Hình 3. Các trường hợp xếp chồng điểm ảnh
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 17 -
Ta quy ước mầu trắng tương ứng với 0, đen với 1:
Cấu trúc kết quả có thể được mô tả bởi một ma trận đại số Boole m×n S=[s
ij
], s-
ij
=1 nếu điểm con thứ j trong phần thứ i là màu đen. Khi các phần i
1
,i
2
, i
r
được xếp
chồng với nhau sao cho các điểm con trùng khớp, chúng ta nhìn thấy một phần kết hợp
mà những điểm con màu đen là kết quả phép boole “or” của các hàng i
1
,i
2
, i
r
trong S.
Mức xám của phần kết hợp trên tỉ lệ với trọng lượng Hamming H(V) phép “or” của m-
vector V. Mức xám này được giải thích bởi hệ thống trực quan của những người tham
gia như màu đen nếu H(V)≥d và màu trắng nếu H(V)<d-
α

1. Đối với bất kỳ S trong C
0
, “or” V của bất kì k của n dãy thoả mãn
H(V)≤d-
α
m.
2. Đối với bất kỳ S trong C
1
, “or” V của bất kì k của n dãy thoả mãn
H(V)≥d.
3. Đối với bất kì tập con {i
1
, i
2
,. .i
q
} of {1,2,…n} với q<k, hai tập hợp
của ma trận q×m D
t
với t
∈
{0,1} có được bằng cách giới hạn mỗi ma
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 18 -
trận n×m trong C
t
(t=0,1) đến các dãy i
1
,i

và C
1
(chúng không cần phải có kích thước bằng
nhau, nhưng trong tất cả các phép dựng của chúng ta thì chúng bằng
nhau). log(r) thể hiện số bit ngẫu nhiên cần thiết để tạo ra các phần và
không ảnh hưởng gì đến chất lượng của hình ảnh.
Kết quả: Chúng ta có một số các phép dựng đối với các giá trị cụ thể của k và n.
Đối với k tổng quát, chúng ta có phép dựng đối với ngưỡng k với m=2k-1 và
k 1
1
2
α
−
=

và chúng ta có sự chứng minh đối với tính tối ưu của lược đồ này. Đối với k và n tổng
quát, chúng ta có phép dựng với
( )
.2
O klogk
m log n=
và
(k)
1
2
α
Ω
=
.


 
 
 
 
 
}
Bất cứ một phần riêng lẻ nào trong C
0
hoặc C
1
là sự lựa chọn ngẫu nhiên của
một điểm ảnh con màu đen và n-1 điểm ảnh con màu trắng. Bất kì hai phần của một
điểm ảnh màu trắng có trọng lượng Hamming được kết hợp bằng 1, trong khi cứ hai
phần của một điểm ảnh màu trắng có trọng lượng Hamming được kết hợp bằng 2 trông
tối hơn. Hiệu số trực quan giữa hai trường hợp này trở nên rõ ràng hơn khi chúng ta
xếp chồng thêm các trong suốt.
Vấn đề ban đầu của mật mã trực quan là trường hợp đặc biệt của ngưỡng 2 chia
sẻ bí mật trực quan. Nó có thể được giải quyết cùng với hai điểm ảnh con trong mỗi
điểm ảnh, nhưng trong thực tế, điều này có thể bóp méo khuôn dạng của ảnh gốc.
Chính vì thế người ta gợi ý nên sử dụng 4 điểm ảnh con được sắp xếp trong một dãy
2×2 mà mỗi phần có một trong số các dạng có thể nhìn thấy được trong hình trên. Các
dãy bổ sung màu trắng từ danh sách dưới đây. Bất kì một phần riêng biệt là sự lựa chọn
ngẫu nhiên của hai điểm ảnh đen và hai đểm ảnh màu trắng mà trông có màu xám
trung bình. Khi hai phần được xếp chồng lên nhau, kết quả là hoặc là màu xám trung
bình (thể hiện màu trắng) hoặc màu đen toàn bộ (thể hiện màu đen).
Trường hợp tiếp theo là ngưỡng 3 chia sẻ bí mật trực quan, được giải bằng sơ đồ
sau đây:
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 20 -

là chính xác 6 dãy 2×2
của các điểm ảnh con từ sơ đồ 1. Mỗi ma trận hoặc ở C
0
hoặc C
1
có chứa một phần
hình nằm ngang, một phần nằm dọc và một phần hình chéo. Mỗi phần chứa đựng một
sự lựa chọn ngẫu nhiên của hai điểm ảnh màu đen, và bất kì 1 cặp phần nào đến từ một
trong các ma trận có chứa một sự lựa chọn ngẫu nhiên của một điểm ảnh con tổng quát
màu đen và hai điểm ảnh con màu đen riêng lẻ. Kết quả là, quá trình phân tích một
hoặc hai phần làm cho nó không thể phân biệt được giữa C
0
và C
1
. Tuy nhiên, một sự
chồng chéo của 3 trong suốt từ C
0
chỉ có ¾ màu đen. Trong khi đó, một sự chồng chéo
của 3 trong suốt từ C
1
màu đen toàn bộ.
Lược đồ dưới đây tổng quát 3 trong 3 lược đồ thành 3 trong n lược đồ đối với
bất kì n≥3. Gọi B là ma trận màu đen n×(n-2) chứa duy nhất 1, và gọi I là ma trận n×n
có chứa 1 hình chéo và 0 ở các phần khác. Gọi BI là ma trận n×(2n-2) thu được bằng
cách ghép B và I, và đặt c(BI) là Boolean bổ sung của ma trận BI. Sau đó:
C
0
={tất cả các ma trận có được bằng cách hoán vị các cột của c(BI)}
Mật mã trực quan Hoàng Thu Phương CH 07 – 09


1100
1100
1100
1100
1100
1100
 
 
 
 
 
 
 
 
 
}
C
1
={tất cả các ma trận có được bằng cách hoán vị các cột của
0101
1010
1100
0011
0110
1001
 
 
 
 
 

1
tương ứng với tập con thứ i, tức là, S
1
[i,j]=1 nếu nguyên
tố thứ j nằm trong tập con thứ i. S
0
là ma trận n×m mà mỗi hàng là 1
m/2
0
m/2
. C
0
và C
1

có được từ việc hoán vị tất cả các cột của S
0
và S
1
. Sự đối chiếu có được cách này là
1/m.

2.3.4. Lược đồ tổng quát ngưỡng (k, k)
Bây giờ chúng ta có thể miêu tả hai phép dựng tổng quát có thể giải quyết được
vấn đề chia sẻ bí mật của bất kì ngưỡng (k, k) phần tử nào bằng cách sử dụng các điểm
ảnh con 2
k
và 2
k-1
tương ứng. Sau đó chúng ta chứng minh rằng phép dựng hình thứ hai

1 0
k
k
J
−
=
. Gọi
1 1 1
1 2
, ,
k
J J J
là các véc tơ có chiều dài k trên GF[2] với
tính chất chúng độc lập đối với GF[2]. (Điều này có thể được coi như là số một của mật
mã Reed-Muller)
Mỗi danh sách miêu tả một ma trận k×2
k
với S
t
khi t
∈
{0,1}và các tập hợp C
0
và
C
1
có được bằng cách hoán vị các cột của ma trận tương ứng đối với các cách có thể.
Chúng ta có thể lập chỉ số các cột của S
t
bằng các véc tơ có chiều dài k trên GF[2]. Đối

!
Chứng minh: Để chỉ ra sự đối chiếu, chú ý rằng trong ma trận S
0
có hai cột mà
tất cả đều bằng 0; trong ví dụ đã cho, đây là những cột được lập chỉ số bằng
k
0
x
=
r
và
các cột được lập chỉ số bằng
k-1
0 1
x =
r
. Mặt khác, trong S
1
chỉ có duy nhất một cột mà
tất cả đều bằng không, chúng tương ứng với
k
0
x
=
r
. Chính vì thế trong bất kì phép hoán
vị nào của S
0
phép “or” của k hàng cho 2
k-2

2.3.4.2. Phép dựng 2
Bây giờ chúng ta chỉ ra một lược đồ tốt hơn một chút cùng với các tham số
m=2
k-1
,
α
=1/2
k
và r=2
k-1
!. Xem xét một tập hợp cơ sở W={e
1
,e
2
,…e
k
} của k nguyên tố
và gọi
k 1
1 2
2
, ,
π π π
−
là một danh sách gồm tất cả các tập con của các số các yếu tố trong
một tập hợp và gọi
k 1
1 2
2
, ,

nếu e
i
∈
j
σ
.
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 24 -
Như phép dựng hình bên trên, các tập hợp C
0
và C
1
có được bằng cách hoán đổi
tất cả các cột của ma trận tương ứng.
Bổ đề 2 : Sơ đồ bên trên là lược đồ ngưỡng (k, k) phần tử với các tham số
m=2
k-1
,
α
=1/2
k
và r=2
k-1
!.
Chứng minh: Để chỉ ra sự đối chiếu, chú ý rằng trong ma trận S
0
có một cột
mà tất cả đều bằng 0; được lập chỉ số bằng tập hợp rỗng. Mặt khác, trong S
1

được giới hạn chặt mà
α
≥2k-1. Vấn đề tổ hợp chính được sử dụng như sau: Cho hai
dãy
1 2 k
A ,A , ,A
…
và
1 2 k
, , ,
B B B
…
của các tập hợp của một số tập hợp cơ sở G, ta có
đối với mỗi tập hợp con
{1, }
U k
⊂
với kích thước gần bằng k-1, thì
i U i
A
∈
I
=
i U i
B
∈
I
,
và
1 1

và
1 2
, , ,
k
B B B
. Tập hợp cơ sở có kích thước m-r và các nguyên tố của
nó được lập chỉ số bằng (x,y) khi 1≤x≤r và 1≤y≤m. Nguyên tố (x,y) nằm trong tập A
i

nếu
1
[ ] 1
i
S iy
=
.
Mật mã trực quan Hoàng Thu Phương CH 07 – 09

- 25 -
Chúng ta có thể nhận thấy rằng với bất kì
{1, }
U k
⊂
với kích thước q<k đẳng
thức
i U i i U i
A B
∈ ∈
=I I
tồn tại: điều kiện bảo mật của C cho thấy rằng chúng ta có thể

1
1
.
2
k k
i i i i
k
B rm A
= =
−
≤ +U U

Điều này có nghĩa rằng đối với ít nhất một ma trận trong C
1
và một ma trận
trong C
0
, sự khác nhau giữa các trọng lượng Hamming của phép “or” của các hằng gần
bằng
1
1
.
2
k
m
−
. Chính vì thế chúng ta có:
Định lí 1: Trong bất kỳ lược đồ ngưỡng (k, k) thì
α
≥

C T T T
=
. Hơn nữa, giả thiết rằng lược đồ là không đổi, nghĩa là, có một hàm số
( )
f q
mà với bất cứ ma trận
t
i
T
nào khi
{0,1}
t
∈
và
1
i r
≤ ≤
và với bất kì
1 1
q k
≤ ≤ −
các
hàng của trọng lượng Hamming
t
i
T
của phép “or” của q hàng là
( )
f q
. Chú ý rằng tất