ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN

Trƣơng Mạnh Cƣờng

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

NGHIÊN CỨU CÁC THUẬT TOÁN MÃ HÓA KHÓA CÔNG
KHAI VÀ ỨNG DỤNG TRONG CHỮ KÝ ĐIỆN TỬ
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60 48 01

THÁI NGUYÊN - 2014

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

/>

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CNTT & TT THÁI NGUYÊN

Trƣơng Mạnh Cƣờng

LUẬN VĂN THẠC SỸ KHOA HỌC MÁY TÍNH

NGHIÊN CỨU CÁC THUẬT TOÁN MÃ HÓA KHÓA CÔNG
KHAI VÀ ỨNG DỤNG TRONG CHỮ KÝ ĐIỆN TỬ

GIÁO VIÊN HƢỚNG DẪN
PGS.TS BÙI THẾ HỒNG


2.1.2.1 Họ hàm băm SHA (Secure Hash Algorithm) ............................ 29
2.1.2.2 Họ hàm băm MD (Message-Digest algorithm) ........................ 32
2.2 Chữ ký điện tử ....................................................................................... 39
2.2.1 Tổng quan về chữ ký điện tử .................................................... 39
2.2.2 Định nghĩa chữ ký điện tử........................................................ 42
Số hóa bởi trung tâm học liệu

/>

2.2.3 Một số qui ước trong chữ ký điện tử ........................................ 43
2.3 Những vấn đề trao đổi cặp khóa đặt ra trong thực tế ....................... 44
2.3.1 Sự tương tự với bưu chính ....................................................... 44
2.3.2 Mối quan hệ giữa khóa công khai với thực thể sở hữu khóa. 47
2.3.3 Các vấn đề liên quan tới thời gian thực................................... 47
CHƢƠNG 3: XÂY DỰNG ỨNG DỤNG .................................................. 52
3.1 Phát triển ứng dụng .............................................................................. 52
3.1.1 Sơ đồ hệ thống và chức năng của ứng dụng .......................... 52
3.1.1.1 Sơ đồ hệ thống.......................................................................... 52
3.1.1.2 Chức năng của ứng dụng .......................................................... 53
3.1.2 Phân tích ứng dụng................................................................... 54
3.1.2.1 Tạo khóa công khai và bí mật bằng thuật toán RSA................. 54
3.1.2.2 Băm dữ liệu bằng hàm băm MD5 ............................................. 54
3.1.3.3 Mã hóa giá trị băm bằng khóa bí mật ...................................... 54
3.1.4.4 Giải mã bằng khóa công khai và kiểm tra tính toàn vẹn của văn
bản......................................................................................................... 54
3.2. Cài đặt ứng dụng .................................................................................. 55
3.2.1. Giới thiệu chương trình .......................................................... 55
3.2.2. Một số giao diện chính trong chương trình............................ 55
3.2.2.1 Giao diện chương trình............................................................. 55
3.2.2.2 Tạo file khóa công khai và bí mật, lưu file khóa....................... 56

Secure Hash Algorithm

MAC

Message Authentication Code

PKCS

Public Key Cryptography Standards

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

/>

DANH MỤC CÁC HÌNH
STT

TÊN HÌNH

TRANG

1

Hình 1.1: Kênh liên lạc

9

2

Hình 2.1: Hoạt động của một hàm băm tiêu biểu

Hình 3.2: Giao diện chương trình

55

8

Hình 3.3: Giao diện tao cặp khóa

56

9

Hình 3.4: Giao diện lựa chọn văn bản cần ký

56

10

11

Hình 3.5: Giao diện ký văn bản đã lựa chọn bằng khóa
bí mật
Hình 3.6: Giao diện giải mã văn bản đã ký bằng khóa
công khai

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

/>
57


Nghiên cứu các giải thuật mã hóa khóa công khai.
Nghiên cứu về chữ ký điện tử, tìm hiểu về hàm băm và các giải thuật
về hàm băm.
Số hóa bởi trung tâm học liệu

/>

