Chữ ký số người xác nhận không thể chối bỏ

gọn được xây dựng như một sự ghép của 4 từ A, B, C, D. Các từ này gần tương tự như 4 thanh ghi trong máy tính. Các thanh ghi có giá trị khởi tạo từ bước 1. Xử lý mảng M[] tại một thời điểm, thực hiện 16 từ của M[] và lưu trữ chúng trong mảng X[] tại bước 3. Tại bước 4 giá trị của A, B, C, D được lưu trữ trong các biến AA, BB, CC, DD. Sau đó chúng ta thực hiện 3 vòng lặp của hashing. Mỗi vòng thực hiện các phép toán số học và logic trên 16 từ của X, các toán hạng này sau khi thực hiện trong 3 vòng sẽ cho giá trị mới bằng cách cộng vào các giá trị được lưu trữ trong bước 4. Đây là phép cộng các số nguyên được rút gọn bằng phép module 232. Khi MD4 thực hiện đầy đủ thì một điều cần thiết phải tính đến đó là cấu trúc của bộ vi xử lý trong máy tính nhằm mục đích thực hiện các phép cộng chính xác nhất. Trong 3 vòng Round1, Round2, Round3 của MD4 thực hiện các phép toán logic sau: + a << s: phép quay vòng dịch trái đại lượng a đi s bit, 1 Ê s Ê 32 +ỉa: phép đảo bit + Ù: phép and + Ú: phép or + Å: phép Xor + “+”: cộng 2 số nguyên theo module 232 Mỗi vòng chỉ sử dụng một trong 3 hàm f, g, h: f(A, B, C) = (AÙB)Ú(AC) g(A, B, C) = (AÙB)Ú(AÙC)Ú(BÙC) h(A, B, C) = A Å B Å C Ta ký hiệu các hằng số: K1 = 0x5a827999 K2 = 0x6ed9eba1 Các biến Xi, i = Bảng chân lý của 3 hàm: A B C f(A, B, C) g(A, B, C) h(A, B, C) 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 3 vòng Round1, Round2, Round3 được mô tả theo bảng sau: Round1: 1 A = (A + f(B, C, D) + Xo)<<3 2 D = (D + f(A, B, C) + X1)<<7 3 C = (C + f(D, A, B) + X2)<<11 4 B = (B + f(C, D, A) + X3)<<19 5 A = (A + f(B, C, D) + X4)<<3 6 D = (D + f(A, B, C) + X5)<<7 7 C = (C + f(D, A, B) + X6)<<11 8 B = (B + f(C, D, A) + X7)<<19 9 A = (A + f(B, C, D) + X8)<<3 10 D = (D + f(A, B, C) + X9)<<7 11 C = (C + f(D, A, B) + X10)<<11 12 B = (B + f(C, D, A) + X11)<<19 13 A = (A + f(B, C, D) + X12)<<3 14 D = (D + f(A, B, C) + X13)<<7 15 C = (C + f(D, A, B) + X14)<<11 16 B = (B + f(C, D, A) + X15)<<19 Round2: 1 A = (A + g(B, C, D) + Xo + K1)<<3 2 D = (D + g(A, B, C) + X4 + K1)<<5 3 C = (C + g(D, A, B) + X8 +K1)<<9 4 B = (B + g(C, D, A) + X12 + K1)<<13 5 A = (A + g(B, C, D) + X1 + K1)<<3 6 D = (D + g(A, B, C) + X5 + K1)<<5 7 C = (C + g(D, A, B) + X8 +K1)<<9 8 B = (B + g(C, D, A) + X13 + K1)<<13 9 A = (A + g(B, C, D) + X2 + K1)<<3 10 D = (D + g(A, B, C) + X6 + K1)<<5 11 C = (C + g(D, A, B) + X10 +K1)<<9 12 B = (B + g(C, D, A) + X14 + K1)<<13 13 A = (A + g(B, C, D) + X3 + K1)<<3 14 D = (D + g(A, B, C) + X7 + K1)<<5 15 C = (C + g(D, A, B) + X11 +K1)<<9 16 B = (B + g(C, D, A) + X15 + K1)<<13 Round3: 1 A = (A + h(B, C, D) +X0 + K2)<<3 2 D = (D + h(A, B, C) + X8 + K2)<<9 3 C = (C + h(D, A, B) + X4 + K2)<<11 4 B = (B + h(C, D, A) + X12 + K2)<<15 5 A = (A + h(B, C, D) +X2 + K2)<<3 6 D = (D + h(A, B, C) + X10 + K2)<<9 7 C = (C + h(D, A, B) + X6 + K2)<<11 8 B = (B + h(C, D, A) + X14 + K2)<<15 9 A = (A + h(B, C, D) +X1 + K2)<<3 10 D = (D + h(A, B, C) + X9 + K2)<<9 11 C = (C + h(D, A, B) + X5 + K2)<<11 12 B = (B + h(C, D, A) + X13 + K2)<<15 13 A = (A + h(B, C, D) +X3 + K2)<<3 14 D = (D + h(A, B, C) + X11 + K2)<<9 15 C = (C + h(D, A, B) + X7 + K2)<<11 16 B = (B + h(C, D, A) + X15 + K2)<<15 Chương IV Chữ Ký Chống Chối Bỏ IV.1. Giới thiệu Chữ ký chống chối bỏ được công bố bởi Chaum và van Antwerpen vào năm 1989. Nó có một số nét riêng mới lạ rất thú vị. Quan trọng nhất trong số đó là chữ ký không thể kiểm tra khi không có sự cộng tác của người ký, Bob. Sự bảo vệ này của Bob đề phòng khả năng chữ ký trong tài liệu của anh ta bị sao chép và phân bố bởi thiết bị điện tử mà không có sự đồng ý của anh ta. Ví dụ, Bob có một phần mềm và chữ ký kèm theo được tạo ra nhờ thuật toán của chữ ký số thông thường. Như vậy, sẽ không tránh khỏi trường hợp phần mềm đó bị sao chép mà Bob không biết. Người mua sẽ kiểm tra chữ ký kèm theo phần mềm nhờ thuật toán kiểm tra công khai Ver và công nhận đó là chữ ký đúng. Vì như chúng ta đã biết bản sao của chữ ký số là đồng nhất với bản gốc. Đương nhiên như vậy Bob đã bị mất bản quyền. Để tránh điều bất lợi đó Bob đã dùng chữ ký số chống chối bỏ. Sự kiểm tra sẽ thành công khi thực hiện giao thức hỏi - đáp. Lược đồ chữ ký chống chối bỏ gồm 3 phần: thuật toán ký, giao thức kiểm tra, giao thức chối bỏ. IV.2. Lược đồ chữ ký chống chối bỏ IV.2.1. Thuật toán ký * Tạo khoá: Cho p, q là các số nguyên tố lẻ sao cho p = 2q + 1 và bài toán rời rạc trên Zp là khó. Lấy a ẻ Zp* là một phần tử của bậc q (Nếu a0 là phần tử nguyên thuỷ của Zp thì a = a0(p -1)/q modp). Lấy 1 Ê a Ê q-1 và xác định: b = aa modp. Lấy G là phân nhóm nhân của Zp* bậc q (G bao gồm các thặng dư bậc 2 theo modun p). Lấy P = A = G, xác định: K = { (p, a, a, b): b = aa modp} Các giá trị p, a, b là công khai, a là bí mật. * Tạo chữ ký: Với K = (p, a, a, b) và x ẻ G, xác định chữ ký y trên thông báo x: y = sigk(x) = xa modp IV.2.2. Giao thức kiểm tra Với x, y ẻ G, sự kiểm tra được tiến hành theo giao thức sau: 1. Alice chọn e1, e2 ngẫu nhiên, e1, e2 ẻ Zp*. 2. Alice tính c = y b modp và gửi nó cho Bob. 3. Bob tính d = c modp và gửi nó cho Alice. 4. Alice chấp nhận y là chữ ký đúng khi và chỉ khi: d º xamodp. * Vai trò của p, q trong lược đồ: Lược đồ nằm trong Zp; tuy nhiên chúng ta cần tính toán trong phân nhóm nhân G của Zp* của bậc nguyên tố lẻ. Đặc biệt, chúng ta cần tính phần tử nghịch đảo theo modun ẵGẵ, điều này lý giải tại sao ẵGẵnên là nguyên tố lẻ. Nó thuận tiện nếu lấy p =2q+1 với q là nguyên tố lẻ. Trong trường hợp này, phân nhóm G là tồn tại. *Chứng minh bước 4 của giao thức kiểm tra: ở đây, chúng ta chứng minh rằng Alice sẽ chấp nhận chữ ký đúng. Trong các phép toán dưới đây, tất cả số mũ là biến đổi theo modun q. Ta có: d º c modp Mà c = y b modp ị d º ybmodp (1) Ta lại có: b º aamodp ị b º a modp (2) Tương tự ta cũng có: y = xa modp ị y = x modp (3) Thay (2), (3) vào (1) được: d º xamodp. _ Đó là điều phải chứng minh. Ví dụ: Giả sử chúng ta lấy p = 467. Từ 2 là căn nguyên thuỷ => 22 = 4 là thặng dư bậc 2 theo modun 467 và 4 là phần tử sinh của G. Lấy a = 4. Giả sử a = 101, ta có: b = aamodp = 4101 mod467 = 449 Bob sẽ ký thông báo x = 119 với chữ ký: y = xa modp = 119101 mod467 = 129 Giả sử Alice muốn kiểm tra chữ ký y. Alice chọn ngẫu nhiên e1 = 38, e2 = 397. Ta có: c = y b modp = 12938 449397 mod467 = 13 Alice gửi c =13 cho Bob và Bob sẽ tính d theo: d = c modp ị d = 13101 mod233 mod467 (q = (p - 1)/2 = (467 –1 )/2 = 233) ị d = 9 Alice kiểm tra chữ ký y theo bước 4. Có: xamodp = 11938 4397 mod467 = 9 ị d º xamodp . Do đó, Alice chấp nhận chữ ký là đúng. IV.2.3. Giao thức chối bỏ Một vấn đề đặt ra, nếu sự cộng tác của Bob là cần thiết trong việc kiểm tra chữ ký thì điều gì đã ngăn cản Bob từ chối chữ ký do chính anh ta tạo ra trong thời gian gần đây? Tất nhiên, Bob có thể cho rằng chữ ký đúng đó là giả mạo và từ chối kiểm tra nó hoặc Bob thực hiện một giao thức mà theo đó chữ ký sẽ không được kiểm tra. Vì vậy, một lược đồ chữ ký chống chối bỏ được kết hợp chặt chẽ với một giao thức chối bỏ và nhờ điều đó Bob có thể chứng minh được rằng chữ ký đó là giả mạo. (Nếu anh ta từ chối thực hiện một phần trong giao thức chối bỏ, điều đó đồng nghĩa với dấu hiệu chứng minh chữ ký đó là xác thực trên thực tế và anh ta đang cố gắng từ chối chữ ký của mình). Giao thức chối bỏ gồm 2 tiến trình của giao thức kiểm tra và có các bước sau: Alice chọn e1, e2 ngẫu nhiên, e1, e2 ẻ Zq*. 2. Alice tính c = y b modp và gửi nó cho Bob. 3. Bob tính d = c modp và gửi nó cho Alice. 4. Alice kiểm tra d ạ xamodp. 5.Alice chọn f1, f2 ngẫu nhiên, f1, f2 ẻ Zq*. 6. Alice tính C = yb modp và gửi nó cho Bob. 7. Bob tính D = c modp và gửi nó cho Alice. 8. Alice kiểm tra D ạ xamodp 9. Alice kết luận rằng y là chữ ký giả mạo khi và chỉ khi (da) º (Da) modp Các bước 1 – 4 và 5 – 8 là 2 tiến trình không thành công của giao thức kiểm tra. Bước 9 là bước “kiểm tra tính chính xác” cho phép Alice xác định rõ chữ ký đó có xác thực hay không nếu sự trả lời của Bob được tạo ra như giao thức theo lý thuyết. Ví dụ: Ta lấy tương tự như ví dụ trước. Lấy p =467, a = 4, a = 101, b = 449. Ký thông báo x =286 với chữ ký y = 83 (là giả mạo). Bob muốn thuyết phục Alice rằng chữ ký đó là không đúng. Vậy phải thực hiện như sau: Alice chọn ngẫu nhiên e1 = 45, e2 = 237. Alice tính c = 305 và Bob trả lời với d = 109. Alice tính: 28645. 4237mod467 = 149. Vì 149 ạ 109 nên Alice thực hiện tiếp giao thức chối bỏ. Alice chọn tiếp f1 = 125, f2 = 9, ngẫu nhiên, Alice tính C = 270 và Bob trả lời với D = 68. Alice tính: 286125.49mod467 = 25. Vì 25 ạ 68 nên Alice thực hiện bước cuối cùng của giao thức tức là thực hiện kiểm tra tính chính xác. Ta có: (109.4-237)125 º 188 mod467 và (68.4-9)45 º 188 mod467 ị(da) º (Da) modp Vậy Alice tin chắc rằng chữ ký đó là không đúng. Š Bây giờ, chúng ta cần phải chứng minh 2 điều là: Bob có thể thuyết phục Alice rằng chữ ký không đúng đó là giả mạo. b. Bob không thể làm cho Alice bị thuyết phục rằng chữ ký đúng đó là giả mạo ngoại trừ xác suất rất nhỏ. IV. 3. Các định lý IV.3.1 Định lý 1: Nếu y ạ xa modp, Alice sẽ chấp nhận y như là một chữ ký đúng của x với xác suất . Chứng minh: Trước tiên, ta nhận xét rằng mỗi yêu cầu c có thể xảy ra sẽ tương ứng chính xác với một cặp (e1, e2) bậc q. (Bởi vì y và b đều là phần tử của nhóm nhân G có bậc nguyên tố lẻ q). Khi Bob nhận yêu cầu c anh ta không biết Alice đã dùng cặp (e1, e2) nào để xây dựng c. Chúng ta cần phải chứng minh rằng, nếu y ạ xamodp thì các câu trả lời của Bob d ẻ G có thể đúng với duy nhất một cặp (e1, e2) trong các cặp (e1, e2) bậc q. Từ phần tử sinh a của nhóm G, chúng ta có thể viết được một số phần tử của G như là một khả năng của a với số mũ xác định duy nhất theo modun q. Như vậy, ta có thể viết: c = ai, d = aj, x = ak, y = al với i, j, k, l ẻ Zp và tất cả tính theo modun p. Ta xét 2 đồng dư sau: c º yebe modp (1) d º xeaemodp (2) Û ai º al .e.bemodp với b = aamodp ị ai º al .e. aa.emodp Û ai º al .e + a .emodp ị i º l.e1 + a.e2 modq (3) (2) ị aj º ak .e. aemodp Û aj º ak .e + emodp ị j º k.e1 + e2 modq (4) Từ (3) và (4) ta có hệ: i º l.e1 + a.e2 modq j º k.e1 + e2 modq Xét D = ẵlk a1ẵ = l – a.k (5) Mặt khác: y ạ xa modp (gt) Û al ạ ak .amodp ị l ạ a.k modq (6) Từ (5) và (6) ị D ạ 0 Vì hệ số ma trận của hệ đồng dư theo modun q ạ 0 nên hệ có một nghiệm duy nhất nghĩa là ta tìm được duy nhất một cặp (e1, e2) " i, j, k, l ẻ Zp. Do đó, " d ẻ G là câu trả lời thì tất cả các câu trả lời đó chỉ đúng với một cặp (e1, e2) trong các cặp (e1, e2) bậc q. Vậy, xác suất rằng Bob đưa cho Alice câu trả lời d mà sẽ được kiểm tra là và đồng nghĩa với việc Alice chấp nhận y là chữ ký đúng của x với xác suất IV.3.2. Định lý 2. Khi Alice và Bob cùng thực hiện giao thức chối bỏ. Nếu y ạ xamodp thì (da-e)f º (Da-f)e modp. Chứng minh: Ta có: d º camodp Mà c º yebe modp ị d º ye.a.be.amodp Mặt khác: b º aa modp ị d º ye.a. ae.a.a modp Do vậy: (d.a-e)f º (ye.a.ae.a.a.a-e)f modp º ye.a.f.ae.f – e.f modp º ye.a.f modp (1) Tương tự như trên ta cũng tính được: (D.a-f)e º ye.a.f modp (2) với D º Camodp C º yfbf modp b º aa modp Từ (1) và (2) ị(da-e)f º (Da-f)e modp. ‹ Vì vậy, nếu y là chữ ký giả mạo thì Bob có thể thuyết phục Alice tin chữ ký đó là giả mạo. IV.3.3. Định lý 3. Giả sử y º xamodp, Alice thực hiện giao thức chối bỏ. Nếu d ạ xeaemodp, D ạ xfafmodp thì khả năng (da-e)f ạ (Da-f)e modp có xác suất là 1 – . Chứng minh: ở đây, ta xét trường hợp rằng Bob có thể thử từ chối chữ ký đúng của anh ta. Trong trường hợp này, chúng ta không thể giả định Bob làm theo giao thức nghĩa là Bob có thể không xây dựng d và D như lý thuyết bởi giao thức, chúng ta chỉ giả định Bob tạo ra 2 giá trị d và D thoả mãn điều kiện trong bước 4, bước 8 và bước 9 của giao thức chối bỏ. Giả thiết chúng ta có: y º xamodp d ạ xeaemodp D ạ xfafmodp (da-e)f º (Da-f)e modp Từ (da-e)f º (Da-f)e modp có: (da-e)f.e º D.a-f modp (da-e)f.e .af º D modp Û D º (dea-e.e)f. af modp Đặt d0 = dea-e.emodp _ d0 chỉ phụ thuộc vào bước 1 – 4 của giao thức. ị D º d0f.af modp Từ d0 = dea-e.emodp ị d0e = da-e.modp ị d = d0e.aemodp áp dụng định lý 1, chúng ta kết luận y là chữ ký đúng của d0 với xác suất 1 –. Nhưng chúng ta đang giả định y là chữ ký đúng của x. Do đó, với xác suất cao chúng ta có: xa º d0a modp ị x = d0 (1) Mặt khác: d ạ xeaemodp (gt) d.a-e ạ xemodp (d.a-e)e ạ xmodp x ạ d e .a-e. e modp mà d0 = d e a-e. e modp (theo trên) ị x ạ d0 (2) Ta thấy (1) và (2) mâu thuẫn . Vì vậy, để (da-e)f ạ (Da-f)e modp với d ạ xeaemodp và D ạ xfafmodp thì xác suất xảy ra là rất cao 1 – . Nghĩa là, Bob chỉ có thể lừa Alice trong trường hợp này với xác suất rất nhỏ là. IV.4. Vấn đề cần giải quyết Ba định lý trong phần này đều mới chỉ đề cập tới một khía cạnh là Bob chấp nhận hay chối bỏ chữ ký của mình mà chưa nói tới một khía cạnh khác là Alice có thể chối bỏ việc mình đã đọc thông báo do Bob gửi. Ta giả định rằng, nếu Bob gửi cho Alice một thông báo đòi nợ nhưng Alice chưa muốn trả hoặc không muốn trả thì cô ta sẽ lờ đi và coi như chưa nhận hay chưa đọc thông báo đó. Vậy Bob có thể làm cách nào để chứng minh Alice đã mở thông báo? Để giải quyết vấn đề trên Bob và Alice thực hiện theo giao thức sau: Trước tiên, Bob và Alice cùng xây dựng khoá K theo lược đồ trao đổi khoá Diffie – Hellman. Giao thức như sau: Giả sử p là số nguyên tố, a là căn nguyên thuỷ của Zp*; a, p là công khai. Cuộc trao đổi khoá giữa Bob và Alice theo các bước sau: Bob chọn ngẫu nhiên aB: 0 Ê aB Ê p – 2 Bob tính aamodp và gửi nó cho Alice Bob chọn ngẫu nhiên aA: 0 Ê aA Ê p – 2 Bob tính aamodp và gửi nó cho Bob Bob tính K = (aa )a modp Alice tính K = (aa )a modp Sau đó, Bob tiếp tục xây dựng một khoá K1, K1 bí mật. Bob có thể xây dựng K1 theo hệ mật đối xứng(DES , AES - đó là hệ một khoá. Các khoá lập và giải mã là như nhau hay dễ dàng xác định lẫn nhau. Các hệ một khoá cung cấp một cách tuyệt vời cho việc mã hoá các tệp riêng của người dùng). Bob và Alice tiến hành tiếp theo các bước dưới đây: Bob dùng K1 để mã hoá thông báo x và chữ ký kèm theo: y = sigB(x) i = eK(x, y) Bob gửi i cho Alice Alice gửi lại thông báo x1 kèm chữ ký y1 = sigA(x1) và mã y1 bằng K: j = eK(y1) rồi gửi cho Bob. Trong đó x1 chứa ngày, giờ, lời yêu cầu và chứa cả i. Bob tính i1 = eK(K1) và gửi nó cho Alice. Khi Bob và Alice tiến hành theo giao thức trên, muốn đọc được thông báo thì Alice phải gửi lại một thông báo (đã được mã hoá bằng khoá K) tới Bob, yêu cầu Bob gửi khoá K1 cho mình bởi vì K1 chỉ mình Bob biết. Bob kiểm tra thông báo của Alice theo thuật toán kiểm tra công khai Ver để xác định thông báo có đúng của Alice gửi hay không? Nếu đúng, anh ta gửi khoá K1 cho Alice mà K1 đã được mã hoá theo K. Bob thực hiện theo cách trên sẽ có đủ chứng cứ để chứng minh trước toà rằng Alice có mở và đọc thông báo anh ta gửi tới bằng cách đưa thông báo có kèm theo chữ ký của Alice và cả ngày giờ Bob nhận được thông báo đó. Chương V Chữ ký người xác nhận được chỉ định V.1. Giới thiệu Phép chứng minh tri thức không là phép chứng minh dùng để thuyết phục bên nhận tin những điều người chứng minh đưa ra là đúng đắn nhưng không cho phép bên nhận thuyết phục người khác. Đây là phép chứng minh rất thú vị trong các hệ thống chứng minh tương tác. Hệ thống chứng minh này chỉ có 2 người tham gia, giả sử là Peggy và Vic. Peggy là người chứng minh và Vic là người kiểm tra. Peggy biết một vài điều trong thực tế và cô ấy muốn chứng minh với Vic rằng cô ấy đúng. Ban đầu cả Peggy và Vic đều có đầu vào x. Peggy thuyết phục Vic rằng x có một vài đặc tính định rõ nhưng cuối giao thức Vic vẫn không biết cách chứng minh x có đặc tính này như thế nào. Ngược lại, chữ ký số tự xác thực (ví dụ chữ ký RSA, Elgamal…) là cực đối lập với phép chứng minh tri thức không. Chữ ký số thực xác thực không chỉ cho phép bên nhận thuyết phục người khác một cách đơn giản bằng cách cung cấp một bản copy của chữ ký mà còn cho phép người bất kỳ đã bị thuyết phục đi thuyết phục người khác. Điều này có nghĩa là bất kỳ người nào cũng có khả năng kiểm tra chữ ký. Chữ ký chống chối bỏ có một vị trí đặc biệt, nó ở một nơi giữa các cực này, bảo vệ cả những lợi ích riêng của người ký trong việc bảo đảm rằng các chữ ký không bị bên nhận dùng sai mục đích cũng như các việc làm của bên nhận để thuyết phục người khác sau này. Bên nhận chữ ký chống chối bỏ bị thuyết phục rằng tất cả nhưng ngưòi nào giữ nó đều có thể thách thức người ký nó và rằng ngưòi ký không thể trả lời sai. Bởi vì người ký luôn luôn có thể thuyết phục một người bất kỳ nào đó rằng một chữ ký tin cậy là tin cậy và chữ ký không tin cậy là không tin cậy. Như vậy người nhận ít nhất yên tâm rằng người ký không thể từ chối một chữ ký tin cậy. Các chữ ký chống chối bỏ có nhiều ứng dụng như trong cuộc bán đấu giá mà sự trả giá được giữ bí mật, bảo vệ sự sao chép phần mềm… Đối với bên nhận, các chữ ký chống chối bỏ có ưu thế hơn so vơi tri thức không ở chỗ bên nhận nắm giữ điều gì đó mà sau này, trong những hoàn cảnh nhất định, có thể được sử dụng để thuyết phục người khác. Ví dụ, Bob ký một thông báo cho phép Alice rút $1000 từ tài khoản của Bob bằng chữ ký chống chối bỏ. Alice muốn rút được tiền thì phải chứng minh chữ ký trên thông báo đúng là của Bob. Nhưng trong nhiều ứng dụng thực tế sự bảo vệ này là quá yếu. Nó dựa trên người ký cộng tác trong việc tiếp tục xác nhận chữ ký. Nếu người ký không thể đáp ứng đầy đủ các điều kiện trong giao thức hỏi đáp hoặc người ký từ chối hợp tác thì bên nhận không thể sử dụng chữ ký. Ví dụ, nếu Bob xây dung câu trả lời d không đúng theo giao thức hoặc Bob từ chối tham gia kiểm tra chữ ký thì Alice không thể sử dụng chữ ký đó để rút tiền. Ví dụ 1: Ông Giám đốc một công ty nào đó gửi một thông báo, có kèm chữ ký của ông ta, tới nhân viên trong công ty trên mạng máy tính. Nội dung thông báo muốn công ty thanh toán một hoá đơn mua hàng, mà thực ra là hoá đơn khống. Anh nhân viên đó thực hiện theo đúng hoá đơn. Nhưng khi Thanh tra kiểm tra và phát hiện hoá đơn đó là giả, ông Giám đốc muốn trắng tội nên ông ta phủ nhận chữ ký điện tử trên thông báo gửi cho anh nhân viên Ví dụ 2: Ông Giám đốc công ty Phần mềm bán phần mềm, có kèm chữ ký điện tử của ông ta được tạo theo thuật toán ký của lược đồ chữ ký chống chối bỏ, trên mạng máy tính. Khách hàng muốn kiểm tra độ tin cậy của chữ ký trên phần mềm thì cần phải có sự cộng tác của người ký. Điều này không thể thực hiện thường xuyên đối với một ông Giám đốc. Vậy phải giải quyết vấn đề này như thế nào? Cơ sở giao thức người xác nhận được chỉ định giải quyết điểm yếu này của chữ ký chống chối bỏ. Nó lôi cuốn 3 phía cùng tham gia: đó là bên nhận chữ ký, người ký và người xác nhận. Bên nhận chữ ký đặt tên là Rita, là phía không cần khóa công khai. Người ký đặt tên là Simon, và người xác nhận, đặt tên là Colin, mỗi người có khóa công khai được phép chấp nhận bởi Rita. Giao thức ký chỉ gồmtương tác giữa Simon và Rita. Nó làm cho Rita bị thuyết phục rằng Simon đã đưa cho cô ấy một chữ ký người xác nhận được chỉ định, đối với thông báo được thỏa thuận, sử dụng khóa riêng của Simon và khóa công khai của colin. Do đó Rita bị thuyết phục rằng chữ ký của Simon trên thông báo này có thể được xác nhận bởi Colin. Giao thức xác nhận bất kỳ sau đó bởi Colin, phụ thuộc vào việc anh ta tiết lộ nhiều như thế nào có thể là tri thức không, người xác nhận được chỉ định hoặc tự xác thực. V.2. Hệ thống cơ sở Ta xây dựng một vị trí đơn giản cho giao thức người xác nhận được chỉ định cơ sở như sau: Simon đưa cho Rita chữ ký số tự xác thực trên thông báo thỏa thuận được ký bởi khóa riêng của anh ta – trừ việc chữ ký là không đầy đủ theo nghĩa nó tùy thuộc vào sự tin cậy của chữ ký chống chối bỏ bất kỳ. Chữ ký chống chối bỏ này được tạo bởi Simon như thể nó được ký bởi Colin và nó tương ứng một cách tin cậy với khóa công khai của Colin. ( Simon có khả năng tạo chữ ký như thế của Colin nhưng chỉ trên các thông báo ngẫu nhiên bởi vì sau khi anh ta chọn chữ ký, anh ta được tự do để chọn giá trị bất kỳ cho thông báo đã được ký). Simon sau đó chứng minh với Rita rằng chữ ký chống chối bỏ đó là tin cậy. Rita không thể chứng minh điều gì về bản sao sự hợp tác của cô ấy với Simon, trừ khi cô ấy nhận được sự giúp đỡ. Nhưng Colin với khóa riêng của mình luôn luôn có thể giúp Rita bằng cách chứng minh với người bất kỳ rằng chữ ký chống chối bỏ mà Simon là tin cậy, do đó thuyết phục họ về sự tin cậy của chữ ký gốc không đầy đủ của Simon. Vì vậy, Colin có thể chứng minh điều đó bằng nhiều cách khác nhau. Sự khéo léo của tiếp cận cấu trúc ở trên là cách để tạo chữ ký tự xác thực tùy thuộc vào chữ ký chống chối bỏ. Điều này có hai khía cạnh. Một mặt, nếu chữ ký chống chối bỏ là không tin cậy và có thể được chọn tự do thì chữ ký tự xác thực sẽ không có giá trị theo nghĩa là bất kỳ người nào cũng có thể dễ dàng tạo ra nó. Mặt khác, nếu chữ chống chối bỏ là tin cậy và ai đó bị thuyết phục về sự tin cậy của nó thì họ sẽ bị thuyết phục về sự tin cậy của chữ ký tự xác thực. Các tính chất này có thể được hoàn thành với các lược đồ chữ ký xác thực dựa trên hàm một chiều. Một dạng điển hình của chữ ký là nơi đầu ra của hàm một chiều được dùng để xác định cái sẽ là thách thức của chứng minh tri thức không. Lược đồ chữ ký như thế được sửa đổi sao cho việc xác định hàm một chiều bao gồm chữ ký chống chối bỏ theo cách thích hợp. Chẳng hạn, đầu ra của hàm một chiều mới có thể được xác định như đầu ra của hàm gốc được XOR với chữ ký chống chối bỏ. Như vậy sự tự do hoàn toàn trong lựa chọn cái gì là chữ ký chống chối bỏ cho phép sự tự do hoàn toàn trong việc chọn đầu ra của hàm một chiều mới, nhưng sự lựa chọn có giới hạn của chữ ký chống chối bỏ có nghĩa là những ràng buộc trên đầu ra của hàm một chiều mới. V.3. Giao thức ký Giao thức này nhằm để cho Simon ký thông báo và thuyết phục Rita rằng chữ ký là tin cậy. Để đơn giản, Simon sẽ sử dụnglược đồ chữ ký RSA với môdun khoá công khai n và số mũ 3. Khoá công khai của Colin sẽ là h = gz, trong đó z là khoá riêng của Colin, g là căn nguyên thuỷ (có bậc cao nhất) của n. Khoá công khai này và tất cả những tính toán trong giao thức là trong nhóm bậc nguyên tố mà ở đó bài toán logarit rời rạc được giả thiết là khó. V.3.1. Tạo khoá Simon chọn n = p.q với p, q là các số nguyên tố lớn khác nhau, f(n) = (p - 1)(q - 1). Cho P = A = Zn và xác định: K = {(n, p, q, 3-1, 3): n = p.q; p, q nguyên tố: 3-1.3 º 1 mod f(n)} Các giá trị n, 3 công khai; các giá trị p, q, 3-1 bí mật. V.3.2. Tạo chữ ký Simon tiến hành ký thông báo m như sau: Simon chọn x ngẫu nhiên và tính: a = gx b = hx Với K = (n, p, q, 3-1, 3) Simon tính chữ ký RSA trên H(a, b) Å F(m) a = (H(a, b) Å F(m)) modn Trong đó H(a, b) là hàm tổ hợp để khử cấu trúc nhân nhưng lại dễ dàng tính ngược; F là hàm Hash thích hợp. Sau đó Simon gửi a, b , a cho Rita. ở giao thức này, Simon đã tạo ra được một chữ ký chống chối bỏ như thể nó được ký bởi Colin. Ta dễ dàng chứng minh được điều này. Ta có: a = gx b = hx mà h = gz ị b = (gz)x = (gx)z = az Mặt khác: z là khoá riêng của Colin Do đó: b = (gx)z là chữ ký chống chối bỏ của Colin, với g là căn nguyên thuỷ có bậc cao nhất của n và z là khoá bí mật. V.3.3. Giao thức kiểm tra ở đây ta giả thiết người ký tham gia vào giao thức kiểm tra, chưa cần sự có mặt của người xác nhận. Giao thức kiểm tra diễn ra với sự cộng tác của Simon (người ký) và Rita (người nhận). Giao thức tiến hành như sau: Rita chọn s, t ngẫu nhiên và tính c = gsht , rồi gửi c cho Simon. Simon chọn ngẫu nhiên và tính: d = g; e = (c.d)x Simon gửi d, e cho Rita. Rita gửi s, t cho Simon Simon kiểm tra nếu gsht = c thì simon gửi cho Rita Rita kiểm tra nếu d = g, e.a = asbt, H(a, b) Å F(m) = a3 modn thì chữ ký là tin cậy. Ngược lại, chữ ký là không tin cậy. Trong bước 5, Rita kiểm tra đẳng thức e.a = asbt tức là kiểm tra b = az. Thật vậy: Từ asbt = e.a ị bt = e.a.a-s (1) mà e = (c.d)x c = gsht d = g ị e = (gs.ht.g )x = gs.x.ht.x.g.x = (gx)s.ht.x.(gx) = as.htx.a (2) Từ (1) và (2) ị bt = as.htx.a . a.a-s = ht.x ị b = hx = (gz)x = (gx)z = az.  Điều này thuyết phục Rita rằng chữ ký này do Simon tạo ra và có thể được kiểm tra bởi Colin. Nhưng Rita không thể dùng kết quả này để chứng minh nó với những người khác. V.4. Giao thức xác nhận Giao thức này để cho người kiểm tra bị thuyết phục rằng chữ ký là phù hợp nhưng cũng không cho phép người kiểm tra đi thuyết phục người khác. Giao thức như sau: Người kiểm tra Veronica chọn u, v ngẫu nhiên và tính: k = gu.av. Rồi gửi k cho Colin. Colin chọn ngẫu nhiên và tính: l = g, n = (k.l)z Sau đ