Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai

Trong mô hình mật mã cổ điển Alice (ngƣời gửi) và Bob (ngƣời nhận) chọn

một cách bí mật khoá K. Sau đó dùng K để tạo luật mã hoá ekvà luật giải mã dk. Trong

hệ mật này dk hoặc giống nhƣ ek hoặc dễ dàng tính đƣợc từ ek. Các hệ mật thuộc loại

này đƣợc gọi là hệ mật khoá bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn.

Nhƣợc điểm của hệ mật này là nó yêu cầu phải có thông tin về khoá K giữa

Alice và Bob qua một kênh an toàn trƣớc khi gửi một bản mã bất kỳ. Trên thực tế điều

này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên

lạc với nhau bằng thƣ tín điện tử (Email). Trong tình huống đó Alice và Bob không thể

tạo một kênh bảo mật với giá phải chăng.

Ý tƣởng xây dựng một hệ mật khoá công khai (hay khoá dùng chung) là tìm

một hệ mật không có khả năng tính toán để xác định dk khi biết ek. Nếu thực hiện đƣợc

nhƣ vậy thì quy tắc mã ek có thể đƣợc công khai bằng cách công bố nó trong một danh

bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ƣu điểm của hệ mật khoá công

khai là ở chỗ Alice (hoặc bất kì một ai) có thể gửi một bản tin đã mã cho Bob (mà

không cần thông tin trƣớc về khoá mật) bằng cách dùng luật mã công khai ek. Ngƣời

nhận sẽ là ngƣời duy nhất có thể giải đƣợc bản mã này bằng cách sử dụng luật giải mã

bí mật dk của mình.

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 1

Trang 1

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 2

Trang 2

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 3

Trang 3

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 4

Trang 4

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 5

Trang 5

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 6

Trang 6

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 7

Trang 7

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 8

Trang 8

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 9

Trang 9

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai trang 10

Trang 10

Tải về để xem bản đầy đủ

pdf 92 trang minhkhanh 6400
Bạn đang xem 10 trang mẫu của tài liệu "Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

Tóm tắt nội dung tài liệu: Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai

Giáo trình Bảo mật thông tin - Chương 4: Các hệ mật mã khoá công khai
Giáo trình Bảo mật thông tin 
89 
CHƢƠNG 4: CÁC HỆ MẬT MÃ KHOÁ CÔNG KHAI 
4.1. Giới thiệu về mật mã khoá công khai 
Trong mô hình mật mã cổ điển Alice (ngƣời gửi) và Bob (ngƣời nhận) chọn 
một cách bí mật khoá K. Sau đó dùng K để tạo luật mã hoá ekvà luật giải mã dk. Trong 
hệ mật này dk hoặc giống nhƣ ek hoặc dễ dàng tính đƣợc từ ek. Các hệ mật thuộc loại 
này đƣợc gọi là hệ mật khoá bí mật, nếu để lộ ek thì làm cho hệ thống mất an toàn. 
Nhƣợc điểm của hệ mật này là nó yêu cầu phải có thông tin về khoá K giữa 
Alice và Bob qua một kênh an toàn trƣớc khi gửi một bản mã bất kỳ. Trên thực tế điều 
này rất khó đảm bảo. Chẳng hạn khi Alice và Bob ở cách xa nhau và họ chỉ có thể liên 
lạc với nhau bằng thƣ tín điện tử (Email). Trong tình huống đó Alice và Bob không thể 
tạo một kênh bảo mật với giá phải chăng. 
Ý tƣởng xây dựng một hệ mật khoá công khai (hay khoá dùng chung) là tìm 
một hệ mật không có khả năng tính toán để xác định dk khi biết ek. Nếu thực hiện đƣợc 
nhƣ vậy thì quy tắc mã ek có thể đƣợc công khai bằng cách công bố nó trong một danh 
bạ (bởi vậy nên có thuật ngữ hệ mật khoá công khai). Ƣu điểm của hệ mật khoá công 
khai là ở chỗ Alice (hoặc bất kì một ai) có thể gửi một bản tin đã mã cho Bob (mà 
không cần thông tin trƣớc về khoá mật) bằng cách dùng luật mã công khai ek. Ngƣời 
nhận sẽ là ngƣời duy nhất có thể giải đƣợc bản mã này bằng cách sử dụng luật giải mã 
bí mật dk của mình. 
Có thể hình dung hệ mật này tƣơng tự nhƣ sau: Bob tạo hai khóa lập mã Kd và 
giải mã Ke rồi gửi khóa lập mã cho Alice, Alice dùng khóa lập mã của Bob để mã hóa 
sau đó gửi bản tin đã mã cho Bob. Bob dùng khóa bí mật của mình để giải mã bản tin 
nhận đƣợc. 
Ý tƣởng về một hệ mật khoá công khai đã đƣợc Diffie và Hellman đƣa ra vào 
năm 1976. Việc hiện thực hoá nó do Rivesrt, Shamir và Adleman đƣa ra đầu tiên vào 
năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA. Kể từ đó một số hệ mật đƣợc công bố, 
độ mật của chúng dựa trên các bài toán tính toán khác nhau. 
Giáo trình Bảo mật thông tin 
90 
4.1.1. Một số bài toán cơ bản 
Phần này giới thiệu một số bài toán số học đƣợc sử dụng khi xây dựng các hệ 
mật mã khoá công khai 
Bài toán phân tích số nguyên (thành thừa số nguyên tố): 
 Cho số nguyên dƣơng n , tìm tất cả các ƣớc số nguyên tố của nó, hay là tìm 
