Đồ án Tình hình tìm hiểu chữ kí nhóm và ứng dụng trong giao dịch điện tử

Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử 1 LỜI NÓI ĐẦU Trong xu hướng phát triển của thế giới và Việt Nam hiện nay, mạng Internet đang đem đến sự bùng nổ thông tin một cách mạnh mẽ. Nó được sử dụng để truyền thư điện tử, truy cập các website, kết nối các công sở, liên lạc với các khách hàng và sử dụng các dịch vụ ngân hàng, các giao dịch điện tử… Tiềm năng của mạng Internet là rất lớn. Như ta đã biết các giao tiếp, trao đổi thông tin qua Internet đều sử dụng giao thức TCP/IP. Các gói tin truyền từ điểm nguồn tới điểm đích sẽ đi qua rất nhiều máy tính trung gian, vì vậy độ an toàn thấp, nó rất dễ bị xâm phạm, theo dõi và giả mạo trên đường truyền. Vấn đề không an toàn cho thông tin trên đường truyền khiến nhiều người đắn đo trong việc sử dụng mạng Internet cho những ứng dụng về tài chính, giao dịch ngân hàng, hoạt động mua bán và khi truyền các thông tin kinh tế, chính trị vv… Những biện pháp đảm bảo an toàn thông tin đưa ra đều nhằm đáp ứng 3 yêu cầu: bảo mật thông tin, xác thực thông tin và toàn vẹn thông tin trên đường truyền. Các hệ mã hóa thông tin bảo đảm tính bí mật nội dung thông tin, các sơ đồ chữ ký số bảo đảm xác thực thông tin trên đường truyền. Tuy nhiên, nhu cầu của con người không chỉ dừng lại ở việc giao dịch giữa các cá nhân với nhau, mà còn giao dịch thông qua mạng giữa các nhóm người, các công ty, các tổ chức khác nhau trên thế giới. Dựa trên những yêu cầu thực tế đó các nhà khoa học đã nghiên cứu và đề xuất ra một kiểu chữ ký mới, đó chính là chữ ký nhóm. Trong đồ án này tôi đã tìm hiểu và nghiên cứu về chữ ký nhóm. Đây là một loại chữ ký điện tử cho phép một nhóm người tạo các chữ ký đại diện cho nhóm, và chỉ những thành viên trong nhóm mới có thể ký vào các thông điệp của nhóm. Người quản trị của nhóm có trách nhiệm thành lập nhóm và trong trường hợp cần thiết phải biết được ai là người ký vào thông điệp. Trong quá trình làm đồ án tốt nghiệp, em đã nhận được sự hướng dẫn tận tình của TS.Lê Phê Đô. Em xin chân thành cảm ơn! Đồng thời, em xin cảm ơn các thày cô giáo bộ môn Tin học – trường Đại học Dân lập Hải Phòng đã trang bị cho em những kiến thức cơ bản trong quá trình học tập tại trường. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 2 Chương I CÁC KHÁI NIỆM CƠ BẢN 1.1 Cơ sở toán học 1.1.1. Ước số - Bội số Định nghĩa : Ướ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à BCNN 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.1.2. Số nguyên tố Định nghĩa : Số nguyên tố là số chỉ chia hết cho 1 và chính nó, ngoài ra không còn số nào nó có thể chia hết nữa. Hệ mật thường sử dụng số nguyên tố lớn cỡ 512bits và thậm chí còn lớn hơn nữa. Hai số m và n gọi là hai số nguyên tố cùng nhau khi ước số chung lớn nhất của chúng bằng 1. Chúng ta có thể viết như sau: UCLN(m,n) = 1 1.1.3. Khái niệm nhóm Định nghĩa : Nhóm là bộ đôi (G, ∗ ), trong đó G là tập φ≠ và ∗ là một phép toán hai ngôi trong G thỏa mãn ba tiên đề sau 1. Phép toán nhóm kết hợp a * (b * c) = (a * b) * c ∀ a, b, c ∈G 2. Có một phần tử 0 ∈G được gọi là phần tử đơn vị thỏa mãn a * 0 = 0 * a ∀ a ∈G 3. Với mỗi a ∈G, tồn tại một phần tử a-1 ∈G được gọi là nghịch đảo a * a-1 = a-1 * a = 0 Nhóm được gọi là giao hoán (hay nhóm Abel) nếu a * b = b * a ∀ a, b ∈G 1.1.4. Nhóm hữu hạn Định nghĩa : Nhóm (G, ∗ ) hữu hạn nếu |G| là hữu hạn. Số các phần tử của nhóm G được gọi là cấp của nhóm. Ví dụ : ™ Tập các số nguyên Z với phép cộng sẽ tạo nên một nhóm. Phần tử đơn vị của nhóm này được kí hiệu là 0, phần tử ngược của một số nguyên a là số nguyên –a. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 3 ™ Tập Zn với phép cộng modulo tạo nên một nhóm cấp n. Tập Zn với phép toán nhân theo modulo n không phải là một nhóm vì không phải mọi phần tử của nhóm đều có nghịch đảo. Tuy nhiên tập Z *n sẽ là một nhóm cấp φ (n) với phép toán nhân theo modulo n và có phần tử đơn vị là 1. 1.1.5. Nhóm con Định nghĩa : Bộ đôi (S, ∗ ) được gọi là nhóm con của (G, ∗ ) nếu: ™ S ⊂ G, phần tử trung gían e ∈ S ™ x, y ∈ S ⇒ x * y ∈ S 1.1.6. Nhóm Cyclic Định nghĩa : Nhóm G được gọi là nhóm cyclic nếu tồn tại một phần tử α ∈ G sao cho với mỗi b ∈G có một số nguyên I sao cho b = αi. Phần tử α như vậy được gọi là phần tử sinh của G Nếu G là một nhóm và a ∈ G thì tập tất cả các lũy thừa của a sẽ tạo nên một nhóm con cyclic của G. Nhóm này được gọi là nhóm con sinh bởi a và được kí hiệu là a 1.1.7. Các thuật toán trong Z Cho a và b là các số nguyên không âm và nhỏ hơn hoặc bằng n. Cần chú ý rằng số các bit trong biểu diễn nhị phân của n là [lgn] + 1 và số này xấp xỉ bằng lg n. Số các phép toán bit đối với bốn phép toán cơ bản trên các số là cộng , trừ, nhân và chia sử dụng các thuật toán kinh điển được tóm lược trên bảng sau. Các kỹ thuật tinh tế hơn đối với các phép toán nhân và chia sẽ có độ phức tạp nhỏ hơn. Phép toán Độ phức tạp bit Cộng a + b Trừ a – b Nhân a * b Chia a = qb + r 0(lg a + lg b) = 0 (lg n) 0(lg a + lg b) = 0 (lg n) 0 ( )b) (lg*a) (lg = 0 ( )n)2 (lg 0 ( )b) (lg*a) (lg = 0 ( )n)2 (lg 1.1.8. Thuật toán Euclide : Tính UCLN của 2 số nguyên VÀO : Hai số nguyên không âm a và b với a > b RA : UCLN của a và b (1). while b ≠ 0 do R ← a mod b, a ← b, b ← r (2). Return (a) Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 4 1.1.9. Thuật toán Euclide mở rộng VÀO : Hai số nguyên không âm a và b với a > b RA : d = UCLN (a, b) và các số nguyên x và y thỏa mãn ax + by = d (1) Nếu b = 0 thì đặt d ← a, x ← l, y ← 0 và return (d, x, y) (2) Đặt x2 ← l, x1 ← 0, y2 ← 0, y1 ← l (3) while b > 0 do 1. q ← [a/b], r ← a – qb, x ← x2 – qx1 , y ← y2 – qy1 2. a ← b, b ← r, x2 ← x1, x1 ← x, y2 ← y1 , y1 ← y (4) Đặt d ← a, x ← x2, y ← y2 và return (d, x, y) 1.1.10. Định nghĩa hàm Φ Euler Định nghĩa : Với n≥1 chúng ta gọi φ (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ố → φ (p) = p-1 ™ Nếu p=m.n , gcd(m,n)=1 → φ (p)= φ (m).φ (n) ™ Nếu n = kekeee pppp ....321 321 là thừa số nguyên tố của n thì → φ (n) = n ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − kppp 11...1111 21 1.1.11. Đồng dư thức Định nghĩa : Cho a và b là hai số nguyên tố, a được gọi là đồng dư với b theo modulo n, ký hiệu là a ≡ b(mod n) nếu a, b chia cho n có cùng số dư. Ví dụ : 24 ≡ 9 mod 5 vì 24 - 9 = 3 * 5 -11 ≡ 17 mod 7 vì -11 - 17 = -4 * 7 Tính chất : Đối với a, a1, b, b1, c ∈ Z ta có : ™ a ≡ a (mod n) ™ a ≡ b (mod n) ↔ b ≡ a (mod n) ™ a ≡ b (mod n) , b ≡ c (mod n) → a ≡ c (mod n) ™ a ≡ a1 (mod n) , b ≡ b1 (mod n) a+b≡ a1+b1 (mod n) a.b ≡ a1.b1 (mod n) 1.1.12. Số nghịch đảo Định nghĩa : Cho a ∈ Zn. Một số nguyên x ∈ Zn gọi là nghịch đảo của a theo mod n nếu a.x ≡ 1mod n.. Nếu có số x như vậy thì nó là duy nhất và ta nói a là khả nghịch. Ký hiệu là a -1 . Có thể suy ra rằng a khả nghịch theo mod n khi và chỉ khi gcd (a,n)=1. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 5 1.1.13. Nhóm nhân Z*n Định nghĩa : 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. Đặc biệt với n là số nguyên tố thì Z*n={ a ∈ Zn | 1≤a≤n-1} Định nghĩa : Cho a ∈ Z*n khi đó bậc của a kí hiệu là ord (a) là một số nguyên dương t nhỏ nhất sao cho a t ≡ 1(mod n). 1.1.14. Định nghĩa thặng dư bậc 2 Định nghĩa : Cho a ∈ Z*n gọi a là thặng dư bậc 2 theo modulo n nếu tồn tại x sao cho x2 ≡ a (mod n) . Nếu không tồn tại thì gọi a là bất thặng dư bậc 2. Tập tất cả các thặng dư bậc hai modulo n được kí hiệu là nQ , còn tập tất cả các thặng dư không bậc hai được kí hiệu là nQ . 1.1.15. Phần dư China CRT ( Chinese Remainder Theorem) Nếu các số nguyên n1, n2, …, nk là nguyên tố cùng nhau từng thì hệ các phương trình đồng dư: x ≡ a1 (mod n1) x ≡ a2 (mod n2) ……………… x ≡ ak (mod nk) sẽ có nghiệm duy nhất theo modulo n (n = n1, n2, …, nk) x = ∑ = k i 1 ai Ni Mi mod n Trong đó Ni = n / ni và Mi = N 1−i mod ni Các tính toán này có thể được thực hiện bởi 0 ( ))2n (lg các phép toán trên bit. Ví dụ : Cặp phương trình đồng dư x ≡ 5 (mod 9) x ≡ 19 (mod 23) có nghiệm duy nhất x ≡ 203 (mod 207) Tính chất Nếu (n1, n2) = 1 thì cặp phương trình đồng dư x ≡ a (mod n1), x ≡ a (mod n2) có một nghiệm duy nhất x ≡ a (mod n1, n2) 1.1.16. Độ phức tạp tính toán Lý thuyết thuật toán và các hàm số tính được ra đời từ những năm 30 của thế kỉ 20 đã đặt nền móng cho việc nghiên cứu các vấn đề “ tính được ”, “ giải được ” trong toán học. Tuy nhiên từ các “ tính được ” đến việc tính toán thực tế là một khoảng cách rất lớn. Có rất nhiều vấn đề chứng minh là có thể tính được nhưng không tính được trong thực tế dù có sự trợ giúp của máy tính. Vào những năm 1960 lý thuyết độ phức tạp Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 6 tính toán được hình thành và phát triển nhanh chóng, cung cấp nhiều hiểu biết sâu sắc về bản chất phức tạp của các thuật toán và các bài toán, cả những bài toán thuần túy lý thuyết đến những bài toán thường gặp trong thực tế. Độ phức tạp tính toán của một tiến trình tính toán là số ô nhớ được dùng hay số các phép toán sơ cấp được thực hiện trong tiến trình tính toán đó. Dữ liệu đầu vào đối với một thuật toán thường được biểu diễn qua các từ trong một bảng kí tự nào đó. Độ dài của một từ là số kí tự trong từ đó. 1.1.17. Các thuật toán trong Zn Cho n là một số nguyên dương. Các phần tử của Zn sẽ được biểu thị bởi các số nguyên Q21 = {0, 1, 2, … n-1}. Ta thấy rằng, nếu a, b ∈ Zn thì (a + b) mod n = Bởi vậy phép cộng ( và trừ ) theo modulo có thể thực hiện đựợc mà không cần phép chia. Phép nhân modulo của a và b có thể được thực hiện bằng cách nhân các số nguyên thông thường rồi lấy phần dư của kết quả sau khi chia cho n. Các phần tử nghịch đảo trong Zn có thể được tính bằng cách dùng thuật toán Euclide mở rộng được mô tả dưới đây: 1.1.18. Thuật toán ( Tính các nghịch đảo trong Zn ) VÀO : a ∈ Zn RA : a-1 mod n (nếu tồn tại) 1. Dùng thuật toán Euclide mở rộng để tìm các số nguyên x và y sao cho ax + ny = d trong đó d = (a, n) 2. Nếu d >1 thì a-1 mod n không tồn tại. Ngược lại return (x) Phép lũy thừa theo modulo có thể được thực hiện có hiệu quả bằng thuật toán nhân và bình phương có lặp. Đây là một thuật toán rất quan trọng trong nhiều thủ tục mật mã. Cho biểu diễn nhị phân của a là : ∑ = t i 0 ki2i trong đó mỗi ki ∈ {0, 1} khi đó a + b với a + b < n a + b – r.n với a + b ≥ n Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 7 ak = k t i kia 2 0 ∏ = = ( ) ( ) ( ) tt kkk aaa 222 ...1100 Thuật toán nhân và bình phương có lặp để lấy lũy thừa trong Z n VÀO : a ∈ Zn và số nguyên k, (0 ≤ k < n) có biểu diễn nhị phân : k = i t i ik 2 0 ∑ = RA : ak mod n 1. Đặt b ← l. Nếu k = 0 thì return (b) 2. Đặt A ← a 3. Nếu k0 = 1 thì đặt b ← a 4. for i from l to t do 1. Đặt A ← A2 mod n 2. Nếu ki = l thì đặt b ← A*b mod n 5. Return (b). Số các phép toán bit đối với phép toán cơ bản trong Zn Phép toán Độ phức tạp bit Cộng modulo 0(lg n) Trừ modulo 0(lg n) Nhân modulo 0 ( )2)(lg n Nghịch đảo modulo 0 ( )2)(lg n Lũy thừa modulo 0 ( )3)(lg n Độ phức tạp bit của các phép toán cơ bản trong Zn Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 8 1.1.19. Hàm một phía - Hàm một phía có cửa sập Một hàm một phía là hàm mà dễ dàng tính toán ra quan hệ một chiều nhưng rất khó để tính ngược lại. Ví dụ : Biết giả thiết x thì có thể dễ dàng tính ra f(x), nhưng nếu biết f(x) thì rất khó tính ra được x. Trong trường hợp này khó có nghĩa là để tính ra được kết quả thì phải mất rất nhiều thời gian để tính toán. F(x) được gọi là hàm một phía có cửa sập nếu tính xuôi y = f(x) thì dễ nhưng tính ngược x =f 1− (y) thì khó tuy nhiên nếu có “ cửa sập ” thì vấn đề tính ngược trở nên dễ dàng. Cửa sập ở đây là một điều kiện nào đó giúp chúng ta dễ dàng tính ngược. Ví dụ : y = f(x) = xb mod n tính xuôi thì dễ nhưng tính ngược x = ya mod n thì khó vì phải biết a với a * b ≡ 1 ( )))(mod( nφ trong đó φ (n) = (p-1)(q-1). Nhưng nếu biết cửa sập p, q thì việc tính n = p * q và tính a trở nên dễ dàng. Hộp thư là một ví dụ về hàm một phía có cửa sập. Bất kỳ ai cũng có thể bỏ thư vào thùng. Bỏ thư vào thùng là một hành động công cộng. Mở thùng thư không phải là hành động công cộng. Nó là việc khó khăn, bạn sẽ cần đến mỏ hàn để phá hoặc những công cụ khác. Hơn nữa nếu bạn có “ cửa sập ” ( Trong trường hợp này là chìa khóa của hòm thư ) thì công việc mở hòm thư thật dễ dàng. 1.2 Tìm hiểu về mật mã Mật mã học là khoa học nghiên cứu sự an toàn, toàn vẹn của dữ liệu, xác nhận sự tồn tại và xác nhận tính nguyên bản của thông tin. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 9 Sơ đồ khối một hệ truyền tin mật Định nghĩa : Một hệ mật mã là một bộ năm (P, C, K, E, D) thoả mãn các điều kiện sau đây: + 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ã e k ∈ E e k : P → C và một hàm giải mã d k ∈ D d k : C → P sao cho d k ( )(x)ek = x với mọi x ∈P Trong thực tế, P và C thường là bảng chữ cái (hoặc tập các dãy chữ cái có độ dài cố định). 1.2.1. Mã cổ điển Hệ mã cổ điển (hệ mã đối xứng) là hệ mật mã mà khóa mã hóa có thể dễ dàng tìm được từ khóa giải mã và ngược lại. Trong nhiều trường hợp, khóa mã hóa và khóa giải mã là giống nhau. Hệ mật mã cổ điển yêu cầu người gửi và người nhận phải thỏa thuận một mã trước khi tin tức được gửi đi, khóa này phải được cất giữ bí mật. Độ an toàn của hệ này phụ thuộc vào khóa. Nếu để lộ khóa, thì bất kỳ người nào cũng có thể mã hóa và giải mã thông điệp đó. Nguồn tin Bộ mã hóa Kênh mở (không an toàn) Bộ giải mã Nhận tin Thám mã Kênh an toàn Nguồn khóa Bản rõ Bản mã Bản mã KD KE B A Bản rõ Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 10 ™ Các đặc điểm của hệ mã cổ điển 1. Các phương pháp mã hóa cổ điển đòi hỏi người mã hóa và người giải mã phải có cùng chung một khóa. 2. Khóa phải được giữ bí mật tuyệt đối, khóa phải được gửi đi trên kênh an toàn. Vì dễ dàng xác định một khóa nếu biết khóa kia. 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 kịp thời. Ưu điểm là tốc độ mã hóa và giải mã rất nhanh. Các hệ mật mã cổ điển cũng dùng chung một khoá cho việc lập mã và giải mã, các bản rõ và bản mã thường dùng cơ sở là bảng chữ cái trong ngôn ngữ tự nhiên. Và trong phần này ta sẽ dùng bảng chữ cái tiếng Anh làm ví dụ. ™ Nơi ứng dụng Hệ mã cổ điển thường được sử dụng trong môi trường mà khóa có thể dễ dàng trao chuyển bí mật. Nó cũng được dùng để mã hóa thông tin khi lưu trữ trên đĩa. 1.2.1.1. Mã dịch chuyển Định nghĩa : Mã dịch chuyển: (P, C, K, E, D) P = C = K = Z 26 với k ∈ K, định nghĩa e k (x) = (x + k) mod 26 d k (y) = (y – k) mod 26 (x, y ∈ Z 26 ) Ví dụ: Dùng khoá k = 2 để mã hoá dòng thư: "madichchuyen'" dòng thư đó tương ứng với dòng số m a d i c h c h u y e n 12 0 3 8 2 7 2 7 20 24 4 13 Qua phép mã hoá e 2 sẽ được: 14 2 5 10 4 9 4 9 22 26 6 15 o c f k e j e j w z g p Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 11 Bản mã sẽ là: “ocfkejejwzgp” Nhận được bản mã đó, dùng d 2 để 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 Z m 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. 1.2.1.2. Mã thay thế Định nghĩa Mã thay thế: (P, C, K, E, D) P = C = Z 26 , K = S (Z 26 ) Với mỗi π є K, tức là một hoán vị trên Z 26 , ta xác định e π (x) = π (x) d π (y) = π -1 (y) với x, y є Z 26 , π -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 Z 26 ): a b c d e f g h i j k l m n z y x w v u t s r q p o n m o p q r s t u v w x y z l k j i h g f e d c b a Bản rõ: “mathaythe” sẽ được mã hoá thành bản mã (với khoá π): “nzgszbgsv” 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 Z 26 , hay là 26! > 4.10 26 . 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ễ Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 12 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 1.2.1.3. Mã Affine Định nghĩa Mã Affine: (P, C, K, E, D) P = C = Z 26 , K = { (a, b) є Z 26 x Z 26 : (a, 26) = 1 } với mỗi k = (a, b) є K ta định nghĩa: e k (x) = ax + b mod 26 d k (y) = a -1 (y – b) mod 26 trong đó x, y є Z 26 Ví dụ: Lấy k = (5, 6). Bản rõ: “maaffine” m a a f f i n e x 12 0 0 5 5 8 13 4 Y=5x + 6 mod 26 14 6 6 5 5 20 19 0 y o g g f f u t a Bản mã: “oggffuta” Thuật toán giải mã trong trường hợp này có dạng: d k (y) = 21(y − 6) mod 26 Với mã Affine, 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ã Affine cũng không phải là mã an toàn Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 13 1.2.1.4. Mã Vingenere Định nghĩa Mã Vingenere: (P, C, K, E, D) Cho m là số nguyên dương. P = C = K = (Z 26 )m với mỗi khoá k = (k 1 , k 2 ,…,k m ) ∈ K có: e k (x 1 , x 2 ,…, x m ) = (x 1 + k 1 , x 2 + k 2 ,…, x m + k m ) d k (y 1 , y 2 ,…, y m ) = (y 1 – k 1 , y 2 – k 2 ,…, y m – k m ) 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õ: “mavingenere” m a v i n g e n e r e x 12 0 21 8 13 6 4 13 4 17 4 k 2 8 15 7 4 17 2 8 15 7 4 y 14 8 10 15 17 23 6 21 19 24 8 o i k p r x g v t y i Bản mã “ oikprxgvtyi ” Từ bản mã đó, dùng phép giải mã d k tương ứng, ta lại thu được bản rõ. Chú ý: Mã Vingenere với m = 1 sẽ trở thành mã Dịch chuyển. Tập hợp các khoá trong mã Vingenere mới m ≥ 1 có tất cả là 26 m 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. 1.2.1.5. Mã Hill Định nghĩa Mã Hill: (P, C, K, E, D) Cho m là số nguyên dương. P = C = (Z 26 )m Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 14 K = { k ∈ (Z 26 )mxm mxm : ( )26 det(k), = 1 } với mỗi k ∈ K định nghĩa: e k (x 1 , x 2 ,…, x m ) = (x 1 , x 2 ,…, x m ).k d k (y 1 , y 2 ,…, y m ) = (y 1 , y 2 ,…,y m ).k -1 Ví dụ: Lấy m = 2, và k = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 73 811 Với bộ 2 ký tự (x 1 , x 2 ), ta có mã là (y 1 , y 2 ) = (x 1 , x 2 ). k được tính bởi y 1 = 11.x 1 + 3.x 2 y 2 = 8.x 1 + 7.x 2 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ó k = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba Ta có ma trận nghịch đảo k 1− = 1− ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba Và được tính như sau 1− ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba = ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ −− − − − − bcad a bcad c bcad b bcad d Một chú ý là để phép chia luôn thực hiện được trên tập Z 26 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 Z 26 , 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. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 15 Khi đó: k -1 .k = I là ma trận đơn vị (đường chéo chính bằng 1) 1− ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba = ⎟⎟ ⎟⎟ ⎠ ⎞ ⎜⎜ ⎜⎜ ⎝ ⎛ −− − − − − bcad a bcad c bcad b bcad d ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ dc ba = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 10 01 Định thức của ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 73 811 Là 11*7 – 8*3 = 1 ≡ 1 mod 26 Khi đó 1 73 811 − ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ = ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − − 113 87 ≡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ 1123 187 mod 26 1.2.1.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 = Z 26 , K = S m ( )mk xxxe ...,,, 21 = ( ) ( ) ( )( )mxxx πππ ...,,, 21 ( )mk yyyd ...,,, 21 = ( ) ( ) ( )( )myyy 111 ...,,, 21 −−− πππ với mỗi k = π ∈ S m , ta có Trong đó π -1 là hoán vị nghịch đảo của π Ví dụ: Giả sử m = 4, và khoá k được cho bởi phép hoán vị π Khi đó phép hoán vị nghịch đảo π -1 là: 1 2 3 4 2 3 4 1 1 2 3 4 4 1 2 3 Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 16 Bản rõ: “ mahoanvi ” m a h o a n v i vt 1 2 3 4 1 2 3 4 π 1→2 2→3 3→4 4→1 1→2 2→3 3→4 4→1 vt 2 3 4 1 2 3 4 1 a h o m a h o m Bản mã: “ ahomahom ” 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 π = (k ij ), 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ế) 1.2.2. Mã khóa công khai Trong mô hình mật mã cổ điển trước đây mà hiện nay đang được nghiên cứu, A(người gửi) và B (người nhận) chọn khóa bí mật K. Sau đó dùng K để tạo luật mã hóa ek và luật giải mã dk. Trong hệ mật này dk hoặc giống ek hoặc khác, nếu để lộ ek thì làm cho hệ thống mất an toàn. Nhược điểm của hệ mật này là nó yêu cầu phải có thông tin trước về khóa K giữa A và B qua một kênh an toàn trước khi gửi một bản mã bất kỳ. Trên thực tế điều này rất khó đảm bảo. Chẳng hạn khi A và B ở cách xa nhau và họ chỉ có thể liên lạc với nhau bằng E-mail. Trong tình huống đó A và B không thể tạo một kênh bảo mật với giá phải chăng. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 17 Ý tưởng xây dựng một hệ mật khóa công khai là tìm một hệ mật không có khả năng tính tóan để xác định dk khi biết ek. Nếu thực hiện được như vậy thì quy tắc mã ek có thể được công khai bằng cách công bố nó trong một danh bạ (bởi vậy nên có thuật ngữ hệ mật khóa công khai). Ưu điểm của hệ mật khóa công khai là ở chỗ A (hoặc bất kỳ A) có thể gửi một bản tin đã mã hóa cho B (mà không cần thông tin trước về khóa mật) bằng cách dùng mật mã công khai ek. Người nhận A sẽ là người duy nhất có thể giải mã được bản mã này bằng việc sử dụng luật giải bí mật dk của mình. Có thể hình dung hệ mật này tương tự như sau: A đặt một vật vào một hộp kim loại và rồi khóa nó lại bằng một khóa số do B để lại. Chỉ có B là người duy nhất có thể mở được hộp vì chỉ có anh ta mới biết tổ hợp mã của khóa số của mình. Ý tưởng về một hệ mật khóa công khai được Diffie và Hellman đưa ra vào năm 1976. Còn việc hiện thực hóa nó thì do Riyesrt, Shamir và Ableman đưa ra lần đầu vào năm 1977, họ đã tạo nên hệ mật nổi tiếng RSA và một số hệ mật khác. Độ bảo mật của hệ RSA dựa trên độ khó của việc phân tích ra thừa số nguyên lớn. ™ Nơi ứng dụng Sử dụng chủ yếu trên các mạng công khai như Internet, khi mà việc trao chuyển khóa bí mật tương đối khó khăn. Đặc trưng nổi bật của hệ mã hóa khóa công khai là cả khóa công khai và bản mã đều có thể gửi đi trên một kênh thông tin không an toàn. 1.2.2.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 φ(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 φ(n)} Với K = (n, p, q, a, b) ta xác định: eK (x) = xb mod n và dK (y) = ya mod n (x, y ∈ Zn) Các giá trị n và b được công khai và các giá trị p, q, a được giữ kín Ví dụ: Chọn p = 2, q = 5. Tính n = p.q = 2*5 = 10 φ(n)= (p – 1).(q – 1) = 1*4 = 4 Do UCLN(φ(n), b) = 1 nên chọn b = 3 Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 18 a.b ≡ 1 mod φ(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(x)= xb mod n = 33 mod 10 = 7 Khi N nhận được bản mã y = 7, anh ta sử dụng số mũ a mật để tính: x = dK(y) = 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(x) = xb mod n là hàm một chiều. Bởi vậy thám mã sẽ gặp khó khăn 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 φ(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. 1.2.2.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, α, β) trong đó p là số nguyên tố, α ∈ pZ là phần tử nguyên thuỷ (hay phần tử sinh), β ∈ *pZ Mục tiêu: Hãy tìm một số nguyên duy nhất a, 0 ≤ a ≤ p – 2 sao cho: αa ≡ β (mod p) Ta sẽ xác định số nguyên a bằng log α β. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 19 Định nghĩa mã hoá công khai Elgamal trong *pZ : Cho p là số nguyên tố sao cho bài toán logarithm rời rạc trong pZ là khó giải. Cho α ∈ *pZ là phần tử nguyên thuỷ. Giả sử P = *pZ , C = *pZ x *pZ . Ta định nghĩa: K = {(p, α, a, β): β ≡ αa (mod p)} Các giá trị p, α, β được công khai, còn a giữ kín. Với K =(p, α, a, β) và một số ngẫu nhiên bí mật k ∈ 1−pZ , ta xác định: eK(x, k) = (y1, y2). Trong đó: y1 = αk mod p y2 = x. βk mod p với y1, y2 ∈ *pZ ta xác định: dK(y1, y2) = y2(y1a) – 1 mod p Ví dụ: Chọn p = 7 α ∈ *pZ là phần tử nguyên thuỷ nên α = 3 Chọn a sao cho 0 ≤ a ≤ p – 2 nên a = 2 Khi đó : β = αa mod p = 32 mod 7 = 2 Chọn một số ngẫu nhiên bí mật k ∈ 1−pZ , 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 = αk mod p = 33 mod 7 = 6 y2 = x. βk 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á Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 20 Chương II CHỮ KÍ ĐIỆN TỬ 2.1. Tìm hiểu về chữ ký điện tử ( electronic signature ) 2.1.1. Khái quát về chữ ký điện tử ? Về căn bản, khái niệm chữ ký điện tử (electronic signature) cũng giống như chữ viết tay. Bạn dùng nó để xác nhận lời hứa hay cam kết của mình và sau đó không thể rút lại được. Chữ ký điện tử không đòi hỏi phải sử dụng giấy mực, nó gắn đặc điểm nhận dạng của người ký vào một bản cam kết nào đó, nó là đoạn dữ liệu ngắn đính kèm với văn bản gốc để chứng thực tác giả của văn bản và giúp người nhận kiểm tra tính toàn vẹn của nội dung văn bản gốc. Con người đã sử dụng các hợp đồng dưới dạng điện tử từ hơn 100 năm nay với việc sử dụng mã Morse và điện tín. Vào năm 1889, tòa án tối cao bang New Hampshire (Hoa kỳ) đã phê chuẩn tính hiệu lực của chữ ký điện tử. Tuy nhiên, chỉ với những phát triển của khoa học kỹ thuật gần đây thì chữ ký điện tử mới đi vào cuộc sống một cách rộng rãi. Vào thập kỷ 1980, các công ty và một số cá nhân bắt đầu sử dụng máy fax để truyền đi các tài liệu quan trọng. Mặc dù chữ ký trên các tài liệu này vẫn thể hiện trên giấy nhưng quá trình truyền và nhận chúng hoàn toàn dựa trên tín hiệu điện tử. Hiện nay, chữ ký điện tử có thể bao hàm các cam kết gửi bằng email, nhập các số định dạng cá nhân (PIN) vào các máy ATM, ký bằng bút điện tử với thiết bị màn hình cảm ứng tại các quầy tính tiền, chấp nhận các điều khoản người dùng (EULA) khi cài đặt phần mềm máy tính, ký các hợp đồng điện tử online. Chữ ký điện tử được tạo ra bằng cách áp dụng thuật toán Băm một chiều trên văn bản gốc để tạo ra bản phân tích văn bản (message digest) hay còn gọi là fingerprint, sau đó mã hóa bằng private key tạo ra chữ ký số đính kèm với văn bản gốc để gửi đi. Khi nhận, văn bản được tách làm 2 phần, phần văn bản gốc được tính lại fingerprint để so sánh với fingerprint cũ cũng được phục hồi từ việc giải mã chữ ký số. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 21 So sánh chữ ký thông thường và chữ ký diện tử Chữ ký thông thường Chữ ký điện tử Vấn đề ký một tài liệu Chữ ký chỉ là một phần vật lý của tài liệu Vấn đề ký một tài liệu Chữ ký điện tử không gắn kiểu vật lý vào bức thông điệp nên thuật toán được dùng phải “không nhìn thấy” theo một cách nào đó trên bức thông điệp Vấn đề về kiểm tra Chữ ký được kiểm tra bằng cách so sánh nó với chữ ký xác thực khác. Tuy nhiên, đây không phải là một phương pháp an toàn vì nó dễ bị giả mạo. Vấn đề về kiểm tra Chữ ký điện tử có thể kiểm tra nhờ dùng một thuật toán “kiểm tra công khai”. Như vậy, bất kì ai cũng có thể kiểm tra được chữ ký điện tử. Việc dùng chữ ký điện tử an toàn có thể chặn được giả mạo. Bản copy thông điệp được ký bằng chữ ký thông thường lại có thể khác với bản gốc. Bản copy thông điệp được ký bằng chữ ký điện tử thì đồng nhất với bản gốc, điều này có nghĩa là cần phải ngăn chặn một bức thông điệp ký số không bị dùng lại. 2.1.2. Định nghĩa về sơ đồ ký điện tử Một sơ đồ chữ ký S là một bộ năm S = (P , A , K , S , V) Trong đó: P là một tập hữu hạn các thông báo có thể có, A là một tập hữu hạn các chữ ký có thể có, K là một tập hữu hạn các khoá, mỗi khoá K ∈ K gồm có hai phần K=(K’,K''), K' là khoá bí mật dành cho việc ký, còn K'' là khoá công khai dành cho việc kiểm thử chữ ký. Với mỗi K =(K’,K''), trong S có một thuật toán ký sigk’ : P → A , và trong V có một thuật toán kiểm thử verk” : PxA → {đúng,sai} thoả mãn điều kiện sau đây đối với mọi thông báo x ∈ P và mọi chữ ký y ∈ A : verk” (x, y) = đúng ↔ y = sigk’ (x ) Với sơ đồ trên, mỗi chủ thể sở hữu một bộ khoá K =(K’,K''), công bố công khai khoá K'' để mọi người có thể kiểm thử chữ ký của mình, và giữ bí mật khoá K’ để thực hiện chữ ký trên các thông báo mà mình muốn gửi đi. Các hàm verk” và sigk’ Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 22 (khi biết K’) phải tính được một cách dễ dàng (trong thời gian đa thức), tuy nhiên hàm y = sigk’ (x ) là khó tính được nếu không biết K’ - điều đó bảo đảm bí mật cho việc ký, cũng tức là bảo đảm chống giả mạo chữ ký. Các chữ ký số phải thỏa mãn điều kiện cơ bản sau : ™ Không thể giả mạo. Nếu P ký thông báo M bằng chữ ký F(P,M) thì không ai có thể tạo được cặp [M.S(M.P)] ™ Xác thực : nếu R nhận được cặp [M.S(M.P)] được coi là của P thì R có thể kiểm tra được rằng chữ ký có thực sự là của P hay không ? Chỉ có P mới có thể tạo được chữ ký này và chữ ký được ″gắn chặt″ với M. Hai yêu cầu đầu tiên này là những trở ngại chính trong giao dịch qua máy tính. Hai tính chất bổ trợ sau là những tính chất mong muốn đối với giao dịch được hoàn tất nhờ chữ ký số. ¾ Không thể thay đổi : sau khi được phát M không thể thay đổi bởi F.R hoặc bởi một kẻ thu trộm nào. ¾ Không thể sử dụng lại : một thông báo trước đó được đưa ra sẽ ngay lập tức bị R phát hiện. 2.1.3. Sơ đồ chữ ký RSA Sơ đồ chữ ký RSA được cho bởi bộ năm S = (P , A , K , S , V) Trong đó : P = A =Zn , với n =p.q là tích của hai số nguyên tố lớn p,q K là tập các cặp khoá K =(K’,K''), với K’ = a và K'' = (n,b) a và b là hai số thuộc Z* n thoả mãn a.b ≡ 1(modφ (n)). Các hàm sigk’ và verk” được xác định như sau: sigk’ (x) = x a modn , verk” (x,y ) = đúng ↔ x ≡ y b (modn). Dễ chứng minh được rằng sơ đồ được định nghĩa như vậy là hợp thức, tức là với mọi x ∈ P và mọi chữ ký y ∈ A: verk” (x,y ) = đúng ↔ y = sigk’ (x) Chú ý rằng tuy hai vấn đề xác nhận và bảo mật theo sơ đồ RSA là có bề ngoài giống nhau, nhưng nội dung của chúng là hoàn toàn khác nhau: Khi A gửi thông báo x cho B, để B có căn cứ xác nhận đó đúng thực là thông báo do A gửi, A phải gửi kèm theo chữ ký sigk’ (x), tức là A gửi cho B (x, sigk’ (x)), trong các thông tin gửi đi đó, thông báo x hoàn toàn không được giữ bí mật. Cũng tương tự như vậy, nếu dùng sơ đồ mật mã RSA, khi một chủ thể A nhận được một bản mật mã ek’(x) từ B thì A chỉ biết rằng thông báo x được bảo mật, chứ không có gì để xác nhận x là của B. Nếu ta muốn hệ truyền tin của ta vừa có tính bảo mật vừa có tính xác nhận, thì ta phải sử dụng đồng thời hai hệ mật mã và xác nhận (bằng chữ ký). Giả sử trên mạng Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 23 truyền tin công cộng, ta có cả hai hệ mật mã khoá công khai S1 và hệ xác nhận bằng chữ ký S2. Giả sử B có bộ khoá mật mã K = (K', K'') với K' = (n, e) và K'' = d trong hệ S1, và A có bộ khoá chữ ký Ks = (K’s , K''s) với K’s = a và K''s = (n,b) trong hệ S2. 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 ký trên thông báo x trước, rồi thay cho việc gửi đến B văn bản cùng chữ ký (x,sigk’s(x)) thì A sẽ gửi cho B bản mật mã của văn bản đó được lập theo khoá công khai của B, tức là gửi cho B ek’((x, sigk’s (x)). Nhận được văn bản mật mã đó B sẽ dùng thuật toán giải mã dk’’ của mình để thu được (x, sigk’s (x)), sau đó dùng thuật toán kiểm thử chữ ký công khai verk”s của A để xác nhận chữ ký sigk’s(x) đúng là của A trên x. 2.1.4. Sơ đồ chữ ký Elgamal Sơ đồ chữ ký ElGamal được đề xuất năm 1985, gần như đồng thời với sơ đồ hệ mật mã ElGamal, cũng dựa trên độ khó của bài toán lôgarit rời rạc. Sơ đồ được thiết kế đặc biệt cho mục đích ký trên các văn bản điện tử, được mô tả như một hệ: S = (P , A , K , S , V) Trong đó P = Z*p , A = Z*p x Zp-1, với p là một số nguyên tố sao cho bài toán tính lôgarit rời rạc trong Z*p là rất khó. Tập hợp K gồm các cặp khoá K=(K’,K''), với K’=a là một số thuộc Z*p , K'' =(p, α , β), α là một phần tử nguyên thuỷ của Z*p , và β=αamodp. K’ là khoá bí mật dùng để ký, và K'' là khoá công khai dùng để kiểm thử chữ ký. Các thuật toán ký và kiểm thử chữ ký được xác định như sau: Với mỗi thông báo x, để tạo chữ ký trên x ta chọn thêm môt số ngẫu nhiên k ∈ Z*p-1 , rồi tính : sig k’ (x,k ) = (γ , δ) với γ = α k modp, δ = (x – a.γ). k-1 mod(p -1). Thuật toán kiểm thử được định nghĩa bởi: verk” (x,(γ , δ)) = đúng ↔ β γ . γ δ ≡ α x (modp). Dễ thấy rằng sơ đồ chữ ký được định nghĩa như trên là hợp thức. Thực vậy, nếu sigk’(x,k ) = (γ , δ) thì ta có : β γ . γ δ ≡ α aγ. α kδ mod p ≡ α x mod p, vì k.δ +a.γ ≡ x mod(p -1). Do đó, verk” (x,(γ , δ)) = đúng. Ví dụ: Giả sử p = 467, α = 2, a = 127. Khi đó β = 2127mod467=132. Cho x =100; ta chọn ngẫu nhiên k =213 (∈ Z*466 ) và được k-1mod466 = 431. Chữ ký trên văn bản x=100 với số ngẫu nhiên k =213 là (γ , δ), trong đó γ =2213mod467 = 29 và δ = (100 - 127.29).431mod466 =51. Để kiểm thử ta tính : β γ . γ δ = 13229.2951 ≡ 189 (mod467), Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 24 α x = 2100 ≡ 189 (mod467), hai giá trị đó đồng dư với nhau theo mod 467, chữ ký (β γ . γ δ) = (29,51) được xác nhận là đúng. 2.1.5. Sơ đồ chữ ký DSS Sơ đồ chữ ký DSS được cho bởi bộ năm S = (P , A , K , S , V) Trong đó P = Z*p , A = Z*q x Z*q p là một số nguyên tố lớn có độ dài biểu diễn 512 ≤ lp ≤ 1024 bit (với l là bội của 64) sao cho bài toán tính logarit rời rạc trong Zp là khó. q là một ước số nguyên tố của p -1 có lq biểu diễn cỡ 160 bit. Gọi α ∈ Z*p ,α = h(p-1)/q mod p ≠ 1 với 1<h<p-1 a là số ngẫu nhiên (0 < a < q ) β ≡ αa modp. k là số ngẫu nhiên (0 < k < q ) K=(K’,K''), trong đó khoá bí mật K’ = a, và khoá công khai K'' = (p,q, α, β). ™ Hàm ký sigk’ : sigk’ (x,k ) = (γ , δ) Trong đó γ = (αk modp) modq, δ = (x + a. γ).k-1 modq. ™ Hàm kiểm thử verk” : verk” (x,(γ , δ)) = đúng ↔ ( 21 . ee βα modp)modq = γ , Trong đó e1 = x . w và e2 = γ. w với w = δ-1 mod q Chú ý rằng ta phải có δ ≠ 0 mod q để có thể tính được δ-1mod q dùng trong thuật toán kiểm thử, vì vậy nếu chọn k mà được δ ≡ 0 mod q thì phải chọn lại số k khác để có được δ ≠ 0 mod q. Cũng dễ thấy rằng sơ đồ như trên là đúng. Thực vậy nếu x, γ,δ là đúng thì : ( 21 . ee βα modp)modq = (αx.w. β γ.w mod p) mod q = (αx.w. αa. γ.w mod p) mod q = (α(x+a.γ).w mod p) mod q (1) Hơn nữa w = δ-1 mod q = (x + a.γ)-1.k mod q → (x + a. γ).w = k mod q (2) Từ (1) và (″) → ( 21 . ee βα mod p)mod q = (αk mod p) mod q = γ Như vậy verk” (x,(γ ,δ)) = đúng Ví dụ : Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 25 Giả sử p = 124540019 , q = 17389 Suy ra (p-1)/q = 7162, h = 110217528 Và Tính α = h7162 mod 124540019 = 10083255 ≠ 1, chọn a = 12496 Tính β = α12496 mod 124540019 = 119946256. Vậy khóa công khai là: (p = 124540099, q = 17389, α = 10083255, β = 119946256) khóa bí mật là : (a=12496) Ký: x = 2546, k = 9557 tính k-1 mod q = 7631 γ = 100832559557 mod 124540019) mod 17389 = 27039929 mod 1738 9 = 34 δ = (7631){5246+(12496)(34)} mod 17389 = 13049 Kiểm thử: w = δ-1 mod q = 1799 e1= x.w mod q = 5246.1799 mod 17389 = 12716 e2= γ.w mod q = 34.1799 mod 17389 = 8999 (αe1. βe2 modp)modq = (1008325512716.1199462658999mod124540019)mod 17389 = 27039929 mod 17389 = 34 = γ Như vậy verk” ( )),(, δγx = Đúng 2.2. Chữ ký không thể chối bỏ Trong các sơ đồ chữ ký điện tử ta đã trình bày ở trên, việc kiểm thử tính đúng đắn của chữ ký là do người nhận tiến hành. Như vậy, cả văn bản cùng chữ ký có thể được sao chép và phát tán cho nhiều người mà không được phép của người gửi. Để tránh khả năng đó, người ta đưa ra sơ đồ chữ ký không thể chối bỏ được với một yêu cầu là chữ ký không thể được kiểm thử nếu không có sự hợp tác của người ký. Sự hợp tác đó được thể hiện qua giao thức kiểm thử ( giao thức xác nhận ). Khi chữ ký đòi hỏi được xác nhận bằng một giao thức kiểm thử thì một vấn đề nảy sinh là làm sao có thể ngăn cản người ký chối bỏ một chữ ký mà anh ta đã ký? Để đáp ứng yêu cầu đó, cần có thêm một giao thức chối bỏ, thông qua giao thức này, người ký có thể chứng minh một chữ ký không phải là chữ ký của mình. Nếu anh ta từ chối không tham gia giao thức đó thì có bằng chứng là anh ta không chứng minh được chữ ký đó là giả mạo, tức là anh ta không chối bỏ được chữ ký của mình. Một sơ đồ chữ ký không thể chối bỏ có 3 phần: ™ Một thuật toán ký ™ Một giao thức kiểm thử ( giao thức xác nhận ) ™ Một giao thức chối bỏ Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 26 2.3. Chứng minh không tiết lộ thông tin Phép chứng minh không tiết lộ thông tin đã được mô hình hóa bởi Quisquater and Guillou trong ví dụ về “ Hang động của Ali Baba”. Ví dụ này được giải thích như sau ™ Từ bây giờ chúng ta sẽ coi Peggy là Prover (người chứng minh), còn Victor là Verifier (người kiểm thử) như nhiều tài liệu Mật mã. Peggy(P) muốn chứng minh với Victor(V) rằng cô ta biết câu thần chú có thể mở được cánh cửa bí mật tại các điểm R-S, nhưng cô ta không muốn tiết lộ bí mật đó với Victor. ™ Quá trình đến nơi đó diễn ra như sau: Victor đi tới P và đợi đến khi Peggy đi khỏi R hoặc S. Sau đó Victor di chuyển đến Q và gọi Peggy ra ngoài từ bên trái hoặc bên phải của đường hầm( kỹ thuật cut and choose). Nếu Peggy không biết câu thần chú, cô ta chỉ có 50% khả năng ra ngoài từ bên đúng. Giao thức có thể được lặp lại nhiều lần đến khi Victor tin rằng Peggy đã biết câu thần chú. Nếu giao thức được lặp lại k lần, xác suất lừa gạt của Peggy là 2k. Và nó không có nghĩa là giao thức đã được lặp bao nhiêu lần. Victor vẫn không biết được bí mật. Ý nghĩa chính ẩn trong nguyên nhân là: Peggy muốn chứng minh một sự thật hiển nhiên F1 nhưng cô ta không muốn tiết lộ sự chứng minh này. Vì thế cô ta đi tìm những sự thật F2 khác, mà có thể tiết lộ công khai, như là F2 là ĐÚNG NẾU F1 ĐÚNG( điều kiện cần thiết). Vì thế cô ta “ Thay thế ” phép chứng minh của F1 chỉ bằng chứng minh F2. Trong ví dụ, F1 là câu thần chú bí mật,và F2 là khả năng xuất hiện từ mọi phía của đường hầm. Nếu Victor đồng rằng F2 không thể đúng nếu F1 không đúng, sau đó giao thức có thể tiến hành. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 27 2.4. Vấn đề ký số trên đại diện văn bản Khái niệm : Việc sử dụng các hệ mật mã và các sơ đồ chữ ký số thường là mã hóa và ký số trên từng bit của thông tin, thời gian để mã hóa và ký sẽ tỷ lệ thuận với dung lượng của thông tin. Thêm vào đó có thể xảy ra trường hợp với nhiều bức thông điệp đầu vào khác nhau, sử dụng hệ mật mã, sơ đồ ký số giống nhau ( có thể khác nhau ) thì cho ra kết quả bản mã, bản ký số giống nhau. Điều này sẽ dẫn đến một số rắc rối về sau cho việc xác thực thông tin. Với các sơ đồ ký số, chỉ cho phép ký các thông điệp ( thông tin ) có kích thước nhỏ và sau khi ký, bản ký số có kích thước gấp đôi bản thông điệp gốc ( trong trường hợp của sơ đồ ký số DSS ). Trong khi đó, trên thực tế, ta cần phải ký các thông điệp có kích thước lớn hơn nhiều, chẳng hạn vài chục Megebyte, hơn nữa dữ liệu truyền qua mạng không chỉ là bản thông điệp gốc, mà còn bao gồm cả bản ký số (có dung lượng gấp đôi bản thông điệp gốc ), để đáp ứng việc xác thực sau khi thông điệp đến người nhận. Một cách đơn giản để giải bài toán (với thông điệp vài chục Megabyte ) này là chặt thông điệp thành nhiều đoạn 160 bit sau đó ký lên các đoạn đó độc lập nhau. Nhưng biện pháp này có một số vấn đề khi tạo ra chữ ký số : ™ Thứ nhất : Với một thông điệp có kích thước a thì sau khi ký kích thước của chữ ký sẽ là 2a (trong trường hợp chữ ký số DSS) ™ Thứ hai : Với các chữ ký “an toàn ” thì tốc độ chậm vì chúng dùng nhiều phép tính số học phức tạp như số mũ modulo ™ Thứ ba : Vấn đề nghiêm trọng hơn đó là kết quả sau khi ký, nội dung của thông điệp có thể bị xáo trộn các đoạn với nhau, hoặc một số đoạn trong chúng có thể bị mất mát, trong khi người nhận cần xác minh lại thông điệp. Ta cần phải bảo vệ tính toàn vẹn của thông điệp. Giải pháp cho các vấn đề trên là dùng hàm băm để trợ giúp cho việc ký số. Các thuật toán băm với đầu vào là các bức thông điệp có dung lượng tùy ý, các bức thông điệp có thể là dạng văn bản, âm thanh, hình ảnh, … và với các giải thuật toán băm : MD2, MD4, MD5, SHA do các bản băm có kích thước cố định: 128 bit với dòng MD, 160 bit với dòng SHA. Như vậy, bức thông điệp kích thước tùy ý sau khi băm sẽ được thu gọn thành các văn bản – được gọi là văn bản đại diện - có kích thước cố định (128 bit hoặc 160 bit) . Với mỗi thông điệp đầu vào chỉ có thể tính ra được một văn bản đại diện duy nhất. Giá trị băm được coi là đặc thù của thông điệp, giống như dấu vân tay của mỗi người. Hai thông điệp khác nhau chắc chắn có hai văn bản đại diện khác nhau. Khi đã có văn bản đại diện duy nhất cho bức thông điệp, áp dụng các sơ đồ chữ ký số ký trên văn bản đại diện đó. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 28 2.4.1. Sơ lược về hàm băm (Hash Function) 2.4.1.1. Giới thiệu Theo các sơ đồ chữ ký ở trên thì chữ ký của thông điệp cũng có độ dài bằng độ dài của thông điệp, đó là một điều bất tiện. Ta mong muốn như trong trường hợp chữ ký viết tay, chữ ký có độ dài ngắn và hạn chế cho dù văn bản có độ dài bằng bao nhiêu. Vì chữ ký số được ký cho từng bit của thông điệp, nếu muốn chữ ký có độ dài hạn chế trên thông điệp có độ dài tuỳ ý thì ta phải tìm cách rút gọn độ dài thông điệp. Nhưng bản thân thông điệp không thể rút ngắn được, nên chỉ còn cách là tìm cho mỗi thông điệp một thông điệp thu gọn có độ dài hạn chế và thay việc ký trên thông điệp, ta ký trên thông điệp thu gọn. Do vậy các hàm băm đóng vai trò cơ bản trong mã khóa công khai. Hàm băm sẽ tạo ra một đầu ra từ bản tin đầu vào. Đầu ra này được định nghĩa là một mã băm. 2.4.1.2. Định nghĩa hàm Hash Hàm Hash là một hàm tính toán có hiệu quả khi ánh xạ các dòng nhị phân có độ dài tuỳ ý thành các dòng nhị phân có độ dài cố định nào đó. Hàm Hash yếu: Hàm Hash được gọi là yếu nếu cho một thông điệp x thì về mặt tính toán không tìm ra được thông điệp 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 điệp x và x’ sao cho: x’ ≠ x và h(x’) = h(x) Chọn giá trị x ngẫu nhiên, x ∈ X Tính z = h(x) Tính x1 = A(z) Nếu x1 ≠ x thì x1 và x va chạm dưới h( thành công) Ngược lại là thất bại Hàm Hash có tính chất một chiều: Hàm Hash có tính chất một chiều nếu cho trước thông điệp rút gọn z thì về mặt tính toán không tìm ra được thông điệp x sao cho : h(x) = z. Hàm Hash yếu làm cho chữ ký số trở nên tin cậy giống như việc ký trên toàn thông điệp. 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 điệp có nội dung khác nhau, sau đó thu nhận chữ ký hợp pháp cho một bản thông điệp dễ được xác nhận rồi lấy nó giả mạo làm chữ ký của thông điệp thứ 2. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 29 2.4.1.3. Tính chất của hàm băm ™ Hàm băm h phải thỏa mãn tính chất không va chạm yếu nghĩa là : Khi cho trước một thông điệp x không thể tiến hành về mặt tính toán để tìm ra bức điện x’ ≠ x mà h(x’) = h(x). ™ Hàm băm h không va chạm mạnh nghĩa là không có khả năng tính toán dễ tìm ra hai thông điệp x và x’ mà x’ ≠ x và h(x’) = h(x). ™ Hàm băm h là hàm một chiều nghĩa là khi cho trước một bản tóm lược thông điệp z thì không thể thực hiện về mặt tính toán để tìm ra thông điệp ban đầu x sao cho h(x)= z. Các hàm băm phổ biến là các hàm băm dòng MD : MD2, MD4, MD5 do Rivest đưa ra có kết quả đầu ra là 128 bit. Chuẩn hàm băm an toàn SHA được công bố trong hồ sơ liên bang năm 1992 và được chấp nhận làm tiêu chuẩn vào năm 1993 do viện tiêu chuẩn và công nghệ quốc gia (NIST), kết quả đầu ra có độ dài 160 bit. Dưới đây là thuật toán băm MD5. 2.4.1.4. Thuật toán MD5 Thuật toán MD5 được Ron Rivest đưa ra vào năm 1991. Đầu vào của thuật toán là các khối có độ dài 512 bit và đầu ra là một bản băm đại diện cho văn bản gốc có độ dài 128bit. Các bước tiến hành : Bước 1 : Độn thêm bit Đầu tiên thông điệp được đệm thêm vào để chiều dài của nó là 64 bit. Vi dụ : Nếu thông điệp dài 448 bit thì nó được đệm thêm vào 512 bit để trở thành 960 bit. Số lượng bit được thêm vào nằm trong khoảng từ 1 đến 512 bit. Dãy bit thêm vào bắt đầu bằng số 1 vào theo sau là dãy số 0. Bước 2 : Thêm độ dài Một biểu diễn 64 bit của độ dài của thông điệp (trước khi các bit đệm được thêm vào) được thêm vào để dẫn đến kết quả của bước 1, nếu chiều dài của thông điệp ban đầu lớn hơn 264 thì chỉ có những bit nhỏ hơn 64 mới được sử dụng. Hai bước trên để đáp ứng yêu cầu độ dài của thông điệp là một bội số của 512 bit Bước 3 : Khởi tạo bộ đệm của MD Một bộ đệm 128 bit được khởi tạo để lưu giữ kết quả của hàm băm. Bộ đệm được biểu diễn bởi thanh ghi 32 bit. Các giá trị khởi tạo của 4 thanh ghi là : A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210 Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 30 Bước 4 : Tiến trình thực hiện Thuật toán được thực hiện qua 4 vòng lặp, 4 vòng lặp này có cấu trúc giống nhau nhưng sử dụng các phép toán logic khác nhau. Các phép toán logic được sử dụng bao gồm : AND, XOR, OR và phép modulo 232 Bước 5 : Đầu ra Sau khi tất cả các khối 512 bit được xử lí thì một văn bản đại diện 128 bit được sinh ra. ABCD Quá trình tạo hàm băm của MD5 2.5. Xác thực Trong phạm vi truyền thông qua internet người ta nhận được các dạng tấn công sau đây. ™ Khám phá : Để lộ các nội dung thông báo do không xử lý khóa mật mã thích hợp ™ Phân tích luồng thông tin : Phát hiện luồng thông tin giữa các thành viên. Trong một ứng dụng hướng kết nối, người ta có thể xác định được tần số và khoảng thời gian kết nối. Trong môi trường hướng kết nối hoặc không. Hướng kết nối người ta có thể xác định được số lượng và độ dài của các thông báo giữa các thành viên. Thông điệp Y0 Y1 Yq YL-1 MD 5 MD 5 MD 5 MD 5 L x 512 bits = N x 32 bits K bits Độn thêm vào Chiều dài thông điệp 512 bit 128 bit digest Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 31 ™ Giả mạo : Đưa thêm các thông báo có nguồn gốc giả mạo trên mạng. Thông thường kẻ giả mạo sẽ tạo ra các thông báo và gửi cùng với các thông báo hợp pháp. ™ Sửa đổi nội dung : Thay đổi nội dung của thông báo như chèn thêm, xóa, sửa đổi. ™ Sửa đổi trình tự : Sửa đổi trình tự thông báo giữa các thành viên chẳng hạn như xóa bỏ hay sắp xếp theo trình tự mới. ™ Sửa đổi thời gian : Làm trễ hoặc chuyển tiếp nhiều lần các thông báo. ™ Chối bỏ : Người nhận chối bỏ những thông báo gửi đến hoặc người gửi chối bỏ thông báo gửi đi. Xác thực : Là một thủ tục nhằm kiểm tra các thông báo nhận được xem chúng có đến từ một người gửi hợp lệ và có bị sửa đổi hay không. Xác thực cũng có thể kiểm tra trình tự và tính đúng lúc. Chữ ký số là một kỹ thuật xác thực. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 32 Chương III CHỮ KÝ NHÓM 3.1. Khái niệm về chữ ký nhóm( Groups Signature ) Trong xu hướng phát triển cuả thế giới và Việt Nam hiện nay, việc giao dịch giữa người với người thông qua mạng đã trở thành một việc không thể thiếu. Hai người ở cách xa nhau hàng vạn cây số nhưng vẫn có thể thực hiện việc ký kết các hợp đồng thương mại với nhau thông qua mạng. Để việc ký kết các hợp đồng đó có cơ sở pháp lý, các nhà khoa học đã phát minh ra chữ ký điện tử. Đó là một phát minh vĩ đại của loài người trong kỉ nguyên công nghệ thông tin. Tuy nhiên, việc giao dịch không chỉ dừng lại ở mức độ giữa hai người với nhau, mà đòi hỏi việc giao dịch đó có thể là giao dịch giữa các nhóm người, các tổ chức khác nhau trên thế giới và được thực hiện qua mạng. Việc xác thực thông tin và toàn vẹn thông tin lúc này là xác thực và toàn vẹn thông tin của một nhóm người, một tổ chức. Chữ ký nhóm đã được đề xuất nhằm đáp ứng được yêu cầu này của xã hội. Chữ ký nhóm là chữ ký điện tử đại diện cho một nhóm người, một tổ chức Các thành viên của một nhóm người được phép ký trên thông điệp với tư cách là người đại diện cho nhóm. Chữ ký nhóm được David Chaum và Van Heyst giới thiệu lần đầu tiên vào năm 1991. Kể từ đó đến nay đã có nhiều nhà khoa học nghiên cứu và đưa ra một số sơ đồ chữ ký nhóm khác như sơ đồ chữ ký nhóm của Chen và Pedersen năm 1994, sơ đồ chữ ký nhóm của Camenisch và Stadler năm 1997. 3.2. Những đặc điểm của chữ ký nhóm ™ Chỉ có thành viên trong nhóm mới có thể ký tên vào bản thông báo đó ™ Người nhận thông điệp có thể kiểm tra xem chữ ký đó có đúng là của nhóm đó hay không, nhưng người nhận không thể biết được người nào trong nhóm đã ký vào thông điệp đó. ™ Trong trường hợp cần thiết chữ ký có thể được “mở” (có hoặc là không có sự giúp đỡ của thành viên trong nhóm) để xác định người nào đã ký vào thông điệp đó 3.2.1. Ta có hệ chữ ký nhóm Undeniable Signature Đây là chữ ký mà thuật toán kiểm định đòi hỏi phải có sự tham gia của người ký. Thực chất đây là chữ ký có tính chất không thể chuyển giao được (untransferable): Chỉ có ý nghĩa đối với người nhận là có người trao đổi làm ăn với người ký, khi chuyển nó cho một người khác thì không có tác dụng nữa (không thể kiểm định được chữ ký Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 33 nữa). Các văn bản có chữ ký này không nhằm mục đích đem đi công bố ở nơi khác mà chỉ có tính chất giấy phép. Vì thế nếu sao chép là mất ý nghĩa. Chữ ký này được dùng trong việc bán các sản phẩm phần mềm: Các hãng phần mềm sẽ bán các sản phẩm của mình có chữ ký chứng tỏ tính bản quyền. Việc kiểm định đòi hỏi phải liên lạc với hãng này. Nếu như có việc một người buôn nào đó bán phần mềm sao chép thì lúc người mua đòi kiểm định sẽ bị lộ ngay vì không thực hiện được. MultiSignature ( Đồng ký ) Ở đây, chữ ký không phải của một người mà của một nhóm người. Muốn tạo được chữ ký, tất cả những người này cùng phải tham gia vào protocol. Tuy nhiên chữ ký có thể được kiểm định bởi bất kỳ ai. Đây là trường hợp dành cho thực tế của việc đưa ra những quyết định do nhiều người. Proxy Signature (chữ ký ủy nhiệm) Hệ chữ ký này dành cho các trường hợp mà người chủ chữ ký vì một lí do nào đó mà không thể ký được. Vì vậy chữ ký ủy nhiệm được tạo ra để người chủ có thể ủy nhiệm cho một người nào đó ký thay. 3.2.2. Một sơ đồ chữ ký nhóm gồm thành phần cơ bản ™ Người quản lý nhóm ™ Các thành viên trong nhóm ™ Người không thuộc nhóm 3.2.3. Một sơ đồ chữ ký nhóm thường bao gồm 5 thủ tục ™ KeyGen: Là thuật toán sinh khóa công khai của nhóm, khóa bí mật của người quản lý nhóm : KeyGen() → (pk,gmsk) trong đó pk là khóa công khai của nhóm (dùng để xác minh chữ ký của nhóm), gmsk là khóa bí mật của nhóm. Nếu số người trong nhóm là cố định thì KeyGen()→ (pk,gmsk,sk i ) trong đó sk i là khóa bí mật của thành viên thứ i trong nhóm ™ Join : Cho phép một người không phải là thành viên nhóm gia nhập nhóm. Khi gia nhập nhóm, thành viên i sẽ nhận được khóa bí mật của mình là sk i , người quản lý nhóm sẽ lưu thông tin của thành viên mới này ™ Sig : Khi thành viên i muốn ký thông điệp m đại diện cho nhóm, anh ta sẽ sử dụng thủ tục Sig: Sig(m, sk i )→. Chữ ký trên thông điệp m là δ. ™ Verify : Khi muốn kiểm tra chữ ký δ có phải là chữ ký đại diện cho nhóm trên thông điệp m sử dụng thủ tục Verify(m, δ,pk) = ⎢⎣ ⎡ False True Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 34 ™ Open : Với mỗi chữ ký trên thông điệp m, người quản lý nhóm có thể xác định được thành viên nào đã ký vào thông điệp bằng việc sử dụng thủ tục Open(gmsk,m, δ), đầu ra của thủ tục là thông tin về thành viên đã ký. 3.2.4. Hiệu quả của chữ ký nhóm Khi đánh giá hiệu quả của một sơ đồ chữ ký nhóm ta cần quan tâm đến các thông số sau: ™ Độ lớn của khóa công khai nhóm γ (số bit) ™ Độ lớn của chữ ký trên một thông điệp (số bit) ™ Hiệu quả của các thủ tục Setup, Join, Sign, Verify, Open Tính ưu việt của chữ ký nhóm chính là khả năng cho phép những nhóm người, những tổ chức giao tiếp với nhau, mà trong đó việc xác thực các thông tin gửi cho nhau thông qua các khóa công khai của mỗi nhóm. Nhờ đó những thành viên của nhóm có thể ký nặc danh đại diện cho nhóm của mình mà không thể để lộ thông tin cá nhân của mình, và chỉ có người quản trị mới có thể xác định được người ký. 3.2.5. Việc đảm bảo an ninh đối với chữ ký nhóm. ™ Không thể giả mạo : Chỉ có các thành viên trong nhóm mới có thể đại diện cho nhóm ký trên thông điệp của nhóm. ™ Người ký nặc danh có thể tính toán được : Bất kỳ ai cũng có thể xác thực chữ ký một cách dễ dàng nhưng không thể biết được ai là người ký ( Trừ người quản lí nhóm ). ™ Không thể chối bỏ : Một thành viên ký trên một thông điệp thì không thể chối bỏ chữ ký đó được. Người quản lý nhóm có thể xác định được ai đã ký vào thông điệp đó. ™ Không thể phân tích quan hệ : Việc phân tích xem hai chữ ký của một thành viên trong nhóm khác nhau như thế nào là khó đối với các thành viên của nhóm trừ người quản lí nhóm. ™ Ngăn chặn framing Attacks : Khi một số thành viên liên kết với nhau cũng không thể giả mạo chữ ký của thành viêc khác trong nhóm. ™ Ngăn chặn sự liên minh : Khi một số thành viên liên kết với nhau cũng không thể tạo ra một chữ ký hợp lệ mà không xác định được người ký. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 35 3.3. Các sơ đồ chữ ký nhóm của David Chaum và Van Heyst 3.3.1. Sơ đồ chữ ký nhóm thứ nhất. Z ( là người quản lý nhóm hoặc là người tin cậy được ủy nhiệm ) chọn một hệ thống khóa công khai và đưa cho mỗi thành viên một danh sách các khóa bí mật (các danh sách này là khác nhau) và công bố một danh sách đầy đủ các khóa công khai tương ứng ( theo thứ tự ngẫu nhiên ) trong một Trusted Public Directory – TPD Mỗi thành viên có thể ký một thông điệp bằng một khóa bí mật trong danh sách của anh ta, và người nhận có thể kiểm tra chữ ký bằng một khóa công khai tương ứng từ danh sách khóa công khai. Mỗi khóa chỉ được sử dụng một lần, nói cách khác các chữ ký đã được tạo bằng khóa này được liên kết. Z biết tất cả các danh sách khóa bí mật, vì thế trong trường hợp cần thiết, Z có thể biết được ai đã tạo ra chữ ký đó. Để làm được điều này Z phải “mở” chữ ký. Nếu mỗi người có cùng một số lượng các khóa bí mật, thì chiều dài của khóa công khai của nhóm là tuyến tính với số thành viên, nhưng số thông điệp của mỗi thành viên ký là không đổi. Một vấn đề đối với sơ đồ này là Z biết tất cả các khóa bí mật của các thành viên và có thể giả mạo chữ ký. Điều này có thể được giải quyết bằng việc sử dụng các khóa công khai mù. Lấy g là phần tử sinh của nhóm nhân Z *p với p là một số nguyên tố. Thành viên thứ I lấy khóa bí mật của mình là si và tính g is mod p rồi gửi cho Z, Z có một danh sách các khóa công khai khác nhau này cùng với tên của các thành viên. Mỗi tuần Z đưa cho thành viên I một số ngẫu nhiên ri ∈ { }1...,,2,1 −p và công bố danh sách tất cả các khóa công khai mù là ( ) ii rsg . Trong suốt tuần này thành viên I sẽ sử dụng siri mod (p-1) làm khóa bí mật. Ưu điểm của việc cải biên này là Z không thể giả mạo chữ ký, và mỗi thành viên sẽ có một “ khóa bí mật thực sự ”. Nếu ri chẳng may bị lộ thì vẫn không có một thông tin nào về khóa bí mật si bị lộ. Trong một cải biên khác, không cần phải có người ủy quyền tin cậy, mỗi người dùng gửi một (hoặc nhiều hơn ) các khóa công khai tới một danh sách công khai sẽ là khóa công khai của nhóm. Nhưng chỉ những thành viên của nhóm mới có thể gửi các khóa công khai vào danh sách này. 3.3.2. Sơ đồ chữ ký nhóm thứ hai Z chọn hai số nguyên tố lớn p, q khác nhau và một hàm một chiều và tính N=p*q. Z đưa cho thành viên thứ I một khóa bí mật si ,là một số nguyên tố lớn ngẫu nhiên thuộc tập hợp [ ] [ ]{ }12,, −= NN Kφ , và tính v = ∏ is , và công bố N, v và f. Nếu thành viên I muốn ký thông điệp m, chữ ký của anh ta sẽ là ( )( ) ismf mod N. Z phải chứng minh cho người nhận rằng si là ước của v, và si ∈ φ mà không để lộ bất kì thông tin nào về si. Trong trường hợp có xảy ra tranh cãi sau đó, người nhận có Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 36 thể sử dụng giao thức xác nhận hoặc giao thức chống chối bỏ yêu cầu bên gửi phải chứng minh rằng chữ ký không phải của bên gửi. 3.3.2.1. Giao thức xác nhận Người ký P sẽ phải chứng minh rằng S là chữ ký của anh ta trên thông điệp m với V mà không để lộ thông tin nào về khóa bí mật s của anh ta, việc này sẽ được giải quyết bởi giao thức 1, chúng ta sẽ phải tính toán các blob an toàn B . Ta coi bản thu gọn của thông điệp là m. Giao thức xác nhận 1 Nếu giao thức này được lặp lại k lần, V sẽ tin rằng s ∈ Ω; nhưng V sẽ không nhận được gì hơn ngoài sự thật là s ∈ Ω; Giao thức 1 1. P chọn r ∈ (0, …, β). Tính các blob trên z1 ≡ x r (mod N) và z2 ≡ x β−r (mod N), và gửi không theo thứ tự { })B(z),B(z 21 cho V . 2. V chọn ngẫu nhiên b ∈ (0, 1) và gửi cho P 3. P gửi lại cho V trong trường hợp b = 0:r và mở các blob b = 1: z~ là (c + r) hoặc (c + r - β) và tương ứng z1 hoặc z2 (gọi là z~ ) 4. V kiểm tra trong trường hợp : b = 0 : kiểm tra r ∈ ( 0, …, β) và các blob của xr và xr-β theo thứ tự nào đó b = 1 : kiểm tra r~ ∈ Ω và một trong các blob chứa z~ và z~ thỏa mãn rm ~ ≡ z~ S (mod N). Nếu P có thể trả lời đúng cả hai yêu cầu khi V gửi b thì chữ ký S trên thông điệp m đúng là của P . Còn nếu một trong hai câu có kết quả sai hoặc cả hai câu đều sai thì chữ ký S trên thông điệp m không phải là chữ ký của P. Blob B có thể được tính bằng cách sau: Z chọn các phần tử sinh gp và hq của *pZ và *qZ và tính g ≡ ⎩⎨ ⎧ ql pg p mod mod và h ≡ ⎩⎨ ⎧ qh pl q mod mod sử dụng CRT Để tính B(y) thì P chọn r1, r2 ∈ (1, …, N) và tính B(y) = y 21 rr hg mod N Khóa bí mật của P : s Công khai : N, m, S, Ω; m, s ∈ Z *N , Ω = [ ] [ ]{ }12,, −NN K ⊂ N Chứng minh với V : m s ≡ S (mod N) và s ∈ Ω Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 37 Trong giao thức này, chúng ta tạo một giao thức xác nhận, vì P muốn chứng minh cho người nhận V rằng P đưa cho một V chữ ký có giá trị S. Trường hợp này được giải quyết như sau : Giao thức xác nhận 2 Giao thức 2 1. Chứng minh tồn tại s sao cho ms ≡ S (mod N) và s ∈ Ω bằng giao thức 1, thực hiện k lần. 2. Chứng minh rằng s|v như sau: Giao thức 2 3.3.2.2. Giao thức chối bỏ Nếu P muốn chứng minh cho V rằng S không phải là chứ ký của anh ta trên thông điệp m, trường hợp này sẽ được giải quyết như sau: Giao thức chói bỏ Khóa bí mật của P : s Công khai : N, m, S, Ω; m, s ∈ Z *N , Ω = [ ] [ ]{ }12,, −NN K ⊂ N Chứng minh với V : m s ≡ S (mod N) và s ∈ Ω và s|v (s là ước của v) P V a ≡ Sr Chọn r ∈ (1,…, N) b ≡ av/s B(b) Kiểm tra a r Mở blob Kiểm tra blob và b ≡ mvr Khóa bí mật của P : s Công khai : N, m, S, Ω; m, s ∈ Z *N Chứng minh với V : m s ≡ S (mod N) và s ∈ Ω và s|v (s là ước của v) Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 38 Z công bố ( hg , ) được sinh trong nhóm Z *N (cách tính hg , như sau: chọn các số nguyên a1, a2, b1, b2 thỏa mãn gcd(a1, b1, p-1) = gcd (a2, b2, q-1) = 1 và công khai 2121 ~,~ bbaa hghhgg ≡≡ với g, h là các phần tử sinh của Zp* và Z*q), cùng đó là một thư mục công khai tin cậy chứa ( tên thành viên, ss hg ~,~ ). Lấy l là một hằng số rất nhỏ để việc tìm kiếm toàn diện trên (0, …, 1) là khả thi. Chú ý rằng nếu S ≡ ms, thì p không thể tính a từ ( )as Sm / , vì khi đó ( )as Sm / = 1. Khi đó anh ta sẽ phải đoán a. Giao thức 3 Do chữ ký được tạo ra là chữ ký không thể chối bỏ, ta có thể sử dụng giao thức chối bỏ của sơ đồ chữ ký không thể chối bỏ do chính tác giả David Chaum sáng tác để thưc hiện việc chứng minh chữ ký S không phải là chữ ký của P trên thông điệp m với V . Z công bố g~ và isg~ (mod N), S-1i (mod ϕ(N)) tương ứng từng thành viên. Giao thức 4 sẽ giải quyết vấn đề chối bỏ chữ ký như sau : Giao thức 4 Bước 1 : V chọn ngẫu nhiên 2 số nguyên x1, x2 ∈ Ф, tính ( ) 21 ~ xsx gSc= mod N, sau đó gửi cho P Bước 2 : P tính ( ) 1−= scd mod N, gửi d cho V Bước 3 : V thử điều kiện d ≠ 21 ~ xx gm mod N. Nếu đúng thì tiếp tục bước 4. Nếu sai thì chữ ký đúng là của P P V 2~~ ra hgm ≡ Sr Chọn r1, r2 ∈ (1,…, N) và a ∈ (0, …, 1) ( ) ( ) 21 ~~ rsrsa hgS Tính a từ ( )as Sm / B(b) Bằng cách kiểm tra Toàn bộ các số r1, r2 Mở blob Kiểm tra blob Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 39 Bước 4 : V chọn ngẫu nhiên 2 số nguyên tố x’1, x’2 ∈ Ф tính ( ) 2'1' ~' xsx gSc = mod N, sau đó gửi c’ cho P . Bước 5 : P tính ( ) 1'' −= scd mod N, sau đó gửi d’ cho V Bước 6 : V thử điều kiện d’ ≠ 2'1' ~ xx gm mod N. Nếu đúng thì tiếp tục bước 7. Nếu sai thì chữ ký đúng là của P . Bước 7 : V kiểm tra ( ) ( ) 1'2'12 ~~ ' xxxx gdgd −− ≡ mod N ? Nếu đồng dư thức đùng thì kết luận chữ ký không phải là của P. Ví dụ : Một ví dụ về sơ đồ chữ ký nhóm dựa trên hệ mật mã RSA ™ Thành lập một nhóm có 5 thành viên, quá trình cài đặt nhóm do người quản lý nhóm thực hiện như sau : Z chọn p = 101, q = 113, N = pq = 11413, ϕ(N) = (p-1)(q-1) = 11200, Z chọn khóa bí mật của Z là Sz = 149, gp = 3, hq = 2 là các phần tử sinh của Z*p và Z *q. Chọn a1 = 3, a2 = 7, b1 = 11, b2 = 13. Tính 21~ aa hgg = mod N = 3456 và 21~ bb hgh = mod N = 2448 Các khóa bí mật của các thành viên như sau : s1= 107,s2 = 113, s3 = 123, s4 = 129, s5 = 137 Khóa công khai của các thành viên ( là nghịch đảo của khóa bí mật của các thành viên trong trường mod ϕ(N)) được gửi lên TPD như sau (không theo thư tự ): 5443, 2577, 3187, 8769, 10873. Các khóa công khai này sẽ được người nhận thông điệp dùng để xác minh có đúng hay không. Khóa công khai của nhóm là N = 11413 v = ∏ iz ss =3916191121461 ™ Ký văn bản : ký văn bản m = 1234 thì Chữ ký của từng thành viên lần lượt là : 278, 6093, 6541, 6528, 8331 ™ Xác nhận chữ ký ( sử dụng giao thức 1) Thành viên 1 muốn xác nhận chữ ký S = 278 đúng là của anh ta ( gọi là P ) trên văn bản m = 1234 với người xác nhận ( gọi là V ) thì anh ta thực hiện giao thức xác nhận ( giao thức 1) Bước 1 : P chọn β = 57, chọn r = 23. Tính z1 = 123423 mod 11413 = 4016, z2 = 123423-57 = mod 11413 = (1234-1)34 mod 11413 = 951734 mod 11413 = 2429. Tính các blob : g = 1922, h = 4748, chọn r1 = 5,r2 = 7. B(z1) = 4016.19225.47487 mod 11413 = 8712 B(z2) = 2429.19225.47487 mod 11413 = 1518 Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 40 Bước 2 : V chọn b = 0 hoặc b = 1 rồi gửi cho P Bước 3 : P gửi cho V Nếu b = 0 thì r = 23, β = 57, mở các blob g = 1922, h = 4748, r1 = 5,r2 = 7, z1 = 4016, z2 = 2429 Nếu b = 1 thì r = 107 + 23 = 130, z = 4016 Bước 4 : V xác định Nếu b = 0 thì r ∈ (0, …, β) và kiểm tra z1 = 4016, z2 = 3418 sau đó kiểm tra B(4016) = 8712 và B(3418) = 5505 theo thứ tự nào đó mà P đã gửi ở bước 1. Nếu kiểm tra thỏa mãn thì chữ ký là đúng . Nếu b = 1 thì kiểm tra 1234130 ≡ 4016.278 (mod 11413) ↔9387 ≡ 9387. do đó chữ ký là đúng. ™ Chối bỏ chữ ký ( sử dụng giao thức 4). Giả sử thành viên thứ 1 ký thông điệp m = 1234, chữ ký S = 278, thành viên thứ 3 muốn chứng minh rằng đó không phải là chữ ký của anh ta. Khi đó người quản lý nhóm công bố : N = 11413, g~ = 1299, sg~ = 4528 (mod N) (công khai), s-1 = 3187 (mod ϕ(N)) ( cho thành viên cần phải chứng minh biết P). Bước 1 : V chọn x1 = 3, x2 = 5. Tính c = 2783.45285 (mod N) = 6595. Gửi c cho P Bước 2 : P tính d = 65953187 (mod N) = 5172. Rồi gửi cho V Bước 3 : V thử 5172 ≡ 12343 12995 (mod 11413)? →5172 ≡ 4285 Bước 4 : V tính c’ = 2784.45286 (mod N) = 1236 rồi gửi c’ cho P Bước 5 : P tính d’ = 12363187 (mod N) = 6038 rồi gửi cho V Bước 6 : V thử 6038 ≡ 1234412996(mod 11413)? →6038 ≡ 694 Bước 7 : V kiểm tra ( ) ( )( ) ( )⎪⎩ ⎪⎨ ⎧ = = − − 2682mod1299.5172 2682mod1299.6038 45 36 N N do đó chữ ký không phải là của P ™ Một vài nhận xét đối với sơ đồ chữ ký nhóm thứ hai Nếu tất cả thành viên của nhóm có âm mưu loại một người thì khóa bí mật của người này sẽ bị lộ. Việc này có thể dễ dàng được giải quyết khi Z là một thành viên của nhóm, khi đó Z sẽ tính v = ∏ iz ss , trong đó sz là một khóa bí mật mà chỉ Z mới biết. Độ dài của khóa công khai v tuyến tính với số thành viên của nhóm, do đó việc tăng một số lũy thừa của v sẽ là một lần tuyến tính số thành viên của nhóm. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 41 3.3.3. Sơ đồ chữ ký nhóm thứ ba Chúng ta giả sử rằng có một thư mục công khai tin cậy trong đó các modulo RSA của mỗi thành viên được liệt kê ( số mũ RSA công khai không cần trong sơ đồ này) Khóa bí mật của thành viên thứ I sẽ là thừa số của modulo RSA của anht a Ni= piqi. trong suốt quá trình cài đặt, Z chọn một số modulo RSA N độc lập với tất cả các Ni của các thành viên. Lấy M là một số nguyên công khai sao cho pi∈Ф=[ ] [ ]{ }12...,, −MM và qi> 4 M (đối với mọi i). nếu thành viên i muốn ký thông điệp m, anh ta chọn ngẫu nhiên một bộ Γ người ( bao gồm cả anh ta ), chữ ký của anh ta sẽ là : ( )( ) ipmf,Γ mod N Và anh ta sẽ phải đưa ra một chứng cớ không tiết lộ thông tin rằng sử dụng thừa số pi ∈ Ф và pi là một ước số của modulo RSA của các người trong Γ . Điều này có thể được giải quyết bằng Giao thức 2 ( với Ω = Ф). Nếu một thành viên muốn chối bỏ một chữ ký, anh ta có thể sử dụng Giao thức 3. 3.3.3.1. Vấn đề “ mở ” chữ ký Trong trường hợp cần thiết, người quản lý nhóm có thể xác định một chữ ký là do thành viên nào trong nhóm ký bằng cách thực hiện giao thức chối bỏ với từng thành viên trong nhóm. Bởi vì chữ ký, mà mỗi thành viên ký là một chữ ký không thể chối bỏ, do đó nếu sử dụng giao thức chối bỏ ( Giao thức 3) thì một thành viên sẽ không thể phủ nhận chữ ký mà mình đã ký. Và khi đó người quản lý nhóm sẽ biết được chữ ký đó là của ai. 3.3.3.2. Nhận xét Các sơ đồ chữ ký nhóm của D.Chaum đều dựa trên hệ mã RSA và việc tính logarit rời rạc đối với một số nguyên tố lớn là khó. Các thông tin về người ký là an toàn, không ai trong nhóm có thể biết được ( tất nhiên là trừ người đã ký). Trong các sơ đồ thì số người trong nhóm là cố định, riêng trong sơ đồ thứ ba, khi một người muốn ký một văn bản mà không muốn lộ tên anh ta thì đồng thời anh ta tạo một nhóm người (các khóa công khai lấy từ thư mục công khai tin cậy) và anh ta sẽ chứng minh rằng anh ta thuộc nhóm người này. Chữ ký được tạo ra là chữ ký không thể chối bỏ. Độ dài của khóa công khai tuyến tính với số người trong nhóm. 3.4. Sơ đồ chữ ký nhóm của Jan Camenish và Stadler David Chaum và Van Heyst đã đưa ra các sơ đồ chữ ký nhóm đầu tiên trên thế giới, nhưng trong các sơ đồ của họ thì số thành viên trong nhóm phải là cố định, nhưng thực tế một số nhóm luôn luôn thay đổi thành viên, để khắc phục được nhược điểm Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 42 này, năm 1997 Jan Camenish và Stadler đã đưa ra một sơ đồ chữ ký số nhóm mới mà theo đó số thành viên trong nhóm sẽ có thể thay đổi được. Sơ đồ chữ ký số nhóm do Jan Camenish và Stadler gồm 5 thủ tục: ™ Setup: Sinh khóa công khai của nhóm và khóa bí mật của người quản lý nhóm ™ Join: Thủ tục tương tác giữa người quản lý nhóm và một thành viên mới của nhóm để cung cấp cho thành viên này khóa bí mật và chứng nhận thành viên. ™ Sign: Thủ tục ký một thông điệp của một thành viên trong nhóm. ™ Verify: Thủ tục kiểm tra chữ ký trên một thông điệp xem có đúng là chữ ký của nhóm đó hay không. ™ Open: Là thủ tục để xác định xem chữ ký S trên thông điệp m là của thành viên nào trong nhóm. 3.4.1. Một số khái niệm cần thiết Khái niệm 1 Một chữ ký dựa trên kiến thức về logarit rời rạc kép của y theo g, và a trên thông điệp m với một tham số an toàn l kí hiệu là : ( )[ ]( )mgySKLOGLOG al αα = Là một nhóm ( )lsssc ...,,,, 21 ∈ { } lml Zx1,0 thỏa mãn : ( )ll PPPagymHc ...,,,,,,, 21= Trong đó ( ) [ ] ( ) [ ]⎪⎩ ⎪⎨ ⎧ ≠↔ =↔= 0 0 icy icg P is is a a i Khái niệm 2 Một chữ ký dựa trên kiến thức về logarit rời rạc thành phần gốc thứ e của y theo g trên thông điệp m được ký hiệu: ( )[ ]( )mgySKROOTLOG el αα = Là một nhóm ( )lsssc ...,,,, 21 ∈ { } lml Zx1,0 thỏa mãn : ( )ll PPPagymHc ...,,,,,,, 21= Trong đó ( ) [ ] ( ) [ ]⎪⎩ ⎪⎨ ⎧ ≠↔ =↔= 0 0 icy icg P e i e i s s i Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 43 3.4.2. Sơ đồ chữ ký ™ Setup : Người quản trị nhóm chọn tham số an toàn l rồi làm các bước sau : ¾ Một cặp khóa công khai RSA(n, e) và một khóa bí mật d. Trong đó n có độ dài tối thiểu là 21bit, n = pq, p = P + 1, q = 2Q + 1 p, q, P, Q là các số nguyên tố ¾ Một nhóm Cyclic G = ¾ Một phần tử *nZ∈α ngẫu nhiên. ¾ Một số mũ λ và một hằng số μ >1, μ càng lớn thì hệ thống càng an toàn ™ Join : A muốn tham gia vào nhóm thì phải thực hiện các bước sau: ¾ Lấy một khóa bí mật { }12...,,1,0 −∈ λx ¾ Tính y = ax (mod n) ¾ Tính khóa thành viên z = gy, A sẽ sử dụng khóa bí mật của mình để ký z. ¾ Để có được chứng nhận thành viên của nhóm, A gửi (y, z) cho người quản lý nhóm, anh ta sẽ cấp cho A chứng nhận thành viên : v≡(y+1)d(mod n) ™ Sign : Để ký một thông điệp m, A làm theo các bước sau : ¾ rgg =~ với r ∈ Zn ¾ ( )ry zgz == ~~ ¾ [ ] ( )mgzSKLOGLOGV l ~~1 == α ¾ [ ]( )mggzSKROOTLOGV l ββ ~~~2 == Chữ ký trên thông điệp m gồm s = ( )21,,~,~ VVzg ™ Verify : Để xác thực chữ ký s đúng là chữ ký trên m ta phải làm các bước sau : ¾ Kiểm tra V1 thỏa mãn 1~~~ += αaggz hay không ¾ Kiểm tra V2 là chữ ký dựa trên hàm logarit rời rạc của phần tử gốc thứ e. ™ Open : Với chữ ký s = ( )21,,~,~ VVzg trên thông điệp m, người quản lý nhóm có thể xác định người ký bằng cách kiểm tra xem pygz ~~ = với mọi thành viên P của nhóm với yp = logg zp và zp là khóa bí mật của thành viên P. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 44 Chương IV ỨNG DỤNG CHỮ KÝ NHÓM 4.1. Tìm hiểu về giao dịch điện tử Giao dịch điện tử là giao dịch được thực hiện thông qua các phương tiện điện tử và cũng có giá trị pháp lý như nó được ghi chép, hoặc mô tả bằng văn bản theo phương pháp truyền thống. Có thể coi văn bản pháp lý đầu tiên ở Việt Nam về giao dịch điện tử là quyết định của Thủ tướng Chính phủ số 44, năm 2002 về chấp nhận chữ ký điện tử trong thanh toán liên ngân hàng. Ngày 28/10/2005, kỳ họp thứ 8 Quốc hội Khóa XI đã thảo luận về Dự thảo Luật Giao dịch điện tử. Tham gia phiên thảo luận, Bộ trưởng Bộ Bưu chính Viễn thông Đỗ Trung Tá đã phát biểu ý kiến về nội dung quan trọng trong Dự thảo Luật Giao dịch điện tử “Chính phủ quy định cụ thể về việc thừa nhận chữ ký điện tử và chứng thư điện tử nước ngoài”. Hiện nay, ngành ngân hàng đang ứng dụng một số giao dịch điện tử như gửi, nhận, cung cấp thông tin qua mạng, xử lý chứng từ kế toán, giao dịch giữa ngân hàng với khách hàng. Giao dịch điện tử gồm các hình thức thông điệp dữ liệu, chữ ký điện tử, chứng thực điện tử, giao kết và thực hiện hợp đồng điện tử... 4.2. Thẻ thanh toán điện tử Trước đây, các hệ thống thanh toán trên thế giới phần lớn do các ngân hàng thương mại (NHTM) tự liên kết với nhau đứng ra thành lập và vận hành, Ngân hàng Trung ương chỉ là nơi quyết toán vốn. Những năm gần đây, khi công nghệ thông tin phát triển nhanh, các trung tâm thanh toán cũ gặp rất nhiều khó khăn trong việc đầu tư mới và nâng cấp kỹ thuật công nghệ, mặt khác, rủi ro trong hoạt động ngân hàng nói chung và trong hệ thống thanh toán nói riêng thực sự đe doạ sự mất an toàn hệ thống là một thách thức đối với các Ngân hàng Trung ương. Do vậy, nhiều Ngân hàng Trung ương đã tự đầu tư xây dựng mới hệ thống thanh toán điện tử liên ngân hàng xử lý các khoản thanh toán giá trị cao hoặc hợp nhất các trung tâm thanh toán thành những trung tâm lớn hơn để quản lý và giám sát. Xuất phát từ đặc điểm, một hệ thống thanh toán hoàn chỉnh phải hội đủ hai yếu tố. Một là, nói đến hệ hệ thống thanh toán là nói đến yếu tố kỹ thuật (nhanh, chậm, chính xác...); Hai là, hệ thống phải quản lý được dòng chu chuyển vốn bằng việc quản lý số dư tài khoản thanh toán, quyết toán, bù trừ. Chữ ký nhóm có rất nhiều ứng dụng trong thực tế như: Bỏ phiếu điện tử, thanh toán điện tử. Hiện nay các loại thẻ thanh toán điện tử, thẻ rút tiền tự động ATM (automated teller machine) đã trở thành phổ biến trên thế giới và cũng đang rất phát triển tại Việt Nam. Tuy nhiên nếu mỗi ngân hàng đều phát hành một loại thẻ riêng thì chi phí bỏ ra Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 45 sẽ rất cao, và người tiêu dùng khi muốn thanh toán hoặc rút tiền sẽ phải tìm đến đúng điểm (pos) cho phép của ngân hàng đó mới có thể thực hiện giao dịch. Điều này sẽ gây cản trở trong việc phát triển các hệ thống thanh toán trực tuyến, rút tiền tự động… Chính vì thế mà việc đòi hỏi có một loại thẻ chung giữa các ngân hàng, và các máy kiểm tra thẻ, máy rút tiền tự động có thể thực hiện giao dịch đối với thẻ của các ngân hàng. Chữ ký nhóm sẽ được ứng dụng trong trường hợp này. Một liên minh ngân hàng (hay một nhóm các ngân hàng) trong đó mỗi ngân hàng là một thành viên trong nhóm đó với người quản lý nhóm là một ngân hàng trung tâm ( phải là ngân hàng có rất uy tín và thường là ngân hàng trung ương ). Ngân hàng trung tâm sẽ tạo ra các khóa bí mật và khóa công khai của nhóm, tạo các khóa bí mật cho các ngân hàng thành viên. Khi đó các ngân hàng sẽ tạo trên thẻ thanh toán do ngân hàng mình phát hành dựa trên khóa bí mật của mình. Khi một người tiêu dùng có thẻ của liên minh ngân hàng đó, anh ta có thể thanh toán, rút tiền,…tại các địa điểm hỗ trợ của liên minh ngân hàng. Các máy kiểm tra thẻ sẽ kiểm tra chữ ký của ngân hàng phát hành trên thẻ đó, xem thẻ có hợp lệ hay không, và sẽ đưa ra quyết định thực hiện giao dịch. Khóa công khai của liên minh ngân hàng sẽ tuyến tính theo số lượng của các ngân hàng thành viên. Bất kì sự liên minh nào trong liên minh ngân hàng (không bao gồm ngân hàng trung tâm) đều không thể biết được khóa bí mật của ngân hàng khác, do đó sẽ không thể làm giả được thẻ của ngân hàng khác. Cùng với sự phát triển của thế giới thương mại điện tử cũng đang rất được quan tâm và phát triển, một số công ty thực hiện bán hàng trực tuyến qua mạng do đó việc áp dụng chữ ký nhóm là rất hữu ích, giảm tiện, kinh tế hơn, thuận tiện cho người sử dụng và rất cần thiết. 4.3.Việc ứng dụng và phát triển công nghệ tại Việt Nam hiện nay Công ty Cổ phần Chuyển mạch Tài chính Quốc gia Việt Nam (Banknetvn) được Thống đốc NHNN (ngân hàng nhà nước) Việt Nam cấp Giấy phép hoạt động ngày 09/07/2004 và khai trương hoạt động vào ngày 09/08/2004. Banknetvn được thành lập trên cơ sở góp vốn của các cổ đông và có số vốn điều lệ là 94,5 tỷ đồng. Hiện nay Banknetvn có 8 thành viên cổ đông sáng lập, bao gồm: Ngân hàng Nông nghiệp và Phát triển nông thôn Việt nam (VBARD), Ngân hàng Đầu tư và Phát triển Việt nam (BIDV), Ngân hàng Công thương Việt nam (ICB), Ngân hàng Sài gòn Thương tín (Sacombank), Ngân hàng Sài gòn Công thương (Saigonbank), Ngân hàng Á Châu (ACB), Ngân hàng Đông Á (EAB) và Công ty Điện toán và truyền số liệu (VDC). Banknetvn hoạt động theo luật doanh nghiệp và các luật chuyên Ngành liên quan. Mục tiêu hoạt động kinh doanh chính là thực hiện kết nối các hệ thống thanh toán thẻ ngân hàng, thẻ thanh toán giữa các ngân hàng được phép phát hành, chấp nhận, thanh Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 46 toán thẻ và các tổ chức khác được phép cung ứng dịch vụ thanh toán; thực hiện thanh toán bù trừ đối với các giao dịch thanh toán thẻ ngân hàng và cung ứng các dịch vụ có liên quan trong lĩnh vực thẻ thanh toán. Tình hình về phát hành thẻ và dịch vụ ATM ở các Ngân hàng thương mại ở Việt Nam Vài năm gần đây, với sự phát triển của công nghệ trên toàn thế giới và bằng những nỗ lực của mình, Việt Nam đã ứng dụng được nhiều công nghệ mới, tiên tiến và đã có những thành quả đáng ghi nhận trong lĩnh vực thẻ thanh toán. Tuy nhiên, việc sử dụng công nghệ mới trong phương thức thanh toán không dùng tiền mặt Việt Nam còn hạn chế, đơn giản với doanh số chưa nhiều. Về lĩnh vực thẻ, các Ngân hàng Việt Nam mới đang phát triển hệ thống thẻ từ, trong khi trên thế giới các Ngân hàng đã và đang chuyển sang hệ thống thẻ thông minh theo chuẩn EMV (Europay, Mastercard và Visa) Những máy giao dịch tự động (ATM) và những chiếc thẻ ATM đầu tiên ở Việt Nam được triển khai trong một dự án do Ngân hàng Nhà nước Việt nam chủ trì từ năm 1996. Vào thời gian đó ATM và thẻ ATM là những thứ rất lạ đối với thị trường Việt Nam. Có thể nói, khi đó những người hiểu biết về ATM và thẻ ATM rất ít ỏi, hơn nữa, những điều kiện cần có để phát triển dịch vụ ATM vào thời gian này cũng chưa có gì. Vietcombank là Ngân hàng thương mại đầu tiên thực hiện việc thử nghiệm này. Và trong khoảng thời gian 5 năm 1996-2000 chỉ có một vài ngân hàng lớn tiếp tục thực hiện việc nghiên cứu, thử nghiệm dịch vụ ATM. Vào thời kỳ này số lượng ATM ở Việt nam còn khá ít, tổng cộng chỉ vài chục chiếc. Thẻ ATM phát hành chủ yếu cho cán bộ ngân hàng (để thí điểm) là chính. Ngoài thẻ ATM một số ngân hàng có dịch vụ chấp nhận thanh toán thẻ tín dụng quốc tế (Visa, MasterCard v.v.) nhưng đều thực hiện bằng phương pháp thủ công. Smart card (thẻ thông minh), một dạng ví điện tử cũng được số ít ngân hàng thử nghiệm trong phạm vi rất nhỏ. Như vậy, có thể nói giai đoạn 1996-2000 là thời kỳ mở đầu, chủ yếu nghiên cứu, tiếp cận thị trường thanh toán thẻ ở Việt Nam. Từ năm 2001 đến năm 2005 chúng ta đã được chứng kiến sự phát triển vượt bậc của thị trường thẻ thanh toán. Nhiều ngân hàng, kể cả các NHTM Nhà nước và các NHTM cổ phần đã triển khai các dịch vụ thanh toán thẻ với việc ứng dụng công nghệ thông tin, trang bị hệ thống công nghệ thẻ hiện đại và phát hành nhiều loại thẻ khác nhau. Theo số liệu khảo sát của Banknetvn, vào thời điểm cuối năm 2005 ở Việt Nam đã có khoảng 2,7 triệu thẻ thanh toán các loại được phát hành, có trên 1.700 máy ATM và trên 9.000 điểm chấp nhận thẻ (POS) đã được lắp đặt sử dụng. Các loại thẻ thanh toán được phát hành và sử dụng khá phong phú, bao gồm: thẻ ATM, thẻ ghi nợ, thẻ tín dụng, thẻ nội địa, thẻ quốc tế, thẻ tiền mặt v.v. Tốc độ phát triển thẻ thanh toán trong thời kỳ này rất cao, thường xuyên tăng từ trên 200%/năm. Các dịch vụ thanh toán dựa Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 47 trên thẻ cũng ngày được tăng cường. Nó không chỉ dừng ở dịch vụ rút tiền mặt trên ATM mà đã mở rộng ra các dịch vụ chuyển khoản, thanh toán hàng hóa, thanh toán hóa đơn, mua vé, thanh toán cước phí v.v. Nhiều ngân hàng đã kết nối thực hiện thanh toán và phát hành thẻ quốc tế (Visa, MasterCard, Amex, JCB v.v.). Trong thời gian này chủ yếu các Ngân hàng tự đầu tư phát triển dịch vụ thẻ. Điều đáng mừng là việc nhận thức và sự chấp nhận sử dụng các dịch vụ thanh toán thẻ của nhiều tầng lớp nhân dân, nhất là giới trẻ đã được cải thiện đáng kể. Những năm gần đây, đã có những sự liên minh, liên kết giữa các nhóm Ngân hàng để tạo ra các mạng thanh toán thẻ rộng hơn. Nhưng các liên minh thanh toán thẻ này còn nhỏ, lẻ và chưa đáp ứng được nhu cầu kết nối tạo ra một mạng thanh toán thẻ chung thống nhất trong quy mô quốc gia. Từ năm 2006 thị trường thẻ thanh toán Việt Nam tiếp tục phát triển với tốc độ cao. Chỉ tính đến cuối tháng 8/2006 theo ước tính của Banknetvn ở Việt Nam đã có gần 4 triệu thẻ thanh toán được phát hành, trên 2.700 ATM và 12.000 POS được lặp đặt sử dụng. Nhiều Ngân hàng tích cực ứng dụng công nghệ hiện đại, mạnh dạn đầu tư phát triển dịch vụ thanh toán thẻ. Các dịch vụ thanh toán thẻ đã trở nên phổ biến hơn, gần gũi, thân thiện hơn với nhiều người dân. Các Ngân hàng và liên minh thẻ cũng đang xích lại gần nhau hơn. Chắc chắn một mạng thanh toán thẻ chung cho tất cả các ngân hàng sẽ được hình thành trong thời gian không xa. Bởi theo dự báo chủ quan của chúng tôi thị trường thẻ Việt Nam sẽ còn phát triển mạnh trong thời gian ít nhất là 5 năm tới. Với phương châm “đi tắt, đón đầu” trong lĩnh vực thanh toán bằng thẻ, Chính phủ đã ban hành đề án thanh toán không dùng tiền mặt giai đoạn 2006 - 2010. Dự kiến, đến năm 2010, thẻ do một ngân hàng phát hành có thể sử dụng được ở nhiều máy ATM và POS của các ngân hàng khác. Đề án mới về thanh toán không dùng tiền mặt còn nêu rõ, đối với khu vực dân cư sẽ khuyến khích, tạo điều kiện cho các tổ chức cung ứng dịch vụ thanh toán tập trung đầu tư cơ sở hạ tầng, thiết bị phục vụ cho các giao dịch thanh toán hiện đại. Trong kế hoạch từ nay đến 2010, sẽ tập trung chủ yếu cho dịch vụ thẻ và tạo điều kiện phát triển thanh toán qua internet, mobile, đồng thời tiếp cận nhanh chóng với công nghệ hiện đại trên thế giới theo cách thức “đi tắt, đón đầu”. Bên cạnh đó, Chính phủ sẽ chỉ đạo xây dựng trung tâm chuyển mạch thẻ thống nhất, kết nối các hệ thống máy tính ATM của các liên minh thẻ hiện hành thành một hệ thống thống nhất, nhằm tăng tính thuận tiện cho người sử dụng dịch vụ thẻ ngân hàng. Theo đề án, thẻ do một ngân hàng phát hành có thể sử dụng ở nhiều máy ATM và POS của các ngân hàng khác. Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 48 Một trong những mục tiêu không kém phần quan trọng của đề án là phấn đấu đến cuối năm 2010, tất cả các Bộ, cơ quan ngang Bộ, các cấp chính quyền tỉnh, thành phố đều thực hiện chi tiêu bằng phương tiện thanh toán không dùng tiền mặt. Từ 2011 - 2020 sẽ triển khai mở rộng đến các đối tượng là Sở, Ban, ngành, các cấp chính quyền huyện, xã trên phạm vi toàn quốc. Theo lộ trình, đến cuối năm 2010 sẽ có khoảng 20 triệu tài khoản cá nhân; 70% cán bộ hưởng lương ngân sách và 50% công nhân lao động trong khu vực doanh nghiệp, tư nhân được trả lương qua tài khoản. Đến năm 2020, sẽ là 45 triệu tài khoản cá nhân; 95% cán bộ hưởng lương ngân sách và 80% lao động được trả lương qua tài khoản. Tại khu vực doanh nghiệp, sẽ có khoảng 80% các khoản thanh toán giữa doanh nghiệp với nhau được thực hiện qua tài khoản tại ngân hàng và đạt 95% vào năm 2020. Với đề án này, tương lai không xa “ví tiền” của cán bộ, viên chức và công nhân lao động sẽ thu gọn trong 1 tấm thẻ. 4.4. Chương trình a. Mã nguồn #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); Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 49 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 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) Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 50 { 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++; } Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 51 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); Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 52 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); } //=============Hàm 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"); Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 53 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!!"); Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 54 } 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; Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 55 else return t % n; } //====================================================== void chaum() { printf("\n\n =====* GIAO THUC CHOI BO *====="); long a0, a1 = 144, a2 = 874, b1 = 1873, b2 = 2345; long alpha = 25, beta = 1866, gamma1 = 5065; long gamma2 = 5076, p = 5087, q = (p - 1) >> 1; long r, s, x = 4785, y1 = 2219, y2 = 458, z1, z2; r = (gamma1 * exp_mod(gamma2, x, p)) % p; s = (exp_mod(alpha, y1, p) * exp_mod(beta, y2, p)) % p; if (r == s) printf("\nChu ky duoc chap nhan\n"); else printf("\nChu ky khong duoc chap nhan\n"); z1 = (a1 + x * b1) % q; z2 = (a2 + x * b2) % q; if (z2 > y2) a0 = ((y1 - z1) * Extended_Euclidean(z2 - y2, q)) % q; else a0 = ((z1 - y1) * Extended_Euclidean(y2 - z2, q)) % q; if (a0 < 0) a0 += q; printf("alpha = %ld\n", alpha); printf("beta = %ld\n", beta); printf("p = %ld\n", p); printf("q = %ld\n", q); printf("gamma1 = %ld\n", gamma1); printf("gamma2 = %ld\n", gamma2); printf("a1 = %ld\n", a1); printf("a2 = %ld\n", a2); printf("b1 = %ld\n", b1); printf("b2 = %ld\n", b2); printf("x = %ld\n", x); printf("y1 = %ld\n", y1); printf("y2 = %ld\n", y2); printf("sig(%ld) = (%ld, %ld)\n", x, z1, z2); printf("a0 = %ld\n", a0); Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 56 if (beta == exp_mod(alpha, a0, p)) printf("a0 duoc xac nhan\n"); else printf("a0 khong duoc chap nhan\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; Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 57 } 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; } Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 58 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) Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 59 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(" [2].CHU KY ELGAMAL"); printf("\n [3].GIAO THUC CHOI BO"); printf(" [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() Đồ án tốt nghiệp Tìm hiểu Chữ kí nhóm và ứng dụng trong giao dịch điện tử Sinh viên: Phạm Thị Hiểu Lớp CT702 60