ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thu Hồng

HỆ MẬT MÃ KHOÁ CÔNG KHAI
ỨNG DỤNG BẢO MẬT THÔNG TIN TRONG
THƯƠNG MẠI ĐIỆN TỬ LUẬN VĂN THẠC SỸ


2.1.1. Nguyên lý cơ bản của hệ mật mã khoá công khai - 27 -
2.1.2. Hoạt động của hệ mật mã khoá công khai - 27 -
2.1.3. Khả năng ứng dụng của hệ mật mã khoá công khai - 29 -
2.1.4. Các yêu cầu của hệ mật mã khoá công khai - 30 -

- 3 -
2.2. HỆ MẬT MÃ KHÓA CÔNG KHAI BA LÔ - 31 -
2.2.1. Bài toán ba lô - 31 -
2.2.2. Bài toán ba lô siêu tăng - 31 -
2.2.3. Hệ mật mã khoá công khai ba lô Merkle-Hellman - 32 -
2.2.3.1. Mô tả các quá trình tạo khoá, mã hoá, giải mã - 32 -
2.2.3.2. Tính đúng của quá trình giải mã - 35 -
2.2.4. Đánh giá hệ mật mã khoá công khai ba lô - 37 -
2.2.4.1. Độ an toàn - 37 -
2.2.4.2. Hiệu suất thực hiện và ứng dụng - 38 -
2.3. HỆ MẬT MÃ KHÓA CÔNG KHAI ELGAMAL - 38 -
2.3.1. Bài toán logarithm rời rạc - 38 -
2.3.2. Định nghĩa các tập làm việc của hệ mật mã ElGamal - 39 -
2.3.3. Mô tả các quá trình tạo khoá, mã hoá, giải mã - 39 -
2.3.4. Tính đúng của quá trình giải mã - 40 -
2.3.5. Đánh giá hệ mật mã công khai Elgamal - 42 -
2.3.5.1. Độ an toàn - 42 -
2.3.5.2. Hiệu suất thực hiện và ứng dụng - 43 -
2.4. HỆ MẬT MÃ KHÓA CÔNG KHAI RSA - 43 -
2.4.1. Bài toán phân tích số nguyên - 43 -
2.4.2. Định nghĩa các tập làm việc của hệ RSA - 44 -
2.4.3. Mô tả các quá trình tạo khoá, mã hoá và giải mã - 44 -
2.4.5. Chi phí thực hiện các phép tính cơ bản trong mã hoá và giải mã - 48 -
2.4.6. Một số phương pháp thám mã hệ mật mã RSA - 49 -
2.4.7. Các thuận toán phân tích ra thừa số - 52 -

3.2.1. Chữ ký mù - 79 -
3.2.2. Lược đồ chữ ký Schnorr - 80 -
3.2.3. Chia cắt và lựa chọn (Cut and Choose) - 81 -
3.2.4. Chia sẻ bí mật - 83 -
3.2.5. Giao thức truyền bit - 83 -
3.2.6. Bài toán biểu diễn trong nhóm nguyên tố - 84 -
3.3. HỆ THỐNG TIỀN ẨN DANH (Chaum-Fiat-Naor) - 85 -
3.3.1. Giao thức rút tiền - 85 -

- 5 -
3.3.2. Giao thức thanh toán - 86 -
3.3.3. Giao thức gửi tiền - 86 -
3.3.4. Khả năng đáp ứng các đặc trưng - 86 -
3.3.5. Chi phí về tiền và thời gian - 88 -
3.3.6. Khả năng tấn công - 88 -
3.4. HỆ THỐNG TIỀN ẨN DANH KHÔNG CÓ KHẢ NĂNG GHI NHẬN - 88 -
3.4.1. Giao thức rút tiền - 89 -
3.4.2. Giao thức thanh toán - 93 -
3.4.3. Giao thức gửi tiền - 93 -
3.4.4. Khả năng đáp ứng các đặc trưng - 93 -
3.4.5. Khả năng tấn công - 94 -
3.5. LƯỢC ĐỒ BRAND - 94 -
3.5.1. Giao thức mở tài khoản - 95 -
3.5.2. Giao thức rút tiền - 96 -
3.5.3. Giao thức thanh toán - 98 -
3.5.4. Giao thức gửi tiền - 99 -
3.5.5. Khả năng đáp ứng các đặc trưng - 99 -
3.5.6. Khả năng tấn công - 101 -
3.5.7. Chi phí về tiền và thời gian - 102 -
3.5.8. Khó khăn - 102 -

