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


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

  • $\begingroup$ 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?? $\endgroup$ – Mary Star Jun 11 '15 at 23:07
  • $\begingroup$ It looks OK to me. $\endgroup$ – Clement C. Jun 11 '15 at 23:15
  • $\begingroup$ Ok... Thanks a lot!! :-) $\endgroup$ – Mary Star Jun 11 '15 at 23:23
  • $\begingroup$ Could you take also a look at my other question: math.stackexchange.com/questions/1322188/rsa-signature-system ?? $\endgroup$ – Mary Star Jun 12 '15 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.