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. | 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 } () thường là k không lớn với weight(ℓ)
