Phương pháp xây dựng tập Slist các logarit có trọng số thấp

Bài viết 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.
Nội dung trích xuất từ tài liệu:
Phương pháp xây dựng tập Slist các logarit có trọng số thấp Công nghệ thông tin & Cơ sở toán học cho tin học 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. 148 Đ. 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.” Nghiên cứu khoa học công nghệ 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, 2 ký hiệu Cost1(k,m), không đến Cost của thuật toán gốc, ký hiệu Cost0(k,m) tức là k 1 k 1 Cost0(k,m)  Cost1(k,m) (1.2) 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ũ x  x1 x2 x3 , với xi 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 ...