Phương pháp xây dựng tập slist các logarit có trọng số thấp - Đặng Vũ Sơn

Công nghệ thông tin & Cơ sở toán học cho tin học Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 148 PHƯƠNG PHÁP XÂY DỰNG TẬP Slist CÁC LOGARIT CÓ TRỌNG SỐ THẤP Đặng Vũ Sơn1, Nguyễn Thanh Sơn1,*, Phạm Quốc Hoàng2 Tóm tắt: Bài báo này trình bày một số phương pháp xây dựng tập Slist các logarit có trọng số thấp nhằm giải bài toán logarit rời rạc. Các tác giả trình bày thuật toán gốc trong xây dựng tập S, sau đó, đề xuất thêm hai thuật toán mới tại mục 3, mục 4; Đồng thời, đánh giá độ phức tạp của hai thuật toán mới so với thuật toán gốc ban đầu. Từ khóa: Thuật toán tính logarit rời rạc theo kiểu tính sẵn, Tấn công logarit trọng số thấp. 1. MỞ ĐẦU Đối với các hệ mật có độ an toàn dựa trên độ "khó" của bài toán logarit trên nhóm cyclic hữu hạn g tồn tại một kiểu tấn công theo kiểu tính sẵn tập với một số giá trị ℓ[0,#g) nào đó ([1], [2],[4],[5]). Tập được tính sẵn đó được ký hiệu là Slist Slist = {(b,ℓ): b = gℓ}. Việc tính logarit rời rạc lúc này, chuyển thành việc tra bảng Slist. Khi này, với mỗi b  g, ta có thể hy vọng tính được loggb theo thuật toán sau: Thuật toán 1. (tìm logarit đã được tính sẵn) Input: a  g. Output: ℓ = loggb khi (b,ℓ)  Slist và "Failure" trong trường hợp ngược lại. 1 (b,ℓ)  First(Slist); 2 while ((b,ℓ)  Null) do { if (b==a) return ℓ; (b,ℓ)  Next((b,ℓ),Slist); } 3 return "Failure". ở trên các hàm First(.) và Next(.,.) được định nghĩa như sau: First(S) Input: S là một tập hợp. Output: Phần tử đầu tiên trong S nếu có. Ngược lại trả về Null. Next(x,S) Input: x, S trong đó S là một tập hợp còn x  S. Output: Phần tử đứng ngay sau x trong S nếu còn, ngược lại trả về Null. Ví dụ. Trường hợp Slist = {(b,ℓ): b = gℓ, ℓ  B} thường là B không lớn thì thuật toán 1 còn được gọi là thuật toán "tấn công các logarit giá trị thấp". Trường hợp Slist = {(b,ℓ): b = gℓ, weight(ℓ)  k, len(ℓ) m } (1.1) thường là k không lớn với weight(ℓ) là số các bít 1 trong biểu diễn nhị phân của ℓ, và được gọi là trọng số của ℓ, thì thuật toán 1 còn được gọi là thuật toán "tấn công các logarit trọng số thấp". Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 149 Tấn công các logarit trọng số thấp sẽ có độ phức tạp tính toán ít hơn, bởi vì với các số mũ trọng số thấp, việc thực hiện phép mũ hóa theo thuật toán nhân và bình phương có lặp sẽ tốn ít thời gian hơn. Do đó, việc lập tập tính sẵn Slist cũng tốn ít thời gian hơn. Rõ ràng các loại tấn công tìm logarit rời rạc dựa trên một tập các logarit rời rạc đã được tính sẵn thì việc xây dựng tập Slist chiếm hầu hết chi phí, do đó, mọi cải tiến nhằm giảm được chi phí trong công đoạn này là quan trọng nhất. Trong bài báo này, chúng tôi xét đến thuật toán tấn công các logarit trọng số thấp, cụ thể đưa ra được hai thuật toán mới để xây dựng tập Slist. Dùng thước đo là số phép toán nhóm cần thiết để xây dựng tập Slist của thuật toán, ký hiệu là Cost. Tại phần 2 chúng tôi đã chỉ ra rằng Cost của thuật toán mới thứ nhất, ký hiệu Cost1(k,m), không đến 2 1k  Cost của thuật toán gốc, ký hiệu Cost0(k,m) tức là Cost0(k,m)  1 2 k  Cost1(k,m) (1.2) ở trên m=log2#g. Thuật toán mới thứ hai trình bày tại mục 4 là một chuyển thể của phương pháp baby- steps, giant-steps do Daniel Shanks đưa ra từ năm 1969 [3] cho phép tách tập Slist thành hai phần Sbaby và Sgiant theo công thức Slist = Sbaby  Sgiant (1.3) Độ phức tạp của thuật toán 2 được ký hiệu là Cost2(k,m). Việc đánh giá độ phức tạp của thuật toán 2 được thực hiện ở mục 4.2.2. Có một số công trình trên thế giới có liên quan đến chủ đề của bài báo này. Trong công trình [6], [7] việc lập tập Slist được thực hiện một cách trực tiếp, mà không có việc tách bit như trong thuật toán 1 được đề xuất trong bài báo này. Trong công trình [8] dựa trên việc phân tích số mũ 1 2 3x x x x , với ix là các số có trọng số thấp, sau đó tìm x. Với việc tách 1 bit nhờ hàm Div(x) tập Slist sẽ được tích lũy một cách tuần tự theo trọng số tăng dần, việc này giúp giảm độ phức tạp tính toán cho thuật toán 1 được đề xuất. Sau đó, thuật toán 2 được đề xuất dựa trên phương pháp baby-steps, giant-steps và thuật toán 1. 2. PHƯƠNG PHÁP TRUYỀN THỐNG XÂY DỰNG TẬP Slist 2.1. Thuật toán gốc Tìm các logarit có trọng số thấp (không quá k) theo phương pháp truyền thống được thực hiện theo thuật toán sau. Thuật toán 0 Input: k, g trong đó k là một số nguyên dương còn # g là số m-bits, tập S là tập các số ℓ có trọng số weight(ℓ) k , độ dài của ℓ theo bit len(ℓ ) m và được sắp theo thứ tự tăng dần. Output: Slist = {(b,ℓ): b = gℓ, ℓ S }. 1 Slist  {(1,0)}; 2 Với mỗi ℓS, ℓ tăng dần thực hiện { b  gℓ; Slist  Slist  {(b,ℓ)}; } 3 return Slist. 2.2. Phân tích thuật toán 0 Công nghệ thông tin & Cơ sở toán học cho tin học Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 150 Mệnh đề 1. Số phép toán nhóm của thuật toán 0 được đánh giá theo công thức sau: Cost0(k,m)  1 1 2 k w m w k C    (2.1) Chứng minh: Biết rằng có đúng L =   k 0w w mC giá trị ℓ thỏa mãn weight (ℓ)  k, len(ℓ ) m . Để tính gℓ người ta sẽ tính sẵn các giá trị 2 4 8 2, , ,..., m g g g g rồi lưu lại, mỗi lần dùng thì tra bảng. Vì vậy, mỗi lần tính lg chỉ cần weight(ℓ)-1 phép toán nhân. Suy ra độ phức tạp tính toán của thuật toán gốc là: Cost0(k,m)= w w 1 (w 1) k mC   (2.2) Ta có, cho các số , , ,x y a b sao cho ,y x b a  , dễ dàng suy ra bất đẳng thức sau: ( )( ) 2 x y a b xa yb     (2.3) Với giả thiết 2 m k  ta có wmC sẽ tăng theo giá trị của w với (1,..., k)w . w w 1 (w 1) k mC   = 1 20. 1. ... ( 1) km m mC C k C    = 1 2 1(0. ( 1) ) (1. ( 2) ) ...k km m m mC k C C k C       Áp dụng bất đẳng thức (2.3) ta thu được: w w 1 (w 1) k mC   1 2 1 1 1 ( ) ( ) ... 2 2 k k m m m m k k C C C C         w w 1 (w 1) k mC   w w 1 1 2 k m k C     (2.4) Và đây là điều cần chứng minh. 3. THUẬT TOÁN MỚI XÂY DỰNG TẬP Slist 3.1. Thuật toán Thuật toán xây dựng tập Slist đưa ra ở đây được trình bày như việc tính hàm 3 biến đầu vào MakeSlist(g,m,k) được thực hiện như sau. Ý tưởng của thuật toán 1 là tách số mũ ℓ thành hai thành phần ℓ1, ℓ2 sao cho weight(ℓ1)=1, weight(ℓ2)=weight(ℓ)-1 và ℓ= ℓ1+ℓ2, việc này dễ dàng thực hiện bằng việc tách 1 bit cao nhất bên trái khỏi ℓ. Các tập số mũ có trọng số thấp sẽ được xây dựng từ S1, và tập mới tính được sẽ bao trùm tập trước đó. Việc phân tích cụ thể thuật toán 1 được trình bày ở mục 3.2. 3.1.1. Thuật toán tính hàm MakeSlist(g,m,k) Thuật toán 1. Input: k, g trong đó, k là một số nguyên dương còn # g là số m-bits. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 151 Output: Slist = {(b,ℓ): b = gℓ, weight(ℓ)  k, len(ℓ ) m }. 1 Sindex[w]  {ℓ: ℓ[0, # g ) and weight(ℓ) = w} with 2wk; 2 Slist  {(1,0)}; 3 ℓ  1; 4 b  g; 5 S1 {(b,ℓ)}; 6 while (ℓ<# g ) do { 6.1 b  b*b; //Phép * ở đây là phép toán nhóm. 6.2 ℓ  2*ℓ; //Phép * ở đây là phép nhân thông thường. 6.3 S1  S1{(b,ℓ)}; } 7 Snew  S1; 8 Slist  Slist  Snew; 9 for w from 2 to k do { 9.1 Sold  Snew; 9.2 Snew  {}; 9.3 ℓ  Fist(Sindex[w]); 9.4 while (ℓ  Null) { 9.4.1 (ℓ1,ℓ2)  Div(ℓ); 9.4.2 (b1,ℓ1)  Search((.,ℓ1),S1); 9.4.3 (b2,ℓ2)  Search((.,ℓ2),Sold); 9.4.4 b  b1*b2; //* là phép toán nhóm 9.4.5 Snew  Snew{(b,ℓ)}; 9.4.6 ℓ  Next(ℓ,Sindex[w]); } 9.5 Slist  Slist  Snew;} 10 return Slist. 3.1.2. Định nghĩa một số hàm sử dụng trong thuật toán Search((x,.),S); Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ nhất của S. Output: (x,b) trong S. Search((.,x),S); Input: S là một tập hợp các cặp phần tử (a,b), x thuộc về tập các phần tử thứ hai của S. Output: (a,x) trong S. Div(x): Input: x  [0, 2m). Output: (x1,x2)  [0, 2m)[0, 2m) thỏa mãn weight(x1) = 1, weight(x1) + weight(x2) = weight(x) và x = x1 + x2. 3.2. Phân tích thuật toán 1 Trước hết, ta chứng tỏ tính đúng đắn của thuật toán 1. Công nghệ thông tin & Cơ sở toán học cho tin học Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 152 Kết quả 2. Tập Slist tại đầu ra của thuật toán chứa tất cả các cặp (b,ℓ) với weight(ℓ)  k. Nói một cách khác thì tập này chính là tập cần xây dựng. Chứng minh: Sau bước 2 thì Slist chứa cặp (1,0) tức là tập cần lập ứng với k=0. Các bước từ 3 đến 6 chính là tạo tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1, do đó, Slist sau bước 8 sẽ chứa các cặp (b,ℓ) với weight(ℓ)1. Giả sử quy nạp rằng tập Snew trước bước 9.1 của vòng lặp thứ w chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w1 (điều này đã đúng với w=2), ta sẽ chứng tỏ tập này sau bước 9.4 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w. Quả vậy, từ định nghĩa hàm Div(x) nên cặp (ℓ1,ℓ2) thu được trong bước 9.4.1 thỏa mãn: weight(ℓ1) = 1 nên (b,ℓ1) trong bước 9.4.2 sẽ khác Null. (3.1) weight(ℓ1) + weight(ℓ2) = weight(ℓ) hay weight(ℓ2) = w1. (3.2) ℓ1+ℓ2 =ℓ. (3.3) Như đã chỉ ra ở trên tập S1 chứa toàn bộ các cặp (b,ℓ) với weight(ℓ)=1 nên với (3.1) cặp (b1,ℓ1), do đó, tìm được trong 9.4.2 sẽ khác "Failure" điều này có nghĩa b1 = 1g (3.4) Từ 9.1 ta có Sold chính là Snew trước bước này nên theo giả thiết quy nạp tập này chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w1, cùng với (3.2) nên cặp (b2,ℓ2) do đó tìm được trong 9.4.3 sẽ khác "Failure" điều này có nghĩa b2 = 2g (3.5) Từ (3.4) và (3.5) nên giá trị b trong bước 9.4.4 sẽ là: b = b1*b2 )5.3(&)4.3(  1g * 2g = 21g   )3.3(  gℓ. (3.6) Trong vòng lặp này duyệt toàn bộ các giá trị ℓ với weight(ℓ)=w nên Snew tính được trong 9.4.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ) = w và đây là điều cần chứng minh. Điều trên cho thấy Slist sau bước 9.5 sẽ chứa tất cả các cặp (b,ℓ) với weight(ℓ)w và vì thế sau bước 9 Slist chính là tập cần xây dựng. Do mỗi lần tính b = gℓ trong thuật toán 1 (bước 9.4.4) chỉ cần đúng 1 phép toán nhóm nên ta có kết quả sau. Kết quả 3. Số phép toán nhóm tối đa của thuật toán 1, ký hiệu Cost1(k,m), được đánh giá theo công thức sau Cost1(k,m)=   k 1w w mC . (3.7) Từ (2.1) và (3.7) ta thu được hệ quả sau đây: Hệ quả 4. Cost0(k,m)  1 2 k  Cost1(k,m). Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 153 4. PHƯƠNG PHÁP BABY-STEPS, GIANT-STEPS TÌM LOGARIT CÓ TRỌNG SỐ THẤP 4.1. Thuật toán Trong phần này, chúng tôi đưa ra một mô tả của thuật toán như sau. Thuật toán 2 dựa vào phương pháp baby-steps, giant-steps tách ℓ=2n ℓ1+ ℓ2 với / 2n m    , sau đó xây dựng các tập Sbaby và Sgiant. Sau đó, thuật toán sẽ tìm va chạm trong tập Sbaby. Việc chứng minh tính đúng đắn của thuật toán được làm rõ trong mục 4.2.1. Thuật toán 2. (tính logarit trọng số nhỏ theo phương pháp baby-steps, giant-steps) Input: a  g, k, m với #g là số m-bits. Output: ℓ = logga nếu tìm được. Ngược lại trả về "Failure". 1 n  m/2; 2 Sbaby  MakeSlist(g,n,k); 3 g1  n2g ; 4 Sgiant  MakeSlist(g1,n,k); 5 (b1,ℓ1)  First(Sgiant); 6 while ((b1,ℓ1)  Null) do { 6.1 b  a*b1; 6.2 (b,ℓ2)  Search((b,.),Sbaby); 6.3 if ((b,ℓ2)  "Failure") then return (2nℓ1+ℓ2); 6.4 (b1,ℓ1)  Next((b1,ℓ1),Sgiant); }. 4.2. Đánh giá thuật toán 2 4.2.1. Khả năng tìm được các logarit trọng số thấp của thuật toán 2 Kết quả 5. Với mọi a = gℓ thỏa mãn các điều kiện sau ℓ = 2nℓ1+ ℓ2 (4.1) weight(ℓi)k và ℓi<2n (i=1,2) (4.2) Thì thuật toán 2 luôn tìm được ℓ. Chứng minh: Theo định nghĩa hàm MakeSlist(g1,n,k) đưa ra trong phần 2 thì Sbaby gồm các cặp (b,ℓ) trong đó weight(ℓ)k, ℓ<2n và b=gℓ còn Sgiant gồm các cặp (b,ℓ) trong đó weight(ℓ)k, ℓ<2n và b=g1ℓ =        n2g . Từ (4.2) thì luôn tồn tại cặp (b2,ℓ2)Sbaby và cặp (b1,ℓ1)Sgiant tức là b2 = gℓ2 còn b1 = g1ℓ1 = 1 2ng        do đó, b=a*b1=gℓ* 1 2ng        =gℓ2=b2 nên, Search((b,.),Sbaby)=(b2,ℓ2)"Failure" Điều kiện trong 6.3 xảy ra và ta tìm được ℓ=logga. Công nghệ thông tin & Cơ sở toán học cho tin học Đ. V. Sơn, N. T. Sơn, P. Q. Hoàng, “Phương pháp xây dựng logarit có trọng số thấp.” 154 Chú ý rằng từ hai điều kiện (4.1) và (4.2) về ℓ trong kết quả 5 ta có: weight(ℓ) = weight(ℓ1) + weight(ℓ2) (4.3) điều này có nghĩa thuật toán 2 có thể tìm được tất cả các logarit với trọng số không quá k, thậm chí có thể tìm được cả logarit với trọng số lên đến 2k. Chẳng hạn số các logarit trọng số 2k có thể tìm được theo thuật toán 2 là  2knC trên tổng số k2n2C . 4.2.2. Đánh giá Cost2 của thuật toán Theo công thức (3.7) trong kết quả 3 thì số phép toán nhóm cần thực hiện tại các bước 2 và 4 của thuật toán 2 đều là   k 1w w nC . Bước 3 của thuật toán này cần đến một phép tìm phần tử ngược trong nhóm, biết rằng công thức chung cho mọi nhóm là aℓ = a#gℓ nên số phép toán nhóm cần cho phép toán này là không quá 4n. Phần tìm logarit của thuật toán thực hiện tối đa   k 1w w nC vòng trong bước 6 mà mỗi vòng cần đúng một phép toán nhóm tại bước 6.1, do đó, ta có: Cost2(k,2n)     k 1w w n n4C3 (4.5) 5. KẾT LUẬN Bài báo đã đề xuất 2 thuật toán mới và đưa ra đánh giá độ phức tạp tính toán của các thuật toán này. Sau khi đánh giá ta thấy thuật toán 1 có độ phức tạp ít hơn so với thuật toán truyền thống, thuật toán đề xuất thứ 2 có thể tìm các logarit trọng số lên đến 2k. Tuy nhiên, thuật toán 2 tốn bộ nhớ lưu trữ, vì vậy, nhóm sẽ nghiên cứu cải tiến thuật toán 2 bằng cách sử dụng hàm băm mật mã. Hướng nghiên cứu tiếp theo của nhóm sẽ sử dụng hàm băm để tiết kiệm bộ nhớ lưu trữ dựa trên kết quả [6]. TÀI LIỆU THAM KHẢO [1]. V. Miller.Use of elliptic curves in cryptography. In H. Williams, editor, Advances in Cryptology, Proc. Eurocrypt '85, volume 218 of Lecture Notes in Computer Csience, pages 417-426, Springer-Verlag, 1985. [2]. A. Odlyzko. Discrete logarithms in finite fields and their cryptographyc significance. In Advances in Cryptology, Proc. Eurocrypt '84, volume 209 of Lecture Notes in Computer Csience, pages 224-313, Springer-Verlag, 1985. [3]. D. Shanks, Class number, a theory of factorization, and general. In 1969 Number Theory Institue, Stony Brook, N. Y., volume 20 of Proc. Sympos. Pure Math., pages 415-440. Amer. Math. Soc., 1971. [4]. S. Kim, J. H. Cheon, Parameterized splitting systems for the discrete logarithm, IEEE transactions on Information Theory, 2009. [5]. A. May, I. Ozerov A generic algorithm for small weight discrete logarithm in composite groups, 2014. [6]. B. Kacsmar, S. Plosker, R. Henry, Computing Low-weght discrete logarithms, 24th Annual Conference on Selected Areas in Cryptography (SAC 2017). [7]. D.R. Stinson Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem, 2001. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 52, 12 - 2017 155 [8]. Jung Hee Chenon, Hong TaeKim, Analysis of Low Hamming weight products, Discrete applied mathematics, 2008. ABSTRACT A BUIDING METHOD OF SET Slist FOR LOW WEIGHT LOGARITS In this paper, some methods construction set Slist, consist low-weight logarithm for solve discrete logarithm problem are described. Original algorithm construction set Slist is described, then two new algorithms in section 3, 4 are proposed; Complexity of new algorithms is evaluated. The proposed algorithm uses much memory. In the future, method using hash function for reducing storage memory, based on [6] will be researched. Keywords: Algorithm solve discrete logarithm, Solve low-weight discrete logarithm. Nhận bài ngày 11 tháng 07 năm 2017 Hoàn thiện ngày 03 tháng 08 năm 2017 Chấp nhận đăng ngày 20 tháng 12 năm 2017 Địa chỉ: 1Ban Cơ yếu chính phủ; 2Học viện Kỹ thuật Mật mã, Ban Cơ yếu chính phủ. *Email:nguyenthanhson@nacis.gov.vn.