Bài giảng "Mật mã ứng dụng: Bài toán logarit rời rạc và Diffie-Hellman" trình bày các nội dung chính sau đây: Định nghĩa Nhóm; Cấp của một phần tử trong nhóm; Hàm logarit rời rạc và hàm mũ; Bài toán Logarit rời rạc; . Mời các bạn cùng tham khảo! | Mật mã ứng dụng Bài toán logarit rời rạc và Diffie-Hellman Nội dung Bài toán Logarit rời rạc Bài toán Diffie-Hellman Định nghĩa Nhóm Một nhóm Abel quot thoả mãn các tính chất sau 1. Có phần tử đơn vị 1 thoả mãn 1 1 2. Mọi phần tử đều khả nghịch thoả mãn 1 3. Kết hợp ta có 4. Giao hoán ta có Cấp của một phần tử trong nhóm Cấp của phần tử ký hiệu ord a là số quot gt 0 nhỏ nhất thoả mãn 1 . Định lý Lagrange Trong nhóm hữu hạn với lực lượng ta có ord . Hệ quả Trong nhóm hữu hạn với lực lượng ta có quot 1. Ký hiệu 2 0 là nhóm con sinh bởi . Nhóm vòng Ký hiệu quot quot 0 là nhóm con sinh bởi quot . Nếu quot thì quot là một phần tử sinh của . Khẳng định quot ord quot . Định nghĩa G là nhóm vòng nếu có g thoả mãn Hàm logarit rời rạc và hàm mũ Khẳng định Nếu là nhóm vòng cấp 0 và là phần tử sinh thì quan hệ 1 quot là 1-to-1 giữa 0 1 0 1 và . Hàm mũ x à gx Hàm logarit rời rạc gx à x Tính ngẫu nhiên của lũy thừa 627x mod 941 Bài toán Logarit rời rạc Xét là một phần tử sinh của ℤ và ℎ ℤ . Bài toán Logarit rời rạc DLP là bài toán tìm một số mũ 1 thỏa mãn quot ℎ mod . Số 1 được gọi là logarit rời rạc cơ sở của ℎ và ký hiệu Dlog ℎ . Bài tập Hãy tính các logarit rời rạc sau. 1. Dlog amp 13 trong modun nguyên tố 23 2. Dlog 22 trong modun nguyên tố 47. 3. Dlog amp 608 trong modun nguyên tố 941. Tính Logarit rời rạc Xét số nguyên tố 56509 và ta có thể kiểm tra 2 là một căn nguyên thủy modun . Làm thế nào để tính log amp 38679 Một phương pháp là tính 2 2 2 amp 2 mod 56509 cho đến khi được lũy thừa bằng 38679. Bạn có thể kiểm tra rằng 2 amp 38679 mod 56509. Nội dung Bài toán Logarit rời rạc Bài toán Diffie-Hellman Bài tập Hãy tính hai giá trị sau trong ℤ . DH 10 5 DH amp 12 9 biết rằng 2 1 2 4 8 3 6 12 11 9 5 10 7 7 1 7 10 5 9 11 12 6 3 8 4 2 DHg ga gb gab mod p Nhắc lại Giao thức Diffie-Hellman 1977 Xét nhóm vòng G G Zp với cấp n Lấy một phần tử sinh g thuộc G . G 1 g g2 g3 gn-1 Alice Bob Chọn ngẫu nhiên a in 1 n Chọn ngẫu nhiên b trong 1 n A ga B gb Ba g b a ab g a b Ab kAB g
