Số hóa bởi Trung tâm Học liệu – ĐHTN
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN VĂN THỰC
CHỮ KÝ SỐ VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH Chuyên ngành : Khoa học máy tính
Mã số : 60 48 01
Số hóa bởi Trung tâm Học liệu – ĐHTN
ii
MỤC LỤC
LỜI CẢM ƠN i
DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT iv
DANH MỤC CÁC HÌNH VẼ ÐỒ THỊ v
MỞ ĐẦU 1
CHƢƠNG 1
TỔNG QUAN VỀ MẬT MÃ VÀ ỨNG DỤNG CHỮ KÝ SỐ 3
1.1. Giới thiệu: 3
1.2. Khái niệm hệ mật mã 4
1.3. Hệ mật mã đối xứng 4
1.3.1. Khái niệm 4
1.3.2. Khái niệm Block ciphers (khối mật mã) và Stream ciphers (dòng mậtmã)5
1.3.3. Thuật toán DES 6
1.3.4. Ƣu, nhƣợc điểm của Hệ mật mã khóa đối xứng 13
1.4. Hệ mật mã khóa công khai 14
1.4.1. Hệ mật mã khóa công khai là g
ì
? 14
1.4.2. Thuật toán RSA 15
1.4.3. Ƣu, nhƣợc điểm của Hệ mật mã khóa công khai 17
1.5. Hàm băm 19
1.5.1. Khái niệm 19
2.2.2. Chức năng cơ bản của PKI 46
2.2.3. Một số chức năng khác của PKI 47
2.3. Hệ thống chứng chỉ số CA (Certificate Authority) 49
2.3.1. Chức năng của CA 50
2.3.2. Các mô h
ì
nh CA 52
2.3.3. Một số chứng chỉ số do CA phát hành 57
CHƢƠNG 3
CÀI ĐẶT HỆ THỐNG CHỨNG CHỈ SỐ THỦ NGHIỆM 59
3.1 Tổng quan về hệ thống chứng chỉ số thử nghiệm tại Trƣờng Dự bị Đại học
Dân tộc Sầm Sơn (phát biểu bài toán, mô hình hệ thống). 59
3.1.1 Phát biểu bài toán 59
3.2. Quy trình đăng kí, cấp phát và huỷ bỏ chứng chỉ 64
3.2.1. Qui trình đăng ký và cấp chứng chỉ 64
3.2.2. Qui trình huỷ bỏ chứng chỉ 65
3.3 Xây dựng phần mềm Demo về việc tạo Ký và Xác thực 65
3.3.1 Ký văn bản và xác thực chữ ký 65
3.3.2 Ký trên thông điệp 68
3.3.3 Tạo chữ ký 69
KẾT LUẬN 70
KIẾN NGHỊ CÁC HƢỚNG NGHIÊN CỨU TIẾP THEO 71
DANH MỤC TÀI LIỆU THAM KHẢO 72
Số hóa bởi Trung tâm Học liệu – ĐHTN
Domain Name System
9
WAN
Wide Area Networks
10
LAN
Local Area Network
11
MMC
Microsoft Management Console
12
CRL
Certificate Revocation List
13
LDAP
Giao thức truy nhập nhanh dịch vụ thƣ mục ( Lightweight
Directory Access Protocol)
14
RA
Thành phần cấp quyền đǎng nhập (Registration Authorities)
15
TSA
Thành phần gán nhãn thời gian (Timestamp Authorities)
16
OCSP
Online Certificate Status Protocol
khóa riêng P để giải mã khóa bí mật S …….18
Hình 5.1. Minh họa hàm băm 19
Hình 6.1 : Mô h
ì
nh tổng quát quá trình
ký
và kiểm tra chữ k
ý
21
Hình 6.2 a : Băm thông điệp 22
Hình 6.2 b :
Ký tr
ê
n bản băm 22
Hình 6.2 c : Truyền dữ liệu thông tin cần gửi 22
Hình 6.3 a : Xác minh chữ ký 23
Hình 6.3 b : Tiến hành băm thông điệp gốc đi k
è
m 23
Hình 6.3 c : Kiểm tra tính toàn vẹn của thông điệp 24
Hình 2.1 : Chứng chỉ số 31
Hình 2.2 : Khuôn dạng chứng chỉ X.509 34
Hình 2.3 : Nội dung chi tiết của chứng chỉ 37
Hình 2.4 : Khuôn dạng danh sách chứng chỉ bị thu hồi 40
Hình 2.5 : Client kiểm tra trạng thái Chứng chỉ sử dụng OCSP 42
Hình 2.6 : Các thành phần của PKI 43
Hình 2.7: Mô h
ì
nh trao đổi dữ liệu giữa CA, RA, Clients với Repository 45
Hình 2.7 : Mối quan hệ giữa các thành phần của PKI 46
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 nên sử
dụng con dấu hay chữ ký thông thƣờng mà sử dụng chữ ký số là một giải
pháp tốt nhất.
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, để đảm bảo sự
không thể chối cãi khi ai đó đƣa thông tin cá nhân của ngƣời khác lên mạng
Internet cần phải chứng thực rằng mình đã đƣa ra thông tin đó, để khi cần thì
các cơ quan pháp luật có thể sử dụng khi có sự kiện tụng, hay tranh chấp.
Trong sự phát triển không ngừng của ngành Công nghệ thông tin kéo
theo là rất nhiều ứng dụng 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ả các 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 nên sử
dụng con dấu hay chữ ký thông thƣờng mà sử dụng chữ ký số là một giải
pháp tốt nhất.
Số hóa bởi Trung tâm Học liệu – ĐHTN
2
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, để đảm bảo sự
không thể chối cãi khi ai đó đƣa thông tin cá nhân của ngƣời khác lên mạng
Internet, trao đổi thông tin giữa các cơ quan, trong một cơ quan cần phải
CHƢƠNG 1:
TỔNG QUAN VỀ MẬT MÃ VÀ ỨNG DỤNG CHỮ KÝ SỐ
1.1. Giới thiệu:
Mật mã đã đƣợc con ngƣời sử dụng từ lâu đời. Các hình thức mật
mã sơ khai đã đƣợc tìm thấy từ khoảng bốn nghìn năm trƣớc trong nền văn
minh Ai Cập cổ đại. Trải qua hàng nghìn năm lịch sử, mật mã đã đƣợc sử
dụng rộng rãi ở khắp nơi tr
ê
n thế giới từ
Đô
ng sang Tây để giữ bí mật cho
việc giao lƣu thông tin trong nhiều lĩnh vực hoạt động giữa con ngƣời và
các quốc gia, đặc biệt trong các lĩnh vực quân sự , chính trị, ngoại giao.
Mật mã trƣớc hết là một loại hoạt động thực tiễn, chức năng chính
của nó
là để giữ bí mật thông tin. Ví dụ muốn gửi một văn bản từ một ngƣời
gửi A đến một ngƣời nhận B, A phải tạo cho văn bản đó một bản mã mật
tƣơng ứng và thay vì gửi văn bản rõ thì A chỉ gửi cho B bản mã mật, B
nhận đƣợc bản mã mật và khôi phục lại văn bản mã mật mình nhận đƣợc
thành văn bản rõ
để hiểu đƣợc thông tin mà A muốn gửi cho m
ì
nh.
Do văn bản gửi đi thƣờng đƣợc chuyển qua các con đƣờng công khai
nên ngƣời khác có thể “lấy trộm” đƣợc, nhƣng vì đó là bản mật mã nên
không đọc hiểu đƣợc nội dung thông tin; Còn A có thể tạo ra bản mã mật và
B có thể giải bản mã mật thành bản rõ để hiểu đƣợc là do hai ngƣời đã có
một thoả thuận về một ch
1 . P là tập hữu hạn các các bản rõ có thể
2 . C tập hữu hạn các bản mã có thể
3 . K là tập hữu hạn các khóa có thể
4 . E là tập các hàm lập mã
5 . D là tập các hàm giải mã. Với mỗi k K, có một hàm lập mã e
k
E, e
k
: P → C và một hàm giải mã d
k
D, d
k
: C → P sao cho d
k
(e
k
(x))
= x , x P
Quá trình mã hóa và giải mã
Hình 2.1 : Quá trình mã hóa và giải m
ã1.3. Hệ mật mã đối xứng
1.3.1. Khái niệm
Trong các hệ mã đối xứng chỉ có một khóa đƣợc chia sẻ giữa các
bên tham gia liên lạc, trao đổi thông tin.
Số hóa bởi Trung tâm Học liệu – ĐHTN
quá
trình này thì thành phần quan trọng nhất cần phải đƣợc giữ bí mật
chính là khóa. Việc trao đổi, thỏa thuận về thuật toán đƣợc sử dụng trong
việc mã hóa có thể tiến hành một cách công khai, nhƣng bƣớc thỏa thuận
về khóa dùng cho việc mã hóa và giải mã phải tiến hành bí mật. [4]
1.3.2. Khái niệm Block ciphers (khối mật mã) và Stream ciphers
(dòng mật mã)
Mã hóa đối xứng có thể ph
â
n thành hai nhóm phụ :
1.3.2.1. Block ciphers (khối mật mã)
- Block ciphers: thuật toán khối - trong đó từng khối dữ liệu trong
văn bản ban đầu đƣợc thay thế bằng một khối dữ liệu khác có cùng độ dài.
Độ dài mỗi khối gọi là block size, thƣờng đƣợc tính bằng đơn vị bit . Ví dụ :
+ Thuật toán 3 – Way có kích thƣớc khối bằng 96 bit .
Số hóa bởi Trung tâm Học liệu – ĐHTN
6
+ Thuật toán DES có kích thƣớc khối là 64 bit.
- Một số thuật toán khối nhƣ DES , 3DES , AES , 3 - Way…
1.3.2.2. Stream ciphers (dòng mật mã)
- Stream ciphers: thuật toán dòng - trong đó dữ liệu đầu v
à
o đƣợc mã
hóa từng bit một .
- Các thuật toán dòng có tốc độ nhanh hơn các thuật toán khối,
đƣợc
dùng khi khối lƣợng dữ liệu cần mã hóa chƣa đƣợc biết trƣớc, ví dụ trong
là một xâu 64 bit. Hiện nay, DES và biến thể của nó (3DES) vẫn đƣợc sử
dụng th
à
nh công trong nhiều ứng dụng.
1.3.3.2. Quy tr
ì
nh của thuật toán DES
Số hóa bởi Trung tâm Học liệu – ĐHTN
7
1.3.2.2.1. Qui trình mã hóa theo DES.
Giai đoạn 1 : Bản Rõ chữ ===== Bản Rõ số (Dạng nhị phân)
Chia thành
Giai đoạn 2 : Bản Rõ số ===== Các đoạn 64 bit Rõ số
Giai đoạn 3 : 64 bit Rõ số ===== 64 bit Mã số
Kết nối
Giai đoạn 4 : Các đoạn 64 bit Mã số == Bản Mã số (Dạng nhị phân)
Giai đoạn 5 : Bản Mã số ===== Bản Mã chữ
1.3.2.2.2. Lập mã và Giải mã DES
1.3.2.2.2.1. Qui trình lập mã DES
Thuật toán DES tập trung thực hiện Giai đoạn 3 .của qui trình mã hóa.
Đó là chuyển đổi bản rõ số với 64 bit thành bản mã với 64 bit.
Sơ đồ
= L
14
f ( R
14
,
k
15
)
L
15
= R
14
R
1
= L
0
f ( R
0
, k
1
)
L
1
= R
0
2
k
16Số hóa bởi Trung tâm Học liệu – ĐHTN
8
1.3.2.2.2.2. Thực hiện mã hóa DES theo Sơ đồ
- Bản rõ là xâu x , Bản mã là xâu y, Khoá là xâu K, đều có độ dài 64
bit.
- Thuật toán mã hóa DES thực hiện qua 3 bước chính nhƣ sau:
Bước 1: Bản rõ x đƣợc hoán vị theo phép hoán vị IP, thành IP (x).
IP (x) = L
0
R
0
,trong đó L
0
là 32 bit đầu (Left),R
0
là 32 bit cuối (Right).
(IP (x) tách thành L
16
L
16
, thu đƣợc
bản mã y.
y = IP
-1
(R
16
, L
16
).
- Bảng hoán vị ban đầu IP:
+ bit 1 của IP(x) là bit 58 của x.
+ bit 2 của IP(x) là bit 50 của x.
- Bảng hoán vị cuối cùng IP
-1
:
58
50
42
34
41
33
25
17
9
1
59
51
43
35
27
19
11
3
61
53
45
37
29
21
13
5
63
55
47
39
31
23
15
7
45
13
53
21
61
29
36
4
44
12
52
20
60
28
35
3
43
11
51
19
59
27
34
2
42
10
50
18
58
26
C
1
D
1 C
2
D
2
……………………………
C
16
2
PC - 2
k
1
PC - 2
k
2
Số hóa bởi Trung tâm Học liệu – ĐHTN
10
1). Khoá K là xâu dài 64 bit, trong đó 56 bit là khoá và 8 bit để kiểm tra
tính chẵn lẻ nhằm phát hiện sai, các bit này không tham gia vào quá trình tính
toán.
Các bit kiểm tra tính chẵn lẻ nằm ở vị trí 8, 16, 24,…, 64 đƣợc xác
định, sao cho mỗi byte chứa một số lẻ các số 1. Bởi vậy mỗi sai sót đơn lẻ
đƣợc xác định trong mỗi nhóm 8 bit.
2). Tính khoá k
i
nhƣ sau:
+ Với khoá K độ dài 64 bit, ta loại bỏ các bit kiểm tra tính chẵn lẻ,
hoán vị 56 bit còn lại theo phép hoán vị PC-1:
PC-1 (K ) = C
0
D
0
Trong đó C
0
i
= PC-2 (C
i
D
i
) (48 bit).
- Phép hoán vị PC - 1: - Phép hoán vị PC - 2:
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
S
1
S
C
4
C
5
C
6
C
7
C
8
,k
):
1). Mở rộng xâu R (32 bit) thành xâu 48 bit, theo hàm mở rộng E:
E: R (32 bit) > E(R) (48 bit).
E(R) gồm 32 bit của cũ của R và 16 bit của R xuất hiện lần thứ 2.
2). Tính E(R) k, trong đó E(R) (48 bit) và k (48 bit).
Kết quả gồm 8 xâu B
j
, mỗi xâu B
j
có 6 bit (8*6 = 48):
B = B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
.
(C
j
là xâu 4 bit) theo qui
tắc sau:
- Giả sử B
j
= b
1
b
2
b
3
b
4
b
5
b
6
. (6 bit).
+ b
1
b
6
xác định biểu diển nhị phân của hàng r trong S
j
(0
r
3 ).
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
16 7 20 21 29 12 28 17
1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9
19 13 30 6 22 11 4 25
Số hóa bởi Trung tâm Học liệu – ĐHTN
13
1.3.2.2.2.5. Qui trình giải mã DES
Qui trình giải mã của DES tƣơng tự nhƣ qui trình lập mã, nhƣng theo
dùng các khóa thứ tự ngƣợc lại: k
16
, k
15
, … , k
1
.
lớn
đáp ứng đƣợc nhu cầu mã dịch, ngƣời ta xem
xét
đến việc sử dụng các hệ
mật mã khối với độ dài không lớn lắm nhƣ DES…
Mặc dù đã thực hiện việc mã hóa và giải mã bằng các hệ mật mã
khối nhƣ đã nêu ở trên thì vấn đề phân phối và thoả thuận khóa vẫn phải
đƣợc thực hiện. Nhƣ vậy phân phối và thoả thuận khóa là một vấn đề chƣa
thể đƣợc giải quyết trong các hệ mật mã khóa đối xứng.
Số hóa bởi Trung tâm Học liệu – ĐHTN
14
1.4. Hệ mật mã khóa công khai
Hệ mật mã khóa công khai ra đời đã giải quyết vấn đề phân phối và
thoả thuận khóa của mật mã khóa đối xứng.
1.4.1. Hệ mật mã khóa công khai là g
ì
?
Hệ mật mã khóa công khai hay còn đƣợc gọi là hệ mật mã phi đối
xứng sử dụng một cặp khóa, khóa mã hóa còn gọi là khóa công khai (public
key) và khóa giải mã đƣợc gọi là khóa bí mật hay khóa ri
ê
ng (private key).
Trong hệ mật này, khóa mã hóa khác với khóa giải mã. Về mặt toán học
thì từ khóa công khai rất khó tính đƣợc khóa ri
ê
ng. Biết đƣợc khóa n
à
y
chính
là của Bob chứ không phải của ai khác ( thông qua chứng chỉ điện tử ),
Alice dùng nó để mã hóa thông điệp của m
ì
nh và gửi Bob.
Khi Bob nhận đƣợc bức thông điệp đã mã hóa, Bob sẽ dùng ch
ì
a
khóa bí mật của mình để giải mã nó. Nếu giải mã thành công th
ì
bức thông
điệp đó đúng là gửi cho Bob. [2]
1.4.2. Thuật toán RSA
Hệ RSA là hệ đƣợc cộng đồng chuẩn quốc tế và công nghiệp chấp
nhận rộng rãi trong việc thực
thi mật mã khóa công khai.
Hệ mật mã RSA, do Rivest, Shamir và Adleman tìm ra, đã đƣợc công
bố lần đầu tiên vào tháng 8 năm 1977 tr
ê
n tạp chí Scientific American. Hệ
mật mã RSA đƣợc sử dụng rộng rãi trong thực tiễn đặc biệt cho mục đích
bảo mật và xác thực dữ liệu số. Tính bảo mật và an toàn của chúng đƣợc
bảo đảm bằng độ phức tạp của một bài toán số học nổi tiếng là bài toán
phân tích số nguyên thành các thừa số nguyên tố.
Thuật toán RSA đƣợc mô tả nhƣ hình 4.2:
- Tính khóa giải mã d = e
-1
mod ((p-1)*(q-1))
- Xây dựng khóa công khai từ (n, e)
- Xây dựng khóa ri
ê
ng từ (d, n)
Mã h
ó
a :
c = m
e
mod n Số hóa bởi Trung tâm Học liệu – ĐHTN
16
Sơ đồ tạo chữ ký RSA
Sơ đồ chữ ký RSA có độ phức tạp tính toán phụ thuộc vào việc giải
quyết bài toán lũy thừa theo modulo các số rất lớn. Các phƣơng pháp tấn công
RSA và các vấn đề khác liên quan đƣợc đƣa ra bởi Davia, Jonge và Chaum.
1/. Thuật toán sinh khoá
+ Chọn hai số nguyên tố lớn ngẫu nhiên p và q.
Tính n = pq và = (p - 1)(q - 1 ).
+ Chọn số tự nhiên ngẫu nhiên b:
1< b < và UCLN(b, ) = 1 hay b
Z
a
(mod n) = 31229978
4430237
(mod
55465219) = 30729435.
Xác nhận chữ ký:
+ Tính m' = s
b
(mod n) = 30729435
5
(mod 55465219) = 31229978.
+ Chữ ký đúng vì m’ = m.
1.4.3. Ưu, nhược điểm của Hệ mật mã khóa công khai
1.4.3.1. Ưu điểm
Vấn đề còn tồn đọng của hệ mật mã khóa đối xứng đƣợc giải
quyết nhờ hệ mật mã khóa công khai. Chính ƣu điểm này đã thu hút
nhiều trí tuệ vào việc đề xuất, đánh giá các hệ mật mã công khai.
Một vấn đề nữa nảy sinh khi sử dụng các hệ mật mã khóa công khai
l
à
việc xác thực mà trong mô hình hệ mật mã khóa đối xứng không đặt ra.
Do các khóa mã công khai đƣợc công bố một cách công khai tr
ê
n mạng
cho n
ê
n việc đảm bảo rằng “ khóa đƣợc công bố có đúng là của đối tƣợng
cần liên lạc hay không ? ” là một kẽ hở có thể bị lợi dụng. Vấn đề xác thực
này đƣợc giải quyết cũng chính bằng các hệ mật mã khóa công khai. Nhiều
thủ tục xác thực đã đƣợc nghiên cứu và sử dụng nhƣ Kerberos, X.509…
Hình 4.3.2.1 : Mã hóa thông điệp sử dụng khóa bí mật S để m
ã t
hông
điệp và khóa công khai P để mã khoa bí mật S Hình 4.3.2.2 : Giải mã thông điệp sử dụng khóa bí mật S để giải m
ã
thông điệp và khóa riêng P để giải mã khóa bí mật S. [8] Số hóa bởi Trung tâm Học liệu – ĐHTN
19
1.5. Hàm băm
1.5.1. Khái niệm
Hàm băm (hash function) là giải thuật nhằm sinh ra các giá trị
băm tƣơng ứng với mỗi khối dữ liệu (có thể là một chuỗi kí tự, một đối
tƣợng…) các thuật toán này không sử dụng khoá để mã hoá , nó có
nhiệm vụ băm thông điệp đƣợc đƣa vào theo một thuật toán h một chiều
nào
đó,
rồi đƣa ra một bản băm – văn bản đại diện – có kích thƣớc cố định.
Giá trị của hàm băm là duy nhất và không thể suy ngƣợc lại đƣợc nội
nh thông
điệp x’ thì h(x’) ≠ h(x). Cho dù chỉ là một sự thay đổi nhỏ hay chỉ là xoá đi
1 bit dữ liệu của thông điệp thì giá trị băm cũng vẫn thay đổi.
- Nội dung của thông điệp gốc không thể bị suy ra từ giá trị h
à
m
băm. Nghĩa là với thông điệp x thì dễ dàng tính đƣợc z = h(x), nhƣng lại
Băm
(sử dụng hàm băm)
Văn bản đã băm
(độ dài cố định)
Văn bản cần băm
(độ dài bất kỳ)
Copyright: Tài liệu đại học ©