ElGamal signature scheme

Question

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.

• 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).

• 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$ ??

Answer 1

Caveat: did not carefully check, but I believe the following works.

For $m$, from the description of the scheme $r = g^k \mod p$ and $s= k^{-1}(m+ar) \mod q$. Thus, for message $m^\prime \stackrel{\rm def}{=} mr$, you need to forge (mod $q$) $$ r^\prime = g^{\ell} $$ with $\ell\in\mathbb{Z}_q^\ast$ and $$ s^\prime = \ell^{-1}(m^\prime+ar^\prime) = \ell^{-1}(mr+ar^\prime) . $$

Since all you know is $(r,s)$ and $m$, the "natural" way to do so is to try something like setting $s^\prime = sr$ and see what happens. $$ sr = k^{-1}(m+ar)r = k^{-1}(mr+ar^2) = k^{-1}(m^\prime+ar^2) $$ which looks promising. The next natural step is to set $r^\prime \stackrel{\rm def}{=}r^2\ (\text{mod } p)$, by looking at the expression above where the term $r^\prime$ should be. This is almost nice, as then $sr = k^{-1}(m^\prime+ar^\prime)$.

The only issue is that $r^\prime = r^2 = g^{2k}\ (\text{mod } p)$, but you only have a $k^{-1}$ above. To fix that, you need to get a $(2k)^{-1}= k^{-1}2^{-1}= 2^{-1}k^{-1}$ (mod $q$) there; i.e., to define $$ s^\prime \stackrel{\rm def}{=} 2^{-1} sr = (2k)^{-1}(m^\prime+ar^\prime) $$ as wished. ($\ell=2k$ mod $q$, $r^\prime = g^\ell = r^2$)