1
$\begingroup$

Alice uses an ElGamal signature in group $(Z/pZ)^{*}$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in \{0, 1, \dots, q-1\}$ where $q/p-1$ is prime number and the order of the base $g$ and then calculates $r\equiv g^{k}\pmod p$ and $s\equiv k^{-1}(m+ar)\pmod q$ where $a$ is the private key of Alice.For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$ (without using the private key). The public key of Alice is $y=13$

Could someone give some hints on how to construct this signature in message $m'=3$?

$\endgroup$
1
$\begingroup$

Just read the original paper for ElGamal signatures. Especially one of the attacks in section IV. B should help you out. Alternatively, the Wikipedia article about ElGamals signatures also has a section about existential forgeries.

Since this is clearly homework, I'll leave the rest up to you. One last hint: Use q instead of p-1, since you're actually in a smaller multiplicative subgroup.

$\endgroup$

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.