giải mã của Hệ ba lô Merkele-Hellman 34
Bảng 2.3. Các bước toạ khoá, mã hoá, giải mã của Hệ ElGamal 40
Bảng 2.4. Các bước tạo khoá, mã hoá, giải mã của hệ RSA 45
Bảng 2.5. Bảng chi phí thời gian cần thiết để phân tích các số nguyên N 54
Bảng 3.1. Một số hệ thống tiền điện tử Off-line 79 - 8 -
DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Sơ đồ quá trình viết bí mật thông tin 12
Hình 1.2. Mô hình mã hóa khóa đối xứng 15
Hình 1.3. Mô hình mã hóa không đối xứng 16
Hình 2.1. Sơ đồ nguyên lý cơ bản của hệ mật mã khóa công khai 27
Hình 2.2. Sơ đồ hoạt động của hệ mật mã khóa công khai 28
Hình 2.3. Sơ đồ minh họa tính mật của hệ mật mã khóa công khai 29
Hình 2.4. Sơ đồ minh họa tính xác thực của hệ mật mã khóa công khai 29
Hình 2.5. Sơ đồ minh họa tính mật và tính xác thực
của hệ mật mã khóa công khai 30
Hình 2.6. Sơ đồ minh họa hàm băm 55
Hình 2.7. Sơ đồ thực hiện tổng quát của thuật toán MD5 58
Hình 2.8. Sơ đồ xử lý một khối 512 bits thứ i 61
Hình 2.9. Sơ đồ xử lý một bước, trong 64 bước của thuật toán MD5 61
Hình 2.10. Mô tả hình tổng quát của chữ ký điện tử 66
Hình 2.11. Sơ đồ minh hoạ các bước tạo chữ ký điện tử 67
Hình 2.12. Sơ đồ minh hoạ các bước kiểm tra chữ ký điện tử 68
Hình 2.13. Mô hình chữ ký điện tử dùng quá trình mã hóa và giải mã 69
Hình 3.1. Vòng đời của đồng tiền điện tử 77
Hình 3.2. Giao thức rút tiền của lược đồ Ferguson 92
Hình 3.3. Giao thức thanh toán của lược đồ Ferguson 93

Thanh toán trong thương mại điện tử với ưu điểm đẩy mạnh quá trình lưu thông
tiền tệ và hàng hóa. Thanh toán điện tử giúp thực hiện thanh toán nhanh, an toàn,
đảm bảo quyền lợi cho các bên tham gia thanh toán, hạn chế rủi ro so với thanh toán
bằng tiền mặt, mở rộng thanh toán không dùng tiền mặt, tạo lập thói quen mới trong
dân chúng về thanh toán hiện đại.
Tiến cao hơn một bước, thanh toán điện tử tạo ra một loại tiền mới, tiền số hóa,
không chỉ thỏa mãn các tài khoản tại ngân hàng mà hoàn toàn có thể dùng để mua
hàng hóa thông thường. Quá trình giao dịch được đơn giản và nhanh chóng, chi phí
giao dịch giảm bớt đáng kể và giao dịch sẽ trở nên an toàn hơn. Tiền số hóa không

