Chữ ký số, sơ đồ ký Chaum-Van Antwerpen

CHỮ KÝ SỐ.SƠ ĐỒ KÝ CHAUM-VAN ANTWERPEN Giáo viên hướng dẫn : Trần Ngọc Thái Nhóm sinh viên : Nguyễn Thị Vân Nguyễn Thị Anh Thư B NỘI DUNG CHÍNH Sơ đồ ký Chữ ký không thể phủ nhận và không thể chối bỏ Sơ đồ chữ ký của Chaum-van Antverpen Ví dụ I. Sơ đồ ký  Một sơ đồ chữ ký là một bộ (P,A,K,S,V)  Trong đó +P là một tập hữu hạn các thông báo có thể có +A là tập hữu hạn các chữ ký có thể có+K là một tập hữu hạn các khoá, mỗi khoá K  K gồm có 2 phần tử K=(K’,K”), K’ là khoá bí mật dành cho việc ký K” là khoá công khai dành cho việc kiểm thử chữ ký Với mỗi K=(K’,K”) trong S có thuật toán ký  sigK’ : P  A và trong V có một thuật toán kiểm thử verK’ : P X A  {đúng, sai} thoả mãn điều kiện sau với mọi thông báo x  P và mọi chữ ký y  A II. Chữ ký không thể phủ nhận và không thể chối bỏ + Ở một số sơ đồ ký điện tử việc kiểm thử tính đúng đắn là do người nhận thực hiện. Như vậy có thể xảy ra việc cả văn bản cùng chữ ký được sao chép & phát tán cho nhiều người mà ko được phép của người gửi. + Người ta đưa ra các sơ đồ ký không phủ định được với yêu cầu là chữ ký không thể được kiểm thử nếu không có sự hợp tác của người ký. + Sự hợp tác đó được thực hiện thông qua giao thức đòi hỏi và trả lời giữa người nhận và người gửi (cũng là người ký ) gọi là giao thức kiểm thử. + Khi chữ ký đòi hỏi được xác nhận bằng giao thức kiểm thử thì làm thế nào để tránh việc người ký chối bỏ chữ ký của mình bằng cách tuyên bố chữ ký đó là giả mạo? + Cần có thêm một giao thức chối bỏ, thông qua đó người ký có thể chứng minh một chữ ký không phải của mình đúng thực là giả mạo. Nếu anh ta từ chối không tham gia giao thức đó thì có bằng chứng để chứng tỏ anh ta không chứng minh được đó là chữ ký giả tức không chối bỏ được chữ ký của mình. Như vậy một sơ đồ ký không phủ định được gồm 3 phần : thuật toán ký, giao thức kiểm thử và giao thức chối bỏ. III. Sơ đồ chữ ký của Chaum-van Antverpen Một chủ thể A chọn một số nguyên tố dạng Sophie Germain p = 2q+1 trong đó q là số nguyên tố chọn   Zp* là một phần tử cấp q Gọi G là nhóm con (theo cấp nhân) cấp q sinh bởi  của Zp* Sơ đồ chữ ký Chaum-van Antverpen của A gồm có+ P = A = G+ Cặp khoá K = (K’,K”) gồm khoá bí mật K’=a khoá công khai K” ={ (p, , a, ):  = a (mod p) } Thuật toán ký A ký trên văn bản x  P = G với chữ ký y = sigK’(x) = xa (mod p). Giao thức kiểm thử Với văn bản x và chữ ký y người nhận B cùng người ký A thực hiện giao thức kiểm thử sau: 1. B chọn ngẫu nhiên 2 số e1,e2  Zq* , tính c = ye1e2 (mod p) và gửi cho A 2. A tính d  cinv(a) (mod q) (mod p) và gửi d cho B. 3. B chấp nhận y là chữ ký của A trên x nếu d  xe1  e2 (mod p) Giao thức chối bỏ 1. B chọn ngẫu nhiên 2 số e1,e2  Zq* , tính c = ye1e2 (mod p) và gửi cho A 2. A tính d = cinv(a) (mod q) (mod p) và gửi d cho B. 3. B thử điều kiện d  xe1  e2 (mod p). 4. B chọn tiếp 2 số f1,f2  Zq* , tính C = yf1f2 (mod p) và gửi C cho A 5. A tính D = Cinv(a) (mod q) (mod p) và gửi D cho B 6. B tính thử điều kiện D  xf1  f2 (mod p) 7. B kết luận y là chữ ký giả mạo nếu (d*-e2)f1  (D*-f2)e1 (mod p). Kiểm chứng các giao thức Giao thức kiểm thử : Ta có d  cinv(a) (mod q) (mod p)  ye1*inv(a)e2*inv(a) (mod p). Mà  = a (mod p) => inv(a)   (mod p) Tương tự y = xa (mod p) => y inv(a)  x (mod p) => d  xe1  e2 (mod p) Vậy nếu y đùng là chữ ký của A trên x thì B chấp nhận y là chữ ký của A theo giao thức kiểm thử là đúng Giao thức chối bỏ Giả sử y  xa (mod p) => tương tự như trên ta có d  xe1  e2 (mod p) => B sẽ thực hiện các bất đồng dư thức từ bước 3 đến bước 6 của giao thức Vì  = a (mod p) => (d*-e2)f1 (( ye1e2)inv(a) -e2 )f1 (modp)  yinv(a)e1f1e2inv(a)f1 -e2f(modp)  yinv(a)e1f1 Tương tự (D*-f2)e1  yinv(a)e1f1 Như vậy có thể kết luận y là chữ ký giả mạo của A trên x là chính xác IV. Ví dụ Giả sử lấy p=467. Khi đó q=233 , lấy  = 4 chọn a=101 ->  = a mod 467 = 449 * B muốn xác nhận chữ ký y: A ký trên văn bản x=119 với chữ ký y = 119101 mod 467 = 129 B chọn giá trị ngẫu nhiên e1 = 38 & e2 = 397 -> c = 13 gửi cho A A sẽ đáp lại với d=9 và gửi cho B B kiểm tra bằng cách xác minh lại 119384397  9 (mod 467) -> B chấp nhận y là chữ ký của A trên văn bản 119 * Giao thức chối bỏ : Giả sử A gửi văn bản x=286 với chữ ký y=831. B chọn ngẫu nhiên e1 = 45 & e2 = 237 rồi tính c=305 gửi cho A 2. A tính d = 109 rồi gửi lại cho B 3. B tính 286454237 mod 467 = 149  1094. B chọn ngẫu nhiên 2 số f1 = 125 & f2 = 9, tính C=270 rồi gửi cho A 5. A tính D=68 rồi gửi cho B6. B tính 28612549 mod 467 = 25  687. Vì (109*4-237)125 = 188 mod 467 & (68*4-9)45 = 188 mod 467=> B kết luận y không phải là chữ ký của A