Bài báo này trình bày về phương pháp baby-step giant-step và phương pháp baby-step giant-step tìm logarit rời rạc trong miền cho trước (thuật toán cải biên). Và sau đó đưa ra đánh giá về khả năng thành công của thuật toán cải biên dựa vào việc định lượng xác suất thành công của thuật toán. Xác suất thành công của thuật toán được xác định phụ thuộc vào kích thước của số nguyên tố p được sử dụng trong bài toán logarit rời rạc. | Tìm Logarit theo phương pháp Baby-Step Giant-Step Nghiên cứu khoa học công nghệ TÌM LOGARIT THEO PHƯƠNG PHÁP BABY-STEP GIANT-STEP Nguyễn Thanh Sơn* Tóm tắt: Bài báo này trình bày về phương pháp baby-step giant-step và phương pháp baby-step giant-step tìm logarit rời rạc trong miền cho trước (thuật toán cải biên). Và sau đó đưa ra đánh giá về khả năng thành công của thuật toán cải biên dựa vào việc định lượng xác suất thành công của thuật toán. Xác suất thành công của thuật toán được xác định phụ thuộc vào kích thước của số nguyên tố p được sử dụng trong bài toán logarit rời rạc. Từ khóa: Thuật toán tính logarit rời rạc, Baby-step, Giant-step, Xác suất thành công, Kích thước p. 1. MỞ ĐẦU Việc ứng dụng bài toán logarit rời rạc (DLP) trong mật mã đã được sử dụng rộng rãi nhằm bảo mật thông tin. Việc xây dựng các thuật toán mật mã ứng dụng DLP trong bảo mật thông tin đã được triển khai phổ biến trên thế giới. Các hệ mật tiêu biểu có thể kể đến như giao thức trao đổi khóa Difie-Hellman, ElGamal, Trong các hệ mật đó, các tham số mật mã được sử dụng trong hệ mật đóng vai trò cực kỳ quan trọng, quyết định tính an toàn của hệ mật. Các tổ chức tiêu chuẩn quốc tế đã công bố các tiêu chuẩn cho tham số cho bài toán DLP, tuy vậy, trong các tiêu chuẩn này không đưa ra cơ sở lý thuyết để lựa chọn các tham số như vậy. Nhằm đánh giá một cách định lượng về độ an toàn của tham số p, bài báo sẽ trình bày việc đánh giá xác suất thành công khi giải bài toán logarit rời rạc trên trường hữu hạn bằng thuật toán baby-step giant-step và thuật toán baby-step giant-step cải biên. Đầu tiên, chúng tôi nhắc lại định nghĩa bài toán logarit rời rạc. Định nghĩa: (Bài toán Logarit rời rạc - DLP) Cho số nguyên tố p , một phần tử sinh của nhóm nhân Z *p và một phần tử Z *p . Hãy tìm số nguyên x , 2 x p 2 , sao cho x (mod p) . Ta có thể tìm x bằng phép tính x log . Độ khó giải của bài toán DLP là độc lập với việc chọn phần tử .
