Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (1.73 MB, 62 trang )

Bạn đang đọc: Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Mục lục
Tác giả

Tên bài

Trang

Trần Minh Tân
Nguyễn Văn Tam

Nâng cao hiệu quả bảo mật cho hệ thống tên miền

Đỗ Văn Tuấn
Phạm Văn Ất

Một thuật toán giấu tin trong ảnh có bảng màu

Lưu Hồng Dũng

Phát triển thuật toán mật mã khóa công khai dựa trên hệ mật
Elgamal

Mai Thị Như

Nguyễn Duy Phương

Một phương pháp lọc cộng tác dựa trên mô hình đồ thị hai
phía

Nguyễn Đức Quang,
Phạm Hồng Liên và Lưu
Thanh Trà

Giải pháp sử dụng bộ lọc thích nghi Kalman cho hệ thống
ước lượng kênh truyền WiMAX di động

Nguyễn Thị Thu Hương
Lê Ngọc Minh

Ứng dụng văn phạm liên kết trong dịch máy Việt – Anh

Cao Hữu Tình
Vũ Hỏa Tiễn
Nguyễn Công Định

Khảo sát hệ thống tự động ổn định trên khoang tên lửa điều
khiển bằng phương pháp gas-động mômen

Danh sách phản biện Chuyên san số 28

-3-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Contents
Authors

Paper name

Page

Tran Minh Tan
Nguyen Van Tam

Security Enhancement for Domain Name System

Do Van Tuan

Pham Van At

A New Data Hiding Algorithm in Palette Images

Luu Hong Dung

Development of Public Key Cryptographic Algorithm
Based On Elgamal Cryptosystem

Mai Thi Nhu
Nguyen Duy Phuong

A collaborative Filtering Method Based on Bipartite Graph
Model

Solution of Applying Adaptive Kalman Filter for Channel
Estimation in Mobile WiMAX System

Nguyen Thi Thu Huong
Le Ngoc Minh

Application of Link Grammar Formalism in Vietnamese English Translation

Cao Huu Tinh
Vu Hoa Tien
Nguyen Cong Dinh

The Investigation on Automatic Stability System of Missile
with Lateral Impulsive Thrust

Nguyen Duc Quang
Pham Hong Lien
Luu Thanh Tra

List of Paper Reviewers of Special Issue No.28

-4-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Nâng cao hiệu quả bảo mật cho hệ thống tên miền
Security Enhancement for Domain Name System
Tần Minh Tân và Nguyễn Văn Tam

Abstract: Domain Name Server (DNS) system, a
root source providing answers with IP addresses for
any request for domain names, is regarded as the most
important part of Internet. DNS system also plays a
very important part of cryptography analytic
infrastructure of Internet. Any change made to DNS
system can make the system fall into malfunction,
boosting complexity levels in dealing with triggered
issues [2,11]. Therefore, security for DNS is a vital
must. For the time being, RSA algorithm [6,12] has
become the de factor standard for DNS security.
However, RSA requires a longer key length of more
than 1000 bits [10,15], affecting performance
efficiency of DNS system. Hence, elliptic curve
cryptography or ECC is regarded as an alternative
mechanism for implementing public-key cryptography.
The ECC is expected to be used not only in new
generation mobile devices [13] but also in DNS
system in the near future as ECC requires shorter key
length than RSA but providing the same security level.
This paper focuses on introducing ECC and new
findings related to this mechanism such as key pair
generation algorithms, key transfer, encryption and
decryption in ECC, as well as findings of the trial on
the Vietnam national domain name system dot VN;
these findings aims to apply for certification domain
name data transfer for the DNS system of a country
and compare with the same method in RSA algorithm.
I. GIỚI THIỆU
Bảo mật cho các hệ thống mạng Internet nói chung

và hệ thống tên miền nói riêng là một nhiệm vụ hết
sức quan trọng và cấp bách trong hoàn cảnh hiện nay.
Tiến triển theo thời gian, các cuộc tấn công vào mạng
Internet ở Việt Nam và trên thế giới đang diễn ra ngày

càng nhiều với hình thức ngày một tinh vi, phạm vi
ngày càng lớn hơn. Thực tế đã có những trường hợp,
những thời điểm tin tặc thông qua việc tấn công vào
hệ thống máy chủ tên miền (DNS) đã làm tê liệt mạng
Internet trên diện rộng trong nhiều giờ gây thiệt hại
lớn về an ninh cũng như kinh tế. Để giải quyết vấn đề
an toàn cho hệ thống DNS, công nghệ bảo mật
DNSSEC (DNS Security Extensions) đã được nghiên
cứu và đang được đưa vào áp dụng trong thời gian qua
[6].
Năm 1976, Whifield Diffie và Martin Hellman đã
đưa ra khái niệm mã bảo mật khóa công khai (PKC Public Key Cryptography). Từ đó, nhiều ứng dụng của
nó đã ra đời và nhiều thuật toán đã được phát triển để
giải quyết các bài toán bảo mật. Mức độ bảo mật yêu
cầu càng cao thì cỡ khóa phải càng lớn. Với hệ mật mã
RSA đang được áp dụng trong hầu hết các ứng dụng,
trong đó bao gồm cả bài toán bảo mật cho DNS qua
công nghệ DNSSEC [2,6,9] đã nói ở trên, để đảm bảo
yêu cầu bảo mật, hiện phải cần cỡ khóa lớn hơn 1000
bit [10,15]. Thực tế, tháng 3 năm 2010, tại hội nghị
DATE 2010 – Dresden Đức, các nhà khoa học Andrea
Pellegrini, Valeria Bertacco và Todd Austin thuộc
trường Đại học Michigan đã công bố kết quả phát hiện
một kẽ hở trong hệ mật mã RSA, cách phá vỡ hệ
thống, lấy khoá bí mật của RSA 1024 bit chỉ trong

vòng 104 giờ thay vì vài năm nếu tấn công theo cách
dò tìm lần lượt thông thường [15]. Công bố này cũng
đồng nghĩa với tuyên bố rằng, với RSA để đảm bản an
toàn sẽ phải tiếp tục tăng độ dài khóa (công nghệ
DNSSEC cho hệ thống DNS hiện tại thường sử dụng
RSA với độ dài khóa 2048 bit). Điều này kéo theo
việc phải tăng năng lực tính toán của thiết bị; làm tăng
đáng kể kích thước các file dữ liệu được ký xác thực;
tăng thời gian xử lý và lưu lượng dữ liệu phải truyền

-5-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

tải trên mạng; đòi hỏi dung lượng lưu trữ của bộ nhớ
lớn hơn, nguồn tiêu thụ nhiều hơn,… Và như vậy cũng
có nghĩa là sẽ không đảm bảo hiệu quả về mặt kinh tế.
Năm 1985, Neal Koblitz và Victor Miller đã nghiên
cứu và đưa ra những công bố về hệ mật mã bảo mật
dựa trên đường cong Elliptic (Elliptic Curve
Cryptography – ECC) có những đặc tính đặc biệt
[3,4,8]: Yêu cầu năng lực tính toán thấp; tiết kiệm bộ
nhớ; tiết kiệm băng thông; tiết kiệm năng lượng; tính
bảo mật cao. Từ những đặc điểm nổi trội ấy, nhiều nhà
khoa học đã đi sâu vào nghiên cứu hệ mật mã bảo mật
đường cong Elliptic [1,7,10,11] và bước đầu đã có các
ứng dụng vào một số lĩnh vực bảo mật, đặc biệt cho

các thiết bị thông tin di động [13], thiết bị USB[9].
Phát triển các kết quả này, Công ty Certicom Công ty đi đầu trong lĩnh vực nghiên cứu hệ mật mã
bảo mật ECC [16], đã nghiên cứu, triển khai một số
ứng dụng và công bố các số liệu so sánh về mức độ
bảo mật giữa các hệ mật mã RSA và ECC. Theo đó
với độ dài khóa 160 bit, hệ mật mã ECC đã có độ bảo
mật tương đương với hệ mật mã RSA-1024 bit; và với
độ dài khóa 224 bit, hệ mật mã ECC có độ bảo mật
tương đương với hệ mật mã RSA-2048 bit [3].

Bảng 1. So sánh độ dài khóa của các hệ mật mã với
cùng mức độ bảo mật [3]
Hệ mật
mã

Kích thước khóa (tính theo bit)

Khóa đối
xứng

RSA/
DSA

512 1024 2048 3072 7680

ECC

112

160

112

224

128

256

192

384

256

15360

512

Hình 1. So sánh mức độ bảo mật giữa ECC với
RSA/DSA [13]
Do kích thước khóa nhỏ và khả năng bảo mật cao
nên trong giai đoạn vừa qua, ECC chủ yếu được
nghiên cứu để bước đầu áp dụng cho các ứng dụng
trên môi trường mạng có giới hạn về thông lượng
truyền dữ liệu, các thiết bị có giới hạn về năng lực xử

lý, khả năng lưu trữ (đặc biệt là với các thiết bị di
động) [13]. Tuy nhiên với các lợi thế về mức độ bảo
mật và kích thước khóa nhỏ như đã nói ở trên, ECC
hoàn toàn có thể được áp dụng cho các hệ thống lớn
như DNS để thay thế, khắc phục các nhược điểm về
độ dài khóa của RSA. Bài báo này chúng tôi sẽ đề
xuất phương pháp cài đặt hệ mật mã ECC lên các giao
dịch trao đổi dữ liệu giữa các máy chủ trong hệ thống
DNS để nâng cao tính bảo mật và hiệu năng cho hệ
thống này.
Trong [1], tác giả đã chỉ ra những bước cơ bản để
xây dựng thuật toán bảo mật bằng đường cong
Elliptic, tuy vậy mới dừng lại ở công thức tổng quan
hoặc ở ví dụ cụ thể bằng số. Ở đây, chúng tôi sẽ xây
dựng chi tiết các thuật toán tạo khóa, chuyển khóa, mã
hóa và giải mã trên ECC một cách đơn giản và rõ ràng
hơn nhằm giảm số bước thực hiện. Đây là nền tảng để
xây dựng hệ mật mã ECC.

-6-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
Trong các nội dung tiếp theo, Phần 2 chúng tôi sẽ
trình bày phát biểu bài toán hệ mật mã đường cong
Elliptic (ECC) và kết quả xây dựng một số thuật toán
trong ECC để áp dụng cho việc xác thực trong quá
trình trao đổi dữ liệu trên mạng Internet; Phần 3 trình
bày kết quả thực nghiệm ECC, ứng dụng các thuật
toán nói trên trong việc xác thực dữ liệu tên miền

trong hệ thống DNS cấp quốc gia, so sánh với cách sử
dụng phương pháp tương tự bằng RSA; cuối cùng là
phần kết luận.

Tập V-1, Số 8 (28), tháng 12/2012

Tập các điểm trên đường cong Elliptic (E) có các
đặc điểm sau:
•

Điểm Θ là điểm thuộc (E) nằm ở vô cùng,
được gọi là phần tử trung hòa.

•

Với mỗi điểm P=(x,y), phần tử đối của P là
điểm -P=(x,-y), ta định nghĩa tổng hai điểm
P+(-P) = P-P = Θ. Hay -P là điểm đối xứng
của P qua trục Ox.

•

Với 2 điểm P=(xP, yP) và Q=(xQ, yQ) với xP ≠
xQ, một đường thẳng đi qua hai điểm P, Q sẽ
giao với (E) tại một điểm duy nhất. Ta định
nghĩa điểm R = -(P+Q). Nếu đường thẳng này
là tiếp tuyến của (E) tại điểm P hoặc Q thì
tương ứng R≡P hoặc R≡Q. Điểm đối xứng của
R là -R được gọi là điểm tổng của P và Q.

•

Đường thẳng đi qua P và -P (tức P và Q có
cùng hoành độ), sẽ giao với (E) tại điểm vô
cùng, do vậy R = P+(-P) = Θ.

•

Để nhân đôi điểm P, ta vẽ tiếp tuyến của (E)
tại P, tiếp tuyến này sẽ giao với (E) tại điểm
Q, ta có Q= -(P+P)=-2P. Hay -Q=2P

II. PHÁT BIỂU BÀI TOÁN
Đường cong Elliptic trên GF(p) hoặc Zp với số
nguyên tố p được xác định bằng phương trình Cubic:
y2 = ( x3 + ax + b) mod p, với các hệ số a và b và các
biến x và y là các phần tử của Zp thỏa mãn ràng buộc
(4a3 + 27b2) mod p ≠ 0 [14].
Như vậy ta dễ dàng nhận thấy đường cong Elliptic
(E) có phương trình là hàm chẵn đối với biến y, do đó
đồ thị của (E) nhận trục hoành Ox là trục đối xứng.

Với những đặc điểm trên, tập các điểm thuộc
đường cong (E) tạo thành một nhóm Abel.
Hệ mật mã đường cong Elliptic (ECC) được xây
dựng trên cơ sở bài toán logarith trên đường cong
Elliptic. Độ bảo mật ECC phụ thuộc vào độ khó của
bài toán logarith rời rạc đường cong Elliptic. Giả sử P
và Q là hai điểm trên đường cong Elliptic sao cho
k*P=Q trong đó k là một đại lượng vô hướng với P và

Q đã cho, bằng cách tính toán suy luận để thu được k
trên cơ sở thuật toán rời rạc của Q đối với P.

Hình 2. Một dạng đường cong Elliptic

Với một điểm P cho trước và hệ số k, ta có thể dễ
dàng tính ra được điểm Q tương ứng trên đường cong
Elliptic. Tuy nhiên theo chiều ngược lại, để tìm ra hệ
số k (khóa k) từ điểm Q và điểm P lại là một bài toán
“rất khó” nếu như hệ số k là một số đủ lớn (có độ dài
224 bit chẳng hạn). Dựa trên cơ sở bài toán logarit rời
rạc xét trên tập các điểm thuộc đường cong Elliptic
này, hệ mật mã ECC cung cấp đầy đủ cả 4 dịch vụ an
ninh: mã hóa, xác thực, ký số và trao đổi khóa; đảm

-7-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Thuật toán tạo khóa: Hai bên gửi A và nhận B.

bảo cho việc xây dựng một hạ tầng xác thực khóa
công khai trên Internet. Do đó một trong những thuật
toán chủ yếu trong ECC là tạo khóa, chuyển khóa, mã
hóa và giải mã [14].

Thống nhất

Trên cơ sở bài toán này, chúng tôi đề xuất các thuật
toán cụ thể:

Chọn ngẫu
nhiên nB < n

Chọn ngẫu
nhiên nA< n

1. Tạo khóa:

– Đường Elliptic
– T (p, a, b, G, n, h)

Đường cong Elliptic trên trường GF(p) có dạng:
y2 = (x3 + ax + b) mod p

(1)

PA = nA*G
(XA, YA)

Tham số hệ mật mã ECC trên trường nguyên tố
hữu hạn Fp.[4]:
T = (p, a, b, G, n, h)

đã nói ở trên với các tham số p, a và b đã chọn. Lấy
điểm cơ sở G từ nhóm Ep(a,b) trên đường cong
Elliptic, bậc của nó phải là một giá trị n lớn [14]. Bậc
n của điểm G trên đường cong Elliptic được xác định
bằng số nguyên dương bé nhất n sao cho n*G = 0 [14].

PB = nB*G
(XB, YB)

Cặp khóa

(2)

Trong đó: p là số nguyên dương xác định trường
nguyên tố hữu hạn Fp và chọn [log2P] ∈ {192, 224,
256, 384, 512}; a,b là các hệ số ∈Fb xác định đường
cong trên Elliptic E(Fb) trên trường Fb(1); h là phần
số thập phân, h= #E(Fb)/n với #E(Fb) là số các điểm
thuộc đường cong E(Fb).

Theo các bước tạo khóa được xác định tại [14],
chúng tôi xây dựng thuật toán như Hình 3.

Cặp khóa

Hình 3. Thuật toán tạo khóa
2. Thuật toán trao đổi khóa

Thuyết minh thuật toán:
•

•

Đầu vào: Bên gửi A và Bên nhận B thống nhất
đường cong Elliptic và tham số hệ mật mã
đường cong Elliptic T.

a’

b’

Đầu ra: Khóa công khai của A: PA và khóa
công khai của B: PB cần được thiết lập.

Các bước thuật toán:
x

1. A chọn ngẫu nhiên một số nguyên dương nA < n.
2. A xác lập tích PA = nA*G = (xA, yA)

K = nA*PB

x
Khóa
chia sẻ

K = nB*PA

Cặp khóa công khai và khóa riêng của A là (PA, nA)
3. B chọn ngẫu nhiên số nguyên nB< n và tính

K= nA*PB = nA * (nB * G) = nB * (nA* G) = nA* nB* G

PB = nB * G = (xB, yB)
Cặp khóa công khai, khóa riêng của B là (PB, nB).

Hình 4. Thuật toán trao đổi khóa

-8-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
Thuyết minh thuật toán:
Thuật toán trao đổi khóa được hình thành sau khi
bên A và bên B đã được tạo khóa PA và PB thể hiện ở
điểm a, b tương ứng trên hình 3 như đã nói ở trên.
Thuật toán được diễn đạt như sau:
• Đầu vào: Cặp khóa PA và PB
• Đầu ra: PA B ; PB A
Xác nhận đúng đối tượng cần kết nối thông tin
bằng kết quả hai bên tìm được khóa chia sẻ chung K.

Tập V-1, Số 8 (28), tháng 12/2012

• Đầu vào: A muốn gửi bản tin M cho B.
• Đầu ra : Văn bản mã cM
• Các bước thực hiện:
1. A chọn ngẫu nhiên một số nguyên dương thỏa
mãn 0 < k < n và tính: c1 = k*G và c2 = M + k*PB

trong đó PB là khóa công khai của B.
2. A gửi văn bản đã mã hóa cM = { c1, c2} cho B.
Thuật toán giải mã

Các bước thực hiện :

{c1, c2}

1. A truyền khóa PA cho B; B truyền khóa PB cho
A.
2. Cả A và B tính khóa chia sẻ:
• Phía A: Lấy nA của mình nhân với khóa PB
nhận được từ B tạo ra:
K= nA*PB = nA *(nB*G) = nA* nB* G
• Phía B: Lấy nB của mình nhân với khóa PA
nhận được từ A tạo ra:
K= nB*PA = nB* (nA*G) = nA*nB* G
Như vậy cả A và B đều nhận được K giống nhau.

x
nB*c1

3. Thuật toán mã hóa và giải mã

Hình 6. Lưu đồ thuật toán giải mã

Thuật toán mã hóa và giải mã Elliptic được Bellaer
và Rogaway đề xuất [3], thực chất là một biến thể của
hệ mật mã công khai Elgamal. Ở đây chúng tôi cụ thể
hơn dưới dạng lưu đồ thuật toán và đơn giản hơn bằng
cách bỏ qua thủ tục tính cặp khóa, tính bản mã sử
dụng.

•
•

Đầu ra:
Khôi phục lại văn bản M do A gửi đến.

•

Đầu vào ở B:
B nhận được văn bản mã CM = { c1, c2}

Thuật toán mã hóa:
k

Các bước thực hiện :

B tách c1 và nhân c1 với khóa riêng nB của nó
và lấy c2 trừ đi kết quả đó:
c2 – nB*c1 = M + k*PB – nB * (k*G)

= M + k*(nB*G) – nB*(k*G)
=M

c1= k*G

Vậy đã thực hiện xong giải mã.

c2 = M + k*P

Nhận xét:
+
cM={c1, c2}

Hình 5. Lưu đồ thuật toán mã hóa

Thuật toán này không yêu cầu kiểm tra điểm R có
thuộc đường cong Elliptic hay không; không cần tính

điểm Z = k*k*R như trong [1,3,14] làm cho tốc độ
tính nhanh hơn.

-9-

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Bảng 2. Tổng hợp số liệu về thời gian ký xác thực và kích thước các zone file tên miền .VN trước và sau khi ký
bằng DNSSEC với RSA-2048 bit và ký bằng ECC-224 bit.
Zone

Kích thước
zone file ban
đầu (Bytes)

.vn
.com.vn
.net.vn
.org.vn
.edu.vn
.ac.vn

3 520 683
3 495 013
120 257
142 423
263 367

5 765

Kích thước zone file sau khi ký
xác thực (bytes)
Với DNSSEC sử
Với ECCdụng RSA-2048 bit
224 bit

27 126 822
24 357 519
840 584
1 078 018
1 749 856
42 885

6 337 230
5 941 522
198 424
243 544
442 456
10 492

III. KẾT QUẢ THỰC NGHIỆM
Trên cơ sở các thuật toán đề xuất ở trên, chúng tôi
đã sử dụng ngôn ngữ lập trình Java để cài đặt các thuật
toán, áp dụng vào quá trình xác thực trong các giao
dịch trao đổi dữ liệu tên miền giữa máy chủ DNS
chính (Primary DNS Server) và các máy chủ phụ
(Secondary DNS Server). Thí nghiệm được thực hiện
trên các zone file dữ liệu tên miền được lấy trực tiếp

về từ hệ thống DSN quốc gia.
Để đảm bảo an toàn và dự phòng bổ sung, san tải
cho nhau, hệ thống DNS được thiết kế theo quy định
sẽ gồm một máy chủ DNS chính và nhiều máy chủ
DNS phụ. Theo các mốc thời gian định kỳ tùy thuộc
vào cơ chế khai báo trên máy chủ DNS chính, các máy
chủ DNS phụ sẽ tự động kết nối với máy chủ DNS
chính để tải các file dữ liệu tên miền đã có sự thay đổi
trên máy chủ chính về máy chủ phụ để đáp ứng việc
cập nhật kịp thời các thay đổi nhằm trả lời chính xác
các truy vấn về tên miền từ các máy tính trên mạng
Internet được hỏi đến nó. Quá trình này được gọi là cơ
chế zone transfer trong quy trình quản lý hệ thống
DNS. Để bảo mật cho quá trình đồng bộ dữ liệu này,
ngoài giải pháp phần cứng (khai báo cấu hình mạng
chỉ cho phép các máy chủ phụ có địa chỉ IP từ trong
một danh sách đã được định nghĩa trước mới có quyền
kết nối vào máy chủ chính), hiện chỉ mới có công
nghệ bảo mật DNSSEC sử dụng RSA đang được áp

Thời gian ký (giây)
Với DNSSEC sử
dụng RSA-2048 bit

Với ECC224 bit

171,135
145,342
5,094
6,668

10,464
0,269

21,942
18,633
0,621
0,877
1,291
0,038

Số tên
miền
được
ký

