ݺߣ

ݺߣShare a Scribd company logo

Hệ mật mã Rabin

•Download as PPTX, PDF•
•
Thành phố Đà Lạt
Thành phố Đà Lạt

Thuyết trình nhóm về Hệ mật mã Rabin

1 of 36
TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA VẬT LÝ NGÀNH ĐIỆN TỬ-VIÊN THÔNG MÃ HÓA THÔNG TIN GVHD : Lê Ngọc Luyện NHÓM : 1 SVTH : Nguyễn Thị Hoàng Đăng Huỳnh Gia Đạt Đề tài : Hệ mật mã Rabin
NỘI DUNG CHÍNH  GIỚI THIỆU VỀ HỆ MÃ RABIN  HỆ MÃ HÓA RABIN • SƠ ĐỒ HỆ MÃ HÓA • GIAI ĐOẠN MÃ HÓA • GIAI ĐOẠN GIẢI MÃ • MỘT SỐ VÍ DỤ  CÁC ĐẶC TRƯNG CỦA HỆ MÃ RABIN • TÍNH AN TOÀN CỦA HỆ MÃ • VẤN ĐỀ SỬ DỤNG DƯ THỪA DỮ LIỆU • TÍNH HIỆU QUẢ CỦA HỆ MÃ
GIỚI THIỆU HỆ MẬT MÃ RABIN
SƠ ĐỒ HỆ MẬT MÃ RABIN Sơ đồ hệ mật mã khóa công khai Rabin được cho bởi : S = (P, C, K, E, D) P = C = Zn (n là một số nguyên Blum) n = p.q p ≡ 3 mod 4, q ≡ 3 mod 4 K = (K’, K”) K’ (khóa công khai) = (n, B) (0 <= B <= n-1) K” (khóa bí mật)= (p, q)
Các thuật toán E và D được xác định bởi: E(K’, x) = y = x (x + B) mod n D(K”,y) = B2 4 + y − B 2 mod n SƠ ĐỒ HỆ MẬT MÃ RABIN (TT)
Thuật toán giải mã dK” = D(K”,.): Đặt C = (B2/ 4 ) + y Ta có dK”(y) = 𝐶 − 𝐵 2 mod n, do đó để có dK’’(y),ta cần tính 𝐶mod n, tức cần giải phương trình 𝐙 𝟐 ≡ C mod n. Phương trình đó tương đương với hệ thống gồm hai phương trình sau đây: 𝐙 𝟐 ≡ C mod p 𝐙 𝟐 ≡ C mod q (2) SƠ ĐỒ HỆ MẬT MÃ RABIN (TT)
Vì p và q lá các số nguyên tố nên ta có: 𝐂 𝐩−𝟏 /𝟐 ≡ 1 mod p, 𝐂 𝐩−𝟏 /𝟐 ≡ 1 mod q Theo giả thuyết, p ≡ 3 mod 4 và q ≡ 3 mod 4 nên (p+1)/4 và (q+1)/4 là các số nguyên và ta có: (±𝐂 𝐩+𝟏 /𝟒 ) 𝟐 ≡ C mod p (±𝐂 𝐪+𝟏 /𝟒 ) 𝟐 ≡ C mod q SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
Do đó, phương trình 𝐙 𝟐 ≡ C mod n hay hệ phương trình (*) có 4 nghiệm theo mod n tương ứng với 4 hệ phương trình sau đây: Z ≡ 𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ 𝑪 𝒒+𝟏 /𝟒 mod q (1) Z ≡ 𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ -𝑪 𝒒+𝟏 /𝟒 mod q (2) Z ≡ -𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ 𝑪 𝒒+𝟏 /𝟒 mod q (3) Z ≡ -𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ -𝑪 𝒒+𝟏 /𝟒 mod q (4) SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
Cả 4 nghiệm của 4 hệ phương trình đó theo mod n đều được viết chung dưới 1 ký hiệu là C mod n, vì vậy thuật toán giải mã dK”(y) thực tế sẽ cho ta 4 giá trị khác nhau theo mod n mà bản rõ là 1 trong 4 giá trị đó. Việc chọn giá trị nào trong 4 giá trị tìm được làm bản rõ tuỳ thuộc vào những đặc trưng khác của bản rõ mà người giải mã nhận biết.(vd: bản rõ dưới dạng số phải có biểu diễn nhị phân là mã của 1 văn bản tiếng Anh thông thường) SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
GIẢI THUẬT TẠO KHÓA Đầu tiên mỗi bên tạo 1 khóa công khai và 1 khóa bí mật tương ứng. Bên A phải làm các việc sau: 1. Tạo 2 số ngẫu nhiên lớn và khác nhau là p và q. 2. Tính n = p.q 3. Khóa công khai của A là n, khóa bí mật của A là (p,q)
Sau khi A đã tạo và công khai khóa mã hóa công khai. Lúc đó B gửi một thông điệp cho A thì B sẽ dùng khóa công khai của A để mã hóa, và sau đó A sẽ giải mã thông điệp bằng khóa bí mật tương ứng của mình. Khi đó B cần làm những việc sau: GIẢI THUẬT MÃ HÓA
1. Nhận khóa công khai đã được xác thực của A là n 2. Giả sử thông điệp là một số nguyên m trong khoảng [0, 1, …, n-1] 3. Tính c = m2 mod n 4. Gửi bản mã hóa c cho A GIẢI THUẬT MÃ HÓA(TT)
Chú ý: Vấn đề chọn p và q thì ta có thể chọn p và q là một số nguyên tố bất kỳ. Nhưng chúng ta có thể chọn p ≡ q ≡ 3 mod 4 để việc giải mã được đơn giản. Khi đó chúng ta có 2 cách để giải mã: 1. Giải mã khi chọn p và q bất kỳ 2. Giải mã khi chọn p ≡ q ≡ 3 mod 4 Cách mã hóa thì vẫn làm như nhau. GIẢI THUẬT MÃ HÓA(TT)
Sau khi A nhận được thông điệp đã được mã hóa của B. A đã có khóa bí mật là n = p.q, để nhận được bản rõ m và c thì A phải làm các việc sau: GIẢI THUẬT GIẢI MÃ
I. Giải mã theo cách chọn p và q là bất kỳ a. Chọn ngẫu nhiên b∈Zp cho đến khi b2 – 4a là 1 số không dư bậc 4 mod p, nghĩa là b2−4a p = 1 b. Gọi f là 1 đa thức f = x2 – bx + a trong Zp x c. Tính r = C p+1 /4 mod f (r sẽ là 1 số nguyên) d. Trả lại (r, -r). e. Thực hiện tương tự để tìm 2 căn bậc 2 của a theo mod q. Kết quả sẽ được (s,-s) GIẢI THUẬT GIẢI MÃ(TT)
f. Sửdụng giải thuật Euclidean mở rộng để tìm các số nguyên c và d thỏa: cp+dq = 1 g. Đặt x = ( rdq + scp) mod n và y = ( rdq – scp ) mod n h. Kết quả trả về sẽ là: (±x mod n, ±y mod n) GIẢI THUẬT GIẢI MÃ(TT)
II. Giải mã theo cách chọn p ≡ q ≡ 3 mod 4 Nếu p và q được chọn để cả p ≡ q ≡ 3 mod 4 thì thuật toán để tìm 4 căn bậc 2 của c mod n có thể đơn giản như sau: GIẢI THUẬT GIẢI MÃ(TT)
1. Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a và b thoả mãn: ap + bq = 1 2. Tính r = C p+1 /4 mod p 3. Tính s = C p+1 /4 mod q 4. Tính x = (aps + bqr) mod n. 5. Tính y = (aps – bqr) mod n. 6. 4 căn bặc 2 của c mod n là x, -x mod n và y, -y mod n. GIẢI THUẬT GIẢI MÃ(TT)
1. Tạo khóa: A chọn số nguyên tố p=331, q=311 có p≡q≡3 mod 4 Và tính n = pq = 102941. Khóa công khai của A là n = 102941 Khóa bí mật của A là (p = 331, q = 311). VÍ DỤ
2. Mã hoá: Giả sử 6 bít cuối cùng của thông điệp ban đầu cần phải được lặp lại trước khi mã hoá. Để mã hoá thông điệp 10 bit m =633(10)=1001111001(2), B lặp lại 6 bit cuối cùng của m để nhận được thông điệp 16 bit m =1001111001111001 Theo hệ 10 thì m = 40569. Sau đó B tính: c = m2 mod n =405692 mod 102941 = 23053 và gửi c cho A VÍ DỤ
3. Giải mã: • Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a và b thoả mãn: ap + bq = 1 Tìm được a = 140, b = -149 VÍ DỤ
• Tính r= C p+1 /4 mod p =23053 331+1 /4 mod 331 = 144 • Tính s= C p+1 /4 mod q =23053 311+1 /4 mod 311 = 139 • Tính x=(aps+bqr) mod n =(6052060-6672816) mod 102941 = -25674 • Tính y=(aps-bqs) mod n=(6052060+6672816) mod 102941=40569 VÍ DỤ
Bốn căn bậc 2 của c mod n là x, -x mod n, y và –y mod n. m1 =25674(10) =644A(H)=0110010001001010(2) m2 =77267(10)=2DD3(H)= 0010110111010011(2) m3 = 40569(10)= 9E79(H)= 1001111001111001(2) m4 = 62372(10) = F3A4(H)= 1111001110100100(2) Vì chỉ có m3 có dư thừa dữ liệu yêu cầu, A giải mã c thành m3 (bỏ 6 bit lặp cuối cùng) và phục hồi bản rõ ban đầu là m = 10011110012= 633(10) VÍ DỤ
Ví dụ : Cho n = 77, thông điệp c = 56 Giải mã thông điệp trên VÍ DỤ
Dựa vào thuật toán Euclide mở rộng tìm được a = -8; b = 3 p = 7, q= 19 Tính: r = C p+1 /4 mod p = 4 7+1 /4 mod 7 = 2 s = C q+1 /4 mod q = 4 19+1 /4 mod 19 = 17 x = (aps+bqr) mod n=(-952+114) mod 133=93 y = (aps-bqr) mod n=(-952-114) mod 133=131 m1=x=93 m2=-x mod n=40 m3=y=131 m4=-y mod n=2 VÍ DỤ
1. Tính an toàn của hệ mã a) Một người tấn công bị động cần phục hồi bản rõ m từ bản mã c. Đây chính là giải toán căn bậc 2 ở trên. Vấn đề phân tích ra thừa số n và tính căn bặc 2 theo module n là tương đương về mặt tính toán. Vì vậy giải sử việc phân tích ra thừa số số n là khó về mặt tính toán thì lược đồ mã hóa công khai Rabin được chứng minh là an toàn đối với một người tấn công bị động. TÍNH CHẤT CỦA HỆ MÃ RABIN
(b) Trong khi được chứng minh là an toàn đối với một người tấn công bị động, lược đồ mã hóa công khai Rabin lại không chống nổi một cuộc tấn công bản mã lựa chọn. Một cuộc tấn công như vậy có thê mô tả như sau: TÍNH CHẤT CỦA HỆ MÃ RABIN (TT)
Người tấn công chọn 1 số nguyên m∈Z*n và tính c = m2 mod n. Người tấn công sau đó đưa c đến máy giải mã của A, giải mã c và trả lại 1 bản rõ y nào đó. Vì A không biết m, và m được chọn ngẫu nhiên, bản rõ y không nhất thiết phải giống hệt m. Với khả năng ½, y≢ ± m mod n, khi đó gcd(m-y, n) là một trong các thừa số của n. Nếu y≡±m mod n, người tấn công lại lặp lại với một số m mới. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
Lược đồ mã hoá công khai Rabin dễ bị thương tổn bởi những cuộc tấn công tương tự như với các trường hợp của hệ mã hoá RSA. Giống như hệ RSA, các cuộc tấn công (a) và (b) có thể bị thất bại bằng cách biến đổi bản rõ, trong khi các cuộc tấn công đó có thể tránh được bằng cách thêm dư thừa dữ liệu trước khi mã hoá. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) 2. Sử dụng dư thừa dữ liệu (1) Một nhược điểm của hệ mã hoá công khai Rabin là người nhận phải có nhiệm vụ chọn bản rõ đúng từ 4 khả năng. Sự nhầm lẫn trong việc giải mã có thể vượt qua một cách dễ dàng bằng cách thêm dư thừa dữ liệu vào bản rõ gốc một cách xác định trước khi mã hoá. (ví dụ: 64 bit cuối cùng của thông điệp có thể được lặp lại).
TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) Với khả năng cao, chỉ 1 trong 4 căn bậc 2 của bản mã c là m1, m2, m3, m4 có được dư thừa đó. Người giải mã sẽ chọn bản này làm bản rõ. Nếu không có căn bậc 2 nào của c có dư thừa này, người nhận sẽ từ chối c, vì nó là giả mạo. (2) Nếu sử dụng dư thừa dữ liệu như trên, lược đồ Rabin sẽ không còn dễ bị thương tổn bởi các cuộc tấn công bản mã lựa chọn như nói ở trên.
TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) Nếu người tấn công chọn 1 thông điệp m có dư thừa dữ liệu như yêu cầu và đưa c = m2 mod n vào máy giải mã của A, khả năng rất cao là máy sẽ trả lại bản rõ m cho người tấn công (vì 3 căn bậc 2 của c kia sẽ có khả năng rất cao là không chứa dư thừa dữ liệu như yêu cầu), không đưa ra thông tin mới nào. Mặt khác, nếu người tấn công chọn một thông điệp m mà không có dư thừa dữ liệu cần thiết, khả năng cao là cả bốn căn bậc 2 của c mod n đều không có dư thừa dữ liệu cần thiết
Trường hợp này máy giải mã sẽ thất bại việc giải mã c và không trả lời người tấn công. Chú ý rằng việc chứng minh tính tương đương của việc phá khoá lược đồ cải tiến này bởi một người tấn công thụ động với việc phân tích ra thừa số không còn giá trị nữa. Tuy nhiên, nếu giả sử rằng việc giải mã Rabin gồm hai giai đoạn, giai đoạn thứ nhất là tìm bốn căn bậc 2 của c mod n, và giai đoạn thứ hai là lựa chọn căn bậc 2 làm bản rõ thì vẫn chứng minh được tính tương đương. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
Vì vậy lược đồ mã hoá khoá công khai Rabin, được sửa đổi một cách thích hợp bằng cách thêm dư thừa dữ liệu, là rất được quan tâm ứng dụng. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) 3. Tính hiệu quả Việc mã hoá Rabin là cực kỳ nhanh vì nó chỉ liên quan đến việc tính một bình phương theo module duy nhất. Để so sánh, mã hoá của hệ RSA với e = 3 cần một phép nhân module và một phép bình phương module. Giải mã Rabin chậm hơn mã hoá, nhưng có thể sánh được với tốc độ giải mã của hệ RSA.
Hệ mật mã Rabin

