# ElGamal signature scheme

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

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$)
• I understand!! Thank you very much!! :-)  For the second question we can use the formulas of the first question and then we get the following: $$r' \equiv r^2 \pmod p \Rightarrow r' \equiv 2 \pmod {23} \\ s \equiv 2^{-1} sr \pmod q \Rightarrow s' \equiv 5 \pmod {11}$$ Is this correct?? – Mary Star Jun 11 '15 at 23:07