69 530
59 483
2 069
2 684
4 232
108

dụng là có triển khai việc ký xác thực, mã hóa dữ liệu
tên miền trong quá trình trao đổi giữa các máy chủ
DNS với nhau. Ở đây, chúng tôi đã xây dựng chương
trình ký xác thực, mã hóa, giải mã bằng ECC tương tự
như các bước làm của DNSSEC sau đó lần lượt sử
dụng ECC để thực hiện việc ký xác thực, mã hóa dữ
liệu trên các zone tên miền quốc gia bao gồm .vn,
.com.vn, .net.vn, .org.vn, .edu.vn và .ac.vn và so sánh

với các kết quả đã thu được bằng phương pháp sử
dụng DNSSEC.
Các kết quả thu bằng hai phương pháp được đem ra
so sánh theo các tiêu chí sau: 1/ Thời gian ký xác thực;
2/Kích thước zone file sau khi ký xác thực. Chi tiết
được thể hiện trong Bảng 2.
Kết quả so sánh này cho thấy, sau khi ký xác thực
bằng RSA-2048 bit với DNSSEC, kích thước các zone
file tăng bình quân xấp xỉ 7,31 lần, trong khi đó sau ký
xác thực bằng ECC-224 bit kích thước chỉ tăng bình
quân 1,74 lần so với file dữ liệu gốc. Về thời gian ký
xác thực, khi sử dụng RSA-2048 bit sẽ lâu hơn bình
quân 7,8 lần so với việc ký bằng ECC-224 bit theo
thuật toán đã đề xuất.
Tổng hợp so sánh kết quả thực nghiệm trên các
zone file được lấy liên tiếp mỗi khi có sự thay đổi các
bản ghi tên miền trên zone của máy chủ DNS chính
trong vòng 24 giờ liên tục (theo cơ chế yêu cầu máy
chủ DNS phụ cập nhật toàn bộ nội dung file mỗi khi
có thay đổi) được thể hiện trên các sơ đồ sau:

– 10 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

DNSSEC với cùng một mức độ bảo mật. Việc sử dụng
ECC đã làm giảm tương đối thời gian, dữ liệu phải

truyền tải trên mạng trong quá trình đồng bộ tên miền
giữa máy chủ DNS chính và các máy chủ DNS phụ,
đồng thời tiết kiệm đáng kể băng thông (hiện tại hệ
thống DNS quốc gia đang phải đồng bộ dữ liệu thường
xuyên trong ngày giữa máy chủ chính và 26 máy chủ
phụ đặt tại các địa điểm khác nhau trên toàn cầu). Việc
ứng dụng ECC sẽ nâng cao rõ rệt hiệu năng cho hệ
thống máy chủ tên miền.
IV. KẾT LUẬN
Bài báo này nghiên cứu áp dụng mã bảo mật đường
cong Elliptic, trong đó đã :

Hình 7. So sánh kích thước zone file tên miền sau khi
ký xác thực với RSA-2048 bit và ECC-224 bit

– Xây dựng lưu đồ thuật toán tạo khóa dựa trên
đường cong Elliptic và tham số T(p, a, b, G, n, h),
giúp cho việc tính toán rõ ràng và đơn giản.
Xây dựng thuật toán trao đổi khóa thống nhất với thuật
toán tạo khóa và bỏ qua được các bước A tạo PA gửi B
và B tạo PB gửi A như trong [3]. Đồng thời thuật toán
ở đây đơn giản.
– Đưa ra thuật toán mã hóa, giải mã đơn giản hơn
so với trước đây.
– Cuối cùng trong bài báo này, chúng tôi đã trình
bày kết quả thực nghiệm cài đặt thuật toán, áp dụng
thử nghiệm trên các file dữ liệu tên miền được lấy trực
tiếp về từ hệ thống DSN quốc gia (các file trên thực tế
sẽ tham gia trong quá trình trao đổi dữ liệu tên miền
giữa máy chủ DNS quốc gia). So sánh thời gian ký xác

thực, kích thước các file dữ liệu sau khi triển khai thử
nghiệm bằng ECC-224 bit qua các thuật toán được xây
dựng trong bài báo với các kết quả đã thu được khi sử
dụng công nghệ DNSSEC sử dụng RSA-2048 bit. Kết
quả thực nghiệm đã khẳng định được tính ưu việt của
việc ứng dụng các thuật toán trên ECC đã được đề
xuất trong bài báo so với phương pháp thông dụng
hiện nay là RSA.

Hình 8. So sánh thời gian ký xác thực bằng RSA2048 bit và ECC-224 bit trên các zone file gốc
Như vậy, rõ ràng ECC có các ưu điểm vượt trội
về thời gian xử lý và đặc biệt là làm giảm đáng kể kích
thước các zone file dữ liệu tên miền sau khi được ký
xác thực so với phương pháp dùng RSA trong

Từ những phân tích trên, ta thấy việc nghiên cứu,
ứng dụng mã bảo mật đường cong Elliptic – ECC như
những kết quả đã đưa ra đã đạt yêu cầu làm tăng tính
bảo mật hơn so với RSA, đồng thời với ba thuật toán

– 11 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
đã nêu làm đơn giản số bước tính toán. Đây sẽ là nền
tảng cơ sở để giải quyết việc tránh phải tiếp tục nâng
độ dài khóa như RSA mà vẫn đáp ứng được yêu cầu
về bảo mật (khó phá khóa) với kích thước khóa nhỏ
hơn. Việc áp dụng mã bảo mật đường cong Elliptic ECC trong các hệ thống lớn như DNS là một hướng đi
đúng và trọng tâm trong thời gian tới. Trong hướng

nghiên cứu sắp tới, chúng tôi sẽ mở rộng xét chọn
miền tham số cho đường cong Elliptic để sử dụng làm
mã bảo mật.

TÀI LIỆU THAM KHẢO
[1] ANOOP MS, Elliptic Curve Cryptography. An
Implementation Guide. anoopms@tataelxsi.co.in
[2] B. WELLINGTON, Domain Name System Security
(DNSSEC) signing Authority, RFC 3008, Internet
Engineering
Task
Force,
November
2000
http://www.ietf.org/rfc/rfc3008.txt
[3] CERTICOM RESEARCH, SEC1: Elliptic Curve
Cryptography, Version 1.0, September 2000,
http://www.secg.org/collateral/sec1_final.pdf
[4] CERTICOM RESEARCH, SEC2: Recommended
Elliptic Curve Domain Parameters, Version 2.0
January 27, 2010, www.secg.org/download/aid784/sec2-v2.pdf
[5] DARREL
HANKERSON,
JULIO
LÓSPEZ
HERNANDERZ, ALFRED MENEZES, Software
Implementation of Elliptic Curve Cryptography over
Binary Fields, CHES 2000.
[6] DANIEL MASSEY, ED LEWIS and OLAFUR
GUDMUNDSSON, Public Key Validation for the DNS

Security Extensions, DARPA Information Survivability
Conference & Exposition II, 2001. DISCEX ’01.
Proceedings, Print ISBN: 0-7695-1212-7, 2001.
[7] F. HESS, Generalising the GHS attack on the Elliptic
Curve Discrete logarithm problem, LMS J. Comput,
Math 7, 2004.
[8] JACOB SCOTT, Elliptic
December 14, 2010.

Curve

Tập V-1, Số 8 (28), tháng 12/2012
International Journal of Computer Science and
Network Security, VOL. 11 No. 11, November 2011.

[10] N. GURA A. PATEL, A. WANDER, H. EBERLE and
S.C
SHANTZ,
Comparing
Elliptic
Curve
Cryptography and RSA on 8 bit CPUS, Proccedings of
Workshop on Cryptographic Hardware and Embedded
Systems (CHES 2004) 6th Internetional Workshop 2004
[11] M. ABDALLA, M. BELLARE and P.ROGAWAY,
DHAES. An encryption Scheme based on the Difflie Hellman problem, Submission to P1363a: Standerd
specifications for Public-Key Cryptography, Additional
Techniques, 2000.
[12] REZA CURTMOLA, ANIELLO DEL SORBO,
GIUSEPPE ATENIESE, On the Performance and

Analysis of DNS Security Extensions, Cryptology and
Network Security, 4th International Conference, CANS
2005.
[13] WENDY CHOU, Elliptic Curve Crytography and its
Applications to Mobile Devices, University of
Maryland,
College
Park,
2003
http://www.cs.umd.edu/Honors/reports /ECCpaper.pdf
[14] W. STALLINGS, Crypotography
Security, Fourth Edition 2009.

and

Network

[15] ANDREA PELLEGRINI, VALERIA BERTACCO and
TODD AUSTIN, Fault Based Attack of RSA
Authentication, Design, Automation and Test in Europe
(DATE) conference in Dresden on March 10.
http://web.eecs.umich.edu/~valeria/research/publication
s/DDTE10RSA.pdf

[16]

Certicom Website: http://certicom.com

Nhận bài ngày: 25/05/2012

Cryptography,

[9] JAGDISH BHATTA and LOK PRAKASH PANDEY,
Perfomance Evaluation of RSA Variants and Elliptic
Curve Cryptography on Handheld Devices. IJCSNS

– 12 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
SƠ LƯỢC VỀ TÁC GIẢ

Tập V-1, Số 8 (28), tháng 12/2012

NGUYỄN VĂN TAM
Sinh ngày 21/02/1947.

TRẦN MINH TÂN
Sinh ngày 02/9/1968 tại Hưng
Yên.
Tốt nghiệp Đại học Sư phạm
Hà Nội I – Khoa Vật Lý năm
1991, Đại học Bách khoa Hà
Nội – Khoa CNTT năm 1996.
Nhận bằng Thạc sỹ chuyên
ngành CNTT năm 2006 tại Trường Đại học Công
nghệ – ĐHQG Hà Nội. Đang là nghiên cứu sinh tại
Viện Công nghệ Thông tin – Viện Khoa học và Công
nghệ Việt Nam.

Tốt nghiệp Đại học CVUT, Praha, Tiệp Khắc năm
1971.
Bảo vệ luận án Tiến sĩ tại Viện Nghiên cứu VUMS,
Praha, Tiệp Khắc năm 1977.
Được phong Phó Giáo sư năm 1996.
Hiện đang công tác tại Phòng Tin học viễn thông Viện Công nghệ Thông tin.
Lĩnh vực nghiên cứu: Công nghệ mạng và Quản trị, an
toàn mạng.
Điện thoại: 0913390606, 04.38362136
Email: nvtam@ioit.ac.vn

Hiện công tác tại Trung tâm Internet Việt Nam – Bộ
Thông tin và Truyền thông.
Lĩnh vực nghiên cứu: An toàn, bảo mật trên mạng
Internet, công nghệ IPv6, DNS.
Điện thoại: 0913275577, 04.35564944 máy lẻ 512
Email: tantm@vnnic.net.vn

– 13 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Một thuật toán giấu tin trong ảnh có bảng màu
A New Data Hiding Algorithm in Palette Images
Đỗ Văn Tuấn và Phạm Văn Ất
Abstract: This paper proposes a new algorithm to
embed data in palette image. In each image block of

original image, this algorithm can hide a bit by
modifying at most one pixel of block. New color of
modified pixel resembles the color of its some
neighborhood pixels, so the image after hiding very
close to the original image. The experimental results
showed that the invisible of proposed algorithm is
better than algorithms Fridrich and Ez Stego.
Keywords: data hiding, steganography, security
watermarking, Palette images
I. GIỚI THIỆU
Ngày nay, mạng Internet đóng vai trò quan trọng
trong việc trao đổi dữ liệu giữa những người dùng.
Bên cạnh những thuận lợi, vấn đề bảo mật thông tin
trên Internet luôn là những thách thức đối với các cấp
quản lý và các nhà nghiên cứu. Trước đây, các phương
pháp mã hóa luôn là sự lựa chọn để bảo mật thông tin
và đã mang lại những thành công nhất định. Tuy
nhiên, việc truyền tải công khai các bản mã sẽ tạo ra
sự chú ý, thách thức đối với các đối thủ, những người
muốn khám phá nội dung của bản mã một cách trái
phép. Gần đây, bên cạnh các phương pháp mật mã
truyền thống, kỹ thuật giấu tin giữ vai trò quan trọng
trong các bài toán bảo mật thông tin, bảo vệ bản
quyền, xác thực dữ liệu.
Giấu tin là kỹ thuật nhúng thêm thông tin vào các
dữ liệu đa phương tiện. Thông tin được nhúng có thể
là các thông điệp bí mật cần trao đổi, hoặc là các thông
tin về sản phẩm. Dữ liệu dùng để mang thông tin
nhúng thường là những dạng dữ liệu phổ biến trên
Internet như: ảnh, âm thanh, video. Theo [1], kỹ thuật

giấu tin cần có một số tính chất cơ bản như: tính che

giấu, tính khả nhúng và tính bảo mật. Theo định dạng
ảnh, các kỹ thuật giấu được chia thành hai loại chính.
Loại thứ nhất, gồm các kỹ thuật giấu tin trên ảnh
không có bảng màu [2,9,10]. Ảnh không có bảng màu
thường là những ảnh có số lượng màu lớn, dữ liệu ảnh
chính là các giá trị màu của điểm ảnh. Lợi dụng sự hạn
chế của hệ thống thị giác không phát hiện ra sự thay
đổi nhỏ về màu sắc, các thuật toán giấu tin trên dạng
ảnh này dễ dàng có được tính che giấu cao bằng cách
thay đổi một lượng nhỏ giá trị màu trong vùng dữ liệu
ảnh. Loại thứ 2, gồm các kỹ thuật giấu tin trên ảnh có
bảng màu [3]-[8]. Đối với ảnh có bảng màu, dữ liệu
ảnh là chỉ số màu của điểm ảnh. Hai chỉ số gần nhau
có thể tham chiếu tới hai màu rất khác nhau. Do vậy,
các thuật toán giấu tin trên dạng ảnh này gặp phải
những khó khăn nhất định, bởi vì chỉ cần có thay đổi
nhỏ về chỉ số màu có thể sẽ dẫn đến sự khác biệt lớn
về màu sắc của điểm ảnh trước và sau khi thay đổi.
Với ảnh có bảng màu, để nâng cao tính che giấu,
các kỹ thuật giấu tin thường tìm cách thay thế một
màu có chỉ số chẵn bằng màu gần nhất có chỉ số lẻ
hoặc ngược lại [3,4,7,8]. Dựa trên ý tưởng này,
phương pháp Ez Stego [7] sắp xếp lại các màu trong
bảng màu theo cường độ sáng. Cường độ sáng của
màu c với các thành phần Rc, Gc, Bc được tính theo
công thức:
= 0.299

+ 0.587

+ 0.144

) +(

Sau khi sắp xếp lại bảng màu, các màu giống nhau
sẽ có chỉ số màu gần nhau. Tuy nhiên, theo
Fridrich[3,4], hai màu khác nhau vẫn có thể có cường
độ sáng bằng nhau, vì vậy tác giả đã sử dụng khoảng
cách Euclid để đánh giá sự khác biệt về màu ứng với
các chỉ số màu i và j theo công thức:

– 14 –

(

−

)

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
trong đó Ri, Gi, Bi và Rj, Gj, Bj là giá trị màu ứng với
các chỉ số i và j trong bảng màu. Khi cần thay đổi một
màu có chỉ số chẵn (hay lẻ), Fridrich sẽ duyệt các màu
có chỉ số lẻ (hay chẵn) để tìm màu gần nhất (theo
khoảng cách Euclid) với màu cần thay đổi. Tuy nhiên,
chiến thuật thay thế màu gần nhất của các thuật toán
vẫn có thể tạo ra các màu mới cô lập, vì vậy trong một
số trường hợp, ảnh chứa tin giấu dễ bị phát hiện.
Để nâng cao chất lượng của ảnh sau khi giấu tin,
trong [6] các tác giả G. Pan, Z. Wu, Y. Pan đã đề xuất
thuật toán giấu tin cho ảnh ít màu bằng cách sử dụng
một tập các khối mẫu có kích thước 3×3, các khối mẫu
sẽ có sự ưu tiên khác nhau trong quá trình sử dụng để
nhúng tin. Mỗi khối mẫu được xác định bởi 8 điểm
xung quanh điểm tâm của khối, trong đó chia làm hai
phần liên thông, một phần gồm các điểm có màu
giống nhau được gọi là màu mẫu, phần còn lại gồm
các điểu có màu khác màu mẫu được gọi là màu tham
dự (nominated color). Thuật toán sẽ tìm các khối ảnh
kích thước 3×3 trùng với một mẫu trong tập mẫu và
nhúng một bít bằng cách biến đổi màu của điểm tâm
khối thành màu mẫu hoặc màu tham dự. Với cách thay
đổi như vậy, thuật toán có hai tính chất quan trọng:
điểm ảnh được chọn để thay đổi luôn nằm trên biên
của hai miền có màu khác nhau và không xuất hiện
màu mới. Nhờ vậy, thuật toán có tính che giấu cao.
Tuy nhiên, khối lượng tin có thể nhúng được còn chưa
nhiều như chính nhận xét của các tác giả. Cũng cần
nhận xét thêm, ý tưởng chọn điểm trên biên để thay

đổi cũng đã được các tác giả M. Wu [11] và Y. C.
Tseng[12] sử dụng để giấu tin trên ảnh nhị phân,
nhưng mỗi phương pháp đều có cách chọn khác nhau.
Dựa trên phương pháp giấu tin theo khối bít và tính
chẵn lẻ, bài báo này đề xuất một lược đồ giấu tin trên
ảnh có bảng màu. Theo đó, vùng dữ liệu của ảnh gốc
sẽ được chia thành các khối cùng kích thước. Với mỗi
khối sẽ giấu được một bít và biến đổi nhiều nhất một
phần tử. Khi cần biến đổi tính chẵn lẻ của khối, thuật
toán sẽ thay thế giá trị của một phần tử bằng giá trị của
phần tử liền kề nhưng khác tính chẵn lẻ. Với chiến
thuật thay thế như vậy, thuật toán đề xuất cũng có hai

Tập V-1, Số 8 (28), tháng 12/2012

tính chất giống như thuật toán [6], do đó nó cũng có
tính che giấu khá cao.
Nội dung tiếp theo của bài báo được tổ chức như
sau: Phần 2 giới thiệu một số ký hiệu và định nghĩa
được sử dụng trong bài báo. Phần 3 trình bày nội dung
thuật toán đề xuất. Tính đúng đắn của thuật toán được
chứng minh trong Phần 4. Phần 5 trình bày kết quả
thực nghiệm của thuật toán đề xuất và so sánh với hai
thuật toán Fridrich, Ez Stego. Cuối cùng, Phần 6 là
một số kết luận.
II. MỘT SỐ KÝ HIỆU VÀ ĐỊNH NGHĨA
Để tiện cho việc trình bày, trong bài báo sử dụng
một số ký hiệu và định nghĩa như sau:
– Ký hiệu × là tập các ma trận nguyên không âm
cấp m×n (m hàng và n cột).

Xem thêm: Tải NhacCuaTui cho máy tính PC Windows phiên bản mới nhất

– Với ∈ ×, nói phần tử (i,j) có nghĩa là phần tử
trên hàng i và cột j (chỉ quan tâm đến vị trí), nói phần
tử Fi,j là phần tử trên hàng i, cột j và có giá trị bằng Fi,j
(quan tâm đến cả vị trí và giá trị). Hai giá trị Fi,j, Fu,v
khác tính chẵn lẻ được ký hiệu là Fi,j# Fu,v
Định nghĩa 2.1 Phép nhân đồng vị ⊗ hai ma trận
∈ ×, ∈ × ký hiệu là C = A ⊗ B và được
xác định theo công thức: Ci,j = Ai,j × Bi,j với i=1,2,…,m
và j = 1,2,…,n

Định nghĩa 2.2 Phép toán SUM trên ma trận ∈
×
là một số nguyên, ký hiệu SUM(A) và tính theo
công thức:
!”#( ) = $ $
%& %&

Định nghĩa 2.3 Phép toán MOD trên ma trận nguyên
∈ × là ma trận nhị phân cấp m×n ký hiệu là:

C = MOD(F) và được tính theo công thức: Ci,j = Fi,j
mod 2 với i =1,2,…,m và j = 1,2,…,n

Định nghĩa 2.4 Trên ma trận ∈ ×, phần tử (u,v)
được gọi là liền kề với phần tử (i,j) ký hiệu là:

Định nghĩa 2.5 Ma trận nhị phân ‘ ∈ × được gọi

là ma trận liên thông nếu với mỗi cặp hai phần tử bất

– 15 –

(i,j)

(u,v) nếu Max{|u-i|, |v-j|}= 1

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

kỳ không kề nhau (i,j) và (u,v) có giá trị Ki,j=Ku,v=1
luôn tồn tại dãy các phần tử (pt,qt), t=1,…,k sao cho:

1) Nếu s = 0 hoặc s = SUM(K), không giấu tin và
kết thúc thuật toán.

K pt ,qt = 1, t= 1,..k và

2) Nếu 1≤ s ≤SUM(K)-1, chuyển sang Bước 3

(i,j)

(p1,q1)

(p2,q2)

….

(pk,qk)

Bước 3: Xét hai khả năng:

(u,v)

1) Nếu s mod 2 = b, đặt G = F và kết thúc thuật
toán

III. THUẬT TOÁN ĐỀ XUẤT
Với ảnh có bảng màu, dữ liệu ảnh là một ma trận
gồm các chỉ số màu có giá trị nguyên từ 0 đến 255.
Ma trận dữ liệu ảnh được chia thành các ma trận con
cùng cấp và thuật toán sẽ giấu một bít dữ liệu trên mỗi
ma trận con. Để tiện cho việc theo dõi, dưới đây sẽ
trình bày thuật toán giấu một bít vào một ma trận con.
III.1. Ý tưởng của thuật toán đề xuất
Giả sử cần nhúng một bít tin mật b vào ma trận con
∈ ×. Thuật toán đề xuất dựa trên ý tưởng giấu
tin của Wu-Lee[11], sử dụng ma trân nhị phân
‘ ∈ × làm khóa bí mật và biến đổi nhiều nhất một
phần tử trên F để !”#( ⨂’) cùng tính chẵn lẻ với b.

2) Nếu s mod 2 ≠ b, chuyển sang Bước 4
Bước 4: Xây dựng tập ∏ theo công thức
=(>, ?)|’, = 1,

; = < =(>, ?)|’, = 1,

AℎăDE, ∃(u, v): (H, I) ⇔ (>, ?)và

