Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN THÀNH CHUNG
CHỮ KÝ SỐ VÀ ỨNG DỤNG BẢO MẬT
TRANG THÔNG TIN ĐIỆN TỬ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thái Nguyên - 2013
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn LỜI CAM ĐOAN
Tôi cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện theo sự
hướng dẫn khoa học của PGS.TS Đoàn Văn Ban.
Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa học
của luận văn này.
Thái Nguyên, ngày tháng 8 năm 2013
Ngƣời Cam Đoan
Nguyễn Thành Chung Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
LỜI CẢM ƠN
Trước tiên tôi bầy tỏ lời cảm ơn chân thành đến các Thầy, Cô giáo đã
giảng dạy, hướng dẫn và giúp đỡ tôi trong thời gian học tập và nghiên cứu
hoàn thành luận văn này.
Xin được bầy tỏ lòng biết ơn sâu sắc tới Thầy giáo PGS.TS Đoàn Văn
Ban đã tận tình hướng dẫn, giúp đỡ và đóng góp cho tôi nhiều ý kiến quí báu
để hoàn thành luận văn này.
rất nhiều ứng dụng của nó vào đời sống của con người, tạo cho chúng ta sự thoái
mái trong việc giao tiếp, trao đổi thông tin, tất cả những sự việc đều được cập nhật
một cách nhanh chóng trên các phương tiện truyền thông. Mọi thông tin của cá
nhân, tập thể, doanh nghiệp, hay thậm chí của các bộ, ban ngành các cấp đều có thể
được đưa lên mạng Internet. Làm thế nào để có thể khẳng định những thông tin đó
là của ai? Để giải quyết vấn đề này không thể sử dụng con dấu hay chữ ký thông
thường điều này dẫn đến sự ra đời của chữ ký số.
Mặt khác sự bùng nổ phương thức truyền thông tin thông qua Internet và các
phương tiện truyền thông khác đã đưa chúng ta đến việc cần phải đối mặt với việc
bảo mật những thông tin cá nhân, thông tin riêng tư, các thông tin cá nhân riêng tư
có thể bị thay đổi khi đưa lên Internet.
Vấn đề an toàn, an ninh mạng không mới nhưng càng ngày càng trở nên
quan trọng cùng với sự phát triển theo chiều rộng và chiều sâu của xã hội thông tin.
Ví dụ đơn giản như gần đây rất nhiều trang web, các hệ thống mạng ở Việt nam bị
hacker tấn công gây hậu quả đặc biệt nghiêm trọng. Việc xây dựng một số thuật
toán tối ưu hóa nhằm tăng hiệu quả của chương trình bảo mật thông tin và ứng dụng
vào chữ ký số là cơ sở nội dung trong đề tài luận văn này.
2. Đối tƣợng và phạm vi nghiên cứu
Đối tƣợng nghiên cứu:
Nghiên cứu các giải pháp mã hóa để bảo mật thông tin và những phương
pháp, kỹ thuật tạo chữ kí số trên các tài liệu, văn bản điện tử để xác thực nguồn gốc
tài liệu hay văn bản của người gửi.
Các hệ mật mã khóa công khai, trong đó hệ mật mã RSA được sử dụng làm
đối tượng nghiên cứu chính của đề tài nhằm phát hiện các phép xử lý toán học cần
tối ưu. Từ các kết quả thu được bước đầu đề tài đưa ra một cách xây dựng thử
nghiệm vào chữ ký số áp dụng được các kết quả tối ưu hóa.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
3.4 Giao thức bảo mật ứng dụng chữ ký số cho các văn bản pháp quy trên
trang thông tin
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
3.5 Cài đặt thực nghiệm và đánh giá
3.6 Kết luận chương
4. Các kí hiệu dùng trong luận văn
P Là tập hữu hạn các văn bản có thể.
A Là tập hữu hạn các chữ ký có thể.
K Là tập hữu hạn các khoá có thể.
S Là tập các thuật toán ký.
V Là tập các thuật toán kiểm thử.
C Là tập hữu hạn các bản mã có thể;
E Là tập hợp các hàm mã hóa có thể;
D Là tập các hàm giải mã có thể;
e
k
Thuật toán mã hoá
d
k
Thuật toán giải mã
gcd Ước chung lớn nhất
lcm Bội chung nhỏ nhất
Sig
k
Thuật toán ký
Ver
, a
2
, …, a
n
đều là ước của d, thì d được gọi là ước chung lớn nhất
(UCLN) của a
1
, a
2
, …, a
n
. Ký hiệu d = gcd (a
1
, a
2
, …, a
n
) hay d = UCLN(a
1
, a
2
, …,
a
n
). Nếu gcd (a
1
, a
2
, …, a
n
của a
1
, a
2
, …, a
n
. Ký hiệu m = lcm (a
1
, a
2
, …, a
n
) hay m = BCNN (a
1
, a
2
, …, a
n
).
Ví dụ: Cho a =20, b =25, gcd (20, 25) = 5, lcm (20, 25) = 100.
Hai số 20 và 13 là số nguyên tố cùng nhau, vì gcd (20, 13) = 1
Thuật toán Euclide tìm ước chung lớn nhất
INPUT: Hai số nguyên không âm a và b, với a = b.
OUTPUT: Ước số chung lớn nhất của a và b.
1. Trong khi còn b > 0, thực hiện:
đặt r ← a mod b, a ←b , b ← r.
2. Cho ra kết quả (a).
Ví dụ: Tìm gcd (528, 234) bằng thuật toán Euclide
1. Nếu b = 0 thì đặt d ← a , x ←1, y ← 0, và cho ra (d, x, y).
2. Đặt x
2
= 1, x
1
= 0 , y
2
= 0 , y
1
= 1.
3. Trong khi còn b > 0, thực hiện:
3.1. q←a div b, r ← a mod b , x ← x
2
- q*x
1
, y ← y
2
- q*y
1
.
3.2. a ←b, b ←r , x
2
← x
1
, x
1
← x , y
2
← y
1
0
1
1
0
234
60
2
60
1
-2
1
0
-2
1
60
54
3
54
-3
7
-3
1
7
-2
54
6
1
nguyên tố” Phương pháp „cổ điển‟ và phương pháp „xác suất‟.
1.1.3 Quan hệ đồng dƣ [3,4]
Cho các số nguyên a, b, m (n > 0). Ta nói rằng a và b “đồng dư” với nhau
theo modulo m, nếu chia a và b cho m nhận được cùng một số dư (hoặc a – b chia
hết cho m). Ký hiệu: a ≡ b (mod m).
Ví dụ:
23 ≡ 11 (mod 4) vì chia 23 và 11 cho 4, được cùng số dư là 3.
Phƣơng trình đồng dƣ tuyến tính
Phương trình đồng dư tuyến tính có dạng: a*x = b (mod m ) (1)
Trong đó a, b, n là các số nguyên, m > 0, x là ẩn số. Phương trình (1) có nghiệm khi
và chỉ khi d = gcd (a,m ) / b, và khi đó nó có đúng d nghiệm theo modulo m.
Bây giờ ta xét hệ thống các phương trình đồng dư tuyến tính.
nn
max
max
max
mod
, , m
n
là n số nguyên
lớn hơn 1 đôi một nguyên tố cùng nhau. Đặt M = m
1
*m
2
* *m
n
. Cho trước các số
nguyên a
1
, a
2
, , a
n
khi đó tồn tại duy nhất một số nguyên x (0x<M) thoả mãn các
phương trình đồng dư sau đây:
max
mod
mod
mod
22
11
Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo modun
M = m
1
*m
2
* *m
k
, trong đó m
1
, m
2
, , m
n
đôi một nguyên tố cùng nhau. Trong bài
toán Hàn Tín n = 3 và m
1
= 3, m
2
= 5, m
3
= 7.
Ta xét phương trình đồng dư bậc hai có dạng đơn giản sau:
Mã hoá dữ liệu là mã hóa với mục đích làm cho dữ liệu không thể đọc được
bởi bất cứ ai, ngoại trừ những ai được phép đọc. Mã hóa sử dụng thuật toán và
khóa để biến đổi dữ liệu từ hình thức đơn giản rõ ràng (plain hay cleartext) sang
hình thức mật mã vô nghĩa (code hay ciphertext). Chỉ có những ai có thông tin giải
mã thì mới giải mã và đọc được dữ liệu.
1.2.2 Phân loại hệ mã hóa [4]
1.2.2.1 Hệ mã hóa khóa đối xứng
Hệ mã hoá khóa đối xứng là Hệ mã hóa mà biết được khóa mã hoá thì có thể
“dễ” tính được khóa giải mã và ngược lại.
Trong hệ thống mã hoá đối xứng, trước khi truyền dữ liệu, 2 bên gửi và nhận
phải thoả thuận về khoá dùng chung cho quá trình mã hoá và giải mã. Sau đó, bên
gửi sẽ mã hoá bản rõ (Plaintext) bằng cách sử dụng khoá bí mật này và gửi thông
điệp đã mã hoá cho bên nhận. Bên nhận sau khi nhận được thông điệp đã mã hoá sẽ
sử dụng chính khoá bí mật mà hai bên thoả thuận để giải mã và lấy lại bản rõ
(Plaintext).
Hình 1.1 Quá trình thực hiện cơ chế mã hóa
Mã hoá đối xứng có thể đƣợc phân thành hai loại:
Gửi
Nhận
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
b. Nhƣợc điểm
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
Hệ mã hoá khoá đối xứng “không an toàn” so với hệ mã hoá khoá công khai
bởi lý do sau:
Người mã hoá và người giải mã phải có “chung” một khoá. Khóa phải được
giữ bí mật tuyệt đối, vì biết khoá này “dễ” xác định được khoá kia và ngược lại.
Vấn đề thỏa thuận khoá và quản lý khóa chung là khó khăn và phức tạp.
Người gửi và người nhận phải luôn thống nhất với nhau về khoá. Việc thay đổi
khoá là rất khó và dễ bị lộ. Khóa chung phải được gửi cho nhau trên kênh an toàn.
1.2.2.2 Hệ mã hóa khóa công khai
Hệ mã hoá khoá công khai là hệ mã hoá có khoá lập mã và khoá giải mã
khác nhau, biết được khoá này “khó” tính được khoá kia.
Hệ mã hoá này được gọi là hệ mã hoá khoá công khai vì khoá lập mã được
công khai (gọi là khoá công khai – Public key), Khoá giải mã giữ bí mật (gọi là
khoá riêng – Private key). Điều quan trọng đối với hệ thống là không thể tìm ra
khóa bí mật nếu chỉ biết khóa công khai.
Hình 1.2 Quá trình thực hiện mã hóa khóa công khai
Quá trình truyền và sử dụng mã hoá khoá công khai được thực hiện như sau:
Bên gửi yêu cầu cung cấp hoặc tự tìm khoá công khai của bên nhận trên một
server chịu trách nhiệm quản lý khoá.
Tiến trình mã hóa khối truyền thông điệp đến các khối, mỗi khối sẽ thực hiện
En/Decrypted sau khi nhận thông điệp. Như mã hóa thay thế, nó sử dụng một block
rất lớn 64 bit hay hơn.
Tiến trình mã hóa dòng truyền thông điệp thành dòng từng bit hay byte ở
một thời điểm khi En/Decryting.
Hiện có rất nhiều thuật toán mã hóa khối được sử dụng như DES, MD4,
MD5, SH1, SH2
a. Ƣu điểm
Chỉ cần biết một cặp khối bản rõ và bản mã người ta có thể dễ dàng suy ra
được khóa và dùng khóa để giải các khối bản mã khác.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
b. Nhƣợc điểm
Khi kích thước khối lớn thì số dòng của bảng khóa cũng lớn và gây trở ngại
cho việc lưu trữ cũng như trao đổi khóa giữa người gửi và nhận.
1.3 Một số hệ mã hóa khóa công khai
1.3.1 Hệ mã hóa khóa công khai RABIN
Sơ đồ
Hệ mã hóa là bộ gồm 5 thành phần: {P, C, K, E, D}, trong đó:
+ P (Plaintext): là tập hữu hạn các bản rõ có thể.
+ C (CipherText): là tập hữu hạn các bản mã có thể.
+ K (Key): là tập hữu hạn các khóa có thể.
+ E (Encyption): là tập hợp các hàm mã hóa có thể.
+ D (Decyption): là tập các hàm giải mã có thể.
Với mỗi k
K, ta định nghĩa e
k
q
(3mod 4) (tức là: p = 3 + 4*t, q = 3 + 4*m).
Mã hóa
Vớ i bản rõ x P, đị nh nghĩ a bản mã là: y = e
k
(x) = x* (x + b) (mod n).
Giải mã
Vớ i bản mã y C, bản rõ là: x = d
k
(y) =
24
2
bb
y
(mod n).
+ Đặt z = x + b/2, ta có:
z
2
= x
2
+ b
2
/4 + 2x * b/2 = x
2
+ b
2
/4 + x*b = b
2
/4 + x*(x + b) (mod n).
+ Vì p, q là các số nguyên tố, nên ta có: T
(p -1)/2
1 (mod p), T
(q -1)/2
1 (mod q).
+ Nhân 2 vế với T ta được: T
(p +1)/2
T (mod p), T
(q +1)/2
T (mod q) hay ta có:
(p+1)/4 2
(p+1)/4 2
( T ) T mod p
( T ) T mod q
(3)
+ Từ (2), (3) ta có hệ phương trình:
(p+1)/4 2 2
(p+1)/4 2 2
( T ) z
( T ) z
(p 1)/ 4
(q 1)/ 4
z T modp
z T modq
(p 1)/ 4
(q 1)/4
z T modp
z T modq
yC
: d
k
(y) = x. (vì: d
k
(e
k
(x)) = x).
*Tạo cặp khóa (bí mật, công khai) (a, h) :
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
18
Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong Z
p
là “khó” giải.
Chọn phần tử nguyên thuỷ g Z
p
*. Đặt P = Z
p
*, C = Z
p
*
Z
p
*.
Chọn khóa bí mật là a Z
p
*. Tính khóa công khai h g
* Giải mã: d
k
(y
1
, y
2
) = y
2
*
(y
1
a
)
-1
mod p.
1.3.3 Hệ mã hóa khóa công khai RSA [4]
Hệ mã hóa khóa công khai được đề xuất bởi Ron Rivest, Adi Shamir và Len
Adleman (MIT) vào năm 1977.
Hệ mã hóa sử dụng phương pháp mã hóa khối với mỗi khối là một số
nguyên < n: Thông thường kích cỡ n là 1024 bit ≈ 309 chữ số thập phân.
Sơ đồ
Giả sử khối bản gốc của người gửi là M và khối bản mã của người nhận là C,
quá trình mã hóa và giải mã RSA là: C = M
e
mod n và M = C
d
mod n
Cả người gửi và người nhận phải biết giá trị n. Người gửi biết giá trị e và chỉ
người nhận biết giá trị d. Đây là một thuật toán mã hóa khóa công khai với khóa
Trong chương 1 đã trình bày những vấn đề mang tính cơ sở khoa học, nền
tảng cho việc sử dụng chữ ký số vào việc bảo mật và xác thực thông tin. Khái niệm
chữ ký số, cách phân loại, thuật toán chữ ký số một số sơ đồ chữ ký hiện đang được
sử dụng phổ biến sẽ được trình bày trong nội dung của chương 2. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
22
dùng để tạo chữ ký số, khoá công khai dùng để thẩm định chữ ký số hay xác thực
người tạo ra chữ ký số đó.
2.1.2 Phân loại chữ ký số
Hai nhó m chí nh củ a Electronic Signature (Chữ ký điện tử) đã đượ c phá t
triể n dự a trên 2 công nghệ cơ bả n: Digital Signatures (Chữ ký số) và E-SIGN (Dấu
điện tử).
2.1.2.1 Digital Signatures (Chữ ký số)
Chữ ký số là một dạng chữ ký điện tử, độ an toàn cao và được sử dụng rộng
rãi, được phát triển dựa trên lý thuyết mật mã và thuật toán mã hóa bất đối xứng.
Thuật toán mã hóa dựa vào cặp khóa bí mật (Private Key) và khóa công khai
(Public Key). Được sử dụng thông qua nhà cung cấp chính thức ( CA – Certificate
Authority).
Chữ ký số giúp người nhận thông điệp có thể tin tưởng ở nội dụng văn bản
mình nhận được là của người quen biết. Người gửi cũng không thể chối bỏ trách
nhiệm là chính mình đã gửi văn bản đó đi, văn bản đã được số hóa là một chuỗi bit
(vd email, contracts, được gửi thông qua những giao thức mã hóa).
2.1.2.2 E-SIGN (Dấu điện tử)
Dấu điện tử là một dạng chữ ký thông thường không sử dụng hạ tầng khóa
công khai PKI ( Public Key Infrastructure). Chủ yếu quản lý dựa vào danh tính và
nhận dạng Logs (Log – in).
Dấu điện tử có tính bảo mật không cao nên chỉ hợp cho các hệ thống đóng.
2.1.2.3 Biometric Signatures (Chữ ký sinh trắc học)
Đôi khi ta cũng có thể sử dụng những dấu vân tay hoặc hình ảnh tròng đen
của mắt như một kiểu chữ ký sinh trắc.
Electronic
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
24
Quy trình kiểm tra chữ ký số
Dùng public key của người gửi để giải mã chữ ký số của thông điệp.
Dùng giải thuật MD5 hoặc SHA băm thông điệp đính kèm.
So sánh kết quả thu được ở trên, nếu thấy trùng nhau ta kết luận thông điệp
này không bị thay đổi trong quá trình truyền và thông điệp này là của người gửi.
Sơ đồ
Hình 2.2 Quy trình kiểm tra chữ ký số
Chữ ký số (digital signature) là một dạng chữ ký điện tử (là tập con của chữ
ký điện tử) được tạo ra bằng sự biến đổi một thông điệp dữ liệu sử dụng hệ thống
mật mã công khai, theo đó người có thông điệp dữ liệu ban đầu và khóa công khai
của người ký có thể xác định được.
2.1.3.2 Chữ ký điện tử (electronic signature) [13]
Là thông tin đi kèm theo dữ liệu (văn bản, hình ảnh, âm thanh,…) nhằm mục
đích xác định chủ nhân của dữ liệu đó.
Chữ ký điện tử được tạo lập dưới dạng từ, chữ, số, ký hiệu, âm thanh hoặc
các hình thức khác bằng phương tiện số, gắn liền hoặc kết hợp một cách logic với
thông điệp số, có khả năng xác nhận người ký thông điệp dữ liệu và xác nhận sự
chấp thuận của người đó đối với nội dung thông điệp đã ký.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
25
2.1.4 Sơ đồ chữ ký số
Sơ đồ chữ ký là bộ năm (P, A, K, S, V ), trong đó:
để mã hóa, khi đó ta được chữ ký số. Khi cần kiểm tra, bên nhận giải mã để lấy lại
chuỗi gốc (được sinh ra qua hàm băm ban đầu) và kiểm tra với hàm băm của văn
bản nhận được. Nếu 2 giá trị này khớp nhau thì bên nhận có thể tin tưởng rằng văn
bản xuất phát từ người sở hữu khóa bí mật.
Tất nhiên là chúng ta không thể đảm bảo 100% là văn bản không bị giả mạo
vì hệ thống vẫn có thể bị phá vỡ. Vấn đề xác thực đặc biệt quan trọng đối với
các giao dịch tài chính.
Tính toàn vẹn
Cả hai bên tham gia vào quá trình thông tin đều có thể tin tưởng là văn bản
không bị sửa đổi trong khi truyền vì nếu văn bản bị thay đổi thì hàm băm cũng sẽ
thay đổi và lập tức bị phát hiện.
Copyright: Tài liệu đại học ©