Bài giảng Mật mã học - Chương 3: Mã hoá khoá công khai và quản lý khoá

 khoá bí 
mật của người đó.
15
2. Hệ mã hoá khoá công khai
Encryption
16
2. Hệ mã hoá khoá công khai
Y = E(PUb, X)
X = D(PRb, Y)
Secrecy
17
2. Hệ mã hoá khoá công khai
 Ứng dụng:
– Các thuật toán tạo chữ ký số khoá công 
khai có thể dùng để chứng thực: Một 
người sử dụng có thể mã hoá văn bản 
với khoá bí mật của mình. Nếu một 
người khác có thể giải mã với khoá 
công khai của người gửi thì có thể tin 
rằng văn bản thực sự xuất phát từ người 
gắn với khoá công khai đó.
18
2. Hệ mã hoá khoá công khai
Authentication
19
2. Hệ mã hoá khoá công khai
Authentication
20
2. Hệ mã hoá khoá công khai
 Ứng dụng:
– Trao đổi khoá: Hai bên hợp tác để trao đổi session 
key. Có một số phương pháp tiếp cận khác nhau liên 
quan đến các khóa bí mật của một hoặc cả hai bên. 
Trước tiên, mã hoá thông điệp X sử dụng khoá 
secret của người gởi (cung cấp chữ ký số) để được 
Y.
Kế đó, mã hoá tiếp Y với khoá public của người 
nhận.
Chỉ có người nhận đã xác định trước mới có khoá 
secret của người nhận và khoá public của người 
gởi để giải mã hai lần để được X.
21
2. Hệ mã hoá khoá công khai
Authentication và Secrecy
Z = E(PUb, E(PRa, X))
X = D(PUa, D(PRb, Z))
22
2. Hệ mã hoá khoá công khai
 Một số giải thuật hệ mã hoá khoá công khai
Algorithm Encryption/
Decryption
Digital
Signature
Key
Exchange
RSA x x x
Elliptic Curve x x x
Diffie-Hellman x
DSS x
23
2. Hệ mã hoá khoá công khai
 Định nghĩa:
Cho các tập hữu hạn S và T.
Hàm một chiều f: S T là hàm khả nghịch thoả:
 f dễ thực hiện; cho x  S, dễ dàng tính được y = 
f(x).
 f-1 là hàm ngược của f, khó thực hiện; cho y  T, 
rất khó tính được x = f-1(y).
 f-1 chỉ có thể tính được khi biết thêm một số 
thông tin cần thiết.
24
2. Hệ mã hoá khoá công khai
 Ví dụ:
f: pq  n là hàm một chiều với p và q là 
các số nguyên tố lớn.
 Có thể dễ dàng thực hiện phép nhân pq 
