Chúng ta đã dành thời gian đáng kể để xét bài toán logarithm rời rạc (DL) vào việc phân tích số. Ta sẽ còn trở lại hai bài toán này trong các loại hệ mật và các giao thức mã khác nhau. | Vietebooks Nguyễn Hoàng Cương điều này kéo theo Xi 1 L2 Pi i 0 Vì rằng xi 1 L2 p nên thuật toán là đúng. Các chi tiết dành cho độc giả xem xét. . TRƯỜNG Hũu HẠN VÀ CÁC HỆ THốNG ĐƯƠNG CONG ELLIPTIC. Chúng ta đã dành thời gian đáng kể để xét bài toán logarithm rời rạc DL vào việc phân tích số. Ta sẽ còn trở lại hai bài toán này trong các loại hệ mật và các giao thức mã khác nhau. Bài toán DL đã được nghiên cứu trong trương hữu hạn Zp tuy nhiên việc xét bài toán này theo các thiết lập khác nhau cũng rất có ích và là chủ đề của phần này. Hệ mật Elgamal có thể được áp dụng trong một nhóm bất kì mà bài toán DL là khó giải. Ta đã dùng nhóm nhân Zp tuy nhiên các nhóm khác cũng là những ứng cử viên thích hợp. Trước hết ta phát biểu bài toán DL trong một nhóm hữu hạn nói chung G hữu hạn và ở đó kí hiệu phép lấy nhóm là dấu o . Dạng bài toán tổng quát hoá như vậy trình bài trên hình . Dễ dàng xác định một hệ mật Elgamal trong nhóm con H theo cách tương tự đã mô tả trong Zp và được trình bày trên hình . Chú ý rằng phép mã hoá yêu cầu dùng số nguyên k ngẫu nhiên sao cho 0 k I H I - 1. Tuy nhiên nếu Alice không biết cấp của nhóm con H thì cô ta có thể tạo một số nguyên k thoả mãn 0 k I G I -1 khi đó sẽ không có bất kì sự thay đổi nào trong quá trình mã và giải mã. Cũng cần chú ý là nhóm G không phải là nhóm Aben Tuy H vẫn là nhóm Aben vì nó là nhóm cyclic . Trang 16 Vietebooks Nguyễn Hoàng Cương Hình . Bài toán logarithm rời rạc trong G 0 Đặc trưng của bài toán I G a P trong đó G là một nhóm hữu hạn với phép lấy nhóm o a e G và p e H trong đó H ai i 0 là một nhóm con sinh bởi a. Mục tiêu Tìm một số nguyên duy nhất a sao cho 0 a I H I -1 và aa p với kí hiệu aa có nghĩa là a o . . . o a a lần Ta sẽ kí hiệu số nguyên a này bằng logap Bây giờ ta sẽ trở lại bài toán DL tổng quát hoá . Nhóm con H được sinh bởi phần tử a tuỳ ý e G dĩ nhiên phải là nhóm con cyclic cấp I H I. Bởi vậy dạng bất kì của bài toán theo một nghĩa nào đó đều tương đương với bài toán DL trong một nhóm
