Đồ án Chữ ký không chối bỏ được và ứng dụng

vào bji : là bit thứ i trong khối thứ j Å : là phép cộng modulo 2 Sơ đồ hàm Hash sử dụng phép XOR. Khối 1: b11 b12 b1n Khối 2: b21 b22 b2n Khối m: bm1 bm2 bmn Mã Hash: C1 C2 Cn Ci là bit kiểm tra tính chẵn lẻ cho vị trí thứ i khi ta chia tệp dữ liệu thành từng khối, mỗi khối con vị trí. Nó có tác dụng như sự kiểm tra tổng thể tính toàn vẹn của dữ liệu. Khi mã hóa một thông báo dài thì ta sử dụng mode CBC (The Cipher Block Chaining), thực hiện như sau: Giả sử thông báo X được chia thành các khối 64 bit liên tiếp X= X1X2 Xn Khi đó mã Hash C sẽ là: C = XNH = X1Å X2 ÅÅ Xn Sau đó mã hóa toàn bộ thông báo nối với mã Hash theo mode CBC sản sinh ra bản mã. Y1Y2 YN+1 2.1.2. Kỹ thuật khối xích : Người ta đầu tiên đề xuất kỹ thuật mật mã xích chuỗi nhưng không có khóa bí mật là Rabin. Kỹ thuật này được thực hiện như sau : Chia thông báo M thành các khối có cỡ cố định là M1, M2, , MN, sử dụng hệ mã thuận tiện như DES để tính mã Hash như sau : H0 = giá trị ban đầu Hi = EMi(Hi-1), i = G = HN 2.2. Các hàm Hash mở rộng: Ở trên, ta đề cập đến hàm Hash có nhiều đầu vào hữu hạn. Tiếp theo ta sẽ đề cập tới loại hàm Hash mạnh với đầu vào vô hạn thu được do mở rộng một hàm Hash mạnh có đầu vào độ dài hữu hạn. Hàm này sẽ cho phép ký các thông báo có độ dài tùy ý. Giả sử h: (Z2 )m ® (Z2 )t là một hàm Hash mạnh, trong đó m ³ t + 1 ta sẽ xây dựng một hàm Hash mạnh : h*: X ® (Z2 )t, trong đó = È(Z2 )i Xét trường hợp m ³ t + 2 Giả sử x Î X, vậy thì tồn tại n để x Î(Z2 )n, n ³ m. Ký hiệu : |x| là độ dài của x tính theo bit. Khi đó, |x| = n. Ký hiệu : x || y là dãy bit thu được do nối x với y. Giả sử |x| = n ³ m. Ta có thể biểu diễn x như sau: x = x1 ÷÷ x2÷÷ ÷÷ xk Trong đó = = = = m – t – 1 và = m – t – 1 – d, 0 £ d £ m – t – 2 Þ ³ 1 và m – t – 1 ³ 1, k ³ 2. Khi đó: k = + 1 Thuật toán xây dựng h thành h* được mô tả như sau : Cho i = 1 tới k-1 gán yi = xi ; yk = xk || 0d (0d là dãy có d số 0. Khi đó yk dài m-t-1) yk+1 là biểu diễn nhị phân của d (|yk+1| = m-t-1) g1 = h( 0t+1 çç y1) ( = t, 0t+1 çç y1 dài m) Cho i=1 tới k thực hiện gi+1 = h( gi çç1ççyi+1 ) a. h*(x) = gk+1 Ký hiệu y(x) = y1 || y2 || || yk+1 Ta thấy rằng y(x) ¹ y(x’) nếu x ¹ x’ Xét trường hợp m=t+1 Cũng như trên, ta giả sử |x| = n >m Ta xác định f như sau: f(0) = 0; f(1) = 01; Thuật toán xây dựng h* khi m=t+1 như sau : Cho y= y1,y2, , yk =11 || f(x1) || f(x2) f(xn) (x1 là một bit) g1 = h( 0t çç y1) ( = m – t ) Cho i=1 tới k -1 thực hiện gi+1 = h( gi ççyi+1 ) ( = m – t - 1) 4. h*(x) = gk* Ngoài ra còn có một số hàm Hash khác như hàm Hash MD4 và hàm Hash MD5. Chương 3 CHỮ KÝ CHỐNG CHỐI BỎ 1. Giới thiệu: Chữ ký không chối bỏ được công bố bởi Chaum và Van Antverpen vào năm 1989. Nó có một nét riêng mới lạ và 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ý, A(giả sử người ký là A). Sự bảo vệ này của A đề 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ụ: A 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à B không biết. Người mua sẽ kiểm tra chữ ký kèm theo nhờ thuật toán kiểm tra công khai Ver và công nhận chữ ký đó là đúng. Vì như chúng ta đã biết bản sao của chữ ký số đồng nhất với bản gốc. Đương nhiên như vậy A sẽ bị mất bản quyền. Để tránh điều bất tiện đó A đã dùng chữ ký khô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ỏ. 2. Lược đồ chống chối bỏ: 2.1. Thuật toán ký: * Tạo khóa: 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ử bậc q( Nếu a0 là phần tử nguyên thủy 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 Z*p bậc q (G bao gồm các thặng dư bậc hai 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 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 : A chọn e1,e2 ngẫu nhiên, e1, e2 Î Zp*. A tính c = y b modp gửi nó cho B. B tính d= c modp và gửi nó cho A. A chấp nhận chữ đú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 lấy p=2q+1 với q là số nguyên tố lẻ. Trong trường hợp này, phân nhóm G tồn tại. Ví dụ: giả sử ta lấy p = 467, từ 2 là căn nguyên thủy => 22 = 4 là thặng dư bậc hai theo modun 267 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 A sẽ ký thông báo x=119 với chữ ký: y = xa modp = 119101 mod467 = 129 Giả sử B muốn kiểm tra chữ ký y, B chọn ngẫu nhiên e1 = 38,e2 = 397. Ta có: c = y b modp = 12938 449397 mod467 = 13 B gửi c=13 cho A và A tính d theo: d = c modp Þ d = 13101 mod233 mod467 (q = (p - 1)/2 = (467 –1 )/2 = 233) Þ d = 9 B muốn kiểm tra chữ ký y theo bước 4. Có: xamodp = 11938 4397 mod467 = 9 Þ d º xamodp => B chấp nhận chữ ký là đúng 2.3. Giao thức chối bỏ Một vấn đề đặt ra, nếu sự cộng tác của chủ thể ký là cần thiết trong việc kiểm tra chữ ký thì điều gì đã ngăn cản anh ta trong việc từ chối chữ ký do anh ta tạo ra. Tất nhiên, anh ta có thể cho rằng chữ ký đúng đó là giả mạo và từ chối kiểm tra nó hoặc anh ta 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 đó chủ thể ký có thể chứng minh được chữ ký đó là giả mạo. (Nếu anh ta từ chối thực hiện 1 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à của anh ta và anh ta đang cố gắng từ chối chữ ký của mình). Giao thức chối bỏ gồm hai tiến trình của giao thức kiểm tra và có các bước sau: B chọn e1, e2 ngẫu nhiên, e1, e2 Î Zq*. B tính c = y b modp và gửi nó cho A A tính d = c modp và gửi nó cho B B kiểm tra d ¹ xamodp. B chọn f1,f2 ngẫu nhiên, f1, f2 Î Zq*. B tính C = yb modp và gửi nó cho A A tính D = c modp và gửi nó cho B B kiểm tra D ¹ xamodp B kết luận rằng y là chữ ký giả mạo khi và chỉ khi (da) º (Da) modp Ví dụ: Lấy p=467, a = 4, a = 101, b = 449. Ký trên thông báo x=286 với chữ ký y= 83 (là giả mạo). A muốn thuyết phục B rằng chữ ký đó là không đúng. Vậy phải thực hiện như sau: Chọn ngẫu nhiên e1 = 45, e2 = 237. B tính c=305 và A trả lời với d= 109. B tính 28645. 4237mod467 = 149. Vì 149 ¹ 109 nên ta phải thực hiện giao thức chối bỏ B chọn tiếp f1 = 125, f2 = 9, ngẫu nhiên, B tính C=270 và A trả lời với D=68. B tính: 286125.49mod467 = 25. Vì 25 ¹ 68 nên B thực hiện tiếp bước cuối cùng của giao thứ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 B tin chắc rằng đó là chữ ký không đúng Bây giờ vấn đề đặt ra là: - A có thuyết phục được B rằng chữ ký không đúng đó là giả mạo - A không thể làm cho B bị thuyết phục rằng chữ kí đó đúng là giả mạo ngoại trừ xác suất rất nhỏ. 3. Các định lý: 3.1.Định lý 1: Nếu y ¹ xa modp B sẽ chấp nhận y như là một chữ ký đúng của x với xác suất 1/q. Chứng minh: Trước tiên, ta nhận xét rằng mỗi yêu cầu c sẽ xảy ra 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ử thuộc nhóm nhân G có bậc nguyên tố lẻ q). Khi A nhận yêu cầu c, A không biết B đã 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 A d Î G có thể đúng 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 của 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 của p. Ta xét 2 đồng dư sau: c º yebe modp (1) d º xeaemodp (2) (1)Û 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 modulo q ¹ 0 nên hệ có 1 nghiệm duy nhất nghĩa là 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 1 cặp (e1, e2) trong các cặp (e1, e2) bậc q. Vậy xác suất A đưa cho B câu trả lời d mà sẽ được kiểm tra 1/q, đồng nghĩa với việc B chấp nhận y là chữ ký của A với xác suất 1/q. 3.2. Định lý 2: Khi A và B 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 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ì A có thể thuyết phục được B tin chữ ký đó là giả mạo. 3.3. Định lý 3: Giả sử y º xamodp B thực hiện giao thức chối bỏ. Nếu d ¹ xeae modp, D ¹ xfafmodp thì khả năng (da-e)f ¹ (Da-f)e modp có xác suất là 1-1/q. Ở đây ta xét trường hợp A có thể từ chối chữ ký đúng của anh ta. Trong trường hợp này, chúng ta có thể không giả định A làm theo giao thức nghĩa là A không xây dựng d và D như lý thuyết bởi giao thức, chúng ta chỉ giả định A tạo ra 2 giá trị d và D thỏa mãn điều kiện bước 4, 8, 9 của giao thức chối bỏ. Giả thuyế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 = de.a-e.emodp Þ d0e = da-e.modp Þ d = d0e.aemodp Áp dụng định lý 1, chúng ta kết luận y đúng là chữ ký của d0 với xác suất 1-1/q. 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-1/q. Nghĩa là A có thể lừa B trong trường hợp này có xác suất rất nhỏ 1/q. 3.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à A chấp nhận hay chối bỏ chữ ký của mình chưa nói đến một khía cạnh khác là B có thể chối bỏ việc mình đã đọc thông báo do A gửi. Ta giả định rằng, nếu A gửi cho B một thông báo đòi nợ nhưng B chưa muốn trả hoặc không muốn trả thì anh ta sẽ lờ đi coi như chưa nhận hay chưa đọc thông báo đó. Vậy A có thể làm cách nào để chứng minh B đã mở thông báo? Để giải quyết vấn đề cả A và B thực hiện theo giao thức sau: Trước tiên, A và B phải xây dựng khóa K theo lược đồ trao đổi khóa Diffie- Hellman. Giao thức như sau: Giả sử p là số nguyên tố, a là căn nguyên thủy của Zp*; a, p là công khai cuộc trao đổi khóa giữa A và B diễn ra như sau: A chọn ngẫu nhiên aA : 0 ≤ aA ≤ p-2. A tính aamod p rồi gửi nó cho B. B chọn ngẫu nhiên aB : 0 ≤ aB ≤ p-2. B tính aa và gửi nó cho A. A tính K = (aa ) amod p. B tính K = (aa ) amod p. Sau đó, A tiếp tục xây dựng một khóa K1, K1 bí mật. A có thể xây dựng K1 theo hệ mật đối xứng (DES, AES – đó là một hệ khóa. Các khóa lập mã và giải mã là như nhau hay dễ dàng xác định lẫn nhau. Các hệ một khóa cung cấp một cách tuyệt vời cho việc mã hóa các tệp riêng của người dùng). Avà B tiến hành theo các bước sau đây: A dùng K1 để mã hóa thông báo x và chữ ký kèm theo: y = sigA(x) i = eK(x, y) A gửi i cho B B gửi lại thông báo x1 kèm theo chữ ký y1 = sigB(x1) và mã y1 bằng K: j=eK(y1) rồi gửi cho A. Trong đó x1 chứa ngày, giờ, lời yêu cầu và chứa cả i. A tính i1 = eK(K1) và gửi nó cho B. Khi A và B tiến hành theo giao thức trên, muốn đọc được thông thì B phải gửi lại một thông báo (đã được mã hóa bằng khóa K) tới A, yêu cầu A gửi khóa K1 cho mình, bởi vì K1 chỉ mình A biết. A kiểm tra thông báo của B theo thuật toán kiểm tra công khai Bver để xác định thông báo có đúng là của B gửi hay không? Nếu đúng, anh ta gửi K1 cho B mà K1 đã được mã hóa theo K. A thực hiện theo cách trên sẽ có đủ chứng cứ để chứng minh trước tòa rằng B có mở và đọc thông báo anh ta gửi tới bằng cách đưa ra thông báo có kèm theo chữ ký của B và cả ngày, giờ B đọc thông báo đó. Chương 4 CHỮ KÝ NGƯỜI XÁC NHẬN ĐƯỢC CHỈ ĐỊNH 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 đi thuyết phục người khác. Đây là phép chứng minh rất thú vị trong 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ả Paggy và Vic đều có đầu vào x. Pegyy 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ó những đặc tính như thế nào. Chữ ký 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ố tự 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 mà 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ý không thể trả lời sai. Bởi 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 có thể yên tâm rằng người ký không thể từ chối một chữ ký tin cậy. Đố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ể 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ý (nếu Bob xây dựng 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 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 hóa đơn mua hàng, thực ra là hóa đơn khống. Anh nhân viên đó thực hiện theo đúng hóa đơn. Nhưng khi thanh tra kiểm tra và phát hiện hóa đơn 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 theo chữ ký điện tử của ông ta được tạo ra theo thuật toán ký của lược đồ 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ý gồm tươ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. Giao thức xác nhận sau đó bởi Colin phụ thuộc vào việc anh ta tiết lộ 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. 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ể đượ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 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à 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 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ữ ký chống chối bỏ là tin cậy thì 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. 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ụng lược đồ chữ ký RSA với modun khóa công khai n và số mũ 3. Khóa công khai của Colin sẽ là: h=gz, trong đó z là khóa riêng của Colin, g là căn nguyên thủy (có bậc cao nhất) của n. Khóa 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ó. 3.1. Tạo khóa: 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. 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 rất 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 chữ ký chống chối bỏ như thể đượ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à khóa 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 thủy có bậc cao nhất của n và z là khóa bí mật. 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 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. 4. Giao xác thứ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 Veron 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. Rồi gửi l, n cho Veron. Người kiểm tra gửi u, v cho Colin. Colin kiểm tra nếu k= gu .av thì Colin gửi cho người kiểm tra Veron. Người kiểm tra Veron 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 Veron 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.  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ư lũy 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ư lũy 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 khóa 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 ngẫu nhiên w rồi tính: r = aw y = w + z.F(a, r). Sau đó gửi r, y cho người kiểm tra Veron. Người kiểm tra Veron kiểm tra nếu ay = r. bF(a, r) thì chữ ký là tin cậy. Ngược lại là chữ ký 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. 6. Tổng quát: Lược đồ chữ ký cơ sở có thể được tổng quát hóa bằng cách bao gồm nhiều người xác nhận. Hơn một khóa 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 khóa 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. Chương 5 CHỮ KÝ NGƯỜI XÁC NHẬN KHÔNG THỂ CHỐI BỎ 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ỏ 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 nghiã với 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 n