Giải pháp nâng cao độ an toàn cho lược đồ chữ kí số có độ an toàn dựa trên bài toán logarit rời rạc trong vành hữu hạn Zn

Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 90 GIẢI PHÁP NÂNG CAO ĐỘ AN TOÀN CHO LƯỢC ĐỒ CHỮ KÍ SỐ CÓ ĐỘ AN TOÀN DỰA TRÊN BÀI TOÁN LOGARIT RỜI RẠC TRONG VÀNH HỮU HẠN Lê Văn Tuấn1*, Lều Đức Tân2 Tóm tắt: Bài báo này đã đề xuất giải pháp nâng cao độ an toàn cho lược đồ chữ kí số trên vành hữu hạn . Dựa trên giải pháp đê xuất, tác giả đề xuất một lược đồ chữ kí số mới có độ an toàn dựa trên bài toán logarit rời rạc trên vành . Hơn nữa, dựa trên cách xây dựng ngưỡng an toàn của Arjen K. Lenstra and Eric R. Verheul, tác giả đã xây dựng công thức tính ngưỡng an toàn và hệ tiêu chuẩn tham số an toàn cho lược đồ đề xuất. Lược đồ chữ kí đề xuất có độ an toàn cao hơn các lược đồ chữ kí số Elgamal cùng các biến thể của nó và có thể áp dụng trong Quốc phòng - An ninh. Từ khóa: Chữ kí số; Logarit rời rạc; Ngưỡng an toàn. 1. MỞ ĐẦU Vào năm 1985, Elgamal đã đề xuất lược đồ chữ kí số có độ an toàn dựa trên tính khó giải của bài toàn logarít rời rạc trên trường (còn gọi là lược đồ chữ kí số trên trường , kí hiệu là ). Kể từ khi lược đồ ElGamal [8], [9] ra đời, đã có nhiều lược đồ chữ kí số biến thể được đề xuất bởi các nhà khoa học trên thế giới, chẳng hạn như: lược đồ chữ kí số Schnorr năm 1990 [10], lược đồ chữ kí số DSA năm 1994 [11] Nhìn chung, các lược đồ chữ kí số trên trường hữu hạn không an toàn trong những tình huống lộ khóa phiên hoặc trùng khóa phiên, mà nguyên nhân là do các lược đồ này đã công khai bậc của phần tử sinh, điều này được chỉ ra trong các kết quả nghiên cứu liên quan [12], [13], [14], [15], [16]. Để khắc phục những điểm tồn tại đã chỉ ra trong lược đồ chữ kí số Elgamal và biến thể của nó các nhà khoa học trong nước [1], [2], [3], [17] và trên thế giới nghiên cứu [18], [19], phát triển các lược đồ chữ kí số trên vành hữu hạn Z, bởi một số lí do sau: Thứ nhất, trên vành hữu hạn Z mới có thể che giấu được bậc của phẩn tử sinh [3]. Chúng ta biết rằng tập Z cùng với phép cộng và phép nhân theo modul n tạo nên một vành hữu hạn Z, trong đó n được cấu tạo từ hai đến 3 số nguyên tố (thông thường n=p.q, trong đó p, q là các số nguyên tố phân biệt). Trường hợp n = p. q thì nhóm nhân Z ∗ sẽ là nhóm có bậc lớn nhất là (p − 1). (q − 1) và việc tìm giá trị này được cho là khó khi không biết phân tích của n, tức là bậc của các nhóm con của nhóm nhân Z ∗ có thể giữ được bí mật khi không biết phân tích của n. Thứ hai, bài toán logarít rời rạc trên vành Z (n = p. q, trong đó: p, q là các số nguyên tố phân biệt) được cho là khó hơn bài toàn logarít rời rạc trên trường Z[3], bởi vì để giải nó thì phải giải đồng thời ba bài toán, đó là: bài toán phân tích số n = p. q, bài toán DLP và DLP Thứ ba, cho đến nay, ngoài thuật toán Baby step- giant step của Danied Shank có thể ứng dụng đề giải bài toán logarít rời rạc trên vành Z[6] thì các thuật toán khác chẳng hạn như: thuật toán Rho của Pollard, thuật toán Pohlig-Hellman, chỉ áp dụng để giải bài toán logarít rời rạc trên trường hữu hạn Z Chính vì thế lược đồ chữ kí số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành sẽ an toàn hơn các lược đồ chữ kí số trên trường hữu hạn và đang được nghiên cứu, đề xuất bởi các nhà khoa học trong nước như: Pham Van Hiep, Nguyen Huu Mong, Luu Hong Dung [1] vào năm 2018; Vũ Long Vân, Hồ Ngọc Duy, Nguyễn Kim Tuấn, Nguyễn Thị Thu Thủy [3] vào năm 2017. Bên cạnh đó là các lược đồ của 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ố 57, 10 - 2018 91 nhà khoa học trên thế giới. Tiêu biểu là lược đồ S. K. Tripathi và B. Gupta[18] vào năm 2017; Chik How Tan [19] vào năm 2003; Chúng ta biết rằng trong thực hành, một lược đồ chữ kí số từ khâu thiết kế đến khi đưa vào sử dụng được ban hành theo một chuẩn nào đó cần phải trải qua 3 công đoạn, công đoạn thứ nhất là xây dựng sơ đồ chữ kí nguyên thủy với với tập thông báo đầu vào là {0,1} và phải chứng minh được độ an toàn của nó dựa trên một bài toán khó giải nào đó theo nghĩa việc giả mạo chữ kí phải đối mặt với bài toán khó đó; công đoạn thứ hai, phải xác định ngưỡng an toàn (_ℎ) cho lược đồ chữ kí số dựa trên quan điểm kẻ tấn công “không thể đầu tư”, tức là kẻ tấn công muốn phá vỡ hệ chữ kí thì phải tính toán một khối lượng 2_ phép toán, đây là con số mà kẻ tấn công không có khả năng để thực hiện. Dựa trên ngưỡng an toàn để xây dựng hệ tiêu chuẩn cho các tham số để khi sử dụng các tham số này cho sơ đồ chữ kí, để giả mạo kẻ tấn công phải có chi phí tính toán không dưới 2_ phép tính; công đoạn thứ ba, phải xây lược đồ chữ kí ở dạng ứng dụng và chứng minh an toàn trước các mô hình tấn công khác nhau. Qua nghiên cứu, khảo sát các lược đồ chữ kí số trên vành của các nhà khoa học trong nước [1], [2], [3], [17] và trên thế giới [18], [19], cho thấy các nhà khoa học mới dừng lại ở công đoạn thứ nhất, tức là họ mới đề xuất các lược đồ chữ kí ở dạng nguyên thủy và chứng minh độ an toàn của nó được dựa trên một bài toán cho là khó (bài toán phân tích số, bài toán logarit rời rạc, bài toán khai căn theo modul). Như vậy là chưa đủ bởi các bài toán khó (các bài toán phân tích số, bài toán logarit rời rạc hay bài toán khai căn theo modul) về lí thuyết là khó giải tuy nhiên trên thực tế nó không phải luôn khó giải. Ví dụ phân tích số n thành tích của số nguyên tố p nhân với số nguyên tố q được coi là bài toán khó, tuy nhiên, nếu p=2, q=3 thì việc phân tích n=p.q là không khó, hoặc p là số nguyên tố có 20 chữ số thập phân, trong khí đó số nguyên tố q có độ lớn khoảng 1000 chữ số thập phân thì việc phân tích n=p.q cũng không khó. Vấn để đặt ra phải chọn n thỏa mãn điều kiện khi phân tích n=p.q dựa trên một thuật toán tốt nhất (thuật toán NFS là tốt nhất cho đến thời điểm hiện tại) vẫn phải là khó với khả năng tính toán của máy tính đến một thời điểm nào đó trong tương lai và khi đó thì giá trị của p và q đồng thời phải thỏa mãn một số điều kiện nào đó chẳng hạn như giá trị của nó phải lớn hơn một giá trị ngưỡng nào đó hoặc ± 1 phải có ước nguyên tố thỏa mãn một điều kiện nào đó. Vậy là xác định được ngưỡng an toàn và hệ tiêu chuẩn tham số an toàn cho lược đồ chữ kí là bước không thể thiếu trước khi đưa lược đồ chữ kí số vào ứng dụng thực tế. Hơn nữa, một số lược đồ chữ kí mà bậc của phân tử sinh chưa tường minh, miền giá trị lớn hơn mức cần thiết vừa chi phí tính toán lớn, vừa tốn bộ nhớ mà chưa chắc đã an toàn [18], [19]. Một số lược đồ có bậc của phần tử sinh đuợc cấu tạo bởi các số nguyên tố siêu mạnh mà việc sinh các số nguyên tố này rất khó khăn [18]. Dựa trên những điểm còn tồn tại trên các lược đồ chữ kí số trên vành , nhóm tác giả đã đề xuất giải pháp nhằm nâng cao độ an toàn cho lược đồ chữ kí số trên vành Z với nội dung cơ bản của giải pháp được trình bày trong mục ba và mục bốn của bài báo. Phần còn lại của bài báo được kết cấu gồm: phần hai, nội dung trình bày một số công việc liên quan. Phần ba, nội dung giải pháp. Phần bốn, trình bày một số kết quả thử nghiệm về sinh tham số theo hệ tiêu chuẩn, sinh chữ kí và xác nhận chữ kí. 2. MỘT SỐ KIẾN THỨC LIÊN QUAN 2.1. Định nghĩa 1. Hàm H: {0,1} →: {0,1} chuyển một xâu có độ dài hữu hạn bất kỳ thành xâu có độ dài 512 bít 2.2. Định nghĩa 2. Hàm Num() đổi một xâu nhị phân thành số nguyên không quá T bít, kí hiệu Num: : {, } → . Ứng cặp (, . . . ) thành số = + 2 +. . . +2 (,)(,)) Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 92 2.3. Định nghĩa 3. Hàm Str() có chức năng đổi số nguyên không âm a thành xâu nhị phân. Kí hiệu Str: ℤ0→: {, } . Giả sử ứng với số nguyên không âm a, = + 2. +. . . +2 thì () =, . . . 2.4. Định nghĩa 4. Hàm (): Hàm lấy ngẫu nhiên một phần tử thuộc tập , giả sử phần tử đó là k, ta kí hiệu ∈ 2.5. Vành : Chúng ta biết rằng tập cùng với phép cộng và phép nhân theo modul n tạo nên một vành hữu hạn , trong đó n được cấu tạo từ hai đến 3 số nguyên tố trở lên (thông thường n=p.q, trong đó p, q là các số nguyên tố phân biệt). Khi đó tập ℤ ∗ = {1 ≤ < |(, ) = 1} là nhóm nhân. 2.6. Một số bài toán liên quan 2.6.1. Bài toán phân tích số, kí hiệu FP (Factorization Problem): Cho n là một số tự nhiên. Hãy tìm biểu diễn của n ở dạng sau: = ∏ (1) trong đó, p là các số nguyên tố khác nhau, gọi là bài toán phân tích số 2.6.2. Một số bài toán trên vành a. Bài toán khai căn theo modul: Cho vành , với a ∈ ℤ ∗ và e là một số tự nhiên. Cho phương trình đại số sau: = (2) - Bài toán căn bậc e của a: là tìm ∈ ℤ ∗ thỏa mãn phương trình (2). - Bài toán RSA: Giải phương trình (2) trong trường hợp (, ()) = 1, gọi là bài toán , kí hiệu (Rivert, Shamir, Adleman Problem). - Bài toán khai căn bậc hai: Giải phương trình (2) trong trường hợp = 2, gọi là bài toán căn cấp hai, kí hiệu (Square Roots Problem). b. Bài toán logarít rời rạc: Cho ≠ 1, ∈ ℤ ∗ . Phương trình mũ như sau: = . (3) - Hãy tìm số tự nhiên x là nghiệm của (3) là bài toán logarít rời rạc cơ số g của a theo modul n hay còn gọi là bài toán logarít rời rạc trên vành , kí hiệu - Giải phương trình (3) để tìm x nhỏ nhất trong trường hợp = 1 được gọi là bài toán tìm cấp của g, kí hiệu (Order Problem). 2.7. Ngưỡng an toàn: Ngưỡng an toàn của hệ mật, kí hiệu là security_strength là giá trị mà muốn phá vỡ hệ mật phải thực hiện ít nhất là 2_ phép tính cơ bản. 2.8. Các số nguyên tố bổ trợ: Cho n=p.q trong đó p, q là các số nguyên tố : ước nguyên tố của − 1 : ước nguyên tố của + 1 : ước nguyên tố của − 1 : ước nguyên tố của + 1 2.9. Một số kết quả đánh giá độ phức tạp tính toán Cho , là các số nguyên dương. Giả sử n là một số có độ lớn L bít và 0≤ , ≤ − 1, khi đó : - Phép toán ± có độ phức tạp (). - Phép toán a.b có độ phức tạp là () ≈ (,), ký hiệu là - Độ phức tạp của phép lũy thừa là (). ≈ . trong đó là số bít của . - (, ) có độ phức tạp (. ) 3. GIẢI PHÁP ĐỀ XUẤT 3.1. Ý tưởng Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 93 Ý tưởng cơ bản của giải pháp là phát triển một lược đồ chữ kí số có độ an toàn dựa trên tính khó giải của bài toán logarit rời rạc trên vành , che giấu bậc của phẩn tử sinh[]. Chúng ta biết rằng tập Z cùng với phép cộng và phép nhân theo modul n tạo nên một vành hữu hạn Z, trong đó n được cấu tạo từ hai đến 3 số nguyên tố (thông thường n=p.q, trong đó p, q là các số nguyên tố phân biệt). Trường hợp n = p. q thì nhóm nhân Z ∗ sẽ là nhóm có bậc lớn nhất là (p − 1). (q − 1) và việc tìm giá trị này được cho là khó khi không biết phân tích của n, tức là bậc của các nhóm con của nhóm nhân Z ∗ có thể giữ được bí mật khi không biết phân tích của n. Khi đó, các kiểu tấn công giả mạo chữ kí dựa trên khóa phiên hoặc khóa bí mật đều phải đối mặt với bài toán logarít rời rạc trên vành Z(DLP;), nó được cho là khó hơn bài toàn logarít rời rạc trên trường Z, bởi vì để giải nó thì phải giải đồng thời ba bài toán, đó là: bài toán phân tích số n = p. q, bài toán DLP và DLP; cho đến nay, ngoài thuật toán Baby step- giant step của Danied Shank có thể ứng dụng đề giải bài toán logarít rời rạc trên vành Z[6] thì các thuật toán khác chẳng hạn như: thuật toán Rho của Pollard, thuật toán Pohlig-Hellman, chỉ áp dụng để giải bài toán logarít rời rạc trên trường hữu hạn Z. Nội dung tiếp theo của giải pháp là dựa trên phương pháp xây dựng ngưỡng an toàn của Arjen K. Lenstra, Eric R. Verheul[22] nhóm tác giả đã xác định ngưỡng an toàn và xây dựng được hệ tiêu chuẩn tham số an toàn cho lược đồ cho những năm y≥ 2018 trong lĩnh vực kinh tế - xã hội (KT-XH) và trong Quốc phòng-An ninh (QP-AN). 3.2. Đề xuất lược đồ chữ kí số mới trên vành Lược đồ mới đề xuất ở đây được phát triển trên cơ sở kết quả nghiên cứu trong [2], [17]. Tuy nhiên, điểm khác biệt trong lược đồ đề xuất so với các lược đồ trong [2] là trong lược đồ đề xuất, thành phần nghịch đảo trong modul n của khóa bí mật x trong công thức tính thành phần thứ hai được tính trước, nên giảm đáng kể thời gian sinh chữ kí. Dựa trên kết quả nghiên cứu trong [2], [3], [17], nhóm tác giả xây dựng miền tham số của lược đồ đề xuất như sau: 3.2.1. Miền tham số - Tham số = . với , là các số nguyên tố lớn thỏa mãn việc phân tích n ra thừa số là khó. Giá trị t = . với , là các nguyên tố thỏa mãn điều kiện sau: |( -1), |( -1), ∤ ( -1), ∤ ( -1). Giá trị và hai giá trị , được giữ bí mật; - Giá trị là độ dài bít của t, kí hiệu = (). - Giá trị g là phần tử sinh của nhóm có cấp t trong modul n. Tham số và được chọn sao cho bài toán tìm x từ phương trình = là bài toán khó. - Giá trị là khóa riêng phải được giữ bí mật; x được chọn ngẫu nhiên trong đoạn [1, -1] sao cho tồn tại theo modul t - Giá trị là khóa công khai, với = . - Giá trị k được chọn ngẫu nhiên trong đoạn [1, -1] là số bí mật tương ứng duy nhất cho mỗi thông báo (còn được gọi là khóa phiên). - Bộ giá trị (, , , ) làm khóa bí mật và (, , , ) làm khóa công khai. 3.2.2. Sinh chữ kí và xác nhận chữ kí a. Thuật toán 1: Sinh chữ kí Input: (n, t, g, x), , T ∈ {0,1}∗. Output: (r,s). 1. k ∈ (1, t). 2. r ¬ g mod n. 3. z ¬ Num(N,H(T||Str(r))) Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 94 4. s ¬x(k − z)mod t. 5. if ( = 0) (|) (|) (|) then goto 1. 6. return (r, s). b. Thuật toán 2: Xác nhận chữ kí Input: Thông báo T và chữ kí (r, s), khóa công khai (n, N, g, y). Output: "accept" hoặc "reject". 1. z ¬Num(N, H(T||Str(r))). 2. u ¬g. y mod n 3. if (r = u) return "accept" else return "reject". Bắt đầu t = p1.q1, ordn(g)= t N= Len(t) x= random(t), tồn tại x-1 trong Zt, y = g x mod t Kết thúc (n, g, x, t) is secret key (n, g, y, N) is public key; Sinh tham số r = gk mod n. z = number(N, H(T||str(r))) s = x-1 (k-z) mod t z = number(N, H(T||str(r))) u=(gz.ys) mod n. u=r Xác nhận chữ kí Sinh chữ kí Accept Reject k= Random(1,t) S=0 or p1|k or q1|k or q1|k or t|r F T T F Sinh số n tố p, q, p1, q1; p1|(p-1), q1|q-1, p1∤ (q-1), q1∤ (p-1); Gửi(r,s,T) tới nơi nhận Hình 1. Lưu đồ thuật toán lược đồ chữ kí . Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 95 c. Tính đúng đắn của thuật toán Ta có = . = . = . = = . 3.2.3. Mức độ an toàn của lược đồ đề xuất a.Tấn công khóa bí mật: Ở lược đồ mới đề xuất, khóa bí mật của một đối tượng ký là cặp (t,x), tính an toàn của lược đồ sẽ bị phá vỡ khi cặp khóa này có thể tính được bởi kẻ tấn công. Để tính được khóa bí mật x, kẻ tấn công phải giải được bài toán logarit rời rạc trên vành , để tính được t (t là bậc của phần tử sinh), kẻ tấn công phải giải bài toán tìm bậc của phần tử sinh trong vành . Bài toán DLPvà bài toán tìm bậc của phần tử sinh trong là hai bài toán khó nếu tham số của bài toán được chọn theo một hệ tiêu chuẩn an toàn. Khi tham số t được giữ bí mật, nếu tình huống trùng khóa phiên hoặc lộ khóa phiên xảy ra thì kẻ tấn công cũng khó có thể tính được khóa bí mật. Dưới đây, xét hai trường hợp trùng khóa phiên và lộ khóa phiên. - Trường hợp thứ nhất: Khóa phiên bị lộ, khi đó khóa bí mật x sẽ được xác định bởi công thức sau đây: s ¬.(k- z) mod t. → ¬ ( − ) . Do được giữ bí mật nên kẻ tấn công khó có thể xác định được và khóa bí mật . - Trường hợp thứ hai: Khóa phiên bị dùng trùng lặp, giả sử thông báo và ’ dùng cùng một khóa phiên, khi đó khóa bí mật sẽ được xác định bởi công thức sau: z ¬Num(N,H(T||str(r))) (4) ¬Num (N,H(T||str(r))) (5) s ¬. ( − ) (6) ¬. ( − ) (7) = ( − ). ( − ) (8) Do t được giữ bí mật nên không thể xác định được trong - Trường hợp thứ ba: Kẻ tấn công có được khóa bí mật , do được giữ bí mật nên không thể xác định được trong modul và vì thế cũng không xác định được thành phần và của chữ kí và chữ kí không thể giả mạo trong trường hợp có khóa bí mật . Vậy lược đồ chữ ký đề xuất an toàn với mô hình tấn công “Total Break” b. Tấn công giả mạo chữ kí - “Existential forgery”: Lược đồ chữ kí đề xuất an toàn với mô hình giả mạo “Existential forgery”, đây là kiểu giả mạo có tính mục đích yếu nhất bởi kẻ tấn công thường lấy ngẫu nhiên một chữ kí (r,s) sau đó tạo ra bản rõ T theo (r,s) đmả bảo thỏa mãn với phương trình xác nhận chữ kí và không cần quan tâm đến nội dung . Mục đích của tấn công giả mạo là tạo ra một chữ kí hợp lệ (r,s) cho thông báo T, khi đó kẻ tấn công phải tìm được cặp (r,s) thỏa mãn phương trình sau: r = (,(||( ))). (9) Từ (9) cho thấy, việc tìm cặp (r,s) bằng cách chọn trước r, tìm s đều khó hơn việc giải , hoặc là việc chọn trước s cũng không có cơ sở vì miền giá trị của nó thuộc khoảng (1,t) với t được giữ bí mật. Giả sử chọn ngẫu nhiên (r,s) rồi tính T theo (r,s) cũng không khả thi bởi hàm băm SHA 512 kháng xung đột yếu, kháng xung đột mạnh và kháng tiền ảnh, nên việc chọn ngẫu nhiên cặp (r,s) thỏa mãn (9) không khả thi với kẻ tấn công. Vây lược đồ đề xuất an toàn với kiểu tấn công giả mạo “Existential forgery”. - Selective forgery: Lược đồ đề xuất còn an toàn bởi tấn công giả mạo kiểu “Selective forgery”, kẻ tấn công không thể tạo ra chữ kí hợp lệ (r,s) cho một thông báo được lựa chọn từ trước, bởi vì tìm nghiệm của phương trình (9) phải đối mặt với giải bài toán khó. Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 96 3.2.4. Tính hiệu quả Tính hiệu quả của lược đồ đề xuất sẽ được phân tích trên hai mặt, đó là độ phức tạp của thuật toán và không gian lưu trữ. Để thuận tiện cho đánh giá độ phức tạp tính toán, trong bài báo sẽ sử dụng là độ phức tạp tính toán của phép nhân hai số trong modul n có () = và kí hiệu là độ phức tạp tính toán của phép nhân hai số trong modul t, () = bít và là độ phức tạp của công thức tính nghiệm theo định lí Phần dư Trung Hoa. a. Không gian lưu trữ: Giả sử trong hệ thống sử dụng lược đồ chữ kí số có thành viên. Đối với các lược đồ , , cả thành viên sử dụng chung một bộ tham số. Đối với các lược đồ chữ kí số của chúng tôi đề xuất, mỗi thành viên bắt buộc phải sử dụng một số modul riêng (tránh tấn công sử dụng modul chung), nên tham số hệ thống của các lược đồ chữ kí số này yêu cầu không gian lưu trữ gấp lần so với yêu cầu về không gian lữu trữ trong các lược đồ chữ kí , ̀. Hơn nữa, trong lược đồ chữ kí số , , thành phần r trong mỗi chữ kí là = () (bít) trong khi đó thành phần trong lược đồ đề xuất là L= len(n) (bít), vậy là giá trị r của lược đồ đề xuất lớn hơn lần thành phần r trong lược đồ , . b. Độ phức tạp tính toán: - Thuật toán 1: Độ phức tạp thuật toán 1 tập trung ở phép lũy thừa ¬ , do = . . Phép tính nghịch đảo được tính trước, nên ta có ước lượng sơ bộ thuật toán 1 như sau: ≈ . + 2. (10) Nếu phép toán ¬ được áp dụng định lí Phần dư Trung Hoa, thì độ phức tạp tính toán của nó là tổng của độ phức tạp các phép tính ¬ và ¬ và công thức tính nghiệm và khi đó độ phức tạp của thuật toán 1 sẽ thấp hơn so với (9) và kết quả ước lượng như sau: ≈ . + + 2. + (11) Trong đó thành phần là độ phức tạp của công thức tính nghiệm hệ phương trình đồng dư theo định lí Phần dư Trung Hoa. () = O(. (() p) + . (p q) ) n Trong đó: = = - Thuật toán 2: Độ phức tạp thuật toán 2 tập trung ở phép lũy thừa ¬. ; nên độ phức tạp của nó được ước lượng như sau: ≈ . + (12) Tuy nhiên, áp dụng định lí Phần dư Trung Hoa, công thức (11) có ước lượng chi phí tính toán như sau: ≈ . ( +) ++ (13) Tóm lại: Lược đồ chữ kí số do chúng tôi đề xuất sẽ yêu cầu không gian lưu trữ lớn hơn nhiều so với lược đồ chữ kí số Elgamal cùng các biến thể do mỗi thành viên trong hệ thống phải sử dụng số modul n riêng. Tuy nhiên, nhờ sự hỗ trợ của định lí phần dư Trung hoa mà độ phức tạp tính toán của các thuật toán kí và xác nhận chữ kí trong lược đồ đề xuất là thấp hơn so với thuật toán kí và xác nhận chữ kí trong lược đồ Elgamal cùng các biến thể. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 97 3.3. Ngưỡng an toàn Để lược đồ chữ kí có thể ứng dụng vào thực tiễn, điều kiện bắt buộc phải xác đinh ngưỡng an toàn cho lược đồ. Các lược đồ chữ kí số trên vành mà nhóm tác giả đã khảo sát [1], [2], [3], [17], [18], [19] đều thiếu bước này. Việc xác định ngưỡng và xây dựng hệ tiêu chuẩn tham số an toàn là đóng góp quan trọng nhất của bài báo. 3.3.1. Ngưỡng an toàn của Arjen K. Lenstra và Eric R. Verheul Theo Arjen K. Lenstra và Eric R. Verheul [22], ngưỡng an toàn đến năm y của một hệ mật được xác định thông qua 3 thành phần: Ngưỡng an toàn xuất phát, lấy năm 1982 làm thời điểm xuất phát; tốc độ phát triển đến năm y của năng lực máy tính; tiềm lực phát triển kinh tế đến năm y (mức đầu tư để gia tăng tốc độ tính toán của máy tính). Các giả thiết của [22] như sau: - Giả thiết 1: Ngưỡng an toàn tại năm 1982 là 0,5 MMY Theo giả thiết này, 1MMY = 103 x MY và MY là số phép toán thực hiện được trong 1 năm của một bộ vi xử lý có tốc độ 1 Mega flops (106 phép tính trên giây), như vậy: 1MY = 10631.536.000  244,84207 (14) Giả thiết này được đưa ra dựa trên cơ sở hệ mật DES được phép sử dụng cho đến năm 1982, tức là mã DES, độ dài khóa 56 bít (DES 64 bít nhưng chỉ 56 bit khóa) đã bị phá vỡ. Tuy nhiên, với phương pháp tấn công bằng phần cứng (sử dụng máy tính chuyên dụng với trị giá đầu tư là 50 triệu USD) thì DES bị phá trong vòng 2 ngày [22] tức là số phép tính thực hiện được trong một giấy của máy tính chuyên dụng này phải là 1012, vì thế Arjen K. Lenstra và Eric R. Verheul đã đưa ra ngưỡng an toàn tại năm 1982 (ký hiệu là IMY(1982)) là một con số gấp một triệu lần ngưỡng ở giả thiết 1, tức là: IMY(1982) = 106.0,5.MMY= 106.0,5.103.MY = 5.108.MY  273 (15) - Giả thiết 2: Một cách áp dụng được công nhận rộng rãi hiện nay là tốc độ tính toán của bộ vi xử lý được nhân đôi sau 18 tháng với giá thành không đổi. Giả thiết này là một biến thể của định luật Moore: “Số lượng transistor trên mỗi đơn vị inch vuông sẽ tăng lên gấp đôi sau 18 tháng với giá thành không đổi” [17]. Như vậy, cứ sau 10 năm, với cùng một giá thành thì tốc độ tính toán sẽ tăng lên là: 210x12/18 100 lần. - Giả thiết 3: Sức mạnh kinh tế của mỗi tổ chức cũng được tăng gấp đôi sau 10 năm. Giả thiết này được đưa ra từ việc mở rộng định luật Moore kết hợp với sự thay đổi về tiềm năng phát triển kinh tế. Ví dụ, tổng sản phẩm quốc nội Mỹ (US Gross National Product) năm 1975 là 1630 tỷ USD, năm 1985 là 4180 tỷ USD, năm 1995 là 7269 tỷ USD [1], [2], [17] năm 2005 là 12.332 tỷ, năm 2018 dự đoán trên 19.000 tỷ và năm 2020 là 22.900 tỷ USD. Kết hợp 3 giả thuyết 1, 2, 3 ở trên nếu năm 1982 số lượng phép tính không thể đầu tư là 0,5. MMY thì đến năm 1992 số lượng phép tính mà không thể đầu tư là 2.100.0,5.MMY= 102.MMY và 2002 là 2. 104.MMY. Dựa trên các giả thiết 1, 2 và 3 ta có công thức tính ngưỡng như sau: Ký kiệu IMY(y) là số các MY không thể thực hiện vào năm đó (chính là ngưỡng an toàn tại năm y tính theo đơn vị MY), () = (1982). 2 () . 2 () (16) = 2 () (17) - Giả thiết 4: Tiến bộ mã thám cũng tăng trưởng theo luật Moore, cụ thể là cứ sau 18 tháng thì việc phá vỡ hệ mật này sẽ giảm chi phí đi một nửa. Giả thuyết này được đưa ra Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 98 trên cơ sở hệ mã RSA có cỡ số modul = 512 bít được phân tích thành công với chi phí 10 ≈ 2, khoảng 2. 10 phép toán cơ bản. Về lí thuyết để tính chi phí phân tích số nguyên lớn, người ta ước lượng tiệm cận cho thuật toán sàng trường số[26] (NFS), kí hiệu là [2()], với () xác định như sau:   e.NN..NE 2log3 2 2lnlnln2ln921)(  (18) Và chi phí để phân tích một số nguyên lớn 512 bít là:   tbie...)E( 632log3 2 2lnln512ln2ln512921512  Arjen K. Lenstra và Eric R. Verheul đã đưa ra công thức về chi phí thực tế () để phá khóa công khai RSA với số modul n cỡ N bít, ký hiệu là [2] và chi phí lí thuyết ()để phá khóa công khai RSA với số modul n cỡ N bít, ký hiệu là [2]: [2] = [] [2] (19) Kết hợp với giả thiết 4 ta có chi phí thực tế () của việc phá các khóa − tại năm ≥ 1999, kí hiệu là [, 2] theo công thức sau: [, 2] = 2. ( . [, 2] (20) Vậy hệ RSA dùng an toàn cho đến năm y phải được xác định cỡ của số modul n, kí hiệu là N phải thỏa mãn điều kiện sau: [, 2] > () (21) Từ (20) và (21) ta có bất đẳng thức sau: 2. ( . [, 2] ≥ () (22) [, 2] ≥ 2, .() . () = VF_LENTRA(y) (23) Giá trị N thỏa mãn với bất đẳng thức (23) là tham số securty_strength. Bảng dưới đây thống kê Security_strength cho một số năm tương ứng với số modul n có dạng 512 + 256.x (với x=0..25). Bảng 1. Securty_strength theo Lenstra và Verheul. Năm N securty_strength VF_LENTRA(y) 2018 1792 110 110 2019 2048 117 111 2020 2048 117 113 2021 2048 117 114 2022 2048 117 116 2023 2048 117 117 2024 2304 123 119 2025 2304 123 120 2026 2304 123 121 2027 2304 123 123 2028 2560 128 124 2029 2560 128 126 2030 2560 128 127 3.3.2. Ngưỡng an toàn cho lược đồ đề xuất Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 99 Dựa trên bốn giả thiết của Arjen K. Lenstra và Eric R. Verheul [22], chúng tôi xác định giá trị strength_security cho lược đồ chữ kí số đề xuất trong môi trường KT-XH và trong lĩnh vực QP–AN. Việc xác định ngưỡng an toàn dựa trên các căn cứ sau đây: - Thứ nhất, đánh giá tiềm năng tính toán của đối tượng của QP-AN là (Mĩ và Trung Quốc) viết tắt là TB. - Thứ hai, cập nhật các thông tin mới nhất về sự tiến bộ của công nghệ. - Thứ ba, kế thừa cách tiếp cận của [4], [5] để xây dựng lại công thức tính ngưỡng an toàn trong lĩnh vực QP-AN và trong lĩnh vực KT-XH. Giả thiết I: Tổng kinh phí đầu tư cho TB thuộc lĩnh vực QP-AN tăng gấp đôi trong 10 năm. Trong giả thiết này, nhóm nghiên cứu lấy mốc thời gian tính là năm 2011. Giả thiết này tham khảo trong [4], [5] và dựa trên kết quả khảo sát của nhóm nghiên cứu [22]. Theo [4], [5] “sức mạnh của tổ chức TB Mĩ đã có lần đưa ra con số tổng kinh phí trong năm 1997 là 26,6 tỷ USD và năm 1998 là 26,7 tỷ và ước lượng kinh phí cho năm 1999 phải lên tới 29 tỷ, năm 2011 khoảng 66,6 tỷ”. Kết quả khảo sát trong [22] về ngân quỹ dành cho các tổ chức tình báo Mĩ trong một số năm gần đây: Bảng 2. Dữ liệu khảo sát ngân quỹ dành cho tổ chức tình báo của Mĩ. Dựa trên giả thiết I, chúng tôi tính ngân quỹ của tổ chức TB trong năm 2018 (kí hiệu là ) như sau: TLKTTB=66,6.2  84,8 (tỷ USD) = 848 trăm triệu USD (24) - Giả thiết II: Sức mạnh tính toán của bộ vi xử lý siêu máy tính được nhân đôi sau mỗi 12 tháng với giá thành không đổi. Giả thiết II của chúng tôi cũng dựa kết quả khảo sát tốc độ tính toán của các siêu máy tính hiện nay và dựa trên các kết quả khảo sát trong [4], [5], [24]. Trong [5] đã xét một số kết quả khảo sát. Ngày 23/3/2005 do cơ quan An ninh và Hạt nhân Mỹ (NNSA) cung cấp về siêu máy tính Blue Gene/L cũng với tổng kinh phí 100 triệu USD sẽ hoàn thiện vào tháng 6 năm 2005 với công suất cực đại là 367 tetaflops. Theo [5], năm 2011 sẽ cho ra đời siêu máy tính Titan có tốc độ 10 Peta flops với chi phí 100 triệu USD. Vậy chỉ sau 6 năm cùng một giá thành công suất của dòng siêu máy tính hàng đầu thế giới đã tăng lên gấp 10 petaflop/367 Teta = 101015/3671012 27 lần, tuy chưa đạt gấp 2 lần về công suất sau một năm nhưng cũng đã vượt xa công suất 2 lần sau 18 tháng. Theo [24] đến năm 2016 một máy tính Sunway Taihu Light của Trung Quốc có tốc độ 93 petaflop với giá 273 triệu USD, sau 5 năm tốc độ siêu máy tính đã tăng lên 93.1015/10.10159 lần. Hệ thống Summit của IBM khoảng 150 triệu tỉ phép tính trên giây và giá thành khoảng 122 triệu USD, vượt qua "ngôi vương" hiện nay là Sunway Taihu Light của Trung Quốc với tốc độ 93 petaflop. Chúng tôi sẽ lấy con số trung bình một siêu máy tính thực hiện được năm 2018 (kí hiệu TLTT) là: TLTTSMT(2018)= 130.10 6109.31536000 281 (25) Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 100 Giả thiết III: Thực lực tính toán của tổ chức TB (kí hiệu là ) bằng tiềm năng kinh tế của (kí hiệu là ) nhân với số phép tính mà một siêu máy tính mạnh nhất thực hiện được tại thời điểm năm đó. Về bản chất của giả thuyết này là tổ chức TB đầu tư toàn bộ ngân quỹ để mua các siêu máy tính cho việc tính toán. Chúng tôi đã đưa ra tiềm lực tính toán của tổ chức TB tại năm 2018, kí hiệu (2018) là: (2018) = . (2018) = = 848. 2 2 (26) Việc xác định hệ số ngưỡng an toàn, theo [22] lấy hệ số 106, trong [5] lấy hệ số là 103 lần năng lực tối đa của một siêu máy tính. Dựa trên [4],[5], kết hợp với kết quả khảo sát trên [24] về một số dự báo đến năm 2020, Trung Quốc cho ra đời một siêu máy tính có tốc độ một tỷ tỷ phép tính trên giây, tôi lấy hệ số 10 số phép tính không thể đầu tư trong năm 2018 cho ngưỡng an toàn trong môi trường Quốc phòng-An ninh (QP-AN) bởi một số lí do sau: Thứ nhất, những số liệu công khai về ngân quỹ dành cho QP-AN thường thấp hơn con số trên thực tế. Thứ hai, trong lĩnh vực QP-AN thì an toàn thông tin được đặt hàng đầu. Từ lập luận trên, chúng tôi đưa ra công thức tính ngưỡng an toàn trong lĩnh vực QP-AN cho năm 2018 như sau: A1(2018) = 10 3.TLTB (2018)= 2 99 (27) Trong lĩnh vực kinh tế - xã hội, mọi đầu tư đều gắn với bài toán kinh tế, nên để tính ngưỡng an toàn trong năm 2018, chúng tôi lấy năng lực tính toán của một siêu máy tính mạnh nhất trong năm 2018 nhân với hệ số 10(tương đương với số siêu máy tính có thể bỏ tiền ra mua) của ngưỡng an toàn, công thức tính ngưỡng như sau: (2018) = 10 . (2018) = 2 (28) Từ các giả thiết I, II và III ta có công thức tính ngưỡng an toàn tại năm ³2018, kí hiệu (), ( = 0,1) trong các môi trường KT-XH và QP-AN như sau: - Kinh tế - Xã hội: () = 2 () = (2018). 2 . 2 = 2 () (29) (y) = 91 + 11( − 2018) 10 Quốc phòng – An ninh: () = 2 () = (2018). 2 (). 2 = = 2 () (30) ()=99 + () - Giả thiết IV: Chúng tôi kế thừa giả thiết 4 của [22], nội dung giả thuyết là tiến bộ mã thám cũng tăng trưởng theo luật Moore, cụ thể là cứ sau 18 tháng thì việc phá vỡ hệ mật này sẽ giảm chi phí đi một nửa. Áp dụng bất đẳng thức (21) ta có: + Công thức tính ngưỡng cho lĩnh vực KT-XH là: [, 2] ≥ 2, .() . () (31) Trong đó [, 2]= 2(), () =   e.NN..NE 2log3 2 2lnlnln2ln921)(  Thay kết quả () ở (29) vào (31) ta có: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 101 () = 1,92.  3 22lnlnln2ln NN . ≥ ≥ 109,36 + () = () (32) Công thức xác định ngưỡng trong QP-AN như sau: [, 2] ≥ 2, .() . () (33) Trong đó [, 2]= 2(), () =   e.NN..NE 2log3 2 2lnlnln2ln921)(  Thay kết quả () ở (30) vào (33) ta có: 118,36 + () = 1() (34) Giá trị () thỏa mãn với (31) và (33) lần lượt là ngưỡng an toàn của lược đồ chữ kí số trong lĩnh vực KT-XH (Kinh tế- Xã hội) và trong lĩnh vực QP-AN(Quốc phòng-An ninh). Bảng 3. Độ lớn của số modul n trong KT-XH. Năm Y a0(y) nlen Securty_strength(nlen) VF0(Y) 2018 91 1792 110 109 2019 92 2048 117 111 2020 93 2048 117 113 2021 94 2048 117 115 2022 95 2048 117 116 2023 96 2304 123 118 2024 98 2304 123 120 2025 99 2304 123 122 2026 100 2304 123 123 2027 101 2560 128 125 2028 102 2560 128 127 2029 103 2816 134 129 2030 104 2816 134 131 Bảng 4. Độ lớn của số modul n trong Quốc phòng – An ninh. Năm a1(y) N Securty_strength(nlen) VF1(y) 2018 100 2304 123 118 2019 101 2304 123 120 2020 102 2304 123 122 2021 103 2560 128 124 2022 104 2560 128 125 2023 106 2560 128 127 2024 107 2816 134 129 2025 108 2816 134 131 2026 109 2816 134 132 2027 110 2816 134 134 2028 111 3072 139 136 2029 112 3072 139 138 2030 113 3328 143 140 Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 102 3.4. Xây dựng hệ tiêu chuẩn cho lược đồ đề xuất 3.4.1. Một số chuẩn tham số trên thế giới Để có cơ sở xây dựng hệ tiêu chuẩn cho lược đồ chữ kí đề xuất, nội dung mục này sẽ giới thiệu dưới đây a. Chuẩn FIPS 186-3 [4], [5], [23] Chuẩn 186 − 3 được phê duyệt và công bố vào tháng 6-2009. Theo chuẩn này, yêu cầu đối với tham số của hệ mật gồm các tiêu chuẩn sau: - Các ước nguyên tố của ± 1 và ± 1 (các số nguyên tố bổ trợ), kí hiệu là , và , phải thỏa mãn các thông số kỹ thuật được cho trong bảng 5 dưới đây: Bảng 5. Tiêu chuẩn an toàn các số nguyên tố bổ trợ. Nlen Độ dài tối thiểu của , , và Độ dài tối đa của () + () và () + l() Các số nguyên tố xác suất Các số nguyên tố Chứng minh được 1024 >100 bít <496 bít <239 bít 2048 >140 bít <1007 bít <494 bít 3072 >170 bít <1518 bít <750 bít - √2. 2 ≤ , ≤ 2. - |pq| >2 - Số mũ công khai e là phải là số nguyên nguyên tố cùng nhau với -1 và -1 đồng thời thỏa mãn:2 < < 2. - Số mũ bí mật d phải thỏa mãn > 2 . b. Chuẩn TCVN 7635:2007 [4], [5] Tại Việt Nam, hiện nay mới chỉ có duy nhất một chuẩn liên quan đến hệ mật , đó là chuẩn 7635: 2007 được công bố vào năm 2007. Theo đó, các tham số của hệ mật có 4 tiêu chuẩn như sau: - Độ dài số modul n, kí hiệu nlen= len(n) không được nhỏ hơn 1024 và tăng lên theo thời gian sống, được cụ thể hóa trong bảng 6 dưới đây: Bảng 6. Tiêu chuẩn một số tham số RSA của Việt Nam. Thời gian sử dụng Độ an toàn nlen tối thiểu Tới năm 2010 80 1024 bít Tới năm 2020 112 2048 bít Sau năm 2030 128 3072 bít - Số mũ công khai phải được chọn với các ràng buộc sau: + Chọn trước khi tạo số mũ bí mật . + Là số nguyên dương lẻ sao cho 65537 £ < 2._ - Hai số nguyên tố p, q phải được tạo ngẫu nhiên và được chọn với các ràng buộc sau: + − 1 và − 1 phải nguyên tố cùng nhau với e; + Các số nguyên tố bổ trợ, kí hiệu lần lượt là , , , phải lớn hơn: 2_. + √2. 2 ≤ , ≤ 2 − 1. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 103 - Số mũ bí mật d phải được xác định sau khi tạo p và q với ràng buộc: > 2 3.4.2. Xây dựng hệ tiêu chuẩn cho lược đồ chữ kí số đề xuất Dựa trên công thức xác định giá trị ngưỡng an toàn cho lược đồ chữ kí đến năm y≥ 2018 (công thức 31 và 33) nhóm nghiên cứu xây dựng hệ tiêu chuẩn tham số cho các lược đồ chữ kí số đề xuất, bao gồm: - Chuẩn về độ lớn số modul n đảm bảo chống phân tích bằng thuật toán sàng trường số. - Chuẩn về kích thước của các số nguyên tố và , đảm bảo bài toán phân tích = . theo các thuật toán hiện nay là khó. - Chuẩn về kích thước của các số nguyên tố bổ trợ , lần lượt là ước của + 1 và − 1; , lần lượt là ước của + 1 và − 1 đảm bảo cho phân tích được n là khó. - Cấp t của phần tử sinh g phải là tích của hai số nguyên tố đủ lớn (là hợp số) để chống tấn công bằng thuật toán vét cạn. - Chuẩn về cỡ khóa bí mật x và khóa phiên k đủ lớn để chống thuật toán vét cạn. Dựa trên kết quả tính ngưỡng an toàn, dựa trên các chuẩn tham số được giới thiệu ở phần trên, nhóm nghiên cứu xây dựng hệ tiêu chuẩn tham số an toàn cho lược đồ đề xuất như sau: Tiêu chuẩn 1. Số modulo n dùng phải có độ lớn cỡ N bit với N thoả mãn bất đẳng thức sau để chống phân tích bằng thuật toán sàng trường số [22] ở năm y nào đó, và được lấy làm giá trị security_strength. () = . . . ( + ) . ≥ () cho KT-XH () = . . . ( + ) . ≥ () cho QP-AN Tiêu chuẩn 2. Các số nguyên tố p và q đều xấp xỉ N tham khảo trong [4], [5], [23] √2. 2 ≤ , ≤ 2 (35) Tiêu chuẩn 3: Chống lại tấn công dựa vào thuật toán của Femart, nhóm nghiên cứu tham khảo chuẩn X9.31 và chuẩn FIPS 186-3 |pq| >2 . (36) Tiêu chuẩn 4: Tiêu chuẩn về ước nguyên tố của ± 1 và q±1. Các số nguyên tố bổ trợ , , , đều là các số nguyên tố chứng minh được được xây dựng nhằm chống lại tấn công thuật toán phân tích số p-1 của Pollard và thuật toán phân tích số p1 của Williams. Tiêu chuẩn này nhóm nghiên cứu tham khảo trong [3], [4], [5 ] cụ thể như sau: - len(pi), len(qi) 2.security_strength(nlen)(i=1,2) (37) - |( 1), |( 1), ∤ ( 1), ∤ ( 1). (38) Tiêu chuẩn 5: Tiêu chuẩn này đảm bảo việc sinh thành công các số nguyên tố p, q trong tiêu chuẩn 4 mà p±1 có các ước nguyên tố trong tiêu chuẩn 3. Số nguyên tố p chỉ được chọn trong tập các số nguyên bít dạng: . + với A= 1 −1 < (39) q chỉ được chọn trong các số nguyên bít dạng . +B với B= 1 −1 < (40) Chính vì vậy các tích p1p2 và q1q2 không được quá lớn để trong tập các số nguyên đó có tồn tại ít nhất một số nguyên tố. Tiêu chuẩn sau đây được đưa ra nhằm đảm bảo điều đó. Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 104 () + () ≤ − 18 (41) () + () ≤ − 18 (42) Tiêu chuẩn 6: Chống lại tấn công dựa vào thuật toán của Femart, nhóm nghiên cứu tham khảo chuẩn X9.32 và chuẩn FIPS 186-3 [4], [5], [23] |pq| >2 . (43) Tiêu chuẩn 7: Tiêu chuẩn về giá trị và bậc của phần từ sinh g Để sinh g chúng tôi tham khảo trong kết quả nghiên cứu [3]. Để tính độ lớn cấp của g, nhóm nghiên cứu dựa trên kết quả nghiên cứu của mình trong bài báo “phát triển thuật toán của Pollard tính cấp của phần tử trong Zn” tham khảo trong [7]. Bài báo đã đề xuất thuật toán tìm cấp của phần tử g với độ phức tạp tính toán là O(√) phép tính cơ bản và độ phức tạp về không gian lưu trữ là O() bít, trong đó t= Ordn(g). Vậy để đảm bảo an toàn cho bậc của g trong Zn thì bậc t phải thỏa mãn bất đẳng thức sau đây: (√) ≥ 2 Security_strength (44) Vậy cấp của g, kí hiệu là t phải được chọn như sau: + Các số p,q và các số nguyên tố phụ trợ , , , được sinh theo tiêu chuẩn 3 + Giá trị t được tính theo công thức: = . (45) Với giá trị t như (2.56) ta có: ≥ 2 _2_ = 2_ Giả sử cần xây dựng các lược đồ chữ kí số có Security_Strength là 194 bít, các giá trị m, , cần phải chọn như sau: | |≥388 bít, || ≥ 194 bít, || ≥194 bít. Ngoài ra số modul hợp số n là tích của hai số nguyên tố mạnh p, q và có kích thước tương ứng là |q|≈1792 bít - Miền giá trị của phần tử sinh g thỏa mãn: 2≤ ≤ − 1 Tiêu chuẩn 8: Cỡ khóa bí mật x và khóa phiên k phải thỏa mãn: () ≥ _ℎ (46) Len(k)≥ Security Strength 4. THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ Thử nghiệm được tiến hành trên một số khâu, thứ nhất là sinh bộ tham số trên cơ sở hệ tiêu chuẩn được đề xuất. Các số nguyên tố được sinh theo thuật toán Pocklington và Lucas; thứ hai là tiến hành thử nghiệm quá trình kí và xác nhận chữ kí đối với lược đồ đề xuất. 4.1. Thiết kế mẫu thử Trong phần thử nghiệm này, xét độ dài khóa nlen lần lượt là: 1792, 2048, 3072 (bít) để sinh tham số, kí và xác nhận chữ kí cho lược đồ đề xuất.Văn bản được sử dụng để thử nghiệm quá trình kí là file có tên prime.dat có dung lượng 13 KB. Số lần thử nghiệm cho mỗi bộ tham số là khoảng 100 lần. Hàm băm SHA 512 được sử dụng trong các lược đồ chữ kí đề xuất. Chương trình thử nghiệm viết bằng ngôn ngữ lập trình C++, được biên dịch bởi trình QT Creater và chạy trên hệ điều hành Window 7. Bộ vi xử lý Core2 Duo 2.2 GHz bộ nhớ 2GB. 4.2. Thử nghiệm 4.2.1. Thử nghiệm việc sinh tham số Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 105 Phần này, bài báo trình bày việc thử nghiệm việc sinh tham số trên một số loại số modul n, có độ dài nlen =len(n). Mỗi loại modul cho kết quả về thời gian sinh trung bình được thống kê trong bảng 7 dưới đây: Bảng 7. Thời gian sinh tham số. Nlen Lớn nhất Nhỏ nhất Trung bình cộng 2048 171.175 35.231 103 2560 131.534 51.502 86 3072 298.729 102.324 200.526 Tiến hành thử nghiệm sinh tham số, kết quả đã sinh thành công các bộ tham số trên một số loại modul cho lược đồ chữ kí số đề xuất với độ chính xác cao. Dưới đây là một bộ tham số dành cho lĩnh vực QP-AN(Quốc phong- An ninh) áp dụng cho đến năm 2020: − Đố ượ: − − ă á ụ: 2020 − = 2304 − _ℎ = 123 − ℎ ố ê ố =6117232749284706947203239371920572680913581374344079905019539757 091969779609195832178686393815797179231584450687350904654445901047926261 016391750900375290723316522983402788068103910649132595781452276218835313 692858357640592707117099769490265568891466928058587361831331617083895320 3869922556001914227403684473177613538613050971211766442851841479167 =6117232749284706947203239372165241178407805609524707140304808021 334700107240094221457980974875579665856482486696897809652770444839304520 315729844974399636145908775883111646022320901144698890700654345944211702 444975058600757808341016317243880619615949481340623010847483640168347025 2769537799849573649168308139563948193089504447954945026836236283583 =1590534206344756541002473361362267517782751327132616137494589001 34176602566388781570317 =1985614919418770253554139577696688725104410919860671548392634757 923125112244407698045596289355450387186381030320100489242104155573878362 130569 = . = =374205365089213343236799977368799187378492399860705535514121185384 913202133246715572720056609310372232927934637558406882632683400404075811 820725438478222157337957545056124043570988682123189979622934691619308827 858101685690917024653851393783159621883547875379248977845729740928005914 101132515205529382820021778317541296828514820228504485687518794794569049 122344781840916367291864533267221572266034555898463003353317004181383947 023853924555396776944029816527765834205868915496984985760288645667395616 399903073198478653716808973067345000250599372237500349919525811510434898 463163281112582895213952411321630863594163907384146979093552223043493624 4590061640318236939497659923371024947768457598615361 = . =315818844996404145811487217753602854439434425805693451987126031751 165091268437889910768969124664130130474124314135515268407159958855091705 051328439558536170824344041603195552322851049527624457364994979717665410 375124601608720373 - Phần tử sinh g: Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 106 =2722740927518078804297162359634694107036703104215097031961026956 647548389244408487053935938553338345233841480396080689038796880104959987 729457411391891046515421618509804723046914768262384217993614370095985681 251046180419351630430635035951088415801907314724412195094326850422208394 346652685460227298924015353725112900662690850110151111414819751303096920 602275342188347901558539481400551818506671844045497402678284867676891538 667392149323649415492487221834464512784480685206155466892348500722070942 894717375776387642493975395949518903382388505875340604188635201555508477 905685471268827956062659846294860057557133780352367131142854775017831066 836135468060630019680931986760987291719305484543621237 - Khóa bí mật x: =4789605382688032943311390894628144271798153262079258960121000980 45534372655953263094516497271186507247792819591 = =258064992683523437872834804309596370418683035575698005674961406876 926457917853356034840864626618241032365043046180910481036205265467769320 815723316816286889253547378270943002995461712050784378735837103278455263 26326124989411910 - Khóa công khai y: =1958140090805843080033460308163404599040361320280771592344408253 939131809624402273145590485252449976947879275371099433474526095422112163 545721079573569411844060790684328164774046180231665724275313173576543351 661208439954269674093332628492273475418157345089961280030573788292239732 882896480339223363693177804238670419677164430351781684872234419041550292 459169441973051934598903114472857856373055275683186960759129594844445207 185141966575440425040876652748242428063984245427291009504071697553229257 768688302241305180478207662424476681195042311595647296925236593093534165 660805548964914113588144331077326730829155058301641062893844038421671295 978470932888830211012059530008248541089800072129828242 - Thời gian sinh: 207.879s 4.2.2. Sinh chữ kí và xác nhận chữ kí a. Sinh chữ kí - Giá trị băm của tập tin cần kí H(T) là: H(T)=08E03FBB02A9DD798D32F4CFA47C8460B5AF20E90C1BC5ADD194870 E7398847C32D9F8C353B299C615AEC113C6F4139DEB32027B585CB8E6CD88AF5E 3DCFFF55 - Giá trị khóa phiên k: k=32834684253690707691998692287039616877148471016008902096218554898 555884104656978148054041457605695905241558409100777620283981529290008760 451237447829403292823393666233556310720082661543993222477354281284575475 9783254266468 - Chữ ký được sinh: r=33520797050380488230489455953272723697539979981291831868360929429 345742617198557345380954737221413498603373208559904619776003669036366863 972170394778519944912088292755976458759364044921871908293963707576678905 313416511197800412556924336730455141564034875682196399048143505619847695 Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 107 985036593491611072906249422597524465469492830012841606008449123709490061 356922717296083169345014561015596787433078368133920123031256021130812426 594694485271403865519256337033560576514306420738889323471846720737216196 802868513526301835157835817241381045267277096002079776066750593046263443 561889489343148592433897849001052354890006031459917947382038975484570399 87719011264206485038093084193581462951808808948378211 s=57090929290690807750238295155975129257654618079720693182493393039 861012270764916833964817360441744233679722372241360555716843825674762462 399971724716670361047378997489132820965307305772958660716557488292480872 193758459370160544 - Thời gian sinh chữ ký (r,s) mất 11.262(s) b. Xác nhận chữ kí: Việc xác nhận chữ kí được thực hiện trên thông báo T có giá trị băm là SHA-512(T). H(T)=08E03FBB02A9DD798D32F4CFA47C8460B5AF20E90C1BC5ADD194870E7 398847C32D9F8C353B299C615AEC113C6F4139DEB32027B585CB8E6CD88AF5E3D CFFF55 Chữ kí (r,s) là của T, kết quả thử nghiệm xác nhận chữ kí đã thành công với thời gian xác nhận là19.595(s) 5. KẾT LUẬN Bài báo đã đề xuất giải pháp nâng cao độ an toàn cho lược đồ chữ kí số trên vành hữu hạn . Nội dung giải pháp đề xuất là phát triển một lược đồ chữ kí số mới trên vành hữu hạn khắc phục được một số nhược điểm của lược đồ chữ kí số Elgamal và biến thể của nó trong tình huống lộ khóa phiên hoặc trùng khóa phiên, đồng thời chỉ ra một số điểm tồn tại trên các lược đồ chữ kí số trên vành của một số nhà khoa học[1], [2], [3], [17], [18], [19], trong đó, điểm tồn tại đáng lưu ý nhất của các lược đồ chữ kí số này là các nhà khoa học chưa xây dựng được công thức tính ngưỡng an toàn và hệ tiêu chuẩn cho các tham số an toàn cho các lược đồ đề xuất. Trên cơ sở chỉ ra những điểm tồn tại trên các lược đồ chữu kí số được khảo sát, dựa trên cách tính ngưỡng an toàn của hai tác giả Arjen K. Lenstra và Eric R. Verheul và dựa trên một số hệ tiêu chuẩn tham số an toàn cho hệ mã RSA của thế giới, nhóm nghiên cứu đã xác định được công thức tính ngưỡng an toàn và xây dựng được hệ tiêu chuẩn tham số an toàn cho lược đồ đề xuất cho năm 2018 và những năm tiếp theo, có thể nói đây là đóng góp quan trọng nhất của bài báo. Phần thử nghiệm được tiến hành trên hai công đoạn: công đoạn sinh tham số theo hệ tiêu chuẩn đã đề xuất và công đoạn kí, xác nhận chữ kí. Kết quả thử nghiệm đã tạo ra một bộ tham số an toàn đến năm 2020 cho lược đồ chữ kí số đề xuất. Phân tích kết quả thử nghiệm cho thấy các tham số được tạo ra đều chính xác, đạt đúng tiêu chuẩn đã xây dựng. TÀI LIỆU THAM KHẢO [1]. Phạm Văn Hiệp, Nguyễn Hữu Mộng, Lưu Hồng Dũng, Một thuật toán chữ ký xây dựng trên tính khó của việc giải đồng thời hai bài toán phân tích số và logarit rời rạc, Tạp chí KH và CN, Đại học Đà nẵng, 2018 [2]. Lê Văn Tuấn, Bùi Thế Truyền, Lều Đức Tân, Phát triển lược đồ chữ kí số mới có độ an toàn dựa trên bài toán logarit rời rạc trên vành , Tạp chí KHCN Thông tin và Truyền thông, Học viện CNBCVT No ,10- 2018. [3]. Vũ Long Vân, Hồ Ngọc Duy, Nguyễn Kim Tuấn, Nguyễn Thị Thu Thủy, Giải pháp nâng cao độ an toàn cho lược đồ chữ kí số, SOIS Thành phố HCM,12 - 2017. Kỹ thuật điều khiển & Điện tử L. V. Tuấn, L. Đ. Tân, “Giải pháp nâng cao độ an toàn trong vành hữu hạn Zn.” 108 [4]. Hoàng Văn Thức, Hệ tiêu chuẩn an toàn cho hệ mã RSA và ứng dụng, Luận án tiến sỹ, Hà Nội, 2011, 22- 23 [5]. Chu Minh Yên, Nghiên cứu xây dựng hạ tầng cơ sở khóa công khai trong lĩnh vực An ninh – Quốc phòng, Luận án tiến sỹ, Hà Nội –2012 [6]. Lê Văn Tuấn, Bùi Thế Truyền, Phát triển thuật toán của SHANK giải bài toán logarít rời rạc trên vành ,Tạp chí Nghiên cứu KH & CNQS số 48, 4- 2017 [7]. Lê Văn Tuấn, Lều Đức Tân, Phát triển thuật toán Rho porllard tính cấp của phần tử trên vành , Tạp chí Nghiên cứu KH & CNQS số 49, 6-2017. [8]. T. ElGamal, A public key cryptosystem and signature scheme based on discrete logaríthms, IEEE Transaction on Information Theory, 1985, IT-31(4): pp. 469 - 472. [9]. W. C. Kuo, On ElGamal Signature Scheme, Future Generation Communication and Networking (FGCN 2007), Jeju, 2007, pp. 151-153 [10]. C. P. Schnorr, Efficient signaturegeneration for smartcards, Journal of Cryptology Vol. 4, pp. 161-174, 1991. [11]. B. Yang, A DSA-Based and Efficient Scheme for Preventing IP Prefix Hijacking, International Conference on Management of e-Commerce and e-Government, Shanghai, 2014, pp. 87-92. [12]. J.m.Liu, X.g.Cheng, and X.m.Wang, Methods to forge elgamal signatures and determine secret key, in Advanced Information Networking and Applications, AINA 2006 20th International Conferenceon, vol.1.IEEE, 2006, pp. 859–862. [13]. L. Xiao-fei, S. Xuan-jing and C. Hai-peng, An Improved ElGamal Digital Signature Algorithm Based on Adding a Random Number, Second International Conference on Networks Security, Wireless Communications and Trusted Computing, Wuhan, Hubei, 2010, pp. 236-240. [14]. C. Y. Lu, W. C. Yang and C. S. Laih, Efficient Modular Exponentiation Resistant to Simple Power Analysis in DSA-Like Systems, International Conference on Broadband, Wireless Computing, communication and Applications, Fukuoka, 2010, pp. 401-406. [15]. H. Zhang, R. Li, L. Li and Y. Dong, Improved speed Digital Signature Algorithm based on modular inverse, Proceedings of 2013 2nd International Conference on Measurement, Information and Control, Harbin, 2013, pp. 706-710. [16]. Z. Ping, W. Tao and C. Hao, Research on L3 Cache Timing Attack against DSA Adopting Square-and-Multiply Algorithm, Fifth International Conference on Instrumentation and Measurement, Computer, Communication and Control (IMCCC), Qinhuangdao, 2015, pp. 1390-1393. [17]. Lê Văn Tuấn, Bùi Thế Truyền, Lều Đức Tân, Contructing the digital signature besed on the discrete logaríthmic problem, The research journal of military science and technology, No 51ª,11- 2017, ISSN 1859 – 1043, pp 44-56 [18]. S. K. Tripathi and B. Gupta, An efficient digital signature scheme by using integer factorization and discrete logaríthm problem, International Conference on Advances in Computing, Communications and Informatics (ICACCI), Udupi, 2017, pp. 1261-1266. [19]. Chik How Tan, Xun Yi and Chee Kheong Siew, Signature scheme based on composite discrete logarithm, Fourth International Conference on Information, Communications and Signal Processing, 2003, pp. 1702-1706 [20]. D.R Stinson, Cryptography Theory and Practice, CRC Press, pp 176, 2003 [21]. D. M. Gordon, Strong Primes Are Ease to Find, Advances in Cryptology- Proceedings of EUROCRYPT 84 (LNCS 209), 216-223, 1985. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 109 [22]. Arjen K. Lenstra, Eric R. Verheul, Selecting Cryptographic Key Sizes, Springer- Verlag Berlin Heidelberger 2000, pp. 446-465 [23]. National Institute of Standards and Technology (NIST), FIPS Publication 186: Digital Signature Standards (DSS)(1994) [24]. //.www.top500.org [25]. [https://fas.org/irp/budget/] [26]. Richard Crandall, Carl Pomerance, Prime Numbers, A Computational Perspective, Second Edition, Springer Science + Business Media, Inc, 2005. ABSTRACT A SOLUTION FOR IMPROVING THE SECURITY OF THE DIGITAL SIGNATURE SCHEME IN WHICH ITS SECURITY IS BASED ON THE DISCRETE LOGARITHM PROBLEM IN THE FINITE RING In this paper, a solution for improving the security of signature schemes in the finite ring is proposed. Based on proposed solution, a new signature scheme in which its security is based on discrete logarithms problem in ring is proposed. In addition, basing on Arjen K. Lenstra and Eric R. Verheul's method of calculating the secure thresholds, the authors developed a secure threshold formula and to constructed a secure parameter domain for the proposed digital signature scheme. We will prove that the proposed signature scheme is secure than the Elgamal signature schemes and its variants on finite field and can be applied in national defence- national security. Keywords: Digital signatures; Discrete logarithms; Safety thresholds. Nhận bài ngày 20 tháng 07 năm 2018 Hoàn thiện ngày 27 tháng 08 năm 2018 Chấp nhận đăng ngày 11 tháng 10 năm 2018 Địa chỉ: 1 Học viện Khoa học quân sự; 2 Học viện Kỹ thuật Mật mã. *Email: levantuan71@yahoo.com.