- 10 -
chiếm một không gian hữu hình nào mà có thể chuyển một nửa vòng trái đất chỉ
trong chớp mắt bằng thời gian của ánh sáng. Đây sẽ là một cơ cấu tiền tệ mới, một
mạng tài chính hiện đại gắn liền với mạng Internet. Vì vậy, vấn đề đảm bảo an toàn
trong giao dịch điện tử nhất là vấn đề thanh toán điện tử là rất quan trọng. Công
nghệ thông tin được phát triển một cách nhanh chóng thì các nguy cơ xâm nhập
thông tin dữ liệu vào các hệ thống truyền tin, các mạng dữ liệu ngày càng gia tăng.
Bảo vệ an toàn thông tin dữ liệu là một chủ đề khó đánh giá được như thế nào là tối
ưu. Vấn đề dẫn đến sự lựa chọn hoặc căn cứ vào tiêu chí tham số nào để đánh giá,
ví dụ độ bảo mật, tính hiệu quả, tính kinh tế hoặc độ phức tạp của hệ thống…Trước
những yêu cầu cấp thiết đó việc nghiên cứu ứng dụng giải pháp mật mã là cách tốt
nhất có thể đáp ứng đầy đủ những vấn đề đặt ra. Hiểu một cách sơ lược về giải pháp
này là: người gửi phải sử dụng một kỹ thuật mã hoá để xáo trộn nội dung thông tin
nhằm đảm bảo tính an toàn tại nơi lưu trữ cũng như khi truyền đi trên mạng. Nếu
thông tin bị đánh cắp hoặc bị chặn trên đường truyền, muốn hiểu được hacker phải
tốn một thời gian rất lớn (có thể mất hàng trăm năm) cho việc giải mã. Tuy nhiên
đối với người nhận hợp pháp thì công việc giải mã và xác thực thông tin lại trở nên
dễ dàng. Vì giữa người gửi và người nhận luôn có một sự thống nhất về các thuật
toán, các tham số cần thiết cho việc mã hoá giải mã và xác thực thông tin.
Trong quá trình học tập, nghiên cứu, hoạt động thực tiễn cùng với sự gợi ý của

cũng như khi chuyền đi trên mạng. Cho dù sự trao đổi này diễn ra trên môi trường
truyền thông không an toàn.
Mã hoá (Encription): Là quá trình chuyển đổi thông tin có thể chuyển đổi thông
tin từ dạng có thể hiểu được, sang dạng không hiểu được để đảm bảo tính bí mật
thông tin.
Giải mã (Decryption): là quá trình khôi phục lại thông tin ban đầu, từ dạng
thông tin đã được mã hoá.
Bản rõ (Plaintext): lưu thông tin chưa mã hoá (có thể đọc được).
Bản mã (Ciphertext): lưu thông tin đã mã hoá (không thể đọc được).
Khoá mã (Key): là dãy các ký tự và số dùng làm biến cho các quá trình mã hoá
hay giải mã thông tin.
Thám mã (Cryptanalysis): là những người phân tích các bản mã. Bộ lập mã
(Encipher)
Khoá (Key)
Bản mã
(Ciphertext)
Bản rõ
(Encipher)

tương tự, mỗi phép biến đổi giả mã D
k
được xác định bởi thuật toán giải mã D
chung và một khoá k phân biệt. Yêu cầu đặt ra cho quá trình giải mã là: E
k
(x
1
)  E
k

(x
2
) nếu x
1
 x
2
. Mặt khác nếu E
k
(x
1
) = E
k
(x
2
) mà x
1
 x
2
là


cách hệ thống phép biến đổi lập mã E
k
khi cho phép C, ngay cả khi đã biết
bản rõ M (nghĩa là, không thể mã hoá bản rõ M‟ để thay thế bản mã giả C‟
= E
k
(M‟) cho bản mã thật C).
 Đối với những người thám mã thì về mặt tính toán là không nổi để tìm một
cách hệ thống bản mã C‟ sao cho D
k
(C‟) là bản rõ hợp thức trong tập P.
1.1.4. Phƣơng pháp mã hoá dữ liệu
Có hai phương pháp mã hoá khoá, đó là phương pháp mã hoá khoá đối xứng và
phương pháp mã hoá khoá không đối xứng. Những hệ mật mã dựa trên phương
pháp mã hoá khoá đối xứng gọi là hệ mật mã khoá đối xứng (Symmetric key
Cryptography) ngược lại, các hệ mật mã dựa trên phương pháp mã hoá không đối
xứng, gọi là hệ mật mã khoá không đối xứng (Asymmetric key Cryptography), hay
hệ mật mã khoá công khai (Public key Cryptography).
1.1.4.1. Mã hoá khoá đối xứng
Trong phương pháp mã hoá khoá đối xứng [4], người gửi và người nhận sẽ dùng
chung một khoá k duy nhất cho cả hai quá trình mã hoá và giải mã dữ liệu (hình
1.2). Trước khi thực hiện việc trao đổi thông tin bí mật thông qua môi trường mạng,
hai bên gửi và nhận phải có khoá trước (bên gửi chuyển khoá bí mật cho bên nhận),
đồng thời phải thống nhất các thuật toán dùng cho quá trình mã hoá và giải. Hiện tại
có nhiều hệ mật mã được xây dựng trên phương pháp mã hóa khóa đối xứng như:
DES, 3DES-Triple, RC2-Rivest Cipher 2…


