Để thử những gì đã cố gắng, chúng ta phải xác định $H$ với đầu ra trên tập hợp tất cả các bản mã ElGamal. Điều này là có thể, và tôi giả định điều này trong đoạn tiếp theo.
Trái ngược với RSA trong sách giáo khoa, mã hóa ElGamal không phải là một chức năng: mã hóa lặp đi lặp lại một bản rõ nhất định tạo ra (với xác suất áp đảo) các bản mã khác nhau. Do đó, khi chúng tôi cố gắng xác minh chữ ký như trong câu hỏi, không có lý do gì mã hóa chữ ký sẽ mang lại hàm băm ban đầu và (với xác suất áp đảo) việc xác minh chữ ký sẽ không thành công. Hệ thống chữ ký được xem xét trong câu hỏi không hợp lý.
Để đơn giản, hãy xem xét ElGamal trong nhóm nhân modulo $p$, lưu ý $\mathbb Z_p^*$, với $p$ và $(p-1)/2$ số nguyên tố và $G$ như vậy mà $G^{(p-1)/2}\bmod p\,=\,p-1$:
- Khóa riêng là bí mật ngẫu nhiên $x\in[0,p-1)$, khóa công khai là $X:=G^x\bmod p\in[1,p)$.
- Mã hóa bản rõ tùy ý $M\in[1,p)$ đi
- tạo bí mật ngẫu nhiên phù du $y\in[0,p-1)$
- tính toán $Y:=G^y\bmod n$
- tính toán $Z:=M\cdot X^y\bmod n$
- đầu ra bản mã $(Y,Z)$
- Giải mã bản mã tùy ý $(Y,Z)\in[1,p)\times[1,p)$ đầu ra $M':=Y^{n-1-x}\cdot Z\bmod n$.
$M'=M$ bất kể $y$. Gợi ý bằng chứng: Định lý nhỏ Fermat.
Trái ngược với RSA trong sách giáo khoa, biến thể này của ElGamal gần giống như IND-CPA, nhưng không hoàn toàn. Gợi ý chứng minh: xét quan hệ giữa biểu tượng huyền thoại của $\left(\frac M p\right)$, $\left(\frac X p\right)$, $\left(\frac Y p\right)$. Chúng tôi bỏ qua vấn đề tương đối nhỏ này sau đây.
Một trong những nỗ lực đơn giản nhất để khắc phục sự cố được nêu trong đoạn thứ hai của câu trả lời này là khắc phục $y=1$, do đó $Y=G$. Lược đồ chữ ký của câu hỏi sau đó có thể sử dụng hàm băm $H$ với đầu ra $H(m)$ trong miền đầy đủ $[1,p)$ Như là
$$H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{ với }b=64\left\lceil\log_2(p)/64 +2\right\ceil$$
và sau đó
- Khóa riêng và khóa chung giống như trong mã hóa
- Chữ ký của $m$ Là $\sigma:=G^{n-1-x}\cdot H(m)\bmod n$
- kiểm tra xác minh $\sigma\cdot X\bmod n=H(m)$.
Ít nhất, việc xác minh thành công mà không cần thay đổi, do đó sơ đồ chữ ký này là hợp lý. Nhưng nó không an toàn ngay cả theo tiêu chí đơn giản nhất UF-KOA.
Những nỗ lực đơn giản khác cũng thất bại, bao gồm
- chế tạo $y$ một bí mật được thêm vào khóa riêng, với $Y:=G^y\bmod n$ và $Y':=X^y\bmod n$ được thêm vào khóa công khai
- chế tạo $y$ một hàm băm của tin nhắn $m$
- chế tạo $Y$ một hàm băm của tin nhắn $m$
- rõ ràng, bất kỳ thứ gì hoạt động trong một nhóm tùy ý khi sử dụng mã hóa ElGamal và chữ ký là một thành phần nhóm dưới dạng đầu ra giải mã ElGamal.
Mặc dù điều này không áp dụng cho ElGamal, nhưng một vấn đề khác phát sinh khi cố gắng xây dựng chữ ký từ lược đồ mã hóa khóa công khai chung và hàm băm trên miền bản mã của nó: việc giải mã một bản mã tùy ý có thể không thành công (và đối với các hệ thống thực tế như RSA-OAEP, RSAES-OAEP, RSAES-PKCS1-v1_5). Đó thực sự là một tính năng vì lợi ích của IND-CCA Bảo vệ.
Không có cách chung để xây dựng chữ ký an toàn từ mã hóa khóa công khai an toàn. Ngay cả chữ ký RSA-FDH cũng không hoạt động theo cách đó: nó xây dựng chữ ký từ hoán vị cửa sập một chiều và hàm băm trên miền của hoán vị.
