# Tag Info

4

The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm. If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher ...

1

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

1

Before continuing to read this answer, read my above hint: Try writing down all the equations for the different s and try to solve the system of equations. If you still can't solve this one, you may read the remainder of the answer. First observe that $s_1 \equiv k_1 \cdot h(m) + r_1\cdot x \pmod {53}$ and $s_2 \equiv k_2 \cdot h(m') + r_2\cdot x ... 1 Daniel Bleichenbacher has described such kind of attacks in his article Generating ElGamal signatures without knowing the secret key. (PDF) He noticed that if verifier would accept signatures where$r$is larger than$p$then any signature$(r,s)$on$H(M)$could be used to generate a signature$(r2, s2)$on arbitrary hash value$H(M2)$. For that attacker ... 1 It's not a complete answer because an adversary needs control on the random choice of a signing algorithm. First let me define ElGamal signature to not get lost in notation.$x \in N$is the secret key.$p$is a prime, it defines$Z_p^*$.$g$is a generator of$Z_p^*$.$y=g^x$and the public key is$(p, g, g^x)$. Then$k\$ is picked at random from ...

Only top voted, non community-wiki answers of a minimum length are eligible