khó khăn trong việc quản lý khoá vì một người sử dụng phải giữ quá
nhiều khoá bí mật của các đối tác muốn trao đổi thông tin với họ. - 16 -
 Ứng dụng
 Mã hoá dữ liệu đường truyền (tranmission encryption): cũng do những ưu
thế về tính bảo mật, tốc độ và thực hiện đơn giản.
 Mã hoá dữ liệu lưu trữ (Data storage encryption): cũng do những ưu thế trên,
mà hệ này được dùng phổ biến trong việc mã hoá cơ sở dữ liệu, mã hoá hệ
thống file an toàn (secure file system),…
Nhận xét: Do những nhược điểm trên nên luận văn sẽ không đi sâu nghiên cứu chi
tiết mật mã dựa theo phương pháp mã hoá khoá đối xứng. Vì phương pháp mã hoá
này rất khó đáp ứng được mục tiêu của đề tài đã đặt ra.
1.1.4.2. Mã hoá khoá không đối xứng
Phương pháp mã hoá không đối xứng [1], [4], [6] đã giải quyết được những
nhược điểm của phương pháp mã hoá khoá đối xứng. Đây chính là phương pháp mã
hoá mà luận văn này sẽ đi sâu nghiên cứu chi tiết để giải quyết vấn đề đã đặt ra.
Trong phương pháp này sử dụng hai khoá có vai trò trái ngược nhau bao gồm một
khoá công khai (public key), được công bố rộng dãi dùng cho quá trình mã hoá.
Khoá riêng (private key) tương xứng còn lại được giữ bí mật của từng người, dùng
cho quá trình giải mã (hình 1.3). Tuy nhiên, hai khóa này có quan hệ toán học với
nhau, từ khoá riêng có thể tính toán để đưa ra được khoá công khai nhưng điều
ngược lại về mặt tính toán là không thể làm nổi với điều kiện chiều dài khoá đủ lớn.

ta có thể dễ thực hiện phép nhân N = p  q (độ phức tạp đa thức), nhưng khi
tính 
-1
lại là bài toán cực khó (đây chính là bài toán phân tích ra thừa số
nguyên tố có tốc độ phức tạp dạng mũ).
 
k, N
:x  x
k
mod N là hàm một chiều, với N = p  q, p và q là các số nguyên
tố lớn, k  k‟  1 (mod  (N)). Thực vậy phép tính x
k
mod N có độ phức tạp
đa thức. Nhưng khi tính 
-1
lại cực khó. Tuy nhiên nếu biết k‟ thì dễ dàng
tính được x khi biết x
k
từ công thức (x
k
)
k‟
= x.
1.2. LÝ THUYẾT SỐ
1.2.1. Các phép toán số học modul
Các phép cộng (+) và phép nhân (
*
) trong số học modulo n cũng giống các phép
cộng, phép nhân thông thường nhưng kết quả được chia cho n để lấy phần dư [1], [2].
 Phép cộng: Cho a, b  Z và n  N

2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
Ghi chú: Phép cộng trong số học modulo n cũng có phần tử nghịch đảo cộng (hay số
âm) được định nghĩa như sau: với bất kỳ số x  Z
n
  y  Z
n
: (x + y) mod n = 0
Ví dụ: (2 + 3) mod 5 = 0, (4 + 1) mod 5 = 0.

Phép nhân: Cho a, b  Z và n  N
*.

2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1