dạng phân tích chính tắc của n = 1 2
1 2. ...
k
kp p p
 , trong đó pi là các số nguyên tố từng cặp 
khác nhau và các i 1. 
 Bài toán này có liên hệ mật thiết với các bài toán thử tính nguyên tố hay thử 
tính hợp số của một số nguyên. 
 Trong lý thuyết mật mã, bài toán này thƣờng đƣợc sử dụng với các dữ liệu n là 
số nguyên Blum, tức các số nguyên dƣơng có dạng tích của hai số nguyên tố lớn nào 
đó. 
Bài toán RSA (Rivest-Shamir-Adleman) : 
 Cho số nguyên dƣơng n là tích của hai số nguyên tố lẻ khác nhau, một số 
nguyên dƣơng e sao cho gcd(e, (n)) = 1, và một số nguyên c, tìm một số nguyên m 
sao cho (mod )em c n . 
 Điều kiện gcd(e, (n)) = 1 bảo đảm với mỗi số nguyên c 0, 1,..., n -1 có 
đúng một số m 0, 1,..., n -1 sao cho (mod )em c n 
Nếu biết hai thừa số nguyên tố của n thì sẽ tính đƣợc (n) = (p -1)(q -1). Vì 
gcd(e, (n)) =1 nên tính đƣợc d = e -1mod (n), do đó sẽ tìm đƣợc m = c d modn. Nhƣ 
vậy, bài toán RSA có thể qui dẫn trong thời gian đa thức về bài toán phân tích số 
nguyên. 
Bài toán thặng dƣ bậc hai : 
 Cho một số nguyên lẻ n là hợp số, và một số nguyên a Jn ( tập tất cả các số a 
có ký hiệu Jacobi J(a,n) =1). Hãy quyết định xem a có là thặng dƣ bậc hai theo mod n 
hay không? 
 Trong lý thuyết mật mã, bài toán này cũng thƣờng đƣợc xét với trƣờng hợp n là 
số nguyên Blum. Khi đó nếu a Jn , thì a là thặng dƣ bậc hai theo modn khi và chỉ khi 
J(a,n) =1, điều kiện này có thể thử đƣợc vì nó tƣơng đƣơng với điều kiện a (p -1)/2  1 
(modp). Nhƣ vậy, trong trƣờng hợp này, bài toán thặng dƣ bậc hai có thể qui dẫn trong 
Giáo trình Bảo mật thông tin 
91 
thời gian đa thức về bài toán phân tích số nguyên. Mặt khác, nếu không biết cách phân 
tích n thành thừa số nguyên tố thì cho đến nay, không có cách nào giải đƣợc bài toán 
thặng dƣ bậc hai trong thời gian đa thức. 
Bài toán tìm căn bậc hai mod n : 
 Cho một số nguyên lẻ n là hợp số Blum, và một số a Qn (tập các thặng dƣ bậc 
hai theo modn). Hãy tìm một căn bậc hai của a theo modn, nghĩa tìm x sao cho x 2  a 
(modn). 
 Nếu biết phân tích n thành thừa số nguyên tố n =p*q, thì bằng cách giải các 