lẻ, ∃(u, v): (u, v) ⇔ (i, j)và

=(>, ?)|’, = 1, ∃(u, v): (u, v) ⇔ (i, j)và

M,N #

Q
, P, EêHR = 1
P, EêQHR = !”#(‘) − 1 X

M,N #
,

P, EêQH2 ≤ R ≤ !”#(‘) − 2

Bước 5: Biến đổi F để nhận được G, thực hiện tuần tự
như sau:
1) Chọn một phần tử (i,j) ∈ ∏

2) Chọn một phần tử (u,v) sao cho: (u,v)

Xem thêm: Tiểu luận Lịch sử nghệ thuật

(i,j) và
Fu,v # Fi,j (Theo định nghĩa của ∏, luôn tồn tại (u,v)
như vậy)
3) Thay Fi,j bằng Fu,v. Đặt G = F, kết thúc thuật toán.

Trong thuật toán Wu-Lee, Fi,j là các giá trị 0 hoặc 1,
nên việc biến đổi một phần tử trên F chỉ đơn giản là
chuyển từ 0 sang 1 hoặc từ 1 sang 0. Ở đây, Fi,j có giá
trị từ 0 đến 255. Vấn đề chọn phần tử nào để biến đổi
và chọn giá mới cho phần tử cần biến đổi để nâng cao
chất lượng của ảnh sau khi giấu tin là các nội dung
chính của thuật toán đề xuất.

Nhận xét 1: Dễ dàng thấy rằng, khi thuật toán thực
hiện thành công (kết thúc tại Bước 3 hoặc Bước 5), G
luôn thỏa mãn các điều kiện (3.1) và (3.2). Như vậy,
để chứng minh tính đúng đắn của thuật toán chỉ cần
chỉ ra ∏ ≠ Ø. Điều này sẽ được chứng minh trong mục
4.

Trong thuật toán đề xuất sử dụng ma trận khóa nhị
phân liên thông ‘vớ iđiê0ukiệnSUM(K) ≥ 3. Khi

Nhận xét 2: Trong Bước 5 có thể có nhiều cách chọn
(i,j) và (u,v). Dưới đây sẽ trình bày phương pháp xác
định (i,j) và (u,v) để thuật toán giấu tin có thể đạt được
tính che giấu cao.

thực hiện thành công (có giấu tin), thuật toán sẽ cho
ma trận G thỏa mãn các điều kiện:

–

1≤ SUM(MOD(G)⊗K) ≤ SUM(K) – 1

(3.1)

–

SUM(G⊗K) mod 2 = b
F và G khác nhau tối đa một phần tử

(3.2)

Đầu tiên chọn (i,j) sao cho:
(i,j) ∈ ∏ và g(i,j) = max {g(p,q)| (p,q) ∈ ∏}

Các điều kiện (3.1) và (3.2) được sử dụng để khôi
phục tin giấu.
III.2. Nội dung thuật toán giấu tin
Bước 1: Đặt s = SUM(MOD(F)⊗K)
Bước 2: Kiểm tra điều kiện giấu tin, xét hai trường
hợp:

Ở đây g(p,q) là số phần tử trên ma trận F liền kề với
(p,q) và có giá trị bằng Fp,q.

Sau khi đã có (i,j), (u,v) được chọn trong tập Y, gồm
các phần tử liền kề với (i,j) và khác tính chẵn lẻ với
Fi,j:
Ω i, j = { ( p, q ) | ( p, q ) <=> (i, j ) va ɳ Fp, q # Fi, j }

Với mỗi (p,q) ∈ Ωi, j, gọi f(p,q) là số phần tử trong

Ωi, j có giá trị bằng Fp,q.
– 16 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
Giấu b1 =1 vào F1:

Chọn (u,v) sao cho:

(H, I) ⇔ (>, ?)và Z(H, I) = max{f(p, q)|(p, q) ∈ Ω, }

Cách chọn này đảm bảo hai yêu cầu:
– Phần tử được chọn để biến đổi nằm trên khóa K và
xung quanh nó có nhiều phần tử cùng giá trị với nó
nhất.
– Giá trị thay thế khác tính chẵn lẻ với phần tử được
chọn và xung quanh phần tử được chọn có nhiều phần
tử cùng giá trị với giá trị thay thế.
Do phần tử được chọn (i,j) nằm trên khóa K
(Ki,j=1), nên sau khi thay đổi giá trị Fi,j từ chẵn sang lẻ
hoặc ngược lại thì SUM(F⊗K) sẽ thay đổi tính chẵn
lẻ, do đó ma trận G luôn thỏa mãn điều kiện (3.2). Mặt
khác cách thay đổi màu tại điểm (i,j) như vậy, sẽ rất
khó phát hiện vì xung quanh nó luôn có các điểm cùng
màu với màu mới và nhiều khả năng tồn tại các điểm
cùng màu mới màu cũ của điểm (i,j). Điều này làm
tăng tính che giấu của thuật toán.

III.3. Minh họa thuật toán

1
0
1

0
1
1

Giấu b2=1 vào F2:
s = SUM(MOD(F2)⊗K)= 4, do 0Bước 3: s mod 2 ≠ b2, sang bước 4:
∏={(1,2), (2,1), (3,2), (3,3)}
Theo nhận xét 2: g(1,2)=0, g(2,1)=0, g(3,2)=1,
g(3,3)=1, nên chọn (i,j)=(3,2);
Khi đó: Ω3,2={(2,2),(2,3),(3,1)}
f(2,3)=1, f(3,1)=0.

và

f(2,2)=1,

Chọn (u,v) = (2,2) và thay F23,2 bằng F22,2, đặt G2=F2.
Giấu b3= 0 vào F3:
s = SUM(MOD(F3)⊗K) = 1, do 0Bước 3: s mod 2 ≠ b3, sang bước 4:
∏ = {(1,2), (2,1), (3,2), (3,3)}
Theo nhận xét 2: g(1,2)=0, g(2,1)=1, g(3,2)=1,
g(3,3)=0, nên chọn (i,j)=(2,1)

Chọn (u,v)=(3,1), thay F32,1 bằng F33,1 và đặt G3 = F3.
Giấu b4=0 vào F4:
s = SUM(MOD(F4)⊗K) = 3, do 0Bước 3: s mod 2 ≠ b4, sang bước 4:

Hình 3.1 Khóa K
Dãy bít cần giấu: b1b2b3b4 = 1100, ảnh được chia
thành 4 khối:
F1

s = SUM(MOD(F1)⊗K)= 1, do 0Bước 3: s mod 2 = b1, G1 = F1

Khi đó Ω2,1={(1,1), (2,2), (3,1)} và f(1,1)=0,
f(2,2)=1, f(3,1)=1

Giả sử K bằng :
0
1
0

Tập V-1, Số 8 (28), tháng 12/2012

145
120
105

46
34
230

253
46
139

139
47
16

179
78
39

200
78
39

245
78
53

76
53
78

34
57

195
57
231

246
249
23

195
230
199

∏ = {(1,2), (2,1), (2,3), (3,2), (3,3)}
Theo nhận xét 2, chọn (i,j) = (1,2) và (u,v) = (1,1).
Thay F41,2 bằng F41,1 và đặt G4 = F4.
Như vậy, các Gi nhận được sau khi kết thúc thuật
toán giấu tin như hình sau:
G1

145 46 253 139 179 200
120 34 46 47 78 78
105 230 139 16 78 39

F3
F4
Hình 3.2 Ảnh trước khi giấu tin

Trong ví dụ này: SUM(K) = 5, dưới đây sẽ minh
họa thuật toán giấu bít bi vào khối Fi (i = 1,2,3,4).

– 17 –

245
53
53

76 34 195 195 195
53 57 57 249 230
78 64 231 23 199
G3
G4
Hình 3.3 Ảnh sau khi giấu tin

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

III.4. Thuật toán khôi phục thông tin

Chứng minh bổ đề

Giả sử G là ma trận giấu một bít tin mật và K là
ma trận khóa được sử dụng trong thuật toán giấu tin.
Dựa trên các điều kiện (3.1) và (3.2), có thể xây dựng
thuật toán khôi phục bít tin mật như sau:

Do Q1≠ Φ và Q2≠ Φ nên có thể chọn một phần tử
(i0,j0) ∈ Q1 và (u0,v0) ∈ Q2. Nếu hai phần tử
(i0,j0) (u0,v0) thì đương nhiên bổ đề đúng với (i,j)=
(i0,j0) và (u,v) = (u0,v0). Trong trường hợp hai phần tử
(i0,j0) và (u0,v0) không kề nhau, thì do K liên thông nên
phải tồn tại dãy các phần tử (pt,qt), t = 1,…,k sao cho:

Bước 1: Tính s’= SUM(MOD(G)⊗K)
Bước 2: Kiểm tra G có giấu tin hay không
Nếu s’= 0 hoặc s’= SUM(K), kết luận G không
chứa tin giấu
Trái lại, tính b = s’ mod 2, b là bít tin mật cần
khôi phục.
III.5. Tính bảo mật của sơ đồ
Mục đích của giấu tin là để bảo vệ dữ liệu được
nhúng trên các môi trường trao đổi thông tin. Vì vậy,
mỗi một sơ đồ giấu tin đều phải có tính an toàn bảo
mật bằng cách đưa vào các khóa bí mật. Khóa bí mật
được sử dụng trong cả thuật toán giấu tin và khôi phục
thông tin.
Trong lược đồ đề xuất, sử dụng một ma trận nhị
phân liên thông K cấp m×n làm khóa bí mật. Do đó số
phương án khóa xấp xỉ bằng 2mxn. Đây là một số khá
lớn, vì vậy, việc dò tìm khóa K để trích rút thông tin
mật đã nhúng trong ảnh là một việc làm tương đối khó
khăn. Như vậy, vai trò của khóa K là để ngăn ngừa
việc sử dụng trái phép thông tin mật đã nhúng trong
ảnh, làm cho quá trình trao đổi thông tin trở lên an
toàn hơn.

K pt, qt = 1, t= 1,..k
(i0,j0)

(p1,q1)

(p2,q2)

….

(pk,qk)

(u0,v0)

Nếu cả k phần tử của dãy thuộc Q2, thì bổ đề đúng
với (i,j) = (i0,j0) và (u,v) = (p1,q1). Trong trường hợp
trái lại (dãy có ít nhất một phần tử ∈ Q1), gọi (ph,qh) là
phần tử cuối cùng của dãy thuộc Q1. Nếu h= k thì bổ
đề đúng với (i,j) = (pk,qk) và (u,v) = (u0,v0). Nếu hthì do (ph,qh) là phần tử cuối cùng thuộc Q1 nên
(ph+1,qh+1) phải thuộc Q2, do đó bổ đề đúng với
(i,j)=(ph,qh) và (u,v) = (ph+1,qh+1).
Vậy bổ đề được chứng minh.
Chứng minh tính đúng đắn của thuật toán:
Trước hết từ (4.1) dễ dàng suy ra:
s = SUM(MOD(F)⊗K) = |Q1|

(4.4)

Theo nhận xét 1 trong mục 3, để chứng minh tính
đúng đắn của thuật toán chỉ cần chỉ ra ∏ ≠ Ø. Ta xét

lần lượt xét ba trường hợp: s =1, s = SUM(K)-1 và
11) Nếu s =1 thì theo Bước 4 (mục 3):
∏ = {(i,j) | Ki,j = 1, Fi,j chẵn, ∃ (u,v): (u,v) (i,j) và
Fu,v # Fi,j}

IV. TÍNH ĐÚNG ĐẮN CỦA THUẬT TOÁN

Ngoài ra từ (4.3) và (4.4) ta có:

Trước hết ta xét một số khái niệm và bổ đề sau:

|Q1| = s = 1

Đặt:
Q1 ={(i,j)| Ki,j =1 và Fi,j lẻ}

(4.1)

Q2 ={(u,v)| Ku,v =1 và Fu,v chẵn}

(4.2)

|Q2| = SUM(K) – |Q1| = SUM(K) -1
Vậy Q1 ≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra tồn tại
(u,v) ∈ Q1, (i,j) ∈ Q2 và (u,v) (i,j). Theo định nghĩa
Q1, Q2 thì: Fu,v lẻ, Ki,j= 1 và Fi,j chẵn. Từ đó suy ra (i,j)
∈ ∏, vậy ∏ ≠ Φ.

Từ (4.1) và (4.2) dễ dàng suy ra:

Q1 ∩ Q2 = Φ và |Q1| + |Q2| = SUM(K)

(4.3)

Bổ đề: Nếu Q1≠ Φ, Q2≠ Φ và K là ma trận nhị phân
liên thông thì luôn tồn tại hai phần tử (i,j) và (u,v) sao
cho:
(i,j)

2) Nếu s = SUM(K) – 1 thì theo Bước 4:

(u,v), (i,j) ∈ Q1 và (u,v) ∈ Q2

– 18 –

∏={(i,j) | Ki,j = 1, Fi,j lẻ, ∃ (u,v): (u,v)
Fu,v#Fi,j}

(i,j) và

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Ngoài ra từ (4.3) và (4.4) ta có:
|Q1| = s = SUM(K) – 1
|Q2| = SUM(K) – |Q1| =1
Vậy Q1≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra tồn tại
(i,j) ∈ Q1, (u,v) ∈ Q2 và (i,j) (u,v). Theo định nghĩa

Q1, Q2 thì: Ki,j = 1, Fi,j lẻ, Fu,v chẵn. Từ đó suy ra (i,j)
∈ ∏, vậy ∏ ≠ Φ.
3) Nếu 1< s < SUM(K) -1 thì theo Bước 4:
∏ = {(i,j) |Ki,j = 1, ∃ (u,v): (u,v)

(i,j) và Fu,v # Fi,j}

Ngoài ra từ (4.3) và (4.4) ta có:
1< |Q1| < SUM(K) – 1
b) Ảnh của lược đồ đề xuất

|Q2| = SUM(K) – |Q1| >1
Vậy Q1≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra tồn tại
(i,j) ∈ Q1, (u,v) ∈ Q2 và (i,j)
(u,v). Theo định nghĩa
Q1, Q2 thì: Ki,j = Ku,v =1, Fi,j lẻ, Fu,v chẵn. Từ đó suy ra
cả (i,j) và (u,v) đều thuộc ∏, vậy ∏ ≠ Φ.
V. THỰC NGHIỆM
Để so sánh tính che giấu của thuật toán đề xuất với
hai thuật toán Ez Stego và Fridrich, chúng tôi đã cài
đặt và thực hiện giấu tin theo cả ba thuật toán trên
cùng các tham số đầu vào được cho như sau:
– Dữ liệu nhúng là 461 bít được tạo ngẫu nhiên
– Ảnh gốc có 8 màu và kích thước 256× 256

c) Ảnh của thuật toán Fridrich

a) Ảnh gốc
Ảnh sau khi nhúng 461 bít của các thuật toán:

d) Ảnh của thuật toán Ez Stego

– 19 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
Kết quả thực nghiệm cho thấy rằng, trên các ảnh
của hai thuật toán Fridrich, Ez Stego có xuất hiện màu
cô lập, nhưng màu cô lập không xuất hiện trên ảnh của
thuật toán đề xuất. Thay vào đó, các màu bị biến đổi
của ảnh trong thuật toán đề xuất chỉ xuất hiện ở những
vị trí giáp ranh và luôn tồn tại các điểm ảnh lân cận có
màu giống với màu bị biến đổi.
6. KẾT LUẬN
Bài báo đề xuất một thuật toán giấu tin mới áp
dụng cho ảnh có bảng màu. Theo đó, dữ liệu ảnh được
chia thành các khối cùng cấp m×n, mỗi khối có thể
giấu được một bít và biến đổi nhiều nhất một phần tử
của khối. Khi cần biến đổi một phần tử, thuật toán sẽ
lựa chọn vị trí thay đổi và giá trị thay thế hợp lý để
không làm xuất hiện màu cô lập, do đó nâng cao chất
lượng của ảnh sau khi giấu tin. Kết quả thực nghiệm
chỉ ra rằng, tính che giấu của thuật toán đề xuất tốt
hơn so với hai thuật toán Ez Stego và Fridrich.
Trong [6], các tác giả G. Pan, Z. Wu, Y. Pan đã
thực nghiệm giấu tin trên cùng ảnh được sử dụng
trong bài báo này. Qua quan sát cho thấy, tính che giấu
của thuật toán [6] có phần cao hơn so với thuật toán đề
xuất, nhưng lượng thông tin giấu ít hơn. Thử nghiệm
trong [6] nhúng 289 bít, còn thực nghiệm trong bài

báo này nhúng 461 bít.
TÀI LIỆU THAM KHẢO
[1] PHẠM VĂN ẤT, NGUYỄN HIẾU CƯỜNG, ĐỖ
VĂN TUẦN, BÙI HỒNG QUẾ, TRẦN ĐĂNG
HIÊN, Một số nhận xét về phương pháp giấu tin của
Chen – Pan – Tseng, Kỷ yếu Hội thảo: Một số vấn đề
chọn lọc của Công nghệ thông tin và truyền thông,
2007

Tập V-1, Số 8 (28), tháng 12/2012

[4] J. FRIDRICH, J.DU, Secure Steganographic Methods
for Pallete Image. The 3rd Information Hiding
Workshop, Lecture Notes in Computer Science. 1768,
47-60 (2000)
[5] M.Y. WU, Y. H. HO, JIA-HONG LEE, An iterative
method of palette-based image steganography, Pattern
Recognition Letters 25, 301–309, (2004)
[6] GANG PAN, ZHAOHUI WU, YUNHE PAN, A Data
Hiding Method for Few – Color Images.
IEEE Proceedings of the 2002 International
Conference on Acoustic, Speech, and Signal
Processing, ICASSP 02, Vol. 4, 13-17 May 2002
[7] R. MACHADO. EZ STEGO,
http://www.scribd.com/doc/62118082/105/EZ-Stego
[8] S.M. KIM, ZIQIANG CHENG, KEE YOUNG YOO,
A New Steganography Scheme based on an Indexcolor Image, Sixth International Conference on
Information Technology, (2009)
[9] S. KR GHOSAL, A New Pair Wise Bit Based Data
Hiding Approach on 24 Bit Color Image using

Steganographic Technique. IEM, (2011)
[10] V. K. SHARMA, V. SHRIVASTAVA, A
Steganography Algorithm For Hiding Image In Image
By Improved Lsb Substitution By Minimizedetection,
Journal of Theoretical and Applied Information
Technology (2012)
[11] M. WU, J. LEE. A novel data embedding method for
two-color fascimile images. In Proceedings of
international symposium on multimedia information
processing. Chung-Li, Taiwan, R.O.C, 1998
[12] YU-CHEE TSENG, HSIANG-KUANG PAN. Secure
and Invisible Data Hiding in 2-Color Images.
INFOCOM 2001. Twentieth Annual Joint Conference
of the IEEE Computer and Communications Societies.
Proceedings IEEE, 887 – 896 vol.2

[2] PHẠM VĂN ẤT, ĐỖ VĂN TUẦN, NGUYỄN HIẾU
CƯỜNG, Thuật toán giấu tin dung lượng cao, Tạp chí
Khoa học Giao thông vận tải, số 19 năm 2007
[3] J. FRIDRICH, Secure steganographic methods for
palette images, Proceedings of 3rd Int. Workshop on
Information Hiding,1999.

Nhận bài ngày: 02/02/2012

– 20 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

SƠ LƯỢC VỀ TÁC GIẢ
PHẠM VĂN ẤT
Sinh ngày 12/6/1945 tại Hà Nội.

ĐỖ VĂN TUẤN
Sinh ngày 9/6/1975 tại Hải
Dương.

Tốt nghiệp Đại học năm 1967 và
tiến sĩ năm 1980 tại Trường Đại
học Tổng hợp Hà Nội. Năm 1984
nhận học hàm PGS.

Tốt nghiệp Đại học HVKTQS
năm 2002, Thạc sĩ năm 2007 tại
Trường Đại học Công nghệ –
ĐHQGHN.

Hiện giảng dạy tại Khoa CNTT –
Trường Đại học Giao thông Vận tải Hà Nội.

Hiện giảng dạy tại Khoa CNTT – Trường Cao đẳng
Thương mại và Du lịch Hà Nội.

Lĩnh vực quan tâm: Lý thuyết ma trận, xử lý ảnh, an
toàn thông tin, phân tích dữ liệu.

Lĩnh vực quan tâm: Giấu tin, mật mã, phát hiện ảnh

giả mạo

Email: phamvanat83@vnn.vn

Email: dvtuanest@gmail.com

– 21 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Phát triển thuật toán mật mã khóa công khai
dựa trên hệ mật Elgamal
Development of Public Key Cryptographic Algorithm Based on Elgamal
Cryptosystem
Lưu Hồng Dũng
1- Chọn số nguyên tố đủ lớn p sao cho bài toán

Abstract: This paper proposed a new public key
cryptographic algorithm based on the ElGamal
cryptosystem. This algorithm has the capacity of
information security and anthentication information.
The paper also offers analysis on the safety of the
proposed schemes, has shown the ability to apply it in
practice.

logarit trong Z p là khó giải.
2- Chọn g ∈ Z *p là phần tử nguyên thủy.

3- Chọn khóa mật x là số ngẫu nhiên sao cho:
1 < x < p. Tính khóa công khai y theo công thức:

y = g x mod p .

I. ĐẶT VẤN ĐỀ

1.2 Thuật toán mã hóa

Trong thực tế, nhiều ứng dụng đòi hỏi việc bảo
mật thông tin cần phải được thực hiện đồng thời với
việc xác thực về nguồn gốc và tính toàn vẹn của thông
tin. Nội dung bài báo đề xuất một thuật toán mật mã
khóa công khai được phát triển dựa trên hệ mật
ElGamal [1] cho phép giải quyết tốt các yêu cầu nêu
trên.

Giả sử người gửi là A, người nhận là B. Người gửi
A có khóa bí mật là xa và khóa công khai là ya. Người
nhận B có khóa bí mật là xb và khóa công khai là yb.
Khi đó, để gửi bản tin M cho B, với: 0 ≤ M < p ,
người gửi A sẽ thực hiện các bước như sau:
1-

Chọn

số ngẫu nhiên k thỏa
1 < k < p. Tính giá trị R theo công thức:

mãn:

R = g k mod p .

II. PHÁT TRIỂN THUẬT TOÁN MẬT MÃ
KHÓA CÔNG KHAI DỰA TRÊN HỆ MẬT
ELGAMAL

2- Sử dụng khóa công khai của B để tính:

C = M × ( y b ) k mod p