More Related Content

Hệ mật mã Rabin

  • 1. TRƯỜNG ĐẠI HỌC ĐÀ LẠT KHOA VẬT LÝ NGÀNH ĐIỆN TỬ-VIÊN THÔNG MÃ HÓA THÔNG TIN GVHD : Lê Ngọc Luyện NHÓM : 1 SVTH : Nguyễn Thị Hoàng Đăng Huỳnh Gia Đạt Đề tài : Hệ mật mã Rabin
  • 2. NỘI DUNG CHÍNH  GIỚI THIỆU VỀ HỆ MÃ RABIN  HỆ MÃ HÓA RABIN • SƠ ĐỒ HỆ MÃ HÓA • GIAI ĐOẠN MÃ HÓA • GIAI ĐOẠN GIẢI MÃ • MỘT SỐ VÍ DỤ  CÁC ĐẶC TRƯNG CỦA HỆ MÃ RABIN • TÍNH AN TOÀN CỦA HỆ MÃ • VẤN ĐỀ SỬ DỤNG DƯ THỪA DỮ LIỆU • TÍNH HIỆU QUẢ CỦA HỆ MÃ
  • 4. SƠ ĐỒ HỆ MẬT MÃ RABIN Sơ đồ hệ mật mã khóa công khai Rabin được cho bởi : S = (P, C, K, E, D) P = C = Zn (n là một số nguyên Blum) n = p.q p ≡ 3 mod 4, q ≡ 3 mod 4 K = (K’, K”) K’ (khóa công khai) = (n, B) (0 <= B <= n-1) K” (khóa bí mật)= (p, q)
  • 5. Các thuật toán E và D được xác định bởi: E(K’, x) = y = x (x + B) mod n D(K”,y) = B2 4 + y − B 2 mod n SƠ ĐỒ HỆ MẬT MÃ RABIN (TT)
  • 6. Thuật toán giải mã dK” = D(K”,.): Đặt C = (B2/ 4 ) + y Ta có dK”(y) = 𝐶 − 𝐵 2 mod n, do đó để có dK’’(y),ta cần tính 𝐶mod n, tức cần giải phương trình 𝐙 𝟐 ≡ C mod n. Phương trình đó tương đương với hệ thống gồm hai phương trình sau đây: 𝐙 𝟐 ≡ C mod p 𝐙 𝟐 ≡ C mod q (2) SƠ ĐỒ HỆ MẬT MÃ RABIN (TT)
  • 7. Vì p và q lá các số nguyên tố nên ta có: 𝐂 𝐩−𝟏 /𝟐 ≡ 1 mod p, 𝐂 𝐩−𝟏 /𝟐 ≡ 1 mod q Theo giả thuyết, p ≡ 3 mod 4 và q ≡ 3 mod 4 nên (p+1)/4 và (q+1)/4 là các số nguyên và ta có: (±𝐂 𝐩+𝟏 /𝟒 ) 𝟐 ≡ C mod p (±𝐂 𝐪+𝟏 /𝟒 ) 𝟐 ≡ C mod q SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
  • 8. Do đó, phương trình 𝐙 𝟐 ≡ C mod n hay hệ phương trình (*) có 4 nghiệm theo mod n tương ứng với 4 hệ phương trình sau đây: Z ≡ 𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ 𝑪 𝒒+𝟏 /𝟒 mod q (1) Z ≡ 𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ -𝑪 𝒒+𝟏 /𝟒 mod q (2) Z ≡ -𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ 𝑪 𝒒+𝟏 /𝟒 mod q (3) Z ≡ -𝑪 𝒑+𝟏 /𝟒 mod p Z ≡ -𝑪 𝒒+𝟏 /𝟒 mod q (4) SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
  • 9. Cả 4 nghiệm của 4 hệ phương trình đó theo mod n đều được viết chung dưới 1 ký hiệu là C mod n, vì vậy thuật toán giải mã dK”(y) thực tế sẽ cho ta 4 giá trị khác nhau theo mod n mà bản rõ là 1 trong 4 giá trị đó. Việc chọn giá trị nào trong 4 giá trị tìm được làm bản rõ tuỳ thuộc vào những đặc trưng khác của bản rõ mà người giải mã nhận biết.(vd: bản rõ dưới dạng số phải có biểu diễn nhị phân là mã của 1 văn bản tiếng Anh thông thường) SƠ ĐỒ HỆ MẬT MÃ RABIN(TT)
  • 10. GIẢI THUẬT TẠO KHÓA Đầu tiên mỗi bên tạo 1 khóa công khai và 1 khóa bí mật tương ứng. Bên A phải làm các việc sau: 1. Tạo 2 số ngẫu nhiên lớn và khác nhau là p và q. 2. Tính n = p.q 3. Khóa công khai của A là n, khóa bí mật của A là (p,q)
  • 11. Sau khi A đã tạo và công khai khóa mã hóa công khai. Lúc đó B gửi một thông điệp cho A thì B sẽ dùng khóa công khai của A để mã hóa, và sau đó A sẽ giải mã thông điệp bằng khóa bí mật tương ứng của mình. Khi đó B cần làm những việc sau: GIẢI THUẬT MÃ HÓA
  • 12. 1. Nhận khóa công khai đã được xác thực của A là n 2. Giả sử thông điệp là một số nguyên m trong khoảng [0, 1, …, n-1] 3. Tính c = m2 mod n 4. Gửi bản mã hóa c cho A GIẢI THUẬT MÃ HÓA(TT)
  • 13. Chú ý: Vấn đề chọn p và q thì ta có thể chọn p và q là một số nguyên tố bất kỳ. Nhưng chúng ta có thể chọn p ≡ q ≡ 3 mod 4 để việc giải mã được đơn giản. Khi đó chúng ta có 2 cách để giải mã: 1. Giải mã khi chọn p và q bất kỳ 2. Giải mã khi chọn p ≡ q ≡ 3 mod 4 Cách mã hóa thì vẫn làm như nhau. GIẢI THUẬT MÃ HÓA(TT)
  • 14. Sau khi A nhận được thông điệp đã được mã hóa của B. A đã có khóa bí mật là n = p.q, để nhận được bản rõ m và c thì A phải làm các việc sau: GIẢI THUẬT GIẢI MÃ
  • 15. I. Giải mã theo cách chọn p và q là bất kỳ a. Chọn ngẫu nhiên b∈Zp cho đến khi b2 – 4a là 1 số không dư bậc 4 mod p, nghĩa là b2−4a p = 1 b. Gọi f là 1 đa thức f = x2 – bx + a trong Zp x c. Tính r = C p+1 /4 mod f (r sẽ là 1 số nguyên) d. Trả lại (r, -r). e. Thực hiện tương tự để tìm 2 căn bậc 2 của a theo mod q. Kết quả sẽ được (s,-s) GIẢI THUẬT GIẢI MÃ(TT)
  • 16. f. Sửdụng giải thuật Euclidean mở rộng để tìm các số nguyên c và d thỏa: cp+dq = 1 g. Đặt x = ( rdq + scp) mod n và y = ( rdq – scp ) mod n h. Kết quả trả về sẽ là: (±x mod n, ±y mod n) GIẢI THUẬT GIẢI MÃ(TT)
  • 17. II. Giải mã theo cách chọn p ≡ q ≡ 3 mod 4 Nếu p và q được chọn để cả p ≡ q ≡ 3 mod 4 thì thuật toán để tìm 4 căn bậc 2 của c mod n có thể đơn giản như sau: GIẢI THUẬT GIẢI MÃ(TT)
  • 18. 1. Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a và b thoả mãn: ap + bq = 1 2. Tính r = C p+1 /4 mod p 3. Tính s = C p+1 /4 mod q 4. Tính x = (aps + bqr) mod n. 5. Tính y = (aps – bqr) mod n. 6. 4 căn bặc 2 của c mod n là x, -x mod n và y, -y mod n. GIẢI THUẬT GIẢI MÃ(TT)
  • 19. 1. Tạo khóa: A chọn số nguyên tố p=331, q=311 có p≡q≡3 mod 4 Và tính n = pq = 102941. Khóa công khai của A là n = 102941 Khóa bí mật của A là (p = 331, q = 311). VÍ DỤ
  • 20. 2. Mã hoá: Giả sử 6 bít cuối cùng của thông điệp ban đầu cần phải được lặp lại trước khi mã hoá. Để mã hoá thông điệp 10 bit m =633(10)=1001111001(2), B lặp lại 6 bit cuối cùng của m để nhận được thông điệp 16 bit m =1001111001111001 Theo hệ 10 thì m = 40569. Sau đó B tính: c = m2 mod n =405692 mod 102941 = 23053 và gửi c cho A VÍ DỤ
  • 21. 3. Giải mã: • Dùng thuật toán Euclide mở rộng tìm 2 số nguyên a và b thoả mãn: ap + bq = 1 Tìm được a = 140, b = -149 VÍ DỤ
  • 22. • Tính r= C p+1 /4 mod p =23053 331+1 /4 mod 331 = 144 • Tính s= C p+1 /4 mod q =23053 311+1 /4 mod 311 = 139 • Tính x=(aps+bqr) mod n =(6052060-6672816) mod 102941 = -25674 • Tính y=(aps-bqs) mod n=(6052060+6672816) mod 102941=40569 VÍ DỤ
  • 23. Bốn căn bậc 2 của c mod n là x, -x mod n, y và –y mod n. m1 =25674(10) =644A(H)=0110010001001010(2) m2 =77267(10)=2DD3(H)= 0010110111010011(2) m3 = 40569(10)= 9E79(H)= 1001111001111001(2) m4 = 62372(10) = F3A4(H)= 1111001110100100(2) Vì chỉ có m3 có dư thừa dữ liệu yêu cầu, A giải mã c thành m3 (bỏ 6 bit lặp cuối cùng) và phục hồi bản rõ ban đầu là m = 10011110012= 633(10) VÍ DỤ
  • 24. Ví dụ : Cho n = 77, thông điệp c = 56 Giải mã thông điệp trên VÍ DỤ
  • 25. Dựa vào thuật toán Euclide mở rộng tìm được a = -8; b = 3 p = 7, q= 19 Tính: r = C p+1 /4 mod p = 4 7+1 /4 mod 7 = 2 s = C q+1 /4 mod q = 4 19+1 /4 mod 19 = 17 x = (aps+bqr) mod n=(-952+114) mod 133=93 y = (aps-bqr) mod n=(-952-114) mod 133=131 m1=x=93 m2=-x mod n=40 m3=y=131 m4=-y mod n=2 VÍ DỤ
  • 26. 1. Tính an toàn của hệ mã a) Một người tấn công bị động cần phục hồi bản rõ m từ bản mã c. Đây chính là giải toán căn bậc 2 ở trên. Vấn đề phân tích ra thừa số n và tính căn bặc 2 theo module n là tương đương về mặt tính toán. Vì vậy giải sử việc phân tích ra thừa số số n là khó về mặt tính toán thì lược đồ mã hóa công khai Rabin được chứng minh là an toàn đối với một người tấn công bị động. TÍNH CHẤT CỦA HỆ MÃ RABIN
  • 27. (b) Trong khi được chứng minh là an toàn đối với một người tấn công bị động, lược đồ mã hóa công khai Rabin lại không chống nổi một cuộc tấn công bản mã lựa chọn. Một cuộc tấn công như vậy có thê mô tả như sau: TÍNH CHẤT CỦA HỆ MÃ RABIN (TT)
  • 28. Người tấn công chọn 1 số nguyên m∈Z*n và tính c = m2 mod n. Người tấn công sau đó đưa c đến máy giải mã của A, giải mã c và trả lại 1 bản rõ y nào đó. Vì A không biết m, và m được chọn ngẫu nhiên, bản rõ y không nhất thiết phải giống hệt m. Với khả năng ½, y≢ ± m mod n, khi đó gcd(m-y, n) là một trong các thừa số của n. Nếu y≡±m mod n, người tấn công lại lặp lại với một số m mới. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
  • 29. Lược đồ mã hoá công khai Rabin dễ bị thương tổn bởi những cuộc tấn công tương tự như với các trường hợp của hệ mã hoá RSA. Giống như hệ RSA, các cuộc tấn công (a) và (b) có thể bị thất bại bằng cách biến đổi bản rõ, trong khi các cuộc tấn công đó có thể tránh được bằng cách thêm dư thừa dữ liệu trước khi mã hoá. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
  • 30. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) 2. Sử dụng dư thừa dữ liệu (1) Một nhược điểm của hệ mã hoá công khai Rabin là người nhận phải có nhiệm vụ chọn bản rõ đúng từ 4 khả năng. Sự nhầm lẫn trong việc giải mã có thể vượt qua một cách dễ dàng bằng cách thêm dư thừa dữ liệu vào bản rõ gốc một cách xác định trước khi mã hoá. (ví dụ: 64 bit cuối cùng của thông điệp có thể được lặp lại).
  • 31. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) Với khả năng cao, chỉ 1 trong 4 căn bậc 2 của bản mã c là m1, m2, m3, m4 có được dư thừa đó. Người giải mã sẽ chọn bản này làm bản rõ. Nếu không có căn bậc 2 nào của c có dư thừa này, người nhận sẽ từ chối c, vì nó là giả mạo. (2) Nếu sử dụng dư thừa dữ liệu như trên, lược đồ Rabin sẽ không còn dễ bị thương tổn bởi các cuộc tấn công bản mã lựa chọn như nói ở trên.
  • 32. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) Nếu người tấn công chọn 1 thông điệp m có dư thừa dữ liệu như yêu cầu và đưa c = m2 mod n vào máy giải mã của A, khả năng rất cao là máy sẽ trả lại bản rõ m cho người tấn công (vì 3 căn bậc 2 của c kia sẽ có khả năng rất cao là không chứa dư thừa dữ liệu như yêu cầu), không đưa ra thông tin mới nào. Mặt khác, nếu người tấn công chọn một thông điệp m mà không có dư thừa dữ liệu cần thiết, khả năng cao là cả bốn căn bậc 2 của c mod n đều không có dư thừa dữ liệu cần thiết
  • 33. Trường hợp này máy giải mã sẽ thất bại việc giải mã c và không trả lời người tấn công. Chú ý rằng việc chứng minh tính tương đương của việc phá khoá lược đồ cải tiến này bởi một người tấn công thụ động với việc phân tích ra thừa số không còn giá trị nữa. Tuy nhiên, nếu giả sử rằng việc giải mã Rabin gồm hai giai đoạn, giai đoạn thứ nhất là tìm bốn căn bậc 2 của c mod n, và giai đoạn thứ hai là lựa chọn căn bậc 2 làm bản rõ thì vẫn chứng minh được tính tương đương. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
  • 34. Vì vậy lược đồ mã hoá khoá công khai Rabin, được sửa đổi một cách thích hợp bằng cách thêm dư thừa dữ liệu, là rất được quan tâm ứng dụng. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT)
  • 35. TÍNH CHẤT CỦA HỆ MÃ RABIN(TT) 3. Tính hiệu quả Việc mã hoá Rabin là cực kỳ nhanh vì nó chỉ liên quan đến việc tính một bình phương theo module duy nhất. Để so sánh, mã hoá của hệ RSA với e = 3 cần một phép nhân module và một phép bình phương module. Giải mã Rabin chậm hơn mã hoá, nhưng có thể sánh được với tốc độ giải mã của hệ RSA.