Ghi chú: Tương tự như phép cộng, phép nhân modulo n cũng có phần tử nghịch
đảo được định nghĩa như sau: cho a  Z
n
nếu  x  Z
n
sao cho: a
*
x  1 (mod n)
thì x gọi là phần tử nghịch đảo nhân của a mod n, ký hiệu x = a
-1
mod n. Ví dụ như

– 1)
 Định lý 1.1 (Định lý Euler)
Cho n là một số nguyên dương khác 0 và a là một số nguyên, a nguyên tố cùng nhau
với n. Nghĩa là gcd(a,n) = 1 thì khi đó ta có:  Định lý 1.2 (Định lý Fermat)
Cho p là một số nguyên tố và a là một số nguyên không chia hết cho p. Nghĩa là
gcd(a, c) = 1 thì khi đó ta có:  Định nghĩa 1.5: Một trường hữu hạn là một trường F chứa một số hữu hạn
các phần tử. Bậc của nhóm F là số các phần tử tồn tại trong F.
 Định nghĩa 1.6: Cho F
q
là một trường hữu hạn và một phần tử g  F
q
, định
nghĩa bậc (order) của g là số nguyên dương m nhỏ nhất sao cho: g
m
 1
(mod q), và ký hiệu là: Ord
q
(g) = m.
 Định nghĩa 1.7: Một phần tử sinh g của trường hữu hạn F
q
, nếu g có bậc
q – 1:
Phát biểu tương đương: g là phần tử sinh (chính), nếu luỹ thừa của g có thể sinh
ra tất cả các phần tử khác không của F

n
*
sao cho x
2
 a mod n. Tập tất cả các thặng dư bậc hai modul n được
ký hiệu là Q
n
.
 Định nghĩa 1.9: Cho aQ
n
. Nếu x Z
n
*
thỏa mãn x
2
 a mod n thì x được
gọi là căn bậc hai modul n.
 Định nghĩa 1.10: Cho p là số nguyên tố và a là số nguyên. Ký hiệu Jacobi
(a/p) bằng 1 nếu a là thặng dư bậc hai của p, ngược lại thì bằng -1.
 Định nghĩa 1.11: Nếu n không phải số nguyên tố thì ký hiệu Jacobi được
định nghĩa như sau:
 
 
 
n
n
a
n
aa
n

- 21 -
x
3
=Z(-1, 1)
pq

4. Số thứ tư có giá trị nằm giữa 1 và pq và có (a/p)=-1, (a/q)=-1
x
4
=Z(-1, 1)
pq

 Định nghĩa 1.14: Nhóm (G,

) gồm tập G và tóan tử

trên G thỏa mãn các
tiên đề sau đây:
(i) Tính kết hợp: a

(b

c)=(a

b)

c với mọi a, b, c  G
(ii) Có môt phần tử 1G được gọi là phần tử đơn vị sao cho:
a


2. u
0
= 1; u
1
= 0;
3. v
0
= 0; v
1
= 1;
4. While (g
1
<> 0)
5. q = qout(g
0,
g
1
)
temp = g
0 –
g
1*
q;
g
0
= g
1
;
g
1

6. x= v
0
;
7. if(x>=0) Return x
8. else Return (x + n);
1.3.2. Thuật toán kiểm tra tính nguyên tố
Các thuật toán kiểm tra tính nguyên tố của một số nguyên bằng xác suất Monte
Carlo [2], [4] như thuật toán Miller-Rabin, Soloway-Strassen, đều có tốc độ thực
hiện khá nhanh (khoảng 0(n
2
), với n là số bits của số cần kiểm tra). Tuy nhiên,
những thuật toán này không đưa ra một kết luận chính xác về tính nguyên tố của
con số, mà luôn có một xác suất sai sót. Như vậy để có một sai số cực nhỏ chấp
nhận được, ta phải thực hiện thuật toán kiểm tra nhiều lần. Một câu hỏi khác đặt ra
là với khoảng bao nhiêu số nguyên dương ngẫu nhiên (có chiều dài xác định) thì có
thể tìm ra được một số nguyên tố? Lý thuyết số nguyên tố đã chứng minh được số
các số nguyên tố nhỏ hơn N là: N/ln(N). Như vậy, nếu p là một số nguyên ngẫu
nhiên thì xác suất để p trở thành số nguyên tố là: 1/ln(p). Giả sử nếu chọn p là số
nguyên tố có chiều dài 512-bits, thì xác suất để số p nguyên tố là 1/354. Mặt khác,
do chúng ta chỉ quan tâm đến những số lẻ, nên xác suất để p nguyên tố là 2/354 =
1/177. Nghĩa là, trung bình khoảng 177 số lẻ ngẫu nhiên sẽ có 1 số nguyên tố.
Người ta đã cũng chứng minh được, thuật toán Miller-Rabin dùng kiểm tra tính
nguyên tố của một số nguyên dương lẻ với sai số nhiều nhất là