1. Hệ mật Elgamal
Hệ mật Elgama được đề xuất vào năm 1984 trên cơ
sở bài toán logarith rời rạc. Sau đó, các chuẩn chữ ký
số DSS [2] của Mỹ và GOST R34.10-94 [3] của Liên
bang Nga đã được hình thành trên cơ sở hệ mật này.
1.1 Thuật toán hình thành tham số và khóa
Các thành viên trong hệ thống muốn trao đổi thông
tin mật với nhau bằng thuật toán mật mã Elgamma thì
trước tiên thực hiện quá trình hình thành khóa như
sau:

3- Gửi bản mã gồm (C, R ) đến người nhận B.
1.3 Thuật toán giải mã
Để khôi phục bản tin ban đầu (M) từ bản mã

(C, R )

nhận được, người nhận B thực hiện các bước

như sau:

– 22 –

1- Tính giá trị Z theo công thức:

Z = R xb mod p = g k. xb mod p
2- Tính gía trị nghịch đảo của Z:

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

(

Z −1 = g k. xb

)

−1

bản mã C và gửi C cho người nhận B. Sẽ có các tình
huống xảy ra như sau:

mod p = g − k. xb mod p

3- Khôi phục bản tin ban đầu (M):

– Người nhận B không thể biết chắc chắn rằng bản tin
nhận được (M) có nguồn gốc từ người gửi A.

−1

M = C × Z mod p

– Giả sử bản mã C đã bị thay đổi thành C * và người

1.4 Tính đúng đắn của thuật toán mật mã Elgamal
Giả sử bản tin nhận được sau quá trình giải mã

nhận giải mã được bản tin M *. Trường hợp này,
người nhận không thể khẳng định được nội dung
bản tin do A gửi đi đã bị thay đổi.

(C, R ) là M, thế thì:

M = C × Z −1 mod p =

Thuật toán mật mã được đề xuất, phát triển trên cơ
sở hệ mật ElGamal sau đây sẽ là giải pháp cho các vấn
đề nêu trên.

= [(M × ( y b ) k mod p) × ( g − k. xb mod p )] mod p
= M × g k. xb × g − k. xb mod p
=M
Như vậy, bản tin nhận được sau giải mã ( M )
chính là bản tin ban đầu (M).

2. Thuật toán mật mã khóa công khai dựa trên hệ
mật Elgamal
2.1. Thuật toán hình thành tham số và khóa

1.5 Mức độ an toàn của hệ mật ElGamal

1- Sinh cặp số nguyên tố p và q đủ lớn và:

q | ( p − 1) sao cho bài toán logarit trong Z p là

Hệ mật ElGamal sẽ bị phá vỡ nếu khóa mật x hoặc
k có thể tính được. Để tính được x hoặc k, cần phải
giải một trong hai bài toán logarit rời rạc, chẳng hạn:

khó giải.
2- Chọn g = α ( p −1) / q mod p, là phần tử sinh có bậc

y = g x mod p hay: R = g k mod p .

q của nhóm Zp, nghĩa là:

Tuy nhiên, trong thực tế việc giải bài toán logarit
rời rạc này là việc khó [4].

mãn: 1 < α < ( p − 1) .
3- Khóa bí mật x là một giá trị được chọn ngẫu
nhiên trong khoảng: 1 < x < q. Khóa công khai

tin M và M * được các bản mã tương ứng là (C, R )

y được tính theo công thức:

)

và C *, R *. Khi ấy ta sẽ có:
* −1

C × (C )

1 < g < p và:

g q ≡ 1 mod p. Ở đây: α là một số nguyên thỏa

Một điểm yếu có thể bị tấn công trong hệ mã
ElGamal là khi giá trị k bị sử dụng lại. Thực vậy, giả
sử cùng một giá trị k được sử dụng để mã hóa hai bản

(

Tập V-1, Số 8 (28), tháng 12/2012

y = g x mod p

≡

4- Lựa chọn hàm băm (hash) H: {0,1} ֏ Z q
*

≡ M × ( g ) × ( M * × ( g x ) k ) −1 mod p
x k

(Ví

dụ: SHA-1, MD5).

Suy ra:

2.2 Thuật toán mã hóa

M * × C × (C * ) −1 ≡ M mod p
Nghĩa là, chỉ cần biết nội dung của một trong hai
bản tin M hoặc M * thì sẽ dễ dàng biết được nội dung
của bản tin kia.

Giả sử người gửi A có khóa bí mật là xa, khóa công
khai tương ứng là ya; người nhận B có khóa bí mật là
xb và khóa công khai là yb. Để gửi bản tin M cho B, A
thực hiện các bước như sau:

Một vấn đề được đặt ra không chỉ với hệ ElGamal
nói riêng mà với các hệ mật khóa công khai nói chung
là: Giả sử một người gửi A mã hóa bản tin M được

– 23 –

1- Chọn số ngẫu nhiên k thỏa mãn: 1 < k < q .
2- Tính giá trị R theo công thức:

R = g k mod p

(1)

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Chú ý:
Trường hợp sử dụng giá trị H ( x || M ) thay cho k,

3- Tính thành phần E theo công thức:

E = H ( R || M ) mod q

Tập V-1, Số 8 (28), tháng 12/2012

(2)

thuật toán giải mã vẫn được giữ nguyên.

4- Tính thành phần S theo công thức:

S = [k − xa × E ] mod q

2.4 Tính đúng đắn của thuật toán mới đề xuất

(3)

5- Sử dụng khóa công khai của B để tính thành phần
C theo công thức:

C = M × ( yb ) k mod p

(4)

6- Gửi bản mã gồm (C, E, S ) đến người nhận B.

Tính đúng đắn của hệ mật mới đề xuất là sự phù
hợp giữa thuật toán giải mã với thuật toán mã hóa.
Điều cần chứng minh ở đây là:
Cho: p, q là 2 số nguyên tố độc lập,

Tương tự thuật toán Elgamal, thuật toán mật mã
mới đề xuất có thể bị tấn công khi sử dụng lại giá trị
của k. Có thể khắc phục yếu điểm trên nếu sử dụng giá
trị H ( x || M ) thay cho k, với H(.) là hàm băm kháng va
chạm (chẳng hạn SHA-1, MD5,…) và “||” là toán tử
nối/xáo trộn xâu. Khi đó thuật toán mã hóa sẽ được
mô tả lại như sau:
1- Tính giá trị R theo công thức:

H : {0,1} ֏ Z p, R = g H ( xa ||M ) mod p ,
*

E = H ( R || M ) mod q, S = [ H ( xa || M ) − xa × E ] mod q ,

C = M × ( yb ) H ( xa ||M ) mod p .

Nếu: R = ( g ) S × ( y a ) E mod p, M = C × ( R ) − x mod p ,
b

E = H ( R || M ) mod q thì: M = M và E = E .

2- Tính thành phần E theo công thức:

Chứng minh:

E = H ( R || M ) mod q
3- Tính thành phần S theo công thức:
S = [ H ( xa || M ) − xa × E ] mod q

Thật vậy, thay (3) vào (5) ta có:

R = g S × y a mod p
E

= g k − xa ×E × y a mod p
E

4- Sử dụng khóa công khai yb của người nhận để
tính thành phần C theo công thức:
H ( xa || M )

= g k × g − xa × E × y a mod p
E

= R × ya

mod p

−E

× y a mod p

2.3 Thuật toán giải mã
Từ bản mã (C, E, S ) nhận được, B khôi phục và

Từ (8) suy ra:

kiểm tra nguồn gốc cũng như tính toàn vẹn của bản tin
ban đầu (M) như sau:

Thay (4) và (9) vào (6) ta có:

R = g k mod p

= {M × y b mod p ×
k

(5)

× ( g k ) − xb mod p} mod p =

2- Khôi phục bản tin ban đầu theo công thức:

M = C × (R )

mod p

= M × yb × yb
k

(6)

−k

mod p = M

Thay (8) và (10) vào (7) ta được:

3- Tính thành phần E theo công thức:

E = H ( R || M ) mod q

(9)

M = C × ( R ) − xb mod p

1- Tính giá trị R theo công thức:

R = g S × ( y a ) E mod p

(8)

5- Gửi bản mã gồm (C, E, S ) đến người nhận B.

− xb

α ∈ Z *p ,

xa, xb ∈ [1, q − 1], y a = g xa mod p, yb = g xb mod p ,

R = g H ( xa || M ) mod p

C = M × yb

g = α ( p −1) / q mod p ,

E = H ( R || M ) mod q

(7)

4- Kiểm tra nếu E = E thì M = M và M có nguồn
gốc từ người gửi A.

= H ( R || M ) mod q
=E

Đây là điều cần chứng minh.

– 24 –

(10)

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
2.5 Mức độ an toàn của thuật toán mới đề xuất
Mức độ an toàn của thuật toán mới đề xuất được

đánh giá bằng:
1) Khả năng chống thám mã.

Về khả năng chống thám mã, có thể thấy rằng mức
độ an toàn của thuật toán mật mã mới đề xuất là hoàn
toàn tương đương với thuật toán Elgamal. Hệ mật sẽ
bị phá vỡ nếu khóa mật x có thể tính được từ việc giải
toán

logarit

rời

rac

Những phân tích về mức độ an toàn cho thấy khả
năng ứng dụng thuật toán mới đề xuất trong thực tế là
hoàn toàn có thể.
TÀI LIỆU THAM KHẢO.

2) Khả năng chống giả mạo về nguồn gốc và nội
dung của bản tin.

bài

Tập V-1, Số 8 (28), tháng 12/2012

như:

[1]. T. ELGAMAL. A public key cryptosystem and a

signature scheme based on discrete logarithms. IEEE
Transactions on Information Theory. 1985, Vol. IT-31,
No. 4. pp.469–472.
[2]. National Institute of Standards and Technology,

NIST FIPS PUB 186-3. Digital Signature Standard,
U.S. Department of Commerce,1994.

y = g x mod p

hay: S = [ H ( x || M ) − x × E ] mod q
Khả năng chống giả mạo về nguồn gốc và nội dung
bản tin phụ thuộc vào mức độ khó của việc tạo ra các

cặp (C, E, S ) giả mạo thỏa mãn điều kiện kiểm tra

(

của thuật toán giải mã: E = E. Giả sử cặp E *, S *

)

là giả mạo, thế thì nó cần phải thỏa mãn:

[3]. GOST R 34.10-94. Russian Federation Standard.
Information Technology. Cryptographic data
Security. Produce and check procedures of
Electronic Digital Signature based on Asymmetric
Cryptographic Algorithm. Government Committee
of the Russia for Standards, 1994 (in Russian).

E * ≡ H (( g S × y E mod p ) || M ) mod q

[4]. D.R STINSON, CRYPTOGRAPHY, Theory and
Practice, CRC Press 1995.

Với H(.) là hàm băm kháng va chạm, hơn nữa nội
dung bản tin M cũng chưa biết thì việc chọn được cặp

Nhận bài ngày: 20/03/2012

)

, S * giả mạo là hầu không thể thực hiện được.

SƠ LƯỢC VỀ TÁC GIẢ
LƯU HỒNG DŨNG
Sinh năm 1966 tại Hưng Yên.

III. KẾT LUẬN
Bài báo đề xuất một thuật toán mật mã khóa công
khai được phát triển dựa trên hệ mật ElGamal có khả

năng đồng thời:

Tốt nghiệp Đại học chuyên ngành
Vô tuyến điện tử năm 1989 và
Cao học ngành Kỹ thuật Điện tử
và Thông tin liên lạc năm 2000 tại
Học viện Kỹ thuật Quân sự.

1) Bảo mật thông tin.
2) Xác thực về nguồn gốc thông tin.
3) Xác thực về tính toàn vẹn của thông tin.
Hơn nữa, mặc dù bản mã được tạo ra bởi thuật toán
mới đề xuất bao gồm 3 thành phần (C,E,S) nhưng độ
dài của nó không lớn hơn độ dài bản mã 2 thành phần
(C,R) mà thuật toán ElGamal tạo ra.
Giả sử |p| = 512 bit, |q| = 160 bit khi đó độ dài bản
mã do thuật toán ElGamal tạo ra là: |C| + |R| = 512 bit
+ 512 bit = 1024 bit, còn độ dài bản mã do thuật toán
mới đề xuất tạo ra là: |C| + |E| + |S| = 512 bit + 160 bit
+ 160 bit = 832 bit.

Hiện là giảng viên Khoa Công nghệ Thông tin, Học
viện Kỹ thuật Quân sự.
Lĩnh vực nghiên cứu: An toàn và bảo mật thông tin,
An ninh mạng máy tính.
Email: luuhongdung@gmail.com

– 25 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT

Tập V-1, Số 8 (28), tháng 12/2012

Một phương pháp lọc cộng tác dựa trên mô hình
đồ thị hai phía
A Collaborative Filtering Method Based on Bipartite Graph Model
Mai Thị Như và Nguyễn Duy Phương
Abstract: Collaborative filtering is a technique to
predict the utility of items for a particular user by
exploiting the behavior patterns of a group of users
with similar preferences. This method has been widely
successful in many e-commerce systems. In this paper,
we present an effective collaborative filtering method
based on general bipartite graph representation. The
weighted bipartite graph representation is suitable for
all of the real current data sets of collaborative
filtering. The prediction method is solved by the basic
search problem on the graph that can be easy to
implement for the real applications. Specially, the
model tackled the effect of the sparsity problem of
collaborative filtering by expanding search length
from the user node to the item node. By this way, some
users or items can not be detemined by the
correlations but can be computed by the graph model.
Experimental results on the real data sets show that
the proposed method improve significantly prediction
quality for collaborative filtering.
I. PHÁT BIỂU BÀI TOÁN LỌC CỘNG TÁC
Cho tập hợp hữu hạn U = {u1, u2,…, uN} là tập

gồm N người dùng, P = {p1, p2,…, pM} là tập gồm M
sản phẩm. Mỗi sản phẩm px∈P có thể là hàng hóa,
phim, ảnh, tạp chí, tài liệu, sách, báo, dịch vụ hoặc bất
kỳ dạng thông tin nào mà người dùng cần đến. Để
thuận tiện trong trình bày, ta viết px∈P ngắn gọn thành
x∈P; và ui∈U là i∈U.
Mối quan hệ giữa tập người dùng U và tập sản
phẩm P được biểu diễn thông qua ma trận đánh giá
R = (rix), i = 1…N, x = 1…M. Mỗi giá trị rix biểu diễn

đánh giá của người dùng i∈U cho sản phẩm x∈P. Giá
trị rix có thể được thu thập trực tiếp bằng cách hỏi ý
kiến người dùng hoặc thu thập gián tiếp thông qua cơ
chế phản hồi của người dùng. Giá trị rix = ∅ được hiểu
người dùng i chưa đánh giá hoặc chưa bao giờ biết đến
sản phẩm x.
Tiếp đến ta ký hiệu, Pi ⊆P là tập các sản phẩm
được đánh giá bởi người dùng i∈U và Ux⊆U là tập các
người dùng đã đánh giá sản phẩm x∈P. Với một người
dùng cần được tư vấn a∈U (được gọi là người dùng
hiện thời, hay người dùng tích cực), bài toán lọc cộng
tác là dự đoán đánh giá của người dùng a đối với
những mặt hàng x∈(P\Pa), trên cơ sở đó tư vấn cho
người dùng a những sản phẩm được đánh giá cao.
Bảng 1 thể hiện một ví dụ với ma trận đánh giá R
= (rij) trong hệ gồm 5 người dùng U = {u1, u2, u3, u4,
u5} và 7 sản phẩm P = {p1, p2, p3, p4, p5, p6, p7,}. Mỗi
người dùng đều đưa ra các đánh giá của mình về các
sản phẩm theo thang bậc {1,2,3,4,5}. Đối với tập dữ
liệu MovieLens [11], rix = 5 được hiểu là người dùng i

đánh giá phim x ở mức độ “rất tốt”; rix = 4 được hiểu
là người dùng i đánh giá “tốt”; rix = 3 được hiểu là
người dùng i đánh giá phim x ở mức độ “bình
thường”; rix = 2 được hiểu là người dùng i đánh giá
phim x ở mức độ “kém”; rix = 1 được hiểu là người
dùng i đánh giá phim x ở mức độ “rất kém”. Giá trị
rij=∅ được hiểu là người dùng ui chưa đánh giá hoặc
chưa bao giờ biết đến sản phẩm pj. Các ô được đánh
dấu ‘?’ thể hiện giá trị hệ thống cần dự đoán cho người
dùng u5.

– 26 –

Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT
Bảng 1. Ma trận đánh giá của lọc cộng tác.
Sản phẩm
Người
dùng
p1 p2 p3 p4 p5 p6 p7
u1
4 ∅ 1 5 ∅ 1 ∅
u2
∅ 5 2 5 1 ∅ 2
u3

∅

Tập V-1, Số 8 (28), tháng 12/2012

Hình 1. Đồ thị hai phía cho lọc cộng tác
II. CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN
QUAN
Có hai hướng tiếp cận chính giải quyết bài toán
lọc cộng tác bằng mô hình đồ thị: Lọc cộng tác dựa
trên mô hình đồ thị tổng quát và Lọc cộng tác dựa trên
mô hình đồ thị hai phía [3,4,6,7]. Để thuận tiện cho
việc trình bày mô hình đề xuất, chúng tôi tóm tắt lại
những nghiên cứu về mô hình đồ thị hai phía cho lọc
cộng tác của Huang và các cộng sự [3,4].
Trong mô hình này, Huang xem xét bài toán lọc
cộng tác như bài toán tìm kiếm trên đồ thị hai phía,
một phía là tập người dùng U, phía còn lại là tập sản
phẩm P. Cạnh nối giữa người dùng i∈U đến sản phẩm
x∈P được thiết lập nếu người dùng i đánh giá “tốt”
hoặc “rất tốt” sản phẩm x. Ví dụ với ma trận đánh giá
được cho trong Bảng 1, các giá trị đánh giá rix =4, rix =
5 sẽ được biến đổi thành 1, những giá trị còn lại được
biến đổi thành 0. Khi đó, ma trận kề biểu diễn đồ thị
hai phía được thể hiện trong Bảng 2, đồ thị hai phía
tương ứng theo biểu diễn được thể hiện trong Hình 1.
Bảng 2. Ma trận kề biểu diễn đồ thị hai phía.

Người
dùng

Sản phẩm
p1

Xem thêm: Nâng cao khả năng ứng dụng công nghệ thông tin vào dạy, học ở Học viện Lục quân hiện nay

Phương pháp dự đoán trên đồ thị được thực hiện
bằng thuật toán lan truyền mạng để tìm ra số lượng
đường đi độ dài L từ đỉnh người dùng i∈U đến đỉnh
sản phẩm x∈P. Những sản phẩm x∈P có số lượng
đường đi nhiều nhất đến người dùng i∈U sẽ được
dùng để tư vấn cho người dùng này [3].
Với phương pháp biểu diễn và dự đoán nêu trên,
chúng tôi đã tiến hành kiểm nghiệm trên các bộ dữ
liệu thực và nhận thấy một số những hạn chế dưới đây.
Thứ nhất, biểu diễn của Huang chỉ quan tâm đến
các giá trị đánh giá “tốt” hoặc “rất tốt” và bỏ qua các
giá trị đánh giá “kém” hoặc “rất kém”. Đối với các hệ
thống lọc cộng tác thực tế, mức đánh giá của người
dùng được chia thành nhiều thang bậc khác nhau (tập
dữ liệu MovieLens có 5 mức đánh giá, tập
BookCrossing có 10 mức đánh giá) [11,12]. Chính vì
vậy, biểu diễn này chưa thực sự phù hợp với các hệ
thống lọc cộng tác hiện nay. Mặt khác, các phương
pháp dự đoán của lọc cộng tác được thực hiện dựa trên
thói quen sử dụng sản phẩm của cộng đồng người
dùng có cùng sở thích, do vậy các giá trị đánh giá
“tốt” hay “không tốt” đều phản ánh thói quen sử dụng

Xem thêm: 6 ứng dụng báo thức khó đỡ tặng cho những người thích ngủ nướng trong năm mới

sản phẩm của người dùng. Việc bỏ qua các giá trị
“không tốt” sẽ ảnh hưởng rất nhiều đến chất lượng dự
đoán thói quen sử dụng sản phẩm của người dùng.
Thứ hai, đối với các hệ thống lọc cộng tác số
lượng giá trị đánh giá rix=∅ nhiều hơn rất nhiều lần số
lượng giá trị đánh giá rix≠∅. Vì vậy, việc bỏ qua các
giá trị “không tốt” khiến cho vấn đề dữ liệu thưa của
lọc cộng tác trở nên trầm trọng hơn. Điều này có thể

– 27 –

