Chuyên Đề Các hệ mật khoá công khai thác

Tên đề tài
Các hệ mật khoá công khai thác​
Trong chương này ta sẽ xem xét một số hệ mật khoá công khai khác.


Hệ mật Elgamal dựa trên bài toán logarithm rời rạc là bài toán được dùng nhiều trong nhiều thủ tục mật mã. Bởi vậy ta sẽ dành nhiều thời gian để thảo luận về bài toán quan trọng này. ở các phần sau sẽ xem xét sơ lược một số hệ mật khoá công khai quan trọng khác bao gồm các hệ thống loại Elgamal dựa trên các trường hữu hạn và các đường cong elliptic, hệ mật xếp ba lô
Merkle-Helman và hệ mật McElice.

5.1. Hệ mật Elgamal và các logarithm rời rạc.
Hệ mật Elgamal được xây dựng trên bài toán logarithm rời rạc . Chúng
ta sẽ bắt đầu băng việc mô tả bài toán khi thiết lập môi trường hữu hạn
Zp, p là số nguyên tố ( hình 5.1) ( Nhớ lại rằng nhóm nhân Zp* là nhóm cyclic và phần tử sinh của Zp* được gọi là phần tử nguyên thuỷ).


Bài toán logarithm rời rạc trong Zp là đối tượng trong nhiều công trình nghiên cứu và được xem là bài toán khó nếu p được chọn cẩn thận. Cụ thể không có một thuật toán thời gian đa thức nào cho bài toán logarithm rời rạc. Để gây khó khăn cho các phương pháp tấn công đã biết p phải có ít nhất 150 chữ số và (p-1) phải có ít nhất một thừa số nguyên tố lớn. Lợi thế của bài
toán logarithm rời rạc trong xây dượng hệ mật là khó tìm được các logarithm rời rạc ,song bài toán ngược lấy luỹ thừa lại có thể tính toán hiệu quả theo thuật toán "bình phương và nhân". Nói cách khác , luỹ thừa theo modulo p là hàm một chiều với các số nguyên tố p thích hợp.