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

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 đó gửi l, n cho người kiểm tra Veronica. Người kiểm tra gửi u, v cho Colin Colin kiểm tra nếu gu.av = k thì Colin gửi cho người kiểm tra Veronica. Người kiểm tra Veronica sẽ kiểm tra nếu g = l và n.h = hu.bv thì chữ ký là tin cậy. Ngược lại, chữ ký là không tin cậy. ở bước 5, người kiểm tra Veronica kiểm tra đẳng thức n.h = hu.bv cũng chính là kiểm tra b = az. Ta có: n.h = hu.bv ị bv = n. h. h-u (1) Mặt khác: n = (k.l)z k = gu.av l = g ị n = (gu.av.g)z (2) Từ (1) và (2) ị bv = (gu.av.g)z. h. h-u = guz.avz.g.g-uz.g ị bv = av.z ị b = az.  V.5. Giao thức chuyển đổi. Đây là một giao thức xác nhận khác của Colin, giao thức này là cách để Colin chuyển chữ ký người xác nhận được chỉ định thành chữ ký số tự xác thực. ậ đây Colin lập nên một chứng minh không tương tác rằng một người nào đó biết cách biểu diễn b như luỹ thừa của a. ý tưởng cơ bản của sự chuyển đổi này là phải biết cách biểu diễn b như luỹ thừa của a để thành lập cặp (r, y) sao cho ay = r.bF(a, r), trong đó F là hàm một chiều thích hợp. Ta thấy rằng khoá công khai h của Colin không xuất hiện ở đây, h chỉ xuất hiện trong giao thức ký. Do vậy, sau khi Colin thực hiện giao thức chuyển đổi thì bất kỳ người nào cũng có thể kiểm tra chữ ký mà không cần sự có mặt của người ký hay người xác nhận. Giao thức tiến hành như sau: Colin chọn w ngẫu nhiên và tính: r = aw y = w + z.F(a, r) Sau đó gửi r, y cho người kiểm tra Veronica. Người kiểm tra Veronica kiểm tra nếu ay = r. bF(a, r) thì chữ ký là tin cậy. Ngược lại, chữ ký là không tin cậy. Chứng minh: ay = r. bF(a, r) thì chữ ký là tin cậy. Ta có: ay = r. bF(a, r) Û aw + z.F(a, r) = aw.bF(a, r) Û aw.az.F(a, r) = aw.bF(a, r) ị az.F(a, r) = bF(a, r) ị az = b hay b = az ị chữ ký là tin cậy. V.6. Tổng quát Lược đồ chữ ký cơ sở có thể được tổng quát hoá bằng cách bao gồm nhiều người xác nhận. Hơn một khoá công khai của người xác nhận có thể được tổ hợp trong chữ ký chống chối bỏ ( như lấy tích của các khoá công khai), sao cho sự cộng tác của tất cả những người xác nhận sẽ là cần thiết cho sự xác nhận bất kỳ. Càng yêu cầu nhiều người xác thực thì càng khó khăn để nhận sự xác thực, và theo một nghĩa trực quan thì lược đồ chữ ký càng tiếp cận gần hơn với giao thức tri thức không. Và nếu khoá của Simon được kết hợp vào thì kết quả là sự tiết lộ tối thiểu. Chương VI Chữ ký người xác nhận không thể chối bỏ VI.1. Giới thiệu ở các chương trước chúng ta đã làm quen với khái niệm về chữ ký chống chối bỏ và chữ ký người xác nhận. Lược đồ chữ ký người xác nhận đã giải quyết được một số yếu điểm của lược đồ chữ ký chống chối bỏ. Trong lược đồ chữ ký chống chối bỏ chỉ gồm 2 thành phần tham gia là người ký và người xác nhận (hoặc người kiểm tra). Do vậy, nếu người ký từ chối cộng tác đồng nghĩa với việc chữ ký không được kiểm tra. Trong lược đồ chữ ký người xác nhận, khả năng kiểm tra các chữ ký là người đại diện được thêm vào thực thể gọi là người xác nhận. Sự kiểm tra của người xác nhận chính xác hơn người ký, cô ta ( anh ta) có khả năng xác nhận hoặc từ chối độ tin cậy của chữ ký nhưng cô ta (anh ta) không có khả năng giả mạo mọi chữ ký. Trong nhiều lược đồ chữ ký người xác nhận, người ký không thể xác nhận chữ ký của mình là tin cậy. Nếu người xác nhận từ chối cộng tác dẫn đến chữ ký không thể kiểm tra. Trong thực tế, sự tin cậy của người tham gia giữ vai trò rất quan trọng, vì vậy giảm tình trạng rắc rối của bất kỳ người tham gia nào là mong muốn cao dựa vào cả các lý do kỹ thuật và các lý do tiết kiệm. Điều này được thực hiện nếu chữ ký có thể kiểm tra với sự cộng tác của người ký hoặc cộng tác của người xác nhận. Sau đó người sử dụng có thể trả lời người ký sự kiểm tra chữ ký. Như một sự bảo vệ an toàn, người xác nhận còn có thể kiểm tra chữ ký nếu người ký từ chối cộng tác. Chương này giới thiệu lược đồ chữ ký người xác nhận không thể chối bỏ, đưa ra chức năng kiểm tra chữ ký của cả người ký và người xác nhận. Lược đồ này là sự biến đổi của chữ ký người xác nhận. Lược đồ cung cấp một cách linh hoạt đối với người ký và người sử dụng cũng như bao hàm các biến đổi của người xác nhận được chỉ định – người thường được tin tưởng trong thực tế. Sự bổ sung vào lược đồ nhằm mục đích đánh lạc hướng nghĩa là các chữ ký người xác nhận không thể chối bỏ có thể sinh ra với mục đích đánh lừa. Các chữ ký người xác nhận không thể chối bỏ mù quáng có lợi ích trong nhiều ứng dụng như các hệ thống trả tiền trước với mạng lớn của các dịch vụ nơi mà quyền riêng tư của người sử dụng mạng nên được bảo vệ trong khi kiểm duyệt sự mua bán của các dấu hiệu mua bán dài hạn cần phải được ngăn chặn. VI. 2. Mô hình của chữ ký người xác nhận không thể chối bỏ Phần này cung cấp một kiểu đặc trưng của các chữ ký người xác nhận không thể chối bỏ. Nó cung cấp sự định nghĩa không đổi cho các giao thức giải mã sử dụng các khái niệm chuẩn của máy Turing tương tác, hệ thống chứng minh tương tác và tri thức không. Để đơn giản, chúng ta dùng S chỉ người ký, C chỉ người xác nhận và V là người kiểm tra. Lược đồ chữ ký người xác nhận không thể chối bỏ bao gồm các thuật toán và các giao thức sau: - Thuật toán tạo khoá: tạo 2 khoá GENS và GENC nhận 1l là đầu vào (1l nghĩa là một dãy có l số 1), trong đó l là tham số an toàn và lần lượt là 2 cặp đầu ra (SS, PS) và (SC, PC). Thuật toán GENS được thực hiện bởi S, GENC được thực hiện bởi C. (SS, PS), (SC, PC) lần lượt là các cặp khoá bí mật và công khai của S và C. Khoá bí mật S được sử dụng để tạo ra các chữ ký. Ngoài ra SS, SC được lần lượt sử dụng bởi người người ký và người xác nhận trong các giao thức xác nhận và giao thức chối bỏ. - Thuật toán ký đa thức theo xác suất SIGN nhận khoá bí mật SS, thông báo m và các đầu ra của chữ ký s. - Giao thức kiểm tra chữ ký tương tác (CVer , VVer ). Đây là cặp đầu vào của máy Turing thời gian đa thức tương tác giữa người xác nhận và người kiểm tra: ( CVer (SC), VVer ())(m, s, PS, PC) đ v Đầu vào chung gồm thông báo m, chữ ký s, 2 khoá công khai PS, PC. Người xác nhận có SC là đầu vào riêng. Sự trả về của giao thức là giá trị logic v. Nếu đầu ra là 1 nghĩa là chữ ký s tin cậy trên thông báo m, đầu ra là 0 thì ngược lại. - Giao thức kiểm tra chữ ký tương tác (SVer, VVer). Đây là cặp đầu vào của máy Turing thời gian đa thức tương tác giữa người ký và người kiểm tra: (SVer(SS), VVer())(m, s, PS, PC) đ v Đầu vào chung gồm thông báo m, chữ ký s và 2 khoá công khai PS, PC. Người ký có SS là đầu vào riêng. Sự trả về của giao thức là giá trị logic v. Nếu đầu ra là 1 nghĩa là chữ ký s tin cậy trên thông báo m, đầu ra là 0 thì ngược lại. * Các yêu cầu an toàn của các thành phần trong giao thức: - Tính không thể phân biệt được của chữ ký: Chữ ký mô phỏng SIGNsim được tạo bằng thuật toán thời gian đa thức theo xác suất, nó nhận thông báo m, 2 khoá công khai PS, PC là đầu vào và cho ra một phần tử được gọi là chữ ký mô phỏng trong không gian ký. Chữ ký mô phỏng này không thể phân biệt so với chữ ký thực đối với bất kỳ người nào mà chỉ hiểu các thông tin công khai. Dựa vào một thông báo và một chữ ký có nghĩa, một người nào đó không thể tự mình xác định được chữ ký là tin cậy. - Tính không thể giả mạo của chữ ký: Không tồn tại thuật toán thời gian đa thức nhận khoá công khai PS của người ký; khoá bí mật SC, khoá công khai PC của người xác nhận và truy cập đến chữ ký người tin cậy SIGN, cho ra một cặp thông báo- chữ ký (m’, s’) không được tạo bởi SIGN với xác suất đáng kể. - Tính chính xác của sự kiểm tra: Không lưu ý tới sự dính líu của một trong hai người là người ký hoặc người xác nhận, các giao thức kiểm tra là nhất quán. Ngoại trừ xác suất không đáng kể, giao thức kiểm tra trả về 1 như là đầu ra của người kiểm tra nếu cặp thông báo – chữ ký (m, s) tin cậy, hoặc là 0 nếu (m, s) là không tin cậy. VI.3. Các lược đồ chữ ký và phép chứng minh tương tác VI.3.1. Ký hiệu + Ký hiệu ỗỗ biểu thị sự ghép nối của 2 dãy nhị phân. + Lấy p, q là các số nguyên tố lớn và xem rằng p - 1 chia hết cho q + Cho g là phần tử sinh của phân nhóm nhân G của Z bậc q. + Hàm Hash chịu đựng sự va chạm H: {0, 1} đ Z (k =ẵqẵ, k > 160). VI.3.2. Lược đồ chữ ký Schnorr Định nghĩa : Cho y = gx modp, chữ ký Schnorr trên thông báo m kiểm tra sử dụng khoá công khai (g, y) là cặp (u, v) ẻ Z ´ Z thoả mãn u = H(mỗỗyỗỗgỗỗgvyu). Chữ ký như vậy có thể được tính nếu biết khoá bí mật x bằng cách chọn r ẻ Z (chọn r ngẫu nhiên thuộc Z ) và tính: u = H(mỗỗyỗỗgỗỗgr) và v = r – ux mod q. Để đơn giản, ta dùng S(x, y)(m) biểu thị chữ ký Schnorr trên thông báo m đã được tạo với khoá bí mật x và có thể kiểm tra với khoá công khai y. VI.3.3. Chữ ký Chaum-Petersen dựa vào đẳng thức của thuật toán rời rạc Định nghĩa 2: Cho y1 = g và y2 = g, chữ ký Chaum-Petersen dựa vào đẳng thức của thuật toán rời rạc y1 và y2 với cơ số là g1, g2 trên thông báo m là cặp (u, v) ẻ Z ´ Z thoả mãn: u = H(mỗỗy1ỗỗy2ỗỗg1ỗỗg2ỗỗgyỗỗgy) Dưới mô hình Oracle ngẫu nhiên, chữ ký như thế có thể được thành lập nếu biết khoá bí mật x thoả mãn y1 = g và y2 = g. Chữ ký sau đó được tính bằng cách chọn r ẻ Z, tính: u = H(mỗỗy1ỗỗy2ỗỗg1ỗỗg2ỗỗgyỗỗgy) và v = r – ux mod q. Ta có thể viết lại u như sau: Từ v = r – ux modq ị r = v + ux modq Theo giả thiết: y1 = g ị gy= g(g)u = g = g Tương tự: y2 = g ị gy= g(g)u = g = g Vậy: u = H(mỗỗy1ỗỗy2ỗỗg1ỗỗg2ỗỗgỗỗg) Để đơn giản, ta dùng CP(x, y1, y2, g1, g2)(m) biểu thị chữ ký Chaum-Petersen trên thông báo m đã được tạo ra với khoá bí mật x thoả mãn đẳng thức của thuật toán rời rạc y1, y2 với cơ số lần lượt là g1, g2. VI.3.4. Phép chứng minh ký tương tác Fujioka-Okamoto-Ohta của đẳng thức Phép chứng minh ký đẳng thức log(y1) º log(y2) là giao thức hoặc chứng minh log(y1) º log(y2) hoặc chứng minh log(y1) ạ log(y2). Giao thức của Fujioka-Okamoto-Ohta chứng minh đẳng thức (hoặc không là đẳng thức) của thuật toán rời rạc y1, y2 với cơ số lần lượt là g1, g2. Giao thức như sau: V (người kiểm tra) C (người xác nhận) u, v ẻ Z a = gymodp k, k’, w ẻ Z r1 = g; r2 = g r = g; r= g a = gy? z = k – (v + w) c z’ = k’ – (v + w) k gy = r1 gr = r gr = r = ( g2z y º r2) Ta có thể diễn giải giao thức trên thành các bước sau: Người kiểm tra V chọn u, v ngẫu nhiên ẻ Z và tính a = gymodp, rồi gửi a cho người xác nhận C Người xác nhận C chọn k, k’, w ngẫu nhiên ẻ Zvà tính r1 = g; r2 = g; r = g; r= g Sau đó gửi r1, r2, r1’, r2’ cho V Khi nhận được r1, r2, r1’, r2’ do C gửi, V gửi lại C hai giá trị u, v Người xác nhận nhận được u, v thì kiểm tra đẳng thức a = gymodp. Nếu đúng, C gửi cho V hai giá trị z, z’ được tính như sau: z = k – (v + w) c z’ = k’ – (v + w) k Người kiểm tra V sẽ kiểm tra xem các đẳng thức sau có xảy ra hay không? gy = r1 gr = r gr = r = ( g2z y º r2) Kết thúc giao thức đầu ra của người kiểm tra là . Phép chứng minh trả về 1 nếu log(y1) º log(y2), trả về 0 nếu log(y1) ạ log(y2). Giao thức được ký hiệu như sau: Bi – Proof[log(y1) º log(y2)] Chú ý: ở đây y1, y2 được tính như sau: y1 = g1c mod p, y2 = g2c mod p VI.4. Cấu trúc lược đồ chữ ký người xác nhận không thể chối bỏ VI.4.1. Tạo khoá + Người ký chọn s ẻ Z, thiết lập cặp khoá bí mật và công khai (S S, PS) với SS = s, PS = gs modp. + Người xác nhận chọn c ẻ Z, thiết lập cặp khoá bí mật và công khai (SC, PC ) với SC = c, PC = gc modp. VI.4.2. Tạo chữ ký Để tạo chữ ký s trên thông báo m, người ký S chọn r ẻ Z, tạo: a : = gr, as : = P, as+c : = (PSPC), gs : = PS, gs+c : =PSPC Sau đó S tính s1 = CP(r, a, as+c, g, gs+c)(m) và s2 = S(sr, g, as)(s1). ị Chữ ký s của người ký trên thông báo m là: s = (s1, s2). VI.4.3. Kiểm tra chữ ký Đầu tiên người kiểm tra sẽ kiểm tra độ tin cậy của (s1, s2) với s1 là chữ ký Chaum-Petersen đẳng thức của thuật toán rời rạc tin cậy trên thông báo m và s2 là chữ ký Schnorr tin cậy trên s1. Người kiểm tra dừng nếu mọi sự kiểm tra đều dẫn đến kết quả không tin cậy. Ngược lại, người kiểm tra tiếp tục kiểm tra chữ ký như sau: - Đối với người ký: Đầu ra v của người kiểm tra của (SVer(SS), VVer())(m, s, PS, PC) được tính: v = Bi-Proof [log(as) º logg(gs)] Trong giao thức này người ký đóng vai trò người chứng minh. - Đối với người xác nhận: Đầu ra v của người kiểm tra của (CVer(SC), VVer())(m, s, PS, PC) được tính: v = Bi-Proof [logg (gc ) º log(ac)] Trong giao thức phép chứng minh ký này, người xác nhận giữ nhiệm vụ như người chứng minh và ac = as+c /as. Trong cả 2 sự kiểm tra của người ký và người xác nhận, người kiểm tra chấp nhận chữ ký khi và chỉ khi v =1. VI.4.4. Giải thích cấu trúc bằng trực giác Ta thấy rằng trong cấu trúc này, người ký có khoá bí mật s, khoá công khai gs, người xác nhận có khoá bí mật c, khoá công khai gc. Giá trị gs+c được tính: gs+c =PS.PC = gsgc (vì gs = PS, gc = PC ) Chữ ký người xác nhận không thể chối bỏ s gồm 2 chữ ký là s1, s2. Trong đó s1 là chữ ký Chaum-Petersen được tạo ra với khoá bí mật r1 = r, kiểm tra với khoá công khai a = gr và as+c = g; s2 là chữ ký Schnorr được tạo với khoá bí mật r2 = rs, kiểm tra với khoá công khai as = g. Bằng trực giác thấy rằng, chữ ký là luận chứng của tri thức khoá bí mật. Như vậy nếu một người nào đó có thể tạo ra s1, s2 thì người đó phải có tri thức của r1, r2. Nếu người đó có thể chứng minh rằng r2 = r1s nghĩa là chữ ký đó là tin cậy. Có 2 cách để chứng minh r2 = r1s như sau: * Cách 1: Chứng minh rằng: logg(gs) º log(as). Cách này yêu cầu tri thức của logg (gs ), vì vậy chỉ có thể thực hiện bởi người ký. * Cách 2: Chứng minh rằng: logg(gc ) = log(as+c /as). Cách này yêu cầu tri thức của logg(gc), vì vậy chỉ có thể được thực hiện bởi người xác nhận. VI.5. Phép phân tích an toàn Để chỉ ra rằng cấu trúc là an toàn, chúng ta giả sử rằng lược đồ chữ ký Schnorr và chữ ký Chaum-Petersen dựa vào đẳng thức của thuật toán rời rạc là an toàn. Phép chứng minh ký tương tác Fujioka-Okamoto-Ohta của đẳng thức là an toàn, đúng đắn và chứng cớ không thể phân biệt được. Phép chứng minh an toàn này có thể được chứng minh trong mô hình Oracle ngẫu nhiên. Dưới đây là các chứng minh chỉ ra rằng cấu trúc của chữ ký người xác nhận không thể chối bỏ là không thể giả mạo, không thể phân biệt được và sự kiểm tra chữ ký là nhất quán. VI.5.1.Chữ ký không thể giả mạo Định nghĩa. Đặc tính không thể giả mạo chữ ký vững chắc. Ngoại trừ với xác suất không đáng kể, không tồn tại thuật toán thời gian đa thức theo xác suất A mà có thể sinh ra chữ ký s trên thông báo đặc biệt m, kiểm tra với khoá công khai y khi truy cập đến chữ ký Oracle của tất cả khoá công khai y* cho tất cả các thông báo cần truy cập đến y để được thông báo m. ở đây khi mọi thông báo m*, chữ ký Oracle của khoá công khai y* sinh ra chữ ký s* của m* kiểm tra với y*. Bằng trực giác, đặc tính không thể giả mạo chữ ký vững chắc có nghĩa rằng khi truy cập đến chữ ký Oracle của tất cả các chữ ký công khai tin cậy cho tất cả các thông báo cần chữ ký mong muốn, nó là không thể sinh ra chữ ký s dưới khoá công khai mong muốn, trên thông báo mong muốn m. Định nghĩa này thuyết phục hơn khái niệm chữ ký an toàn chuẩn. Nó là bản sao tương đương của an toàn đối lập với các lựa chọn thích hợp đặc tính tấn công văn bản mật mã của lược đồ giải mã. Do đó lược đồ chữ ký là không thể giả mạo vững chắc nếu nó thoả mãn đặc tính không thể giả mạo chữ ký vững chắc. Bổ đề: Chữ ký s = (s1, s2) là chữ ký qua được sự kiểm tra chỉ nếu s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1) và r1 = r2. Chứng minh: Nếu s là tin cậy, s1 và s2 được thành lập là s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1). Còn lại chứng tỏ r1 = r2. Chúng ta giả sử rằng s khác 0. Chữ ký s được coi là tin cậy nếu nó trải qua một trong hai bước thử kiểm tra, đó là kiểm tra đối với người xác thực và kiểm tra đối với người ký. Kiểm tra đối với người xác nhận phải thực hiện phép chứng minh ký Bi – Proof [logg(gc) º log(ac)]. Do đó nó chỉ ra rằng ac = ac hoặc ac = as+c/ as. Hơn nữa s1, s2 là đúng ị tồn tại r1 và sr2, xem rằng: as+c =g = g(s+c)r , as = gsr ị ac = g= g/ g ị g =g Vì s ạ 0 ị r1 = r2. Với trường hợp kiểm tra đối với người ký tương tự như trên. Định lý: Trong mô hình Oracle ngẫu nhiên, chữ ký người xác nhận không thể chối bỏ là không thể giả mạo. Chứng minh: Theo bổ đề trên, chữ ký s+ là tin cậy nếu s+1 = CP(r1, a, as+c, g, gs+c)(m), s+2 = S(sr2, g, as)(s+1) và r1 = r2. Điều này có nghĩa rằng nếu tồn tại thời gian đa thức đối thủ A thành công tạo ra cả s và s, sau đó A phải biết r1, r2s và khoá bí mật s. Vì vậy chỉ có một viễn cảnh rằng A có thể giả mạo s+ mà không cần truy cập đến khoá bí mật s để đạt được hoặc s hoặc s. Giả sử A đạt được s, s hình thành từ chữ ký s* = (s,s). Theo bổ đề trên, điều này có nghĩa là s, s đã đựoc tạo ra cùng một khoá bí mật r2s ị A biết bí mật để tạo s. Điều này mâu thuẫn với đặc tính không thể giả mạo vững chắc của s2.  VI.5.2. Chữ ký không thể phân biệt Định nghĩa 4: (chữ ký bị giả mạo) Cho x, gy = gy và gz = gz, chữ ký giả mạo s* = (s, s) trên thông báo m được tính: s= CP(x, X, Xy+c, g, gy+c) và s= S(z, g, yz)( s) Trong đó c, gc là khoá bí mật và công khai của người xác nhận, X = gx, Xy+c = g và gy+c = gygc. Chữ ký như trên được đặt dưới mô hình Oracle ngẫu nhiên. Phần đầu của chữ ký là s có thể luôn luôn được thành lập khi biết x. Phần tiếp theo của chữ ký là s, chữ ký Schnorr kiểm tra dùng khoá công khai gz = gz. Chữ ký Schnorr (u,v) được giả mạo trong mô hình Oracle ngẫu nhiên. Điều này được thực hiện bằng cách chọn u,v ngẫu nhiên và Oracle ngẫu nhiên giả mạo trong cách mà nó có các đầu ra u với đầu vào (mỗỗyỗỗgỗỗgvyu). Định lý: Trong mô hình Oracle ngẫu nhiên, nếu tồn tại người giả mạo A mà có thể phân biệt chữ ký tin cậy từ chữ ký giả mạo đã được tạo ra dùng định nghĩa ở trên trong thời gian đa thức theo xác suất thì có một thuật toán giải quyết vấn đề Diffie – Hellman trong thời gian đa thức theo xác suất. Chứng minh: Giả sử có một đối thủ A mà có thể phân biệt chữ ký tin cậy s từ chữ ký giả mạo s* dùng thông tin công khai. Ký hiệu tập hợp của tất cả (a, gb, gcẵab = c) là D và ( a, gb, gc ẵaẻR Z ) là X. Lấy t* = (x1, gy, gz ) ẻ D, t+ = (x2, gy, gz )ẻ X. Theo định nghĩa của chữ ký giả mạo, A có thể tạo ra 2 chữ ký giả mạo s*, s+ lần lượt từ t*, t+. ở đay khoá công khai của người ký là gy. Theo bổ đề trong phần [VI. 5. 1], s* là chữ ký tin cậy, s+ là chữ ký không tin cậy. Ngoài ra sự thuận lợi của A trong phân biệt s* từ s+ là không đáng kể hơn phân biệt giữa t* và t+ . Vì vậy nếu A có khả năng nhận biết chữ ký chính xác từ s* và s+, chúng ta nói rằng t* hoặc t+ hình thành từ D. A đã giải quyết được vấn đề của Diffie – Hellman.   VI.5.3. Tính nhất quán của kiểm tra chữ ký Theo bổ đề phần [VI. 5. 1], chữ ký là tin cậy chỉ khi hoặc as+c /as = ac hoặc as = as. Nó không phức tạp để chỉ ra sự tương quan đối lập, nói cách khác nếu đạt được hoặc as+c /as = ac hoặc as = as thì s1 là phép chứng minh hợp lý của tri thức và đẳng thức, s2 là chữ ký tin cậy, s là chữ ký đúng. Vì vậy tính nhất quán của sự kiểm tra chữ ký tuân theo tính đúng đắn và hợp lý của phép chứng minh ký của tri thức. VI. 6. Chữ ký người xác nhận không thể chối bỏ mù quáng và các ứng dụng VI. 6. 1. Cấu trúc Giao thức chữ ký người xác nhận không thể chối bỏ mù quáng gồm đặc thù của chữ ký Schnorr mù quáng và đặc thù của chữ ký Chaum – Petersen của đẳng thức mù quáng thực hiện song song với nhau. Cấu trúc như sau: Người nhận Người ký p, r1, r2 ẻZ r, r1, r2 ẻ Z a = gr as = gsr as+c = g w2 = g w1 = g W1 = g = = = w2 = w2p. g w1 = w1p. g = W1p. g v = H(m ẵẵẵẵẵẵẵẵw2ẵẵw1ẵẵ) u = v/p v1 = r1 – u(r) v2 = r2 – u(rs) = v1p + r1 = v2p + r2 s+1 = (v, , , , w1, 1) s+2 = (v, , , w2) Trong cấu trúc này, chữ ký người xác nhận không thể chối bỏ mù quáng là s = (s+1, s+2), chúng ta đánh lạc hướng một đặc thù tương tác của giao thức tạo chữ ký từ tạo s1 = CP(r, a, as+c, g, gs+c)(m), s2 = S(sr, g, as)(s1) để tạo s+1 = CP(rp, b, bs+c, g, gs+c)(m), s+2 = S(srp, g, bs)(s+1) trong đó b = ap , bs = a và bs+c = a. Người trung gian tức người nhận chữ ký trong giao thức biết giá trị p. Điều này không phức tạp để kiểm tra s+1 là chữ ký Chaum – Petersen tin cậy trên thông báo m và s+2 là chữ ký Schnorr tin cậy trên thông báo (mùùs+1). Do đó s+ = (s+1, s+2) là chữ ký người xác nhận không thể chối bỏ tin cậy. VI. 6. 2. Lược đồ trả trước có thể leo thang Chúng ta cũng đã khá quen với các hệ thống trả tiền trước để mua một sản phẩm nào đó như đặt mua tạp chí, truyền hình cáp… Hiện nay, cùng với sự phát triển mạnh mẽ của công nghệ thông tin và sự giao lưu thông tin ngày càng trở nên phổ biến trên các mạng truyền thông thì người ta cũng nghĩ tới các hoạt động kinh doanh trên mạng Internet. Các hoạt động thương mại của các dịch vụ trực tuyến trên Internet đòi hỏi phải nhanh và có các phương thức trả tiền đạt hiệu quả cao. Giải pháp phổ biến là micropayment nghĩa là người sử dụng trả một số tiền nhỏ cho tong sản phẩm mua trực tuyến. Giải pháp lựa chọn là trả trước, người sử dụng trả trước với dịch vụ một số tiền cố định gọi là lệ phí hàng năm. Người sử dụng sau đó được cấp một giấy chứng nhận trả trước mà cho phép truy cập đến mọi sản phẩm của dịch vụ. Sự thuận lợi của dịch vụ trả trước trên micropayment là nó giảm một lượng lớn quá trình tiến hành công việc mua bán của sự giao dịch khi mua một sản phẩm định giá nhỏ. Trong thực tế, không xảy ra việc người cung cấp dịch vụ có thể cung cấp tát cả các dịch vụ mong muốn tới người sử dụng. Ngoài ra nó bất tiện với người sử dụng khi phải giữ mã số của giấy chứng nhận trả trước, nếu mỗi sản phẩm người sử dụng phải giữ một giấy chứng nhận trả trước thì điều này sẽ gây phiền toái cho người sử dụng. Giải pháp mong muốn là sẽ liên hiệp các công ty lớn của những người cung cấp dịch vụ để cung cấp nhiều loại khác nhau của các dịch vụ trực tuyến. Trong thứ tự truy cập đến các dịch vụ này, mỗi người sử dụng chỉ cần một giấy chứng nhận đặt trước với cái mà anh ta đã trả tiền lệ phí cố định hàng năm. Khi đó người sử dụng có thể truy cập đến tất cả các dịch vụ cung cấp bởi bất kỳ thành phần nào trong liên hiệp các công ty. Chữ ký mù quáng có thể dùng để thiết kế một hệ thống trả trước với quyền riêng tư của người sử dụng. Trong mô hình này, giấy chứng nhận trả trước là đưa ra chữ ký người xác nhận không thể chối bỏ mù quáng bởi người quản lý của liên hiệp các công ty. Để truy cập tới các dịch vụ trực tuyến, người sử dụng chứng tỏ giấy chứng nhận trả trước tin cậy với người cung cấp dịch vụ, người có vai trò người xác nhận trong lược đồ chữ ký. Thuận lợi chính của cách này là giảm trách nhiệm một lượng lớn quá trình tiến hành công việc mua bán của việc trả một lượng nhỏ trong khi, thậm chí cung cấp cả quyền riêng tư cho người sử dụng. Kết luận Ngày nay, cùng với sự phát triển của khoa học công nghệ hiện đại và Công nghệ thông tin, ngành mật mã đã có những bước phát triển mạnh mẽ, đạt được nhiều kết quả lý thuyết sâu sắc và tạo cơ sở cho việc phát triển các giải pháp bảo mật, an toàn thông tin trong mọi lĩnh vực hoạt động của con người. Đặc biệt là những ưu điểm của chữ ký số. Chữ ký số được biết đến khi sự trao đổi thông tin ngày càng phổ biến trên các mạng truyền thông ở nơi mà chữ ký tay không thể phát huy tác dụng. Trong đồ án này, tôi đã tìm hiểu về lược đồ chữ ký số người xác nhận không thể chối bỏ. Tuy còn nhiều điểm cần phải nghiên cứu và hoàn thiện nhưng do thời gian và trình độ hiểu biết còn hạn chế nên không tránh khỏi những nhược điểm, rất mong sự góp ý của các Thầy, Cô và các bạn. Cuối cùng, em xin chân thành cảm ơn thầy giáo TS. Nguyễn Ngọc Cương đã tận tình chỉ bảo, hướng dẫn giúp em hoàn thành đồ án này. Tài liệu tham khảo TS. Nguyễn Ngọc Cương – “Bài giảng An toàn thông tin” – 1999 Nguyễn Thị Mười Phương – “Luận văn thạc sĩ “- 2003 3. D.R Stinson – “Cryptography Theory and Practice”, CRC press – 1995 4. Moti Yung – “Weaknesses of undeniable Signature Schemes” 5. David Chaum – “Designated Confirmer Signatures” 4. Khanh Nguyen, Yi Mu, Vijay Varadharajan – “Undeniable Confirmer Signature” Mục lục Lời nhận xét Mục lục Đặt vấn đề 1 Chương I: Tổng quan về ngôn ngữ C 4 I.1. Lịch sử hình thành và phát triển 4 I.2. Các tính chất đặc trưng của ngôn ngữ 5 Chương II: Chữ ký số 7 II. 1. Giới thiệu chung về chữ ký số 7 II.2. Định nghĩa lược đồ chữ ký số 8 II.3. Một số lược đồ chữ ký số 9 II.3.1. Lược đồ chữ ký RSA 9 II.3.2.Lược đồ chữ ký ElGamal 11 Chương III: Hàm Hash 15 III.1. Giới thiệu 15 III.2. Định nghĩa 16 III.3. Một số hàm Hash sử dụng trong lược đồ chữ ký số 16 III.3.1.Các hàm Hash đơn giản 16 III.3.2. Kỹ thuật khối xích 18 III.3.3. Các hàm Hash mở rộng 18 III.3.4. Hàm Hash MD4 19 Chương IV: Chữ ký chống chối bỏ 25 IV.1. Giới thiệu 25 IV.2. Lược đồ chữ ký số chống chối bỏ 25 IV.2.1. Thuật toán ký 25 IV.2.2. Giao thức kiểm tra 26 IV.2.3. Giao thức chối bỏ 27 IV.3. Các định lý 29 IV.3.1. Định lý 1 29 IV.3.2. Định lý 2 30 IV.3.3. Định lý 3 31 IV.4. Vấn đề cần giải quyết 33 Chương V: Chữ ký người xác nhận được chỉ định 35 V.1. Giới thiệu 35 V.2. Hệ thống cơ sở 37 V.3. Giao thức ký 38 V.3.1. Tạo khoá 38 V.3.2. Tạo chữ ký 38 V.3.3. Giao thức kiểm tra 39 V.4. Giao thức xác nhận 40 V.5. Giao thức chuyển đổi 41 V.6. Tổng quát 42 Chương VI: Chữ ký người xác nhận không thể chối bỏ 43 VI.1. Giới thiệu 43 VI.2. Mô hình của chữ ký người xác nhận chống chối bỏ 44 VI.3. Các lược đồ chữ ký và phép chứng minh ký tương tác 46 VI.3.1. Ký hiệu 46 VI.3.2. Lược đồ chữ ký Schnorr 46 VI.3.3. Chữ ký Chaum – Petersen dựa vào đẳng thức của thuật toán rời rạc 46 VI.3.4. Phép chứng minh ký tương tác Fujioka – Okamoto – Ohto của đẳng thức 47 VI.4. Cấu trúc 49 VI.4.1. Tạo khoá 49 VI.4.2. Tạo chữ ký 49 VI.4.3. Kiểm tra chữ ký 49 VI.4.4. Giải thích cấu trúc của lược đồ chữ ký bằng trực giác 50 VI.5. Phép phân tích an toàn 50 VI.5.1. Chữ kýkhông thể giả mạo 51 VI.5.2. Chữ ký không thể phân biệt được 52 VI.5.3. Tính nhất quán của kiểm tra chữ ký 53 VI.6. Chữ ký người xác nhận không thể chối bỏ mù quáng và các ứng dụng 54 VI.6.1. Cấu trúc 54 VI.6.2Lược đồ trả trước có thể leo thang 55 Kết luận 57 Tài liệu tham khảo 58