Nguyễn Duy PhươngMột giải pháp lọc cộng tác dựa trên quy mô đồ thị haiphía26Nguyễn Đức Quang, Phạm Hồng Liên và LưuThanh TràGiải pháp sử dụng bộ lọc thích nghi Kalman cho hệ thốngước lượng kênh truyền WiMAX di động35Nguyễn Thị Thu HươngLê Ngọc MinhỨng dụng văn phạm link trong dịch máy Việt – Anh44Cao Hữu TìnhVũ Hỏa TiễnNguyễn Công ĐịnhKhảo sát mạng lưới hệ thống tự động hóa không thay đổi trên khoang tên lửa điềukhiển bằng giải pháp gas-động mômen57Danh sách phản biện Chuyên san số 2863 – 3 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 ContentsAuthorsPaper namePageTran Minh TanNguyen Van TamSecurity Enhancement for Domain Name SystemDo Van TuanPham Van AtA New Data Hiding Algorithm in Palette Images14Luu Hong DungDevelopment of Public Key Cryptographic AlgorithmBased On Elgamal Cryptosystem22Mai Thi NhuNguyen Duy PhuongA collaborative Filtering Method Based on Bipartite GraphModel26Solution of Applying Adaptive Kalman Filter for ChannelEstimation in Mobile WiMAX System35Nguyen Thi Thu HuongLe Ngoc MinhApplication of Link Grammar Formalism in Vietnamese English Translation44Cao Huu TinhVu Hoa TienNguyen Cong DinhThe Investigation on Automatic Stability System of Missilewith Lateral Impulsive Thrust57Nguyen Duc QuangPham Hong LienLuu Thanh TraList of Paper Reviewers of Special Issue No. 2863 – 4 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Nâng cao hiệu suất cao bảo mật thông tin cho mạng lưới hệ thống tên miềnSecurity Enhancement for Domain Name SystemTần Minh Tân và Nguyễn Văn TamAbstract : Domain Name Server ( DNS ) system, aroot source providing answers with IP addresses forany request for domain names, is regarded as the mostimportant part of Internet. DNS system also plays avery important part of cryptography analyticinfrastructure of Internet. Any change made to DNSsystem can make the system fall into malfunction, boosting complexity levels in dealing with triggeredissues [ 2,11 ]. Therefore, security for DNS is a vitalmust. For the time being, RSA algorithm [ 6,12 ] hasbecome the de factor standard for DNS security. However, RSA requires a longer key length of morethan 1000 bits [ 10,15 ], affecting performanceefficiency of DNS system. Hence, elliptic curvecryptography or ECC is regarded as an alternativemechanism for implementing public-key cryptography. The ECC is expected to be used not only in newgeneration mobile devices [ 13 ] but also in DNSsystem in the near future as ECC requires shorter keylength than RSA but providing the same security level. This paper focuses on introducing ECC and newfindings related to this mechanism such as key pairgeneration algorithms, key transfer, encryption anddecryption in ECC, as well as findings of the trial onthe Vietnam national domain name system dot việt nam ; these findings aims to apply for certification domainname data transfer for the DNS system of a countryand compare with the same method in RSA algorithm. I. GIỚI THIỆUBảo mật cho các mạng lưới hệ thống mạng Internet nói chungvà mạng lưới hệ thống tên miền nói riêng là một trách nhiệm hếtsức quan trọng và cấp bách trong thực trạng lúc bấy giờ. Tiến triển theo thời hạn, các cuộc tiến công vào mạngInternet ở Nước Ta và trên quốc tế đang diễn ra ngàycàng nhiều với hình thức ngày một phức tạp, phạm vingày càng lớn hơn. Thực tế đã có những trường hợp, những thời gian tin tặc trải qua việc tiến công vàohệ thống sever tên miền ( DNS ) đã làm tê liệt mạngInternet trên diện rộng trong nhiều giờ gây thiệt hạilớn về bảo mật an ninh cũng như kinh tế tài chính. Để xử lý vấn đềan toàn cho mạng lưới hệ thống DNS, công nghệ tiên tiến bảo mậtDNSSEC ( DNS Security Extensions ) đã được nghiêncứu và đang được đưa vào vận dụng trong thời hạn qua [ 6 ]. Năm 1976, Whifield Diffie và Martin Hellman đãđưa ra khái niệm mã bảo mật thông tin khóa công khai minh bạch ( PKC Public Key Cryptography ). Từ đó, nhiều ứng dụng củanó đã sinh ra và nhiều thuật toán đã được phát triển đểgiải quyết các bài toán bảo mật thông tin. Mức độ bảo mật thông tin yêucầu càng cao thì cỡ khóa phải càng lớn. Với hệ mật mãRSA đang được vận dụng trong hầu hết các ứng dụng, trong đó gồm có cả bài toán bảo mật thông tin cho DNS quacông nghệ DNSSEC [ 2,6,9 ] đã nói ở trên, để đảm bảoyêu cầu bảo mật thông tin, hiện phải cần cỡ khóa lớn hơn 1000 bit [ 10,15 ]. Thực tế, tháng 3 năm 2010, tại hội nghịDATE 2010 – Dresden Đức, các nhà khoa học AndreaPellegrini, Valeria Bertacco và Todd Austin thuộctrường Đại học Michigan đã công bố tác dụng phát hiệnmột kẽ hở trong hệ mật mã RSA, cách phá vỡ hệthống, lấy khoá bí hiểm của RSA 1024 bit chỉ trongvòng 104 giờ thay vì vài năm nếu tiến công theo cáchdò tìm lần lượt thường thì [ 15 ]. Công bố này cũngđồng nghĩa với công bố rằng, với RSA để đảm bản antoàn sẽ phải liên tục tăng độ dài khóa ( công nghệDNSSEC cho mạng lưới hệ thống DNS hiện tại thường sử dụngRSA với độ dài khóa 2048 bit ). Điều này kéo theoviệc phải tăng năng lượng thống kê giám sát của thiết bị ; làm tăngđáng kể kích cỡ các file dữ liệu được ký xác nhận ; tăng thời hạn giải quyết và xử lý và lưu lượng tài liệu phải truyền-5-Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 tải trên mạng ; yên cầu dung tích tàng trữ của bộ nhớlớn hơn, nguồn tiêu thụ nhiều hơn, … Và như vậy cũngcó nghĩa là sẽ không bảo vệ hiệu suất cao về mặt kinh tế tài chính. Năm 1985, Neal Koblitz và Victor Miller đã nghiêncứu và đưa ra những công bố về hệ mật mã bảo mậtdựa trên đường cong Elliptic ( Elliptic CurveCryptography – ECC ) có những đặc tính đặc biệt quan trọng [ 3,4,8 ] : Yêu cầu năng lượng giám sát thấp ; tiết kiệm chi phí bộnhớ ; tiết kiệm ngân sách và chi phí băng thông ; tiết kiệm chi phí nguồn năng lượng ; tínhbảo mật cao. Từ những đặc thù nổi trội ấy, nhiều nhàkhoa học đã đi sâu vào nghiên cứu hệ mật mã bảo mậtđường cong Elliptic [ 1,7,10,11 ] và trong bước đầu đã có cácứng dụng vào một số ít nghành nghề dịch vụ bảo mật thông tin, đặc biệt quan trọng chocác thiết bị thông tin di động [ 13 ], thiết bị USB [ 9 ]. Phát triển các hiệu quả này, Công ty Certicom Công ty đi đầu trong nghành nghề dịch vụ nghiên cứu hệ mật mãbảo mật ECC [ 16 ], đã nghiên cứu, tiến hành một sốứng dụng và công bố các số liệu so sánh về mức độbảo mật giữa các hệ mật mã RSA và ECC. Theo đóvới độ dài khóa 160 bit, hệ mật mã ECC đã có độ bảomật tương tự với hệ mật mã RSA-1024 bit ; và vớiđộ dài khóa 224 bit, hệ mật mã ECC có độ bảo mậttương đương với hệ mật mã RSA-2048 bit [ 3 ]. Bảng 1. So sánh độ dài khóa của các hệ mật mã vớicùng mức độ bảo mật thông tin [ 3 ] Hệ mậtmãKích thước khóa ( tính theo bit ) Khóa đốixứng56RSA / DSA512 1024 2048 3072 7680ECC1128016011222412825619238425615360512 Hình 1. So sánh mức độ bảo mật thông tin giữa ECC vớiRSA / DSA [ 13 ] Do size khóa nhỏ và năng lực bảo mật thông tin caonên trong quy trình tiến độ vừa mới qua, ECC hầu hết đượcnghiên cứu để trong bước đầu vận dụng cho các ứng dụngtrên thiên nhiên và môi trường mạng có số lượng giới hạn về thông lượngtruyền tài liệu, các thiết bị có số lượng giới hạn về năng lượng xửlý, năng lực tàng trữ ( đặc biệt quan trọng là với các thiết bị diđộng ) [ 13 ]. Tuy nhiên với các lợi thế về mức độ bảomật và size khóa nhỏ như đã nói ở trên, ECChoàn toàn hoàn toàn có thể được vận dụng cho các mạng lưới hệ thống lớnnhư DNS để thay thế sửa chữa, khắc phục các điểm yếu kém vềđộ dài khóa của RSA. Bài báo này chúng tôi sẽ đềxuất giải pháp setup hệ mật mã ECC lên các giaodịch trao đổi tài liệu giữa các sever trong hệ thốngDNS để nâng cao tính bảo mật thông tin và hiệu năng cho hệthống này. Trong [ 1 ], tác giả đã chỉ ra những bước cơ bản đểxây dựng thuật toán bảo mật thông tin bằng đường congElliptic, tuy nhiên mới dừng lại ở công thức tổng quanhoặc ở ví dụ đơn cử bằng số. Ở đây, chúng tôi sẽ xâydựng chi tiết cụ thể các thuật toán tạo khóa, chuyển khóa, mãhóa và giải thuật trên ECC một cách đơn thuần và rõ rànghơn nhằm mục đích giảm số bước triển khai. Đây là nền tảng đểxây dựng hệ mật mã ECC. – 6 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTrong các nội dung tiếp theo, Phần 2 chúng tôi sẽtrình bày phát biểu bài toán hệ mật mã đường congElliptic ( ECC ) và tác dụng thiết kế xây dựng một số ít thuật toántrong ECC để vận dụng cho việc xác nhận trong quátrình trao đổi tài liệu trên mạng Internet ; Phần 3 trìnhbày tác dụng thực nghiệm ECC, ứng dụng các thuậttoán nói trên trong việc xác nhận tài liệu tên miềntrong mạng lưới hệ thống DNS cấp vương quốc, so sánh với cách sửdụng giải pháp tựa như bằng RSA ; sau cuối làphần Tóm lại. Tập V-1, Số 8 ( 28 ), tháng 12/2012 Tập các điểm trên đường cong Elliptic ( E ) có cácđặc điểm sau : Điểm Θ là điểm thuộc ( E ) nằm ở vô cùng, được gọi là thành phần trung hòa. Với mỗi điểm P = ( x, y ), thành phần đối của P làđiểm – P = ( x, – y ), ta định nghĩa tổng hai điểmP + ( – P ) = P-P = Θ. Hay – P là điểm đối xứngcủa P qua trục Ox. Với 2 điểm P = ( xP, yP ) và Q = ( xQ, yQ ) với xP ≠ xQ, một đường thẳng đi qua hai điểm P, Q sẽgiao với ( E ) tại một điểm duy nhất. Ta địnhnghĩa điểm R = – ( P + Q. ). Nếu đường thẳng nàylà tiếp tuyến của ( E ) tại điểm P hoặc Q thìtương ứng R ≡ P hoặc R ≡ Q. Điểm đối xứng củaR là – R được gọi là điểm tổng của P và Q.Đường thẳng đi qua P và – P ( tức P và Q cócùng hoành độ ), sẽ giao với ( E ) tại điểm vôcùng, do vậy R = P + ( – P ) = Θ. Để nhân đôi điểm P, ta vẽ tiếp tuyến của ( E ) tại P, tiếp tuyến này sẽ giao với ( E ) tại điểmQ, ta có Q = – ( P + P ) = – 2P. Hay – Q. = 2PII. PHÁT BIỂU BÀI TOÁNĐường cong Elliptic trên GF ( p ) hoặc Zp với sốnguyên tố p được xác lập bằng phương trình Cubic : y2 = ( x3 + ax + b ) mod p, với các thông số a và b và cácbiến x và y là các thành phần của Zp thỏa mãn nhu cầu ràng buộc ( 4 a3 + 27 b2 ) mod p ≠ 0 [ 14 ]. Như vậy ta thuận tiện nhận thấy đường cong Elliptic ( E ) có phương trình là hàm chẵn so với biến y, do đóđồ thị của ( E ) nhận trục hoành Ox là trục đối xứng. Với những đặc thù trên, tập các điểm thuộcđường cong ( E ) tạo thành một nhóm Abel. Hệ mật mã đường cong Elliptic ( ECC ) được xâydựng trên cơ sở bài toán logarith trên đường congElliptic. Độ bảo mật thông tin ECC phụ thuộc vào vào độ khó củabài toán logarith rời rạc đường cong Elliptic. Giả sử Pvà Q là hai điểm trên đường cong Elliptic sao chok * P = Q. trong đó k là một đại lượng vô hướng với P vàQ đã cho, bằng cách giám sát suy luận để thu được ktrên cơ sở thuật toán rời rạc của Q. so với P.Hình 2. Một dạng đường cong EllipticVới một điểm P cho trước và thông số k, ta hoàn toàn có thể dễdàng tính ra được điểm Q. tương ứng trên đường congElliptic. Tuy nhiên theo chiều ngược lại, để tìm ra hệsố k ( khóa k ) từ điểm Q. và điểm P lại là một bài toán ” rất khó ” nếu như thông số k là 1 số ít đủ lớn ( có độ dài224 bit ví dụ điển hình ). Dựa trên cơ sở bài toán logarit rờirạc xét trên tập các điểm thuộc đường cong Ellipticnày, hệ mật mã ECC phân phối khá đầy đủ cả 4 dịch vụ anninh : mã hóa, xác nhận, ký số và trao đổi khóa ; đảm-7-Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Thuật toán tạo khóa : Hai bên gửi A và nhận B.bảo cho việc kiến thiết xây dựng một hạ tầng xác nhận khóacông khai trên Internet. Do đó một trong những thuậttoán đa phần trong ECC là tạo khóa, chuyển khóa, mãhóa và giải thuật [ 14 ]. Thống nhấtTrên cơ sở bài toán này, chúng tôi yêu cầu các thuậttoán đơn cử : Chọn ngẫunhiên nB < nChọn ngẫunhiên nA < nnA1. Tạo khóa : – Đường Elliptic – T ( p, a, b, G, n, h ) nBĐường cong Elliptic trên trường GF ( p ) có dạng : y2 = ( x3 + ax + b ) mod p ( 1 ) PA = nA * G ( XA, YA ) Tham số hệ mật mã ECC trên trường nguyên tốhữu hạn Fp. [ 4 ] : T = ( p, a, b, G, n, h ) đã nói ở trên với các tham số p, a và b đã chọn. Lấyđiểm cơ sở G từ nhóm Ep ( a, b ) trên đường congElliptic, bậc của nó phải là một giá trị n lớn [ 14 ]. Bậcn của điểm G trên đường cong Elliptic được xác địnhbằng số nguyên dương bé nhất n sao cho n * G = 0 [ 14 ]. PB = nB * G ( XB, YB ) Cặp khóa ( 2 ) nATrong đó : p là số nguyên dương xác lập trườngnguyên tố hữu hạn Fp và chọn [ log2P ] ∈ { 192, 224,256, 384, 512 } ; a, b là các thông số ∈ Fb xác lập đườngcong trên Elliptic E ( Fb ) trên trường Fb ( 1 ) ; h là phầnsố thập phân, h = # E ( Fb ) / n với # E ( Fb ) là số các điểmthuộc đường cong E ( Fb ). Theo các bước tạo khóa được xác lập tại [ 14 ], chúng tôi thiết kế xây dựng thuật toán như Hình 3. Cặp khóaPAPBHình 3. Thuật toán tạo khóa2. Thuật toán trao đổi khóaThuyết minh thuật toán : Đầu vào : Bên gửi A và Bên nhận B thống nhấtđường cong Elliptic và tham số hệ mật mãđường cong Elliptic T.nAa ‘ PAb’nBPBĐầu ra : Khóa công khai minh bạch của A : PA và khóacông khai của B : PB cần được thiết lập. Các bước thuật toán : 1. A chọn ngẫu nhiên 1 số ít nguyên dương nA < n. 2. A xác lập tích PA = nA * G = ( xA, yA ) K = nA * PBKhóachia sẻK = nB * PACặp khóa công khai minh bạch và khóa riêng của A là ( PA, nA ) 3. B chọn ngẫu nhiên số nguyên nB < n và tínhK = nA * PB = nA * ( nB * G ) = nB * ( nA * G ) = nA * nB * GPB = nB * G = ( xB, yB ) Cặp khóa công khai minh bạch, khóa riêng của B là ( PB, nB ). Hình 4. Thuật toán trao đổi khóa-8-nBCác công trình nghiên cứu, phát triển và ứng dụng CNTT-TTThuyết minh thuật toán : Thuật toán trao đổi khóa được hình thành sau khibên A và bên B đã được tạo khóa PA và PB biểu lộ ởđiểm a, b tương ứng trên hình 3 như đã nói ở trên. Thuật toán được diễn đạt như sau : • Đầu vào : Cặp khóa PA và PB • Đầu ra : PA B ; PB AXác nhận đúng đối tượng người tiêu dùng cần liên kết thông tinbằng tác dụng hai bên tìm được khóa san sẻ chung K.Tập V-1, Số 8 ( 28 ), tháng 12/2012 • Đầu vào : A muốn gửi bản tin M cho B. • Đầu ra : Văn bản mã cM • Các bước triển khai : 1. A chọn ngẫu nhiên 1 số ít nguyên dương thỏamãn 0 < k < n và tính : c1 = k * G và c2 = M + k * PBtrong đó PB là khóa công khai minh bạch của B. 2. A gửi văn bản đã mã hóa cM = { c1, c2 } cho B.Thuật toán giải mãCác bước thực thi : { c1, c2 } 1. A truyền khóa PA cho B ; B truyền khóa PB choA. 2. Cả A và B tính khóa san sẻ : • Phía A : Lấy nA của mình nhân với khóa PBnhận được từ B tạo ra : K = nA * PB = nA * ( nB * G ) = nA * nB * G • Phía B : Lấy nB của mình nhân với khóa PAnhận được từ A tạo ra : K = nB * PA = nB * ( nA * G ) = nA * nB * GNhư vậy cả A và B đều nhận được K giống nhau. nBnB * c13. Thuật toán mã hóa và giải mãHình 6. Lưu đồ thuật toán giải mãThuật toán mã hóa và giải thuật Elliptic được Bellaervà Rogaway đề xuất kiến nghị [ 3 ], thực ra là một biến thể củahệ mật mã công khai minh bạch Elgamal. Ở đây chúng tôi cụ thểhơn dưới dạng lưu đồ thuật toán và đơn thuần hơn bằngcách bỏ lỡ thủ tục tính cặp khóa, tính bản mã sửdụng. PBĐầu ra : Khôi phục lại văn bản M do A gửi đến. Đầu vào ở B : B nhận được văn bản mã CM = { c1, c2 } Thuật toán mã hóa : c2c1Các bước triển khai : B tách c1 và nhân c1 với khóa riêng nB của nóvà lấy c2 trừ đi tác dụng đó : c2 – nB * c1 = M + k * PB – nB * ( k * G ) = M + k * ( nB * G ) – nB * ( k * G ) = Mc1 = k * GVậy đã thực thi xong giải thuật. c2 = M + k * PNhận xét : cM = { c1, c2 } Hình 5. Lưu đồ thuật toán mã hóaThuật toán này không nhu yếu kiểm tra điểm R cóthuộc đường cong Elliptic hay không ; không cần tínhđiểm Z = k * k * R như trong [ 1,3,14 ] làm cho tốc độtính nhanh hơn. – 9 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Bảng 2. Tổng hợp số liệu về thời hạn ký xác nhận và kích cỡ các zone file tên miền. việt nam trước và sau khi kýbằng DNSSEC với RSA-2048 bit và ký bằng ECC-224 bit. ZoneKích thướczone file banđầu ( Bytes ). vn.com.vn.net.vn.org.vn.edu.vn.ac. vn3 520 6833 495 013120 257142 423263 3675 765K ích thước zone file sau khi kýxác thực ( bytes ) Với DNSSEC sửVới ECCdụng RSA-2048 bit224 bit27 126 82224 357 519840 5841 078 0181 749 85642 8856 337 2305 941 522198 424243 544442 45610 492III. KẾT QUẢ THỰC NGHIỆMTrên cơ sở các thuật toán yêu cầu ở trên, chúng tôiđã sử dụng ngôn từ lập trình Java để thiết lập các thuậttoán, vận dụng vào quy trình xác nhận trong các giaodịch trao đổi tài liệu tên miền giữa sever DNSchính ( Primary DNS Server ) và các sever phụ ( Secondary DNS Server ). Thí nghiệm được thực hiệntrên các zone file tài liệu tên miền được lấy trực tiếpvề từ mạng lưới hệ thống DSN vương quốc. Để bảo vệ bảo đảm an toàn và dự trữ bổ trợ, san tảicho nhau, mạng lưới hệ thống DNS được phong cách thiết kế theo quy địnhsẽ gồm một sever DNS chính và nhiều máy chủDNS phụ. Theo các mốc thời hạn định kỳ tùy thuộcvào chính sách khai báo trên sever DNS chính, các máychủ DNS phụ sẽ tự động hóa liên kết với sever DNSchính để tải các file dữ liệu tên miền đã có sự thay đổitrên sever chính về sever phụ để cung ứng việccập nhật kịp thời các đổi khác nhằm mục đích vấn đáp chính xáccác truy vấn về tên miền từ các máy tính trên mạngInternet được hỏi đến nó. Quá trình này được gọi là cơchế zone transfer trong tiến trình quản trị hệ thốngDNS. Để bảo mật thông tin cho quy trình đồng điệu tài liệu này, ngoài giải pháp phần cứng ( khai báo thông số kỹ thuật mạngchỉ được cho phép các sever phụ có địa chỉ IP từ trongmột list đã được định nghĩa trước mới có quyềnkết nối vào sever chính ), hiện chỉ mới có côngnghệ bảo mật thông tin DNSSEC sử dụng RSA đang được ápThời gian ký ( giây ) Với DNSSEC sửdụng RSA-2048 bitVới ECC224 bit171, Số tênmiềnđượcký69 53059 4832 0692 6844 232108 dụng là có tiến hành việc ký xác nhận, mã hóa dữ liệutên miền trong quy trình trao đổi giữa các máy chủDNS với nhau. Ở đây, chúng tôi đã thiết kế xây dựng chươngtrình ký xác nhận, mã hóa, giải thuật bằng ECC tương tựnhư các bước làm của DNSSEC sau đó lần lượt sửdụng ECC để thực thi việc ký xác nhận, mã hóa dữliệu trên các zone tên miền vương quốc gồm có. vn ,. com.vn ,. net.vn ,. org.vn ,. edu.vn và. ac.vn và so sánhvới các tác dụng đã thu được bằng giải pháp sửdụng DNSSEC.Các tác dụng thu bằng hai giải pháp được đem raso sánh theo các tiêu chuẩn sau : 1 / Thời gian ký xác nhận ; 2 / Kích thước zone file sau khi ký xác nhận. Chi tiếtđược biểu lộ trong Bảng 2. Kết quả so sánh này cho thấy, sau khi ký xác thựcbằng RSA-2048 bit với DNSSEC, size các zonefile tăng trung bình giao động 7,31 lần, trong khi đó sau kýxác thực bằng ECC-224 bit size chỉ tăng bìnhquân 1,74 lần so với file tài liệu gốc. Về thời hạn kýxác thực, khi sử dụng RSA-2048 bit sẽ lâu hơn bìnhquân 7,8 lần so với việc ký bằng ECC-224 bit theothuật toán đã đề xuất kiến nghị. Tổng hợp so sánh hiệu quả thực nghiệm trên cáczone file được lấy liên tục mỗi khi có sự đổi khác cácbản ghi tên miền trên zone của sever DNS chínhtrong vòng 24 giờ liên tục ( theo chính sách nhu yếu máychủ DNS phụ update hàng loạt nội dung file mỗi khicó biến hóa ) được biểu lộ trên các sơ đồ sau : – 10 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 DNSSEC với cùng một mức độ bảo mật thông tin. Việc sử dụngECC đã làm giảm tương đối thời hạn, tài liệu phảitruyền tải trên mạng trong quy trình đồng nhất tên miềngiữa sever DNS chính và các sever DNS phụ, đồng thời tiết kiệm ngân sách và chi phí đáng kể băng thông ( hiện tại hệthống DNS vương quốc đang phải đồng điệu tài liệu thườngxuyên trong ngày giữa sever chính và 26 máy chủphụ đặt tại các khu vực khác nhau trên toàn thế giới ). Việcứng dụng ECC sẽ nâng cao rõ ràng hiệu năng cho hệthống sever tên miền. IV. KẾT LUẬNBài báo này nghiên cứu vận dụng mã bảo mật thông tin đườngcong Elliptic, trong đó đã : Hình 7. So sánh kích cỡ zone file tên miền sau khiký xác nhận với RSA-2048 bit và ECC-224 bit – Xây dựng lưu đồ thuật toán tạo khóa dựa trênđường cong Elliptic và tham số T ( p, a, b, G, n, h ), giúp cho việc đo lường và thống kê rõ ràng và đơn thuần. Xây dựng thuật toán trao đổi khóa thống nhất với thuậttoán tạo khóa và bỏ lỡ được các bước A tạo PA gửi Bvà B tạo PB gửi A như trong [ 3 ]. Đồng thời thuật toánở đây đơn thuần. – Đưa ra thuật toán mã hóa, giải thuật đơn thuần hơnso với trước đây. – Cuối cùng trong bài báo này, chúng tôi đã trìnhbày tác dụng thực nghiệm thiết lập thuật toán, áp dụngthử nghiệm trên các file dữ liệu tên miền được lấy trựctiếp về từ mạng lưới hệ thống DSN vương quốc ( các file trên thực tếsẽ tham gia trong quy trình trao đổi tài liệu tên miềngiữa sever DNS vương quốc ). So sánh thời hạn ký xácthực, kích cỡ các file dữ liệu sau khi tiến hành thửnghiệm bằng ECC-224 bit qua các thuật toán được xâydựng trong bài báo với các tác dụng đã thu được khi sửdụng công nghệ DNSSEC sử dụng RSA-2048 bit. Kếtquả thực nghiệm đã chứng minh và khẳng định được tính ưu việt củaviệc ứng dụng các thuật toán trên ECC đã được đềxuất trong bài báo so với chiêu thức thông dụnghiện nay là RSA.Hình 8. So sánh thời hạn ký xác nhận bằng RSA2048 bit và ECC-224 bit trên các zone file gốcNhư vậy, rõ ràng ECC có các ưu điểm vượt trộivề thời hạn giải quyết và xử lý và đặc biệt quan trọng là làm giảm đáng kể kíchthước các zone file tài liệu tên miền sau khi được kýxác thực so với giải pháp dùng RSA trongTừ những nghiên cứu và phân tích trên, ta thấy việc nghiên cứu, ứng dụng mã bảo mật thông tin đường cong Elliptic – ECC nhưnhững hiệu quả đã đưa ra đã đạt nhu yếu làm tăng tínhbảo mật hơn so với RSA, đồng thời với ba thuật toán – 11 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTđã nêu làm đơn thuần số bước thống kê giám sát. Đây sẽ là nềntảng cơ sở để xử lý việc tránh phải liên tục nângđộ dài khóa như RSA mà vẫn phân phối được yêu cầuvề bảo mật thông tin ( khó phá khóa ) với size khóa nhỏhơn. Việc vận dụng mã bảo mật thông tin đường cong Elliptic ECC trong các mạng lưới hệ thống lớn như DNS là một hướng điđúng và trọng tâm trong thời hạn tới. Trong hướngnghiên cứu sắp tới, chúng tôi sẽ lan rộng ra xét chọnmiền tham số cho đường cong Elliptic để sử dụng làmmã bảo mật thông tin. TÀI LIỆU THAM KHẢO [ 1 ] ANOOP MS, Elliptic Curve Cryptography. AnImplementation Guide. anoopms@tataelxsi.co.in [ 2 ] B. WELLINGTON, Domain Name System Security ( DNSSEC ) signing Authority, RFC 3008, InternetEngineeringTaskForce, November2000http : / / www.ietf.org/rfc/rfc3008.txt [ 3 ] CERTICOM RESEARCH, SEC1 : Elliptic CurveCryptography, Version 1.0, September 2000, http://www.secg.org/collateral/sec1_final.pdf [ 4 ] CERTICOM RESEARCH, SEC2 : RecommendedElliptic Curve Domain Parameters, Version 2.0 January 27, 2010, www.secg.org/download/aid784/sec2-v2.pdf [ 5 ] DARRELHANKERSON, JULIOLÓSPEZHERNANDERZ, ALFRED MENEZES, SoftwareImplementation of Elliptic Curve Cryptography overBinary Fields, CHES 2000. [ 6 ] DANIEL MASSEY, ED LEWIS and OLAFURGUDMUNDSSON, Public Key Validation for the DNSSecurity Extensions, DARPA Information SurvivabilityConference và Exposition II, 2001. DISCEX ‘ 01. Proceedings, Print ISBN : 0-7695 – 1212 – 7, 2001. [ 7 ] F. HESS, Generalising the GHS attack on the EllipticCurve Discrete logarithm problem, LMS J. Comput, Math 7, 2004. [ 8 ] JACOB SCOTT, EllipticDecember 14, 2010. CurveTập V-1, Số 8 ( 28 ), tháng 12/2012 International Journal of Computer Science andNetwork Security, VOL. 11 No. 11, November 2011. [ 10 ] N. GURA A. PATEL, A. WANDER, H. EBERLE andS. CSHANTZ, ComparingEllipticCurveCryptography and RSA on 8 bit CPUS, Proccedings ofWorkshop on Cryptographic Hardware and EmbeddedSystems ( CHES 2004 ) 6 th Internetional Workshop 2004 [ 11 ] M. ABDALLA, M. BELLARE and P.ROGAWAY, DHAES. An encryption Scheme based on the Difflie Hellman problem, Submission to P1363a : Standerdspecifications for Public-Key Cryptography, AdditionalTechniques, 2000. [ 12 ] REZA CURTMOLA, ANIELLO DEL SORBO, GIUSEPPE ATENIESE, On the Performance andAnalysis of DNS Security Extensions, Cryptology andNetwork Security, 4 th International Conference, CANS2005. [ 13 ] WENDY CHOU, Elliptic Curve Crytography and itsApplications to Mobile Devices, University ofMaryland, CollegePark, 2003 http://www.cs.umd.edu/Honors/reports / ECCpaper. pdf [ 14 ] W. STALLINGS, CrypotographySecurity, Fourth Edition 2009. andNetwork [ 15 ] ANDREA PELLEGRINI, VALERIA BERTACCO andTODD AUSTIN, Fault Based Attack of RSAAuthentication, Design, Automation and Test in Europe ( DATE ) conference in Dresden on March 10.http : / / web.eecs.umich.edu/~valeria/research/ publications/DDTE10RSA.pdf [ 16 ] Certicom Website : http://certicom.comNhận bài ngày : 25/05/2012 Cryptography, [ 9 ] JAGDISH BHATTA and LOK PRAKASH PANDEY, Perfomance Evaluation of RSA Variants and EllipticCurve Cryptography on Handheld Devices. IJCSNS – 12 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTSƠ LƯỢC VỀ TÁC GIẢTập V-1, Số 8 ( 28 ), tháng 12/2012 NGUYỄN VĂN TAMSinh ngày 21/02/1947. TRẦN MINH TÂNSinh ngày 02/9/1968 tại HưngYên. Tốt nghiệp Đại học Sư phạmHà Nội I – Khoa Vật Lý năm1991, Đại học Bách khoa HàNội – Khoa CNTT năm 1996. Nhận bằng Thạc sỹ chuyênngành CNTT năm 2006 tại Trường Đại học Côngnghệ – ĐHQG TP. Hà Nội. Đang là nghiên cứu sinh tạiViện Công nghệ tin tức – Viện Khoa học và Côngnghệ Nước Ta. Tốt nghiệp Đại học CVUT, Praha, Tiệp Khắc năm1971. Bảo vệ luận án Tiến sĩ tại Viện Nghiên cứu VUMS, Praha, Tiệp Khắc năm 1977. Được phong Phó Giáo sư năm 1996. Hiện đang công tác làm việc tại Phòng Tin học viễn thông Viện Công nghệ tin tức. Lĩnh vực nghiên cứu : Công nghệ mạng và Quản trị, antoàn mạng. Điện thoại : 0913390606, 04.38362136 E-Mail : nvtam@ioit.ac.vnHi ện công tác làm việc tại Trung tâm Internet Nước Ta – BộThông tin và Truyền thông. Lĩnh vực nghiên cứu : An toàn, bảo mật thông tin trên mạngInternet, công nghệ IPv6, DNS.Điện thoại : 0913275577, 04.35564944 máy lẻ 512E mail : tantm@vnnic.net.vn- 13 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Một thuật toán giấu tin trong ảnh có bảng màuA New Data Hiding Algorithm in Palette ImagesĐỗ Văn Tuấn và Phạm Văn ẤtAbstract : This paper proposes a new algorithm toembed data in palette image. In each image block oforiginal image, this algorithm can hide a bit bymodifying at most one px of block. New color ofmodified px resembles the color of its someneighborhood pixels, so the image after hiding veryclose to the original image. The experimental resultsshowed that the invisible of proposed algorithm isbetter than algorithms Fridrich and Ez Stego. Keywords : data hiding, steganography, securitywatermarking, Palette imagesI. GIỚI THIỆUNgày nay, mạng Internet đóng vai trò quan trọngtrong việc trao đổi tài liệu giữa những người dùng. Bên cạnh những thuận tiện, yếu tố bảo mật thông tin thông tintrên Internet luôn là những thử thách so với các cấpquản lý và các nhà nghiên cứu. Trước đây, các phươngpháp mã hóa luôn là sự lựa chọn để bảo mật thông tin thông tinvà đã mang lại những thành công xuất sắc nhất định. Tuynhiên, việc truyền tải công khai minh bạch các bản mã sẽ tạo rasự chú ý quan tâm, thử thách so với các đối thủ cạnh tranh, những ngườimuốn mày mò nội dung của bản mã một cách tráiphép. Gần đây, bên cạnh các giải pháp mật mãtruyền thống, kỹ thuật giấu tin giữ vai trò quan trọngtrong các bài toán bảo mật thông tin thông tin, bảo vệ bảnquyền, xác nhận tài liệu. Giấu tin là kỹ thuật nhúng thêm thông tin vào cácdữ liệu đa phương tiện. tin tức được nhúng có thểlà các thông điệp bí hiểm cần trao đổi, hoặc là các thôngtin về mẫu sản phẩm. Dữ liệu dùng để mang thông tinnhúng thường là những dạng tài liệu phổ cập trênInternet như : ảnh, âm thanh, video. Theo [ 1 ], kỹ thuậtgiấu tin cần có một số ít đặc thù cơ bản như : tính chegiấu, tính khả nhúng và tính bảo mật thông tin. Theo định dạngảnh, các kỹ thuật giấu được chia thành hai loại chính. Loại thứ nhất, gồm các kỹ thuật giấu tin trên ảnhkhông có bảng màu [ 2,9,10 ]. Ảnh không có bảng màuthường là những ảnh có số lượng màu lớn, tài liệu ảnhchính là các giá trị màu của điểm ảnh. Lợi dụng sự hạnchế của mạng lưới hệ thống thị giác không phát hiện ra sự thayđổi nhỏ về sắc tố, các thuật toán giấu tin trên dạngảnh này thuận tiện có được tính che giấu cao bằng cáchthay đổi một lượng nhỏ giá trị màu trong vùng dữ liệuảnh. Loại thứ 2, gồm các kỹ thuật giấu tin trên ảnh cóbảng màu [ 3 ] – [ 8 ]. Đối với ảnh có bảng màu, dữ liệuảnh là chỉ số màu của điểm ảnh. Hai chỉ số gần nhaucó thể tham chiếu tới hai màu rất khác nhau. Do vậy, các thuật toán giấu tin trên dạng ảnh này gặp phảinhững khó khăn vất vả nhất định, chính do chỉ cần có thay đổinhỏ về chỉ số màu hoàn toàn có thể sẽ dẫn đến sự độc lạ lớnvề sắc tố của điểm ảnh trước và sau khi đổi khác. Với ảnh có bảng màu, để nâng cao tính che giấu, các kỹ thuật giấu tin thường tìm cách sửa chữa thay thế mộtmàu có chỉ số chẵn bằng màu gần nhất có chỉ số lẻhoặc ngược lại [ 3,4,7,8 ]. Dựa trên sáng tạo độc đáo này, chiêu thức Ez Stego [ 7 ] sắp xếp lại các màu trongbảng màu theo cường độ sáng. Cường độ sáng củamàu c với các thành phần Rc, Gc, Bc được tính theocông thức : = 0.299 + 0.587 + 0.144 ) + ( ) + ( Sau khi sắp xếp lại bảng màu, các màu giống nhausẽ có chỉ số màu gần nhau. Tuy nhiên, theoFridrich [ 3,4 ], hai màu khác nhau vẫn hoàn toàn có thể có cườngđộ sáng bằng nhau, thế cho nên tác giả đã sử dụng khoảngcách Euclid để nhìn nhận sự độc lạ về màu ứng vớicác chỉ số màu i và j theo công thức : – 14 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTtrong đó Ri, Gi, Bi và Rj, Gj, Bj là giá trị màu ứng vớicác chỉ số i và j trong bảng màu. Khi cần biến hóa mộtmàu có chỉ số chẵn ( hay lẻ ), Fridrich sẽ duyệt các màucó chỉ số lẻ ( hay chẵn ) để tìm màu gần nhất ( theokhoảng cách Euclid ) với màu cần đổi khác. Tuy nhiên, giải pháp thay thế sửa chữa màu gần nhất của các thuật toánvẫn hoàn toàn có thể tạo ra các màu mới cô lập, thế cho nên trong mộtsố trường hợp, ảnh chứa tin giấu dễ bị phát hiện. Để nâng cao chất lượng của ảnh sau khi giấu tin, trong [ 6 ] các tác giả G. Pan, Z. Wu, Y. Pan đã đề xuấtthuật toán giấu tin cho ảnh ít màu bằng cách sử dụngmột tập các khối mẫu có size 3 × 3, các khối mẫusẽ có sự ưu tiên khác nhau trong quy trình sử dụng đểnhúng tin. Mỗi khối mẫu được xác lập bởi 8 điểmxung quanh điểm tâm của khối, trong đó chia làm haiphần liên thông, một phần gồm các điểm có màugiống nhau được gọi là màu mẫu, phần còn lại gồmcác điểu có màu khác màu mẫu được gọi là màu thamdự ( nominated color ). Thuật toán sẽ tìm các khối ảnhkích thước 3 × 3 trùng với một mẫu trong tập mẫu vànhúng một bít bằng cách đổi khác màu của điểm tâmkhối thành màu mẫu hoặc màu tham gia. Với cách thayđổi như vậy, thuật toán có hai đặc thù quan trọng : điểm ảnh được chọn để đổi khác luôn nằm trên biêncủa hai miền có màu khác nhau và không xuất hiệnmàu mới. Nhờ vậy, thuật toán có tính che giấu cao. Tuy nhiên, khối lượng tin hoàn toàn có thể nhúng được còn chưanhiều như chính nhận xét của các tác giả. Cũng cầnnhận xét thêm, ý tưởng sáng tạo chọn điểm trên biên để thayđổi cũng đã được các tác giả M. Wu [ 11 ] và Y. C.Tseng [ 12 ] sử dụng để giấu tin trên ảnh nhị phân, nhưng mỗi giải pháp đều có cách chọn khác nhau. Dựa trên giải pháp giấu tin theo khối bít và tínhchẵn lẻ, bài báo này đề xuất kiến nghị một lược đồ giấu tin trênảnh có bảng màu. Theo đó, vùng tài liệu của ảnh gốcsẽ được chia thành các khối cùng kích cỡ. Với mỗikhối sẽ giấu được một bít và đổi khác nhiều nhất mộtphần tử. Khi cần đổi khác tính chẵn lẻ của khối, thuậttoán sẽ thay thế sửa chữa giá trị của một thành phần bằng giá trị củaphần tử liền kề nhưng khác tính chẵn lẻ. Với chiếnthuật thay thế sửa chữa như vậy, thuật toán yêu cầu cũng có haiTập V-1, Số 8 ( 28 ), tháng 12/2012 đặc thù giống như thuật toán [ 6 ], do đó nó cũng cótính che giấu khá cao. Nội dung tiếp theo của bài báo được tổ chức triển khai nhưsau : Phần 2 ra mắt 1 số ít ký hiệu và định nghĩađược sử dụng trong bài báo. Phần 3 trình diễn nội dungthuật toán yêu cầu. Tính đúng đắn của thuật toán đượcchứng minh trong Phần 4. Phần 5 trình diễn kết quảthực nghiệm của thuật toán yêu cầu và so sánh với haithuật toán Fridrich, Ez Stego. Cuối cùng, Phần 6 làmột số Kết luận. II. MỘT SỐ KÝ HIỆU VÀ ĐỊNH NGHĨAĐể tiện cho việc trình diễn, trong bài báo sử dụngmột số ký hiệu và định nghĩa như sau : – Ký hiệu × là tập các ma trận nguyên không âmcấp m × n ( m hàng và n cột ). – Với ∈ ×, nói thành phần ( i, j ) có nghĩa là phần tửtrên hàng i và cột j ( chỉ chăm sóc đến vị trí ), nói phầntử Fi, j là thành phần trên hàng i, cột j và có giá trị bằng Fi, j ( chăm sóc đến cả vị trí và giá trị ). Hai giá trị Fi, j, Fu, vkhác tính chẵn lẻ được ký hiệu là Fi, j # Fu, vĐịnh nghĩa 2.1 Phép nhân đồng vị ⊗ hai ma trận ∈ ×, ∈ × ký hiệu là C = A ⊗ B và đượcxác định theo công thức : Ci, j = Ai, j × Bi, j với i = 1,2, …, mvà j = 1,2, …, nĐịnh nghĩa 2.2 Phép toán SUM trên ma trận ∈ là một số nguyên, ký hiệu SUM ( A ) và tính theocông thức : ! ” # ( ) = USD USD % và % và Định nghĩa 2.3 Phép toán MOD trên ma trận nguyên ∈ × là ma trận nhị phân cấp m × n ký hiệu là : C = MOD ( F ) và được tính theo công thức : Ci, j = Fi, jmod 2 với i = 1,2, …, m và j = 1,2, …, nĐịnh nghĩa 2.4 Trên ma trận ∈ ×, thành phần ( u, v ) được gọi là liền kề với thành phần ( i, j ) ký hiệu là : Định nghĩa 2.5 Ma trận nhị phân ‘ ∈ × được gọilà ma trận liên thông nếu với mỗi cặp hai thành phần bất – 15 – ( i, j ) ( u, v ) nếu Max { | u-i |, | v-j | } = 1C ác công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 kỳ không kề nhau ( i, j ) và ( u, v ) có giá trị Ki, j = Ku, v = 1 luôn sống sót dãy các thành phần ( pt, qt ), t = 1, …, k sao cho : 1 ) Nếu s = 0 hoặc s = SUM ( K ), không giấu tin vàkết thúc thuật toán. K pt, qt = 1, t = 1, .. k và2 ) Nếu 1 ≤ s ≤ SUM ( K ) – 1, chuyển sang Bước 3 ( i, j ) ( p1, q1 ) ( p2, q2 ) …. ( pk, qk ) Bước 3 : Xét hai năng lực : ( u, v ) 1 ) Nếu s mod 2 = b, đặt G = F và kết thúc thuậttoánIII. THUẬT TOÁN ĐỀ XUẤTVới ảnh có bảng màu, tài liệu ảnh là một ma trậngồm các chỉ số màu có giá trị nguyên từ 0 đến 255. Ma trận tài liệu ảnh được chia thành các ma trận concùng cấp và thuật toán sẽ giấu một bít tài liệu trên mỗima trận con. Để tiện cho việc theo dõi, dưới đây sẽtrình bày thuật toán giấu một bít vào một ma trận con. III. 1. Ý tưởng của thuật toán đề xuấtGiả sử cần nhúng một bít tin mật b vào ma trận con ∈ ×. Thuật toán yêu cầu dựa trên sáng tạo độc đáo giấutin của Wu-Lee [ 11 ], sử dụng ma trân nhị phân ‘ ∈ × làm khóa bí hiểm và đổi khác nhiều nhất mộtphần tử trên F để ! ” # ( ⨂ ‘ ) cùng tính chẵn lẻ với b. 2 ) Nếu s mod 2 ≠ b, chuyển sang Bước 4B ước 4 : Xây dựng tập ∏ theo công thức = ( >, ? ) | ‘, = 1, ; = < = ( >, ? ) | ‘, = 1, AℎăDE, ∃ ( u, v ) : ( H, I ) ⇔ ( >, ? ) vàlẻ, ∃ ( u, v ) : ( u, v ) ⇔ ( i, j ) và = ( >, ? ) | ‘, = 1, ∃ ( u, v ) : ( u, v ) ⇔ ( i, j ) vàM, N # M, N #, P, EêHR = 1P, EêQHR = ! ” # ( ‘ ) − 1 XM, N # P, EêQH2 ≤ R ≤ ! ” # ( ‘ ) − 2B ước 5 : Biến đổi F để nhận được G, thực thi tuần tựnhư sau : 1 ) Chọn một thành phần ( i, j ) ∈ ∏ 2 ) Chọn một thành phần ( u, v ) sao cho : ( u, v ) ( i, j ) vàFu, v # Fi, j ( Theo định nghĩa của ∏, luôn sống sót ( u, v ) như vậy ) 3 ) Thay Fi, j bằng Fu, v. Đặt G = F, kết thúc thuật toán. Trong thuật toán Wu-Lee, Fi, j là các giá trị 0 hoặc 1, nên việc biến hóa một thành phần trên F chỉ đơn thuần làchuyển từ 0 sang 1 hoặc từ 1 sang 0. Ở đây, Fi, j có giátrị từ 0 đến 255. Vấn đề chọn thành phần nào để biến đổivà chọn giá mới cho thành phần cần đổi khác để nâng caochất lượng của ảnh sau khi giấu tin là các nội dungchính của thuật toán đề xuất kiến nghị. Nhận xét 1 : Dễ dàng thấy rằng, khi thuật toán thựchiện thành công xuất sắc ( kết thúc tại Bước 3 hoặc Bước 5 ), Gluôn thỏa mãn nhu cầu các điều kiện kèm theo ( 3.1 ) và ( 3.2 ). Như vậy, để chứng tỏ tính đúng đắn của thuật toán chỉ cầnchỉ ra ∏ ≠ Ø. Điều này sẽ được chứng tỏ trong mục4. Trong thuật toán yêu cầu sử dụng ma trận khóa nhịphân liên thông ‘ vớ iđiê0ukiệnSUM ( K ) ≥ 3. KhiNhận xét 2 : Trong Bước 5 hoàn toàn có thể có nhiều cách chọn ( i, j ) và ( u, v ). Dưới đây sẽ trình diễn giải pháp xácđịnh ( i, j ) và ( u, v ) để thuật toán giấu tin hoàn toàn có thể đạt đượctính che giấu cao. thực thi thành công xuất sắc ( có giấu tin ), thuật toán sẽ choma trận G thỏa mãn nhu cầu các điều kiện kèm theo : 1 ≤ SUM ( MOD ( G ) ⊗ K ) ≤ SUM ( K ) – 1 ( 3.1 ) SUM ( G ⊗ K ) mod 2 = bF và G khác nhau tối đa một thành phần ( 3.2 ) Đầu tiên chọn ( i, j ) sao cho : ( i, j ) ∈ ∏ và g ( i, j ) = max { g ( p, q ) | ( p, q ) ∈ ∏ } Các điều kiện kèm theo ( 3.1 ) và ( 3.2 ) được sử dụng để khôiphục tin giấu. III. 2. Nội dung thuật toán giấu tinBước 1 : Đặt s = SUM ( MOD ( F ) ⊗ K ) Bước 2 : Kiểm tra điều kiện kèm theo giấu tin, xét hai trườnghợp : Ở đây g ( p, q ) là số thành phần trên ma trận F liền kề với ( p, q ) và có giá trị bằng Fp, q. Sau khi đã có ( i, j ), ( u, v ) được chọn trong tập Y, gồmcác thành phần liền kề với ( i, j ) và khác tính chẵn lẻ vớiFi, j : Ω i, j = { ( p, q ) | ( p, q ) < => ( i, j ) va ɳ Fp, q # Fi, j } Với mỗi ( p, q ) ∈ Ωi, j, gọi f ( p, q ) là số thành phần trongΩi, j có giá trị bằng Fp, q. – 16 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTGiấu b1 = 1 vào F1 : Chọn ( u, v ) sao cho : ( H, I ) ⇔ ( >, ? ) và Z ( H, I ) = max { f ( p, q ) | ( p, q ) ∈ Ω, } Cách chọn này bảo vệ hai nhu yếu : – Phần tử được chọn để đổi khác nằm trên khóa K vàxung quanh nó có nhiều thành phần cùng giá trị với nónhất. – Giá trị thay thế sửa chữa khác tính chẵn lẻ với thành phần đượcchọn và xung quanh thành phần được chọn có nhiều phầntử cùng giá trị với giá trị thay thế sửa chữa. Do thành phần được chọn ( i, j ) nằm trên khóa K ( Ki, j = 1 ), nên sau khi đổi khác giá trị Fi, j từ chẵn sang lẻhoặc ngược lại thì SUM ( F ⊗ K ) sẽ biến hóa tính chẵnlẻ, do đó ma trận G luôn thỏa mãn nhu cầu điều kiện kèm theo ( 3.2 ). Mặtkhác cách biến hóa màu tại điểm ( i, j ) như vậy, sẽ rấtkhó phát hiện vì xung quanh nó luôn có các điểm cùngmàu với màu mới và nhiều năng lực sống sót các điểmcùng màu mới màu cũ của điểm ( i, j ). Điều này làmtăng tính che giấu của thuật toán. III. 3. Minh họa thuật toánGiấu b2 = 1 vào F2 : s = SUM ( MOD ( F2 ) ⊗ K ) = 4, do 0B ước 3 : s mod 2 ≠ b2, sang bước 4 : ∏ = { ( 1,2 ), ( 2,1 ), ( 3,2 ), ( 3,3 ) } Theo nhận xét 2 : g ( 1,2 ) = 0, g ( 2,1 ) = 0, g ( 3,2 ) = 1, g ( 3,3 ) = 1, nên chọn ( i, j ) = ( 3,2 ) ; Khi đó : Ω3, 2 = { ( 2,2 ), ( 2,3 ), ( 3,1 ) } f ( 2,3 ) = 1, f ( 3,1 ) = 0. vàf ( 2,2 ) = 1, Chọn ( u, v ) = ( 2,2 ) và thay F23, 2 bằng F22, 2, đặt G2 = F2. Giấu b3 = 0 vào F3 : s = SUM ( MOD ( F3 ) ⊗ K ) = 1, do 0B ước 3 : s mod 2 ≠ b3, sang bước 4 : ∏ = { ( 1,2 ), ( 2,1 ), ( 3,2 ), ( 3,3 ) } Theo nhận xét 2 : g ( 1,2 ) = 0, g ( 2,1 ) = 1, g ( 3,2 ) = 1, g ( 3,3 ) = 0, nên chọn ( i, j ) = ( 2,1 ) Chọn ( u, v ) = ( 3,1 ), thay F32, 1 bằng F33, 1 và đặt G3 = F3. Giấu b4 = 0 vào F4 : s = SUM ( MOD ( F4 ) ⊗ K ) = 3, do 0B ước 3 : s mod 2 ≠ b4, sang bước 4 : Hình 3.1 Khóa KDãy bít cần giấu : b1b2b3b4 = 1100, ảnh được chiathành 4 khối : F1s = SUM ( MOD ( F1 ) ⊗ K ) = 1, do 0B ước 3 : s mod 2 = b1, G1 = F1Khi đó Ω2, 1 = { ( 1,1 ), ( 2,2 ), ( 3,1 ) } và f ( 1,1 ) = 0, f ( 2,2 ) = 1, f ( 3,1 ) = 1G iả sử K bằng : Tập V-1, Số 8 ( 28 ), tháng 12/2012 F21451201054639 ∏ = { ( 1,2 ), ( 2,1 ), ( 2,3 ), ( 3,2 ), ( 3,3 ) } Theo nhận xét 2, chọn ( i, j ) = ( 1,2 ) và ( u, v ) = ( 1,1 ). Thay F41, 2 bằng F41, 1 và đặt G4 = F4. Như vậy, các Gi nhận được sau khi kết thúc thuậttoán giấu tin như hình sau : G1G2145 46 253 139 179 200120 34 46 47 78 78105 230 139 16 78 39F3 F4Hình 3.2 Ảnh trước khi giấu tinTrong ví dụ này : SUM ( K ) = 5, dưới đây sẽ minhhọa thuật toán giấu bít bi vào khối Fi ( i = 1,2,3,4 ). – 17 – 245535376 34 195 195 19553 57 57 249 23078 64 231 23 199G3 G4Hình 3.3 Ảnh sau khi giấu tinCác công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 III. 4. Thuật toán Phục hồi thông tinChứng minh bổ đềGiả sử G là ma trận giấu một bít tin mật và K làma trận khóa được sử dụng trong thuật toán giấu tin. Dựa trên các điều kiện kèm theo ( 3.1 ) và ( 3.2 ), hoàn toàn có thể xây dựngthuật toán Phục hồi bít tin mật như sau : Do Q1 ≠ Φ và Q2 ≠ Φ nên hoàn toàn có thể chọn một thành phần ( i0, j0 ) ∈ Q1 và ( u0, v0 ) ∈ Q2. Nếu hai thành phần ( i0, j0 ) ( u0, v0 ) thì đương nhiên bổ đề đúng với ( i, j ) = ( i0, j0 ) và ( u, v ) = ( u0, v0 ). Trong trường hợp hai thành phần ( i0, j0 ) và ( u0, v0 ) không kề nhau, thì do K liên thông nênphải sống sót dãy các thành phần ( pt, qt ), t = 1, …, k sao cho : Bước 1 : Tính s ’ = SUM ( MOD ( G ) ⊗ K ) Bước 2 : Kiểm tra G có giấu tin hay khôngNếu s ’ = 0 hoặc s ’ = SUM ( K ), Tóm lại G khôngchứa tin giấuTrái lại, tính b = s ’ mod 2, b là bít tin mật cầnkhôi phục. III. 5. Tính bảo mật thông tin của sơ đồMục đích của giấu tin là để bảo vệ tài liệu đượcnhúng trên các thiên nhiên và môi trường trao đổi thông tin. Vì vậy, mỗi một sơ đồ giấu tin đều phải có tính bảo đảm an toàn bảomật bằng cách đưa vào các khóa bí hiểm. Khóa bí mậtđược sử dụng trong cả thuật toán giấu tin và khôi phụcthông tin. Trong lược đồ yêu cầu, sử dụng một ma trận nhịphân liên thông K cấp m × n làm khóa bí hiểm. Do đó sốphương án khóa xê dịch bằng 2 mxn. Đây là 1 số ít khálớn, vì thế, việc dò tìm khóa K để trích rút thông tinmật đã nhúng trong ảnh là một việc làm tương đối khókhăn. Như vậy, vai trò của khóa K là để ngăn ngừaviệc sử dụng trái phép thông tin mật đã nhúng trongảnh, làm cho quy trình trao đổi thông tin trở lên antoàn hơn. K pt, qt = 1, t = 1, .. k ( i0, j0 ) ( p1, q1 ) ( p2, q2 ) …. ( pk, qk ) ( u0, v0 ) Nếu cả k thành phần của dãy thuộc Q2, thì bổ đề đúngvới ( i, j ) = ( i0, j0 ) và ( u, v ) = ( p1, q1 ). Trong trường hợptrái lại ( dãy có tối thiểu một thành phần ∈ Q1 ), gọi ( ph, qh ) làphần tử sau cuối của dãy thuộc Q1. Nếu h = k thì bổđề đúng với ( i, j ) = ( pk, qk ) và ( u, v ) = ( u0, v0 ). Nếu hthì do ( ph, qh ) là thành phần sau cuối thuộc Q1 nên ( ph + 1, qh + 1 ) phải thuộc Q2, do đó bổ đề đúng với ( i, j ) = ( ph, qh ) và ( u, v ) = ( ph + 1, qh + 1 ). Vậy bổ đề được chứng tỏ. Chứng minh tính đúng đắn của thuật toán : Trước hết từ ( 4.1 ) thuận tiện suy ra : s = SUM ( MOD ( F ) ⊗ K ) = | Q1 | ( 4.4 ) Theo nhận xét 1 trong mục 3, để chứng tỏ tínhđúng đắn của thuật toán chỉ cần chỉ ra ∏ ≠ Ø. Ta xétlần lượt xét ba trường hợp : s = 1, s = SUM ( K ) – 1 và1 ) Nếu s = 1 thì theo Bước 4 ( mục 3 ) : ∏ = { ( i, j ) | Ki, j = 1, Fi, j chẵn, ∃ ( u, v ) : ( u, v ) ( i, j ) vàFu, v # Fi, j } IV. TÍNH ĐÚNG ĐẮN CỦA THUẬT TOÁNNgoài ra từ ( 4.3 ) và ( 4.4 ) ta có : Trước hết ta xét một số ít khái niệm và bổ đề sau : | Q1 | = s = 1 Đặt : Q1 = { ( i, j ) | Ki, j = 1 và Fi, j lẻ } ( 4.1 ) Q2 = { ( u, v ) | Ku, v = 1 và Fu, v chẵn } ( 4.2 ) | Q2 | = SUM ( K ) – | Q1 | = SUM ( K ) – 1V ậy Q1 ≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra sống sót ( u, v ) ∈ Q1, ( i, j ) ∈ Q2 và ( u, v ) ( i, j ). Theo định nghĩaQ1, Q2 thì : Fu, v lẻ, Ki, j = 1 và Fi, j chẵn. Từ đó suy ra ( i, j ) ∈ ∏, vậy ∏ ≠ Φ. Từ ( 4.1 ) và ( 4.2 ) thuận tiện suy ra : Q1 ∩ Q2 = Φ và | Q1 | + | Q2 | = SUM ( K ) ( 4.3 ) Bổ đề : Nếu Q1 ≠ Φ, Q2 ≠ Φ và K là ma trận nhị phânliên thông thì luôn sống sót hai thành phần ( i, j ) và ( u, v ) saocho : ( i, j ) 2 ) Nếu s = SUM ( K ) – 1 thì theo Bước 4 : ( u, v ), ( i, j ) ∈ Q1 và ( u, v ) ∈ Q2 – 18 – ∏ = { ( i, j ) | Ki, j = 1, Fi, j lẻ, ∃ ( u, v ) : ( u, v ) Fu, v # Fi, j } ( i, j ) vàCác công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Ngoài ra từ ( 4.3 ) và ( 4.4 ) ta có : | Q1 | = s = SUM ( K ) – 1 | Q2 | = SUM ( K ) – | Q1 | = 1V ậy Q1 ≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra sống sót ( i, j ) ∈ Q1, ( u, v ) ∈ Q2 và ( i, j ) ( u, v ). Theo định nghĩaQ1, Q2 thì : Ki, j = 1, Fi, j lẻ, Fu, v chẵn. Từ đó suy ra ( i, j ) ∈ ∏, vậy ∏ ≠ Φ. 3 ) Nếu 1 < s < SUM ( K ) – 1 thì theo Bước 4 : ∏ = { ( i, j ) | Ki, j = 1, ∃ ( u, v ) : ( u, v ) ( i, j ) và Fu, v # Fi, j } Ngoài ra từ ( 4.3 ) và ( 4.4 ) ta có : 1 < | Q1 | < SUM ( K ) – 1 b ) Ảnh của lược đồ đề xuất kiến nghị | Q2 | = SUM ( K ) – | Q1 | > 1V ậy Q1 ≠ Φ và Q2 ≠ Φ nên theo bổ đề suy ra sống sót ( i, j ) ∈ Q1, ( u, v ) ∈ Q2 và ( i, j ) ( u, v ). Theo định nghĩaQ1, Q2 thì : Ki, j = Ku, v = 1, Fi, j lẻ, Fu, v chẵn. Từ đó suy racả ( i, j ) và ( u, v ) đều thuộc ∏, vậy ∏ ≠ Φ. V. THỰC NGHIỆMĐể so sánh tính che giấu của thuật toán đề xuất kiến nghị vớihai thuật toán Ez Stego và Fridrich, chúng tôi đã càiđặt và triển khai giấu tin theo cả ba thuật toán trêncùng các tham số đầu vào được cho như sau : – Dữ liệu nhúng là 461 bít được tạo ngẫu nhiên – Ảnh gốc có 8 màu và size 256 × 256 c ) Ảnh của thuật toán Fridricha ) Ảnh gốcẢnh sau khi nhúng 461 bít của các thuật toán : d ) Ảnh của thuật toán Ez Stego – 19 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTKết quả thực nghiệm cho thấy rằng, trên các ảnhcủa hai thuật toán Fridrich, Ez Stego có Open màucô lập, nhưng màu cô lập không Open trên ảnh củathuật toán yêu cầu. Thay vào đó, các màu bị biến đổicủa ảnh trong thuật toán yêu cầu chỉ Open ở nhữngvị trí giáp ranh và luôn sống sót các điểm ảnh lân cận cómàu giống với màu bị đổi khác. 6. KẾT LUẬNBài báo đề xuất kiến nghị một thuật toán giấu tin mới ápdụng cho ảnh có bảng màu. Theo đó, tài liệu ảnh đượcchia thành các khối cùng cấp m × n, mỗi khối có thểgiấu được một bít và biến hóa nhiều nhất một phần tửcủa khối. Khi cần biến hóa một thành phần, thuật toán sẽlựa chọn vị trí biến hóa và giá trị sửa chữa thay thế hài hòa và hợp lý đểkhông làm Open màu cô lập, do đó nâng cao chấtlượng của ảnh sau khi giấu tin. Kết quả thực nghiệmchỉ ra rằng, tính che giấu của thuật toán đề xuất kiến nghị tốthơn so với hai thuật toán Ez Stego và Fridrich. Trong [ 6 ], các tác giả G. Pan, Z. Wu, Y. Pan đãthực nghiệm giấu tin trên cùng ảnh được sử dụngtrong bài báo này. Qua quan sát cho thấy, tính che giấucủa thuật toán [ 6 ] có phần cao hơn so với thuật toán đềxuất, nhưng lượng thông tin giấu ít hơn. Thử nghiệmtrong [ 6 ] nhúng 289 bít, còn thực nghiệm trong bàibáo này nhúng 461 bít. TÀI LIỆU THAM KHẢO [ 1 ] PHẠM VĂN ẤT, NGUYỄN HIẾU CƯỜNG, ĐỖVĂN TUẦN, BÙI HỒNG QUẾ, TRẦN ĐĂNGHIÊN, Một số nhận xét về giải pháp giấu tin củaChen – Pan – Tseng, Kỷ yếu Hội thảo : Một số vấn đềchọn lọc của Công nghệ thông tin và tiếp thị quảng cáo, 2007T ập V-1, Số 8 ( 28 ), tháng 12/2012 [ 4 ] J. FRIDRICH, J.DU, Secure Steganographic Methodsfor Pallete Image. The 3 rd Information HidingWorkshop, Lecture Notes in Computer Science. 1768,47 – 60 ( 2000 ) [ 5 ] M.Y. WU, Y. H. HO, JIA-HONG LEE, An iterativemethod of palette-based image steganography, PatternRecognition Letters 25, 301 – 309, ( 2004 ) [ 6 ] GANG PAN, ZHAOHUI WU, YUNHE PAN, A DataHiding Method for Few – Color Images. IEEE Proceedings of the 2002 InternationalConference on Acoustic, Speech, and SignalProcessing, ICASSP 02, Vol. 4, 13-17 May 2002 [ 7 ] R. MACHADO. EZ STEGO, http://www.scribd.com/doc/62118082/105/EZ-Stego [ 8 ] S.M. KIM, ZIQIANG CHENG, KEE YOUNG YOO, A New Steganography Scheme based on an Indexcolor Image, Sixth International Conference onInformation Technology, ( 2009 ) [ 9 ] S. KR GHOSAL, A New Pair Wise Bit Based DataHiding Approach on 24 Bit Color Image usingSteganographic Technique. IEM, ( 2011 ) [ 10 ] V. K. SHARMA, V. SHRIVASTAVA, ASteganography Algorithm For Hiding Image In ImageBy Improved Lsb Substitution By Minimizedetection, Journal of Theoretical and Applied InformationTechnology ( 2012 ) [ 11 ] M. WU, J. LEE. A novel data embedding method fortwo-color fascimile images. In Proceedings ofinternational symposium on multimedia informationprocessing. Chung-Li, Taiwan, R.O.C, 1998 [ 12 ] YU-CHEE TSENG, HSIANG-KUANG PAN. Secureand Invisible Data Hiding in 2 – Color Images. INFOCOM 2001. Twentieth Annual Joint Conferenceof the IEEE Computer and Communications Societies. Proceedings IEEE, 887 – 896 vol. 2 [ 2 ] PHẠM VĂN ẤT, ĐỖ VĂN TUẦN, NGUYỄN HIẾUCƯỜNG, Thuật toán giấu tin dung tích cao, Tạp chíKhoa học Giao thông vận tải đường bộ, số 19 năm 2007 [ 3 ] J. FRIDRICH, Secure steganographic methods forpalette images, Proceedings of 3 rd Int. Workshop onInformation Hiding, 1999. Nhận bài ngày : 02/02/2012 – 20 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 SƠ LƯỢC VỀ TÁC GIẢPHẠM VĂN ẤTSinh ngày 12/6/1945 tại TP. Hà Nội. ĐỖ VĂN TUẤNSinh ngày 9/6/1975 tại HảiDương. Tốt nghiệp Đại học năm 1967 vàtiến sĩ năm 1980 tại Trường Đạihọc Tổng hợp TP.HN. Năm 1984 nhận học hàm PGS.Tốt nghiệp Đại học HVKTQSnăm 2002, Thạc sĩ năm 2007 tạiTrường Đại học Công nghệ – ĐHQGHN.Hiện giảng dạy tại Khoa CNTT – Trường Đại học Giao thông Vận tải TP. Hà Nội. Hiện giảng dạy tại Khoa CNTT – Trường Cao đẳngThương mại và Du lịch Thành Phố Hà Nội. Lĩnh vực chăm sóc : Lý thuyết ma trận, giải quyết và xử lý ảnh, antoàn thông tin, nghiên cứu và phân tích tài liệu. Lĩnh vực chăm sóc : Giấu tin, mật mã, phát hiện ảnhgiả mạoEmail : phamvanat83@vnn.vnEmail : dvtuanest@gmail.com- 21 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Phát triển thuật toán mật mã khóa công khaidựa trên hệ mật ElgamalDevelopment of Public Key Cryptographic Algorithm Based on ElgamalCryptosystemLưu Hồng Dũng1 – Chọn số nguyên tố đủ lớn p sao cho bài toánAbstract : This paper proposed a new public keycryptographic algorithm based on the ElGamalcryptosystem. This algorithm has the capacity ofinformation security and anthentication information. The paper also offers analysis on the safety of theproposed schemes, has shown the ability to apply it inpractice.logarit trong Z p là khó giải. 2 – Chọn g ∈ Z * p là thành phần nguyên thủy. 3 – Chọn khóa mật x là số ngẫu nhiên sao cho : 1 < x < p. Tính khóa công khai minh bạch y theo công thức : y = g x mod p. I. ĐẶT VẤN ĐỀ1. 2 Thuật toán mã hóaTrong trong thực tiễn, nhiều ứng dụng yên cầu việc bảomật thông tin cần phải được thực thi đồng thời vớiviệc xác nhận về nguồn gốc và tính toàn vẹn của thôngtin. Nội dung bài báo đề xuất kiến nghị một thuật toán mật mãkhóa công khai minh bạch được phát triển dựa trên hệ mậtElGamal [ 1 ] cho phép xử lý tốt các nhu yếu nêutrên. Giả sử người gửi là A, người nhận là B. Người gửiA có khóa bí hiểm là xa và khóa công khai minh bạch là ya. Ngườinhận B có khóa bí hiểm là xb và khóa công khai minh bạch là yb. Khi đó, để gửi bản tin M cho B, với : 0 ≤ M < p, người gửi A sẽ thực thi các bước như sau : 1 – Chọnsố ngẫu nhiên k thỏa1 < k < p. Tính giá trị R theo công thức : mãn : R = g k mod p. II. PHÁT TRIỂN THUẬT TOÁN MẬT MÃKHÓA CÔNG KHAI DỰA TRÊN HỆ MẬTELGAMAL2 – Sử dụng khóa công khai minh bạch của B để tính : C = M × ( y b ) k mod p1. Hệ mật ElgamalHệ mật Elgama được yêu cầu vào năm 1984 trên cơsở bài toán logarith rời rạc. Sau đó, các chuẩn chữ kýsố DSS [ 2 ] của Mỹ và GOST R34. 10-94 [ 3 ] của Liênbang Nga đã được hình thành trên cơ sở hệ mật này. 1.1 Thuật toán hình thành tham số và khóaCác thành viên trong mạng lưới hệ thống muốn trao đổi thôngtin mật với nhau bằng thuật toán mật mã Elgamma thìtrước tiên thực thi quy trình hình thành khóa nhưsau : 3 – Gửi bản mã gồm ( C, R ) đến người nhận B. 1.3 Thuật toán giải mãĐể Phục hồi bản tin khởi đầu ( M ) từ bản mã ( C, R ) nhận được, người nhận B triển khai các bướcnhư sau : – 22 – 1 – Tính giá trị Z theo công thức : Z = R xb mod p = g k. xb mod p2 – Tính gía trị nghịch đảo của Z : Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTZ − 1 = g k. xb − 1 bản mã C và gửi C cho người nhận B. Sẽ có các tìnhhuống xảy ra như sau : mod p = g − k. xb mod p3 – Khôi phục bản tin bắt đầu ( M ) : – Người nhận B không hề biết chắc như đinh rằng bản tinnhận được ( M ) có nguồn gốc từ người gửi A. − 1M = C × Z mod p – Giả sử bản mã C đã bị đổi khác thành C * và người1. 4 Tính đúng đắn của thuật toán mật mã ElgamalGiả sử bản tin nhận được sau quy trình giải mãnhận giải thuật được bản tin M *. Trường hợp này, người nhận không hề chứng minh và khẳng định được nội dungbản tin do A gửi đi đã bị biến hóa. ( C, R ) là M, thế thì : M = C × Z − 1 mod p = Thuật toán mật mã được đề xuất kiến nghị, phát triển trên cơsở hệ mật ElGamal sau đây sẽ là giải pháp cho các vấnđề nêu trên. = [ ( M × ( y b ) k mod p ) × ( g − k. xb mod p ) ] mod p = M × g k. xb × g − k. xb mod p = MNhư vậy, bản tin nhận được sau giải thuật ( M ) chính là bản tin bắt đầu ( M ). 2. Thuật toán mật mã khóa công khai minh bạch dựa trên hệmật Elgamal2. 1. Thuật toán hình thành tham số và khóa1. 5 Mức độ bảo đảm an toàn của hệ mật ElGamal1 – Sinh cặp số nguyên tố p và q đủ lớn và : q | ( p − 1 ) sao cho bài toán logarit trong Z p làHệ mật ElGamal sẽ bị phá vỡ nếu khóa mật x hoặck hoàn toàn có thể tính được. Để tính được x hoặc k, cần phảigiải một trong hai bài toán logarit rời rạc, ví dụ điển hình : khó giải. 2 – Chọn g = α ( p − 1 ) / q mod p, là phần tử sinh có bậcy = g x mod p hay : R = g k mod p. q của nhóm Zp, nghĩa là : Tuy nhiên, trong thực tiễn việc giải bài toán logaritrời rạc này là việc khó [ 4 ]. mãn : 1 < α < ( p − 1 ). 3 – Khóa bí hiểm x là một giá trị được chọn ngẫunhiên trong khoảng chừng : 1 < x < q. Khóa công khaitin M và M * được các bản mã tương ứng là ( C, R ) y được tính theo công thức : và C *, R *. Khi ấy ta sẽ có : * − 1C × ( C ) 1 < g < p và : g q ≡ 1 mod p. Ở đây : α là một số nguyên thỏaMột điểm yếu hoàn toàn có thể bị tiến công trong hệ mãElGamal là khi giá trị k bị sử dụng lại. Thực vậy, giảsử cùng một giá trị k được sử dụng để mã hóa hai bảnTập V-1, Số 8 ( 28 ), tháng 12/2012 y = g x mod p4 – Lựa chọn hàm băm ( hash ) H : { 0,1 } ֏ Z q ≡ M × ( g ) × ( M * × ( g x ) k ) − 1 mod px k ( Vídụ : SHA-1, MD5 ). Suy ra : 2.2 Thuật toán mã hóaM * × C × ( C * ) − 1 ≡ M mod pNghĩa là, chỉ cần biết nội dung của một trong haibản tin M hoặc M * thì sẽ thuận tiện biết được nội dungcủa bản tin kia. Giả sử người gửi A có khóa bí hiểm là xa, khóa côngkhai tương ứng là ya ; người nhận B có khóa bí hiểm làxb và khóa công khai minh bạch là yb. Để gửi bản tin M cho B, Athực hiện các bước như sau : Một yếu tố được đặt ra không riêng gì với hệ ElGamalnói riêng mà với các hệ mật khóa công khai minh bạch nói chunglà : Giả sử một người gửi A mã hóa bản tin M được – 23 – 1 – Chọn số ngẫu nhiên k thỏa mãn nhu cầu : 1 < k < q. 2 – Tính giá trị R theo công thức : R = g k mod p ( 1 ) Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTChú ý : Trường hợp sử dụng giá trị H ( x | | M ) thay cho k, 3 – Tính thành phần E theo công thức : E = H ( R | | M ) mod qTập V-1, Số 8 ( 28 ), tháng 12/2012 ( 2 ) thuật toán giải thuật vẫn được giữ nguyên. 4 – Tính thành phần S theo công thức : S = [ k − xa × E ] mod q2. 4 Tính đúng đắn của thuật toán mới yêu cầu ( 3 ) 5 – Sử dụng khóa công khai minh bạch của B để tính thành phầnC theo công thức : C = M × ( yb ) k mod p ( 4 ) 6 – Gửi bản mã gồm ( C, E, S ) đến người nhận B.Tính đúng đắn của hệ mật mới yêu cầu là sự phùhợp giữa thuật toán giải thuật với thuật toán mã hóa. Điều cần chứng tỏ ở đây là : Cho : p, q là 2 số nguyên tố độc lập, Tương tự thuật toán Elgamal, thuật toán mật mãmới yêu cầu hoàn toàn có thể bị tiến công khi sử dụng lại giá trịcủa k. Có thể khắc phục yếu điểm trên nếu sử dụng giátrị H ( x | | M ) thay cho k, với H (. ) là hàm băm kháng vachạm ( ví dụ điển hình SHA-1, MD5, … ) và “ | | ” là toán tửnối / trộn lẫn xâu. Khi đó thuật toán mã hóa sẽ đượcmô tả lại như sau : 1 – Tính giá trị R theo công thức : H : { 0,1 } ֏ Z p, R = g H ( xa | | M ) mod p, E = H ( R | | M ) mod q, S = [ H ( xa | | M ) − xa × E ] mod q, C = M × ( yb ) H ( xa | | M ) mod p. Nếu : R = ( g ) S × ( y a ) E mod p, M = C × ( R ) − x mod p, E = H ( R | | M ) mod q thì : M = M và E = E. 2 – Tính thành phần E theo công thức : Chứng minh : E = H ( R | | M ) mod q3 – Tính thành phần S theo công thức : S = [ H ( xa | | M ) − xa × E ] mod qThật vậy, thay ( 3 ) vào ( 5 ) ta có : R = g S × y a mod p = g k − xa × E × y a mod p4 – Sử dụng khóa công khai minh bạch yb của người nhận đểtính thành phần C theo công thức : H ( xa | | M ) = g k × g − xa × E × y a mod p = R × yamod p − E × y a mod p2. 3 Thuật toán giải mãTừ bản mã ( C, E, S ) nhận được, B Phục hồi vàTừ ( 8 ) suy ra : kiểm tra nguồn gốc cũng như tính toàn vẹn của bản tinban đầu ( M ) như sau : Thay ( 4 ) và ( 9 ) vào ( 6 ) ta có : R = g k mod p = { M × y b mod p × ( 5 ) × ( g k ) − xb mod p } mod p = 2 – Khôi phục bản tin bắt đầu theo công thức : M = C × ( R ) mod p = M × yb × yb ( 6 ) − kmod p = MThay ( 8 ) và ( 10 ) vào ( 7 ) ta được : 3 – Tính thành phần E theo công thức : E = H ( R | | M ) mod q ( 9 ) M = C × ( R ) − xb mod p1 – Tính giá trị R theo công thức : R = g S × ( y a ) E mod p ( 8 ) = R5 – Gửi bản mã gồm ( C, E, S ) đến người nhận B. − xbα ∈ Z * p, xa, xb ∈ [ 1, q − 1 ], y a = g xa mod p, yb = g xb mod p, R = g H ( xa | | M ) mod pC = M × ybg = α ( p − 1 ) / q mod p, g = α ( p − 1 ) / q mod p, E = H ( R | | M ) mod q ( 7 ) 4 – Kiểm tra nếu E = E thì M = M và M có nguồngốc từ người gửi A. = H ( R | | M ) mod q = EĐây là điều cần chứng tỏ. – 24 – ( 10 ) Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TT2. 5 Mức độ bảo đảm an toàn của thuật toán mới đề xuấtMức độ bảo đảm an toàn của thuật toán mới đề xuất kiến nghị đượcđánh giá bằng : 1 ) Khả năng chống thám mã. Về năng lực chống thám mã, hoàn toàn có thể thấy rằng mứcđộ bảo đảm an toàn của thuật toán mật mã mới yêu cầu là hoàntoàn tương tự với thuật toán Elgamal. Hệ mật sẽbị phá vỡ nếu khóa mật x hoàn toàn có thể tính được từ việc giảitoánlogaritrờiracNhững nghiên cứu và phân tích về mức độ bảo đảm an toàn cho thấy khảnăng ứng dụng thuật toán mới đề xuất kiến nghị trong trong thực tiễn làhoàn toàn hoàn toàn có thể. TÀI LIỆU THAM KHẢO. 2 ) Khả năng chống trá hình về nguồn gốc và nộidung của bản tin. bàiTập V-1, Số 8 ( 28 ), tháng 12/2012 như : [ 1 ]. T. ELGAMAL. A public key cryptosystem and asignature scheme based on discrete logarithms. IEEETransactions on Information Theory. 1985, Vol. IT-31, No. 4. pp. 469 – 472. [ 2 ]. National Institute of Standards and Technology, NIST FIPS PUB 186 – 3. Digital Signature Standard, U.S. Department of Commerce, 1994. y = g x mod phay : S = [ H ( x | | M ) − x × E ] mod qKhả năng chống trá hình về nguồn gốc và nội dungbản tin phụ thuộc vào vào mức độ khó của việc tạo ra cáccặp ( C, E, S ) trá hình thỏa mãn nhu cầu điều kiện kèm theo kiểm tracủa thuật toán giải thuật : E = E. Giả sử cặp E *, S * là trá hình, thế thì nó cần phải thỏa mãn nhu cầu : [ 3 ]. GOST R 34.10 – 94. Russian Federation Standard. Information Technology. Cryptographic dataSecurity. Produce and check procedures ofElectronic Digital Signature based on AsymmetricCryptographic Algorithm. Government Committeeof the Russia for Standards, 1994 ( in Russian ). E * ≡ H ( ( g S × y E mod p ) | | M ) mod q [ 4 ]. D.R STINSON, CRYPTOGRAPHY, Theory andPractice, CRC Press 1995. Với H (. ) là hàm băm kháng va chạm, hơn thế nữa nộidung bản tin M cũng chưa biết thì việc chọn được cặpNhận bài ngày : 20/03/2012 ( E, S * trá hình là hầu không hề thực thi được. SƠ LƯỢC VỀ TÁC GIẢLƯU HỒNG DŨNGSinh năm 1966 tại Hưng Yên. III. KẾT LUẬNBài báo yêu cầu một thuật toán mật mã khóa côngkhai được phát triển dựa trên hệ mật ElGamal có khảnăng đồng thời : Tốt nghiệp Đại học chuyên ngànhVô tuyến điện tử năm 1989 vàCao học ngành Kỹ thuật Điện tửvà tin tức liên lạc năm 2000 tạiHọc viện Kỹ thuật Quân sự. 1 ) Bảo mật thông tin. 2 ) Xác thực về nguồn gốc thông tin. 3 ) Xác thực về tính toàn vẹn của thông tin. Hơn nữa, mặc dầu bản mã được tạo ra bởi thuật toánmới yêu cầu gồm có 3 thành phần ( C, E, S ) nhưng độdài của nó không lớn hơn độ dài bản mã 2 thành phần ( C, R ) mà thuật toán ElGamal tạo ra. Giả sử | p | = 512 bit, | q | = 160 bit khi đó độ dài bảnmã do thuật toán ElGamal tạo ra là : | C | + | R | = 512 bit + 512 bit = 1024 bit, còn độ dài bản mã do thuật toánmới đề xuất kiến nghị tạo ra là : | C | + | E | + | S | = 512 bit + 160 bit + 160 bit = 832 bit. Hiện là giảng viên Khoa Công nghệ tin tức, Họcviện Kỹ thuật Quân sự. Lĩnh vực nghiên cứu : An toàn và bảo mật thông tin thông tin, An ninh mạng máy tính. Email : luuhongdung@gmail.com- 25 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTTập V-1, Số 8 ( 28 ), tháng 12/2012 Một chiêu thức lọc cộng tác dựa trên mô hìnhđồ thị hai phíaA Collaborative Filtering Method Based on Bipartite Graph ModelMai Thị Như và Nguyễn Duy PhươngAbstract : Collaborative filtering is a technique topredict the utility of items for a particular user byexploiting the behavior patterns of a group of userswith similar preferences. This method has been widelysuccessful in many e-commerce systems. In this paper, we present an effective collaborative filtering methodbased on general bipartite graph representation. Theweighted bipartite graph representation is suitable forall of the real current data sets of collaborativefiltering. The prediction method is solved by the basicsearch problem on the graph that can be easy toimplement for the real applications. Specially, themodel tackled the effect of the sparsity problem ofcollaborative filtering by expanding search lengthfrom the user node to the item node. By this way, someusers or items can not be detemined by thecorrelations but can be computed by the graph Mã Sản Phẩm. Experimental results on the real data sets show thatthe proposed method improve significantly predictionquality for collaborative filtering. I. PHÁT BIỂU BÀI TOÁN LỌC CỘNG TÁCCho tập hợp hữu hạn U = { u1, u2, …, uN } là tậpgồm N người dùng, P = { p1, p2, …, pM } là tập gồm Msản phẩm. Mỗi loại sản phẩm px ∈ P hoàn toàn có thể là sản phẩm & hàng hóa, phim, ảnh, tạp chí, tài liệu, sách, báo, dịch vụ hoặc bấtkỳ dạng thông tin nào mà người dùng cần đến. Đểthuận tiện trong trình diễn, ta viết px ∈ P ngắn gọn thànhx ∈ P ; và ui ∈ U là i ∈ U.Mối quan hệ giữa tập người dùng U và tập sảnphẩm P được màn biểu diễn trải qua ma trận đánh giáR = ( rix ), i = 1 … N, x = 1 … M. Mỗi giá trị rix biểu diễnđánh giá của người dùng i ∈ U cho loại sản phẩm x ∈ P. Giátrị rix hoàn toàn có thể được tích lũy trực tiếp bằng cách hỏi ýkiến người dùng hoặc tích lũy gián tiếp trải qua cơchế phản hồi của người dùng. Giá trị rix = ∅ được hiểungười dùng i chưa nhìn nhận hoặc chưa khi nào biết đếnsản phẩm x. Tiếp đến ta ký hiệu, Pi ⊆ P là tập các sản phẩmđược nhìn nhận bởi người dùng i ∈ U và Ux ⊆ U là tập cácngười dùng đã nhìn nhận loại sản phẩm x ∈ P. Với một ngườidùng cần được tư vấn a ∈ U ( được gọi là người dùnghiện thời, hay người dùng tích cực ), bài toán lọc cộngtác là Dự kiến nhìn nhận của người dùng a đối vớinhững loại sản phẩm x ∈ ( P \ Pa ), trên cơ sở đó tư vấn chongười dùng a những mẫu sản phẩm được nhìn nhận cao. Bảng 1 bộc lộ một ví dụ với ma trận nhìn nhận R = ( rij ) trong hệ gồm 5 người dùng U = { u1, u2, u3, u4, u5 } và 7 loại sản phẩm P = { p1, p2, p3, p4, p5, p6, p7, }. Mỗingười dùng đều đưa ra các nhìn nhận của mình về cácsản phẩm theo thang bậc { 1,2,3,4,5 }. Đối với tập dữliệu MovieLens [ 11 ], rix = 5 được hiểu là người dùng iđánh giá phim x ở mức độ “ rất tốt ” ; rix = 4 được hiểulà người dùng i nhìn nhận “ tốt ” ; rix = 3 được hiểu làngười dùng i nhìn nhận phim x ở mức độ “ bìnhthường ” ; rix = 2 được hiểu là người dùng i đánh giáphim x ở mức độ “ kém ” ; rix = 1 được hiểu là ngườidùng i nhìn nhận phim x ở mức độ “ rất kém ”. Giá trịrij = ∅ được hiểu là người dùng ui chưa nhìn nhận hoặcchưa khi nào biết đến loại sản phẩm pj. Các ô được đánhdấu ‘ ? ’ bộc lộ giá trị mạng lưới hệ thống cần Dự kiến cho ngườidùng u5. – 26 – Các công trình nghiên cứu, phát triển và ứng dụng CNTT-TTBảng 1. Ma trận nhìn nhận của lọc cộng tác. Sản phẩmNgườidùngp1 p2 p3 p4 p5 p6 p7u14 ∅ 1 5 ∅ 1 ∅ u2 ∅ 5 2 5 1 ∅ 2 u3u4u5p1Tập V-1, Số 8 ( 28 ), tháng 12/2012 p2u1p3u2p4u3p5u4p6p7u5Hình 1. Đồ thị hai phía cho lọc cộng tácII. CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊNQUANCó hai hướng tiếp cận chính xử lý bài toánlọc cộng tác bằng quy mô đồ thị : Lọc cộng tác dựatrên quy mô đồ thị tổng quát và Lọc cộng tác dựa trênmô hình đồ thị hai phía [ 3,4,6,7 ]. Để thuận tiện choviệc trình diễn quy mô đề xuất kiến nghị, chúng tôi tóm tắt lạinhững nghiên cứu về quy mô đồ thị hai phía cho lọccộng tác của Huang và các tập sự [ 3,4 ]. Trong quy mô này, Huang xem xét bài toán lọccộng tác như bài toán tìm kiếm trên đồ thị hai phía, một phía là tập người dùng U, phía còn lại là tập sảnphẩm P. Cạnh nối giữa người dùng i ∈ U đến sản phẩmx ∈ P được thiết lập nếu người dùng i nhìn nhận “ tốt ” hoặc “ rất tốt ” mẫu sản phẩm x. Ví dụ với ma trận đánh giáđược cho trong Bảng 1, các giá trị nhìn nhận rix = 4, rix = 5 sẽ được đổi khác thành 1, những giá trị còn lại đượcbiến đổi thành 0. Khi đó, ma trận kề trình diễn đồ thịhai phía được biểu lộ trong Bảng 2, đồ thị hai phíatương ứng theo màn biểu diễn được bộc lộ trong Hình 1. Bảng 2. Ma trận kề trình diễn đồ thị hai phía. NgườidùngSản phẩmp1p2p3p4p5p6p7u1u2u3u4u5Phương pháp Dự kiến trên đồ thị được thực hiệnbằng thuật toán Viral mạng để tìm ra số lượngđường đi độ dài L từ đỉnh người dùng i ∈ U đến đỉnhsản phẩm x ∈ P. Những mẫu sản phẩm x ∈ P có số lượngđường đi nhiều nhất đến người dùng i ∈ U sẽ đượcdùng để tư vấn cho người dùng này [ 3 ]. Với chiêu thức trình diễn và Dự kiến nêu trên, chúng tôi đã thực thi kiểm nghiệm trên các bộ dữliệu thực và nhận thấy một số ít những hạn chế dưới đây. Thứ nhất, màn biểu diễn của Huang chỉ chăm sóc đếncác giá trị nhìn nhận “ tốt ” hoặc “ rất tốt ” và bỏ lỡ cácgiá trị nhìn nhận “ kém ” hoặc “ rất kém ”. Đối với các hệthống lọc cộng tác trong thực tiễn, mức nhìn nhận của ngườidùng được chia thành nhiều thang bậc khác nhau ( tậpdữ liệu MovieLens có 5 mức nhìn nhận, tậpBookCrossing có 10 mức nhìn nhận ) [ 11,12 ]. Chính vìvậy, màn biểu diễn này chưa thực sự tương thích với các hệthống lọc cộng tác lúc bấy giờ. Mặt khác, các phươngpháp Dự kiến của lọc cộng tác được triển khai dựa trênthói quen sử dụng loại sản phẩm của hội đồng ngườidùng có cùng sở trường thích nghi, do vậy các giá trị nhìn nhận “ tốt ” hay “ không tốt ” đều phản ánh thói quen sử dụngsản phẩm của người dùng. Việc bỏ lỡ các giá trị “ không tốt ” sẽ ảnh hưởng tác động rất nhiều đến chất lượng dựđoán thói quen sử dụng mẫu sản phẩm của người dùng. Thứ hai, so với các mạng lưới hệ thống lọc cộng tác sốlượng giá trị nhìn nhận rix = ∅ nhiều hơn rất nhiều lần sốlượng giá trị nhìn nhận rix ≠ ∅. Vì vậy, việc bỏ lỡ cácgiá trị “ không tốt ” khiến cho yếu tố tài liệu thưa củalọc cộng tác trở nên trầm trọng hơn. Điều này hoàn toàn có thể – 27 –

Xem thêm: Nghe nhạc và xem phim trên Windows Phone: những điều bạn cần biết

Source: https://mindovermetal.org
Category: Ứng dụng hay

5/5 - (2 votes)