phƣơng trình x 2  a theo các modp và modq, rồi sau đó kết hợp các nghiệm của chúng 
lại theo định lý số dƣ China sẽ đƣợc nghiệm theo modn, tức là căn bậc hai của a theo 
modn cần tìm. Vì mỗi phƣơng trình x 2  a theo modp và modq có hai nghiệm (tƣơng 
ứng theo modp và modq ), nên kết hợp lại thu đƣợc bốn nghiệm, tức bốn căn bậc hai 
của a theo modn. Ngƣời ta đã tìm đƣợc một số thuật toán tƣơng đối đơn giản (trong 
thời gian đa thức) giải phƣơng trình x 2  a (modp) với p là số nguyên tố. Nhƣ vậy, bài 
toán tìm căn bậc hai modn có thể qui dẫn trong thời gian đa thức về bài toán phân tích 
số nguyên. 
Ngƣợc lại, nếu có thuật toán  giải bài toán tìm căn bậc hai modn thì cũng có 
thể xây dựng một thuật toán giải bài toán phân tích số nguyên nhƣ sau: Chọn ngẫu 
nhiên một số x với gcd(x,n) =1, và tính a = x2modn. Dùng thuật toán  cho a để tìm 
một căn bậc hai modn của a. Gọi căn bậc hai tìm đƣợc đó là y. Nếu y  x (modn), thì 
phép thử thất bại, ta phải chọn tiếp một số x khác, nếu y ≢ x (modn) thì gcd(x-y, n) là 
một ƣớc số không tầm thƣờng của n, cụ thể là p hay là q. Vì n có 4 căn bậc hai modn 
nên xác suất của thành công ở mỗi lần thử là 1/2, do đó số trung bình (kỳ vọng toán 
học) các phép thử để thu đƣợc một thừa số p hay q của n là 2, từ đó ta thu đƣợc một 
thuật toán giải bài toán phân tích số nguyên (Blum) với thời gian trung bình đa thức. 
Bài toán logarithm rời rạc : 
 Cho số nguyên tố p, một phần tử nguyên thuỷ theo modulo p (hay là phần 
tử nguyên thuỷ của pZ
 ), và một phần tử  pZ
 . Tìm số nguy ... i khoá Diffie - Hellman 
Nếu không muốn dùng dịch vụ phân phối khoá qua TA thì ngƣời dùng phải 
dùng giao thức thoả thuận khoá để trao đổi khoá mật. Giao thức thoả thuận khoá đầu 
tiên và nổi tiếng nhất là giao thức trao đổi khoá Diffie - Hellman. 
Giao thức Diffie – Hellman: 
Chọn p là số nguyên tố lớn, là phần tử nguyên thuỷ của Z*P, p và công khai. 
1. U chọn aU ngẫu nhiên, mật (0 ≤ aU ≤ p-2) 
2. U tính bu = 
au mod p và gửi đến V. 
3. V chọn aV ngẫu nhiên, mật (0≤ aV ≤ p-2) 
4. V tính bv = 
av mod p và gửi đến U. 
5. U tính: K = ( av ) au mod p 
 V tính: K = ( au ) av mod p 