Cài đặt thử nghiệm một giải thuật sinh chữ ký điện tử.
Một số thuật toán sinh khóa công khai, khóa bí mật;
Một số hàm băm thường sử dụng hiện nay;
Chữ ký điện tử.
4. Ph
Tìm hiểu dựa trên cơ sở lý thuyết, các thuật toán hay về sinh
khóa công khai, khóa bí mật đã có từ trước. So sánh để thấy
những ưu điểm, những hạn chế của từng thuật toán.
Từ cơ sở đó có thể cải tiến, hoặc triển khai ứng dụng cài đặt
một giải thuật tối ưu nhất vào thực tiễn.
Trong quá trình triển khai ứng dụng nêu lên những hạn chế của
đề tài và những khó khăn trong thực hiện đề tài.
Đề xuất hướng phát triển của đề tài trong thời gian tới.
ăn
Ngoài phần mở đầu và kết luận đề tài có cơ cấu gồm 3 chương:
Chương 1 : Tổng quan về các thuật toán mã hóa khóa công khai
Chương 2: Hàm băm và chữ ký điện tử
Chương 3: Xây dựng ứng dụng.

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

/>


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

/>

tính chất khóa công khai và bí mật như đề cập ở trên mà cả hai khóa (cho mã
hóa và giải mã) đều cần phải giữ bí mật.
Trong mật mã hóa khóa công khai, khóa cá nhân phải được giữ bí mật
trong khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng
để mã hóa và khóa còn lại dùng để giải mã. Đ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ệ thống mật mã hóa khóa công khai có thể sử dụng với các mục
đích:
Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải
mã được.
Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo
với một khóa bí mật nào đó hay không.
Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin
mật giữa 2 bên.
Thông thường, các kỹ thuật mật mã hóa khóa công khai đòi hỏi khối
lượng tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi
điểm mà chúng mang lại khiến cho chúng được áp dụng trong nhiều ứng dụng.
Có thể hình dung hệ mật này tương tự như sau. A đặt một vật vào một
hộp kim loại và rồi khoá nó lại bằng một khoá số do B để lại. Chỉ có B là
người duy nhất có thể mở được hộp vì chỉ có người đó mới biết tổ hợp mã
của khoá số của mình.
Thuật toán mã hóa công khai là thuật toán được thiết kế sao cho khóa
mã hóa là khác so với khóa giải mã. Mà khóa giải mã hóa không thể tính
toán được từ khóa mã hóa. Khóa mã hóa gọi là khóa công khai (public key),
khóa giải mã được gọi là khóa riêng (private key).


Năm 1874, William Stanley Jevons xuất bản một cuốn sách mô tả
mối quan hệ giữa các hàm một chiều với mật mã học đồng thời đi sâu vào bài
toán phân tích ra thừa số nguyên tố (sử dụng trong thuật toán RSA). Tháng 7
năm 1996, một nhà nghiên cứu đã bình luận về cuốn sách trên như sau:
Trong cuốn The Principles of Science: A Treatise on Logic and
Scientific Method được xuất bản năm 1890, William S. Jevons đã phát hiện
nhiều phép toán rất dễ thực hiện theo một chiều nhưng rất khó theo chiều
ngược lại. Một ví dụ đã chứng tỏ mã hóa rất dễ dàng trong khi giải mã thì
không. Vẫn trong phần nói trên ở chương 7 (Giới thiệu về phép tính ngược)
tác giả đề cập đến nguyên lý: ta có thể dễ dàng nhân các số tự nhiên nhưng
Số hóa bởi trung tâm học liệu

/>

