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

ủ 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 đó. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -34- 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 Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -35- 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 Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -36- 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, φ(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(φ(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: 1. Simon chọn x ngẫu nhiên và tính: a = gx b = hx 2. Với K = (n, p, q, 3-1, 3) Simon tính chữ ký RSA trên H(a,b) ⊕ F(m) α = (H(a, b) ⊕ F(m)) 13− 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, α 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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -37- 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: 1. Rita chọn s, t ngẫu nhiên và tính c = gsht, rồi gửi c cho Simon. 2. Simon chọn q ngẫu nhiên và tính: d = g q ; e = (c.d)x Simon gửi d,e cho Rita. 3. Rita gửi s,t cho Simon 4. Simon kiểm tra gsht = c thì Simon gửi q cho Rita 5. Rita kiểm tra nếu d = g q , e.a q− = asbt, H(a, b) ⊕ F(m) = α3 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 q− = asbt tức là kiểm tra b = az. Thật vậy: Từ asbt = e.a q− ⇒ bt = e.a q− .a-s (1) mà e = (c.d)x c = gsht d = g q ⇒ e = (gs.ht.g q )x = gs.x.ht.x.g q .x = (gx)s.ht.x.(gx) q = as.htx.a q (2) Từ (1) và (2) ⇒ bt = as.htx.a q . a q− .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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -38- 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: 1. 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. 2. Colin chọn p ngẫu nhiên và tính: l = g p , n = (k.l)z. Rồi gửi l, n cho Veron. 3. Người kiểm tra gửi u, v cho Colin. 4. Colin kiểm tra nếu k= gu .av thì Colin gửi q cho người kiểm tra Veron. 5. Người kiểm tra Veron sẽ kiểm tra nếu g p = l và n.h p = 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 p = hu.bv cũng chính là kiểm tra b = az. Ta có: n.h p = hu.bv ⇒ bv = n. h p . h-u (1) Mặt khác: n = (k.l)z k = gu.av l = g p ⇒ n = (gu.av.g p )z (2) Từ (1) và (2) ⇒ bv = (gu.av.g p )z. h p . h-u = guz.avz.g pz .g-uz.g pz− ⇒ 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: 1. Colin chọn ngẫu nhiên w rồi tính: r = aw y = w + z.F(a, r). Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -39- Sau đó gửi r, y cho người kiểm tra Veron. 2. 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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -40- 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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -41- 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, σ, 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, σ, 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à Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -42- 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 *q × Z *q 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 ∈ R Z *q (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 *q × Z *q thỏa mãn: u = H(m⎜⎜y1⎜⎜y2⎜⎜g1⎜⎜g2⎜⎜g v1 y u1 ⎜⎜g v2 y u2 ) 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 = xg1 và y2 = xg2 . Chữ ký sai đó được tính bằng cách chọn r ∈ R Z *q , tính: u = H(m⎜⎜y1⎜⎜y2⎜⎜g1⎜⎜g2⎜⎜g v1 y u1 ⎜⎜g v2 y u2 ) 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 = xg1 Ö g v1 y u1 = g v1 (g x1 )u = g uxv+1 = g r1 Tương tự: y2 = g x2 Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -43- ⇒ g v2 y u2 = g v2 (g x2 )u = g uxv+2 = g r2 Vậy: u = H(m⎜⎜y1⎜⎜y2⎜⎜g1⎜⎜g2⎜⎜g r1 ⎜⎜g r2 ) Để đơ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 1g (y1) ≡ log 2g (y2) là giao thức hoặc chứng minh log 1g (y1) ≡ log 2g (y2) hoặc chứng minh log 1g (y1) ≠ log 2g (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 ∈ R Z q a = g u1 y v1 modp ⎯→⎯a k, k’, w ∈ R Z q r1 = g k1 ; r2 = g k2 r '1 = g ' 1 k ; r '2 = g ' 2 k ⎯⎯⎯ ⎯← wrrrr ,,,, '22'11 ⎯→⎯ vu , a = g u1 y v1 mod p? z = k – (v + w) c z’ = k’ – (v + w) k ⎯⎯← ',zz g z1 y wv+1 = r1 g '1z r wv+1 = r '1 g '2z r wv+2 = r '2 γ = ( g2z y wv+2 ≡ r2) Ta có thể diễn giải giao thức trên thành các bước sau: 1. Người kiểm tra V chọn u,v ngẫu nhiên ∈ Zq và tính a = g u1 y v1 modp, rồi gửi a cho người xác nhận C 2. Người xác nhận C chọn k, k’, ngẫu nhiên ∈ Zq và tính r1 = g k1 ; r2 = g k2 ; r '1 = g ' 1 k ; r '2 = g ' 2 k Sau đó gửi r1, r2, r1’, r2’ cho V 3. Khi nhận được r1, r2, r1’, r2’ do C gửi, V gửi lại hai giá trị u, v 4. Người xác nhận, nhận được u, v thì kiểm tra đẳng thức Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -44- a = g u1 y v1 modp. 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 5. Người kiểm tra V sẽ kiểm tra xem các đẳng thức sau có xảy ra hay không? g z1 y wv+1 = r1 g '1z r wv+1 = r '1 g '2z r wv+2 = r '2 γ = ( g2z y wv+2 ≡ 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 1g (y1) ≡ log 2g (y2) và trả về 0 nếu log 1g (y1) ≠ log 2g (y2). Giao thức được ký hiệu như sau: Bi – Proof[log 1g (y1) ≡ log 2g (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 ∈ R Z q , 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 ∈ R Z q , 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 ∈ R Z q , tạo: α : = gr, αs : = P rS , αs+c : = (PSPC) r , gs : = PS, gs+c : =PSPC Sau đó tính σ1 = CP(r, α, αs+c, g, gs+c)(m) và σ2 = S(sr, g, αs)(σ1). => Chữ ký σ của người ký trên thông báo m là: σ = (σ1, σ2). 4.3. Kiểm tra chữ ký: Đầu tiên người kiểm tra sẽ kiểm tra độ tin cậy của (σ1, σ2) với σ1 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à σ2 là chữ ký Schnorr tin cậy trên σ1. 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α (αs) ≡ logg(gs)] Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -45- 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, σ, PS, PC) được tính: v = Bi-Proof [logg (gc ) ≡ logα (αc)] 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à αc = αs+c /αs. 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à σ1, σ2. Trong đó σ1 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 α = gr và αs+c = g r cs+ ; σ2 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 αs = g rs . 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 σ1, σ2 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α (αs). 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α (αs+c /αs). 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 Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -46- 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ý σ = (σ1, σ2) là chữ ký qua được sự kiểm tra chỉ nếu σ1 = CP(r, α, αs+c, g, gs+c)(m), σ2 = S(sr, g, αs)(σ1) và r1 = r2. Chứng minh: Nếu σ là tin cậy, (σ1 và σ2 được thành lập là σ1 = CP(r, α, αs+c, g, gs+c)(m), σ2 = S(sr, g, αs)(σ1). Còn lại chứng tỏ r1 = r2. Chúng ta giả sử rằng s khác 0. Chữ ký σ đượ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α (αc)]. Do đó nó chỉ ra rằng αc = αc hoặc αc = αs+c/ αs. Hơn nữa σ1, σ2 là đúng => tồn tại r1 và sr2, xem rằng:αs+c =g 1r cs+ = g(s+c)r 1 , αs = gsr 2 ⇒ αc = g 1cr = g 1)( rcs+ / g 2sr ⇒ g 1sr =g 2sr 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ý σ+ là tin cậy nếu σ+1 = CP(r1, α, αs+c, g, gs+c)(m), σ+2 = S(sr2, g, α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ả σ +1 và σ +2 , 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 σ+ mà không cần truy cập đến khóa bí mật s để đạt được hoặc σ +1 hoặc σ +2 . Giả sử A đạt được σ +1 , σ +2 hình thành từ chữ ký σ* = (σ +1 ,σ *2 ). Theo bổ đề trên, điều này có nghĩa là σ *2 , σ +2 đã được tạo ra cùng một khóa bí mật r2s => A biết bí mật để tạo σ *2 . Đ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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -47- 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 σ* = (σ *1 , σ *2 ) trên thông báo m được tính: σ *1 = CP(x, X, Xy+c, g, gy+c) và σ *2 = S(z, g, yz)( σ *1 ) 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 x cy+ 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à σ *1 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à σ *2 , 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 σ từ chữ ký giả mạo σ* 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 *q ) 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 σ*, σ+ 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 ], σ là chữ ký tin cậy, σ+ là chữ ký không tin cậy. Ngoài ra sự thuận lợi của A trong phân biệt σ* từ σ+ 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ừ σ* và σ+, 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 αs+c /αs = αc hoặc αs = αs. 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 αs+c /αs = αc hoặc αs = αs thì σ1 là phép chứng minh hợp lý của tri thức và đẳng thức, σ2 là chữ ký tin cậy, σ 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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -48- 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 ∈ R Z q r, r1, r2 ∈ R Z q α = gr αs = gsr αs+c = g r cs+ w2 = g 1r w1 = g 2r W1 = g 2r cs+ ⎯⎯⎯⎯⎯ ⎯← + 112 ¦,,,,, Wwwcss ααα β = pα β s = psα β cs+ = p cs+α w2 = w2p. g 2r w1 = w1p. g 1r 1Ω = W1p. g 1r v = H(m ⏐⏐ β ⏐⏐ sβ ⏐⏐ cs+β ⏐⏐w2⏐⏐w1⏐⏐ 1Ω ) u = v/p ⎯→⎯u v1 = r1 – u(r) v2 = r2 – u(rs) ⎯⎯← 21 ,vv 1υ = v1p + r1 2υ = v2p + r2 σ+1 = (v, 1υ , β , cs+β , w1, Ω 1) σ+2 = (v, 2υ , sβ , 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à σ = (σ+1, σ+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 σ1 = CP(r, α, αs+c, g, gs+c)(m), σ2 = S(sr, g, αs)(σ1) để tạo σ+1 = CP(rp, β, βs+c, g, gs+c)(m), Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -49- σ+2 = S(srp, g, βs)(σ+1) trong đó β = αp , βs = α ps và βs+c = α p cs+ . 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 σ+1 là chữ ký Chaum – Petersen tin cậy trên thông báo m và σ+2 là chữ ký Schnorr tin cậy trên thông báo ( m || σ+1) . Do đó σ = (σ+1, σ+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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -50- 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; Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -51- } //================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() { Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -52- 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; Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -53- 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++) { Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -54- 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:{ Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -55- 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) Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -56- { 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; Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -57- 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; Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -58- 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; Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -59- } //============================================================= 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); Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -60- 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!"); Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -61- 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(); } Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -62- 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. Đồ án tốt nghiệp Các chữ ký không chối bỏ được và ứng dụng Sinh viên thực hiện: Nguyễn Văn Tân Lớp: CT702 -63- TÀI LIỆU THAM KHẢO 1. Lý thuyết mật mã và an toàn thông tin – Phan Đình Diệu(NXB ĐHQGHN). 2. Bài giảng an toàn thông tin – TS. Nguyễn Ngọc Cương. 3. Cryptography Theory and Practice – DR. Stínon. 4. Designated Confirmer Signatures – David Chaum. 5. Khanh Nguyen, Yi Mu, Vijay Varadharajan - Undeniable Confirmer Signature. 6. Invisible Designated Confirmer Signatures without Random Oracles - Victor K. Wei. 7. Efficie Convertible Uderniable Signature Schemes .