1/4. Do đó, nếu thực
hiện thuật toán này t lần thì sai số nhiều nhất là 1/4
t
, trong thực hành nên chọn số t >
20 để đảm bảo chắc chắn tính nguyên tố cho kiểm tra. Thuật toán này được sử dụng
trong quá trình tạo khoá ở hệ mật mã RSA và hệ mật mã ELGamal mà luận văn này

1. Đặt n = 2
k
m + 1; (sử dụng thuật toán 2km ở trên).
2. For (j = 1; j ≤ t; j++)
Chọn số ngẫu nhiên a  2,…, n - 1
Tính b = a
m
mod n;
If (b = 1) continue; /* quay lại bước 2*/
i = 1;
While ((i < k) and (b  n – 1))
 b = b
2
mod n;
If (b =1) Return False; /* n là hợp số */

- 24 -
i = i + 1;

If (b <> (n – 1)) Return False; /* n là hợp số*/

3. Return True; /* n là số nguyên tố */
1.3.3. Thuật toán luỹ thừa nhanh
Thuật toán luỹ thừa nhanh modulo N (y = x
e
mod N) [5] được sử dụng rất nhiều
trong các thế hệ mật mã khoá công khai. Tốc độ thực hiện của các quá trình mã hoá
và giải mã của hệ mật mã phụ thuộc rất nhiều vào phép tính này với toán hạng là
những số nguyên cực lớn. Vì vậy đòi hỏi cần phải có một thuật toán thực hiện phép
tính luỹ thừa modulo càng nhanh càng tốt. Trong phần này sẽ trình bầy chi tiết về

=



1
0
2*
k
i
i
i
e
M
=



1
0
k
i
i
i
e
M
2*
mod N.
Đầu tiên gán biến C = 1, sau đó duyệt từng giá trị bít, thông qua biểu diễn nhị
phân của số mũ, bắt đầu từ phía bên trái sang phía bên phải. Tại mỗi vòng lặp thứ I,
thực hiện một phép tính bình phương của kết quả hiện tại (C


- 25 -
3. For (i = k – 1; I  0; i )
{ C = C
*
C mod N;
if (e
i
= 1) C = C
*
M mod N;
}
4. Return (C);
Ví dụ 1.4: Tính 125
54
mod 1024 (M = 125, e = 54, n = 1024)
Biểu diễn nhị phân (54)
10
= (110110)
2
. Chỉ thực hiện 6 bước tính sau:
B1: e
5
= 1  C = (1
*
1)
*
125 = 125
B2: e
4

Mỗi lần lặp thuật toán đều thực hiện một phép tính bình phương (C = C
*
C mod
N), ngoại trừ bước đầu tiên khi C = 1 và một phép nhân (C = C
*
M mod N) với xác
suất xảy ra khoảng
1
/
2
. Như vậy với k lần lặp (k là số bits biểu diễn nhị phân của số
mũ e)  Thuật toán thực hiện tất cả khoảng (3k/2 – 1) phép nhân modulo N, mà chi
phí thời gian để thực hiện một phép nhân modulo N (có chiều dài n-bits) là: 2n
2

+
2n. Như vậy chi phí tổng cộng của thuật toán là (3k – 2)
*
(n
2
+ n), nếu số mũ e có
kích cỡ gần bằng với số N (k  n, số bít của số mũ xấp xỉ với số bít của số n). Thì
chi phí thời gian tổng cộng của thuật toán là :3n
3
+ n
2
+ 0(n
2
).