phân tích kết quả ra thừa số nguyên tố thì không hề đơn giản. Đây chính là
nguyên tắc cơ bản của thuật toán mật mã hóa khóa công khai RSA mặc dù
tác giả không phải là người phát minh ra mật mã hóa khóa công khai.
Thuật toán mật mã hóa khóa công khai được thiết kế đầu tiên bởi
James H. Ellis, Clifford Cocks, và Malcolm Williamson tại GCHQ (Anh)
vào đầu thập kỷ 1970. Thuật toán sau này được phát triển và biết đến dưới
tên Diffie-Hellman, và là một trường hợp đặc biệt của RSA. Tuy nhiên
những thông tin này chỉ được tiết lộ vào năm 1997.
Năm 1976, Whitfield Diffie và Martin Hellman công bố một hệ thống
mật mã hóa khóa bất đối xứng trong đó nêu ra phương pháp trao đổi khóa
công khai. Công trình này chịu sự ảnh hưởng từ xuất bản trước đó của Ralph
Merkle về phân phối khóa công khai. Trao đổi khóa Diffie-Hellman là
phương pháp có thể áp dụng trên thực tế đầu tiên để phân phối khóa bí mật
thông qua một kênh thông tin không an toàn. Kỹ thuật thỏa thuận khóa của
Merkle có tên là hệ thống câu đố Merkle.
Thuật toán đầu tiên cũng được Rivest, Shamir và Adleman tìm ra vào

chung, các thuật toán mã hóa khóa công khai cần phải được sử dụng một
cách thận trọng.
1.2 Các thuật toán mật mã hóa khóa công khai
1.2.1 Thuật toán RSA
Thuật toán được Ron Rivest, Adi Shamir và Len Adleman mô tả lần
đầu tiên vào năm 1977 tại Học viện Công nghệ Massachusetts (MIT). Tên
của thuật toán lấy từ 3 chữ cái đầu của tên 3 tác giả.
Thuật toán RSA có hai khóa: khóa công khai (hay khóa công cộng) và
khóa bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong
quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi
người và được dùng để mã hóa. Những thông tin được mã hóa bằng khóa
công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách
khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí
mật) mới có thể giải mã được.
Ta có thể mô phỏng trực quan một hệ mật mã hóa khoá công khai như
sau: giả sử B muốn gửi cho A một thông tin mật mà B muốn duy nhất A có
thể đọc được. Để làm được điều này, A gửi cho B một chiếc hộp có khóa đã
mở sẵn và giữ lại chìa khóa. B nhận chiếc hộp, cho vào đó một tờ giấy viết
Số hóa bởi trung tâm học liệu

/>

thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại,
sau khi sập chốt khóa ngay cả B cũng không thể mở lại được, không đọc lại
hay sửa thông tin trong thư được nữa). Sau đó B gửi chiếc hộp lại cho A và
A mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ
này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa
chính là khóa bí mật.
Tạo khóa
Giả sử A và B cần trao đổi thông tin bí mật thông qua một kênh không

cũng là số tự nhiên. Khi đó sử dụng giá trị
Từ bước 3, sử dụng
thay cho
Khóa công khai bao gồm:
n – môđun và e - số mũ công khai (cũng gọi là số mũ mã hóa).
Khóa bí mật bao gồm:
n – môđun và d - số mũ bí mật (cũng gọi là số mũ giải mã).
Số hóa bởi trung tâm học liệu

/>

Mã hóa
Giả sử B muốn gửi một thông điệp M cho A. Đầu tiên B chuyển M
thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại
M) được thỏa thuận trước. Sau đó, B yêu cầu A gửi cho mình khóa công khai
của A gồm n và e.
B sẽ tính c là bản mã hóa của m theo công thức:
Có thể dễ dàng tính được c bằng cách sử dụng phương pháp tính hàm
mũ (theo môđun) bằng thuật toán bình phương và nhân. Cuối cùng B gửi c
cho A.
Giải mã
A nhận c từ B và tính được m từ c theo công thức sau:
Biết m, A tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình
giải mã hoạt động vì ta có
.
Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ)
nên:

và
Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung

Mã

C = 887 mod 187 = 11

Giải mã

M = 1123 mod 187 = 88

Có thể dùng định lý phần dư Trung Hoa để giải mã cho nhanh như sau:
a. Tính 1123 mod 11 = 0
b. Tính 1123mod 17 = (-6)23 mod 17 = (-6)16(-6)4 (-6)2 (-6) mod 17 = 3
Vì (-6)2 mod 17 = 2, nên (-6)4 mod 17 = 4, (-6)8 mod 17 = -1
(-6)16 mod 17 = 1
c. 11-1 mod 17 = (-6)-1 mod 17 = 14 nên c2 = 11(11-1 mod 17) = 11
(14 mod 17) = 154
Số hóa bởi trung tâm học liệu

