là tập hợp hữu hạn các thông điệp. A là tập hợp hữu hạn các chữ ký có thể được sử dụng. Không gian khóa K là tập hợp hữu hạn các khóa có thể sử dụng. Với mỗi khóa k ∈ K, tồn tại thuật toán chữ ký sigk ∈ S và thuật toán xác nhận chữ ký tương ứng verk ∈ V. Mỗi thuật toán sigk : P | Chương 7 1. P là tập hợp hữu hạn các thông điệp. 2. A là tập hợp hữu hạn các chữ ký có thể được sử dụng. 3. Không gian khóa K là tập hợp hữu hạn các khóa có thể sử dụng. 4. Với mồi khóa ke K tồn tại thuật toán chữ ký sigk e S và thuật toán xác nhận chữ ký tương ứng verk e V. Mồi thuật toán sigk P A và verk P X A true false là các hàm thỏa điều kiện true nêu y sig x Vx e P Vy e A ver x y if l êê Phương pháp chữ ký điện tử RSA Phương pháp chữ ký điện tử RSA được xây dựng dựa theo phương pháp mã hóa khóa công cộng RSA. Thuật toán . Phương pháp chữ ký điện tử RSA n pq với p và q là hai số nguyên tố lẻ phân biệt. Cho P C Zn và định nghĩa K n p q a b n pq p q là số nguyên tố ab 1 mod ộ n Giá trị n và b được công bố trong khi giá trị p q a được giữ bí mật. Với mỗi K n p q a b e K định nghĩa sigK x xa mod n và verK x y true x ỷ mod n với x y e Zn 192 Chữ ký điện tử Phương pháp chữ ký điện tử ElGamal Phương pháp chữ ký điện tử ElGamal được giới thiệu vào năm 1985. Sau đó Viện Tiêu chuẩn và Công nghệ Quốc gia Hoa Kỳ NIST đã sửa đổi bổ sung phương pháp này thành chuẩn chữ ký điện tử Digital Signature Standard- DSS . Khác với phương pháp RSA có thể áp dụng trong mã hóa khóa công cộng và chữ ký điện tử phương pháp ElGamal được xây dựng chỉ nhằm giải quyết bài toán chữ ký điện tử. Bài toán logarit rời rạc Phát biểu bài toán logarit rời rạc Cho số nguyên tố p gọi a e Zp là phần tử sinh generator và p e Zp . Cần xác định số nguyên dương a e Zp-1 sao cho a p modp Khi đó a được ký hiệu là loga p. Trên thực tế bài toán logarit rời rạc thuộc nhóm NP hay nói cách khác chưa có thuật toán có thời gian đa thức nào có thể giải quyết được vấn đề này. Với p có tối thiếu 150 chữ số và p - 1 có thừa số nguyên tố đủ lớn phép toán lũy thừa modulo p có thể xem như là hàm 1 chiều hay việc giải bài toán logarit rời rạc trên Zp xem như không thể thực hiện được. 193 Chương 7 Phương pháp ElGamal Trong phương pháp ElGamal một thông điệp bất kỳ có thể có nhiều chữ ký hợp .