Giao thức này cũng tƣơng tự với sơ đồ phân phối khoá trƣớc của Diffie - 
Hellman. Sự khác nhau ở chỗ các số mũ aU, aV của U và V đều đƣợc chọn lại mỗi lần 
thực hiện giao thức thay vì cố định. Cũng nhƣ vậy, trong giao thức này, cả U lẫn V đều 
đƣợc đảm bảo khoá tƣơi vì khoá session phụ thuộc vào cả hai số mũ ngẫu nhiên aU và 
aV. 
a. Giao thức trạm tới trạm 
Giáo trình Bảo mật thông tin 
172 
Giao thức thỏa thuận khóa trạm tới trạm (STS) là cải tiến của giao thức phân 
phối khóa Diffie – Hellman, trong đó có bổ sung phần xác thực danh tính của ngƣời 
dùng. STS đƣợc gọi là giao thức thỏa thuận khóa có xác thực. Giao thức giả thiết số 
nguyên tố p và phần tử nguyên thuỷ α đƣợc biết một cách công khai và nó dùng với 
các dấu xác nhận. Mỗi ngƣời sử dụng U sẽ có một sơ đồ chữ ký với thuật toán xác 
minh công khai verU. TA cũng có sơ đồ chữ ký với thuật toán xác minh công khai 
verTA. Mỗi ngƣời sử dụng U có chứng chỉ: 
C(U) = (ID(U), verU, sigTA(ID(U), verU)) 
trong đó ID(U) là thông tin định danh cho U. 
Giao thức trạm tới trạm có xác thực của Diffie, Van Oorschot và Wiener nhƣ sau: 
1. U chọn aU ngẫu nhiên (0≤ aU ≤ p-2) 
2. U tính αau mod p và gửi nó đến V. 
3. V chọn aV ngẫu nhiên, (0≤ aV ≤ p-2) 
4. V tính: αav mod p sau đó tính K = ( αau ) av mod p và yV = sigV (α
au 
,α
av
). 
5. V gửi (C(V), αav, yV) đến U. 
6. U tính: K = ( αav ) au mod p 
Cô dùng verV xác minh yV và xác minh C(V) nhờ verTA 
7. U tính:yU = sigU (α
au 
,α
au
) và gửi (C(U), yU) đến V. 
8. V xác minh yU bằng verU và xác minh C(V) nhờ verTA 
Mức an toàn: 
 STS là giao thức 3 lần truyền tin, thông tin trong giao thức trao đổi nhƣ sau: 
Kẻ tấn công W không thể tính chữ ký của V trên (sigV (α
au 
,α
a‟u
)) vì không biết 
thuật toán ký sigV của V. Tƣơng tự, W không thể thay sigU (α
au 
,α
a‟v
) bằng sigU (α
a‟u 
,α
av
) vì không biết thuật toán ký sigU của U. Điều này đƣợc minh hoạ dƣới đây: 
Tóm lại, nhờ sử dụng chữ ký mà có thể tránh sự tấn công của W. 
Giáo trình Bảo mật thông tin 
173 
Giao thức này không đƣa ra sự khẳng định khoá. Tuy nhiên, dễ dàng biến đổi 
để thực hiện đƣợc điều đó bằng cách định nghĩa: yV = eK(sigV (α
au 
,α
av)) trong bƣớc 4 
và yU = eK(sigU (α
au 
,α
av)) trong bƣớc 7 
b. Các giao thức thoả thuận khoá MTI 
Matsumoto, Takashima, Imai (MTI) đã xây dựng giao thức thỏa thuận khóa 
bằng cách cải biên giao thức trao đổi khóa STS. Giao thức này không yêu cầu U và V 
tính bất kỳ chữ ký nào. Nó là giao thức hai lần truyền vì chỉ có hai lần truyền thông tin 
riêng biệt (một từ U đến V và một từ V đến U). Việc thiết lập giao thức này tƣơng tự 
nhƣ sơ đồ phân phối khoá trƣớc Diffie – Hellman. 
1. U chọn rU ngẫu nhiên, 0≤ rU ≤ p-2 và tính: sU = α
rU 
mod p 
2. U gửi (C(U),sU)) đến V. 
3. V chọn rV ngẫu nhiên, 0≤ rV ≤ p-2 và tính: SV = α
rV 
mod p 
4. V gửi (C(V),sV)) đến U. 
5. U tính: K = sV
au
bV
ru 
mod p tại đây, cô nhận đƣợc giá trị bV từ C(V) 
6. V tính: K = sU
av
bU
rv 
mod p tại đây, anh ta nhận đƣợc giá trị bV từ C(V) 
Trong đó: 
+ p, α đƣợc biết công khai. 
+ Mỗi ngƣời sử dụng U đều có xâu ID(U), số mũ bí mật aU (0≤ aU ≤ p-2) 
và giá trị công khai tƣơng ứng: bU = α
au
 mod p. Tƣơng tự đối với V. 
