tailieunhanh - Đề xuất thuật toán sinh số giả ngẫu nhiên có chu kỳ cực đại bằng phương pháp đồng dư tuyến tính

Bài viết đề xuất phương pháp sinh dãy số giả ngẫu nhiên có chu kỳ cực đại dựa trên phương pháp đồng dư tuyến tính. Mục đích là thỏa thuận khóa hiệu quả đơn giản, dùng trong liên lạc mật dựa trên phương pháp đồng dư tuyến tính. Khóa tạo ra có chu kỳ cực đại, không có chu kỳ con. | Đề xuất thuật toán sinh số giả ngẫu nhiên có chu kỳ cực đại bằng phương pháp đồng dư tuyến tính Kỹ thuật điều khiển & Điện tử ĐỀ XUẤT THUẬT TOÁN SINH SỐ GIẢ NGẪU NHIÊN CÓ CHU KỲ CỰC ĐẠI BẰNG PHƯƠNG PHÁP ĐỒNG DƯ TUYẾN TÍNH Lê Hải Triều1*, Trần Xuân Ban2 Tóm tắt: Bài báo đề xuất phương pháp sinh dãy số giả ngẫu nhiên có chu kỳ cực đại dựa trên phương pháp đồng dư tuyến tính. Mục đích là thỏa thuận khóa hiệu quả đơn giản, dùng trong liên lạc mật dựa trên phương pháp đồng dư tuyến tính. Khóa tạo ra có chu kỳ cực đại, không có chu kỳ con. Từ khóa: Sinh số giả ngẫu nhiên; Đồng dư tuyến tính. 1. MỞ ĐẦU Việc sinh số ngẫu nhiên có nhiều ý nghĩa trong thực tiễn, đặc biệt trong lĩnh vực bảo mật thông tin, chẳng hạn các khóa mã đòi hỏi phải được chọn một cách ngẫu nhiên, nhằm chống lại các tấn công vét cạn (brute force) [1, 2, 3]. Hiện nay, một hệ mật mã được cho là an toàn nếu không gian khóa là đủ lớn và việc chọn khóa trong đó phải là ngẫu nhiên theo nghĩa độc lập, đồng xác suất [5, 6, 7]. Tuy nhiên, việc sinh số hoàn toàn ngẫu nhiên bằng các thuật toán là rất khó khăn, tốn kém [8]. Bài báo này trình bày thuật toán sinh số giả ngẫu nhiên bằng phương pháp đồng dư tuyến tính, dãy số được tạo ra tuần hoàn, có chu kỳ cực đại và không tồn tại chu kỳ con trong khoảng chu kỳ cực đại đó. 2. ĐẶT BÀI TOÁN Xét phương trình đồng dư tuyến tính 1 có dạng sau: ax b mod n (1) với a, b, n là các tham số nguyên, trong đó n 2 Để giải phương trình (1) ta áp dụng các định lý sau: . Định lý 1 Gọi gcd a, n d 1 là hàm trả về ước số chung lớn nhất của a và n, khi đó: a) Phương trình (1) có d nghiệm phân biệt nếu b chia hết cho d (ký hiệu d | b ). b) Phương trình (1) vô nghiệm nếu b không chia hết cho d (ký hiệu ∤ b). Để chứng minh Định lý 1 ta áp dụng bổ đề sau: . Bổ đề: Cho trước 2 số nguyên không âm a và n ( n 2) , khi đó, a là khả đảo theo mod n nếu và chỉ nếu gcd (a, n) 1 , tức là a và n nguyên tố cùng .