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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG ---------- o0o ---------- CHỮ KÝ KHÔNG CHỐI BỎ ĐƯỢC VÀ ỨNG DỤNG ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công Nghệ Thông Tin Giáo viên hướng dẫn : TS. Lê Phê Đô Sinh viên thực hiện : Nguyễn Văn Tân Mã số sinh viên: 10416 HẢI PHÒNG - 2007 MỤC LỤC ĐẶT VẤN ĐỀ 4 Chương 1 : CƠ SỞ LÝ THUYẾT 6 1. Cơ sở toán học: 6 1.1. Phép chia hết: 6 1.2. Không chia hết: 6 1.3. Ước số: 6 1.4. Nguyên tố cùng nhau: 6 1.5. Số nguyên tố: 6 1.6. Định nghĩa hàm phi Euler: 6 1.7. Đồng dư : 7 1.8. Số nghịch đảo: 7 1.9. Nhóm nhân(thặng dư thu gọn): 7 1.10. Cấp của nhóm nhân: 7 1.11. Cấp của một số thuộc Z*n : 7 1.12 Định nghĩa nhóm Cyclic : 7 1.13 Định nghĩa thặng dư bậc 2: 8 1.14 Số Blum: 8 2. Tìm hiểu mật mã 8 2.1. Giới thiệu: 8 2.2. Sơ đồ hệ thống mật mã 8 2.3. Mật mã khóa đối xứng 9 2.4. Mã khóa công khai: 15 Chương 2 : CHỮ KÝ SỐ 19 I. Chữ ký số 19 1. Giới thiệu chung về chữ ký số: 19 2. Định nghĩa lược đồ chữ ký: 20 2.1. Lược đồ chữ ký RSA: 20 2.2. Lược đồ chữ ký ElGamal: 21 II. Hàm Hash 23 1. Giới thiệu: 23 2. Định nghĩa: 23 2.1. Một số hàm Hash sử dụng trong chữ ký số: 24 2.2. Các hàm Hash mở rộng: 25 Chương 3 : CHỮ KÝ CHỐNG CHỐI BỎ 27 1. Giới thiệu: 27 2. Lược đồ chống chối bỏ: 27 3. Các định lý: 29 Chương 4: CHỮ KÝ NGƯỜI XÁC NHẬN ĐƯỢC CHỈ ĐỊNH 34 1. Giới thiệu: 34 2. Hệ thống cơ sở: 35 3. Giao thức ký: 36 4. Giao thức nhận: 38 5. Giao thức chuyển đổi: 38 6. Tổng quát: 39 Chương 5: CHỮ KÝ NGƯỜI XÁC NHẬN KHÔNG THỂ CHỐI BỎ 40 1.Giới thiệu: 40 2. Mô hình của chữ ký người xác nhận không thể chối bỏ: 41 3. Các lược đồ chữ ký và phép chứng minh tương tác: 42 4. Cấu trúc lược đồ chữ ký người xác nhận không thể chối bỏ: 44 5. Phép phân tích an toàn: 45 6. Chữ ký người xác nhận không thể chối bỏ mù quáng và các ứng dụng 48 CHƯƠNG TRÌNH…………………………………………………………..50 KẾT LUẬN 62 TÀI LIỆU THAM KHẢO 63 ĐẶT VẤN ĐỀ Khi ứng dụng trên mạng máy tính càng trở lên phổ biến, thuận lợi và quan trọng thì yêu cầu về an toàn mạng, an ninh dữ liệu mạng ngày càng trở lên cấp bách và cần thiết. Nguồn tài nguyên mạng rất dễ bị đánh cắp hoặc phá hỏng nếu không có một cơ chế bảo mật cho chúng hoặc sử dụng những cơ chế bảo mật quá lỏng lẻo. Thông tin trên mạng, dù đang truyền hay được lưu trữ đều cần được bảo vệ. Các thông tin ấy phải được giữ bí mật; Cho phép người ta kiểm tra để tin tưởng rằng chúng không bị sửa đổi so với dạng nguyên thủy của mình và chúng đúng là của người nhận gửi nó cho ta. Mạng máy tính có đặc điểm là nhiều người sử dụng, nhiều người cùng khai thác kho tài nguyên, đặc biệt là tài nguyên thông tin và người sử dụng thường phân tán về mặt địa lí. Các điểm này thể hiện lợi ích to lớn của mạng thông tin máy tính đồng thời cũng là điều kiện thuận lợi cho những kẻ muốn phá hoại an toàn thông tin trên mạng máy tính. Do đó cách tốt nhất để bảo vệ thông tin là mã hóa thông tin trước khi gửi đi. Mục tiêu cơ bản của mật mã là cho phép hai người, giả sử là A và B, liên lạc qua kênh không an toàn theo cách mà đối thủ O (được nói đến như người thám mã) khó có thể hiểu cái gì đang được nói. Kênh này có thể là đường điện thoại hoặc mạng máy tính. Thông tin A muốn gửi đến B sẽ được gọi là “bản rõ” (plaintext), có thể là bất kì tài liệu nào có cấu trúc tùy ý. A sẽ mã bản rõ bằng khóa xác định trước, và gửi bản mã thu được qua kênh không an toàn. O dù thu trộm được bản mã trên kênh nhưng khó có thể hiểu bản mã đó là gì nhưng B là người biết khóa mã nên có thể giải mã và thiết lập lại bản rõ. Có hai loại hệ mật gồm hệ mật mã khóa bí mật và hệ mật mã khóa công khai. Trong hệ mật mã khóa công khai, hai người muốn trao đổi thông tin với nhau phải thỏa thuận với nhau một cách bí mật khóa k. Trong hệ mật này có hai hàm lập mã ek và hàm giải mã dk . Nếu tiết lộ khóa k sẽ làm cho hệ thống không an toàn. Trong thực tế, Độ an toàn hệ thống chính là độ an toàn tính toán. Một hệ mật là “an toàn tính toán” nếu phương pháp tốt nhất đã biết để phá nó yêu cầu một số lớn không hợp lý thời gian tính toán, nghĩa là quá trình thực hiện tính toán cực kỳ phức tạp, phức tạp đến mức ta coi “không thể được”. Hệ mã khóa công khai đã đáp ứng được yêu cầu đó. Ý tưởng của hệ mã khóa công khai là ở chỗ nó có thể tìm ra một hệ mã khó có thể tính toán xác định dk khi biết ek. quy tắc mã ek có thể công khai. Hàm mã hóa công khai ek phải dễ dàng tính toán nhưng việc giải mã phải khó đối với bất kì người nào ngoài người lập mã. Tính chất dễ tính toán và khó đảo ngược này thường được gọi là tính chất một chiều. Điều này bảo đảm tính bí mật cao. Như chúng ta đã biết, trong cách thức giao dịch truyền thống, thông báo được truyền đi trong giao dịch thường dưới dạng viết tay hoặc đánh máy kèm theo chữ ký(viết tay) của người gửi ở bên dưới văn bản. Chữ ký đó là bằng chứng xác nhận thông báo đúng là của người ký, tức là chủ thể giao dịch. Chữ ký viết tay có nhiều ưu điểm đó là dễ kiểm thử, không sao chép được chữ ký của một người là giống nhau trên nhiều văn bản… Ngày nay, cùng với sự phát triển của khoa học và công nghệ thông tin đặc biệt là sự bùng nổ của mạng máy tính thì nhu cầu trao đổi thông tin trên mạng ngày càng phổ biến. Khi chúng ta chuyển sang cách thức truyền tin bằng các phương tiện hiện đại, các thông báo được truyền đi trên các mạng truyền tin số hóa, bản thân các thông báo cũng biểu diễn duới dạng số hóa tức là dưới dạng bít nhị phân, “chữ ký” nếu có cũng ở dưới dạng các dãy bit, thì các mối quan hệ tự nhiên kể trên không còn giữ được nữa. Chẳng hạn, “chữ ký” của một người gửi trên những văn bản khác nhau phải thể hiện được sự gắn kết trách nhiệm của người gửi đối với từng văn bản đó thì tất yếu phải khác nhau chứ không thể là những đoạn bit giống nhau như các chữ ký giống nhau trên các văn bản thông thường. Chữ ký viết tay có thể được kiểm thử bằng cách so sánh với nguyên mẫu, nhưng “chữ ký” điện tử thì không thể có “nguyên mẫu” để mà so sánh, việc kiểm thử phải được thực hiện bằng những thuật toán đặc biệt. Một vấn đề nữa đó là chữ ký điện tử có thể sao chép tùy ý khó có thể phân biệt được bản sao và bản gốc nên có thể có nguy cơ dùng lại nhiều lần. Vậy làm thế nào để ngăn chặn nguy cơ đó và làm thế nào để có thể ngăn cản được người ký chối bỏ chữ ký của mình hoặc người kiểm tra chối bỏ việc mình đã nhận đọc thông báo. Trước những yêu cầu đó, để nâng cao tính an toàn của chữ ký điện tử và để nâng cao trách nhiệm của người ký và người kiểm tra, đòi hỏi người ta phải đưa ra một lược đồ chữ ký sử dụng các giao thức để có thể khắc phục được những nhược điểm của chữ ký số. Đó là lý do em chọn đề tài “Các Chữ ký không chối bỏ được và ứng dụng”làm đề tài nghiên cứu của mình. Trong đồ án này em đi sâu tìm hiểu về lược đồ chữ ký không chối bỏ, lược đồ chữ ký chống chối bỏ có người xác nhận và người xác nhận không thể chối bỏ. Có nghĩa là chữ ký có thể được kiểm tra mà không cần sự cộng tác của người ký mà là một người thứ ba đó là người xác nhận. Chương 1 CƠ SỞ LÝ THUYẾT 1. Cơ sở toán học: 1.1. Phép chia hết: - ĐN: cho a,b Î Z a. Ta nói a chia hết cho b nếu $ số c sao cho a = b.c ; Ký hiệu: b|a - Tính chất: a,b,c Î Z a|a a|b , b|c → a|c a|b , a|c → a|(x.b+y.c) x,y Î Z a|b , b|a → a ≡ ±b 1.2. Không chia hết: - ĐN: Phép chia gọi là không chia hết nếu tồn tại số r (0 < r < b) sao cho: a = b.q + r Với: q là phần nguyên r là phần dư 1.3. Ước số: - ĐN: Ước số của a và b là c nếu c|a và c|b - Ước số chung lớn nhất : Là số lớn nhất mà a và b chia hết Ký hiệu : c = gcd(a,b) ; (great common divisor) - Bội số chung nhỏ nhất : d là BSCNN của a và b nếu c mà a|c , b|c → d|c Ký hiệu: d = lcm(a,b) ; (least common multiple) - Tính chất: lcm(a,b) = a.b/gcd(a,b) 1.4. Nguyên tố cùng nhau: - ĐN: a,b gọi là hai nguyên tố cùng nhau khi gcd(a,b) = 1 đơn giản (a,b) = 1 1.5. Số nguyên tố: - ĐN: Số nguyên tố là số chỉ chia hết cho 1 và chính nó - Tính chất: Giả sử p là số nguyên tố và p|a.b thì p|a hoặc p|b hoặc cả hai đều chia hết cho p. Có vô số số nguyên tố. 1.6. Định nghĩa hàm phi Euler: - ĐN : Với n≥1 chúng ta gọi f (n) là tập các số nguyên tố cùng nhau với n nằm trong khoảng [1,n] - Tính chất : Nếu p là số nguyên tố → f (p) = p-1 Nếu p=m.n , gcd(m,n)=1 → f (p)= f (m).f (n) Nếu n = p1e1.p2e2.p3e3... → f (n)=n.(1-1/p1).(1-1/p2).(1-1/p3)... 1.7. Đồng dư : - ĐN : Cho n là số nguyên dương, ta nói hai số nguyên a và b là đồng dư với nhau theo modulo n nếu n|(a-b) Ký hiệu : a≡b(modn) - Tính chất : a≡a(modn) a≡b(modn) ↔ b≡a(modn) a≡b(modn) , b≡c(modn) → a≡c(modn) a≡a1(modn) , b≡b1(modn) a+b≡a1+b1(modn) a.b≡a1.b1(modn) 1.8. Số nghịch đảo: - ĐN: Cho a Î Zn. Một số nguyên x Î Zn gọi là nghịch đảo của a theo modn nếu a.x≡1modn. Nếu có số x như vậy thì nó là duy nhất và ta nói a là khả nghịch, nghịch đảo của a ký hiệu là a-1. -Tính chất: a Zn, a khả nghịch khi và chỉ khi gcd(a,n)=1. 1.9. Nhóm nhân(thặng dư thu gọn): - ĐN: Nhóm nhân của Zn ký hiệu là Z*n là tập hợp các phần tử sao cho gcd(a,n)=1 Với n là số nguyên tố thì Z*n={ a Î Zn | 1≤a≤n-1} 1.10. Cấp của nhóm nhân: - ĐN : Cấp của Z*n là số phần tử của Z*n , |Z*n| = f (n) 1.11. Cấp của một số thuộc Z*n : - ĐN : Cho a Î Zn khi đó cấp của a kí hiệu là ord(a) là một số nguyên dương t nhỏ nhất sao cho at = 1(modn) 1.12 Định nghĩa nhóm Cyclic : - ĐN : Cho αÎ Z*n nếu cấp của α là f (n) khi đó α gọi là phần tử sinh hay phần tử nguyên thuỷ của Z*n, và nếu Z*n tồn tại một phần tử sinh thì nó sẽ được gọi là Cyclic - Tính chất : Nếu α là phần tử sinh của Z*n thì Z*n = { α i modn | 0 ≤ i ≤ f (n)} α là phần tử sinh của tập Z*n khi đó b= αi modn cũng là phần tử sinh của Z*n khi và chỉ khi gcd(i, f (n))=1. Nếu p là số nguyên tố thì Z*p chắc chắn có phần tử sinh 1.13 Định nghĩa thặng dư bậc 2: - ĐN: Cho a Î Z*n gọi a là thặng dư bậc 2 theo modulo n nếu tồn tại x Z*n sao cho x2≡a(modn) và nếu không tồn tại thì gọi a là bất thặng dư bậc 2 theo modulo n. Tập các thặng dư bậc 2 ký hiệu là và các tập bất thặng dư bậc 2 ký hiệu là . 1.14 Số Blum: - ĐN: Số Blum là một hợp tử n=p.q nếu p,q là hai số nguyên tố khác nhau và đồng dư với 3mod4. 2. Tìm hiểu mật mã 2.1. Giới thiệu: Mật mã đã được sử dụng từ rất sớm, khi con người biết trao đổi thông tin cho nhau và trải qua bao nhiêu năm nó đã được phát triển từ những hình thức sơ khai cho đến hiện đại và tinh vi. Mật mã được sử dụng trong rất nhiều lĩnh vực của con người và các quốc gia, đặc biệt trong các lĩnh vực quân sự, chính trị, ngoại giao và thương mại. Mục đích của mật mã là tạo ra khả năng trao đổi thông tin trên một kênh thông tin chung cho những đối tượng cùng tham gia trao đổi thông tin và không muốn một đối tượng thứ ba khác biết được những thông tin mà họ trao đổi. Khi một đối tượng A muốn gửi một thông điệp cho những người nhận, A sẽ phải mã hóa thông điệp và gửi đi, những người nhận được thông điệp mã hóa muốn biết được nội dung thì phải giải mã thông điệp mã hóa. Các đối tượng trao đổi thông tin cho nhau phải thỏa thuận với nhau về cách thức mã hóa và giải mã, quan trọng hơn là khóa mật mã đã sử dụng trong quá trình mã hóa và giải mã, nó phải tuyệt đối được giữ bí mật. Một đối tượng thứ ba mặc dù có biết được nhưng sẽ không biết được nội dung thông điệp đã mã hóa. Có hai phương pháp mã hóa dữ liệu là Mã hóa khóa đối xứng và Mã hóa khóa công khai. 2.2. Sơ đồ hệ thống mật mã Là một bộ năm (P, C, K, E, D) trong đó: + P là một tập hữu hạn các bản rõ. + C là một tập hữu hạn các bản mã. + K là một tập hữu hạn các khoá. + Với mỗi k є K, có một hàm lập mã ek є E ek: P → C và một hàm giải mã dk є D dk: C → P sao cho dk(ek(x)) = x với mọi x є P 2.3. Mật mã khóa đối xứng Phương pháp mã hóa đối xứng (symmetric cryptography) còn được gọi là mã hóa khóa bí mật (secret key cryptography). Với phương pháp này, người gửi và người nhận sẽ dùng chung một khóa để mã hóa và giải mã thông điệp. Trước khi mã hóa thông điệp gửi đi, hai bên gửi và nhận phải có khóa chung và phải thống nhất thuật toán dùng để mã hóa và giải mã. Có nhiều thuật toán ứng dụng cho mã hóa khóa bí mật DES - Data Encrytion Standard, 3DES - triple-strength DES, RC2 - Rons Cipher 2 và RC4, v.v... và sơ khai nhất là các hệ mật mã cổ điển. Nhược điểm chính của phương pháp này là khóa được truyền trên kênh an toàn nên chi phí tốn kém và không kip thời. Ưu điểm là tốc độ mã hóa và giải mã rất nhanh. Một số hệ mật mã cổ điển 2.3.1. Mã dịch chuyển: Định nghĩa: Mã dịch chuyển: (P, C, K, E, D) P = C = K = Z26 với k є K, định nghĩa ek(x) = (x + k) mod 26 dk(y) = (y – k) mod 26 (x, y є Z26) Ví dụ: Dùng khoá k = 9 để mã hoá dòng thư: “toinaydichoi” dòng thư đó tương ứng với dòng số t o i n a y d i c h o i 19 14 8 12 0 24 3 8 2 7 14 8 qua phép mã hoá e9 sẽ được: 2 23 17 22 9 7 12 17 11 16 23 17 c x r w j h m r l q x r bản mã sẽ là: “qnwcxrcqdkjh” Nhận được bản mã đó, dùng d9 để nhận được bản rõ. Cách đây 2000 năm mã dịch chuyển đã được Julius Ceasar sử dụng, với khoá k=3 mã địch chuyển được gọi là mã Ceasar. Tập khoá phụ thuộc vào Zm với m là số khoá có thể. Trong tiếng Anh tập khoá chỉ có 26 khoá có thể, việc thám mã có thể được thực hiện bằng cách duyệt tuần tự 26 khoá đó, vì vậy độ an toàn của mã dịch chuyển rất thấp. 2.3.2. Mã thay thế: Định nghĩa Mã thay thế: (P, C, K, E, D) P = C = Z26, K = S (Z26) Với mỗi π є K, tức là một hoán vị trên Z26, ta xác định eπ(x) = π (x) dπ(y) = π -1(y) với x, y є Z26, π -1 là nghịch đảo của л Ví dụ: π được cho bởi (ở đây ta viết chữ cái thay cho các con số thuộc Z26): bản rõ: “toinaydichoi” sẽ được mã hoá thành bản mã (với khoá π): “mfzsxdazygfz” Dễ xác định được π -1, và do đó từ bản mã ta tìm được bản rõ. Mã thay thế có tập hợp khoá khá lớn - bằng số các hoán vị trên bảng chữ cái, tức số các hoán vị trên Z26, hay là 26! > 4.1026. Việc duyệt toàn bộ các hoán vị để thám mã là rất khó, ngay cả đối với máy tính. Tuy nhiên, bằng phương pháp thống kê, ta có thể dễ dàng thám được các bản mã loại này, và do đó mã thay thế cũng không thể được xem là an toàn. 2.3.3. Mã Anffine: Định nghĩa Mã Anffine: (P, C, K, E, D) P = C = Z26, K = { (a, b) є Z26 x Z26 : (a, 26) = 1 } với mỗi k = (a, b) є K ta định nghĩa: ek(x) = ax + b mod 26 dk(y) = a-1(y – b) mod 26 trong đó x, y є Z26 Ví dụ: Lấy k = (5, 6). Bản rõ: “toinaydichoi” t o i n a y d i c h o i x 19 14 8 13 0 14 3 8 2 7 14 8 y=5x + 6 mod 26 y 23 24 20 19 6 24 21 20 16 15 24 20 x y u t g y v u q p y u Bản mã: “xyutgyvuqpyu” Thuật toán giải mã trong trường hợp này có dạng: dk(y) = 21(y − 6) mod 26 Với mã Apphin, số các khoá có thể có bằng (số các số ≤ 26 và nguyên tố với 26) × 26, tức là 12 × 26 = 312. Việc thử tất cả các khoá để thám mã trong trường hợp này tuy khá mất thì giờ nếu tính bằng tay, nhưng không khó khăn gì nếu dùng máy tính. Do vậy, mã Apphin cũng không phải là mã an toàn. 2.3.4. Mã Vigenère: Định nghĩa Mã Vigenere: (P, C, K, E, D) Cho m là số nguyên dương. P = C = K = Z26m với mỗi khoá k = (k1, k2,…,km) є K có: ek(x1, x2,…, xm) = (x1 + k1, x2 + k2,…, xm + km) dk(y1, y2,…, ym) = (y1 – k1, y2 – k2,…, ym – km) các phép cộng phép trừ đều lấy theo modulo 26 Ví dụ: Giả sử m = 6 và khoá k là từ CIPHER - tức k=(2, 8, 15, 7, 4, 17). Bản rõ: “toinaydichoi” t o i n a y d i c h o i x 19 14 8 13 0 24 3 8 2 7 14 8 k 2 8 15 7 4 17 2 8 15 7 4 17 y 21 22 23 20 4 15 5 16 17 14 18 25 v w x u e p f q r o s z Bản mã “vwxuepfqrosz” Từ bản mã đó, dùng phép giải mã dk tương ứng, ta lại thu được bản rõ. Chú ý: Mã Vigenere với m = 1 sẽ trở thành mã Dịch chuyển. Tập hợp các khoá trong mã Vigenere mới m ≥ 1 có tất cả là 26m khoá có thể có. Với m = 6, số khoá đó là 308.915.776, duyệt toàn bộ chừng ấy khoá để thám mã bằng tính tay thì khó, nhưng với máy tính thì vẫn là điều dễ dàng. 2.3.5. Mã Hill: Định nghĩa Mã Hill: (P, C, K, E, D) Cho m là số nguyên dương. P = C = Z26m K = { k є Z26mxm : (det(k), 26) = 1 } với mỗi k є K định nghĩa: ek(x1, x2,…, xm) = (x1, x2,…, xm).k dk(y1, y2,…, ym) = (y1, y2,…,ym).k-1 Ví dụ: Lấy m = 2, và k = Với bộ 2 ký tự (x1, x2), ta có mã là (y1, y2) = (x1, x2). k được tính bởi y1 = 11.x1 + 3.x2 y2 = 8.x1 + 7.x2 Giả sử ta có bản rõ: “tudo”, tách thành từng bộ 2 ký tự, và viết dưới dạng số ta được 19 20 | 03 14 , lập bản mã theo quy tắc trên, ta được bản mã dưới dạng số là: 09 06 | 23 18, và dưới dạng chữ là “fgxs”. Chú ý: Để đơn giản cho việc tính toán, thông thường chọn ma trận vuông 2×2. Khi đó có thể tính ma trận nghịch đảo theo cách sau : Giả sử ta có Ta có ma trận nghịch đảo Và được tính như sau Một chú ý là để phép chia luôn thực hiện được trên tập Z26 thì nhất thiết định thức của k : det(k) = (ad – bc) phải có phần tử nghịch đảo trên Z26, nghĩa là (ad – bc) phải là một trong các giá trị : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, hoặc 25. Đây cũng là điều kiện để ma trận k tồn tại ma trận nghịch đảo. Khi đó: k-1.k = I là ma trận đơn vị (đường chéo chính bằng 1) Định thức của Là 11*7 – 8*3 = 1 ≡ 1 mod 26 Khi đó 2.3.6. Mã hoán vị: Định nghĩa Mã hoán vị: (P, C, K, E, D) Cho m là số nguyên dương. P = C = Z26 , K = Sm với mỗi k = π є Sm , ta có trong đó π-1 là hoán vị nghịch đảo của π Ví dụ: Giả sử m = 6, và khoá k được cho bởi phép hoán vị π 1 2 3 4 5 6 3 5 1 6 4 2 Khi đó phép hoán vị nghịch đảo π-1 là: 1 2 3 4 5 6 3 6 1 5 2 4 Bản rõ: “toinaydichoi” t o i n a y d i c h o i vt 1 2 3 4 5 6 1 2 3 4 5 6 π 1->3 2->5 3->1 4->6 5->4 6->2 1->3 2->5 3->1 4->6 5->4 6->2 vt 3 5 1 6 4 2 3 5 1 6 4 2 i a t y n o c o d i h i Bản mã: “iatynocodihi” Dùng hoán vị nghịch đảo, từ bản mật mã ta lại thu được bản rõ. Chú ý: Mã hoán vị là một trường hợp riêng của mã Hill. Thực vậy, cho phép hoán vị π của {1, 2,…, m}, ta có thể xác định ma trận Kπ=(kij), với Thì dễ thấy rằng mã Hill với khoá Kπ trùng với mã hoán vị với khoá π. Với m cho trước, số các khoá có thể có của mã hoán vị là m! Dễ nhận thấy với m = 26 ta có số khóa 26! (mã Thay thế). 2.4. Mã khóa công khai: Phương pháp mã hóa khóa công khai (public key cryptography) còn được gọi là mã hóa bất đối xứng (asymmetric cryptography) đã giải quyết được vấn đề của phương pháp mã hóa khóa bí mật (đối xứng) là sử dụng hai khóa: khóa bí mật (private key) và (public key). Khóa bí mật được giữ kín, trong khi đó được gửi công khai bởi vì tính chất khó tính được khóa bí mật từ khóa công khai. Khóa công khai và khóa bí mật có vai trò trái ngược nhau, một khóa dùng để mã hóa và khóa kia sẽ dùng để giải mã. Hiện nay các hệ mật mã khóa công khai đều dựa trên hai bài toán “khó” là bài toán logarith rời rạc trên trường hữu hạn và bài toán tìm ước số nguyên tố. Phương pháp cho phép trao đổi khóa một cách dễ dàng và tiện lợi. Nhưng tốc độ mã hóa khá chậm hơn rất nhiều so với phương pháp mã hóa khóa đối xứng rất nhiều, Tuy nhiên, hệ mật mã khóa công khai có một ưu điểm nổi bật là cho phép tạo chữ ký điện tử. Một số hệ mật mã khóa công khai 2.4.1. Mã RSA: Hệ mật này sử dụng tính toán trong Zn, trong đó n là tích của 2 số nguyên tố phân biệt p và q. Ta thấy rằng f(n) = (p – 1).(q – 1). Định nghĩa Cho n = p.q trong đó p và q là các số nguyên tố. Đặt P = C = Zn và định nghĩa: K = {(n, p, q, a, b): n = p.q; p, q là các số nguyên tố, a.b º 1 mod f(n)} Với K = (n, p, q, a, b) ta xác định: eK = xb mod n và dK = ya mod n (x, y Î Zn) Các giá trị n và b được công khai và các gia trị p, q, a được giữ kín Ví dụ: Chọn p = 2, q = 5. Tính n = p.q = 2*5 = 10 f(n)= (p – 1).(q – 1) = 1*4 = 4 Do UCLN(f(n), b) = 1 nên chọn b = 3 a.b º 1 mod f(n) nên chọn a = 7 Giả sử G muốn gửi bản rõ x = 3 tới N, G phải tính: y = eK = xb mod n = 33 mod 10 = 7 Khi N nhận được bản mã y = 1, anh ta sử dụng số mũ a mật để tính: x = dK = ya mod n = 77 mod 10 = 3 Đó chính là bản rõ mà G đã mã hoá. Độ mật của hệ RSA được dựa trên giả thiết là hàm mã eK = xb mod n là hàm một chiều. Bởi vậy thám mã sẽ khó có khả năng về mặt tính toán để giải mã một bản mã. Cửa sập cho phép N chính là thông tin về phép phân tích thừa số n (n = p.q). Vì N biết phép phân tích này nên anh ta có thể tính f(n) = (p – 1).(q – 1) và rồi tính số mũ giải mã a bằng cách sử dụng thuật toán Eculide mở rộng. 2.4.2. Mã Elgamal: Mô tả hệ mã Elgamal Hệ mật mã ElGamal được T. ElGamal đề xuất năm 1985, dựa vào độ phức tạp của bài toán tính lôgarit rời rạc, và sau đó đã nhanh chóng được sử dụng rộng rãi không những trong vấn đề bảo mật truyền tin mà còn trong các vấn đề xác nhận và chữ ký điện tử. Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể là không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết, p phải có ít nhất 150 chữ số và (p – 1) phải có ít nhất một thừa số nguyên tố lớn Hệ mật Elgamal là một hệ mật không tất định vì bản mã phụ thuộc vào cả bản rõ x lẫn giá trị ngẫu nhiên k do G chọn. Bởi vậy sẽ có nhiều bản mã được mã từ cùng một bản rõ. Bài toán logarithm rời rạc trong Zp: Đặc trưng của bài toán: I = (p, a, b) trong đó p là số nguyên tố, a Î Zp là phần tử nguyên thuỷ (hay phần tử sinh), b Î Zp* Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0 £ a £ p – 2 sao cho: aa º b (mod p) Ta sẽ xác định số nguyên a bằng log a b. Định nghĩa mã khóa công khai Elgamal trong Zp*: Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong Zp là khó giải. Cho a Î Zp* là phần tử nguyên thuỷ. Giả sử P = Zp*, C = Zp* x Zp*. Ta định nghĩa: K = {(p, a, a, b): b º aa (mod p)} Các giá trị p, a, b được công khai, còn a giữ kín. Với K =(p, a, a, b) và một số ngẫu nhiên bí mật k Î Zp – 1, ta xác định: eK(x, k) = (y1, y2). Trong đó: y1 = ak mod p y2 = x. bk mod p với y1, y2 Î Zp* ta xác định: dK(y1, y2) = y2(y1a) – 1 mod p Ví dụ: Chọn p = 7 a Î Zp* là phần tử nguyên thuỷ nên a = 3 Chọn a sao cho 0 £ a £ p – 2 nên a = 2 Khi đó : b = aa mod p = 32 mod 7 = 2 Chọn một số ngẫu nhiên bí mật k Î Zp – 1, chọn k =3 Giả sử G muốn gửi thông báo x = 3 cho N, G phải tính: eK(x, k) = (y1, y2) trong đó: y1 = ak mod p = 33 mod 7 = 6 y2 = x. bk mod p = 3*23 mod 7 = 3 Khi N thu được bản mã (y1, y2) = (6, 3), anh ta sẽ tính: x = dK(y1, y2) = y2(y1a)-1 mod p = 3*(62)-1 mod 7 = 3 Đó chính là bàn rõ mà G đã mã hoá. Chương 2 CHỮ KÝ SỐ I. Chữ ký số 1. Giới thiệu chung về chữ ký số: Như chúng ta đã biết, chữ ký viết tay “thường lệ” gắn với tài liệu được dùng để chỉ ra người đã ký nó. Chữ ký được sử dụng hàng ngày như viết thư, ký hợp đồng… Ở đây chúng ta tìm hiểu về chữ ký hoàn toàn khác đó là chữ ký số. Nó là phương pháp ký thông báo được lưu dưới dạng điện tử và thông báo được ký có thể truyền trên mạng máy tính. Chữ ký tay và chữ ký số dù có chung nhiệm vụ là ký nhưng có sự khác biệt cơ bản giữa chúng. Thứ nhất, về việc ký tài liệu: với chữ ký tay thì chữ ký là bộ phận vật lý của tài liệu được ký. Tuy nhiên, chữ ký số không một cách vật lý với thông báo được ký mà được gắn với thông báo theo logic, do đó thuật toán được dùng phải “trói ” chữ ký với thông báo theo một cách nào đó. Thứ hai, về việc kiểm tra: chữ ký tay được kiểm tra bằng cách so sánh nó với những cái khác những chữ ký đã được xác thực. Ví dụ, một người ký một tấm séc mua hàng, người bán hàng phải so sánh chữ ký trên tấm séc với chữ ký nằm sau thẻ tín dụng để kiểm tra. Tuy nhiên, phương pháp này không an toàn lắm vì nó tương đối dễ đánh lừa bởi chữ ký của người khác. Khác với chữ ký tay, chữ ký số có thể được kiểm tra bằng cách dùng thuật toán kiểm tra công khai đã biết. Vì vậy bất kì người nào đều có thể kiểm tra chữ ký số, và việc sử dụng lược đồ ký an toàn sẽ ngăn chặn khả năng đánh lừa. Điều khác nhau cơ bản giữa chữ ký tay và chữ ký số là “bản sao” thông báo số được ký là đồng nhất với bản gốc. Trong khi đó, bản sao tài liệu giấy đã ký thường là khác với bản gốc. Điều này có nghĩa là phải cẩn thận để ngăn chặn thông một thông báo đã ký số bị sử dụng lại. Ví dụ, nếu A ký thông báo số cho B rút 1000$ từ tài khoản trong ngân hàng của mình, A chỉ muốn B làm điều đó 1 lần. Do đó, thông báo đó phải chứa thông tin để ngăn chặn B làm lại việc đó nhiều lần. Lược đồ chữ ký gồm hai thành phần: một thuật toán ký và một thuật toán kiểm tra. A có thể ký thông báo x nhờ thuật toán ký(bí mật) Sig. Chữ ký thu được Sig(x) sau đó có thể được kiểm tra bằng thuật toán kiểm tra công khai Ver. Khi cho cặp(x,y) thuật toán kiểm tra trả lời “đúng” hoặc “sai” phụ thuộc vào việc ký có đích thực không? 2. Định nghĩa lược đồ chữ ký: Lược đồ chữ ký là một bộ năm phần tử (P,A,K,S,V) thỏa mãn các điều kiện sau: P _ là một tập hữu hạn các thông báo. A _ tập hữu các chữ ký có thể. K _ tập hữu hạn các khóa, không gian khóa. Với mỗi k Î K, $ sigk Î S và verk ÎV Mỗi sigk: P® A, verk: P * A® {true, false}là những hàm sao cho mỗi bức điện x ÎP và mỗi chữ ký y ÎA thỏa mãn: Ver(x,y) = Yêu cầu: - Với mỗi k Î K, các hàm sigk và verk là các hàm thời gian đa thức - Verk là hàm công khai, sigk là hàm bí mật tránh trường hợp một người B nào đó có thể giả mạo chữ ký của chủ thể A để ký thông báo. Với mỗi x chỉ duy nhất A tính được chữ ký y sao cho: Ver(x,y)= True Lược đồ chữ ký phải an toàn. Bởi vì người thám mã B có thể kiểm tra tất cả các khả năng của chữ ký y nhờ thuật toán kiểm tra công khai Ver cho tới khi đạt được yêu cầu tức là tìm được chữ ký đúng. Do đó, nếu đủ thời gian cần thiết thì B có thể giả mạo được chữ ký của A. Vì vậy, mục đích của chúng ta là tìm các lược đồ chữ ký sao cho B không đủ thời gian thực tế để thử như thế. 2.1. Lược đồ chữ ký RSA: Lược đồ chữ ký RSA được định nghĩa như sau: Tạo khóa: Sơ đồ chữ ký cho bởi bộ năm (P,A,K,S,V) Cho n=p.q; với mỗ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à định nghĩa: K là tập các khóa, K=(K’,K’’); với K’=a; K’’=(n,b) a,b ÎZn*, thỏa mãn ab º 1mod f(n). Các giá trị n,b là công khai, các giá trị p,q,a là các giá trị bí mật. Tạo chữ ký: Với mỗi K=(n.p,q,a,b) xác định: SigK’(x)= xa mod n Kiểm tra chữ ký: VerK’’(x,y)= true Û x º yb mod n; x, y ÎZn. Giả sử A muốn gửi thông báo x, A sẽ tính chữ ký y bằng cách : y=sigK’(x)= xa mod n (a là tham số bí mật của A) A gửi cặp (x,y) cho B. Nhận được thông báo x, chữ ký số y, B bắt đầu tiến hành kiểm tra đẳng thức x= yb mod(n) (b là khóa công khai A) Nếu đúng, B công nhận y là chữ ký trên x của A. Ngược lại, B sẽ coi x không phải của A gửi cho mình (chữ ký không tin cậy). Người ta có thể giả mạo chữ ký của A như sau: chọn y sau đó tính x= verK’’(y), khi đó y= sigK’(x). Một cách khắc phục khó khăn này là việc yêu cầu x phải có nghĩa. Do đó chữ ký giả mạo thành công với xác suất rất nhỏ. Ta có thể kết hợp chữ ký với mã hóa làm cho độ an toàn tăng thêm. Giả sử trên mạng truyền tin công cộng, ta có hai hệ mật mã khóa công khai δ1 và hệ xác nhận chữ ký δ2. Giả sử B có bộ khóa mật mã K=(K’,K’’) với K’=(n,e) và K’’=d trong hệ δ1, và A có bộ khóa chữ ký Ks=(Ks’,Ks’’) với Ks’= a và Ks’’=(n,b) trong hệ δ2. A có thể gửi đến B một thông báo vừa bảo mật vừa có chữ ký xác nhận như sau: A tính chữ ký của mình là: y= sigA(x), và sau đó mã hóa cả x và y bằng cách sử dụng mật mã công khai eB của B, khi đó A nhận được z= eB(x,y), bản mã z sẽ được gửi tới B. khi nhận được z việc trước tiên B phải giải mã bằng hàm dB để nhận được (x,y). Sau đó B sử dụng hàm kiểm tra công khai của A để kiểm tra xem verA(x,y)= true? Tức là kiểm tra xem chữ ký đó có đúng là của A?. Ví dụ: A dùng lược đồ chữ ký số RSA với n=247,(p=13,q=19); f(n) = 12.18 = 216. Khóa công khai của A là b=7. Þ a = 7-1mod216 = 31. A công khai (n,b) = (247,7) A ký trên thông báo x=100 với chữ ký: y = xa modn = 10031 mod247 = 74. A gửi cặp (x,y) = (100,74) cho B, B kiểm tra bằng cách sử dụng khóa công khai của A như sau: x = yb modn = 747 mod247 = 100 = x. B chấp nhận y=74 là chữ ký tin cậy. 2.2. Lược đồ chữ ký ElGamal: Lược đồ chữ ký ElGamal được giới thiệu năm 1985 và được Viện tiêu chuẩn và Công nghệ quốc gia Mỹ sửa đổi thành chuẩn chữ ký số. Lược đồ chữ ký ElGammal không tất định cũng giống như hệ mã hóa ElGamal. Điều này có nghĩa là có nhiều chữ ký hợp lệ cho một thông báo bất kỳ. Thuật toán kiểm tra phải có khả năng khả năng chấp nhận bất kỳ chữ ký hợp lệ nào khi xác minh. Lược đồ chữ ký ElGamal được định nghĩa như sau: Tạo khóa: Cho p là số nguyên tố sao cho bài toán logarit rời rạc trong Zp là khó và giả sử a ÎZ là phần tử nguyên thủy Cho P = Z, A = Z´ Zp-1 và định nghĩa 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à với số ngẫu nhiên k ÎZ, định nghĩa sigk(g, d), trong đó: g = ak modp và d = (x - ag) k -1mod(p - 1). Kiểm tra chữ ký số Với x, g Î Z và d ÎZp-1 , ta định nghĩa : Ver (x, g, d) = True Û bg. gd º ax modp. Chứng minh: Nếu chữ ký được thiết lập đúng thì hàm kiểm tra sẽ thành công vì: Þbg gd º aa.g ar.d modp º ax modp ( vì ag + rd º x mod(p - 1)). A tính chữ ký bằng cách dùng cả giá trị bí mật a( là một phần của khóa ) lẫn số ngẫu nhiên bí mật k ( dùng để ký trên x). Việc kiểm tra có thể thực hiện duy nhất bằng thông tin công khai. Ví dụ: Giả sử p=467, a = 2, a = 127 Khi đó: b = aa modp = 2127mod467 = 132 Giả sử A có thông báo x=100 và A chọn ngẫu nhiên k=213 vì (213,466)=1 và 213-1 mod466 = 431, A ký trên x như sau: g = ak modp = 2213mod467 = 29 Và d = (x - ag)k-1 mod(p -1) = (100 – 127. 29).431 mod466 = 51. Chữ ký của A trên x= 100 là (29,51). Bất kỳ người nào đó cũng có thể kiểm tra chữ ký bằng cách: 13229 . 2951 º 189 mod 467 2100 º 189 mod 467 Do đó, chữ ký là tin cậy. II. Hàm Hash 1. Giới thiệu: Đối với xác thực và chữ ký số ta thấy rằng các thuật toán thường nhận đầu vào là các dòng bit có độ dài rất ngắn (61.128.160 bit) và có tốc độ thực hiện chậm. Mặt khác, các thông báo ký thường có độ dài khác nhau và trong trường hợp chúng có độ dài lớn cỡ vài Kilôbyte hoặc và Megabyte. Do vậy, muốn ký trên một thông báo dài ta phải cắt thông báo ra nhiều đoạn có độ dài hữu hạn và cố định rồi tiến hành ký độc lập từng đoạn và gửi từng đoạn đó đi, khi đó lại xuất hiện một vấn đề như: - Tốc độ sẽ chậm vì phải ký trên quá nhiều đoạn. - Dễ xảy ra trường hợp không sắp xếp được thông báo theo đúng trật tự ban đầu. - Có thể bị mất các đoạn riêng biệt trong quá trình truyền tin. Để giải quyết vấn đề này ta dùng hàm Hash. Hàm Hash chấp nhận một thông báo có độ dài bất kỳ làm đầu vào, Hàm Hash sẽ biến đổi thông báo này thành một thông báo rút gọn, sau đó sẽ sử dụng lược đồ chữ ký để ký trên thông báo rút gọn. Ta có mô hình chung như sau: Thông báo x độ dài tùy ý Thông báo rút gọn z = h(x) 160 bit Chữ ký y = sigK(x) 320 bit Ta sẽ gửi cặp (x,y) cho người nhận. Nếu cần giữ bí mật x thì ta mã hóa x thành x’ rồi sau đó gửi cặp (x’,y). 2. Định nghĩa: Hàm Hash là hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có độ dài tùy ý thành những dòng nhị phân có độ dài cố định nào đó. - Hàm Hash yếu: hàm Hash gọi là yếu nếu cho một thông báo x thì về mặt tính toán không tìm ra được thông báo x’ khác x sao cho: h(x’) = h(x) - Hàm Hash mạnh: hàm Hash được gọi là mạnh nếu về mặt tính toán không tìm ra được hai thông báo x và x’ sao cho: x1 ¹ x2 và h(x1) = h(x2) Nói cách khác, tìm hai văn bản khác nhau có cùng một đại diện là cực kỳ khó Hàm Hash phải là hàm một phía, nghĩa là cho x tính z = h(x) thì dễ, nhưng ngược lại, biết z tính x là công việc cực khó. Hàm Hash yếu làm cho chữ ký trở lên tin cậy giống như việc ký trên toàn thông báo. Hàm Hash mạnh có tác dụng chống lại kẻ giả mạo tạo ra hai bản thông báo có nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho một bản thông báo dễ được xác nhận rồi lấy nó giả mạo làm chữ ký của thông báo thứ 2 hay nói cách khác tìm 2 văn bản khác nhau có cùng một đại diện là cực kỳ khó. 2.1. Một số hàm Hash sử dụng trong chữ ký số: 2.1.1. Các hàm Hash đơn giản: Tất cả các hàm Hash đều được thực hiện theo quy tắc chung là: Đầu vào được biểu diễn dưới dạng một dãy các khối n bit, các khối n bit này được xử lý theo cùng một kiểu và lặp đi lặp lại để cuối cùng cho đầu ra có số bit cố định. Hàm Hash đơn giản nhất là thực hiện phép toán XOR từng bit một của mỗi khối. Nó được biểu diễn như sau: Ci = b1i Å b2iÅ …Åbmi Trong đó : Ci : là bit thứ i của mã Hash, i = m : là số các khối đầu 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 nhận. Sự kiểm tra của người xác nhận chính xác hơn của 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 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 những 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 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ý 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 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 mỗi người sử dụng mạng nên được bảo vệ trong khi kiểm duyệt sự mua bán. 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 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 khóa: Tạo 2 khóa GENS và GENC nhận 1l là đầu vào ( 11 nghĩa là một dãy số có một số 1), trong đó 1 là tham số an toàn và lần lượt 2 cặp đầu ra (SS, PS) và (SC, PC). Thuật toán GENS thực hiện bởi S, GENC thực hiện bởi C. (SS, PS), (SC, PC) lần lượt là các cặp khóa bí mật và công khai của S và C. Khóa bí mật S được sử dụng để tạo ra chữ ký. Ngoài ra SS, SC được lần lượt sử dụng bởi người ký và người xác nhận trong giao thức xác nhận trong và giao thức chối bỏ. - Thuật toán ký đa thức theo xác suất SIGN nhận khóa bí mật SS, thông báo m và các đầu ra của chữ ký σ. - 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ý σ, 2 khóa 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ý σ 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ý σ và 2 khóa 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 có nghĩa là chữ ký σ 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 trong giao thức: Tính không thể phân biệt 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 khóa công khai PS, PC là đầu vào 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 với bất kỳ người nào mà chỉ cần 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 khóa công khai PS của người ký; khóa bí mật SC, khóa công PC của người nhận và truy cập đến chữ ký người tin cậy SIGN, cho ra một thông báo – chữ ký (m’, σ’) 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 2 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 gặp thông báo – chữ ký (m, σ) tin cậy, hoặc 0 nếu (m, σ) là không tin cậy. 3. Các lược đồ chữ ký và phép chứng minh tương tác: 3.1. Ký hiệu: + Kí hiệu || biểu thị sự 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 nhóm nhân G của Z*p bậc q. + Hàm Hash chịu đựng sự va chạm mạnh H: {0, 1}* Z*p (k = | q |, k > 160). 3.2. Lược đồ chữ ký Schnorr: Định nghĩa: Cho y = gx mod p, chữ ký Schnorr trên thông báo m kiểm tra sử dụng khóa công khai (g, y) là cặp (u, v) Î Z ´ Z thỏa mãn u = H(mççyççgççgvyu). Chữ ký như vậy có thể được tính nếu biết khóa bí mật x bằng cách chọn r Î Z (chọn r ngẫu nhiên thuộc Z*p ) rồi 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 khóa bí mật x và có kiểm tra với khóa công khai y. 3.3. Chữ ký Chaum – Petersen dựa vào đẳng thức toán rời rạc: Định nghĩa 2: Cho y1 = gx1 và y2 = gx2, chữ ký Chaum – Petersen dựa vào đẳng thức của thuật toán rời rạc y1, y2 với cơ số là g1, g2 trên thông báo m là cặp (u, v) Î Z ´ Zthỏa 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 khóa bí mật x thỏa mãn y1 = và y2 = . Chữ ký sai đó được tính bằng cách chọn r Î Z, tính: u = H(mççy1ççy2ççg1ççg2ççgyççgy) và r = r – ux mod q. Ta có thể viết lại như sau: Từ v = r – ux mod q => r = v + ux mod q. Theo giả thiết : y1 = 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 khóa bí mật x thỏa 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. 3.4. Phép chứng minh tương tác Fujioka – Okamoto – Ohta đẳng thức: Phép chứng minh đẳ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 = gymod p? 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 Î Zq 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’, ngẫu nhiên Î Zq và 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 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 lạ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) và 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 4. Cấu trúc lược đồ chữ ký người xác nhận không thể chối bỏ: 4.1. Tạo khóa: + Người ký chọn s Î Z, thiết lập cặp khóa bí mật và công khai (SS, PS) với SS = s, PS = gs mod p. + Người xác nhận chọn c Î Z, thiết lập cặp khóa bí mật và công khai (SC, PC) với SC = c, PS = gc mod p. 4.2. Tạo chữ ký: Để tạo chữ ký σ 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 đó tính σ1 = CP(r, a, as+c, g, gs+c)(m) và s2 = S(sr, g, as)(s1). => Chữ ký σ của người ký trên thông báo m là: s = (s1, s2). 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, σ, 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. 4.4. Giải thích cấu trúc bằng trực giác: Ta thấy rằng trong các cấu trúc này, người ký có khóa bí mật s, khóa công khai g, người xác nhận có khó bí mật c, khóa 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ỏ σ gồm 2 chữ ký là s1, s2. Trong đó s1 là chữ ký Chaum – Petersen được tạo với khóa bí mật r1 = r, kiểm tra với khóa công khai a = gr và as+c = g; s2 là chữ ký Schnorr được tạo với khóa bí mật r2 = rs, kiểm tra với khóa 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 khóa 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 logg(gc ), vì vậy chỉ có thể thực hiện bởi người xác nhận. 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 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 giả mạo, không thể phân biệt được và sự kiểm tra chữ ký là nhất quán. 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 trong thời gian đa thức theo xác suất A mà có thể sinh ra chữ ký σ trên thông báo đặc biệt m, kiểm tra với khóa công khai y khi truy cập đến chữ ký Oracle của tất cả khóa 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 khóa công khai y* sinh ra chữ ký σ* 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 σ dưới khóa 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ó thỏa 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à khóa 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 khóa 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 đã được tạo ra cùng một khóa 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 σ2. 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à khóa 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 khóa 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 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+. Ở đây khóa 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. 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 và hợp lý của phép chứng minh ký của tri thức. 6. Chữ ký người xác nhận không thể chối bỏ mù quáng và các ứng dụng 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. 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ở lên phổ biến trên các mạng truyền thông thì người ra cũng nghĩ tới các hoạt động kinh doanh trên mạng 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 tổng 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ả tiền 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 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ù có thể dùng để thiết kế một hệ thống trả tiền 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ù 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 trong cách này là giảm trách nhiệm một lượng quá lớn quá trình tiến hành công việc mua bán, thậm chí cung cấp cả quyền riêng tư cho người sử dụng. CHƯƠNG TRÌNH #include #include #include #include #include //========================================== int roso(char s); char rochu(int s); void kyvb(char *tep); int Kiemthu(); long int kha_nghich(long int b, long int n); void output(); void Elgamal(); long exp_mod(long x, long b, long n); long Extended_Euclidean(long b, long n); int kiemtra_ngto(long pq); long USCLN(long n,long m); long Ktra_ngto_cungnhau(long b,long phi_N); long Kitep(int Ki); long Doctep(long n); void Ky_RSA(); void chaum(); //=========================================== long int p,a,alpha,k,beta,k1; long int delta,gamma; int chuky[500],sl; //=========================================== int roso(char s) { return s; } char rochu(int s) { return s; } //================ky cao van ban============== void kyvb(char *tep) { clrscr(); char c,c1; long int so; int so1,so2,l,i; FILE *f,*f1; char *tep1; char *s; sl=1; chuky[0]=gamma; f=fopen(tep,"a+t"); if(f==NULL) { printf("Loi mo tep!!!"); getch(); exit(0); } while(!feof(f)) { fscanf(f,"%c",&c); //doc tung ky tu trong tep. if(c!=10) { so=roso(c); //lay gia tri so cua tung ky tu c. delta=((so-a*gamma)*k1)%(p-1); //tinh gia tri ky la gamma. delta=delta+(p-1); //vi delta<0 chuky[sl]=delta; //gia tri ky tren tung ky tu. sl++; } } fclose(f); } //============Ham kiem thu chu ky================= int Kiemthu() { char *tep,*tep1; char c; int d; long int so; FILE *f,*f1; printf("Nhap ten tep can kiem thu:");fflush(stdin); gets(tep); printf("Nhap ten tep chua chu ky can kiem thu:");fflush(stdin); gets(tep1); f=fopen(tep,"rt"); f1=fopen(tep1,"rt"); int kt=1; fscanf(f1,"%2d",&sl); fscanf(f1,"%2d\n",&gamma); int i=1; while(i<sl-1) { fscanf(f,"%c",&c); so=roso(c); fscanf(f1,"%3d",&d); if((a*gamma+k*d)%(p-1)!=so) { kt=0; return kt;} i++; } fclose(f1); fclose(f); return kt; } //===========Tinh Kha nghich ================ long int kha_nghich(long int b, long int n) { long int n0, b0; long int t, t0, temp, q, r; n0=n; b0=b; t0=0; t=1; q=floor(n0/b0); r=n0-q*b0; while(r>0){ temp=t0-q*t; if (temp < 0) temp = n- ((-temp) % n); else temp = temp % n; t0=t; t=temp; n0=b0; b0=r; q=floor(n0/b0); r=n0-q*b0; } if(b0!=1) { printf("Khong co a"); return 0;} else return(t%n); } //=================================================== void output() { char c; char *tep; FILE *f; printf("Nhap ten tep can luu chu ky:");fflush(stdin); gets(tep); f=fopen(tep,"wt"); if(f==NULL) { printf("\nLoi mo tep!!!!!!"); getch(); exit(0); } fprintf(f,"%d",sl); fprintf(f," %d\n",chuky[0]); for(int i=1;i<sl;i++) { fprintf(f," %2d",chuky[i]); } fclose(f); } //=============Ham chinh============================== void Elgamal() { printf("\n\n =====* CHU KY ELGAMAL *======"); long int x,y; int ch; char *tep,*tep1; FILE *f,*f1; char c; printf("\n\nNhap so nguyen to p:");scanf("%ld",&p); printf("Nhap a:");scanf("%ld",&a); printf("Nhap alpha:");scanf("%ld",&alpha); printf("Nhap khoa k:");scanf("%ld",&k); beta=exp_mod(a,alpha,p); gamma=exp_mod(k,alpha,p); k1=kha_nghich(k,p-1); while(1) { printf("\n\nCAC LUA CHON CHO CHU KY SO ELGAMAL\n"); printf("[1].Ky \n"); printf("[2].Hien thi \n"); printf("[3].Kiem thu\n"); printf("[0].Thoat!!\n"); printf("\n\nMoi ban chon:");scanf("%d",&ch); switch(ch) { case 1:{ printf("Nhap ten tep:");fflush(stdin); gets(tep); kyvb(tep); output(); }break; case 2:{ printf("Nhap ten can hien thi:");fflush(stdin); gets(tep); printf("Nhap tep ten chua chu ky tuong ung:");fflush(stdin); gets(tep1); f=fopen(tep,"r+t"); int d; printf("\n\n VAN BAN\n\n"); while(!feof(f)) { fscanf(f,"%c",&c); printf("%c",c); } f1=fopen(tep1,"r+t"); printf("\n\n CHU KY\n\n"); fscanf(f1,"%d",&sl); fscanf(f1,"%d",&gamma); printf("do dai xau:%2d" "gia tri gamma:%2d\n",sl,gamma); for(int i=0;i<sl-1;i++) { fscanf(f1,"%d",&d); printf(" %2d",d); } fclose(f1); fclose(f1); }break; case 3:{ if(Kiemthu()==1)printf("Chu ky dung!!"); else printf("Chu ky gia!!"); } case 0:break; } if(ch==0) break; } getch(); } //=========== Tinh Mod ============ long exp_mod(long x, long b, long n) { long a = 1l, s = x; while (b != 0) { if (b & 1l) a = (a * s) % n; b >>= 1; if (b != 0) s = (s * s) % n; } if (a < 0) a += n; return a; } //============= Tinh theo Euclidean mo rong =========== long Extended_Euclidean(long b, long n) { long b0 = b, n0 = n, t = 1, t0 = 0, temp, q, r; q = n0 / b0; r = n0 - q * b0; while (r > 0) { temp = t0 - q * t; if (temp >= 0) temp = temp % n; else temp = n - (- temp % n); t0 = t; t = temp; n0 = b0; b0 = r; q = n0 / b0; r = n0 - q * b0; } if (b0 != 1) return 0; else return t % n; } //====================================================== void chaum() { printf("\n\n =====* GIAO THUC CHOI BO *====="); long a = 101, alpha = 4, beta = 449, e1 = 46; long e2 = 123, f1 = 198, f2 = 11, i, j, p = 467; long q, x = 157, y = 25, c, d, C, D, r, s, t; q = (p - 1) >> 1; printf("a = %ld\n", a); printf("alpha = %ld\n", alpha); printf("beta = %ld\n", beta); printf("e1 = %ld\n", e1); printf("e2 = %ld\n", e2); printf("f1 = %ld\n", f1); printf("f2 = %ld\n", f2); printf("p = %ld\n", p); printf("q = %ld\n", q); printf("x = %ld\n", x); printf("y = %ld\n", y); i = Extended_Euclidean(a, q); c = (exp_mod(y, e1, p) * exp_mod(beta, e2, p)) % p; d = exp_mod(c, i, p); printf("Alice Tinh c = %ld va gui cho Bob\n", c); printf("Bob Tinh d = %ld va gui lai cho Alice\n", d); if (d != (exp_mod(x, e1, p) * exp_mod(alpha, e2, p)) % p) printf("d != x ^ e1 * alpha ^ e2 mod p\n"); else printf("d == x ^ e1 * alpha ^ e2 mod p\n"); C = (exp_mod(y, f1, p) * exp_mod(beta, f2, p)) % p; D = exp_mod(C, i, p); printf("Alice Tiep tuc tinh C = %ld va gui cho Bob\n", C); printf("Bob Tinh D = %ld va gui cho Alice\n", D); if (D != (exp_mod(x, f1, p) * exp_mod(alpha, f2, p)) % p) printf("D != x ^ f1 * alpha ^ f2 mod p\n"); else printf("D == x ^ f1 * alpha ^ f2 mod p\n"); i = q - e2; if (i < 0) i += q; j = q - f2; if (j < 0) j += q; r = (d * exp_mod(alpha, i, p)) % p; s = exp_mod(r, f1, p); r = (D * exp_mod(alpha, j, p)) % p; t = exp_mod(r, e1, p); if (s == t) printf("Alice Chap nhan chu ky y la chu ky dang tin cay\n"); else printf("Alice Cho rang chu ky y la khong tin cay \n"); getch(); } //============================================================= int kiemtra_ngto(long pq) { for(long i=2;i<=(long)sqrt(pq);i++) if(pq%i==0) { printf("\n\n Khong phai so nguyen to!\n\nMoi ban nhap lai!"); return 0; } return 1; } //============================================================= long USCLN(long n,long m) { while(m!=0&&n!=0) if(n>m) n=n-m; else m=m-n; if(n==0) return m; else return n; } //============================================================= long Ktra_ngto_cungnhau(long b,long phi_N) { if(USCLN(b,phi_N)!=1) { printf("\n\nb khong phai la nguyen to cung nhau voi phi_N\n\n moi chon lai b!"); return 0; } else return 1; } //============================================================= long Kitep(int Ki) { FILE *f; char *tentep; long n; mt:printf("\n\nNhap vao ten tep can Ki:");fflush(stdin);gets(tentep); f=fopen(tentep,"a+t"); if(f==NULL) { printf("\n\nTep %s khong ton tai! Moi nhap lai!",tentep); getch(); goto mt; } fseek(f,0,SEEK_END); n=ftell(f); fseek(f,n,SEEK_SET); fprintf(f,"%d",Ki); fclose(f); return n; } //============================================================= long Doctep(long n) { FILE *f; char *tentep; mt:printf("\n\nNhap vao ten tep can mo:");fflush(stdin);gets(tentep); f=fopen(tentep,"a+t"); if(f==NULL) { printf("\n\nTep %s khong ton tai! Moi nhap lai!",tentep); goto mt; } long ki; fseek(f,n,SEEK_SET); fscanf(f,"%ld",&ki); fclose(f); return ki; } //============================================================= void Ky_RSA() { clrscr(); long x,a,b,n,phi_N,p,q; long Kthuocvb; int Ki,Kiem_thu; printf("\n=====* CHU KY RSA *======"); p:printf("\nNhap so nguyen to p=");scanf("%ld",&p); if(kiemtra_ngto(p)!=1)goto p; q:printf("\nNhap so nguyen to q=");scanf("%ld",&q); if(kiemtra_ngto(q)!=1)goto q; n=p*q; phi_N=(p-1)*(q-1); b:printf("\nMoi ban chon so b (1<b<phi_N) sao cho gcd(b,phi_N)==1\n\n b="); scanf("%ld",&b); if(Ktra_ngto_cungnhau(b,phi_N)!=1)goto b; a=kha_nghich(b,phi_N); printf("\n\n LAP CHU KI "); printf("\nKhoa bi mat dung de tao chu ki la K1(a)=%ld",a); printf("\nNhap vao so de lap chu ki so x=");scanf("%ld",&x); Ki=exp_mod(x,a,n); printf("\nVoi so x ta tao duoc ra chu Ki la :%d",Ki); Kthuocvb=Kitep(Ki); printf("\nVan ban da duoc ki!"); printf("\n\n KIEM THU CHU KI "); printf("\nKiem thu voi khoa cong khai la K2(b,n)=(%ld,%ld)",b,n); Kiem_thu=Doctep(Kthuocvb); printf("\nChu ki duoc lay tu tep la:%d",Kiem_thu); printf("\nKiem thu chu ki so ta duoc x=%d ",exp_mod(Kiem_thu,b,n)); if(exp_mod(Kiem_thu,b,n)==x) printf("\n\n CHU KI TREN LA DUNG!"); else printf("\n\n KHONG PHAI LA CHU KI!"); getch(); } //============================================================= void menu() { int c; while(1) { clrscr(); printf("\n\n=====* CHUONG TRINH CHU KY SO *======="); printf("\n\n[1].CHU KY RSA"); printf("\n[2].CHU KY ELGAMAL"); printf("\n[3].GIAO THUC CHOI BO"); printf("\n[4].Thoat khoi chuong trinh"); printf("\n\n Moi ban chon:");scanf("%d",&c); switch(c) { case 3: chaum(); break; case 4: return; case 2: Elgamal(); break; case 1: Ky_RSA(); break; } } } //=========================================== void main() {clrscr(); menu(); } 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. Nhưng bên cạnh những ưu điểm của chữ ký số mang lại nó còn bộc lộ những hạn chế nhất là đối với các chữ ký tự xác thực (RSA, Elgamal…), đó là khả năng bảo vệ chữ ký, độ an toàn và xác thực chữ ký… Trong đồ án này, tôi đã đi sâu tìm hiểu về lược đồ chữ ký không thể chối bỏ, lược đồ chữ ký người xác nhận được chỉ định và lược đồ chữ ký người xác nhận không thể chối bỏ. Mỗi lược đồ là sự hoàn thiện và từng bước nâng cao sự an toàn và độ tin cậy của chữ ký số. Với lược đồ chữ ký chống chối bỏ nó đã giải quyết được yêu cầu của chữ ký số đó là khả năng bảo vệ chữ ký chống sự sao chép không hợp pháp. Vì chữ ký chống chối bỏ chỉ có thể được kiểm tra khi có sự cộng tác của người ký thông qua giao thức hỏi – đáp. Tuy nhiên, với lược đồ này lại có một vấn đề nữa là nếu người ký không cộng tác trong việc xác thực chữ ký thì chữ ký sẽ không được kiểm tra hoặc người ký không thực hiện đúng giao thức khi họ muốn chối bỏ chữ ký của mình. Với lược đồ chữ ký người xác nhận được chỉ định đã giải quyết được yếu điểm của lược đồ ký không chối bỏ được. Trong lược đồ này có sự tham gia của ba bên đó là người ký, người xác nhận, và người kiểm tra chữ ký. Người xác nhận thông qua phép chứng minh tương tác có thể chứng minh với một người bất kỳ rằng chữ ký của chủ thể ký là đáng tin cậy nhưng nó cũng ngăn cản việc người nhận chữ ký dùng sai mục đích đó là người nhận chữ ký có thể dùng chữ ký đó đi thuyết phục người khác. Lược đồ chữ ký người xác nhận không thể chối bỏ là sự biến đổi khéo léo của lược đồ ký người xác nhận được chỉ định, nó được ứng dụng nhiều trong các hệ thống thanh toán trực tuyến. Luận văn tập chung vào nghiên cứu cơ sở lý thuyết và xây dựng chương trình về chữ ký số.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 độ còn hạn chế nên không thể tránh khỏi những nhược điểm, rất mong được sự góp ý của các Thầy, Cô và các bạn. Cuối cùng em xin cảm ơn thầy giáo TS. Lê Phê Đô thầy đã tận tình chỉ bảo giúp đỡ em hoàn thành đồ án này. TÀI LIỆU THAM KHẢO Lý thuyết mật mã và an toàn thông tin – Phan Đình Diệu(NXB ĐHQGHN). Bài giảng an toàn thông tin – TS. Nguyễn Ngọc Cương. Cryptography Theory and Practice – DR. Stínon. Designated Confirmer Signatures – David Chaum. Khanh Nguyen, Yi Mu, Vijay Varadharajan - Undeniable Confirmer Signature. Invisible Designated Confirmer Signatures without Random Oracles - Victor K. Wei. Efficie Convertible Uderniable Signature Schemes .