Một lược đồ chữ ký tập thể xây dựng trên tính khó của việc giải bài toán phân tích số và khai căn trên Zn - Phạm Văn Hiệp

Công nghệ thông tin P. V. Hiệp, V. S. Hà, L. H. Dũng, “Một lược đồ chữ ký tập thể khai căn trên Zn.” 42 MỘT LƯỢC ĐỒ CHỮ KÝ TẬP THỂ XÂY DỰNG TRÊN TÍNH KHÓ CỦA VIỆC GIẢI BÀI TOÁN PHÂN TÍCH SỐ VÀ KHAI CĂN TRÊN Zn Phạm Văn Hiệp1*, Vũ Sơn Hà 2, Lưu Hồng Dũng 3, Nguyễn Thị Lan Phượng4 Tóm tắt: Bài báo đề xuất một lược đồ chữ ký số tập thể ứng dụng phù hợp cho đối tượng là các cơ quan nhà nước, đơn vị hành chính, doanh nghiệp,... mà ở đó các thông điệp dữ liệu cần phải được chứng thực về nguồn gốc và tính toàn vẹn ở hai cấp độ: thực thể ký và tổ chức (cơ quan, đơn vị, ...) mà thực thể ký là thành viên của nó. Lược đồ mới đề xuất ở đây được phát triển từ một dạng lược đồ chữ ký mới được xây dựng dựa trên tính khó của việc giải hai bài toán phân tích số và khai căn trên vành Zn. Từ khóa: Chữ ký số; Chữ ký số tập thể; Lược đồ chữ ký số; Lược đồ chữ ký số tập thể. 1. ĐẶT VẤN ĐỀ Trong [1] nhóm tác giả đã đề xuất một mô hình ứng dụng chữ k ý số nhằm bảo đảm các yêu cầu chứng thực về nguồn gốc và tính toàn vẹn cho các thông điệp dữ liệu trong các giao dịch điện tử, mà ở đó các thực thể ký là thành viên hay bộ phận của các tổ chức có tư cách pháp nhân trong xã hội. Trong mô hình này, các thông điệp điện tử sẽ được chứng thực ở hai cấp độ khác nhau: thực thể tạo ra nó và tổ chức mà thực thể tạo ra nó là một thành viên hay bộ phận của tổ chức này. Ở đây, thực thể ký là một hay một nhóm thành viên của một tổ chức và được phép ký lên các thông điệp dữ liệu với danh nghĩa thành viên của tổ chức này. Cũng trong mô hình này, CA là bộ phận có chức năng bảo đảm các dịch vụ chứng thực số, như: chứng nhận một thực thể là thành viên của tổ chức, chứng thực các thông điệp dữ liệu được ký bởi các thực thể là thành viên trong một tổ chức, mà CA là cơ quan chứng thực thuộc tổ chức này. Tính hợp lệ về nguồn gốc và tính toàn vẹn của một thông điệp dữ liệu ở cấp độ của một tổ chức chỉ có giá trị khi nó đã được CA thuộc tổ chức này chứng thực, việc chứng thực được thực hiện bằng chữ ký của CA tương tự như việc CA chứng thực khóa công khai cho các thực thể cuối trong các mô hình PKI [2] truyền thống. Trong mô hình này, chữ ký của CA cùng với chữ ký cá nhân của các thực thể ký hình thành nên chữ ký tập thể cho một thông điệp dữ liệu. Nói cách khác, chữ ký tập thể trong mô hình này bao hàm chữ ký với tư cách cá nhân của thực thể ký và chữ ký của CA với tư cách của tổ chức mà đối tượng ký là thành viên thuộc tổ chức này. Ở đây, mô hình ứng dụng chữ ký số với các yêu cầu đặt ra như trên được gọi là mô hình chữ ký số tập thể (Collective Signature Model). Trong bài báo này, nhóm tác giả tiếp tục đề xuất một lược đồ chữ ký số theo mô hình chữ ký số tập thể được xây dựng dựa trên tính khó của việc giải bài toán phân tích một số nguyên lớn ra các thừa số nguyên tố (bài toán phân tích số) và bài toán khai căn trên Zn (bài toán khai căn). 2. XÂY DỰNG LƯỢC ĐỒ CHỮ KÝ SỐ TẬP THỂ 2.1. Các bài toán cơ sở 2.1.1. Bài toán phân tích số Bài toán phân tích số được phát biểu như sau: Cho số Nn , hãy tìm biểu diễn: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 43 ki e k e i ee ppppn ....... 21 21 , với: 1ie và pi là các số nguyên tố. Một trường hợp riêng của bài toán phân tích số được ứng dụng để xây dựng hệ mật RSA [3] mà ở đó n là tích của 2 số nguyên tố p và q. Khi đó, bài toán phân tích số hay còn gọi là bài toán IFP(n) được phát biểu như sau: Bài toán IFP(n): Với mỗi số nguyên dương n, hãy tìm số nguyên tố p hoặc q thỏa mãn phương trình sau: nqp  Giải thuật cho bài toán IFP(n) có thể được viết như một thuật toán tính hàm IFP(.) với biến đầu vào là n, còn giá trị hàm là p hoặc q của phương trình sau:  nIFPp  hoặc:  nIFPq  Trong hệ mật RSA, bài toán phân tích số được sử dụng trong việc hình thành cặp khóa công khai/bí mật cho mỗi thực thể ký. Với việc giữ bí mật các tham số (p, q) thì việc tính được khóa bí mật (d) từ khóa công khai (e) và modulo n là một bài toán khó nếu p, q được chọn đủ lớn và mạnh. Hiện tại, IFP(n) vẫn được coi là bài toán khó do chưa có giải thuật thời gian đa thức cho bài toán này và hệ mật RSA là một minh chứng thực tế cho tính khó giải của bài toán này. 2.1.2. Bài toán khai căn trên Zn Cho cặp số nguyên dương (n,e) với n là tích 2 số nguyên tố p và q sao cho bài toán phân tích số là khó giải trên Zn, còn e là một giá trị thỏa mãn: )(1 ne  và: 1))(,gcd( ne  , ở đây: )1()1()(  qpn . Khi đó, bài toán khai căn trên Zn hay còn gọi là RSAP(n,e) được phát biểu như sau: Bài toán RSAP(n,e): Với mỗi số nguyên dương  nZy , hãy tìm x thỏa mãn phương trình sau: ynxe mod Giải thuật cho bài toán RSAP(n,e) có thể được viết như một thuật toán tính hàm RSAP(n,e)(.) với biến đầu vào là y, còn giá trị hàm là x của phương trình sau:  yRSAPx en ),( Bài toán RSAP(n,e) cũng là cơ sở để xây dựng nên hệ mật RSA. Ở hệ mật RSA nếu giải được RSAP(n,e), kẻ thám mã có thể tìm được bản rõ (M) từ bản mã (C) và các tham số công khai (n,e), hoặc dễ dàng tạo được chữ ký giả mạo (S) cho một bản tin bất kỳ (M) mà không cần biết khóa bí mật (d) của đối tượng ký (bị mạo danh). Tuy nhiên, hiện tại việc tấn công hệ mật RSA bằng việc giải RSAP(n,e) là vẫn chưa khả thi. 2.2. Lược đồ cơ sở Lược đồ mới đề xuất ở đây được phát triển dựa trên tính khó của việc giải hai bài toán phân tích số và bài toán khai căn trên Zn. Lược đồ mới đề xuất bao gồm: các thuật toán hình thành tham số và khóa, thuật toán ký và kiểm tra chữ ký như sau: 2.2.1. Thuật toán hình thành tham số và khóa Mỗi đối tượng ký trong hệ thống hình thành các tham số và khóa theo các bước như sau: Công nghệ thông tin P. V. Hiệp, V. S. Hà, L. H. Dũng, “Một lược đồ chữ ký tập thể khai căn trên Zn.” 44 Thuật toán 1.1: Hình thành tham số và khóa. Input: lp, lq – độ dài (tính theo bit) của số nguyên tố p, q. Output: n, t, y, x1, x2. [1]. Chọn 1 cặp số p, q nguyên tố với: len(p) = lp, len(q) = lq sao cho bài toán phân tích số trên Zn là khó giải. [2]. Tính: qpn  và: )1()1()(  qpn [3]. Chọn t thỏa mãn: 1),gcd( nt [4]. Chọn khóa bí mật thứ nhất x1 trong khoảng (1, n) và: 1),gcd( 1 nx [5]. Tính khóa công khai theo:   nxy t mod1   Kiểm tra nếu: )(ny  hoặc: 1))(,gcd( ny  thì thực hiện lại từ bước [3] [6]. Tính khóa bí mật thứ hai theo: )(mod12 nyx   [7]. Chọn hash function H:   hZ  1,0 , với: h < n Chú thích: + len(.) là hàm tính độ dài (theo bit) của một số. + Khóa công khai là y, khóa bí mật là (x1, x2). + Các tham số công khai là n, t; các tham số bí mật là: p, q và φ(n). Chú ý: + Trong các ứng dụng thực tế, tham số p và q có thể chọn theo FIPS 186 - 4 [4] của Hoa Kỳ cho hệ mật RSA với các kích thước như 512 và 1024 bit. + Hàm băm H(.) có thể chọn theo FIPS 180 - 4 [5] như: SHA - 1, SHA - 256, SHA - 512, với các kích thước dữ liệu đầu ra tương ứng là: 160 bit, 256 bit, 512 bit, 2.2.2. Thuật toán ký Thuật toán 1.2: Sinh chữ ký. Input: n, t, x1, x2, M – bản tin cần ký. Output: (E,S) – chữ ký. [1]. Chọn ngẫu nhiên giá trị k trong khoảng (1, n) [2]. Tính giá trị:   nkR t mod [3]. Tính thành phần thứ nhất của chữ ký theo: )||( RMHE  [4]. Tính thành phần thứ 2 của chữ ký theo:    nxkS xE mod21 Chú thích: + Toán tử “||” là phép nối 2 xâu bit. 2.2.3. Thuật toán kiểm tra Thuật toán 1.3: Kiểm tra chữ ký. Input: n, g, y, M – bản tin cần thẩm tra. Output: (E,S) = true/false. [1]. Tính giá trị:   nSS y mod [2]. Tính giá trị:     nySR Et mod [2]. Tính giá trị: )||( RMHE  [3]. Nếu: EE  thì: (E,S) = true, ngược lại: (E,S) = false Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 45 Chú thích: + (E,S) = true: chữ ký hợp lệ, bản tin M được xác thực về nguồn gốc và tính toàn vẹn. + (E,S) = false: chữ ký hoặc/và bản tin bị giả mạo. 2.2.4. Tính đúng đắn của lược đồ cơ sở Với các tham số và khóa được hình thành bởi Thuật toán 1.1, chữ k ý (E,S) được sinh bởi Thuật toán 1.2, giá trị E được tạo bởi Thuật toán 1.3 thì điều cần chứng minh ở đây là: EE  . Thật vậy, do:                                   Rnk nxxknxnxk nxnxk nnxnnxk nynSnySR t EtEttEttE Et tyxE Et tyxE EtyEt               mod modmodmod modmod modmodmodmod modmodmod . 1 . 1 . 11 . 1 . 1 11 2 2 Từ đây, suy ra điều cần chứng minh: ERMHRMHE  )||()||( 2.2.5. Mức độ an toàn của lược đồ cơ sở a) Tấn công khóa bí mật Ở lược đồ cơ sở, khóa bí mật của một đối tượng ký là cặp (x1,x2), tính an toàn của lược đồ sẽ bị phá vỡ hoàn toàn khi cặp khóa này có thể tính được bởi một hay các đối tượng không mong muốn. Từ Thuật toán 1.1 cho thấy, để tìm được x2 cần phải tính được tham số φ(n), nghĩa là phải giải được bài toán phân tích số IFP(n), còn để tính được x1 cần phải giải được bài toán RSAP(n,e). Như vậy, độ an toàn về khóa của lược đồ cơ sở được quyết định bởi mức độ khó của việc giải các bài toán IFP(n) và RSAP(n,e). b) Tấn công giả mạo chữ ký Từ điều kiện của Thuật toán 1.3, một cặp (E,S) bất kỳ sẽ được coi là chữ ký hợp lệ của đối tượng sở hữu các tham số công khai (n,t,y) lên bản tin M nếu thỏa mãn:    nySMHE Ety mod|| .  Từ điều kiện trên cho thấy, nếu H(.) được chọn là hàm băm có độ an toàn cao (SHA 256/512,...) thì việc chọn ngẫu nhiên cặp (E,S) thỏa mãn điều kiện đã được chỉ ra là hoàn toàn không khả thi trong các ứng dụng thực tế. 2.2.6. Hiệu quả thực hiện của lược đồ cơ sở Đánh giá sơ bộ về hiệu quả thực hiện của lược đồ cơ sở, có thể dựa trên một số phân tích so sánh với hiệu quả thực hiện của lược đồ chữ ký RSA khi lựa chọn cùng bộ tham số như: - Chọn các tham số p, q với: |p| = |q| = 1024 bit, khi đó: |n| = |φ(n)| = 2048 bit, kích thước các khóa bí mật (x1, x2), khóa công khai y của lược đồ cơ sở và khóa bí mật d của lược đồ RSA: |x1| = |x2| = |y| = |d| = 2048 bit. - Chọn kích thước khóa công khai e của RSA và số mũ t của lược đồ cơ sở: |e| = |t| = 16 bit. Công nghệ thông tin P. V. Hiệp, V. S. Hà, L. H. Dũng, “Một lược đồ chữ ký tập thể khai căn trên Zn.” 46 - Chọn hàm băm SHA – 1 với kích thước dữ liệu ra 160 bit. Với các tham số như trên, thuật toán ký của lược đồ cơ sở cần thực hiện 3 phép lũy thừa: một phép lũy thừa với kích thước số mũ 16 bit (   nkR t mod ), phép lũy thừa thứ hai có kích thước số mũ 160 bit ( nx E mod1 ) và phép lũy thừa thứ 3 có kích thước 2048 bit ( naS x mod2 , với:   nxka E mod1 ), trong khi đó thuật toán ký của RSA chỉ thực hiện 1 phép tính lũy thừa duy nhất với kích thước số mũ 2048 bit ( nmS d mod ). Tuy phải thực hiện nhiều hơn 2 phép lũy thừa so với RSA, song do kích thước số mũ của 2 phép lũy thừa đầu khá nhỏ so với kích thước số mũ 2048 bit của phép lũy thừa thứ 3 trong lược đồ cơ sở cũng như kích thước số mũ của phép lũy thừa trong RSA, nên có thể coi tốc độ thực hiện thuật toán ký của lược đồ cơ sở và RSA là tương đương. Ở thuật toán kiểm tra, lược đồ cơ sở cũng phải thực hiện 3 phép lũy thừa có kích thước số mũ như ở thuật toán ký (16 bit, 160 bit và 2048 bit), còn RSA chỉ phải thực hiện 1 phép lũy thừa duy nhất với số mũ có kích thước 16 bit ( nS e mod ), vì vậy tốc độ thực hiện thuật toán kiểm tra của lược đồ cơ sở là khá chậm so với RSA. Đây chính là chi phí phải trả cho việc nâng cao độ an toàn của lược đồ cơ sở, khi mà độ an toàn của RSA sẽ bị phá vỡ hoàn toàn nếu kẻ tấn công chỉ cần giải được 1 trong 2 bài toán IFP(n) hoặc RSAP(n,e) , song muốn phá vỡ được độ an toàn của lược đồ cơ sở thì kẻ tấn công buộc phải giải được đồng thời cả 2 bài toán này. Ngoài ra, việc thực hiện các phép toán lũy thừa với kích thước số mũ 2048 bit hay 4096 bit như ở lược đồ RSA và lược đồ cơ sở là hoàn toàn khả thi trong các ứng dụng thực tế. 2.3. Lược đồ chữ ký tập thể Lược đồ chữ k ý tập thể ở đây được phát triển từ lược đồ cơ sở được đề xuất ở mục 2.2 với các chức năng như sau: - Hình thành chữ ký tập thể từ chữ ký cá nhân của một hay một nhóm đối tượng ký và chữ ký của CA. Kích thước của chữ k ý không phụ thuộc vào số lượng thành viên nhóm k ý. - Kiểm tra chữ ký tập thể của một nhóm đối tượng, được thực hiện tương tự như chữ ký do một đối tượng k ý tạo ra. Giả sử nhóm ký gồm N-thành viên: U = {Ui| i=1,2,...,N}. Các thành viên nhóm ký có khóa bí mật là: KS = {xi| i=1,2,...,N} và các khóa công khai tương ứng là: KP = {yi| i=1,2,...,N}. Còn CA có cặp khóa bí mật/công khai tương ứng là: {xca, yca}. 2.3.1. Thuật toán hình thành tham số và khóa của CA Thuật toán 2.1: Hình thành tham số hệ thống và khóa của CA. Input: lp, lq – độ dài (tính theo bit) của số nguyên tố p, q. Output: n, t, xca, yca. [1]. Chọn 1 cặp số p, q nguyên tố với: len(p) = lp, len(q)= lq sao cho bài toán phân tích số trên Zn =p.q là khó giải. [2]. Tính: qpn  và: )1()1()(  qpn [3]. Chọn t thỏa mãn: 1),gcd( nt [4]. Chọn khóa công khai yca trong khoảng (1, φ(n)) và gcd (yca , φ(n)) = 1 [5]. Tính khóa bí mật xca theo:   )(mod1 nyx caca    [6]. Chọn hash function H:   hZ  1,0 , với: h < n Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 47 2.3.2. Thuật toán hình thành khóa của các đối tượng k ý Thuật toán 2.2: Hình thành khóa của U = {Ui| i=1,2,.,N}. Input: n, t, KS = {xi| i = 1,2,,N}. Output: KP = {yi| i = 1, 2,..,N}. [1]. for i = 1 to N do [1.1].   nxy tii mod   [1.2]. ip yiK ][ [2]. return KP 2.3.3. Thuật toán hình thành chữ k ý Thuật toán 2.3: Hình thành chữ ký tập thể. Input: n, t, M, KS = {xi| i = 1, 2,..,N}, KP = {yi| i = 1, 2,..,N}. Output: (E,S) – chữ k ý của U lên M. [1]. for i = 1 to N do [1.1]. )||( MxHk ii  [1.2].   nkR tii mod [1.3]. send Ri to CA [2]. R ← 1; for i = 1 to N do nRRR i mod [3]. )||( RMHE  , send E to {U1, U2,...., Ui,..., UN}; [4]. for i = 1 to N do [4.1].    nxkS Eiii mod [4.2]. send Si to CA [5]. Su ← 1; for i = 1 to N do [5.1]. if (     nysr Ei t ii mod ) then {return (0,0)} [5.2].   nSSS iuu mod [6].   nSS caxu mod [7]. return (E,S) Chú thích: + Các bước [1], [4] được thực hiện bởi các đối tượng ký. + Các bước [2], [3], [5], [6] và [7] được thực hiện bởi CA. 2.3.4. Thuật toán kiểm tra chữ k ý Thuật toán 2.4: Kiểm tra chữ ký tập thể Input: n, t, yca, KP = {yi| i =1,2,..,N}, M, (E,S). Output: (E,S) = true / false. [1]. if ( E = 0 or S = 0) then {return false} [2]. y ← 1; for i = 1 to N do pyyy i mod [3]. nSu cay mod [3].   nyuv Et mod [4]. )||( vMHE  [5]. if ( EE  ) then {return true} else {return false} Công nghệ thông tin P. V. Hiệp, V. S. Hà, L. H. Dũng, “Một lược đồ chữ ký tập thể khai căn trên Zn.” 48 2.3.5. Tính đúng đắn của lược đồ chữ k ý tập thể Với các tham số và khóa được hình thành bởi Thuật toán 2.1 và 2.2, chữ k ý tập thể (E,S) được sinh bởi Thuật toán 2.3 và giá trị E được tạo bởi Thuật toán 2.4 thì điều cần chứng minh ở đây là EE  . Thật vậy, theo các Thuật toán 2.1, 2.2 và 2.3 ta có: nyy N i i mod 1    , nRR N i i mod và: nSS N i iu mod Nên:        . 1 mod mod mod mod mod ca ca ca ca ca yy x u N x y u u i i u S n S n n S n S S n       Do đó:                            RnnRnnk nknxxk nnxnxnk nnnxnnxk nnynSnySnyuv N i i N i t i N i t i N i N i Et i Et i N i t i EN i t i tN i E i tN i i EN i t i tN i E ii EN i i tN i i Et u Et                                                                              modmodmodmod modmod modmodmodmod modmodmodmodmod modmodmodmodmod 11 11 1 .. 1 111 11 11 Từ đây suy ra điều cần chứng minh: ERMHvMHE  )||()||( 2.3.6. Tính an toàn của lược đồ chữ k ý tập thể Mức độ an toàn của lược đồ chữ k ý tập thể ở đây được thiết lập dựa trên mức độ an toàn của lược đồ cơ sở đã đề xuất ở mục 2.1. Do vậy, về cơ bản mức độ an toàn của nó cũng được quyết định bởi mức độ khó của bài toán IFP(n) và RSAP(n,e). Tuy nhiên, thuật toán hình thành chữ ký ở lược đồ ký tập thể có điểm khác cơ bản với lược đồ cơ sở đó là thành phần R và Su được tạo ra từ nhiều cặp giá trị (Ri, Si) của các thành viên nhóm ký, mà không phải từ 1 cặp giá trị (R,S) duy nhất như lược đồ cơ sở. Nói cách khác, chữ ký tập thể ở đây được tạo ra từ nhiều chữ ký cá nhân của các thành viên, vì thế tấn công giả mạo chữ ký cá nhân của các đối tượng ký trong thủ tục hình thành chữ ký tập thể sẽ là một nguy cơ mất an toàn tiềm ẩn đối với lược đồ chữ ký tập thể mới đề xuất. Vấn đề này hoàn toàn có thể giải quyết bằng việc CA xác thực chữ ký cá nhân của các thành viên nhóm ký ở bước [5.1] trong Thuật toán 2.3. Song đây chỉ là một trong các nguy cơ tấn công giả mạo đối với lược đồ mới đề xuất, mà quá trình phát triển tiếp theo và ứng dụng vào thực tế sẽ cần phải được tiếp tục phát hiện và giải quyết. 3. KẾT LUẬN Bài báo đề xuất một lược đồ chữ k ý số tập thể có thể áp dụng cho đối tượng là các cơ quan, đơn vị, doanh nghiệp,... nhằm đảm bảo cho việc chứng thực các Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 04 - 2019 49 thông điệp dữ liệu trong các thủ tục hành chính điện tử hoàn toàn phù hợp với các thủ tục hành chính trong thực tế xã hội. Với lược đồ mới đề xuất, các thông điệp dữ liệu điện tử sẽ được chứng thực về nguồn gốc và tính toàn vẹn ở hai cấp độ khác nhau: thực thể tạo ra thông điệp dữ liệu cần chứng thực và tổ chức mà thực thể tạo ra nó là một thành viên hay bộ phận của tổ chức này. Lược đồ mới đề xuất ở đây được phát triển từ một dạng lược đồ chữ ký mới xây dựng dựa trên tính khó của việc giải hai bài toán phân tích số và khai căn trên Zn. Vì thế, tính an toàn của lược đồ về khía cạnh tấn công giả mạo là một vấn đề cần được chú ý nghiên cứu trong quá trình phát triển và ứng dụng tiếp theo. TÀI LIỆU THAM KHẢO [1]. Phạm Văn Hiệp, Lưu Hồng Dũng, “Chữ ký số - Mô hình ứng dụng và thuật toán”, Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng CNTT (FAIR 11), Hà Nội 9/8/2018. [2]. Adams C., Understanding Public Key Infrastructures, New Riders Publishing, Indianapolis, 1999. [3]. Rivest R., Shamir A., Adleman L. (1978), “A Method for Obtaining Digital Signatures and Public Key Cryptosystems”, Communications of the ACM, Vol. 21, No. 2, pp. 120 – 126. [4]. National Institute of Standards and Technology, NIST FIPS PUB 186 – 4. Digital Signature Standard, U.S. Department of Commerce, 2013. [5]. National Institute of Standards and Technology, NIST FIPS PUB 180 – 4. Secure Hash Standard (SHS), U.S. Department of Commerce, 2015. ABSTRACT A COLLECTIVE DIGITAL SIGNATURE SCHEMES BASED ON THE DIFFICULTY OF INTEGER FACTORIZATION AND FINDING ROOT PROBLEMS ON THE Zn This paper proposes a collective digital signature schemes application for government agencies, administrative units, enterprises, etc., where data messages need to be authenticated. Origin and integrity at two levels: entity sign and organization (agency, unit, ...) that the entity signing is its member. At the same time, the paper also suggests digital signature schemes based on this application model. The proposed new scheme was developed from a digital signature scheme formulated based on the difficulty of integer factorization and finding root problems based on ring Zn. Keywords: Digital Signature; Collective Signature; Digital Signature Schemes; Collective Digital Signature Schemes. Nhận bài ngày 11 tháng 12 năm 2018 Hoàn thiện ngày 12 tháng 3 năm 2019 Chấp nhận đăng ngày 25 tháng 3 năm 2019 Địa chỉ: 1 ĐH Công Nghiệp Hà Nội; 2 Viện KHCNQS; 3 Học viện Kỹ thuật Quân sự; 4 Trung tâm tin học, Trường Đại học Nội vụ Hà Nội. * Email: hieppv@haui.edu.vn.