(độ phức tạp đa thức).
 Tính f-1 (phân tích ra thừa số nguyên tố -
độ phức tạp mũ) là bài toán cực kỳ khó.
25
3. Giao thức trao đổi khoá Diffie-Hellman
Mục đích của thuật toán là cho phép hai 
người dùng trao đổi khóa bí mật dùng 
chung trên mạng công cộng, sau đó có thể 
sử dụng để mã hóa các thông điệp. 
Thuật toán tập trung vào giới hạn việc trao 
đổi các giá trị bí mật, xây dựng dựa trên 
bài toán khó logarit rời rạc.
26
Giao thức trao đổi khoá Diffie-Hellman
27
3. Giao thức trao đổi khoá Diffie-Hellman
28
3. Giao thức trao đổi khoá Diffie-Hellman
29
Giao thức trao đổi khoá Diffie-Hellman
Ví dụ: 
– A và B chọn số nguyên tố chung là p=353 và 
phần tử sinh g là 3.
– A chọn a=97 rồi gởi cho B giá trị kết quả của 
397 mod 353 = 40.
– B chọn b=233 rồi gởi cho A giá trị kết quả của 
3233 mod 353 = 248.
– Cả A và B đều tính được K = 24897 mod 353 
= 160 = 40233 mod 353.
30
4. Hệ RSA
Giải thuật được phát triển bởi Rivest, Shamir và 
Adleman, sử dụng một biểu thức với hàm mũ. 
Văn bản rõ được mã hóa ở dạng khối, kích cỡ 
của khối phải nhỏ hơn hoặc bằng log2(n).
Trong thực tế, kích thước khối là i bit, với 2i
<n<= 2i +1. 
Mã hóa và giải mã được thực hiện với một số 
khối rõ M (plaintext) và khối mã C (cyphertext): 
C = Me mod n
M = Cd mod n = (Me)d mod n = Med mod n
31
4. Hệ RSA
Giải thuật: 
– Mã hoá:
Từ khoá công khai (n, e) và thông điệp là 
plaintext dưới dạng số nguyên M  [0, n).
Tính cyphertext C = Me mod n
– Giải mã:
M = Cd mod n, với d là khoá bí mật.
32
4. Hệ RSA
Cả người gửi và người nhận phải biết giá trị của n. Người gửi 
biết giá trị của e, và chỉ người nhận mới biết giá trị của d. 
Như vậy, đây là một thuật toán mã hoá khoá công khai với 
một khóa công khai PU={n, e} và một khoá riêng PR={d, n}. 
Các yêu cầu sau đây phải được đáp ứng:
– Phải có khả năng tìm được giá trị của e, d, n sao cho Med
mod n = M, với M < n.
– Phải dễ dàng tính toán được mod Me mod n và Cd cho tất 
cả các giá trị của M < n.
– Không khả thi để xác định d khi cho e và n.
– Để an toàn, RSA đòi hỏi p và q phải là các số nguyên tố 
rất lớn để không thể phân tích được n=pq.
33
4. Hệ RSA
34
4. Hệ RSA
35
4. Hệ RSA
Ví dụ:
36
4. Hệ RSA
Tính 887 mod 187
– 887 mod 187 = [(884 mod 187) x (882 mod 187) 
x (881 mod 187)] mod 187
– 881 mod 187 = 88
– 882 mod 187 = 7744 mod 187 = 77
– 884 mod 187 = 59,969,536 mod 187 = 132
– 887 mod 187 = (88 x 77 x 132) mod 187 = 
894,432 mod 187 = 11
37
4. Hệ RSA
Tính 1123 mod 187
– 1123 mod 187 = [(111 mod 187) x (112 mod 187) x 
(114 mod 187) x (118 mod 187) x (118 mod 187)] 
mod 187
– 111 mod 187 = 11
– 112 mod 187 = 121
– 114 mod 187 = 14,641 mod 187 = 55
– 118 mod 187 = 214,358,881 mod 187 = 33
– 1123 mod 187 = (11 x 121 x 55 x 33 x 33) mod 187 
= 79,720,245 mod 187 = 88
38
4. Hệ RSA
Ví dụ:
Cho các số nguyên tố p=2357 và q=2551.
Tính được: 
n = pq = 6012707
(n) = (p-1)(q-1) = 6007800
Chọn số nguyên e  (1, (n)) là 3674911
d  e-1 mod (n) = 422191
(d được tính bằng cách dùng thuật toán Euclide mở rộng, tìm
số tự nhiên x sao cho d=(x*(n)+1)/e cũng là số tự nhiên).
Khoá công khai: (n, e) = (6012707, 3674911)
Khoá bí mật: d = 422191
39
4. Hệ RSA
Ví dụ:
Để mã hoá bản rõ 
M = 5234673  [0, 6012707)
tính C = Me mod n = 3650502
Để giải mã
tính Cd mod n = 5234673
40
4. Hệ RSA
Ví dụ:
– p = 61 — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa) 
– q = 53 — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa) 
– n = pq = 3233 — môđun (công bố công khai) 
– e = 17 — số mũ công khai 
– d = 2753 — số mũ bí mật 
– Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là:
encrypt(m) = me mod n = m17 mod 3233 với m là văn bản rõ. Hàm giải mã là:
decrypt(c) = cd mod n = c2753 mod 3233 với c là văn bản mã.
– Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính:
encrypt(123) = 12317 mod 3233 = 855 
– Để giải mã văn bản có giá trị 855, ta thực hiện phép tính:
decrypt(855) = 8552753 mod 3233 = 123 
– Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình 
phương và nhân.
41
5. Quản lý khoá
1. Thẩm quyền thu hồi khoá
– Thu hồi khoá khi khoá bị sai sót hoặc có tính phá 
hoại.
– Thường được tham gia bởi từ hai thực thể trở lên. 
Ví dụ: cả Alice và Bob cùng thoả thuận thu hồi 
khoá.
– Cần đảm bảo:
Càng nhiều bên tham gia càng tốt (chống phá 
hoại).
Càng ít bên tham gia càng tốt (thu hồi nhanh).
42
5. Quản lý khoá
2. Phân phối khoá mới
– Phải phân phối khoá mới sau khi khoá cũ bị thu 
hồi nhằm đảm bảo hệ thống tiếp tục hoạt động 
một cách an toàn.
– Cần giảm thời gian giữa thời điểm thu hồi khoá 
và thời điểm phân phối khoá mới tới mức tối 
thiểu.
– Phải đảm bảo yêu cầu về an ninh và yêu cầu về 
tính sẵn sàng của hệ thống.
43
5. Quản lý khoá
3. Thông báo thông tin về thu hồi khoá
– Thông báo về một khóa nào đó bị thu hồi cần 
đến được tất cả những người đang sử dụng nó 
trong thời gian ngắn nhất có thể. 
– Hai cách:
Thông tin được chuyển từ trung tâm tới 
người dùng.
Người dùng lấy thông tin từ trung tâm.
– Cung cấp các chứng thực có thời hạn.
44
5. Quản lý khoá
4. Các biện pháp thực hiện khi lộ khoá
– Hầu hết các trường hợp thu hồi khoá xảy ra khi 
khoá bí mật đã bị lộ. Hai khả năng xảy ra:
Các văn bản mã hóa với khóa công khai sau 
thời điểm T không còn được xem là bí mật.
các chữ ký số thực hiện với khóa bí mật sau 
thời điểm T không còn được xem là thật.
– Cần xác định người có quyền thu hồi khóa, 
cách thức truyền thông tin tới người dùng, cách 
thức xử lý các văn bản mã hóa với khóa bị lộ. 
45
6. Bài tập
1. Viết chương trình nhập vào một số nguyên 
dương n, xuất ra:
– n có phải là số nguyên tố hay không?
– Dãy số nguyên tố nhỏ hơn hoặc bằng n.
– n số nguyên tố đầu tiên.
2. Cho p là một số nguyên tố và n < p là một số 
nguyên dương. Chứng minh rằng a2 mod p = 1 
nếu và chỉ nếu a mod p = 1 hoặc a mod p = -1.
46
6. Bài tập
3. Hacker có thể lợi dụng điểm yếu trong 
giao thức trao đổi khoá Diffie-Hellman 
để thực hiện một cuộc tấn công Man-in-
the-Middle.
 Mô tả cuộc tấn công này. 
 Vẽ hình minh hoạ.
