Is ElGamal Signature Scheme Secure Without Using a Hash Function?

[mathmari]

Hey!

Alice uses the ElGamal signature scheme in the group $(\mathbb{Z}/p\mathbb{Z})^{\star}$ without the use of a hash function. To sign the message $m \in (\mathbb{Z}/p\mathbb{Z})^{\star}$ she calculates the signature $(r,s)$ as follows:
she choose a random $k \in \{0, 1, \dots , q-1\}$, where $q \mid p-1$ is a prime and the order of the basis $g$, and then she calculates $$r \equiv g^k \pmod p \ \ , \ \ s \equiv k^{-1} (m+ar) \pmod q$$ where $a$ is the private key.

1. Show that given the signature$(r, s)$ at the message $m$ we can construct the signature at the message $rm \pmod q$ (without knowing the private key of Alice).
   
2. For $p=23, g=2, q=11$, we are given given the signature $(18, 3)$ at the message $m=2$. Construct a signature at the message $m'=3$ (without calculating the private key). The public key of Alice is $y=13$.

Could you give me some hints for the first question?? How can we find the signature at the message $rm \pmod q$ ?? (Wondering)

 

[Sudharaka]

Hey!

Alice uses the ElGamal signature scheme in the group $(\mathbb{Z}/p\mathbb{Z})^{\star}$ without the use of a hash function. To sign the message $m \in (\mathbb{Z}/p\mathbb{Z})^{\star}$ she calculates the signature $(r,s)$ as follows:
she choose a random $k \in \{0, 1, \dots , q-1\}$, where $q \mid p-1$ is a prime and the order of the basis $g$, and then she calculates $$r \equiv g^k \pmod p \ \ , \ \ s \equiv k^{-1} (m+ar) \pmod q$$ where $a$ is the private key.

1. Show that given the signature$(r, s)$ at the message $m$ we can construct the signature at the message $rm \pmod q$ (without knowing the private key of Alice).
2. For $p=23, g=2, q=11$, we are given given the signature $(18, 3)$ at the message $m=2$. Construct a signature at the message $m'=3$ (without calculating the private key). The public key of Alice is $y=13$.

Could you give me some hints for the first question?? How can we find the signature at the message $rm \pmod q$ ?? (Wondering)

Hi mathmari,

Let me give you a hint. Probably if you are taking a Cryptography course you might have learned (which I assume seeing your previous questions about the ElGamal scheme) that the message is hashed before being encrypted using the ElGamal scheme.

In this question that hashing process was not done. This makes the scheme vulnerable to an attack known as Existential Forgery. All you got to know about this is mentioned in the Wikipedia link.

https://en.wikipedia.org/wiki/ElGamal_signature_scheme#Existential_forgery