+ TA sẽ có sơ đồ chữ ký với thuật toán xác minh công khai verTA và 
thuật toán ký mật sigTA. 
+ Mỗi ngƣời sử dụng U có dấu xác nhận: C(U) = (ID(U), bU, 
sigTA(ID(U), bU)) trong đó bU đƣợc thiết lập nhƣ trên. Tƣơng tự cho V. 
+ Cả U và V cùng tính khoá: K = αruav+rvau mod p 
Ví dụ: 
Giả sử p= 27803, α = 5. 
Giả sử U chọn aU = 21131, V chọn aV = 17555 . Khi đó: 
bU = 5
21131
 mod 27803 = 21420 
bV = 5
17555
 mod 27803 = 17100. 
(bU, bV đƣợc đóng trên giấy xác nhận của U và V). 
 Giả sử U chọn rU = 169, V chọn rV = 23456. Khi đó: 
Giáo trình Bảo mật thông tin 
174 
sU = 5
169
 mod 27803 = 6268. 
sV = 5
23456
 mod 27803 = 26759 
U sẽ gửi sU tới V và V sẽ gửi sV tới U. 
U tính khoá: 
KU,V = sV
au
bV
ru 
mod p 
= 26759
21131
17100
169
 mod 27803 = 21600 
V tính khoá: 
KU,V = sU
av
bU
rv 
mod p 
= 6268
17555
21420
23456
 mod 27803 
= 21600 
Độ mật của giao thức MTI trƣớc sự tấn công thụ động đúng bằng bài toán 
Diffie – Hellman. Khi không dùng chữ ký trong suốt quá trình thực hiện giao thức, có 
thể giao thức không an toàn trƣớc sự tấn công giữa đƣờng. Khi có sự tấn công chủ 
động W thì U và V sẽ tính những khoá khác nhau: 
U tính khoá: K = αruav+r‟vau mod p 
V tính khoá: K = αr‟uav+rvau mod p 
Mặc dù U và V đã tính đƣợc những khoá khác nhau (không có lợi cho họ) 
nhƣng W không thể tính ra khoá của U và V vì chúng đòi hỏi phải biết số mũ mật aU 
và aV tƣơng ứng. Cả U và V đều đƣợc đảm bảo rằng ngƣời sử dụng khác trên mạng chỉ 
có thể tính đƣợc khoá mà họ tính đƣợc. Đây là kiểu xác thực khoá ẩn. 
c. Thoả thuận khoá dùng các khoá tự xác nhận 
Phƣơng pháp thoả thuận khoá của Girault đƣa ra không cần dấu xác nhận. Giá 
trị của khoá công khai và danh tính của ngƣời sở hữu nó sẽ ngầm xác thực nó. 
Sơ đồ Girault kết hợp tính chất của RSA và thuật toán logarithm rời rạc. Giả sử 
n=pq, p= 2p1+1, q= 2q1+1 và p, q, p1, q1 đều là các số nguyên tố lớn. Giá trị n chỉ đƣợc 
biết bởi TA. TA chọn số mũ mã hoá e (công khai) và số mũ giải mã d (bí mật ) mà d = 
e
-1
 mod Φ(n). 
Mỗi ngƣời sử dụng U có một xâu ID(U). U nhận đƣợc khoá tự xác nhận pU từ TA. 
trong đó: bU = pU
e
 + ID(U) mod n. 
Nhận khoá xác nhận từ TA. 
1. U chọn số mũ mật aU và tính: bU = α
aU 
mod n 
Giáo trình Bảo mật thông tin 
175 
2. U đƣa aU và bU cho TA. 
3. TA tính: pU = (bU – ID(U))
d
 mod n 