47
6. Bài tập
4. Nếu cho số nguyên tố p = 353 thì a = 3 là 
một primitive root modulo p. Sử dụng hai 
số này để xây dựng một hệ thống trao đổi 
khoá Diffiel-Hellman. 
a. Nếu Alice chọn một private key XA = 97, 
giá trị public key YA của Alice là?
b. Nếu Bob chọn một private key XB = 233, 
giá trị public key YB của Bob là?
c. Giá trị của khoá bí mật thống nhất giữa 
cả Alice và Bob là bao nhiêu?
48
6. Bài tập
5. Cho p = 13.
a. Chứng minh rằng a = 2 là một primitive 
root modulo p. Sử dụng hai tham số này 
để xây dựng một hệ thống trao đổi khoá 
Diffie-Hellman.
b. Nếu public key của Alice là YA = 7, giá 
trị private key XA của cô ấy là bao 
nhiêu?
c. Nếu public key của Bob là YB = 11, giá 
trị private key XB của anh ấy?
49
6. Bài tập
6. Cho n = 187 = 11 x 17.
a. Cho e = 7, M = 89. Tính giá trị RSA 
ciphertext C.
b. Từ C tính được ở (a), tính toán plaintext 
M.
c. Cho e = 7, M = 88. Tính toán giá trị RSA 
ciphertext C. C có thể sử dụng n = 187? 
Giải thích.
50
6. Bài tập
7. Alice sử dụng phương pháp dưới đây để 
mã hoá văn bản rõ (plaintext messages) 
tiếng Anh với toàn các ký tự viết hoa: 
 Ánh xạ mỗi ký tự viết hoa đến các số từ 
100 đến 125; cụ thể là, ánh xạ A thành 
100, B thành 101, ..., và Z thành 125. 
 Sau đó cô ấy mã hoá các số nguyên này 
sử dụng các giá trị lớn của n và e. 
 Phương pháp này có an toàn? Giải thích.
51
6. Bài tập
8. Giả sử rằng Alice mã hoá một thông 
điệp M sử dụng RSA với public key n = 
437, e = 3, ciphertext C = 75. 
Nếu ai đó nói với Malice rằng M  {8,9}, 
thì Malice có thể xác định giá trị đúng 
của M mà không cần n. 
Malice thực hiện điều này như thế nào?
52
6. Bài tập
9. Viết một ứng dụng client-server sử 
dụng socket API để thực hiện giao 
thức trao đổi khoá Diffie-Hellman.
10. Viết một ứng dụng client-server sử 
dụng để thực hiện mã hoá và giải 
mã RSA, với các tham số của RSA 
được cho trước.
----------------