Nội dung

Kỹ thuật điều khiển & Điện tử 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 90 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.” Nghiên cứu khoa học công nghệ 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 ( , ) ) Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 91 Kỹ thuật điều khiển & Điện tử 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 92 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.” Nghiên cứu khoa học công nghệ Ý 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))) Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 93 Kỹ thuật điều khiển & Điện tử 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 Sinh số n tố p, q, p1, q1; p1|(p-1), q1|q-1, p1∤ (q-1), q1∤ (p-1); t = p1.q1, ordn(g)= t N= Len(t) Sinh tham số x= random(t), tồn tại x-1 trong Z t, y = gx mod t (n, g, x, t) is secret key (n, g, y, N) is public key; k= Random(1,t) Sinh chữ kí r = gk mod n. z = number(N, H(T||str(r))) s = x-1 (k-z) mod t T S=0 or p1|k or q1|k or q1|k or t|r F Gửi(r,s,T) tới nơi nhận z = number(N, H(T||str(r))) u=(gz.ys) mod n. F T u=r Accept Xác nhận chữ kí Reject Kết thúc Hình 1. Lưu đồ thuật toán lược đồ chữ kí . 94 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.” Nghiên cứu khoa học công nghệ 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 DLP và 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ó. Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 95 Kỹ thuật điều khiển & Điện tử 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ể. 96 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.” Nghiên cứu khoa học công nghệ 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 Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 97 Kỹ thuật điều khiển & Điện tử 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: 2 3 E ( N )  1.92. N ln 2 ln N  ln ln 2 . log 2 e   (18) Và chi phí để phân tích một số nguyên lớn 512 bít là: 2 3 E( 512 )  1.92. 512 ln 2 ln 512  ln ln 2 . log 2 e  63bit   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 ] ] 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 năm ≥ 1999, kí hiệu là [ , 2 ] theo công thức sau: (19) − tại ( [ ,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 98 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.” Nghiên cứu khoa học công nghệ 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.106109.31536000 281 (25) Tạp chí Nghiên cứu KH&CN quân sự, Số 57, 10 - 2018 99