4. TA đƣa pU cho U. 
Giao thức thoả thuận khoá Girault 
1. U chọn rU ngẫu nhiên, 0≤ rU ≤ p-2 và tính: sU = α
rU 
mod n 
2. U gửi ID(U), pU, sU cho V. 
3. V chọn rV ngẫu nhiên, 0≤ rV ≤ p-2 và tính: sV = α
rV 
mod n 
4. V gửi ID(V), pV, sV cho U. 
5. U tính: K = sV
au
 ( pV
e
 + ID(V))
ru
 mod n 
6. và V tính: K = sU
av
 ( pU
e
 + ID(U))
rv
 mod n 
Tại thời điểm kết thúc giao thức, U và V cùng tính ra khoá: K = αruav+rvau mod n 
Ví dụ: 
 p = 839, q = 863, α = 5. 
Khi đó: n = pq = 724057, Φ(n) = (p-1)(q-1) = 722356 
Giả sử TA chọn: d= 125777 làm số mũ giảI mã RSA, khi đó e = 84453. 
Giả sử U có ID(U) = 500021 và aU = 111899 thì: 
bU = 48889 và pU = 650704 
Tƣơng tự, V có ID(V) = 500022 và aV = 423456 thì: 
bV = 111692 và pV = 683556 
Bây giờ khi U và V muốn trao đổi khoá thì: 
U chọn rU = 56381, V chọn rV = 356935. Khi đó: 
 sU = 171007, sV = 320688 
Cả U và V đề tính cùng khoá: K = 42869. 
- Khi đối phƣơng W muốn giả dạng U thì W bắt đầu vớI ID(U) và giá trị 
giả b‟U. Khi đó không có cách nào để W tính số mũ a‟U tƣơng ứng với b‟U (nếu 
bài toán logarithm rời rạc là khó giải). Không có a‟U, W không thể tính đƣợc 
khoá. 
- Khi W ngăn cản U và V tính toán ra khoá chung nhƣ kẻ xâm nhập giữa 
cuộc thì W cũng không thể sao lại việc tính toán của U hoặc V, Vì vậy, sơ đồ 
này cung cấp sự xác thực ngầm nhƣ giao thức MTI. 
Giáo trình Bảo mật thông tin 
176 
Tại sao U đƣợc yêu cầu cung cấp giá trị aU tới TA trong khi TA có thể tính 
pU trực tiếp từ bU mà không cần biết aU? lý do là để đảm bảo tính an toàn thì giá 
trị aU phải đƣợc biết trƣớc khi TA tính pU cho U (TA tính bU dựa vào aU, sau đó 
so sánh với bU nhận từ U: nếu giống nhau thì chấp nhận, ngược lại thì huỷ bỏ). 
Giả sử W chọn một giá trị giả a‟U và tính giá trị tƣơng ứng: b‟U = α
a‟U 
mod n. 
Khi đó: 
p‟U = (b‟U – ID(U))
d
 mod n 
W sẽ tính b'W = b‟U – ID(U) + ID(W) và gửi b‟W , ID(W) tới TA. Giả sử TA 
tính và gửi khoá bí mật p‟W tới W: p‟W = (b‟W – ID(W))
d
 mod n 
Vì b'W - ID(W) = b‟U – ID(U) + ID(W) mod n nên p‟W = p‟U 
Giả sử một thời gian sau, U và V thực thi giao thức và W thay thế thông tin nhƣ sau: 
V sẽ tính khoá: K‟ = αr‟uav+rva‟u mod n = KW 
 U sẽ tính khoá: K = αruav+rvau mod n 
 Cho nên W và V sẽ tham gia cùng một khoá, trong khi v nghĩ là mình đang 