/>

Vậy

M = (3.154) mod 187 = 462 mod 187 = 88

Độ an toàn của thuật toán RSA
Độ an toàn của thuật toán RSA dựa vào độ khó giải của việc tính
Ф(N) và điều này đòi hỏi chúng ta cần phân tích N ra thừa số nguyên tố.
Thuật toán phân tích số nguyên tố hiệu quả nhất hiện nay là Berent-Pollard,
chúng ta hãy xem bảng thống kê sau để thấy được tốc độ hoạt động của nó:
Số chữ số trong hệ thập phân của N


Trên thực tế việc để cài đặt RSA cần phải thực hiện các thao tác
modulo với các số 300 chữ số (hay 1024 bit) mà hiện nay các máy tính mới
chỉ thao tác với các số nguyên 128 bit, điều này dẫn đến nhu cầu về các thư
viện số học nhân chính xác để làm việc với các số nguyên lớn này. Ngoài ra
việc sử dụng RSA cần tới các số nguyên tố lớn nên chúng ta cũng phải có
một cơ sở dữ liệu các số nguyên tố.
1.2.2 Trao đổi và thỏa thuận khóa Diffie-Hellman
Thuật toán thỏa thuận khóa Diffie-Hellman là một thuật toán dùng để
trao đổi khóa chứ không dùng để mật mã hóa dữ liệu. Tuy nhiên DiffieHellman lại có ích trong giai đoạn trao đổi khóa bí mật của các thuật toán
mật mã đối xứng. Thuật toán thỏa thuận khóa Diffie-Hellman thúc đẩy việc
nghiên cứu đề xuất các mã khoá công khai, một trong những vấn đề quan
Số hóa bởi trung tâm học liệu

/>

trọng liên quan trực tiếp đến tính an toàn của các thuật toán mật mã đối
xứng là vấn đề thống nhất khoá bí mật giữa các thực thể thông tin.
Giả sử A và B muốn liên lạc sử dụng hệ mật khoá bí mật. Để thoả
thuận mật khoá K chung cho cả hai bên qua một kênh không an toàn mà
không ai khác có thể biết được, A và B có thể dùng thủ tục thoả thuận
khoá Diffie -Hellman sau:
Thuật toán:
Khởi tạo Diffie Hellman
Mọi người dùng thỏa thuận dùng tham số chung:
o Số nguyên tố rất lớn q hoặc đa thức.
o α là căn nguyên tố của mod q.
Mỗi người dùng (A chẳng hạn) tạo khoá của mình:
o Chọn một khoá mật (số) của A: xA < q
o Tính khoá công khai của A: yA = αxA mod q.
o Mỗi người dùng thông báo công khai khoá của mình yA.

a Diffie-

Hellman.

1985. Tính an toàn

của nó dựa trên tính khó giải của bài toán logarit rời rạc. Nhược điểm chính
của nó là kích thước thông tin sau khi mã hóa gửi đi sẽ tăng gấp đôi so với
thông tin gốc. Tuy nhiên so với thuật toán RSA, ElGammal không có nhiều
rắc rối về vấn đề bản quyền sử dụng. Trong thuật toán ElGammal một thông
điệp bất kỳ có thể có nhiều chữ ký hợp lệ khác nhau.
Thuật toán:
Ban đầu chọn một số nguyên tố lớn p và hai số nguyên tùy ý nhỏ hơn
p là a (a là một phần tử nguyên thủy của Z*p) và x (x là của người nhận, bí
mật), sau đó tính:
y = ax mod p
Để mã hóa một thông điệp M (là một số nguyên trên Zp) thành bản mã
C người gửi chọn một số ngẫu nhiên k nhỏ hơn p và tính khóa mã K:
K = yk mod p
Sau đó tính cặp bản mã:
. C1 = ak mod p
.C2 = K.M mod p
Và gửi bản mã C = (C1,C2) đi (lưu ý là sau đó k sẽ bị hủy).
Để giải mã thông điệp đầu tiên ta cần tính lại khóa mã hóa thông
điệp K:
Số hóa bởi trung tâm học liệu

