# Using ElGamal instead of RSA in FDH

In RSA-FDH to sign a message $$m$$, we apply a hash function $$H$$ and then "decrypt" it using the private key $$d$$, so $$Sign(m) = H(m)^d \mod N =: \sigma$$ and then to verify, we use the public key, resulting in $$H(m) = \sigma^e \mod N$$ if all goes well.

Why do we have to use RSA for this instead of something else, for example ElGamal? Is it because the ciphertext in ElGamal is twice as long as the plaintext or is there some adversary forgery possible which is not possible when using RSA-FDH?

• You should not use word decryption for signing and encryption for verification. They are completely different concepts that only have little connection on the RSA!. May 6, 2022 at 14:45

In order to try what's attempted, we'd have to define $$H$$ with output on the set of all ElGamal ciphertexts. This is possible, and I assume this in the next paragraph.

Contrary to textbook RSA, ElGamal encryption is not a function: repeatedly encrypting a given plaintext yields (with overwhelming probability) different ciphertexts. Therefore, when we attempt to verify a signature as in the question, there is no reason that encryption of the signature would yield the original hash, and (with overwhelming probability) the signature verification would fail. The signature system considered in the question is not sound.

For simplicity, consider ElGamal in the multiplicative group modulo $$p$$, noted $$\mathbb Z_p^*$$, with $$p$$ and $$(p-1)/2$$ prime, and $$G$$ such that $$G^{(p-1)/2}\bmod p\,=\,p-1$$:

• Private key is a random secret $$x\in[0,p-1)$$, public key is $$X:=G^x\bmod p\in[1,p)$$.
• Encryption of arbitrary plaintext $$M\in[1,p)$$ goes
• generate ephemeral random secret $$y\in[0,p-1)$$
• compute $$Y:=G^y\bmod n$$
• compute $$Z:=M\cdot X^y\bmod n$$
• output ciphertext $$(Y,Z)$$
• Decryption of arbitrary ciphertext $$(Y,Z)\in[1,p)\times[1,p)$$ outputs $$M':=Y^{n-1-x}\cdot Z\bmod n$$.

$$M'=M$$ regardless of $$y$$. Proof hint: Fermat's little theorem.

Contrary to textbook RSA, this variant of ElGamal comes close to be IND-CPA, but is not quite. Proof hint: consider relations between the Legendre symbols of $$\left(\frac M p\right)$$, $$\left(\frac X p\right)$$, $$\left(\frac Y p\right)$$. We ignore this relatively minor issue in the following.

One of the simplest attempt to correct the issue raised in the second paragraph of this answer would be to fix $$y=1$$, thus $$Y=G$$. The question's signature scheme can then use a hash $$H$$ with output $$H(m)$$ in the full domain $$[1,p)$$ such as $$H(m):=\big(\operatorname{SHAKE256}(m,b)\bmod p-1\big)+1\text{ with }b=64\left\lceil\log_2(p)/64+2\right\rceil$$ and then

• Private and public key are as in the encryption
• Signature of $$m$$ is $$\sigma:=G^{n-1-x}\cdot H(m)\bmod n$$
• Verification checks $$\sigma\cdot X\bmod n=H(m)$$.

At least, verification succeeds absent alterations, thus this signature scheme is sound. But it's insecure even per the simplest criteria UF-KOA.

Other simple attempts also fail, including

• making $$y$$ a secret added to the private key, with $$Y:=G^y\bmod n$$ and $$Y':=X^y\bmod n$$ added to the public key
• making $$y$$ a hash of the message $$m$$
• making $$Y$$ a hash of the message $$m$$
• apparently, anything working in an arbitrary group as ElGamal encryption uses, and the signature is a group element as ElGamal decryption outputs.

While this does not apply to ElGamal, another issue arises when trying to construct signature from a general public-key encryption scheme, and a hash on it's ciphertext domain: decryption of an arbitrary ciphertext can fail (and does for practical systems like RSA-OAEP, RSAES-OAEP, RSAES-PKCS1-v1_5). That's actually a feature in the interest of IND-CCA security.

There's no general way to construct secure signature from secure public-key encryption. Even RSA-FDH signature does not work that way: it constructs signature from a one-way trapdoor permutation and a hash on the permutation's domain.

This had been reiterated many times before in this community.

Digital signature is NOT encrypt with private key. RSA is the only bijection we know where both the public and the private operations are exponentiation modulo a public modulus.

The public and private key in ElGamal serve different roles: the private key is the exponent whereas the public key is the power (and the modulus is a public and shared parameter).

• More precisely: In order to try what's attempted, we'd have to define $H$ with output on the set of all ElGamal ciphertexts. This is possible. But since ElGamal encryption is randomized, there is no reason that encryption of the signature would yield the hash. Thus the signature system considered is not sound. Note: the last paragraph of the current answer would apply if we tried to encrypt with the private key, but the question does not: the proposal is to «… then "decrypt" (the hash) using the private key », which in ElGamal is possible, for proper hash.
– fgrieu
May 4, 2022 at 10:20