tham gia khoá với U. Vì vậy, W sẽ có thể giải mã bức điện gửi từ V tới U. 
Giáo trình Bảo mật thông tin 
177 
BÀI TẬP 
1. Cho hệ chữ ký điện tử Elgamal có p = 1019, = 191 là một phần tử nguyên thủy 
thuộc Z*p, a = 37. 
a. Hãy tìm khóa của sơ đồ chữ ký trên. 
b. Thực hiện ký trên tài liệu X = 102 với số bí mật k = 143. 
c. Kiểm tra xem cặp (251, 507) có phải là chữ ký trên văn bản X = 127 hay 
không? 
2. Cho hệ chữ ký điện tử RSA có p = 31, q = 41, e = 271. 
a. Hãy tìm khóa của sơ đồ chữ ký trên. 
b. Thực hiện ký trên tài liệu X = 100. 
3. Cho hệ chữ ký điện tử DSS có q = 11, p = 67, = 9,  = 62, khóa bí mật a = 4. Để 
ký trên tài liệu X = 8 ngƣời ta chọn k = 2. Hãy xác định chữ ký trên tài liệu X. 
 4. Giả thiết Bob đang dùng sơ đồ Elgamal, anh ta kí hai bức điện x1 và x2 bằng chữ kí 
(,  1) và (,  2) tƣơng ứng (giá trị này của  giống nhau trong cả hai chữ kí). Cũng 
giả sử UCLN ( 1- 2, p-1)=1. 
a. Hãy cho biết cách tính k hiệu quả khi biết thông tin này 
b. Hãy mô tả cách sơ đồ chữ kí có thể bị phá. 
c. Giả sử p=31847, =5, và  =25703. Tính k và a khi cho trƣớc chữ kí (23972, 
31396 ) với bức điện x=8990 và chữ kí (23972, 20481) trên bức điện x = 31415 
5. Giả sử I thực hiên sơ đồ Elgamal với p = 31847, =5, và  =26379 
a. Xác minh chữ kí (20679, 11082 ) trên bức điện x=20543 
b. Xác định số mũ mật a bằng cách dùng thuật toán tối ƣu hoá thời gian - bộ 
nhớ của Shark, sau đó xác định giá trị k ngẫu nhiên dùng trong việc kí lên bức 
điện x. 
6. Giả sử Bob dùng sơ đồ chữ kí Elgamal với p=467, =2 =132. Giả sử Bob kí lên 
bức điện x=100 bằng chữ kí (29, 51). Hãy tính chữ kí giả mạo mà Oscar có thể lập 
bằng cách dùng h = 100, i = 45 và j =293.Hãy kiểm tra xem chữ ký vừa nhận đƣợc có 
thoả mãn điều kiện xác minh không. 
Giáo trình Bảo mật thông tin 
178 
7. Giả sử Bob dùng DSS với q = 101, p = 7879, = 170, a = 75 còn  = 4567. Xác 
định chữ kí của Bob trên bức điện x = 5011, bằng cách dùng giá trị ngẫu nhiên k = 
49 và chỉ ra cách xác minh chữ kí nhận đƣợc. 
8. Trong sơ đồ Lamport, giả sử rằng hai bức điện x và x‟ bội k (k-tuple) đều do Bob kí. 
Cho l = d(x, x‟) là toạ độ trên đó x và x‟ khác nhau. Hãy chỉ ra cách Oscar có thể kí 2l -
2 bức điện mới. 
9. Giả sử Bob đang dùng chữ kí không chối đƣợc của Chaum Van Antwerpen với p = 
467, = 4, a = 101,  = 449. Giả sử Bob đƣợc trình chữ kí y = 25 trên bức điện x 
=157 và anh ta muốn chứng minh rằng nó giả mạo. Giả sử số ngẫu nhiên của Alice là 
e1 = 46, e2 = 123, f1 =198, f2 =11 trong thủ tục từ chối. Hãy tính các yêu cầu c, d, của 
Alice và các câu trả lời C, D của Bob; chỉ ra rằng phép kiểm tra tính phù hợp của Alice 
sẽ thành công. 
10. Giả sử A và B sử dụng kỹ thuật phân phối khóa Diffie – Hellman để truyền tin cho 
nhau với số nguyên tố đƣợc chọn là p = 71 và phần tử nguyên thủy = 7. 
 a. Nếu khóa bí mật của A là XA = 5 thì khóa công khai của A bằng bao nhiêu. 
 b. Nếu khóa bí mật của B là XB = 12 thì khóa công khai của B bằng bao nhiêu. 
 c. Cho biết khóa bí mật dùng để truyền tin. 
