TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Họ và tên:...................................................... MSSV:..................
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSSV: . . . . . . . . . . . . . . . . . . . . Số thứ tự
Học phần: Mật mã Ứng dụng Mã HP: IT4025
Bài thi [ ] giữa kỳ [X] cuối kỳ . . . . . . . . . . .
Ngày thi: . . . . . . . . . . . . . . . Điểm của bài thi
Chữ ký của (các) cán bộ chấm thi
Chữ ký của cán bộ coi thi Tờ .../ ...
Đề thi môn Mật mã Ứng dụng Thời gian: 90 phút. Không sử dụng tài liệu
Bài 1 (1 điểm). Xét E = (E ,D ) là một hệ mã an toàn ngữ nghĩa trên (K ,M ,C ), với M =
{0, 1}L . Hệ mã nào dưới đây cũng là an toàn ngữ nghĩa? Nếu an toàn hãy đưa ra một chứng
minh, ngược lại hãy chỉ ra một cách tấn công. (a) E ( (
1 k , m ) := 0 E (k , m )
(b) E2 k ,m) := E (k ,m) parity(m)
Ở đây, cho xâu bit s , parity(s ) bằng 1 nếu số lượng 1 trong s là lẻ, và bằng 0 trong trường hợp ngược lại. 1 2
Bài 2 (1 điểm). Ta muốn xây dựng một hệ mã khối E = (E ,D ) từ hai hệ mã khối E = ( ) 1 E1, D1 và E = ( ) 2
E2, D2 sao cho nếu ở một thời điểm nào đó trong tương lai một trong hai (nhưng
không phải cả hai) hệ E1 hoặc E2 bị phá thì hệ E vẫn an toàn. Giả sử cả E1 và E2 được định
nghĩa trên (K ,X ). Ta định nghĩa E như sau: E ( (k ) ( ( ) ( (
1, k2 , x ) := E1 k1, E2 k2, x )) và
D ( (k1, k2 , y ) := D2 k2, D1 k1, y )).
Chứng minh rằng E an toàn nếu E1 hoặc E2 an toàn.
Bài 3 (1 điểm). Xét F là một PRF định nghĩa trên (K ,R,X ) với X = {0,1}32. Xét CRC32 là
một mã sửa sai quen thuộc và đơn giản chỉ để phát hiện lỗi ngẫu nhiên; CRC32(m) nhận
input là các xâu nhị phân độ dài ≤ ` và luôn output ra một xâu nhị phân 32 bit. Với bài tập
này, bạn chỉ cần biết rằng CRC32(m ) ) = ) 1 ⊕ CRC32(m2
CRC32(m1 ⊕ m2 . Ta định nghĩa MAC
(S,V ) sau đây: R
S (k , m) := {r ← R, t ← F (k , r ) ⊕ CRC32(m), output(r, t ) } yes
nếu t = F (k , r ) ⊕ CRC32(m)
V (k , m) := no ngược lại.
Hãy chứng minh rằng hệ MAC này không an toàn. 3
Bài 4 (2 điểm). Giả sử H và H 0 là các hàm băm kháng xung đột 1. Hàm băm H 00 trong mỗi
câu dưới đây có kháng xung đột hay không? Hãy giải thích.
(a) H 00(x ) = H (x ) 0...0
(c) H 00(x ) = H (x ) H 0(x )
(b) H 00(x ) = H (H 0(x ))
(d) H 00(x ) = H (x ) ⊕ H 0(x ). 1collision-resistant 4
Bài 5 (2 điểm). Giả sử (E ,D ) là một hệ mã có xác thực2, với không gian khóa K , không gian
bản rõ {0,1}n và không gian bản mã {0,1}s . Hệ mã trong mỗi câu dưới đây có xác thực hay không? Hãy giải thích. D (k (a) E 0 (k ) )
1, D (k2, c ))
nếu D (k2, c ) 6= ⊥
1, k2 , m = E (k2, E (k1, m )) và
D 0 (k1, k2 , c = ⊥ nếu ngược lại
D (k, c ) if c = c
(b) E 0(k ,m) = c ← E (k ,m), output (c , c ) và
D 0(k , (c ) ) = 1 1 2 1, c2 ⊥ nếu ngược lại
(c) E 0(k ,m) = E (k ,m), 0 và
D 0(k , (c , b ) ) = D (k , c ) 2authenticated encryption 5
Bài 6 (1 điểm). Xét F : {0,1}n × {0,1}n → {0,1}n là một PRP an toàn. Ta xây dựng sơ đồ mã
hóa E (k ,m) từ F như sau:
• Thông điệp m được chia thành các khối n bit m = m1 m2 · · · mt .
• Chọn ngẫu nhiên một số n-bit r .
• Output r F (k , r + 1 + m ) ) )
1 F (k , r + 2 + m2 · · · F (k , r + t + mt .
Phương pháp nào sau đây Attacker có thể sử dụng để chỉ ra rằng sơ đồ mã trên không là
CPA an toàn? Hãy giải thích. (a) Lấy một
n -bit block m bất kỳ; và gửi M = = 0
m m và M1
m m − 1. Nhận được bản mã r c =
1 c2. Quyết định output 1 nếu và chỉ nếu c1 c2. (b) Chọn ngẫu nhiên hai
n -bit block m và m0; và gửi M = = 0
m m và M1 m m 0. Nhận được bản mã r c =
1 c2. Quyết định output 1 nếu và chỉ nếu c1 c2. (c) Lấy một
n -bit block m bất kỳ; và gửi output M = = 0 m và M1
m m . Quyết định
output 0 nếu và chỉ nếu bản mã nhận được chứa 2 blocks. (d) Chọn ngẫu nhiên bốn n -bit blocks m = =
1, m2, m3, m4; và gửi M0
m1 m2 và M1
m3 m4. Nhận được bản mã r c1 c2. Quyết định output 0 nếu và chỉ nếu r = 0 . . . 0. 6
Bài 7 (1 điểm). Giả sử có n + 1 bên, gọi là B, A1,..., An, muốn có một khóa chung cho cả
nhóm. Họ muốn có một giao thức sao cho mọi người đều có chung một khóa bí mật,
nhưng kẻ nghe lén dù thấy được toàn bộ quá trình trao đổi vẫn không xác định được k .
Các bên thống nhất một nhóm G có cấp nguyên tố q với phần tử sinh g và dùng giao thức sau đây :
• Mỗi Ai chọn một số ngẫu nhiên ai thuộc {1, . . . , q } và gửi cho B giá trị Xi ← g ai .
• Bên B sinh một số ngẫu nhiên b thuộc {1, . . . , q } và gửi trả lại Ai thông điệp Yi ← X b . i
Khóa cuối cùng của nhóm là g b . Rõ ràng B có thể tính được khóa này. Các Ai tính khóa này
như thế nào ? Hãy giải thích ngắn gọn.
Bài 8 (1 điểm). Nhắc lại rằng hoán vị cửa sập RSA được định nghĩa trong nhóm ∗ Z với N N
là tích của hai số nguyên tố lớn. Khóa công khai là (N , e ) và khóa bí mật là (N ,d ) với d là
nghịch đảo của e trong ∗ Zϕ(N ).
Giả sử trong thuật toán RSA, thay vì lấy N là hợp số bạn lại chọn N = p là số nguyên tố. Hãy
chỉ ra rằng trong trường hợp này mọi người đều có thể tính hoặc không tính được khóa bí
mật (N ,d ) từ khóa công khai (N , e ) bằng mỗi cách tính dưới đây. Hãy giải thích ngắn gọn.
(a) d ← −e (mod p ).
(c) d ← e −1 (mod p ).
(b) d ← e 2 (mod p ).
(d) d ← e −1 (mod p − 1).
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
Họ và tên:...................................................... MSSV:..................
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Họ tên SV: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
MSSV: . . . . . . . . . . . . . . . . . . . . Số thứ tự
Học phần: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Mã HP: . . . . . . . . . . . . . . . . . . .
Bài thi [ ] giữa kỳ [ ] cuối kỳ . . . . . . . . . . .
Ngày thi: . . . . . . . . . . . . . . . . Điểm của bài thi
Chữ ký của (các) cán bộ chấm thi
Chữ ký của cán bộ coi thi Tờ .../ ...
Đề thi môn Mật mã ứng dụng Thời gian: 60 phút
Bài 1 (1 điểm). An chuyển tiền cho Bình qua một hệ thống ngân hàng. Số tiền được biểu
diễn bằng một số nguyên 8-bit. An mã hóa số tiền dùng CTR-mode dựa trên một block
cipher với kích thước block là 8-bit! Bình biết số tiền An chuyển cho mình chỉ là $16 và
ngay lập tức lấy được bản mã trước khi An gửi tới ngân hàng. Giả sử bản mã là 10111100 01100001
1. Bình nên sửa bản mã như thế nào để sau khi giải mã nhận được đúng $32?
2. An nên dùng phương pháp mã hóa nào để tránh được cách tấn công này của Bình? 1 2
Bài 2 (1 điểm). Giả sử có n + 1 bên, gọi là B, A1,..., An, muốn có một khóa chung cho cả
nhóm. Họ muốn có một giao thức sao cho mọi người đều có chung một khóa bí mật,
nhưng kẻ nghe lén dù thấy được toàn bộ quá trình trao đổi vẫn không xác định được k .
Các bên thống nhất một nhóm G có cấp nguyên tố q với phần tử sinh g và dùng giao thức sau đây :
• Mỗi bên Ai chọn một số ngẫu nhiên ai thuộc {1, . . . , q } và gửi cho Bên B giá trị Xi ← g ai .
• Bên B sinh một số ngẫu nhiên b thuộc {1, . . . , q } và trả lại bên Ai thông điệp Yi ← X b . i
Khóa cuối cùng của nhóm là g b . Rõ ràng Bên B có thể tính được khóa này. Các bên Ai tính
khóa này như thế nào ? Hãy giải thích ngắn gọn.
1. Bên Ai tính g b bằng Y ai i
2. Bên Ai tính g b bằng Y −1/ai i
3. Bên Ai tính g b bằng Y 1/ai i
4. Bên Ai tính g b bằng Y −ai i 3
Bài 3 (1 điểm). Nhắc lại rằng hoán vị cửa sập RSA được định nghĩa trong nhóm ∗ Z với N N
là tích của hai số nguyên tố lớn. Khóa công khai là (N , e ) và khóa bí mật là (N ,d ) trong đó
d là nghịch đảo của e trong ∗ Zϕ(N ).
Giả sử trong thuật toán RSA, thay vì dùng hợp số N bạn lại dùng số nguyên tố p . Hãy chỉ
ra rằng trong trường hợp này mọi người đều có thể tính hoặc không tính được khóa bí mật
(N ,d ) từ khóa công khai (N ,e ) bằng cách tính dưới đây. Hãy giải thích ngắn gọn.
1. d ← −e (mod p ).
2. d ← e 2 (mod p ).
3. d ← e −1 (mod p ).
4. d ← e −1 (mod p − 1). 4
Bài 4 (1 điểm). Trong các bài toán dưới đây, ta giả sử N là tích của hai số nguyên tố lớn p
và q , và e nguyên tố cùng nhau với φ(N ). Nếu bài toán RSA là khó, vậy những bài toán nào
dưới đây cũng khó? Hãy giải thích.
1. Cho trước N , e , và lấy ngẫu nhiên y ∈ ∗
Z , tìm x sao cho x e = y mod N . N
2. Cho trước N và e , tìm x , y sao cho x e = y mod N .
3. Cho trước N và e , tìm x sao cho x e = 8 mod N .
4. Cho trước N , e , và lấy ngẫu nhiên x ∈ ∗
Z , tìm y sao cho x e = y mod N N 5
Bài 5 (2 điểm). Giả sử H và H ′ là các hàm băm kháng xung đột1. Hàm băm H ′′ trong mỗi
câu dưới đây có kháng xung đột hay không? Hãy giải thích.
1. H ′′(x ) = H (x ) 0...0
2. H ′′(x ) = H (H ′(x ))
3. H ′′(x ) = H (x ) H ′(x )
4. H ′′(x ) = H (x ) ⊕ H ′(x ). 1collision-resistant 6
Bài 6 (2 điểm). Giả sử (E ,D ) là một hệ mã có xác thực2, với không gian khóa K , không gian
bản rõ {0,1}n và không gian bản mã {0,1}s . Hệ mã trong mỗi câu dưới đây có xác thực hay không? Hãy giải thích. D (k
1. E ′ (k ) )
1, D (k2, c ))
nếu D (k2, c ) ̸= ⊥
1, k2 , m = E (k2, E (k1, m )) và
D ′ (k1, k2 , c = ⊥ nếu ngược lại
D (k, c ) if c = c
2. E ′(k ,m) = c ← E (k ,m), output (c , c ) và
D ′(k , (c ) ) = 1 1 2 1, c2 ⊥ nếu ngược lại
3. E ′(k ,m) = E (k ,m), 0 và
D ′(k , (c , b ) ) = D (k , c ) 2authenticated encryption 7
Bài 7 (1 điểm). Giả sử hàm F : {0,1}n × {0,1}n → {0,1}n là một PRF an toàn. Vậy trong các
PRF dưới đây, những PRF nào là an toàn? Nếu an toàn hãy chứng minh; nếu không hãy chỉ
ra một cách tấn công hiệu quả.
1. F ′((k )
1, k2 , x ) = F (k1, x )
F (k2, x ).
F (k, x ) nếu x ̸= 0n
2. F ′(k , x ) = k ngược lại
3. F ′(k , x ) = F (k , x )[0,...,n − 2] (có nghĩa rằng, F ′(k , x ) đạt từ F (k , x ) bằng cách bỏ đi bit cuối) 8
Bài 8 (1 điểm). Xét F : {0,1}n × {0,1}n → {0,1}n là một PRP an toàn. Ta xây dựng sơ đồ mã
hóa E (k ,m) từ F như sau:
• Thông điệp m được chia thành các khối n bit m = m1 m2 · · · mt
• Chọn ngẫu nhiên một số n-bit r .
• Output r F (k , r + 1 + m ) ) )
1 F (k , r + 2 + m2 · · · F (k , r + t + mt
Phương pháp nào sau đây Attacker có thể sử dụng để chỉ ra rằng sơ đồ mã trên không là
CPA an toàn? Hãy giải thích. 1. Lấy một
n -bit block m bất kỳ; và gửi M = = 0
m m và M1
m m − 1. Nhận được bản mã r c =
1 c2. Quyết định output 1 nếu và chỉ nếu c1 c2.
2. Chọn ngẫu nhiên hai
n -bit block m và m′; và gửi M = = 0
m m và M1 m m ′. Nhận được bản mã r c =
1 c2. Quyết định output 1 nếu và chỉ nếu c1 c2. 3. Lấy một
n -bit block m bất kỳ; và gửi output M = = 0 m và M1
m m . Quyết định output 0
nếu và chỉ nếu bản mã nhận được chứa 2 blocks.
4. Chọn ngẫu nhiên bốn n -bit blocks m = =
1, m2, m3, m4; và gửi M0
m1 m2 và M1 m3 m4. Nhận được bản mã
r c1 c2. Quyết định output 0 nếu và chỉ nếu r = 0 . . . 0.