Số hóa bởi trung tâm học liệu 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
PGS.TS BÙI THẾ HỒNG THÁI NGUYÊN - 2014
Số hóa bởi trung tâm học liệu
MỤC LỤC
DANH MỤC CÁC CHỮ TIẾNG ANH VIẾT TẮT 5
DANH MỤC CÁC HÌNH 6
MỞ ĐẦU 7
1. Lý do nghiên cứu đề tài 7
7
8
8
8
CHƢƠNG 1. TỔNG QUAN VỀ CÁC THUẬT TOÁN MÃ HÓA
KHÓA CÔNG KHAI 9
1.1 Khái niệm mã hóa khóa công khai 9
1.1.1 Mật mã hóa khóa đối xứng 9
1.1.2 Mật mã hóa khóa công khai 9
1.2 Các thuật toán mật mã hóa khóa công khai 13
1.2.1 Thuật toán RSA 13
1.2.2 Trao đổi và thỏa thuận khóa Diffie-Hellman 17
1.2.3 Hệ mã ElGammal 19
1.3 So sánh ƣu nhƣợc điểm của các thuật toán 21
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
3.2.2.3 Lựa chọn văn bản 56
3.2.2.4 Ký văn bản 57
3.2.2.5 Giải mã chữ ký 57
58
GIẢI THÍCH MỘT SỐ THUẬT NGỮ 59
TÀI LIỆU THAM KHẢO 60 Số hóa bởi trung tâm học liệu
DANH MỤC CÁC CHỮ TIẾNG ANH VIẾT TẮT
NIST National Institute of Standards and Technology
RSA R. Rivest, A. Shamir, L. Adleman
MITM Man-In-The-Middle attack
MD Message-Digest algorithm
SHA Secure Hash Algorithm
MAC Message Authentication Code
PKCS Public Key Cryptography Standards
25
4
Hình 2.3: Mô hình xác minh chữ ký, kiểm tra tính toàn
vẹn của thông điệp
26
5
Hình 2.4: Mô hình chữ ký điện tử
40
6
Hình 3.1: Sơ đồ hệ thống ứng dụng
53
7
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
Hình 3.5: Giao diện ký văn bản đã lựa chọn bằng khóa
bí mật
57
11
Hình 3.6: Giao diện giải mã văn bản đã ký bằng khóa
công khai
57
cụ thể là áp dụng các thuật toán mã hóa khóa công khai, hàm băm, chữ ký
điện tử, làm mục tiêu nghiên cứu. Mong muốn những tìm tòi của mình có thể
xây dựng được ứng dụng phục vụ cho cơ quan, đơn vị nơi học viên công tác.
2.
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.
nhau là khóa công khai và khóa cá nhân (hay khóa bí mật).
Thuật ngữ "mật mã hóa khóa bất đối xứng" thường được dùng đồng
nghĩa với "mật mã hóa khóa công khai" mặc dù hai khái niệm không hoàn
toàn tương đương. Có những thuật toán mật mã khóa bất đối xứng không có
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
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
Khóa giải mã
A
Bộ mã hóa
Bộ giải mã
B
Khóa mã hóa
Oscar
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
bài toán nổi tiếng vẫn được cho là không có lời giải trong thời gian đa thức
(Xem thêm: Lý thuyết độ phức tạp tính toán). Nhìn chung, chưa có thuật
toán nào được chứng minh là an toàn tuyệt đối (như hệ thống mật mã sử
dụng một lần). Vì vậy, cũng giống như tất cả các thuật toán mật mã nói
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
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
Quốc, ta có:
.
hay:
. Số hóa bởi trung tâm học liệu
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 c
2
= 11(11
-1
mod 17) = 11
(14 mod 17) = 154
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 Diffie-
Hellman 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: x
A
< q
o Tính khoá công khai của A: y
A
= α
x
AB
cho đến khi họ
chọn khoá mới.
Kẻ thám mã cần x, do đó phải giải tính logarit rời rạc
Ví dụ:
Hai người sử dụng A & B muốn trao đổi khoá phiên:
• Đồng ý chọn số nguyên tố q=353 và α=3
• Chọn các khoá mật ngẫu nhiên:
Số hóa bởi trung tâm học liệu
A chọn x
A
=97, B chọn x
B
=233
• Tính các khoá công khai:
y
A
=3
97
mod 353 = 40 (A)
y
B
=3
233
mod 353 = 248 (B)
• Tính khoá phiên chung:
K
AB
mật), sau đó tính:
y = a
x
mod p
Để mã hóa một thông điệp M (là một số nguyên trên Z
p
) 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 = y
k
mod p
Sau đó tính cặp bản mã:
. C
1
= a
k
mod p
.C
2
= 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 = C
1
x
mod p = a
= 50 mod 97
. C
2
= 75.3 mod 97 = 31 mod 97
Vậy bản mã thu được là C = (50,31)
Vấn đề đối với hệ mã công khai nói chung và ElGammal nói riêng là
tốc độ (do phải làm việc với số nguyên lớn), bên cạnh đó dung lượng bộ nhớ
dành cho việc lưu trữ các khóa cũng lớn. Với hệ mã ElGammal chúng ta cần
gấp đôi bộ nhớ để chứa bản mã so với các hệ mã khác. Ngoài ra do việc sử
dụng các số nguyên tố nên việc sinh khóa và quản lý khóa cũng khó khăn
hơn so với các hệ mã khối. Trên thực tế các hệ mã khóa công khai thường
được sử dụng kết hợp với các hệ mã khối (mã hóa khóa của hệ mã) hoặc để
mã hóa các thông tin có dung lượng nhỏ và là một phần quan trọng của một
phiên truyền tin nào đó.
Thám mã với hệ mã ElGmamal:
Để thực hiện thám mã hệ mã ElGammal chúng ta cần giải bài toán
logarit rời rạc. Ở đây chúng ta sẽ xem xét thuật toán có thể áp dụng để giải
bài toán này.
Thuật toán Shank:
Số hóa bởi trung tâm học liệu
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 Z
p
*
, số nguyên y
Output: tìm x sao cho a
2
xem có tồn tại cặp (j, a
-i
mod p)
và (i, ya
-i
mod p) nào mà a
mj
mod p = ya
-I
mod p (tọa độ thứ hai của cặp bằng
nhau)
Bước 6: x = (mj + i) mod (p - 1). Kết quả này có thể kiểm chứng từ
công thức a
mj
mod p = ya
-i
mod p => a
mj + i
mod p = y mod p => x = (mj + i)
mod (p - 1).
Độ phức tạp của thuật toán phụ thuộc vào m = [(p-1)
1/2
], với giá trị
của m, chúng ta cần tính các phần tử thuộc hai danh sách L
1,
L
2
đều là các
phép toán lũy thừa phụ thuộc vào j và i, i và j lại phụ thuộc vào m nên có thể
mã hoá các bản tin ngắn, trao đổi chìa khoá của các hệ mã đối xứng, đặc biệt
là trong giao thức xác nhận chủ thể.
-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
chiều tìm ảnh lại dễ dàng.
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ố;
Copyright: Tài liệu đại học ©