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.
Trang 1
Trang 2
Trang 3
Trang 4
Trang 5
Trang 6
Trang 7
Trang 8
Trang 9
Trang 10
Tải về để xem bản đầy đủ
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 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:
- giao_trinh_bao_mat_thong_tin_chuong_4_cac_he_mat_ma_khoa_con.pdf