Khóa luận Nghiên cứu một số chữ ký số đặc biệt và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2010 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Thị Vân Anh NGHIÊN CỨU MỘT SỐ CHỮ KÝ SỐ ĐẶC BIỆT VÀ ỨNG DỤNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: PGS.TS. Trịnh Nhật Tiến HÀ NỘI - 2010 LỜI CẢM ƠN Trƣớc hết, em xin gửi lời cảm ơn sâu sắc tới PGS.TS. Trịnh Nhật Tiến đã hƣớng dẫn em phát triển khóa luận đi từ lý thuyết đến ứng dụng. Sự hƣớng dẫn của thầy trong suốt thời gian qua đã giúp em tiếp cận tới một hƣớng nghiên cứu khoa học mới: đó là nghiên cứu trong lĩnh vực an toàn thông tin. Qua đó, những lý thuyết về an toàn thông tin đã lôi cuốn em và sẽ trở thành hƣớng nghiên cứu tiếp của em sau khi tốt nghiệp. Em xin bày tỏ lòng biết ơn đến các thầy cô trong trƣờng Đại học Công nghệ đã giảng dạy và cho em những kiến thức quý báu, làm nền tảng để em hoàn thành khóa luận cũng nhƣ thành công trong nghiên cứu, làm việc trong tƣơng lai. Cuối cùng, cho em gửi lời cảm ơn sâu sắc tới gia đình, bạn bè đã động viên kịp thời để em học tập tốt và hoàn thành đƣợc khóa luận. Em xin chân thành cảm ơn! Hà Nội, tháng 5 năm 2010 Sinh viên Phạm Thị Vân Anh TÓM TẮT KHÓA LUẬN Những năm gần đây, nhu cầu trao đổi thông tin từ xa của con ngƣời ngày càng lớn, các ứng dụng trao đổi thông tin qua mạng diễn ra ngày càng nhiều. Tuy nhiên, mỗi loại ứng dụng có những đòi hỏi riêng khác nhau, ví dụ nhƣ ứng dụng bầu cử từ xa cần phải che dấu đƣợc thông tin ngƣời bỏ phiếu, hoặc những văn bản đã đƣợc ký nhƣng không muốn ai cũng có thể xác thực chữ ký khi chƣa đƣợc sự đồng ý của ngƣời ký. Chữ ký mù và chữ ký không thể chối bỏ đã ra đời để giải quyết vấn đề nêu trên. Ý tƣởng chính của ký mù là ngƣời ký không biết mình đang ký trên nội dung gì. Ý tƣởng chính của chữ ký không thể chối bỏ là chữ ký mà ngƣời ký tham gia trực tiếp vào quá trình xác thực chữ ký. Khóa luận tốt nghiệp này đề cập về mặt lý thuyết của hai loại chữ ký trên, xây dựng ứng dụng minh họa tƣơng ứng với từng loại chữ ký; đồng thời xây dựng một ứng dụng thực hiện ký số RSA trên file văn bản tiếng Việt sử dụng thƣ viện mã nguồn mở OpenSSL. MỤC LỤC LỜI MỞ ĐẦU .............................................................................................. 1 Chương 1. CÁC KHÁI NIỆM CƠ BẢN .............................................. 3 1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC ........................................ 3 1.1.1. Một số khái niệm trong số học .......................................................... 3 1.1.2. Một số khái niệm trong đại số ......................................................... 13 1.1.3. Khái niệm độ phức tạp của thuật toán ............................................. 17 1.2. MÃ HÓA ........................................................................................ 21 1.2.1. Khái niệm mã hóa dữ liệu ............................................................... 21 1.2.2. Phân loại hệ mã hóa ........................................................................ 22 1.3. KÝ SỐ ............................................................................................. 25 1.3.1. Khái niệm chữ ký số ........................................................................ 25 1.3.2. Phân loại chữ ký số. ........................................................................ 25 1.3.3. So sánh chữ ký thông thƣờng và chữ ký số .................................... 26 1.3.4. Tạo đại diện tài liệu và hàm băm .................................................... 27 Chương 2. CHỮ KÝ MÙ RSA ............................................................ 30 2.1. KHÁI NIỆM CHỮ KÝ MÙ ........................................................... 30 2.1.1. Sơ đồ chữ ký RSA ........................................................................... 30 2.1.2. Sơ đồ chữ ký mù RSA ..................................................................... 31 2.1.3. Ví dụ minh họa ................................................................................ 32 2.2. ỨNG DỤNG CHỮ KÝ MÙ ........................................................... 33 2.2.1. Ứng dụng trong tiền điện tử ............................................................ 33 2.2.2. Ứng dụng trong bỏ phiếu trực tuyến. .............................................. 34 Chương 3. CHỮ KÝ KHÔNG THỂ CHỐI BỎ ................................ 36 3.1. KHÁI NIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 36 3.1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen ............ 36 3.1.2. Ví dụ minh họa ................................................................................ 38 3.1.3. Một số đánh giá về sơ đồ ................................................................. 39 3.2. HÌNH THỨC TẤN CÔNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ .. 43 3.2.1. Tống tiền ngƣời ký .......................................................................... 43 3.2.2. Nhiều ngƣời cùng xác thực chữ ký mà ngƣời ký không biết .......... 43 3.3. ỨNG DỤNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ ......................... 45 3.3.1. Ứng dụng trong thẻ chứng minh thƣ điện tử. .................................. 45 3.3.2. Ứng dụng trong ký hợp đồng qua điện thoại .................................. 45 Chương 4. THỬ NGHIỆM CÁC CHƢƠNG TRÌNH ...................... 46 4.1. THỬ NGHIỆM ỨNG DỤNG CHỮ KÝ SỐ .................................. 46 4.1.1. Giới thiệu ......................................................................................... 46 4.1.2. Mô tả hoạt động chƣơng trình ......................................................... 47 4.2. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA ........................ 53 4.2.1. Giới thiệu ......................................................................................... 53 4.2.2. Mô tả hoạt động chƣơng trình ......................................................... 53 4.3. THỬ NGHIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ ..................... 55 4.3.1. Giới thiệu ......................................................................................... 55 4.3.2. Mô tả hoạt động chƣơng trình ......................................................... 56 KẾT LUẬN ................................................................................................ 60 DANH SÁCH BẢNG Bảng 1: Ví dụ sử dụng thuật toán Euclide tìm ước chung lớn nhất .......................5 Bảng 2: Ví dụ sử dụng thuật toán Euclide mở rộng để tìm phần tử nghịch đảo ..16 Bảng 3: Thời gian chạy của các lớp thuật toán khác nhau ..................................19 DANH SÁCH HÌNH VẼ Hình 1: Giao diện chương trình ký số RSA ..........................................................46 Hình 2: Giao diện chức năng “Ký”RSA ...............................................................47 Hình 3: Giao diện chức năng xác thực chữ ký số RSA .........................................49 Hình 4: Giao diện chức năng mã hóa DES file văn bản và chữ ký ......................50 Hình 5: Giao diện chức năng giải mã DES ..........................................................51 Hình 6: Giao diện chức năng ký mù .....................................................................53 Hình 7: Giao diện chức năng xóa mù chữ ký .......................................................54 Hình 8: Giao diện của người ký chữ ký không thể chối bỏ ..................................55 Hình 9: Giao diện của người xác thực chữ ký không thể chối bỏ ........................55 Hình 10: Thông báo khi chữ ký không thể chối bỏ được xác thực là đúng ..........57 Hình 11: Thông báo khi điều kiện 𝒅 ≡ 𝒙𝒆𝟏𝒈𝒆𝟐𝒎𝒐𝒅 𝒑 không được thỏa mãn ...58 Hình 12: Thông báo khi chữ ký đúng là giả mạo .................................................58 Hình 13: Thông báo khi phát hiện người ký cố tình chối bỏ chữ ký của mình .....59 1 LỜI MỞ ĐẦU Trong những năm gần đây, sự bùng nổ của cách mạng thông tin đang diễn ra nhanh chóng trên phạm vi toàn thế giới. Sự phổ biến rộng rãi của Internet đã kết nối mọi ngƣời trên toàn thế giới lại với nhau, trở thành công cụ không thể thiếu, làm tăng hiệu quả làm việc, tăng sự hiểu biết, trao đổi, cập nhật các thông tin một cách nhanh chóng và tiện lợi. Tuy nhiên Internet là một mạng mở, nó cũng chứa đựng nhiều hiểm họa đe dọa hệ thống mạng, hệ thống máy tính, tài nguyên thông tin của các tổ chức, cá nhân. Ví dụ những tin tức quan trọng nằm ở kho dữ liệu hay đang trên đƣờng truyền có thể bị trộm cắp, bị làm cho sai lệch hoặc có thể bị làm giả mạo. Vì thế, nảy sinh yêu cầu phải làm thế nào để văn bản khi đƣợc gửi sẽ không đƣợc nhìn thấy hay khó có thể giả mạo dù cho có thể xâm nhập vào văn bản. Với sự ra đời của công nghệ mã hóa và chữ ký số đã trợ giúp cho con ngƣời trong việc giải quyết các bài toán nan giải về an toàn thông tin. Một tình huống nảy sinh khi trao đổi thông tin trên mạng, đó là khi ngƣời ta nhận đƣợc một văn bản truyền trên mạng thì làm sao để có thể đảm bảo rằng đó là của đối tác gửi cho mình. Tƣơng tự, ngƣời nhận nhận đƣợc tờ tiền điện tử thì có cách nào để xác nhận rằng đó là của đối tác đã thanh toán cho họ. Ngoài ra còn có rất nhiều các hoạt động kinh tế, xã hội từ xa nhƣ đàm phán, thanh toán, gửi tiền từ xa,... Do đó chữ ký số đƣợc sử dụng ở rất nhiều lĩnh vực: trong kinh tế với việc trao đổi các hợp đồng của các đối tác kinh doanh, trong xã hội là các cuộc bỏ phiếu điện tử hay thăm dò thông tin từ xa,… Tuy nhiên, yêu cầu về chữ ký đặt ra với các ứng dụng là khác nhau. Có những ứng dụng đòi hỏi sự nặc danh của tài liệu đƣợc ký nhƣ ứng dụng bỏ phiếu điện tử, tiền điện tử. Một số ứng dụng khác lại yêu cầu sự tham gia của ngƣời ký vào quá trình xác thực chữ ký. Chữ ký mù (ra đời năm 1983) và chữ ký không thể chối bỏ ( ra đời năm 1989 ) đã giải quyết hai vấn đề nêu ra ở trên. Trong khóa luận này, em chú trọng vào tìm hiểu cơ sở lý thuyết của chữ ký mù và chữ ký không thể chối bỏ kèm theo ứng dụng minh họa với từng loại. Đồng thời xây dựng một ứng dụng thử nghiệm chữ ký số RSA trên file text tiếng Việt. Khóa luận bao gồm các phần cụ thể sau: Chƣơng 1: Các khái niệm cơ bản: nêu lên những lý thuyết toán học cơ bản mà bất kỳ bài toán an toàn thông tin nào cũng cần tới, các khái niệm cơ bản về mã hóa và ký số. 2 Chƣơng 2: Chữ ký mù RSA: trình bày về sơ đồ chữ ký mù RSA, ví dụ minh họa và ứng dụng chữ ký mù. Chƣơng 3: Chữ ký không thể chối bỏ: trình bày về sơ đồ chữ ký không thể chối bỏ Chaum van Antwerpen, ví dụ minh họa, các hình thức tấn công chữ ký không thể chối bỏ và ứng dụng của của chữ ký này. Chƣơng 4: Thử nghiệm các chƣơng trình: thử nghiệm chƣơng trình chữ ký số RSA, chƣơng trình chữ ký mù RSA và chƣơng trình chữ ký không thể chối bỏ. Kết luận. 3 Chương 1. CÁC KHÁI NIỆM CƠ BẢN 1.1. CÁC KHÁI NIỆM TRONG TOÁN HỌC 1.1.1. Một số khái niệm trong số học 1.1.1.1. Ước chung lớn nhất, bội chung nhỏ nhất 1/. Khái niệm - Ước số và bội số + Cho hai số nguyên a và b, b ≠ 0. Nếu có một số nguyên q sao cho a = b*q, ta nói rằng a chia hết cho b, kí hiệu b\a. Ta nói b là ước của a, và a là bội của b. Ví dụ: a = 6, b = 2, ta có 6 = 2*3, ký hiệu 2\6. Ở đây 2 là ƣớc của 6 và 6 là bội của 2 + Cho các số nguyên a, b ≠ 0, tồn tại cặp số nguyên (q, r) (0  r < /b/) duy nhất sao cho a = b * q + r. Khi đó q gọi là thương nguyên, r gọi là số dư của phép chia a cho b. Nếu r = 0 thì ta có phép chia hết. Ví dụ: Cho a = 13, b = 5, ta có 13 = 5*2 + 3. Ở đây thƣơng là q = 2, số dƣ là r = 3. - Ước chung lớn nhất, bội chung nhỏ nhất + Số nguyên d đƣợc gọi là ƣớc chung của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , nếu nó là ƣớc của tất cả các số đó. + Số nguyên m đƣợc gọi là bội chung của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , nếu nó là bội của tất cả các số đó. + Một ƣớc chung d > 0 của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , trong đó mọi ƣớc chung của 𝑎1, 𝑎2, …, 𝑎𝑛 đều là ƣớc của d, thì d đƣợc gọi là ƣớc chung lớn nhất (UCLN) của 𝑎1, 𝑎2, …, 𝑎𝑛 . Ký hiệu d = gcd (𝑎1, 𝑎2, …, 𝑎𝑛 ) hay d = UCLN(𝑎1, 𝑎2, …, 𝑎𝑛 ). Nếu gcd(𝑎1, 𝑎2, …, 𝑎𝑛 ) = 1, thì các số 𝑎1, 𝑎2, …, 𝑎𝑛 đƣợc gọi là nguyên tố cùng nhau. + Một bội chung m > 0 của các số nguyên 𝑎1, 𝑎2, …, 𝑎𝑛 , trong đó mọi bội chung của 𝑎1, 𝑎2, …, 𝑎𝑛 đều là bội của m, thì m đƣợc gọi là bội chung nhỏ nhất (BCNN) của 𝑎1, 𝑎2, …, 𝑎𝑛 . Ký hiệu m = lcm(𝑎1, 𝑎2, …, 𝑎𝑛 ) hay m = BCNN(𝑎1, 𝑎2, …, 𝑎𝑛 ). 4 Ví dụ: Cho a =12, b =15, gcd(12, 15) = 3, lcm(12, 15) = 60. Hai số 8 và 13 là nguyên tố cùng nhau, vì gcd(8, 13) = 1. - Tập 𝒁𝒏 và 𝒁𝒏 ∗ + 𝑍𝑛 = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n. + 𝑍𝑛 ∗= e  𝑍𝑛 , e là nguyên tố cùng nhau với n. Tức là e ≠ 0. Ví dụ: Z7 = {0, 1, 2, 3, 4, 5, 6}. Khi đó số phần tử của Z7 là |Z7 | = 7. 𝑍7 ∗ = {1, 2, 3, 4, 5, 6}. Khi đó số phần tử của 𝑍7 ∗ là |𝑍7 ∗| = 6. 2/. Tính chất - d = gcd(𝑎1, 𝑎2, …, 𝑎𝑛 )  tồn tại các số x1, x2,…, xn sao cho: d = a1x1 + a2x2 + … + anxn Đặc biệt: a1, a2, …, an nguyên tố cùng nhau  tồn tại các số x1, x2,…, xn sao cho: 1 = a1x1 + a2x2 + … + anxn - d = gcd(𝑎1, 𝑎2, …, 𝑎𝑛 )  gcd(𝑎1/𝑑, 𝑎2/𝑑, …, 𝑎𝑛/𝑑) =1. - m = lcm(𝑎1, 𝑎2, …, 𝑎𝑛 )  gcd(𝑚/𝑎1, 𝑚/𝑎2, …, 𝑚/𝑎𝑛 ) =1. - gcd(𝑚𝑎1, m𝑎2, …, m𝑎𝑛 ) = m * gcd(𝑎1, 𝑎2, …, 𝑎𝑛 ) (với m ≠ 0). - Nếu gcd(a, b) =1 thì lcm(a, b) = a * b - Nếu b > 0, a = bq + r thì gcd(a, b) = gcd(b, r) 3/. Thuật toán Euclide tìm ƣớc chung lớn nhất - Bài toán + Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. + Kết quả: gcd(a,b). - Thuật toán (Mô phỏng bằng ngôn ngữ Pascal): Readln(a, b); While b>0 do begin r := a mod b; a := b; b := r; end; Writeln(a); 5 Ví dụ: a=30, b=18; gcd(30,18) = gcd(18,12) = gcd(12,6) = gcd(6,0) = 6 Bảng 1: Ví dụ sử dụng thuật toán Euclide tìm ước chung lớn nhất a b r a = b.q + r 30 18 12 30 = 18 * 1+12 18 12 6 18 = 12 * 1+6 12 6 0 12 = 6 * 2 + 0 4/. Thuật toán Euclide mở rộng - Bài toán: + Dữ liệu vào: Cho hai số nguyên không âm a, b, a ≥ b. + Kết quả: d = gcd (a,b) và hai số x, y sao cho: a.x + b.y = d. - Thuật toán (Mô phỏng bằng ngôn ngữ Pascal): Readln(a, b); IF b=0 THEN Begin d := a; x := 1; y := 0; writeln(d, x, y); End ELSE Begin x2 := 1; x1 := 0; y2 := 0; y1 := 1; While b>0 Do begin q := a div b; r := a mod b;x := x2 – q * x1; y := y2 – q * y1; a := b; b := r; x2 := x1; x1 := x; y2 := y1; y1 := y; end; d := a; x := x2; y := y2; writeln(d, x1, x2); End; 6 1.1.1.2. Quan hệ “Đồng dư” 1/. Khái niệm - Cho các số nguyên a, b, m (m > 0). Ta nói rằng a và b “đồng dư” với nhau theo modulo m nếu chia a và b cho m ta nhận đƣợc cùng một số dƣ. Ký hiệu: a ≡ b (mod m). Ví dụ: 17 ≡ 5 (mod 3) vì chia 17 và 5 cho 3, đƣợc cùng số dƣ là 2. - Nhận xét: Các mệnh đề sau đây là tƣơng đƣơng: + a ≡ b (mod m) (1) + m \ (a – b) (2) + Tồn tại số nguyên t sao cho a = b + m.t (3) Chứng minh: + (1)  (2): Nếu có (1), thì theo định nghĩa: a, b chia cho m, phải có cùng số dƣ, do đó: a = mqa + r; b = mqb + r; Suy ra (a – b) = m.(qa - qb), tức là m \ (a - b). + (2)  (3): Nếu có (2), tức là m\(a – b). Nghĩa là có t ∈ Z sao cho a - b = mt hay a = b + mt + (3)  (1): Nếu có (3), tức là tồn tại số nguyên t sao cho a = b + m.t. Lấy a chia cho m, giả sử thƣơng là qa và dƣ r, hay a = mqa + r (0 ≤ r < m), do đó: b + m.t = a = mqa + r hay b = m(qa - t) + r (0 ≤ r < m). Điều đó chứng tỏ khi chia a và b cho m đƣợc cùng số dƣ r, hay a ≡ b (mod m). 2/. Các tính chất của quan hệ “đồng dƣ” - Quan hệ “đồng dư” là quan hệ tương đương trong Z Với mọi số nguyên dƣơng m ta có: + a ≡ a (mod m) với mọi a ∈ Z (tính chất phản xạ) + a ≡ b (mod m) thì b ≡ a (mod m) (tính chất đối xứng) + a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m) (tính chất bắc cầu) 7 - Tổng hay hiệu các “đồng dư” + (a+b) (mod n)  [(a mod n) + (b mod n)] (mod n) + (a- b) (mod n)  [(a mod n) - (b mod n)] (mod n) Tổng quát: Có thể cộng hoặc trừ từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m), i = 1...k, thì: 𝑡𝑖𝑎𝑖 ≡ 𝑡𝑖𝑏𝑖(𝑚𝑜𝑑 𝑚) 𝑘 𝑖=1 𝑣ớ𝑖 𝑡𝑖 = ± 1 𝑘 𝑖=1 - Tích các “đồng dƣ”: (a * b) (mod n)  [(a mod n) * (b mod n)] (mod n) Tổng quát: Có thể nhân từng vế nhiều đồng dƣ thức theo cùng một modulo m, ta đƣợc một đồng dƣ thức theo cùng modulo m, tức là: Nếu ai ≡ bi (mod m) với i = 1...k, thì ta có: 𝑎𝑖 ≡ 𝑏𝑖 𝑘 𝑖=1 (𝑚𝑜𝑑 𝑚) 𝑘 𝑖=1 - Hệ quả: + Có thể cộng hoặc trừ cùng một số vào hai vế của một đồng dƣ thức. + Có thể chuyển vế các số hạng của đồng dƣ thức bằng cách đổi dấu các số hạng đó. + Có thể cộng vào một vế của đồng dƣ thức một bội của modulo: a ≡ b (mod m)  a + km ≡ b (mod m) với mọi k  Z + Có thể nhân hai vế của một đồng dƣ thức với cùng một số: a ≡ b (mod m)  ac ≡ bc (mod m) với mọi c  Z + Có thể nâng lên lũy thừa bậc nguyên không âm cho 2 vế của một đồng dƣ thức: a ≡ b (mod m)  an ≡ bn (mod m) với mọi n  Z+ + Có thể chia 2 vế đồng dƣ thức cho một ƣớc chung nguyên tố với modulo: c\a, c\b, (c,m) = 1, a ≡ b (mod m)  a/c ≡ b/c (mod m) 8 + Có thể nhân 2 vế đồng dƣ thức và modulo với cùng một số nguyên dƣơng: Nếu a ≡ b (mod m), c > 0  ac ≡ bc (mod mc) + Có thể chia 2 vế đồng dƣ thức và modulo cho cùng một số nguyên dƣơng là ƣớc chung của chúng: Nếu c \ (a, b, m)  a/c ≡ b/c (mod m/c) + a ≡ b (mod m)  a ≡ b (mod k) với k \ m + a ≡ b (mod m)  gcd(a, m) = gcd(b, m) 3/. Các lớp thặng dƣ - Quan hệ “đồng dƣ” theo modulo m trên tập Z (tập các số nguyên) là một quan hệ tƣơng đƣơng (vì có tính chất phản xạ, đối xứng, bắc cầu), do đó nó tạo ra trên tập Z một phân hoạch gồm các lớp tƣơng đƣơng: hai số nguyên thuộc cùng một lớp tƣơng đƣơng khi và chỉ khi chúng có cùng một số dƣ khi chia cho m. - Mỗi lớp tƣơng đƣơng đại diện bởi một số duy nhất trong Zm = {0, 1, 2,…, m-1} là số dƣ khi chia các số trong lớp cho m, ký hiệu một lớp đƣợc đại diện bởi số a là [a]m .Nhƣ vậy [a]m = [b]m  a ≡ b (mod m) Vì vậy ta có thể đồng nhất Zm với tập các lớp tƣơng đƣơng theo modulo m. - Zm ={0, 1, 2,…, m-1} đƣợc gọi là tập các “thặng dư đầy đủ” theo modulo m. Mọi số nguyên bất kỳ đều có thể tìm đƣợc trong Zm một số đồng dƣ với mình theo modulo m. 1.1.1.3. Số nguyên tố 1/. Khái niệm Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ƣớc là 1 và chính nó. Ví dụ: Các số 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 là số nguyên tố. 2/. Một số định lý về số nguyên tố - Định lý: về số nguyên dương > 1 Mọi số nguyên dƣơng n > 1 đều có thể biểu diễn đƣợc duy nhất dƣới dạng: 1 2 kn n n 1 2 k . ...=P P Pn trong đó: k, ni (i =1,2,..,k) là các số tự nhiên, Pi là các số nguyên tố, từng đôi một khác nhau. 9 - Định lý: Mersenne Cho p = 2 k -1, nếu p là số nguyên tố thì k phải là số nguyên tố. Chứng minh Bằng phản chứng, giả sử k không là nguyên tố. Khi đó k = a.b với 1 < a, b < k. Nhƣ vậy p = 2k -1 = 2ab -1 = (2a)b -1= (2a -1).E (Trong đó E là một biểu thức nguyên - áp dụng công thức nhị thức Newton). Điều này mâu thuẫn giả thiết p là nguyên tố. Vậy giả sử là sai, hay k là số nguyên tố. - Hàm Euler Cho số nguyên dƣơng n, số lƣợng các số nguyên dƣơng bé hơn n và nguyên tố cùng nhau với n đƣợc ký hiệu (𝒏) và gọi là hàm Euler. + Nhận xét: Nếu p là số nguyên tố, thì  𝒑 = 𝒑 − 𝟏 Ví dụ: Tập các số nguyên không âm nhỏ hơn 7 là Z7 = {0, 1, 2, 3, 4, 5, 6}. Do 7 là số nguyên tố, nên tập các số nguyên dƣơng nhỏ hơn 7 và nguyên tố cùng nhau với 7 là Z7 * = {1, 2, 3, 4, 5, 6}. Khi đó |Z| = (p) = p - 1 = 7 - 1 = 6 + Định lý về hàm Euler Nếu n là tích của hai số nguyên tố p, q thì  𝑛 =  𝑝 . 𝑞 = 𝑝 − 1 . 𝑞 − 1 3/. Một số phƣơng pháp kiểm tra tính nguyên tố Kiểm tra tính nguyên tố của một số nguyên dƣơng là bài toán nảy sinh trong nhiều ứng dụng, đặc biệt là trong lý thuyết mật mã. - Phương pháp cổ điển Ý tưởng: Kiểm tra tính nguyên tố của một số nguyên dƣơng n theo định nghĩa: + Thử lần lƣợt tìm các ƣớc của n, từ 2 đến n / 2. + Nếu không tìm đƣợc ƣớc nào thì kết luận n là nguyên tố. 10 Thuật toán: KT := 0; for i := 2 to sqrt(n) do if (n mod i) = 0 then begin KT := 1; Break; end; IF KT = 1 THEN Writeln (‘n không nguyên tố ‘) ELSE Writeln (‘n nguyên tố ‘); - Phương pháp “xác suất“ + Trên cơ sở các định lý về số nguyên tố, hiện nay ngƣời ta có các phƣơng pháp “xác suất“ để kiểm tra tính nguyên tố của một số nguyên dƣơng n. Ví dụ các phƣơng pháp: Solovay-Strassen [13], Miller-Rabin [7][14],… + Định lý Ferma: Nếu p là số nguyên tố, a là số nguyên, thì ap ≡ a (mod p). Nếu p nguyên tố, p không chia hết cho a, thì ap-1 ≡ 1 (mod p). Ví dụ: 47 ≡ 4 (mod 7); 47-1 ≡ 1 (mod 7). + Định lý Euler Nếu gcd(a, m) = 1 thì 𝑎(𝑚) ≡ 1 (mod m). Trƣờng hợp m là số nguyên tố, ta có định lý Ferma. Ví dụ: m = 10,  𝑚 =  2 . 5 = 1 ∗ 4 = 4 Ta có 74 ≡ 1 (mod 10), 94 ≡ 1 (mod 10), 214 ≡ 1 (mod 10). + Hệ quả 1 Nếu gcd(c, m) = 1 và a ≡ b (mod (𝑚)) với a, b là các số tự nhiên, thì c a ≡ cb (mod m) và suy ra ca ≡ 𝑐𝑎 𝑚𝑜𝑑(𝑚) ( mod m ). Chứng minh: a ≡ b (mod (𝑚)) nên a = b + k(𝑚), k  Z và vì vậy 𝑐𝑎 = 𝑐𝑏+𝑘(𝑚) = 𝑐𝑏 . (𝑐(𝑚))𝑘 ≡ 𝑐𝑏 (mod m), theo định lý Euler. 11 Nhận xét: Hệ quả trên giúp giảm nhẹ việc tính toán đồng dƣ của lũy thừa bậc cao. Ví dụ: Ta thấy  15 =  5 . 3 = 4 ∗ 2 = 8 và 1004 ≡ 4 (mod 8). Do đó 21004 (mod 15) = 24 (mod 15) = 16 (mod 15) = 1. + Hệ quả 2 Nếu các các số nguyên e, d thỏa mãn e.d ≡ 1 (mod  𝑚 ), thì với mọi số c nguyên tố cùng nhau với m, ta có (ce)d ≡ c (mod m). Chứng minh: Đặt a = e.d và b = 1, từ hệ quả 1 ta có hệ quả 2. Hệ quả này đóng vai trò then chốt trong việc thiết lập các hệ mã mũ sau này (ví dụ: hệ RSA [1][2] ). 4/. Tính toán đồng dƣ của “ lũy thừa” lớn Để tính đồng dƣ của một số có lũy thừa a lớn theo modulo m, xét hai trƣờng hợp: - Trường hợp a >  𝒎 Trong trƣờng hợp a >  m , khi ấy b < a. Ngƣời ta dùng hệ quả 1 để tính “đồng dƣ” của “ lũy thừa” lớn. - Trường hợp  𝒎 > a Trong thực tế tính toán thƣờng gặp m lớn, do đó  𝑚 lớn, thậm chí > a, khi ấy ngƣời ta dùng kỹ thuật khác, ví dụ phƣơng pháp bình phƣơng liên tiếp. + Phương pháp bình phương liên tiếp Ví dụ: Tính 8743 (mod 103). Khai triển số mũ 43 dƣới dạng cơ số 2: 43 = 32 + 8 + 2 + 1 = 2 5 + 2 3 + 2 1 + 2 0 (*) Tính liên tiếp các “đồng dƣ” bình phƣơng nhƣ sau: 87 (mod 103) = 87 (ứng với 20) 87 2 (mod 103) = 50 (ứng với 21) 87 4 (mod 103) = 50 2 (mod 103) = 28 87 8 (mod 103) = 28 2 (mod 103) = 63 (ứng với 23) 87 16 (mod 103) = 63 2 (mod 103) = 55 12 87 32 (mod 103) = 55 2 (mod 103) = 38 (ứng với 25) Theo khai triển (*), lấy tích của các lũy thừa bậc 25 , 23 , 21 , 20 (rút gọn theo modulo 103), thu đƣợc kết quả: 87 43 (mod 103) = 38 * 63 * 50 * 87 (mod 103) = 85 + Định lý về Số dư (ĐL Trung Quốc) Cho tập số nguyên tố cùng nhau từng đôi một m1, m2,…mr. Với mỗi bộ số nguyên bất kỳ a1, a2,…ar , hệ phƣơng trình đồng dƣ: x ≡ ai (mod mi), (i =1, 2, …, r), luôn có nghiệm duy nhất theo modulo m, m = m1.m2.…mr . Nghiệm này có thể tính theo công thức: x = a1m2m3…mrb1 + m1a2m3…mrb2 + m1m2a3m3…mrb3 +…+ m1m2…mr-1arbr (mod m1.m2.…mr), Trong đó bi = (m1.m2…mi-1mi+1…mr) -1 (mod mi), i =1, 2,…, r. Nhận xét: Định lý số dƣ Trung Quốc cho phép tính đồng dƣ theo modulo của một số lớn (tích của nhiều số nguyên tố cùng nhau), thông qua tính toán đồng dƣ theo modulo các số nhỏ (từng thừa số). Ví dụ: Tìm nghiệm của hệ phƣơng trình: x ≡ 3118 mod 5353 x ≡ 139 mod 391 x ≡ 239 mod 247 Vì các số 5353, 391, 247 nguyên tố cùng nhau, nên theo định lý Trung Quốc về số dƣ, hệ có nghiệm duy nhất theo modulo m = 5353*391*247 = 516976681. Để tìm x mod m ta tính: m1 = m/5353 = 96577 → y1 = 96577 -1 mod 5353 = 5329 m2 = m/391 = 1322191 → y2 = 1322191 -1 mod 391= 16 m3 = m/247 = 2093023 → y3 = 2093023 -1 mod 247 = 238 x = 3118.96577.5329 + 139.1322191.16 + 239.2093023.238 (mod m) = 13824 (mod m) 13 1.1.2. Một số khái niệm trong đại số 1.1.2.1. Cấu trúc Nhóm 1/. Khái niệm Nhóm - Nhóm là một bộ (G, *), trong đó + * là phép toán hai ngôi + G  , trên G thoả mãn ba tính chất sau:  Phép toán có tính kết hợp: (x*y)*z = x*(y*z) (x, y, z  G)  Có phần tử phần tử trung lập e  G: x * e = e * x = x (x  G)  x G, có phần tử nghịch đảo x’ G: x * x’ = x’ * x = e. - Cấp của nhóm G đƣợc hiểu là số phần tử của nhóm, ký hiệu là G . Cấp của nhóm có thể là  nếu G có vô hạn phần tử. - Nhóm Abel là nhóm (G, *), trong đó phép toán hai ngôi * có tính giao hoán. Tính chất: Nếu a * b = a * c, thì b = c Nếu a * c = b * c, thì a = b Ví dụ: - Tập hợp các số nguyên Z cùng với phép cộng (+) thông thƣờng là nhóm giao hoán, có phần tử đơn vị là số 0. Gọi là nhóm cộng các số nguyên. - Tập Q* các số hữu tỷ khác 0 (hay tập R* các số thực khác 0), cùng với phép nhân (*) thông thƣờng là nhóm giao hoán, gọi là nhóm nhân các số hữu tỷ (số thực) khác 0. - Tập các vectơ trong không gian với phép toán cộng vectơ là nhóm giao hoán. 2/. Nhóm con của nhóm (G, *) Nhóm con của G là tập S  G, S  , và thỏa mãn các tính chất sau: - Phần tử trung lập e của G nằm trong S. - S khép kín đối với phép tính (*) trong G, tức là x*y  S (𝑥,𝑦 S) - S khép kín đối với phép lấy nghịch đảo trong G, tức 𝑥−1  S (xS) 14 1.1.2.2. Nhóm Cyclic 1/. Khái niệm nhóm Cyclic Nhóm (G, *) đƣợc gọi là nhóm Cyclic nếu nó đƣợc sinh ra bởi một trong các phần tử của nó. Tức là có phần tử g  G mà với mỗi a  G, đều tồn tại số n  N để g n = g * g * … * g = a. (Chú ý g * g * … * g là g * g với n lần). Khi đó g đƣợc gọi là phần tử sinh hay phần tử nguyên thuỷ của nhóm G. Nói cách khác: G đƣợc gọi là nhóm Cyclic nếu tồn tại g  G sao cho mọi phần tử trong G đều là một luỹ thừa nguyên nào đó của g. Ví dụ: Nhóm (Z +, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g = 1. 2/. Cấp của nhóm Cyclic Cho (G, *) là nhóm Cyclic với phần tử sinh g và phần tử trung lập e. - Nếu tồn tại số tự nhiên nhỏ nhất n mà gn = e, thì G sẽ chỉ gồm có n phần tử khác nhau: e, g, g 2 , g 3 , . . . , g n - 1 . Khi đó G đƣợc gọi là nhóm Cyclic hữu hạn cấp n. - Nếu không tồn tại số tự nhiên n để gn = e, thì G có cấp . Ví dụ: (Z +, +) gồm các số nguyên dƣơng là Cyclic với phần tử sinh g = 1, e = 0. Đó là nhóm Cyclic vô hạn, vì không tồn tại số tự nhiên n để gn = e. 3/. Cấp của một phần tử trong nhóm Cyclic Phần tử   G đƣợc gọi là có cấp d nếu d là số nguyên dƣơng nhỏ nhất sao cho d = e, trong đó e là phần tử trung lập của G. Nhƣ vậy phần tử  có cấp 1, nếu  = e. 1.1.2.3. Nhóm (𝒁𝒏 ∗ , phép nhân mod n) 1/. Khái niệm tập thặng dƣ thu gọn theo modulo - Kí hiệu Zn = 0, 1, 2, .. . , n-1 là tập các số nguyên không âm < n. Zn và phép cộng (+) lập thành nhóm Cyclic có phần tử sinh là 1, phần tử trung lập e = 0. (Zn, + ) gọi là nhóm cộng, đó là nhóm hữu hạn có cấp n. 15 - Kí hiệu 𝑍𝑛 ∗ = x  Zn , x là nguyên tố cùng nhau với n (tức là x phải  0). 𝑍𝑛 ∗ đƣợc gọi là Tập thặng dư thu gọn theo mod n, có số phần tử là (n). 𝑍𝑛 ∗ với phép nhân mod n lập thành một nhóm (nhóm nhân),phần tử trung lập e=1. - Tổng quát (Zn * , phép nhân mod n) không phải là nhóm Cyclic. - Nhóm nhân 𝑍𝑛 ∗ là Cyclic chỉ khi n có dạng: 2, 4, pk, hay 2pk với p là nguyên tố lẻ. 2/. Một số kết quả đã đƣợc chứng minh - Định lý Lagrange: Nếu G là nhóm cấp n và   G, thì cấp của  là ước của n. - Hệ quả: Giả sử   có cấp m, thì m là ước của (n). - Định lý: Nếu p là số nguyên tố thì là nhóm Cyclic. Nếu b  thì 𝑏(n)  1 (mod n). Nếu p là số nguyên tố thì (p) = p - 1. Do đó với b  (b nguyên tố với p), thì 𝑏(p) 1 (mod n), hay bp -1  1 (mod n). Chú ý: Theo định nghĩa, phần tử   có cấp d nếu d là số nguyên dƣơng nhỏ nhất sao cho  d = e trong . Nhƣ vậy trong ta hiểu là  d  e (mod n). - Định lý: Nhóm con của một nhóm Cyclic là một nhóm Cyclic. 3/. Phần tử nghịch đảo đối với phép nhân - Định nghĩa: Cho a  Zn , nếu tồn tại b  Zn sao cho a.b  1 (mod n), ta nói b là phần tử nghịch đảo của a trong Zn và ký hiệu a -1 . Một phần tử có phần tử nghịch đảo, gọi là khả nghịch. - Định lý: UCLN (a, n) = 1  Phần tử a  Zn có phần tử nghịch đảo. Chứng minh: Nếu a.a-1 ≡ 1 (mod n) thì a.a-1 = 1 + kn ↔ a.a-1 - kn = 1 → (a, n) =1. Nếu (a, n) = 1, ta có aa-1 + kn = 1 → a.a-1 = 1+kn, do đó a.a-1 ≡ 1 (mod n). - Hệ quả: Mọi phần tử trong 𝑍𝑛 ∗ đều có phần tử nghịch đảo. * nZ * pZ * nZ * pZ * nZ * nZ * nZ 16 - Tìm phần tử nghịch đảo bằng Thuật toán Euclid mở rộng Input: a  Zn , n Output: Phần tử nghịch đảo của a. Procedure Invert(a,n); begin g0:=n; g1:=a; u0:=1; u1:=0; v0:=0; v1:=1; i:=1; while gi  0 do begin y := gi-1 div gi; gi+1 := gi-1 - y.gi; ui+1 := ui-1 - y.ui; vi+1 := vi-1 - y.vi; i:=i+1; end; t := vi-1; if t > 0 then a -1 := t else a -1 := t + n; end; Ví dụ: Tìm phần tử nghịch đảo của 3 trong Z7 Tức là phải giải phƣơng trình 3.x ≡ 1 (mod 7), x sẽ là phần tử nghịch đảo của 3. Bảng 2: Ví dụ sử dụng thuật toán Euclide mở rộng để tìm phần tử nghịch đảo i 𝑔𝑖 𝑢𝑖 𝑣𝑖 y 0 7 1 0 1 3 0 1 2 2 1 1 -2 3 3 0 Vì t = v2 = -2 < 0 do đó x = a -1 := t + n = -2 + 7 = 5. Vậy 5 là phần tử nghịch đảo của 3 trong Z7 Chú ý - Định lý (Euler tổng quát): Nếu (a, n) = 1 thì 𝑎(𝑛) mod n = 1 - Hệ quả: Nếu p là số nguyên tố và (a, p) = 1, thì 𝑎𝑝−1 (mod p) = 1 17 4/. Khái niệm Logarit rời rạc Cho p là số nguyên tố, g là phần tử nguyên thủy của Zp ,   𝑍𝑝 ∗ “Logarit rời rạc” chính là việc giải phƣơng trình x = logg (mod p) với ẩn x. Hay phải tìm số x duy nhất sao cho: gx   (mod p). 5/. Thặng dƣ bậc hai - Thặng dƣ bậc hai: Cho p là số nguyên tố lẻ, x là một số nguyên dƣơng  p-1. x đƣợc gọi là “thặng dư bậc hai” mod p, nếu phƣơng trình y2  x mod p có lời giải. 1.1.3. Khái niệm độ phức tạp của thuật toán 1.1.3.1. Khái niệm thuật toán 1/. Khái niệm bài toán Bài toán đƣợc diễn đạt bằng hai phần: - Input: Các dữ liệu vào của bài toán. - Output: Các dữ liệu ra của bài toán (kết quả). 2/. Khái niệm thuật toán - ”Thuật toán” đƣợc hiểu đơn giản là cách thức để giải một bài toán. Cũng có thể đƣợc hiểu bằng hai quan niệm: Trực giác hay Hình thức nhƣ sau: + Quan niệm trực giác về ”Thuật toán” Một cách trực giác, thuật toán đƣợc hiểu là một dãy hữu hạn các qui tắc (chỉ thị, mệnh lệnh) mô tả một quá trình tính toán, để từ dữ liệu đã cho (Input) ta nhận đƣợc kết quả (Output) của bài toán. + Quan niệm toán học về ”Thuật toán” Một cách hình thức, ngƣời ta quan niệm thuật toán là một máy Turing. - Thuật toán đƣợc chia thành hai loại: Đơn định và không đơn định. + Thuật toán đơn định (Deterministic): Là thuật toán mà kết quả của mọi phép toán đều đƣợc xác định duy nhất. + Thuật toán không đơn định (Non - deterministic): Là thuật toán có ít nhất một phép toán mà kết quả của nó là không duy nhất. 18 1.1.3.2. Khái niệm độ phức tạp của thuật toán 1/. Chi phí của thuật toán (tính theo một bộ dữ liệu vào) Chi phí phải trả cho một quá trình tính toán gồm chi phí về thời gian và bộ nhớ. - Chi phí thời gian của một quá trình tính toán là thời gian cần thiết để thực hiện một quá trình tính toán. Với thuật toán tựa Algol: Chi phí thời gian là số các phép tính cơ bản thực hiện trong quá trình tính toán . - Chi phí bộ nhớ của một quá trình tính toán là số ô nhớ cần thiết để thực hiện một quá trình tính toán. Gọi A là một thuật toán, e là dữ liệu vào của bài toán đã đƣợc mã hoá bằng cách nào đó. Thuật toán A tính trên dữ liệu vào e phải trả một giá nhất định. Ta ký hiệu: tA (e) là giá thời gian và lA(e) là giá bộ nhớ. 2/. Độ phức tạp về bộ nhớ (trong trƣờng hợp xấu nhất) lA(n) = max{l A (e), với |e|  n}. (n là kích thƣớc đầu vào của thuật toán) 3/. Độ phức tạp thời gian (trƣờng hợp xấu nhất) tA(n) = max{tA(e), với |e|  n} 4/. Độ phức tạp tiệm cận Độ phức tạp PT(n) đƣợc gọi là tiệm cận tới hàm f(n), ký hiệu O(f(n)) nếu  các số n0 , c mà PT(n)  c.f(n) , n  n0. 5/. Độ phức tạp đa thức Độ phức tạp PT(n) đƣợc gọi đa thức, nếu nó tiệm cận tới đa thức p(n). 6/. Thuật toán đa thức - Thuật toán đƣợc gọi là đa thức nếu độ phức tạp về thời gian trong trƣờng hợp xấu nhất của nó là đa thức. - Nói cách khác: + Thuật toán thời gian đa thức: là thuật toán có độ phức tạp là O(nt) trong đó t là hằng số. + Thuật toán thời gian hàm mũ: là thuật toán có độ phức tạp O(tf(n)) trong đó t là hằng số và f(n) là hàm đa thức của n. 19 - Thời gian chạy của các lớp thuật toán khác nhau: Bảng 3: Thời gian chạy của các lớp thuật toán khác nhau Độ phức tạp Số phép tính(n=106) Thời gian(106phép tính/s) O(1) 1 1micro giây O(n) 10 6 1 giây O(n 2 ) 10 12 11,6 ngày O(n 3 ) 10 18 32 000 năm O(2 n ) 10 301030 10 301006 tuổi của vũ trụ - Có ngƣời cho rằng ngày nay máy tính với tốc độ rất lớn, không cần quan tâm nhiều tới thuật toán nhanh, chúng tôi xin dẫn một ví dụ đã đƣợc kiểm chứng. Bài toán xử lý n đối tƣợng, có ba thuật toán với 3 mức phức tạp khác nhau sẽ chịu 3 hậu quả nhƣ sau: Sau 1 giờ: + Thuật toán A có độ phức tạp O(n): 3,6 triệu đối tƣợng. + Thuật toán B có độ phức tạp O(nlog n): 0,2 triệu đối tƣợng. + Thuật toán C có độ phức tạp O(2n): 21 đối tƣợng. 1.1.3.3. Phân lớp bài toán theo độ phức tạp 1/. Các khái niệm - Khái niệm "Dẫn về được" Bài toán B đƣợc gọi là "Dẫn về đƣợc” bài toán A một cách đa thức, ký hiệu: B  A, nếu có thuật toán đơn định đa thức để giải bài toán A thì cũng có thuật toán đơn định đa thức để giải bài toán B. Nghĩa là: Bài toán A "khó hơn" bài toán B, hay B "dễ” hơn A, B đƣợc diễn đạt bằng ngôn ngữ của bài toán A, hay có thể hiểu B là trƣờng hợp riêng của A. Vậy nếu giải đƣợc bài toán A thì cũng sẽ giải đƣợc bài toán B. Quan hệ  có tính chất bắc cầu: Nếu C  B và B  A thì C  A. - Khái niệm "Khó tương đương" Bài toán A gọi là “khó tƣơng đƣơng” bài toán B, ký hiệu A ~ B, nếu AB và BA 20 2/. Phân lớp các bài toán - Cho một bài toán, có 2 khả năng xảy ra: + Đã có lời giải + Chƣa có lời giải - Cho một bài toán đã có lời giải, có 2 khả năng xảy ra: + Giải đƣợc bằng thuật toán + Không giải đƣợc bằng thuật toán - Cho một bài toán giải đƣợc bằng thuật toán, cũng chia thành 2 loại: + Thực tế giải đƣợc: hiểu là nó có thể giải đƣợc bởi thuật toán, xử lý trong thời gian đủ nhanh, thực tế cho phép, đó là thuật toán có độ phức tạp thời gian là “đa thức”. Bài toán này thuộc loại “dễ giải”. + Thực tế khó giải: hiểu là nó chỉ có thể giải đƣợc bởi thuật toán, xử lý trong nhiều thời gian, thực tế khó chấp nhận, đó là thuật toán có độ phức tạp thời gian là trên đa thức (“hàm mũ”). Bài toán này thuộc loại “khó giải”. 1.1.3.4. Hàm một phía và hàm cửa sập một phía - Hàm f(x) đƣợc gọi là hàm một phía nếu tính y = f(x) thì “dễ”, nhƣng tính x = f -1 (y) lại rất “khó”. Ví dụ: Hàm f(x) = x (mod p), với p là số nguyên tố lớn, ( là phần tử nguyên thuỷ mod p) là hàm một phía. - Hàm f(x) đƣợc gọi là hàm cửa sập một phía nếu tính y = f(x) thì “dễ”, nhƣng tính x = f -1(y) lại rất “khó”. Tuy nhiên có cửa sập z để tính x = f -1(y) là “dễ”. Ví dụ: Hàm y = f(x) = xa (mod n) (với n là tích của hai số nguyên tố lớn n = p*q) là hàm một phía. Nếu chỉ biết a và n thì tính x = f-1(y) = 𝑦𝑏 𝑚𝑜𝑑 𝑛 ( b thỏa mãn ab ≡ 1 𝑚𝑜𝑑 𝛷(𝑛)) rất khó nhƣng nếu biết cửa sập p và q thì tính đƣợc f-1(y) là khá dễ. 21 1.2. MÃ HÓA 1.2.1. Khái niệm mã hóa dữ liệu Để bảo đảm an toàn thông tin lƣu trữ trong máy tính (ví dụ: giữ gìn thông tin cố định) hay bảo đảm an toàn thông tin trên đƣờng truyền tin (ví dụ: trên mạng máy tính, điện thoại), ngƣời ta phải “che giấu” các thông tin này. - “Che” thông tin (dữ liệu) hay “Mã hóa” thông tin là thay đổi hình dạng thông tin gốc, và ngƣời khác “khó” nhận ra. Nói cách khác “Mã hóa” thông tin là “che” đi “ý nghĩa” của thông tin, và ngƣời khác “khó” hiểu đƣợc (“khó” đọc đƣợc) thông tin đã mã hoá. - “Giấu” thông tin (dữ liệu) là cất giấu thông tin trong bản tin khác, và ngƣời khác cũng “khó” nhận ra. Việc mã hoá phải theo quy tắc nhất định, quy tắc đó gọi là hệ mã hóa. 1.2.1.1. Hệ mã hóa Hệ mã hóa đƣợc định nghĩa là bộ năm (P, C, K, E, D), trong đó: P là tập hữu hạn các bản rõ có thể. C là tập hữu hạn các bản mã có thể. K là tập hữu hạn các khoá có thể. E là tập các hàm lập mã. D là tập các hàm giải mã. Với khóa lập mã ke  K, có hàm lập mã eke  E, eke: P C, Với khóa giải mã kd  K, có hàm giải mã dkd  D, dkd: C P sao cho dkd (eke (T)) = T, T  P. Ở đây T đƣợc gọi là bản rõ, eke (T) đƣợc gọi là bản mã. 1.2.1.2. Mã hóa và giải mã Ngƣời gửi G (có khóa lập mã ke)  eke (T)  Ngƣời nhận N (có khóa giải mã kd)  Tin tặc có thể trộm bản mã eke (T) 22 Ngƣời gửi G muốn gửi bản tin T cho ngƣời nhận N. Để bảo đảm bí mật, G mã hoá bản tin bằng khóa lập mã ke, thu đƣợc bản mã eke (T), sau đó gửi cho N. Tin tặc có thể trộm bản mã eke (T), nhƣng cũng “khó” hiểu đƣợc bản tin gốc T nếu không có khoá giải mã kd. Ngƣời N nhận đƣợc bản mã, họ dùng khoá giải mã kd, để giải mã eke (T), sẽ nhận đƣợc bản tin gốc T = dkd (eke (T)). 1.2.2. Phân loại hệ mã hóa Hiện nay có hai loại mã hóa chính: Mã hóa khóa đối xứng và Mã hóa khoá công khai. - Mã hóa khóa đối xứng: là hệ mã hóa có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia, vì vậy cần phải giữ bí mật cả 2 khóa. - Mã hóa khóa công khai: là hệ mã hóa có khóa lập mã khác khóa giải mã (ke  kd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Vì thế khóa giải mã cần phải đƣợc giữ bí mật, khóa lập mã đƣợc công khai. 1.2.2.1. Hệ mã hóa khóa đối xứng Mã hóa khóa đối xứng là hệ mã hóa có khóa lập mã và khóa giải mã “giống nhau”, theo nghĩa biết đƣợc khóa này thì “dễ” tính đƣợc khóa kia. Đặc biệt một số hệ mã hóa loại này có khoá lập mã và khoá giải mã trùng nhau (ke = kd). Hệ mã hóa khóa đối xứng còn có tên gọi là Hệ mã hóa khoá bí mật, vì phải giữ bí mật cả 2 khóa. Trƣớc khi dùng hệ mã hóa khóa đối xứng, ngƣời gửi và ngƣời nhận phải thoả thuận thuật toán mã hóa và một khoá chung (lập mã hay giải mã), khoá này phải đƣợc giữ bí mật. Độ an toàn của hệ mã hóa loại này phụ thuộc vào khoá. Ví dụ - Hệ mã hóa cổ điển thuộc loại mã hóa khóa đối xứng: dễ hiểu, dễ thực thi, nhƣng có độ an toàn không cao. Vì giới hạn tính toán chỉ trong phạm vi bảng chữ cái, sử dụng trong bản tin cần mã, ví dụ là Z26 nếu dùng các chữ cái tiếng Anh, là Z256 nếu dùng bảng mã ASCII . . . Với hệ mã hóa cổ điển, nếu biết khoá lập mã hay thuật toán lập mã, ngƣời ta có thể “dễ” xác định đƣợc bản rõ, vì “dễ” tìm đƣợc khoá giải mã. - Hệ mã hóa DES(1973) là mã hóa khóa đối xứng hiện đại, có độ an toàn cao ( [1], [2] ) . 23 1/. Các đặc điểm của hệ mã hóa khóa đối xứng - Ƣu điểm: + Mã hóa khóa đối xứng mã hóa và giải mã nhanh hơn mã hóa khóa công khai. - Hạn chế: + Mã hóa khóa đối xứng chƣa thật an toàn vì: Ngƣời mã hoá và ngƣời giải mã phải có “chung” một khoá. Khóa phải đƣợc giữ bí mật tuyệt đối, vì “dễ” xác định khoá này nếu biết khoá kia. Khi hai ngƣời (lập mã, giải mã) cùng biết “chung” một bí mật, thì khó giữ đƣợc bí mật ! + Vấn đề thỏa thuận khoá và quản lý khóa chung là khó khăn và phức tạp. Ngƣời gửi và ngƣời nhận phải luôn thống nhất với nhau về khoá. Việc thay đổi khoá là rất khó và dễ bị lộ. Khóa chung phải đƣợc gửi cho nhau trên kênh an toàn. + Không thể tạo ra chữ ký số. 2/. Phạm vi áp dụng hệ mã hóa đối xứng - Hệ mã hóa khóa đối xứng thƣờng đƣợc sử dụng trong môi trƣờng mà khoá chung có thể dễ dàng trao chuyển bí mật, chẳng hạn trong cùng một mạng nội bộ. - Hệ mã hóa khóa đối xứng dùng để mã hóa những bản tin lớn, vì tốc độ mã hóa và giải mã nhanh hơn hệ mã hóa khóa công khai. 1.2.2.2. Hệ mã hóa khóa công khai Hệ mã hóa khoá công khai do Diffie và Hellman phát minh vào những năm 1970. Mã hóa khóa công khai là hệ mã hóa có khóa lập mã và khóa giải mã khác nhau (ke  kd), biết đƣợc khóa này cũng “khó” tính đƣợc khóa kia. Hệ mã hóa này đƣợc gọi là hệ mã hoá khóa công khai, vì: - Khoá lập mã cho công khai, gọi là khoá công khai (public key). - Khóa giải mã giữ bí mật, còn gọi là khóa riêng (private key). - Một ngƣời bất kỳ có thể dùng khoá công khai để mã hoá bản tin, nhƣng chỉ ngƣời nào có đúng khoá giải mã tƣơng ứng thì mới có khả năng xem đƣợc bản rõ. 24 1/. Các đặc điểm của hệ mã khoá công khai - Ƣu điểm: + Ngƣời mã hoá dùng khóa công khai, ngƣời giải mã giữ khóa bí mật. Vì thế khả năng lộ khóa bí mật khó hơn do khóa bí mật chỉ có một ngƣời giữ. + Nếu kẻ phá hoại biết khoá công khai, cố gắng tìm khoá bí mật thì chúng phải đƣơng đầu với bài toán “khó”. + Khi biết các tham số ban đầu của hệ mã hóa, việc tính ra cặp khoá công khai và bí mật là “dễ”, tức là trong thời gian đa thức. Ngƣời gửi có bản rõ P và khoá công khai, thì “dễ” tạo ra bản mã C. Ngƣời nhận có bản mã C và khoá bí mật, thì “dễ” giải đƣợc thành bản rõ P. + Nếu kẻ phá hoại biết khoá công khai và bản mã C, thì việc tìm ra bản rõ P cũng là bài toán “khó”, số phép thử là vô cùng lớn, không khả thi. + Hệ mã hóa khóa công khai còn tiện lợi hơn Hệ mã hóa khóa đối xứng bởi vì: Thuật toán đƣợc viết một lần, công khai cho nhiều lần dùng và cho nhiều ngƣời dùng, chỉ cần giữ bí mật khóa riêng. - Hạn chế: + Mã hóa khóa công khai mã hóa và giải mã chậm hơn mã hóa khóa đối xứng. 2/. Phạm vi áp dụng hệ mã hóa khoá công khai - Hệ mã hóa khóa công khai đƣợc sử dụng chủ yếu trên các mạng công khai nhƣ Internet, khi mà việc trao chuyển khoá bí mật tƣơng đối khó khăn. Đặc trƣng nổi bật của hệ mã hoá công khai là cả khoá công khai (public key) và bản mã (ciphertext) đều có thể gửi đi trên một kênh truyền tin không an toàn. 25 1.3. KÝ SỐ 1.3.1. Khái niệm chữ ký số 1.3.1.1. Sơ đồ chữ ký số Sơ đồ chữ ký số là bộ năm (P, A, K, S, V ), trong đó: P là tập hữu hạn các văn bản có thể. A là tập hữu hạn các chữ ký có thể. K là tập hữu hạn các khoá có thể. S là tập các thuật toán ký. V là tập các thuật toán kiểm thử. Với mỗi k  K, có thuật toán ký sigk  S, sigk : P A, và thuật toán kiểm thử Verk  V, Verk : P  A đúng, sai, thoả mãn điều kiện sau với mọi xP, y A: Đúng, nếu y = sig k(x) Verk (x, y) = Sai, nếu y ≠ sigk (x) 1.3.2. Phân loại chữ ký số Có nhiều loại chữ ký tùy theo cách phân loại, sau đây xin giới thiệu một số cách. 1.3.2.1. Phân loại chữ ký theo đặc trưng kiểm tra chữ ký 1/. Chữ ký khôi phục thông điệp Là loại chữ ký, trong đó ngƣời gửi chỉ cần gửi “chữ ký”, ngƣời nhận có thể khôi phục lại đƣợc thông điệp, đã đƣợc “ký” bởi “chữ ký” này. Ví dụ: Chữ ký RSA là chữ ký khôi phục thông điệp, sẽ trình bày trong mục sau. 2/. Chữ ký không thể khôi phục đƣợc thông điệp (đi kèm thông điệp) Là loại chữ ký, trong đó ngƣời gửi cần gửi “chữ ký” và phải gửi kèm cả thông điệp đã đƣợc “ký” bởi “chữ ký” này. Ngƣợc lại, ngƣời nhận sẽ không có đƣợc thông điệp gốc. Ví dụ: Chữ ký Elgamal là chữ ký đi kèm thông điệp (xem [1],[2]). 26 1.3.2.2. Phân loại chữ ký theo mức an toàn 1/. Chữ ký “không thể phủ nhận” Nhằm tránh việc nhân bản chữ ký để sử dụng nhiều lần, tốt nhất là ngƣời gửi tham gia trực tiếp vào việc kiểm thử chữ ký. Điều đó đƣợc thực hiện bằng một giao thức kiểm thử, dƣới dạng một giao thức mời hỏi và trả lời. Ví dụ: Chữ ký không thể phủ định Chaum - van Antwerpen, sẽ trình bày trong mục sau. 2/. Chữ ký “một lần” Để bảo đảm an toàn, “Khóa ký” chỉ dùng 1 lần (one- time) trên 1 tài liệu. Ví dụ: Chữ ký Lamport [15], chữ ký Fail - Stop (Van Heyst & Pedersen) [7]. 1.3.3. So sánh chữ ký thông thƣờng và chữ ký số Chữ ký thông thƣờng (tức chữ ký viết tay) đƣợc dùng rất phổ biến trong các công việc hàng ngày, nhƣ viết thƣ, rút tiền từ ngân hàng, ký hợp đồng,... Chữ ký đƣợc sử dụng nhƣ là bằng chứng để xác định ngƣời ký tài liệu là ai và khẳng định ngƣời ký đã chấp nhận hay chịu trách nhiệm về nội dung đƣợc đề cập trong tài liệu. Vì vậy, một chữ ký phải có các thuộc tính sau: - Chữ ký phải có tính tin cậy (xác thực). - Chữ ký không thể giả mạo đƣợc: chữ ký chứng minh chỉ có ngƣời ký đã ký tài liệu một cách chủ định mà không có ai khác. - Chữ ký không thể đƣợc dùng lại: chữ ký phải là một phần của tài liệu và không thể chuyển chữ ký sang tài liệu khác. - Tài liệu đã ký không thể thay đổi đƣợc, tức là không thể sửa đổi tài liệu sau khi ký. - Chữ ký không thể chối bỏ: sau khi ký, ngƣời ký không thể phủ nhận chữ ký mà anh ta đã ký. Trong thời đại bùng nổ công nghệ thông tin ngày nay, hầu nhƣ các hoạt động, giao dịch đều đƣợc thực hiện qua mạng máy tính. Vì vậy, thay vì sử dụng tài liệu giấy với chữ ký viết tay ngƣời ta sử dụng tài liệu điện tử với chữ ký số . Về hình thức, chữ ký số hoàn toàn khác với chữ ký thông thƣờng nhƣng vẫn đảm bảo các thuộc tính của chữ ký nhƣ: tính tin cậy (xác thực), tính không thể giả mạo, tính không thể dùng lại, tính không thể thay đổi, tính không thể chối bỏ. Về mặt thuộc tính chữ ký số và chữ ký 27 thông thƣờng đều có những thuộc tính giống nhau nhƣng về mặt vật lý và cấu trúc có những khác biệt rõ rệt. - Thứ nhất, chữ ký thông thƣờng là một phần vật lý của tài liệu đƣợc ký. Tuy nhiên, chữ ký số không gắn vào thông điệp đƣợc ký nhƣ chữ ký thông thƣờng, vì thế thuật toán ký phải liên kết giữa chữ ký và thông điệp đƣợc ký. - Thứ hai, thẩm định chữ ký thông thƣờng thực hiện bằng cách so sánh nó với chữ ký khác (chữ ký tin cậy). Trái lại, thẩm định chữ ký số dùng thuật toán kiểm tra công khai. Do đó, bất kỳ ai cũng có thể thẩm định. Sử dụng sơ đồ chữ ký an toàn sẽ ngăn chặn đƣợc khả năng giả mạo. - Một sự khác biệt nữa giữa chữ ký số và chữ ký thông thƣờng, bản sao của thông điệp số đã ký hoàn toàn giống với bản gốc. Ngƣợc lại, vẫn có thể phân biệt đƣợc bản sao của tài liệu giấy đã ký và bản gốc. Vì thế, phải ngăn chặn việc sử dụng lại thông điệp số đã ký khi quá hạn sử dụng bằng cách thêm thông tin thời gian khi thông điệp đƣợc ký. 1.3.4. Tạo đại diện tài liệu và hàm băm 1.3.4.1. Một số vấn đề với chữ ký số 1/. Vấn đề 1 Ký số thực hiện trên từng bit tài liệu, nên độ dài của chữ ký số ít nhất cũng bằng độ dài của tài liệu. Một số chữ ký trên bản tin có kích thƣớc gấp đôi bản tin gốc. Ví dụ khi dùng sơ đồ chữ ký số DSS để ký vào bản tin có kích thƣớc 160 bit, thì chữ ký số này sẽ có kích thƣớc 320 bit.Trong khi đó trên thực tế, ta cần phải ký vào các bản tin có kích thƣớc rất lớn, ví dụ vài chục MegaByte ( tƣơng ứng hàng ngàn trang tin trên giấy ). Nhƣ vậy phải tốn nhiều bộ nhớ để lƣu trữ “chữ ký”, mặt khác tốn nhiều thời gian để truyền “chữ ký” trên mạng. 2/. Vấn đề 2 Với một số sơ đồ chữ ký “an toàn” thì tốc độ ký lại chậm vì chúng dùng nhiều phép tính số học phức tạp nhƣ số mũ modulo. 3/. Vấn đề 3 Thực tế có thể xảy ra trƣờng hợp: với nhiều bản tin đầu vào khác nhau, sử dụng hệ mã hóa hay sơ đồ ký giống nhau ( có thể khác nhau ) nhƣng lại cho ra bản mã hay chữ ký giống nhau ( ánh xạ nhiều – một ). Điều này sẽ dẫn đến phức tạp cho việc xác thực thông tin. 28 1.3.4.2. Cách giải quyết các vấn đề trên 1/. Cách 1 - Một cách đơn giản để giải quyết các vấn đề trên với thông điệp có kích thƣớc lớn là “ chặt ” bản tin thành nhiều đoạn nhỏ (Ví dụ các đoạn 160 bit ), sau đó ký lên các đoạn đó độc lập nhau. Nhƣng biện pháp này vẫn không giải quyết đƣợc vấn đề nêu trên. - Hơn thế nữa còn gặp vấn đề nghiêm trọng hơn. Đó là kết quả sau khi ký, nội dung của thông điệp có thể bị xáo trộn các đoạn với nhau, hoặc một số đoạn trong chúng có thể bị mất mát. Ta cần phải bảo vệ tính toàn vẹn của bản tin gốc. 2/. Cách 2 - Thay vì phải ký trực tiếp trên tài liệu dài, ngƣời ta thƣờng dùng “hàm băm” để tạo “đại diện” cho tài liệu, sau đó ký số lên “đại diện” này. - Các tài liệu (bản tin) có thể dƣới dạng văn bản, hình ảnh, âm thanh,… và kích thƣớc của chúng tùy ý (vài KB đến vài chục MB), qua các thuật toán băm nhƣ MD4, MD5, SHA,…các đại diện tƣơng ứng của chúng có kích thƣớc cố định, ví dụ 128 bit với dòng MD, 160 bit với dòng SHA. - Đại diện của tài liệu chính là giá trị của “hàm băm” trên tài liệu, nó còn đƣợc gọi là “tóm lƣợc” hay “bản thu gọn” của tài liệu. - Với mỗi tài liệu ( đầu vào ), qua hàm băm chỉ có thể tính ra đƣợc một “đại diện” với giá trị băm tƣơng ứng - duy nhất. “Đại diện” của tài liệu đƣợc xem là “đặc thù” của tài liệu ( thông điệp ), giống nhƣ dấu vân tay của mỗi ngƣời. - Trên thực tế, hai tài liệu khác nhau có hai “đại diện” khác nhau. Nhƣ vậy khi đã có “đại diện” duy nhất cho tài liệu, thì việc “ký” vào tài liệu, đƣợc thay bằng ký vào đại diện của nó là hoàn toàn hợp lý. Đó là chƣa kể việc tiết kiệm thời gian cho việc ký số, bộ nhớ lƣu giữ “chữ ký”, thời gian truyền “chữ ký” trên mạng. 1.3.4.3. Tổng quan về hàm băm 1/. Khái niệm hàm băm Hàm băm là thuật toán không dùng khóa để mã hóa ( ở đây dùng thuật ngữ “băm” thay cho “mã hóa” ), nó có nhiệm vụ “lọc” ( băm ) tài liệu và cho kết quả là một giá trị “băm” có kích thƣớc cố định, còn gọi là “đại diện tài liệu” hay “đại diện thông điệp”. 29 Hàm băm là “hàm một chiều”, theo nghĩa giá trị của hàm băm là duy nhất, và từ giá trị băm này khó có thể suy ngƣợc lại nội dung hay độ dài ban đầu của tài liệu gốc. 2/. Đặc tính của hàm băm Hàm băm h là hàm một chiều với các đặc tính sau: - Với tài liệu đầu vào (bản tin gốc) x, chỉ thu đƣợc giá trị băm duy nhất z = h(x). - Nếu dữ liệu trong bản tin x bị thay đổi hay bị xóa để thành bản tin x’ thì giá trị băm h(x’) ≠ h(x). - Cho dù chỉ là một sự thay đổi nhỏ, ví dụ chỉ thay đổi 1 bit dữ liệu của bản tin gốc x, thì giá trị băm h(x) của nó cũng vẫn thay đổi. Điều này có nghĩa là: hai thông điệp khác nhau thì giá trị băm của chúng cũng khác nhau. - Nội dung của bản tin gốc khó thể suy ra từ giá trị hàm băm của nó. Nghĩa là: với thông điệp x thì dễ tính đƣợc z = h(x) nhƣng lại khó tính ngƣợc lại đƣợc x nếu chỉ biết giá trị băm h(x) ( kể cả khi biết hàm băm h ). 3/. Ứng dụng của hàm băm - Với bản tin dài x, thì chữ ký trên x cũng sẽ dài, nhƣ vậy tốn thời gian ký, tốn bộ nhớ lƣu giữ chữ ký, tốn thời gian truyền chữ ký trên mạng. Ngƣời ta dùng hàm băm h để tạo đại diện bản tin z = h(x), nó có độ dài ngắn ( Ví dụ 128 bit ). Sau đó ký trên z, nhƣ vậy chữ ký trên z sẽ nhỏ hơn rất nhiều so với chữ ký trên bản tin gốc x. - Hàm băm dùng để xác định tính toàn vẹn dữ liệu. 4/. Các tính chất của hàm băm - Tính chất 1: Hàm băm h là không va chạm yếu. Hàm băm h đƣợc gọi là không va chạm yếu nếu cho trƣớc bức điện x, khó thể tính toán để tìm ra bức điện x’ ≠ x mà h(x’) = h(x) - Tính chất 2: Hàm băm h là không va chạm mạnh. Hàm băm h đƣợc gọi là không va chạm mạnh nếu khó thể tính toán để tìm ra hai bức thông điệp khác nhau x’ và x ( x’ ≠ x ) mà có h(x’) = h(x) - Tính chất 3: Hàm băm h là hàm một chiều Hàm băm h đƣợc gọi là hàm một chiều nếu khi cho trƣớc một bản tóm lƣợc thông báo z thì khó thể tính toán để tìm ra thông điệp ban đầu x sao cho h(x) = z. 30 Chương 2. CHỮ KÝ MÙ RSA 2.1. KHÁI NIỆM CHỮ KÝ MÙ Chữ ký mù đƣợc David Chaum giới thiệu vào năm 1983, nó là một loại chữ ký số, trong đó nội dung của thông điệp cần đƣợc ký bị “che” đi trƣớc khi nó đƣợc ký. Chữ ký thu đƣợc có thể đƣợc xác thực nhƣ là đối với chữ ký số thông thƣờng. Chữ ký mù thƣờng đƣợc dùng trong các vấn đề đòi hỏi sự nặc danh nhƣ trong các ứng dụng tiền điện tử, bỏ phiếu điện tử,…. Chữ ký mù là chữ ký mà ngƣời ký không biết mình đang ký trên nội dung gì. Vì vậy mà ngƣời ta gọi là “mù”. Làm đƣợc nhƣ vậy vì nội dung X trƣớc khi đƣa cho ngƣời ký đã đƣợc làm mù thành X’. Ngƣời ký ký trên X’ chứ không phải ký trên X. A cần B ký cho một chữ ký trên nội dung X, A không đƣa X cho B ký mà làm mù X thành X’. Sau đó A đƣa X’ cho B ký. Sau khi nhận đƣợc chữ ký trên X’, A xóa mù để thu đƣợc chữ ký trên X. Nhƣ vậy A vẫn có chữ ký trên X mà B không biết thông tin gì về X. 2.1.1. Sơ đồ chữ ký RSA 1/. Sơ đồ - Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật 2 số nguyên tố lớn p, q, tính n = p * q, công khai n, đặt P = A = Zn Tính bí mật (n) = (p-1).(q-1). Chọn khóa công khai b < (n), nguyên tố cùng nhau với (n). Khóa bí mật a là phần tử nghịch đảo của b theo mod (n): a*b  1 (mod (n)). Tập cặp khóa (bí mật, công khai) K = (a, b)/ a, b  Zn , a*b  1 (mod (n)). - Ký: Chữ ký trên x  P là y = Sigk (x) = x a (mod n), y  A. - Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n). 31 2/. Ví dụ - Tạo cặp khóa (bí mật, công khai) (a, b) : Chọn bí mật số nguyên tố p = 3, q = 5, tính n = p * q = 3*5 = 15, công khai n. Đặt P = A = Zn . Tính bí mật (n) = (p-1).(q-1) = 2 * 4 = 8. Chọn khóa công khai b = 3 < (n), nguyên tố với (n) = 8. Khóa bí mật a = 3, là phần tử nghịch đảo của b theo mod (n): a * b  1 (mod (n). - Ký số: Chữ ký trên x = 2  P là y = Sig k (x) = x a (mod n)= 2 3 (mod 15) = 8, y  A. - Kiểm tra chữ ký: Verk (x, y) = đúng  x  y b (mod n)  2  8 3 (mod 15). 2.1.2. Sơ đồ chữ ký mù RSA 1/. Sơ đồ Mục đích là ông A có đƣợc chữ ký của bà B trên văn bản x theo sơ đồ chữ ký RSA nhƣng không để cho B biết giá trị x thực sự. Chữ ký đó là giá trị xa mod n. Lúc này A và B phải thực hiện một số bƣớc sau: - A làm mù x ( che x ) thành u: u = Blind(x) = x.r b (mod n) , với n và b đƣợc lấy từ khóa công khai của B, r là ngẫu nhiên  Zn và r nguyên tố cùng nhau với n. ( r phải nguyên tố cùng nhau với n để tồn tại phần tử nghịch đảo r-1 mod n ) - A gửi u cho B, B ký trên u, đƣợc chữ ký là v = Sig(u) sau đó gửi lại cho A: v = Sig(Blind(x)) = Sig( x*r b ) = x a . (r b ) a (mod n) - A xóa mù trên v, sẽ nhận đƣợc chữ ký trên x z = Unblind(v) = v/r mod n = x a . (r b ) a / r (mod n) = x a .r/r mod n = x a mod n Nhƣ vậy A đã nhận đƣợc chữ ký của B: xa mod n, mà B không biết nội dung của văn bản x. Bởi vì nội dung của thông điệp x đã đƣợc làm mù thành u thông qua việc nhân với rb, cho dù b là số công khai lấy từ B, nhƣng r là số ngẫu nhiên mà B khó có thể biết đƣợc. Sau khi B ký xong, A xóa mù ( nhân với r-1) chữ ký trên u để nhận đƣợc chữ ký của B trên x. 32 2.1.3. Ví dụ minh họa Sơ đồ chữ ký mù RSA với K = ( n, p, q, r, b, a ) trong đó: p = 3, q = 5, n = p * q = 15 (n) = ( p -1 ) * (q – 1 ) = 8 Chọn khóa công khai b = 3 < (n), nguyên tố cùng nhau với (n). Khóa bí mật a là phần tử nghịch đảo của b theo mod (n): a = 3. Giả sử thông điệp cần ký là x = 2. - Ông A chọn số ngẫu nhiên r = 4 nguyên tố cùng nhau với n. A che dấu định danh x bằng bí danh u: u = Blind(x) = x.r b (mod n) = 2 * 4 3 (mod 15) = 8. - A gửi bí danh u cho B, nhận đƣợc chữ ký v: v = Sig(u) = u a mod n = 8 3 ( mod 15) = 2 - Sau khi nhận đƣợc v, A xóa mù trên v sẽ nhận đƣợc chữ ký trên định danh x: Unblind(v) = v * 𝑟−1 mod n = 2 * 4-1 ( mod 15) = 8. 33 2.2. ỨNG DỤNG CHỮ KÝ MÙ 2.2.1. Ứng dụng trong tiền điện tử 2.2.1.1. Giao thức dùng tiền điện tử Trong [3], tác giả Trịnh Nhật Tiến đã trình bày giao thức cơ bản của Chaum để thực hiện việc dùng tiền điện tử bằng một minh họa đơn giản, trong đó ngƣời mua hàng là Alice muốn mua một quyển sách với giá 100$ từ một ngƣời bán hàng trực tuyến. Cả Alice và ngƣời bán sách cùng sử dụng một dịch vụ của một ngân hàng. Giao dịch đƣợc thực hiện nhƣ sau: 1/. Rút tiền + Alice tạo đồng tiền điện tử C bao gồm một chuỗi các bit để xác định một vài thông tin nhƣ số seri và giá trị của C ( trong trƣờng hợp này là 100$ ). + Ngân hàng ký mù lên đồng tiền C. + Ngân hàng trừ 100$ trong tài khoản của Alice. 2/. Tiêu tiền + Alice yêu cầu cuốn sách cần mua, Alice chuyển đồng tiền C (đã có chữ ký của ngân hàng) cho ngƣời bán hàng. + Ngƣời bán hàng kiểm tra sự hợp lệ của đồng tiền C bằng cách xác thực chữ ký (sử dụng khóa công khai của ngân hàng). Nếu chữ ký không hợp lệ thì ngƣời bán hàng kết thúc giao thức. 3/. Gửi tiền + Ngƣời bán hàng lấy đồng tiền C (đã nhận đƣợc từ Alice) gửi cho ngân hàng. + Ngân hàng xác thực chữ ký trên đồng tiền C. Nếu chữ ký hợp lệ thì ngân hàng sẽ kiểm tra xem đồng tiền C đã đƣợc tiêu chƣa. Nếu C chƣa đƣợc tiêu trƣớc đó thì ngân hàng sẽ cộng thêm vào tài khoản của ngƣời bán 100$. + Sau khi nhận tiền, ngƣời bán hàng gửi sách cho Alice. Trong trƣờng hợp này ngƣời bán hàng khó thể biết đồng tiền C đó từ tài khoản nào, hơn thế nữa, khi ngƣời bán hàng gửi tiền C vào tài khoản của mình, ngân hàng cũng khó thể biết đồng tiền đó nhận từ Alice vì nó đƣợc ký mù. 34 2.2.1.2. Vấn đề phát sinh khi dùng chữ ký mù Vấn đề có thể xảy ra đối với việc ký mù vào đồng tiền điện tử. Ví dụ Alice gửi cho ngân hàng một đồng tiền không trung thực và yêu cầu ký. Rất có thể Alice làm tờ tiền $1000 nhƣng lại khai báo với ngân hàng là $100 nhƣng khi ký mù thì không biết đƣợc số lƣợng tiền trong đồng tiền do nó đã bị làm mù. Trong [3] đã trình bày hai cách giải quyết vấn đề trên: 1/. Cách 1 Ngân hàng sử dụng các khóa ký (bí mật) khác nhau với các lƣợng tiền khác nhau. Theo đó, nếu Alice muốn lấy $1000 nhƣng khai báo với ngân hàng là $100, vì thế ngân hàng sẽ dùng khóa ký trên $100. ⇒ Khi kiểm tra chữ ký đồng tiền $1000 là không hợp lệ. 2/. Cách 2 Alice và ngân hàng có thể thực hiện một giao thức dựa vào xác suất. Đầu tiên Alice làm 10 tờ tiền ( c1, c2, …, c10 ), các tờ tiền này có mệnh giá giống nhau, chỉ khác nhau về số seri. Sau đó Alice làm mù tất cả các đồng tiền và gửi về cho ngân hàng. Ngân hàng chọn ngẫu nhiên 9 trong số 10 đồng tiền đó để yêu cầu Alice tiết lộ các thông tin xóa mù chúng. Ngân hàng xóa mù 9 đồng tiền này, nếu tất cả đều hợp lệ thì ngân hàng sẽ ký mù lên đồng tiền còn lại và gửi cho Alice. 2.2.2. Ứng dụng trong bỏ phiếu trực tuyến Trong [4], tác giả trình bày ứng dụng của chữ ký mù trong bỏ phiếu trực tuyến nhƣ sau: 2.2.2.1. Giao thức Theo phƣơng thức bỏ phiếu điện tử, mỗi lá phiếu phải có thông tin định danh. Nó có thể là số x nào đó và phải khác nhau. Mỗi lá phiếu phải có chữ ký trên định danh x thì lá phiếu mới có giá trị để bầu cử. Nếu cử tri CT chuyển định danh x cho Ban bầu cử ký, thì những thành viên trong ban bầu cử có thể xác định đƣợc mối quan hệ giữa cử tri và x ( Ví dụ qua địa chỉ nơi gửi trên Internet ). Đó là điều cử tri không muốn vì sợ rắc rối sau này. Vì thế, cử tri biến đổi x thành y trƣớc khi đƣa cho ban bầu cử ký xác nhận, Ban bầu cử ký vào y. Họ trao chữ ký trên y là z cho CT. Cử tri xóa mù trên z sẽ thu đƣợc chữ ký của Ban bầu cử trên định danh x, nhƣ vậy CT có quyền bầu cử. 35 Với kỹ thuật này, cuộc bỏ phiếu bảo đảm đƣợc: quyền bỏ phiếu và bí mật. Tức là: chỉ có ngƣời có quyền bầu cử mới đƣợc bỏ phiếu (vì lá phiếu đã có chữ ký của ban bầu cử ). 2.2.2.2. Vấn đề phát sinh khi dùng chữ ký mù Do ký mù trên lá phiếu nên ban bầu cử không ghi lại đƣợc định danh của cử tri. Do đó cử tri có thể xin nhiều lá phiếu để bỏ phiếu nhiều lần. Có thể giải quyết nhƣ sau: - Cử tri + Cử tri chọn bí mật số định danh x, “làm mù” thành y = blind(x) + Cử tri gửi tới ban bầu cử thông tin nhận dạng của mình, chứng minh thƣ điện tử, số y ( định danh x đã đƣợc làm mù thành y ). - Ban bầu cử + Ban bầu cử nhận dạng cử tri, kiểm tra chứng minh thƣ của cử tri. + Nếu hồ sơ của cử tri hợp lệ, khớp với danh sách cử tri của Ban điều hành, cử tri chƣa xin cấp chữ ký lần nào, thì ra lệnh cho Hệ thống “ký” lên y. Đó là chữ ký z = sign(y). + Ban bầu cử ghi số chứng minh thƣ của cử tri vào danh sách cử tri đã đƣợc cấp chữ ký ( để tránh việc cử tri đăng ký bỏ phiếu nhiều lần ). + Ban Bầu cử gửi chữ ký z về cho cử tri. - Cử tri + Khi nhận đƣợc chữ ký này, cử tri “xóa mù” trên z, thu đƣợc chữ ký trên định danh thật x là sign(x). Lá phiếu có gắn chữ ký sign(x) đƣợc xem nhƣ đã có chữ ký của ban bầu cử, đó là lá phiếu hợp lệ để cử tri ghi ý kiến của mình. + Cử tri có thể kiểm tra chữ ký của ban bầu cử trên lá phiếu của mình có hợp lệ hay không bằng cách dùng hàm kiểm tra chữ ký và khóa công khai của ban bầu cử. 36 Chương 3. CHỮ KÝ KHÔNG THỂ CHỐI BỎ 3.1. KHÁI NIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ Chữ ký số, không giống nhƣ chữ ký trên giấy, nó có thể dễ dàng bị sao chép một cách chính xác. Thuộc tính này có thể có lợi cho những ứng dụng cần sự phổ biến rộng rãi của các thông báo cùng với khóa công khai, khi mà càng nhiều bản sao chép đƣợc phát ra càng tốt. Tuy nhiên, nó không phù hợp với nhiều ứng dụng khác. Ví dụ ứng dụng chữ ký điện tử thay thế cho ứng dụng mang tính cá nhân hoặc nhạy cảm nhƣ bản cam kết viết tay hoặc bằng miệng. Trong những trƣờng hợp này, sự phổ biến của bản sao chép có thể làm cho ngƣời dùng không hợp lệ thực hiện các hành vi nhƣ tống tiền hoặc gián điệp. Ngƣời nhận của những cam kết này có thể chắc chắn rằng ngƣời ký cam kết này sau này không thể chối bỏ nó, nhƣng ngƣời nhận không thể đƣa ra bản cam kết này cho bất kỳ ai khác khi không có sự đồng thuận của ngƣời ký. Chữ ký không thể chối bỏ phù hợp với các ứng dụng nhƣ ở trên. Chữ ký không thể chối bỏ, giống nhƣ chữ ký số thông thƣờng, là một số đƣợc đƣa ra bởi ngƣời ký, phụ thuộc vào khóa bí mật của ngƣời ký và thông điệp cần ký. Tuy nhiên, không giống nhƣ chữ ký số thông thƣờng, kiểm tra chữ ký không thể chối bỏ phải có sự hợp tác của ngƣời ký. Tính hợp lệ của chữ ký không thể chối bỏ có thể đƣợc kiểm tra ( bởi bất kỳ ai) bằng cách đƣa ra các giá trị hỏi ( challenge ) cho ngƣời ký, và ngƣời ký sẽ đƣa ra các giá trị đáp lại (response). Nếu kiểm tra là sai, có hai trƣờng hợp xảy ra: (a) chữ ký là không hợp lệ hoặc (b) ngƣời ký cố tình đƣa ra các giá trị đáp sai để cố tình chối bỏ một chữ ký do anh ta ký. Tuy nhiên cho dù ngƣời ký có máy tính với năng lực tính toán vô hạn, ngƣời kiểm thử chữ ký có thể phân biệt đƣợc trƣờng hợp (a) và (b) với độ chắc chắn cao bằng giao thức hỏi đáp thứ hai. 3.1.1. Sơ đồ chữ ký không thể chối bỏ Chaum – Van Antwerpen Sơ đồ chữ ký không thể chối bỏ đƣợc David Chaum và Hans van Antwerpen đề xuất năm 1989. Sơ đồ gồm 3 phần: thuật toán ký, giao thức kiểm thử và giao thức chối bỏ. 1/. Chuẩn bị các tham số + Chọn số nguyên tố p sao cho bài toán logarit rời rạc trong 𝑍𝑝 là khó giải, đồng thời thỏa mãn điều kiện p = 2 * q + 1, q cũng là nguyên tố. + Chọn g ∈ 𝑍𝑝 ∗ là phần tử có cấp q. 37 + Chọn 1 ≤ a ≤ q – 1, tính h = 𝑔𝑎 mod p. + G là nhóm con (theo phép nhân) cấp q sinh ra bởi g của 𝑍𝑝 ∗ + Tập hữu hạn các văn bản có thể P, tập hữu hạn các chữ ký có thể A + P = A = G + Khóa công khai đƣợc định nghĩa pk = ( p, g, h ), khóa bí mật sk = a. 2/. Thuật toán ký Dùng khóa bí mật sk ở trên để ký lên thông điệp x, chữ ký là: y = sigsk( x ) = x a mod p 3/. Giao thức kiểm thử Bob muốn xác thực chữ ký y trên thông điệp x đƣợc ký bởi Alice. Giao thức đƣợc thực hiện nhƣ sau: - Bob chọn ngẫu nhiên 𝑒1, 𝑒2 ∈ 𝑍𝑞 ∗ - Bob tính c = 𝑦𝑒1𝑕𝑒2 mod p và gửi cho Alice. - Alice tính d = 𝑐𝑎 −1 mod q𝑚𝑜𝑑 𝑝 và gửi cho Bob. - Bob chấp nhận y là chữ ký đúng trên x khi và chỉ khi 𝑑 ≡ 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 4/. Giao thức chối bỏ chữ ký - Bob chọn ngẫu nhiên 𝑒1, 𝑒2 ∈ 𝑍𝑞 ∗ - Bob tính c = 𝑦𝑒1𝑕𝑒2 mod p và gửi cho Alice. - Alice tính d = 𝑐𝑎 −1 mod q𝑚𝑜𝑑 𝑝 và gửi cho Bob. - Bob kiểm tra 𝑑 ≢ 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 - Bob chọn ngẫu nhiên 𝑓1, 𝑓2 ∈ 𝑍𝑞 ∗ - Bob tính C = 𝑦𝑓1𝑕𝑓2mod p và gửi cho Alice3 - Alice tính D = 𝐶𝑎 −1 𝑚𝑜𝑑 𝑞𝑚𝑜𝑑 𝑝 và gửi cho Bob - Bob kiểm tra 𝐷 ≢ 𝑥𝑓1 g𝑓2𝑚𝑜𝑑 𝑝 - Bob kết luận chữ ký y thực sự là giả mạo nếu: (𝒅𝒈−𝒆𝟐)𝒇𝟏 ≡ (𝑫𝒈−𝒇𝟐)𝒆𝟏 𝑚𝑜𝑑 𝑝 38 3.1.2. Ví dụ minh họa Trong ví dụ này, Alice là ngƣời ký, Bob là ngƣời cần xin chữ ký. 1/. Chuẩn bị các tham số Alice chuẩn bị các tham số cho việc ký - Chọn số nguyên tố p = 59747 = 2 * q + 1, q = 29873 cũng là số nguyên tố - G là nhóm nhân con của 𝑍𝑝 ∗ cấp q. Chọn phần tử sinh của nhóm G là g = 3. - Đặt P = A = G, K = {(p, g, a, h ): a ∈ 𝑍𝑞 ∗, h ≡ 𝑔𝑎 mod p } Chọn a = 11, h = 311 mod 59747 = 57653 2/. Thuật toán ký Dùng khóa bí mật sk = a để ký lên x = 229 Chữ ký thu đƣợc là y = sigsk (x) = x a mod p = 229 11 mod 59747 = 30179. 3/. Giao thức kiểm thử chữ ký Dùng khóa công khai pk = ( p, g, h ) = ( 59747, 3, 57653 ) - Bob chọn ngẫu nhiên 𝑒1 = 11, 𝑒2 = 15 ∈ 𝑍𝑞 ∗ - Bob tính c = 𝑦𝑒1𝑕𝑒2mod p = 30179115765315mod 59747 = 55601 - Alice tính d = 𝑐𝑎 −1 mod q𝑚𝑜𝑑 𝑝 = 5560111 −1mod 29873𝑚𝑜𝑑 59747 = 43319 - Bob kiểm tra điều kiện 𝑑 ≡ 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 Có 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 = 22911315mod 59747 = 43319 ≡ 43319 mod 59747  Bob kết luận chữ ký là đúng. 4/. Giao thức chối bỏ chữ ký Giả sử Bob gửi tài liệu x = 229, với chữ ký y = 30178 - Bob chọn ngẫu nhiên 𝑒1 = 11, 𝑒2 = 15 ∈ 𝑍𝑞 ∗ - Bob tính c = 𝑦𝑒1𝑕𝑒2 mod p = 30178115765315 𝑚𝑜𝑑 59747 = 19071 - Alice tính d = 𝑐𝑎 −1mod q𝑚𝑜𝑑 𝑝 = 1907111 −1mod 29873𝑚𝑜𝑑 59747 = 33692 - Bob kiểm tra điều kiện 𝑑 ≡ 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 Có 𝑥𝑒1α𝑒2𝑚𝑜𝑑 𝑝 = 22911315mod 59747 = 43319 ≠ 33692 mod 59747  Bob thực hiện tiếp 39 - Bob chọn ngẫu nhiên 𝑓1 = 17, 𝑓2 = 19 ∈ 𝑍𝑞 ∗ - Bob tính C = 𝑦𝑓1𝑕𝑓2 mod p = 30178175765319mod 59747 = 9217 và gửi cho Alice - Alice tính D = 𝐶𝑎 −1mod q𝑚𝑜𝑑 𝑝 = 921711 −1mod 29873𝑚𝑜𝑑 59747 = 33028 và gửi cho Bob - Bob kiểm tra 𝐷 ≢ 𝑥f1 g𝑓2𝑚𝑜𝑑 𝑝 - Bob kiểm tra: (𝒅𝒈−𝒆𝟐)𝒇𝟏 ≡ (𝑫𝒈−𝒇𝟐)𝒆𝟏 𝒎𝒐𝒅 𝒑 Có (𝒅𝒈−𝒆𝟐)𝒇𝟏 mod p = (33692 * 3-15)17 (mod 59747) = 40635 (𝑫𝒈−𝒇𝟐)𝒆𝟏 ( mod p ) = (33028 * 3-19)11 ( mod 59747 ) = 40635  (𝒅𝒈−𝒆𝟐)𝒇𝟏 ≡ (𝑫𝒈−𝒇𝟐)𝒆𝟏 𝒎𝒐𝒅 𝒑  Bob kết luận chữ ký là giả mạo Ví dụ này đƣợc trình bày với mục đích minh họa, nên chỉ sử dụng các số nguyên tố p, q nhỏ. Trong thực tế ứng dụng, để đảm bảo an toàn, ngƣời ta dùng các số p, q rất lớn, chẳng hạn các số có biểu diễn nhị phân cỡ 512 bits. Khi đó ta có q ≥ 2512 tức là 1/q ≤ 2−512 , một xác suất rất bé, có thể bỏ qua; và vì vậy, các yêu cầu đối với các giao thức kiểm thử và giao thức chối bỏ nhƣ trong phần đặt vấn đề có thể xem nhƣ là đƣợc thỏa mãn. 3.1.3. Một số đánh giá về sơ đồ 3.1.3.1. Độ an toàn của chữ ký Độ an toàn của hệ thống phụ thuộc vào bài toán logarit rời rạc do khóa bí mật sk = a đƣợc tính từ công thức h = ga mod p  a = loggh mod p, trong đó g, h, p là công khai. Đây chính là vấn đề của bài toán logarit rời rạc khó giải. 3.1.3.2. Chứng minh tính đúng đắn của giao thức xác thực 1/. Kết luận 1 Nếu y đúng là chữ ký của Alice trên x ( tức là y ≡ 𝑥𝑎 𝑚𝑜𝑑 𝑝 ), thì việc Bob chấp nhận y là chữ ký của Alice trên x theo giao thức kiểm thử là đúng. 40 Chứng minh Giả sử y là chữ ký hợp lệ trên x. Bắt đầu từ giá trị d mà Bob nhận từ Alice: d = 𝑐𝑎 −1 mod q𝑚𝑜𝑑 𝑝 = 𝑦𝑒1𝑎 −1 𝑕𝑒2𝑎 −1 𝑚𝑜𝑑 𝑝 (1) - Lại có y ≡ 𝑥𝑎𝑚𝑜𝑑 𝑝  𝑦𝑎 −1 ≡ 𝑥 𝑚𝑜𝑑 𝑝 (2) h ≡ 𝑔𝑎𝑚𝑜𝑑 𝑝  𝑕𝑎 −1 ≡ 𝑔 𝑚𝑜𝑑 𝑝 (3) Từ (1) (2) (3)  𝑑 ≡ 𝑥𝑒1 g𝑒2𝑚𝑜𝑑 𝑝 là điều kiện đúng để Bob chấp nhận một chữ ký là đúng. 2/. Kết luận 2 Trong trƣờng hợp y ≠ 𝑥𝑎(𝑚𝑜𝑑 𝑝), tức y không phải là chữ ký của Alice trên x thì việc Bob, theo giao thức kiểm thử, chấp nhận chữ ký y là chữ ký của Alice trên x, có thể xảy ra với xác suất là 1/q. Chứng minh - Giá trị c mà Alice nhận đƣợc quyết định bởi sự lựa chọn 2 giá trị 𝑒1, 𝑒2. - y, h là phần tử trong G cấp q  mỗi giá trị c tƣơng ứng với q cặp (𝑒1, 𝑒2 ) - Khi Alice nhận đƣợc c từ Bob, Alice không có cách gì để biết là Bob đã dùng cặp ( e1, e2) nào trong q cặp có thể đó. Chúng ta sẽ chứng minh rằng, nếu y ≠ x a mod p, bất kỳ giá trị d nào mà Alice trả lại cho Bob tƣơng ứng với duy nhất 1 trong q cặp ( e1, e2 ), tức là trong q cặp đó chỉ có đúng một cặp ( e1, e2) thỏa mãn đồng dƣ thức d ≡ 𝑥𝑒1𝑔𝑒2 (𝑚𝑜𝑑 𝑝). Thật vậy: + g là phần tử sinh của nhóm G theo modulo q. Vì thế chúng ta có thể viết lại nhƣ sau: c = g i mod q, d = g j mod q, x = g k mod q, y = g l mod q trong đó i, j, k, l ϵ Zq. + Kết hợp với c ≡ 𝑦𝑒1𝑕𝑒2 ( 𝑚𝑜𝑑 𝑝 ) d ≡ 𝑥𝑒1𝑔𝑒2 ( 𝑚𝑜𝑑 𝑝 )  i = le1 + ge2 ( mod q ) j = ke1 + e2 ( mod q ) Do giả thiết y ≠ xa( mod p )  l ≢ ak ( mod q ) (I) 41  Định thức của ma trận hệ số của (I) với các ẩn số e1, e2 là khác 0  (I) có nghiệm duy nhất  bất kỳ d ∈ G là giá trị đáp ( response ) của chỉ một trong q cặp giá trị có thể ( e1, e2 )  Xác suất để Alice đƣa ra giá trị đáp đúng cho Bob trong quá trình xác thực chữ ký là 1/q. Nhận định đƣa ra đã đƣợc chứng minh 3.1.3.3. Chứng minh tính đúng đắn của giao thức chối bỏ 1/. Kết luận 1 Nếu y ≠ xa mod p và cả Alice và Bob đều tuân theo giao thức chối bỏ, thì (𝑑𝑔−𝑒2 )𝑓1 ≡ (𝐷𝑔−𝑓2 )𝑒1 𝑚𝑜𝑑 𝑝 tức giao thức cho kết quả chính xác. Chứng minh Giả sử y ≠ xa (mod p), Alice và Bob cùng thực hiện giao thức chối bỏ. Do y không là chữ ký của Alice trên x nên Bob sẽ kiểm thử đúng các bất đồng dƣ thức trong các bƣớc 3 và 6 của giao thức. Vì 𝑕 ≡ 𝑔𝑎 ( 𝑚𝑜𝑑 𝑝 ), nên ta có: (𝒅𝒈−𝒆𝟐)𝒇𝟏 ≡ ((𝑦𝑒1𝑕𝑒2 )𝑎 −1 𝑔−𝑒2 )𝑓1 ( mod p ) ≡ 𝑦𝑎 −1𝑒1𝑓1𝑕𝑎 −1𝑒2𝑓1𝑔−𝑒2𝑓1 ( mod p ) ≡ 𝑦𝑎 −1𝑒1𝑓1 ( mod p ) Tƣơng tự ta cũng có: (𝑫𝒈−𝒇𝟐)𝒆𝟏 ≡ 𝑦𝑎 −1𝑒1𝑓1 ( mod p ) Nhƣ vậy, đồng dƣ thức ở bƣớc 7 của giao thức đƣợc nghiệm đúng, và kết luận y là chữ ký giả mạo của A trên x là chính xác, không thể bác bỏ đƣợc. 2/. Kết luận 2 Một điều thú vị có thể xảy ra khi Alice cố tình muốn chối bỏ một chữ ký của mình bằng cách không tuân theo giao thức hỏi – đáp một cách trung thực. Alice có thể làm cho Bob nghĩ rằng chữ ký thực sự là giả mạo trong khi không phải nhƣ thế. Dƣới đây xin nêu ra 1 kết luận nhƣ sau: Xác suất để Alice chối bỏ một chữ ký đúng của anh ta là 1/q Chứng minh Nếu Alice cố gắng lừa Bob để Bob nghĩ rằng chữ ký đó là giả mạo, có nghĩa là những điều kiện sau đây đồng thời xảy ra: 42 𝑦 ≡ 𝑥𝑎 𝑚𝑜𝑑 𝑝 (1) 𝑑 ≢ 𝑥𝑒1𝑔𝑒2 𝑚𝑜𝑑 𝑝 (2) 𝐷 ≢ 𝑥𝑓1𝑔𝑓2 𝑚𝑜𝑑 𝑝 (3) (𝒅𝒈−𝒆𝟐)𝒇𝟏 ≡ (𝑫𝒈−𝒇𝟐)𝒆𝟏 𝒎𝒐𝒅 𝒑 (4) Điều kiện (4) có thể đƣợc viết lại nhƣ sau 𝐷 ≡ 𝑑𝑜 𝑓1𝑔𝑓2 (mod p ) trong đó x = do = 𝑑 1/𝑒1𝑔−𝑒2/𝑒1𝑚𝑜𝑑 𝑝 mod p (5) Nhƣ trong phần trình bày trƣớc, chúng ta kết luận rằng y là chữ ký hợp lệ của d0 với xác suất 1 – 1/q ( do xác suất của việc chấp nhận chữ ký 𝑦 ≠ 𝑥𝑎 𝑚𝑜𝑑 𝑝 là 1/q ) Do y là chữ ký hợp lệ của x, x = d0 => (2)  x ≢ 𝑑 1/𝑒1𝑔−𝑒2/𝑒1𝑚𝑜𝑑 𝑝 Lại có do = 𝑑 1/𝑒1𝑔−𝑒2/𝑒1𝑚𝑜𝑑 𝑝 Từ 2 điều trên => x ≠ d0. Điều này có nghĩa là Alice làm cho Bob nghĩ rằng y là giả mạo với xác suất 1/q. 43 3.2. CÁC HÌNH THỨC TẤN CÔNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ Trong [8], Markus Jakobsson trình bày hai hình thức tấn công chữ ký không thể chối bỏ nhƣ sau: 3.2.1. Tống tiền ngƣời ký Giả sử Alice ký chữ ký y trên thông điệp x, nhƣng không muốn để lộ thông tin về x cho các đối thủ của cô biết. Ngƣời tống tiền Eve bằng cách nào đó, tìm đƣợc (x, y) và quyết định tống tiền Alice. Eve thực hiện: - Bƣớc 1: Eve thông báo cho các đối thủ của Alice biết cô ta có một số thông tin mà họ cần. Cô ta đƣa cho mỗi đối thủ {Enemyi}( i = 1 – n ) cặp giá trị {y, h} và yêu cầu mỗi đối thủ tạo hai số bí mật ai, bi sau đó tính bí mật ci = 𝑦 𝑎1𝑕𝑏𝑗 và đƣa giá trị ci cho Eve. - Bƣớc 2: Eve cũng tạo bí mật cặp (a0, b0 ), tính c0 = 𝑦 𝑎0𝑕𝑏0 . - Bƣớc 3: Eve tính c = 𝑐𝑖 𝑛 𝑖=0 . Sau đó, Eve bằng cách nào đó yêu cầu Alice ký lên một thông điệp x’ bất kỳ, thu đƣợc chữ ký y’. Thay vì xác thực chữ ký x’, Eve xác thực chữ ký trên x. Alice không thể biết đƣợc điều này bởi vì cặp giá trị ngẫu nhiêu trong giao thức hỏi đáp là do ngƣời xác thực chữ ký thực hiện. Sau khi gửi giá trị c cho Alice, Eve nhận đƣợc d = 𝑥𝑒1𝑔𝑒2 trong đó e1 = 𝑎𝑖 𝑛 𝑖=0 và e2 = 𝑏𝑖 𝑛 𝑖=0 ( vào thời điểm này, Eve không biết các giá trị ai, bi ). - Bƣớc 4: Alice yêu cầu các đối thủ của Alice đƣa cho cô ta cặp giá trị ( ai, bi ). Eve thông báo cho Alice biết cô ta đã có đƣợc thông điệp x và có thể cô ta sẽ nói với các đối thủ của Alice. Nếu Alice không thực hiện theo những gì Eve nói, Eve sẽ thực hiện bƣớc 5 nhƣ sau: - Bƣớc 5: Ở bƣớc này, Eve đƣa ( {𝑎𝑖}𝑖=1 𝑛 , {𝑏𝑖}𝑖=1 𝑛 ,𝑑, 𝑥 ) cho tất cả các đối thủ . Khi đó {Enemy}i có thể thấy cặp (ai, bi) đƣợc dùng trong tập {ai}{bi} dùng để xác thực chữ ký. Vì thế họ tin rằng Alice đã kí lên thông điệp x. 3.2.2. Nhiều ngƣời cùng xác thực chữ ký mà ngƣời ký không biết Eve là ngƣời đứng ra xác thực, cô ta tính c = 𝑐𝑖 𝑛 𝑖=0 từ các giá trị ci = 𝑦 𝑎𝑖𝑕𝑏𝑖 mà những ngƣời muốn xác thực chữ ký gửi đến cho cô ta. Eve gửi c cho Alice. Sau khi nhận đƣợc d từ Alice, Eve gửi ({𝑎𝑖}𝑖=0 𝑛 , {bi}𝑖=0 𝑛 , d) cho những ngƣời vừa gửi ci đến cho Eve. Tất cả những ngƣời này đã xác thực đƣợc chữ ký mà Alice không hề hay biết. Thật vậy: c = 𝑐𝑖 𝑛 𝑖=0 = 𝑦 𝑎𝑖𝑛 𝑖=0 𝑕 𝑏𝑖 = 𝑦 𝑎𝑖 𝑛 𝑖=0 𝑕 𝑏𝑖 𝑛 𝑖=0 44  e1 = 𝑎𝑖 𝑛 𝑖=0 và e2 = 𝑏𝑖 𝑛 𝑖=0 Khi đó tất cả những ngƣời gửi ci cho Eve kiểm tra đƣợc rằng (ai, bi) đã đƣợc sử dụng trong giao thức kiểm tra chữ ký, và chữ ký đƣợc kiểm tra nhƣ là liên hệ trực tiếp với Alice. 45 3.3. ỨNG DỤNG CHỮ KÝ KHÔNG THỂ CHỐI BỎ 3.3.1. Ứng dụng trong thẻ chứng minh thƣ điện tử Bởi vì quá trình xác thực một chữ ký cần sự cộng tác của ngƣời ký, chữ ký không thể chối bỏ phù hợp với ứng dụng chứng minh thƣ điện tử. Ở Bỉ ngƣời ta đã sử dụng chứng minh thƣ điện tử dựa trên chữ ký không thể chối bỏ [6]. Một ví dụ minh họa, ngƣời A mua một vài hàng hóa qua mạng Internet và đƣợc chuyển về bƣu điện địa phƣơng cho A. A ký vào văn bản online sử dụng chữ ký không thể chối bỏ, khi A tới bƣu điện để lấy hàng hóa, A xác thực rằng anh ta chính là chủ sở hữu của những hàng hóa đó. 3.3.2. Ứng dụng trong ký hợp đồng qua điện thoại Một ví dụ khác đƣợc minh họa trong [11]. Bài báo trình bày về sự không chối cãi của cuộc hội thoại VoIP ( Voice – over –IP ). Do sự sử dụng rộng rãi của VoIP, sẽ là một sự tiện lợi nếu chúng ta ghi âm cuộc hội thoại và coi nhƣ 1 bản hợp đồng giữa hai tổ chức. Một bản hợp đồng miệng có tính ràng buộc nhƣ một bản hợp đồng trên giấy, tuy nhiên hợp đồng trên giấy thƣờng đƣợc sử dụng rộng rãi hơn bởi vì có chữ ký của hai bên nên sẽ dễ dàng xử lý khi có tranh chấp. Vì thế nếu chúng ta ghi âm cuộc hội thoại dƣới dạng số và ký trên nó, thì đoạn ghi âm có thể đƣợc sử dụng nhƣ bằng chứng nếu có tranh chấp. Khi đó nó có sức thuyết phục không kém gì hợp đồng trên giấy. Ở đây, chữ ký không thể chối bỏ là một sự lựa chọn tốt, bởi vì nó chỉ liên quan đến hai tổ chức, không cần phát tán ra bên ngoài. Khi đó mỗi tổ chức dùng khóa bí mật của mình ký lên đoạn ghi âm. Khi đó đoạn hội thoại cùng với 2 chữ ký của 2 tổ chức lên đoạn hội thoại chính là hợp đồng. Bởi vì đoạn hội thoại đã đƣợc ký lên, không ai có thể thay đổi nó hoặc tạo ra một chữ ký giả. 46 Chương 4. THỬ NGHIỆM CÁC CHƢƠNG TRÌNH 4.1. THỬ NGHIỆM ỨNG DỤNG CHỮ KÝ SỐ 4.1.1. Giới thiệu Chƣơng trình ký số file văn bản tiếng Việt theo thuật toán ký số RSA đƣợc viết bằng Visual C++ trên nền .NET 3.5, sử dụng thƣ viện nguồn mở OpenSSL. Chƣơng trình có các chức năng chính sau: - Ký văn bản text tiếng việt theo thuật toán RSA - Xác thực 1 chữ ký - Mã hóa văn bản và chữ ký theo thuật toán mã hóa DES - Giải mã văn bản và chữ ký theo thuật toán mã hóa DES Dƣới đây là giao diện của chƣơng trình: Hình 1: Giao diện chương trình ký số RSA 47 4.1.2. Mô tả hoạt động chƣơng trình 4.1.2.1. Chức năng ký số ( sử dụng thuật toán ký số RSA ) 1/. Mô tả cách dùng - Mô tả chức năng: Chƣơng trình sẽ sinh ra khóa ký RSA ngẫu nhiên có độ dài 512 bits hoặc 1024 bits (theo lựa chọn của ngƣời dùng ). Sau đó ghi khóa bí mật và khóa công khai ra các file tƣơng ứng. Trƣớc khi ký, văn bản sẽ đƣợc băm theo thuật toán SHA1. Hình 2: Giao diện chức năng “Ký”RSA - Ngƣời dùng nhập vào các thông tin sau + Key size ( có 2 lựa chọn 512 bits và 1024 bits ). + Input file: Đƣờng dẫn tuyệt đối của văn bản cần ký ( File text Unicode ) + Public key file: đƣờng dẫn tuyệt đối của file sẽ lƣu khóa công khai tạo ra + Private key file: đƣờng dẫn tuyệt đối của file sẽ lƣu khóa bí mật + Digest: đƣờng dẫn tuyệt đối của file sẽ lƣu đại diện của văn bản ( giá trị băm của văn bản trƣớc khi ký ). + Signature: đƣờng dẫn tuyệt đối của file chứa chữ ký. 48 Trong chƣơng trình này, khóa công khai, khóa bí mật, đại diện, chữ ký đƣợc biểu diễn dƣới dạng 1 xâu chứa mã ASCII của các ký tự. 2/. Mô tả cách cài đặt chức năng ký số Chức năng này có các hàm chính sau: - Hàm sinh khóa bí mật và công khai phục vụ việc ký private: RSA* generateKey (String^ klen) đƣợc cài đặt nhƣ sau: + Khởi tạo biến RSA* r bằng hàm RSA_generate_key của thƣ viện OpenSSL. Ở đây chúng ta lƣu ý rằng trong thƣ viện OpenSSL, khóa bí mật và khóa công khai đƣợc biểu diễn theo chuẩn PKCS#1. + Ghi khóa bí mật vào file khóa bí mật + Ghi khóa công khai vào file khóa công khai + Hàm trả lại giá trị r - Hàm thực hiện việc ký private: void hSign(RSA* r ) đƣợc cài đặt nhƣ sau: + Đọc nội dung file cần ký vào mảng buffer có kiểu wchar_t* + Biểu diễn mỗi phần tử trong buffer dƣới dạng mã Unicode của nó. Kết quả thu đƣợc là String mesStr chứa mã Unicode tƣơng ứng của buffer. + Gọi đến hàm SHA1 trong thƣ viện OpenSSL để băm string mesStr theo thuật toán băm SHA1, kết quả thu đƣợc lƣu vào mảng unsigned char* hash. + Gọi đến hàm RSA_sign trong thƣ viện OpenSSL để ký lên mảng hash ở trên với khóa ký r. Kết quả trả về sau khi ký là là mảng unsigned char* signature. + Biểu diễn 2 mảng kiểu unsigned char* hash và signature dƣới dạng các String chứa mã ASCII của các ký tự. Ghi các giá trị này tƣơng ứng ra file chứa đại diện và file chứa chữ ký. + Khi việc ký kết thúc thành công sẽ hiện lên thông báo “Signing completed successfully!!!”. 49 4.1.2.2. Chức năng xác thực chữ ký số 1/. Mô tả Hình 3: Giao diện chức năng xác thực chữ ký số RSA - Ngƣời dùng nhập vào các thông tin sau: + Input file: File văn bản + Signature: File chữ ký trên văn bản + Public key file: File chứa khóa công khai dùng để xác thực chữ ký. - Kết quả trả về là “Signature is true” nếu chữ ký là đúng hoặc “Signature is false” nếu chữ ký là sai. 2/. Mô tả cài đặt Có các hàm chính sau đây: - Hàm xử lý sự kiện click vào nút Verify private:System::Void Verify_Click(System::Object^sender,System::EventArgs^ e) + Đọc file thông điệp vào 1 mảng wchar_t* wbuffer. + Biểu diễn mỗi phần tử trong buffer dƣới dạng mã Unicode của nó. Kết quả thu đƣợc là String mesStr chứa mã Unicode tƣơng ứng của buffer. + Đọc nội dung file chữ ký vào một mảng char* sig 50 + Băm String mesStr theo thuật toán SHA1, giá trị băm đƣợc lƣu vào mảng unsigned char* hash. + Đọc nội dung file khóa công khai vào một mảng unsigned char* pubKey. Tạo biến RSA* rsa từ hàm d2i_RSAPublicKey ( trong thƣ viện nguồn mở OpenSSL ) trong đó pubKey là 1 tham số của hàm. + Gọi đến hàm RSA_verify trong thƣ viện OpenSSL để xác thực chữ ký là đúng hay sai. 4.1.2.3. Chức năng mã hóa theo hệ mã hóa DES 1/. Mô tả - Chức năng: mã hóa file văn bản và file chữ ký theo hệ mã hóa DES Hình 4: Giao diện chức năng mã hóa DES file văn bản và chữ ký - Ngƣời dùng nhập vào các thông tin sau: + Input file: đƣờng dẫn tuyệt đối của file văn bản + Signature: đƣờng dẫn tuyệt đối của file chữ ký + Passphrase + Encrypted input file: đƣờng dẫn tuyệt đối file lƣu bản mã văn bản. + Encrypted signature: đƣờng dẫn tuyệt đối file lƣu bản mã chữ ký 51 2/. Mô tả cài đặt - Hàm mã hóa file thông điệp và file chữ ký theo hệ mã hóa DES private:System::Void encrypt_Click(System::Object^ sender, System::EventArgs^e) đƣợc cài đặt nhƣ sau: + Đọc nội dung file văn bản vào wchar_t* buffer. + Biểu diễn mỗi phần tử trong buffer dƣới dạng mã Unicode của nó. Kết quả thu đƣợc là String mesStr chứa mã Unicode tƣơng ứng của buffer. + Đọc file chữ ký vào một mảng unsigned char* sig. + Tạo khóa mã hóa và giải mã từ passphrase do ngƣời dùng nhập vào. + Lần lƣợt dùng hàm DES_cfb64_encrypt với tùy chọn DES_ENCRYPT của thƣ viện OpenSSL để mã hóa 2 mảng buffer và sig thu đƣợc 2 mảng unsigned char lần lƣợt là resMes và resSig. + Biểu diễn 2 mảng kiểu unsigned char resMes và resSig dƣới dạng các String chứa mã ASCII của các ký tự. Ghi các giá trị này tƣơng ứng ra file chứa bản mã của văn bản và file chứa bản mã của chữ ký. 4.1.2.4. Chức năng giải mã DES 1/. Mô tả Hình 5: Giao diện chức năng giải mã DES 52 - Chức năng: giải mã bản mã thông điệp và bản mã chữ ký thành bản rõ tƣơng ứng. - Ngƣời dùng nhập vào các thông tin sau: + Encrypted input file: đƣờng dẫn tuyệt đối của file chứa bản mã thông điệp + Encrypted signature: đƣờng dẫn tuyệt đối của file chứa bản mã chữ ký + Passphrase + Decrypted input file: đƣờng dẫn tuyệt đối của file sẽ chứa bản rõ thông điệp + Decrypted signature: đƣờng dẫn tuyệt đối của file chứa bản rõ của chữ ký. Sau khi kết thúc quá trình mã hóa, một thông báo “Decryption completed sucessfully!!!” đƣợc đƣa ra. 2/. Mô tả cài đặt Các hàm chính - Hàm giải mã bản mã thông điệp và bản mã chữ ký private:System:: Void decrypt_Click(System::Object^sender, System::EventArgs^e) + Đọc dữ liệu từ file thông điệp đã mã hóa vào mảng unsigned char enFileArr + Đọc dữ liệu từ file chữ ký đã mã hóa vào mảng unsigned char enSigArr. + Tạo khóa DES từ passphrase do ngƣời dùng nhập vào. + Dùng hàm DES_cfb64_encrypt với tùy chọn DES_DECRYPT để giải mã file bản mã thông điệp. Tham số của hàm là mảng unsigned char enFileArr. Kết quả trả về của hàm là 1 mảng unsigned char chứa mã Unicode của các ký tự. Từ mảng này ta chuyển sang đƣợc mảng wchar_t chứa các ký tự của văn bản nguyên gốc. Ghi mảng này vào file ta đƣợc file chứa bản rõ thông điệp. + Dùng hàm DES_cfb64_encrypt với tùy chọn DES_DECRYPT để giải mã file bản mã chữ ký. Tham số của hàm là mảng unsigned char enSigArr. Kết quả trả về của hàm này là 1 mảng unsigned char chứa mã ASCII của các ký tự. Từ mảng này ta chuyển sang mảng char chứa các ký tự nguyên gốc. Ghi mảng này vào file ta đƣợc file chứa bản rõ chữ ký. 53 4.2. THỬ NGHIỆM CHƢƠNG TRÌNH KÝ MÙ RSA 4.2.1. Giới thiệu Chƣơng trình minh họa đƣợc viết bằng Visual C++ trên nền .NET 3.5 gồm 2 chức năng: - Ký mù trên một số nguyên - Xóa mù chữ ký 4.2.2. Mô tả hoạt động chƣơng trình 1/. Chức năng ký mù - Thông tin đầu vào + Số nguyên tố p, q, chọn khóa công khai b, số ngẫu nhiên r (nhƣ mô tả trong thuật toán) + Nhập vào thông điệp cần ký là một số nguyên + Sau khi nhập xong thông tin, bấm Sign để thực hiện việc ký, Cancel để hủy bỏ - Thông tin đầu ra + Giá trị thông điệp sau khi làm mù + Chữ ký mù trên thông điệp Hình 6: Giao diện chức năng ký mù 54 2/. Chức năng xóa mù chữ ký - Thông tin đầu vào + Số n, khóa công khai b, số ngẫu nhiên r, giá trị thông điệp sau khi làm mù, chữ ký mù. + Sau khi nhập các thông tin ở trên, bấm Unblind để xóa mù và xác thực chữ ký, Cancel để hủy bỏ. - Thông tin đầu ra + Giá trị chữ ký sau khi xóa mù. + Xác thực tính đúng sai của chữ ký ( nếu chữ ký là đúng, chƣơng trình trả vể “OK”, ngƣợc lại là “Not OK”). Hình 7: Giao diện chức năng xóa mù chữ ký 55 4.3. THỬ NGHIỆM CHỮ KÝ KHÔNG THỂ CHỐI BỎ 4.3.1. Giới thiệu Chƣơng trinh gồm 2 tab, 1 cho ngƣời ký (signer) và 1 cho ngƣời xác thực chữ ký - Tab Signer Hình 8: Giao diện của người ký chữ ký không thể chối bỏ - Tab verifier Hình 9: Giao diện của người xác thực chữ ký không thể chối bỏ 56 4.3.2. Mô tả hoạt động chƣơng trình 1/. Chuẩn bị các tham số - Khi chƣơng trình đƣợc bật lên, số nguyên tố ngẫu nhiên p, q đã đƣợc chọn sẵn cho ngƣời dùng. Giá trị g cũng đã đƣợc tính sẵn dựa theo p. Tuy nhiên ngƣời dùng có thể nhập trực tiếp giá trị p và g từ bàn phím bằng cách sửa trực tiếp ở các textbox này. - Ngƣời ký nhập giá trị khóa bí mật a ( 0 < a < q ) vào textbox sau đó nhấn enter. Chƣơng trình tự động tính giá trị h = ga mod p. Khi đó: + Tab Signer có các thông tin: p, q, g, a, h + Tab Verifier có các thông tin: p, q, g, h 2/. Ký - Ngƣời cần ký nhập vào thông điệp cần ký ( bên tab Verifier ) là một số sau đó nhấn Enter, khi đó thông điệp đƣợc chuyển sang cho Signer, Signer ký y = x a mod p sau đó bấm vào nút “Send” để gửi giá trị chữ ký cho Verifier. 3/. Giao thức kiểm thử chữ ký - Verifier nhập vào 2 số ngẫu nhiên 𝑒1, 𝑒2 ∈ 𝑍𝑞 ∗. Khi đó chƣơng trình sẽ tính giá trị c và hiển thị giá trị này vào textbox c. Sau đó giá trị này đƣợc gửi cho Signer. - Sau khi nhận đƣợc c, chƣơng trình tính d = 𝑐𝑎 −1𝑚𝑜𝑑 𝑞𝑚𝑜𝑑 𝑝 và hiển thị giá trị này vào textbox d trong tab Signer. Signer bấm vào nút “Send” để gửi giá trị này cho Verifier. - Sau khi nhận đƣợc d, Verifier bấm vào nút “Result” để hiện kết quả kiểm tra chữ ký. Nếu chữ ký là đúng, chƣơng trình sẽ có thông báo: 57 Hình 10: Thông báo khi chữ ký không thể chối bỏ được xác thực là đúng 4/. Giao thức chối bỏ chữ ký - Trƣờng hợp thứ nhất: Ngƣời ký (Signer) chối bỏ một chữ ký không phải do anh ta ký + Verifier nhập 1 số nguyên vào textbox Message. + Verifier nhập chữ ký vào textbox Signature. Sau khi nhập xong, nhấn Enter để chƣơng trình thực hiện việc chuyển thông điệp và chữ ký cho Signer. + Sau đó, ngƣời xác thực chữ ký (Verifier) nhập giá trị 𝑒1, 𝑒2 tƣơng ứng. Nhấn Enter để chƣơng trình tự động tính c. Giá trị c này đƣợc tự động gửi cho Signer. + Sau khi nhận đƣợc c, chƣơng trình tính d = 𝑐𝑎 −1𝑚𝑜𝑑 𝑞𝑚𝑜𝑑 𝑝 và hiển thị giá trị này vào textbox d trong tab Signer. Signer bấm vào nút “Send” để gửi giá trị này cho Verifier. + Sau khi nhận đƣợc d, Verifier bấm vào nút “Result” để hiện kết quả kiểm tra chữ ký. Nếu điều kiện kiểm tra không đƣợc thỏa mãn, chƣơng trình sẽ hiện lên nhƣ sau: 58 Hình 11: Thông báo khi điều kiện 𝒅 ≡ 𝒙𝒆𝟏𝒈𝒆𝟐𝒎𝒐𝒅 𝒑 không được thỏa mãn + Sau khi bấm OK, các textbox 𝑓1, 𝑓2 xuất hiện để ngƣời dùng nhập thông tin vào. Sau khi nhập vào 𝑓1, 𝑓2 Verifier nhấn Enter để chƣơng trình tự động tính C. Giá trị C này đƣợc tự động gửi cho Signer. + Signer sau khi nhận đƣợc C sẽ tính D. Signer bấm “Send” để gửi cho Verifier. + Sau khi Verifier nhận đƣợc D, Verifier click vào nút “Result” để xem kết quả. Nếu chữ ký đúng là giả mạo, thông báo của chƣơng trình nhƣ sau: Hình 12: Thông báo khi chữ ký đúng là giả mạo 59 - Trƣờng hợp Signer cố tình chối bỏ chữ ký của mình + Verifier nhập 1 số nguyên vào textbox Message. + Verifier nhập chữ ký của Signer trên Message vào textbox Signature. Sau khi nhập xong, nhấn Enter để chƣơng trình thực hiện việc chuyển thông điệp và chữ ký cho Signer. + Sau đó, verifier nhập giá trị 𝑒1, 𝑒2 tƣơng ứng. Nhấn Enter để chƣơng trình tự động tính c. Giá trị c này đƣợc tự động gửi cho Signer. + Sau khi nhận đƣợc c, chƣơng trình tính d = 𝑐𝑎 −1𝑚𝑜𝑑 𝑞𝑚𝑜𝑑 𝑝 và hiển thị giá trị này vào textbox d trong tab Signer. Signer có thể chỉnh sửa giá trị d này tùy ý sau đó bấm vào nút “Send” để gửi giá trị này cho Verifier. + Sau khi nhận đƣợc d, Verifier bấm vào nút “Result” để kiểm tra chữ ký. Nếu điều kiện kiểm tra không thỏa mãn, thông báo nhƣ Hình 11 hiện ra. + Sau khi bấm OK, các textbox 𝑓1, 𝑓2 xuất hiện để ngƣời dùng nhập thông tin vào. Sau khi nhập vào 𝑓1, 𝑓2, verifier nhấn Enter để chƣơng trình tự động tính C. Giá trị C này đƣợc tự động gửi cho Signer. + Phía Signer sau khi nhận đƣợc C sẽ tính D. Signer có thể chỉnh sửa giá trị D này tùy ý sau đó bấm vào nút “Send” để gửi giá trị này cho Verifier. + Sau khi Verifier nhận đƣợc D, Verifier click vào nút “Result” để xem kết quả sẽ thu đƣợc thông báo nhƣ sau: Hình 13: Thông báo khi phát hiện người ký cố tình chối bỏ chữ ký của mình 60 KẾT LUẬN a. Kết quả thu đƣợc Sau thời gian thực hiện khóa luận, em đã tìm hiểu đƣợc kiến thức tổng quan về lý thuyết bảo mật thông tin, mã hóa, ký số. Đồng thời đã nghiên cứu sử dụng thƣ viện mã nguồn mở OpenSSL để xây dựng các ứng dụng thử nghiệm. Khóa luận gồm các kết quả nghiên cứu sau: 1/. Tìm hiểu và nghiên cứu các tài liệu để hệ thống lại các vấn đề sau: + Chữ ký mù RSA + Chữ ký không thể chối bỏ 2/. Thử nghiệm các chƣơng trình ứng dụng sau: + Chữ ký số RSA + Chữ ký mù RSA + Chữ ký không thể chối bỏ b. Tƣơng lai phát triển Cùng với sự phát triển nhanh chóng của công nghệ thông tin, nền quản lý hành chính điện tử, thƣơng mại điện tử hay chính phủ điện tử sẽ là những vấn đề cấp thiết cần nghiên cứu và phát triển. Bởi vậy, việc xây dựng một cơ sở hạ tầng thông tin an toàn là rất cần thiết và cấp bách. Chữ ký số là một phƣơng pháp hiệu quả trong bảo vệ thông tin. Vì vậy, nó đã, đang và sẽ thu hút nhiều sự chú ý, nghiên cứu và ứng dụng trên thế giới. Ở Việt Nam, chuyên ngành an toàn thông tin cũng chỉ đang trong giai đoạn phát triển, nên những kiến thức nền tàng này đóng vai trò rất quan trọng. Trong tƣơng lai, em muốn tiếp tục nghiên cứu để cải tiến nhƣợc điểm của các sơ đồ chữ ký trên, cũng nhƣ tìm hiểu thêm nhiều loại chữ ký số khác để có thể áp dụng rộng rãi vào nhiều lĩnh vực khác nhau nhƣ: quản lý hành chính, thƣơng mại điện tử, …. TÀI LIỆU THAM KHẢO [1] Phan Đình Diệu. Lý thuyết mật mã và an toàn thông tin – NXB Đại học Quốc gia Hà Nội - 2006 [2] Trịnh Nhật Tiến. Giáo trình An toàn dữ liệu [3] Trịnh Nhật Tiến, Đinh Vinh Quang. Thanh toán bằng “Tiền điện tử” [4] Trịnh Nhật Tiến, Trƣơng Thị Thu Hiền. Về một quy trình bỏ phiếu từ xa – Tạp chí Khoa học ĐHQGHN, KHTN & CN, T.XXI, SỐ 2PT. 2005 [5] Trịnh Nhật Tiến. Chữ ký: mù, nhóm, mù nhóm và ứng dụng. Kỷ yếu HN KH FAIR lần 2 tại TP Hồ Chí Minh 9/2005 [6] Danny De Cock, Christopher Wolf, Bart Preneel. The Belgian Electronic Identity Card. [7] Doublas Stinson. Cryptography: Theory and Practice – CRC Press 03/17/95 [8] Markus Jakobsson. Blackmailing using undeniable signatures. Springer- Verlag [9] Matt Messsier, John Viega. Secure Programming Cookbook for C and C++ - O’Reilly July 2003 [10] Morten Bohoj, Mads Keblov Kjeldsen. Cryptography report Undeniable signature schems – December 15, 2006 [11] N. Kuntze C. Hett and A. U. Schmidt. Non-repudiation of voice-over-ip conversations with chained digital signatures. From Fraunhofer SIT [12] [13] [14] [15]