11. Giả sử A và B sử dụng kỹ thuật phân phối khóa Diffie – Hellman để truyền tin cho 
nhau với số nguyên tố đƣợc chọn là p = 11 và phần tử nguyên thủy = 2. 
 a. Chứng minh = 2 là phần tử nguyên thủy của Z*11. 
 b. Nếu khóa công khai của A là YA= 9 thì khóa bí mật của A bằng bao nhiêu? 
 c. Nếu B có khóa công khai YB = 3. Hãy tìm khóa bí mật để truyền tin giữa A 
và B. 
12. Giả sử sơ đồ Blom với k =1 đƣợc thực hiện cho tập 4 ngƣời sử dụng, U, V, W và 
X. Giả thiết p = 7873, rU = 2365, rV =6648, rW = 1837 còn rX = 2186. Các đa thức mật 
g nhƣ sau: 
 gU(x) = 6018 + 6351x 
 gV(x) = 3749 + 7121x 
 gW(x) = 7601 + 7802x 
 gX(x) = 635 + 6828x 
Giáo trình Bảo mật thông tin 
179 
a. Tính khoá cho mỗi cặp ngƣời sử dụng, xác minh rằng mỗi cặp nhận đƣợc một 
khoá chung (nghĩa là KU,V = KV,U v.v...) 
b. Chỉ ra cách W và X cùng nhau tính khoá KV,U 
13. Giả thiết sơ đồ Blom với k = 2 đƣợc thực hiện cho tập 5 ngƣời sử dụng U, V, W, X 
và Y. Giả thiết p = 97, rU = 14, rV = 38, rW = 92, rX =69 còn rY = 70. Các đa thức mật g 
nhƣ sau: 
 gU(x) = 15 + 15x + 2x
2
 gV(x) = 95 + 77x + 83x
2
 gW(x) = 88 + 32x + 18x
2
 gX(x) = 62 + 91x + 59x
2
 gY(x) = 10 + 82x + 52x
2
a. Chỉ ra cách U và V tính khoá KU,V = KV,U 
b. Chỉ ra cách W, X và Y cùng nhau tính khoá KU,V 
13. Xét sơ đồ định danh Girault trong đó p = 167, q = 179 và vì thế n = 29893. Giả sử 
 = 2 và e = 11101. 
a. Tính d 
b. Cho trƣớc ID(U) = 10021 và aU = 9843, tính bU và pU. Cho trƣớc ID(V) = 
10022 và aV = 7692, hãy tính bV và pV 
c. Chỉ ta cách có thể tính bU từ pU và ID(V) bằng cách dùng số mũ công khai e. 
Tƣơng tự, chỉ ra cách tính bV từ pV và ID(V). 
d. Giả sử U chọn ra rU = 15556 và V chọn ra rV = 6420. Hãy tính sU và sV và chỉ 
ra cách U và V tính khoá chung của họ. 
Giáo trình Bảo mật thông tin 
180 
TÀI LIỆU THAM KHẢO 
[1] Douglas Stinson - Cryptography: Theory and Practice. Boca Raton. FL. CRC 
Press, 2007. 
[2] William Stallings. Cryptography and Network Security: Principles and Practice. 
Third Edition. Pearson Education, 2003. 
[3] A. Menezes, P. van Oorschot và S. Vanstone. - Handbook of Applied 
Cryptography, Fifth Edition, CRC Press, 1996. 
[4] Phạm Huy Điển, Hà Huy Khoái. Mã hoá thông tin cơ sở toán học và ứng dụng. 
Nhà xuất bản Đại học Quốc gia Hà Nội. 2004. 
[5] Phan Đình Diệu. Lý thuyết mật mã và an toàn thông tin. Nhà xuất bản Đại học 
Quốc gia Hà Nội. 2006. 
[6]  
[7]  
[8]  
[9]  
[10]  

File đính kèm:

  • pdfgiao_trinh_bao_mat_thong_tin_chuong_4_cac_he_mat_ma_khoa_con.pdf