Phát triển thuật toán của Danied Shank để giải bài toán logarit rời rạc trên vành Zn

Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn.
Nội dung trích xuất từ tài liệu:
Phát triển thuật toán của Danied Shank để giải bài toán logarit rời rạc trên vành ZnNghiên cứu khoa học công nghệ PHÁT TRIỂN THUẬT TOÁN CỦA DANIED SHANK ĐỂ GIẢI BÀI TOÁN LOGARIT RỜI RẠC TRÊN VÀNH Zn Lê Văn Tuấn1*, Bùi Thế Truyền2 Tóm tắt: Bài viết này giới thiệu phương pháp tính logarit rời rạc trên trường hữu hạn Zp của Danied Shanks và của Polig-Hellman. Dựa trên phương pháp của Danied Shanks, chúng tôi phát triển nó để giải bài toán logarit rời rạc trên vành Zn. Kết quả nghiên cứu được ứng dụng vào phân tích độ an toàn của lược đồ chữ ký số trên bài toán logarit rời rạc trong vành ZnTừ khoá: Vành hữu hạn, Trường hữu hạn, Bài toán logarit rời rạc. 1. MỞ ĐẦU Tương tự bài toán phân tích số nguyên lớn ra thừa số, bài toán logarit rời rạcthuộc lớp bài toán khó giải. Hiện nay, một lớp hệ mật khóa công khai và biến thểcủa nó được xây dựng dựa trên độ khó của bài toán này. Tuy nhiên, bài toán logaritrời rạc không phải khó giải trong mọi trường hợp. Chính vì thế, các nhà khoa họcđã lợi dụng những trường hợp không khó của bài toán để xây dựng các thuật toángiải bài toán logarit rời rạc. Một thực tế cho thấy, đa số các thuật toán giải bài toánlogarit rời rạc hiện nay, chỉ áp dụng được trên trường hữu hạn Zp. Trong khi đó,một số hệ mã khóa công khai và các biến thể của nó được xây dựng trên cấu trúcvành Zn. Với mục tiêu nhằm loại bỏ những mầm mống không an toàn cho các hệmật khoá công khai và các hệ chữ ký số dựa trên độ khó của bài toán logarit rời rạctrên vành Zn, trên cơ sở tìm hiểu những thuật toán giải bài toán logarit rời rạc đãđược công bố trên thế giới[2][3][5] và một số công trình liên quan đến bài toánlogarit rời rạc trên vành Zn,[1][4][8], chúng tôi phát triển thuật toán Baby stepGiant Step của Danied Shanks để giải được bài toán logarit rời rạc trên vành Zn.Giả sử nhóm cyclic G= là nhóm con của nhóm nhân và cỡ bậc của g là mbit. Khi đó bậc của g thuộc đoạn [2m-1,2m-1] và khoảng tìm giá trị logarit rời rạcthuộc đoạn [0,2m-1]. Trong bài viết này, chúng tôi phát triển thuật toán Baby-stepGiant-step của Danied Shanks để tìm logarit rời rạc trong nửa đoạn [0,2m-1) trênvành Zn. Việc tìm logarit rời rạc thuộc đoạn [2m-1,2m-1] nằm ngoài phạm vi nghiêncứu trong bài báo này. Kết quả nghiên cứu là cơ sở để xây dựng tiêu chuẩn tham sốan toàn [9] cho hệ chữ ký số, hoặc các biến thể của nó dựa vào độ khó của bài toánlogarit rời rạc trên vành Zn. 2. CƠ SỞ TOÁN HỌC2.1. Một số ký hiệu, định nghĩa và tính chất Bitlength(M): Hàm trả về số bít của số nhị phân biểu diễn M. #G: Chỉ bậc của nhóm G. OrdG(g): Chỉ bậc của phần tử g thuộc tập G. Định nghĩa 2.1: Cho G là một nhóm nhân với phần tử đơn vị là 1 và g ∈ G.Nếu tồn tại số tự nhiên d sao cho =1 (2.1)thì g được gọi là “có cấp hữu hạn” và giá trị d nhỏ nhất thỏa mãn đẳng thức (2.1)được gọi là “cấp của g trong G” và ký hiệu là ord(g) mod G hay .■Tạp chí Nghiên cứu KH&CN quân sự, Số 48, 04 - 2017 129 Công nghệ thông tin & Cơ sở toán học cho tin học Lưu ý. Nếu G là nhóm hữu hạn thì mọi phần tử trong G đều có cấp hữu hạn và luôn là ước bậc của nhóm G, ký hiệu |#G, ngoài ra, nếu số tự nhiên dthỏa mãn (2.1) thì cũng là ước của d. Định lí 2.1: Cho G= Zn*(n= pxq), [2m-1,2m-1], 1k1,k2 2m-1, thoảmãn: gk1=b mod n (2.2) k2và g =b mod n (2.3)thì k1=k2. Chứng minh: Giả sử k1 k2 không giảm tổng quát, giả sử k1>k2, từ (2.2) và (2.3)ta có = 1 mod n, khi đó (k1-k2), nghĩa là k1-k2 2m-1, điều này mẫu m-1thuẫn với giả thiết 1k1,k2 2 ■ Định lý 2.2 [11]: Giả sử m1...m Γ là các số nguyên dương nguyên tố cùng nhau từng đôi một vàcho a1...a Γ là các số nguyên. Khi đó, hệ r đồng dư thức x  a i (modm i ) (1 ...