Một số lược đồ chữ ký số mù mới dựa trên hai bài toán DLP và ECDLP - Nguyễn Thị Huyền

Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 3 MỘT SỐ LƯỢC ĐỒ CHỮ KÝ SỐ MÙ MỚI DỰA TRÊN HAI BÀI TOÁN DLP VÀ ECDLP Nguyễn Thị Huyền1*, Nguyễn Tiền Giang1, Nguyễn Hiếu Minh2, Đỗ Thị Bắc3 1Cục Công nghệ thông tin – Bộ Quốc Phòng, 2Học viện kỹ thuật quân sự 3Trường Đại học Công nghệ thông tin và Truyền thông - ĐH Thái Nguyên TÓM TẮT Chữ ký số mù được sử dụng để bảo vệ tính ẩn danh của người dùng trong mạng máy tính. Trong thực tế, ngoài sơ đồ chữ ký số mù đơn (với một người ký) có nhiều ứng dụng yêu cầu nhiều hơn một người ký trên một bản tin điện tử. Khi đó, người dùng sẽ làm mù bản tin cần ký sau đó bản tin đã được làm mù này sẽ được gửi đến từng người ký để họ ký. Và tất cả những người ký đều sử dụng chung một giao thức chữ ký số tập thể mù. Hiện tại, phần lớn các lược đồ chữ ký số mù, đều được xây dựng trên cơ sở sử dụng một bài toán khó. Vì vậy, nếu có thuật toán có thể giải bài toán khó này khi đó lược đồ sẽ bị phá vỡ. Do vậy, để tăng tính an toàn cho các lược đồ này thì chúng cần phải được xây dựng dựa trên sự kết hợp đồng thời của hai bài toán khó. Bài báo này đề xuất một lược đồ chữ ký số mù và chữ ký số tập thể mù mới. Mà cơ sở toán học của các sơ đồ này là dựa trên độ khó của hai bài toán logarit rời rạc: trên trường số nguyên và trên đường cong Elliptic. Đây là các lược đồ chữ ký số mù đầu tiên được đề xuất dựa trên sự kết hợp của hai bài toán khó: DLP và ECDLP. Từ khóa: DLP, ECDLP, chữ ký số mù, chữ ký số mù tập thể, chữ ký số nhóm mù MỞ ĐẦU* Khái niệm về chữ ký số mù (blind signature) được đề xuất bởi David Chaum [5] và nó được phát triển dựa trên lược đồ chữ ký số RSA [16] vào năm 1983. Chữ ký số mù được sử dụng để bảo vệ tính ẩn danh (anonymity) của người dùng trong mạng máy tính, đặc biệt trong các hệ thống thanh toán điện tử (electronic cash systems) và hệ thống bầu cử điện tử (electronic voting systems) bởi nó có hai đặc tính cần phải thỏa mãn [5]: Tính mù (blindless) và tính không truy vết (unlinkability). Tính mù có nghĩa là người ký không được biết về nội dung của văn bản khi ký. Tính không truy vết có nghĩa là khi chữ ký mù được công bố thì người ký không thể thấy được mối liên hệ giữa văn bản mù đã ký với văn bản gốc. Với những tính chất như vậy chữ ký số mù trở nên rất được quan tâm và nghiên cứu trong các ứng dụng cần đảm bảo tính ẩn danh. Có rất nhiều lược đồ chữ ký số mù đã được đề xuất và phát triển, chúng thường được xây dựng dựa trên một số bài * Tel: 0989 954985. Email: huyen41.mta@gmail.com toán khó: bài toán phân tích số (IFP) [5], bài toán logarit rời rạc trên trường số nguyên [7], bài toán logarit rời rạc trên đường cong elliptic [8, 9, 4, 6, 2] và dựa trên sự kết hợp đồng thời hai hay nhiều bài toán khó [14, 10, 13]. Khi chữ ký số mù mới ra đời và phát triển thì các lược đồ chữ ký số mù chỉ cho phép một người ký mù trên văn bản (chữ ký số mù đơn). Tuy nhiên trong thực tế, có thể đặt ra yêu cầu mong muốn nhiều hơn một người ký mù trên văn bản và chữ ký số tập thể mù ra đời để đáp ứng yêu cầu đó. Hiện tại, phần lớn các lược đồ chữ ký số mù, đều được xây dựng trên cơ sở sử dụng một bài toán khó. Mặc dù hiện nay các bài toán khó này vẫn được chứng minh là an toàn, nhưng có thể trong tương lai xuất hiện các thuật toán hiệu quả hơn mà có thể giải được các bài toán này. Vì vậy, để tăng tính an toàn cho các lược đồ chữ ký số mù, bài báo này đề xuất một lược đồ chữ ký số mù đơn và một giao thức chữ ký số tập thể mù mới dựa trên sự kết hợp đồng thời của bài toán logarit rời rạc trên trường số nguyên (DLP) và bài toán logarit rời rạc trên đường cong elliptic Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 4 (ECDLP). Vì vậy, để tấn công các lược đồ này yêu cầu phải giải đồng thời cả hai bài toán khó: DLP và ECDLP. Các lược đồ chữ ký số mù đơn và lược đồ chữ ký số tập thể mù đề xuất, được xây dựng dựa trên các lược đồ chữ ký số cơ sở là lược đồ Schnorr và EC Schnorr [3, 16]. Việc sử dụng các lược đồ chữ ký số của Schnorr để phát triển các lược đồ chữ ký số mù mới cho phép kế thừa các ưu điểm về hiệu năng và độ an toàn của lược đồ chữ ký số đã được kiểm chứng trong thực tế. Phần còn lại của bài báo tổ chức như sau. Trong phần 2, mô tả tổng quan hai bài toán DLP và ECDLP, hai lược đồ chữ ký số của Schnorr và tính chất của chữ ký số mù. Phần 3 trình bày các lược đồ chữ ký số mù đơn và chữ ký số tập thể mù mà để phá vỡ chúng yêu cầu giải đồng thời hai bài toán DLP và ECDLP. Trong phần 4, phân tích các lược đồ được đề xuất và phần cuối cùng là kết luận các nghiên cứu đã thực hiện. CƠ SỞ TOÁN HỌC VÀ MỘT SỐ VẤN ĐỀ LIÊN QUAN Bài toán DLP Cho p là một số nguyên tố, Zp là tập các số nguyên {0, 1, 2, , p-1} mà phép tính cộng và nhân được thực hiện theo modul p. *pg Z khác 0 gọi là phần tử sinh bậc q của .pZ Bài toán logarit rời rạc (DLP) được định nghĩa như sau: Cho một số nguyên tố p, một phần tử sinh g thuộc * pZ , và một số * py Z khác 0 hãy tìm một số nguyên z, 1 2,z p   thỏa mãn điều kiện (mod ).zy g p Số nguyên z được gọi là logarit rời rạc cơ số g của y. Bài toán ECDLP Bài toán logarit rời rạc trên đường cong Elliptic (ECDLP) được định nghĩa như sau: Một đường cong E được định nghĩa trên trường pF trong đó p là số nguyên tố, pF là trường hữu hạn chứa p phần tử, một điểm ( )pG E F có bậc q và một điểm ( )pP E F khi đó tồn tại số nguyên z mà 1 1,z q   thỏa mãn .P zG Lược đồ chữ ký số Schnorr Lược đồ chữ ký số Schnorr: Lược đồ được mô tả ngắn gọn như sau [3]: Pha sinh khóa: Phát sinh hai số nguyên tố mạnh p, q thỏa mãn điều kiện p = Nq + 1 và 1024p  bit, 160q  bit. - Phát sinh phần tử sinh g có bậc q thuộc * .pZ - Chọn số nguyên z với 1 1,z q   làm khóa bí mật. - Tính khóa công khai y = g z mod p. Pha sinh chữ ký: - Phát sinh giá trị k ngẫu nhiên, với 1 1.k q   - Tính r = g k mod p và e=H(M||r). - Tính s = (k +ze) mod q. Bộ giá trị (e, s) là chữ ký trên văn bản M. Pha kiểm tra chữ ký: Sử dụng khóa công khai y của người ký. - Tính r* = g s y -e mod p và * *( ).e H M r - Nếu e* = e thì chữ ký là hợp lệ, ngược lại chữ ký không hợp lệ. Lược đồ chữ ký số EC Schnorr: Lược đồ chữ ký số trên được xây dựng dựa trên đường cong Elliptic [16]. Pha sinh khóa: Phát sinh đường cong E được định nghĩa trên trường pF trong đó p là số nguyên tố, pF là trường hữu hạn chứa p phần tử, và một điểm ( )pG E F có bậc q. Chọn số nguyên z với 1 1,z q   làm khóa bí mật. Tính khóa công khai P = zG. Pha sinh chữ ký: - Phát sinh giá trị k ngẫu nhiên, với 1 1.k q   - Tính R = kG = (xR, yR) và ( ).Re H M x - Tính s = (k + ze) mod q. Bộ giá trị (e, s) là chữ ký trên văn bản M. Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 5 Pha kiểm tra chữ ký: Sử dụng khóa công khai y của người ký. - Tính R* = sG - eP và * * ( ). R e H M x - Nếu e* = e thì chữ ký là hợp lệ, ngược lại chữ ký không hợp lệ. Tính chất của chữ ký số mù Các lược đồ chữ ký số mù phải thỏa mãn các tính chất sau: tính đúng, tính mù, tính không thể giả mạo, tính không liên kết. Tính đúng (correctness): Mọi người đều có thể kiểm tra được tính đúng của chữ ký khi biết khóa công khai và lược đồ chữ ký số mù. Tính không truy vết (unlinkability): Người ký (signer) trong lược đồ chữ ký số mù không biết được nội dung của văn bản khi ký và cũng không thể tìm ra mối liên hệ giữa chữ ký và văn bản gốc ngay cả khi chữ ký được công khai. Tính ngẫu nhiên (randomization): Người ký chọn các hệ số ngẫu nhiên để thực hiện ký mù mà đảm bảo những kẻ tấn công (attacker) không thể tính toán ra được chữ ký và người yêu cầu ký (requester) cũng không thể loại bỏ được các hệ số ngẫu nhiên này của người ký. Tính không thể giả mạo (unforgeability): Chỉ có người ký tham gia vào lược đồ mới tạo ra được chữ ký hợp lệ và không ai có thể tạo ra chữ ký giả mạo và vượt qua được bước kiểm tra. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ MÙ Lược đồ chữ ký số mù đơn Để xây dựng lược đồ chữ ký số mù, mà để tấn công nó yêu cầu phải giải quyết đồng thời bài toán logarit rời rạc trên trường hữu hạn (DLP) và bài toán logarit rời rạc trên đường cong elliptic (ECDLP), có thể phát triển chúng dựa trên sự kết hợp hai lược đồ chữ ký số của Schnorr [3, 16]. Đây là các lược đồ chữ ký số đã được chứng minh là an toàn và hiệu quả, và sẽ được sử dụng như các lược đồ chữ ký số cơ sở để xây dựng các lược đồ chữ ký số mù trong bài báo này. - Tham số chính của bài toán DLP: ( , , ).p q g - Tham số chính của bài toán ECDLP: ( , , , , ).p a b G q Trong đó: p, q là các số nguyên tố mạnh, 1024p  bit, 160q  bit, 1.p Nq  ,a b là hệ số của đường cong Elliptic, g là phần tử sinh của * ,pZ điểm G là phần tử sinh của nhóm điểm trên đường cong Elliptic. Với g, G có cùng bậc q và 1(mod ).qg p Lược đồ chữ ký số mù đề xuất bao gồm ba pha: pha sinh khóa, pha tạo chữ ký, pha kiểm tra chữ ký và có hai thành phần tham gia (người yêu cầu ký A (requester A) và người ký B (signer B)) để tạo chữ ký số mù cho văn bản M. Lược đồ thực hiện như sau: Pha sinh khoá: - Người ký B phát sinh các giá trị ngẫu nhiên 1 2,z z với 1 21 , 1z z q   làm khóa bí mật - Khóa công khai (y, P) được tính như sau: và P=z2G. Pha sinh chữ ký: Thủ tục sinh chữ ký bao gồm 4 vòng được sinh ra bởi người ký B và người yêu cầu ký A. Thủ tục ký được thực hiện trên văn bản M đã được làm mù. - Người ký B (vòng 1): Chọn hai số ngẫu nhiên 1 2, 11 qk k   , và tính 1 (mod ) k r g p và điểm 2 .R k G Sau đó B gửi r và R cho A - Người yêu cầu ký A (vòng 2): Phát sinh các giá trị ngẫu nhiên , , {1,2,..., -1}q    và tính modr rg y p   và điểm ( , ).R RR R G P x y        Sau đó A tính thành phần đầu tiên của chữ ký ( )H Re F M r x   trong đó HF là hàm băm (ví dụ SHA) và (mod ).e e q  Sau đó A gửi e cho B. - Người ký B (vòng 3): Tính các giá trị 1 2,s s theo công thức 1 1 1 (mod ),s k z e q  2 2 2 (mod ).s k z e q  - Sau đó B gửi (s1, s2) cho A. Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 6 - Người yêu cầu ký A (vòng 4): Tính 1s và 2s theo công thức 1 1 (mod ),s s q   2 2 (mod ).s s q   Bộ giá trị 1 2( , , )e s s   là chữ ký số mù cho văn bản M và độ dài của chữ ký là 1 2 3 480 .e s s q bit      Pha kiểm tra chữ ký: Người kiểm tra sử dụng cặp khóa công khai ( , )y P để kiểm tra chữ ký. - Tính giá trị và điểm * * * 2 ( , ).R RR s G e P x y    - Tính giá trị - Nếu *e e  thì chữ ký là hợp lệ, ngược lại chữ ký là không hợp lệ Giao thức chữ ký số tập thể mù Dựa trên lược đồ chữ ký mù đơn đã được trình bày trong phần 3.1. Trong phần này sẽ trình bày về giao thức chữ ký tập thể mù được phát triển dựa trên lược đồ chữ ký số mù đơn. Giao thức chữ ký số đề xuất bao gồm ba pha: pha sinh khóa, pha tạo chữ ký và pha kiểm tra chữ ký. Và thành phần tham gia gồm nhóm m người ký  1 2, ,..., mB B B và người yêu cầu ký A. Pha sinh khóa: Trong giao thức này, khóa công khai ( , )i iy P của từng người ký iB được tính dựa trên các cặp khóa bí mật 1 2( , )i iz z theo công thức 1 (mod )i z iy g p và 2 .i iP z G - 11 21 ( , ),z z 12 22( , ),z z , 1 2( , )m mz z tương ứng là cặp khóa bí mật của các thành viên trong nhóm người ký. Cặp khóa này được phát sinh ngẫu nhiên thỏa mãn 1 21 , 1i iz z q   với ( 1,2,..., )i m và cặp khóa này được người các người ký iB giữ bí mật. - (y1, P1), (y2, P2),, (ym, Pm) tương ứng là cặp khóa công khai của người ký. Cặp khóa (yi, Pi), được người ký Bi tính theo công thức và Pi=z2iG và công khai cho các thành viên tham gia giao thức này. - Cặp khóa công khai tập thể ( , )Y P được tính dựa trên các cặp khóa công khai của tất cả những người ký theo công thức 1 (mod ) m i i Y y p   và 1 (mod ). m i i P P p   Pha sinh chữ ký: Thủ tục sinh chữ ký bao gồm 4 vòng được sinh ra bởi tập thể người ký và người yêu cầu ký A. Thủ tục ký được thực hiện trên văn bản M đã được làm mù. - Tập thể người ký (vòng 1): Mỗi người ký phát sinh cặp số ngẫu nhiên 1 21 , 1i ik k q   và tính 1 (mod ),i k ir g p 2i iR k G và gửi công khai cặp ( , )i ir R cho những người ký còn lại. Sau đó, mỗi người ký tính cặp tham số ngẫu nhiên chung theo công thức 1 (mod ), m i i r r p   1 (mod ) m i i R R p   rồi gửi cho A. - Người yêu cầu ký A (vòng 2): Chọn các giá trị ngẫu nhiên , , {1,2,..., -1}q    tính (mod ),r rg Y p   ( , ).R RR R G P x y        - Sau đó A tính thành phần đầu tiên của chữ ký ( )H Re F M r x   trong đó FH là hàm băm và tính (mod )e e q  . Sau đó A gửi e cho tất cả những người ký. - Tập thể người ký (vòng 3): Mỗi người ký dựa vào cặp giá trị ngẫu nhiên 1 2( , )i ik k và cặp khóa bí mật 1 2( , )i iz z để tính các giá trị - 1 1 1 (mod ),i i is k z e q  2 2 2 (mod ).i i is k z e q  - Sau đó tính cặp chữ ký chung của tất cả những người ký theo công thức 1 1 1 (mod ). m i i s s q   2 2 1 (mod ). m i i s s q   - Sau đó gửi (s1, s2) cho A. - Người yêu cầu ký A (vòng 4): Tính hai thành phần tiếp theo của chữ ký 1 2( , )s s  cho văn bản M theo công thức 1 1 (mod ),s s q   2 2 (mod ).s s q   Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 7 Bộ giá trị 1 2( , , )e s s   là chữ ký số tập thể mù cho văn bản M và chiều dài của chữ ký là 1 2 3 480 .e s s q bit      Pha kiểm tra chữ ký: Thủ tục kiểm tra chữ ký số mù dựa trên cặp khóa công khai chung của tất cả người ký ( , ).Y P - Tính giá trị 1 (mod )s er g Y p    và điểm 2 ( , ).R RR s G e P x y       - Tính giá trị ( ).H Re F M r x    - Nếu e e  thì chữ ký là hợp lệ, ngược lại chữ ký là không hợp lệ. PHÂN TÍCH CÁC LƯỢC ĐỒ ĐỀ XUẤT Trong phần này, đưa ra kết quả phân tích độ an toàn và đánh giá hiệu quả của các lược đồ chữ ký số mù đã đề xuất. Tính đúng Định lý 1 (chữ ký số mù đơn): Chữ ký 1 2( , , )e s s   là chữ ký hợp lệ của người ký có cặp khóa công khai ( , )y P cho văn bản M. Chứng minh Tính các giá trị 1* (mod )s er g y p   và * 2 .R s G e P   Nếu r r   và R R  thì ( ) .H Re F M r x e     Thật vậy, 1 1 1 1 1* s s k z e z ee er g y g y g g y              1 1 ; k g g y r g y r       * 2 2( ) ( )R s G e P s G e P        2 2 2 2 2 2 ( ) ( ) ( ) . k z e G e P k z e G ez G P k G G P R                     ( ) .H Re F M r x e      Khi đó bộ giá trị 1 2( , , )e s s   là chữ ký hợp lệ. Định lý 2 (chữ ký số tập thể mù): Chữ ký 1 2( , , )e s s   là chữ ký hợp lệ của m người ký cho văn bản M. Chứng minh: Sử dụng cặp khóa công khai tập thể của m người ký, ta có: 1 (mod ) m i i Y y p   và 1 . m i i P P   Tính các giá trị 1* (mod )s er g Y p   và * 2 ,R s G e P   ta thấy 1 1 1 11 1 ( ) 1 * m i i i i mk z e z es se e i r g y g y g g y                   1 1 1 1 1 1 1 ( ) 1 1 1 1 1 1 ; i i i i i i i m m k z e z e i i m m m k z e z e i i i m k i g g g y g g g g y g g y rg y r                             * 2 2( ) ( )R s G e P s G e P        2 2 1 ( ( ) ) ( ) m i i i k z e G e P        2 2 2 1 1 1 m m m i i i i i i k G z eG G z eG P            2 1 . m i i k G G P R G P R              .e e  Khi đó bộ giá trị 1 2( , , )e s s   là chữ ký hợp lệ. Tính không truy vết Định lý 3 (Chữ ký số mù đơn): Giao thức chữ ký số mù đề xuất đảm bảo tính không truy vết trong trường hợp văn bản M và chữ ký 1 2( , , )e s s   được công khai với người ký. Chứng minh: Người ký khi tham gia vào giao thức ký mù trên văn bản M họ biết các tham số 1 2( , , , , )r R e s s tạo nên chữ ký. Với xác suất của những người yêu cầu tham gia vào lược đồ là như nhau. Khi đó các tham số này thỏa mãn: 1 (mod ) s er g y p (1) Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 8 2R s G eP  (2) ' ' 1' (mod ) s er g y p (3) ' ' ' 2R s G e P  (4) Từ (1) và (3) ta có ' ' 1 ' ' 1 1 1 ' ( )(mod ) (mod ) s e s s e e s e r g y p g y p r g y        ' (mod ) r g y p r    Từ (2) và (4) ta có: ' ' ' 2 2( ) ( )R R s s G e e P G P        Vì các giá trị , ,   được sinh ra ngẫu nhiên, vì vậy từ bộ giá trị 1 2( , , , , )r R e s s có thể sinh ra rất nhiều bộ giá trị 1 2( , , , , )r R e s s     ngẫu nhiên. Do vậy, dù có lưu lại các bộ giá trị 1 2( , , , , )r R e s s thì người ký cũng không thể biết từ các bộ giá trị này sẽ sinh ra chữ ký số mù nào. Vì vậy, lược đồ chữ ký số mù trên đảm bảo được tính không truy vết. Định lý 4 (Chữ ký số tập thể mù): Giao thức này cung cấp tính không truy vết khi văn bản M và chữ ký 1 2( , , )e s s   được công khai với tất cả những người ký. Chứng minh: Với m người ký khi tham gia vào giao thức ký mù trên văn bản M họ biết các tham số 1 2( , , , , )i i i ir R e s s với 1,2,...,i m tạo nên chữ ký và các tham số: 1 (mod ), m i i r r p   1 (mod ) m i i R R p   (mod )r rg Y p   ; R R G P     (mod );e e p  1 1 1 (mod ) m i i s s q   2 2 1 (mod ); m i i s s q   1 1 (mod )s s q   2 2 (mod ).s s q   Theo công thức trên để tính 1 2( , , , , )r R e s s     cần có 1 2( , , , , )r R e s s và các giá trị ngẫu nhiên , , .   Vì các giá trị , ,   được sinh ra ngẫu nhiên, vì vậy từ bộ giá trị 1 2( , , , , )r R e s s có thể sinh ra rất nhiều bộ giá trị 1 2( , , , , )r R e s s     ngẫu nhiên. Do vậy, dù có lưu lại các bộ giá trị 1 2( , , , , )r R e s s thì các người ký cũng không thể biết từ các bộ giá trị này sẽ sinh ra chữ ký số mù nào. Vì vậy, lược đồ chữ ký số mù trên đảm bảo được tính không truy vết. Tính ngẫu nhiên Định lý 5 (Chữ ký số mù đơn): Lược đồ chữ ký số mù đề xuất đảm bảo tính ngẫu nhiên, đó là người yêu cầu ký không thể loại bỏ được các hệ số ngẫu nhiên của người ký khi thực hiện thủ tục sinh chữ ký. Chứng minh: Trong lược đồ chữ ký số mù, người yêu cầu ký (hoặc kẻ tấn công) không thể tạo một chữ ký mù hợp lệ 1 2( , , )e s s   với vai trò như người ký thông thường. Do người ký phải chọn hai giá trị ngẫu nhiên 1 21 , 1k k q   và tính 1 (mod ), k r g p 2 .R k P Do vậy, để nhận được 1 2,k k từ r và R là thực tế không thể tính được (do cần phải giải được cả hai bài toán khó DLP và ECDLP). Định lý 6 (Chữ ký số tập thể mù): Giao thức chữ ký số mù đề xuất đảm bảo được tính ngẫu nhiên. Chứng minh: Tương tự như chứng minh của chữ ký số mù đơn. Tính không thể giả mạo Định lý 7 (Chữ ký số mù đơn): Chỉ người ký mới có thể tạo ra chữ ký hợp lệ Tấn công 1: Kẻ tấn công cố gắng tìm ra 1 2( , , )e s s   từ văn bản M bằng việc giữ cố định một (hoặc hai) tham số và tìm các tham số còn lại. Ví dụ: Trong giao thức ký mù trên kẻ tấn công giữ cố định e´ và tìm 1 2,s s  thỏa mãn 1 (mod ) s er g y p    và 2R s G e P    . Để làm được điều này kẻ tấn công đầu tiên phải chọn hai tham số ngẫu nhiên r´, R´. Sau đó tính 1 (mod ) s eg r y p   và 2 ,s G R e P    để tính được 1 2,s s  cần phải giải được hai bài toán logarit rời rạc để tìm 1 log ( )(mod ) e gs r y p   và 2 .s G R e P    Do Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 9 vậy, để tính được hai giá trị (thỏa mãn) còn lại của chữ ký, kẻ tấn công cần phải giải đồng thời hai bài toán DLP và ECDLP. Định lý 8 (Chữ ký số tập thể mù): Tấn công 1: Giả thiết (m-1) người ký (cố gắng) tạo chữ ký số tập thể mù hợp lệ tương ứng với m người ký. Thực hiện tính các giá trị khóa công khai: (mod ),mY y y p trong đó 1 1 (mod ). m i i y y p     Và ,mP P P  trong đó 1 1 . m i i P P     (m-1) người ký cố gắng tạo ra 1 2, , ,r R s s thỏa mãn 1 (mod ) s er g Y p và 2R s G eP  1 ( ) (mod ), s e mr g y y p  2 ( ) ( , ).m R RR s G e P P x y   Giả thiết (m-1) người ký có thể tính được * * * * * 1 2( , , , , )r R e s s tương ứng với khóa công khai ( , )Y P khi đó: 1 1 1 1 11 1 * ** * * * ** * * (mod ) ( ) (mod ) (mod ) (mod ) m i i s se e m e z s se e e m m r g Y p g y y p g y y p y g g p              1 1 1 1 1 * * *** * (mod ), m i i s e z se e m my g y g p         với 1 ** * * 1 1 1 1 (mod ). m i i s s e z q      Và * * * * 2 2 ( )mR s G e P s G e P P    * * * 2 1 * * * 2 2 1 * ** 2 ( ) . m m m i i m s G e P e P e P G s e z e P Gs              với 1 ** * * 2 2 2 1 (mod ). m i i s s e z q      Khi đó thông qua chữ ký tập thể giả mạo sẽ tính được chữ ký * ** **1 2( , , )e s s là hợp lệ với văn bản M của người ký thứ m và ( )H Re F M r x    thỏa mãn thủ tục kiểm tra của lược đồ chữ ký số mù đơn. Do vậy, bất kỳ tấn công phá vỡ được chữ ký số mù đơn thì cũng phá vỡ được chữ ký số tập thể mù. Tuy nhiên, theo chứng minh ở trên, thì lược đồ chữ ký số mù đơn là an toàn do đó lược đồ chữ ký số tập thể mù đề xuất là an toàn. Tấn công 2: Giả thiết (m-1) người ký chia sẻ chữ ký số tập thể mù 1 2( , , )i ie s s với i =1, 2,, m-1 với người ký thứ m và (m-1) người ký này (cố gắng) tính toán khóa bí mật của người ký thứ m. (m-1) người ký sẽ phải tính 1 2( , , , )m m m mr R s s được tạo bởi người ký thứ m. Các giá trị này thỏa mãn 1 1 1(mod ) (mod ),m m m s s eze m mr g y p g p   2m m mR s G eP  2 2( ).m mG s ez  Tuy nhiên, , ,m mr R e nằm ngoài khả năng kiểm soát của kẻ tấn công, bởi 1 (mod )m k mr g p và 2m mR k G trong đó 1 2,m mk k là các giá trị ngẫu nhiên được tạo bởi người ký thứ m, e là đầu ra của hàm băm an toàn. Do vậy, những kẻ tấn công không thể chọn giá trị R từ việc chọn giá trị e đặc biệt. Điều này có nghĩa là tương tự với chữ ký số mù đơn việc tính toán khóa bí mật yêu cầu giải đồng thời hai bài toán logarit rời rạc 1 log (mod ),m g mk r p và tính 1 1 1 1( )(mod ).m m mz e k s p   và bài toán logarit rời rạc trên đường cong elliptic 2 ,m mR k G và tính 1 2 2 2( ) .m m mz k s e    Đánh giá hiệu năng Trong phần này, thực hiện phân tích hiệu năng của các lược đồ chữ ký số mù và chữ ký số tập thể mù đã đề xuất thông qua việc tính số lượng các phép tính hàm mũ modulo, số phép tính nhân modulo, số phép tính hàm băm, và số phép tính hàm nghịch đảo modulo. Để thuận tiện, các ký hiệu sau được sử dụng khi đánh giá hiệu năng của các lược đồ chữ ký số mù đề xuất. ET chỉ số lượng phép tính hàm mũ modulo. MT chỉ số lượng phép tính nhân modulo. HT chỉ lượng phép tính hàm băm .HF Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 10 IT chỉ lượng phép tính nghịch đảo theo modulo. Tp chỉ số lượng phép tính nhân điểm. Chú ý: Thời gian để tính phép cộng modulo và phép trừ modulo là được bỏ qua khi thời gian này nhỏ hơn rất nhiều so với ,ET ,MT ,HT .IT Việc so sánh số lượng các phép tính (được thực hiện bởi người yêu cầu ký để tạo và kiểm tra chữ ký) giữa lược đồ chữ ký số mù đơn đề xuất và các lược đồ [7, 10, 11] được thể hiện trong bảng 1. Bảng 1: Số lượng các phép tính được thực hiện bởi người yêu cầu ký để tạo và kiểm tra chữ ký CKS mù đơn đề xuất [7] [10] [11] Số các phép tính hàm mũ 4TE 4TE 11TE 3TE Số các phép tính nghịch đảo 1TI 2TI 4TI 3TI Số các phép băm 2TH 0 4TH 1TH Số các phép tính nhân 3TM 6TM 13TM 8TM Số các phép tính nhân điểm 4Tp 0 0 0 So sánh số lượng các phép tính (được thực hiện bởi người yêu cầu ký để tạo và kiểm tra chữ ký) giữa lược đồ chữ ký số tập thể mù đề xuất và lược đồ [12] được thể hiện trong bảng 2. Bảng 2: Số lượng các phép tính được thực hiện bởi người yêu cầu ký để tạo và kiểm tra chữ ký CKS tập thể mù đề xuất [12] Số các phép tính hàm mũ 4TE 4TE Số các phép tính nghịch đảo 1TI 1TI Số các phép băm 2TH 2TH Số các phép tính nhân 3TM 3TM Số các phép tính nhân điểm 4Tp 0 Trên thực tế, trong hầu hết các ứng dụng dựa trên chữ ký số mù, phía người ký thường có (sở hữu) năng lực xử lý cao hơn so với phía người yêu cầu ký, vì khả năng tính toán ở phía người yêu cầu ký có thể bị hạn chế như khi sử dụng các thiết bị di động. Do vậy để đảm bảo chất lượng của các dịch vụ này cần phải giảm tải tính toán cho phía người yêu cầu ký hơn là cho những người ký. KẾT LUẬN Trong bài báo đã đề xuất một lược đồ chữ ký số mù đơn và chữ ký số tập thể mù mà để tấn công nó phải yêu cầu giải được đồng thời hai bài toán logarit rời rạc trên trường số nguyên và logarit rời rạc trên đường cong elliptic. Các lược đồ chữ ký số mới này yêu cầu số các phép tính cho người yêu cầu ký để tạo và kiểm tra chữ ký là đủ nhỏ, so với các lược đồ chữ ký số mù khác. Các lược đồ này đã được chứng minh đảm bảo tính đúng, tính mù, tính không thể giả mạo, tính ngẫu nhiên và đảm bảo tính an toàn cao hơn so với các lược đồ chữ ký số mà được xây dựng chỉ dựa trên một bài toán khó. TÀI LIỆU THAM KHẢO 1. C. I. Fan, C. I. Wang and W. Z. Sun, “Fast randomization schemes for Chaum blind signatures”, International Journal of Innovative Computing, Information and Control, vol.5, no.11(A), pp.3887-3900, 2009. 2. C. P. Schnorr, “Schnorr Blind Signature Based on Elliptic Curves”, Asian Journal of Information Technology 2 (3):130-134, 2003. 3. C. P. Schnorr, “Efficient signature generation by smart cards”, Journal of Cryptology, (1991), Vol. 4, pp. 161-174. 4. Constantin Popescu, 1999, “Blind Signature and Blind Multisignature Schemes using Elliptic Curves” Informatica, Vol. 44, No. 2, 1999. Nitro PDF Software 100 Portable Document Lane Wonderland Nguyễn Thị Huyền và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 135(05): 3 - 11 11 5. D. Chaum, “Blind signatures for untraceable payments”, Advances in Cryptology, CRYPTO’82, Plenum, pp. 199-203, 1983. 6. F. G. Jeng, T. L. Chen, and T. S. Chen, “An ECC-Based Blind Signature Scheme”, Journal of networks, vol. 5, no. 8, 2010. 7. J. L. Camenish, J. M. Priveteau, and M. A. Stadler, “Blind signature based on the discrete logarithm problem”, Advances in Cryptology (Eurocrypt '94), LNCS 950, Springer-Verlag, pp. 428-432, 1994. 8. J. Debasish, J. K. Sanjay, M. Banshidhari, and P. K. Saroj, “A novel ECDLP-based blind signature scheme with an illustration”, Web engineering and applications, pp. 59-68, 2008. 9. Joe Hurd, “Elliptic Curve Cryptography – A case study in formalization using a higher order logic theorem prover”, Oxford University, course notes 2005. 10. N. M. F. Tahat, E. S. Ismail and R. R. Ahmad, “A New Blind Signature Scheme Based On Factoring and Discrete Logarithms”, International Journal of Cryptology Research 1 (1): 1-9, (2009). 11. N. A. Moldovyan, “Blind Signature Protocols from Digital Signature Standards”, International Journal of Network Security, Vol.13, No.1, pp.22– 30, July 2011. 12. N. A. Moldovyan and A. A. Moldovyan, “Blind Collective Signature Protocol Based on Discrete Logarithm Problem”, International Journal of Network Security, Vol.11, No.2, PP.106-113, Sept. 2010. 13. N. H. Minh, D. V. Binh, N. T.Giang and N. A. Moldovyan, “Blind Signature Protocol Based on Difficulty of Simultaneous Solving Two Difficult Problems”, Applied Mathematical Sciences, Vol. 6, no. 139, 6903 – 6910, 2012. 14. N. M. F. Tahat, S. M. A. Shatnawi and E. S. Ismail, “New Partially Blind Signature Based on Factoring and Discrete Logarithms”, Journal of Mathematics and Statistics 4, pp. 124-129, (2008). 15. R L Rivest, A Shamir, L Adleman, “On Digital Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol 21, No 2, pp120-126, Feb 1978. 16. Zhaohui Cheng, “Simple Tutorial on Elliptic Curve Cryptography” December 1, 2004. SUMMARY NEW BLIND SIGNATURE SCHEMES BASED ON DLP AND ECDLP Nguyen Thi Huyen 1* , Nguyen Tien Giang 1 , Nguyen Hieu Minh 2 , Do Thi Bac 3 1Department of Defense, 2 Le Qui Don Technical University 3 College of Information and Communication Technology - TNU Blind signature is commonly used in electronic transactions to protect the anonymity of users on a computer network as required. In practice, besides the type of single blind signature scheme (with a blind signer), there are many applications may require more than one blind signer on an electronic message. In which, an electronic message is first blinded then passed to each of the signers, who then signs it using a signature protocol such as multisignature protocol. And in this case, all the signers are generally using a protocol known as blind multisignature. Typically, most of the developed blind signatures are based on a single difficult problem. If one finds a solution to this problem then the blind schemes are breakable. Therefore, to improve the security of digital signature schemes, they can be built based on a simultaneous combination of multiple hard problems. This paper proposed a new blind signature scheme and a new blind multisignature protocol. Mathematical basis of the schemes are based on the difficulty of combining both the discrete logarithm problems: on the integer field and on the elliptic curve. There are first blind signature schemes proposed based on the combination of two hard problems: DLP and ECDLP Keyword: DLP, ECDLP, blind signature, signature of collective blindness, blind multisignature Ngày nhận bài:30/11/2014; Ngày phản biện:27/12/2014; Ngày duyệt đăng:31/5/2015 Phản biện khoa học: TS. Lưu Hồng Dũng – Học viện Kỹ thuật Quân sự * Tel: 0989 954985. Email: huyen41.mta@gmail.com Nitro PDF Software 100 Portable Document Lane Wonderland