/>

K = C1x mod p = akx mod p


/>

Thuật toán này còn có tên gọi khác là thuật toán cân bằng thời gian –
bộ nhớ (time – memory trade off), có nghĩa là nếu chúng ta có đủ bộ nhớ thì
có thể sử dụng bộ nhớ đó để giảm thời gian thực hiện của thuật toán xuống.
Input: số nguyên tố p, phần tử nguyên thủy a của Zp*, số nguyên y
Output: tìm x sao cho ax mod p = y
Thuật toán:
Gọi m = [(p-1)1/2] (lấy phần nguyên)
Bước 1: tính amj mod p với 0
-Thuật toán Diffie-Hellman: dùng để trao đổi khóa chứ không dùng để
mật mã hóa dữ liệu.
- ElGammal: n
,
ElGammal

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

.

/>

Nhận xét chung:
Kỹ thuật mật mã bất đối xứng hoàn toàn có thể đáp ứng được những
yêu cầu về bảo mật hệ thống như trong kỹ thuật mật mã đối xứng, mặc dù
tốc độ thực thi của mã bất đối xứng thường thấp hơn do bản chất thuật toán
dựa trên các thao tác số học chứ không dựa trên các thao tác xử lý bit. Hơn
nữa, mã bất đối xứng chỉ phù hợp với việc thực thi bằng phần mềm.
Mật mã bất đối xứng đảm bảo được 2 yêu cầu cơ bản của thông tin là
tính bí mật và tính toàn vẹn.

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

/>

CHƢƠNG 2: HÀM BĂM VÀ CHỮ KÝ ĐIỆN TỬ
2.1 Hàm băm
2.1.1 Tổng quan về hàm băm
Giới thiệu hàm băm
Hàm băm (hash function) là một giải thuật nhằm sinh ra các giá trị

Cho x không thể tìm được y sao cho H(y) = H(x). Đây là tính chất
chống đỡ va chạm yếu, không tìm được thông điệp có cùng Hàm băm với
thông tin đã cho; và không thể tìm được x, y sao cho H(y) = H(x). Đây gọi
là tính chất chống đỡ va chạm mạnh, đây là yêu cầu cao hơn tính chống đỡ
va chạm yếu.
Đặc trƣng của hàm băm
Hàm băm h là hàm một chiều (one-way hàm băm) với các đặc tính:
- Với thông điệp đầu vào x thu được giá trị băm z = h(x) là duy nhất.
- Nếu dữ liệu trong thông điệp x thay đổi để thành thông điệp x’ thì
h(x’)

h(x) => Hai thông điệp hoàn toàn khác nhau thì giá trị hàm băm cũng

khác nhau.
Nội dung của thông điệp gốc không thể bị suy ra từ giá trị hàm băm
=> Với thông điệp x thì dễ dàng tính được z = h(x), nhưng lại không thể
(thực chất là khó) suy ngược lại được x nếu chỉ biết giá trị hàm băm h.
Vai trò hàm băm trong mật mã hiện đại
Được dùng để xác thực tính nguyên vẹn dữ liệu;
Được dùng trong quá trình tạo chữ kí số trong giao dịch điện tử;
Vai trò cơ bản của các hàm băm mật mã là một giá trị băm coi như
ảnh đại diện thu gọn, đôi khi gọi là một dấu vết (imprint), vân tay số (digital
fingerprint), hoặc tóm lược thông báo (message digest) của một xâu đầu vào,
và có thể được dùng như là một định danh duy nhất với xâu đó;
Các hàm băm thường được dùng cho toàn vẹn dữ liệu kết hợp với các
lược đồ chữ kí số;
Số hóa bởi trung tâm học liệu

/>