# 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 There have been some research in Optimal Extension Fields (OEF), introduced at Crypto'98 by Bailey and Paar paper. The idea is to work in a field$GF(p^n)$with$p$prime and of the form$2^{32}\pm c$with small$c$for 32-bit CPUs ($2^{64}\pm c$for 64-bit CPUs), so that they can leverage on CPU's ALU for most computations, therefore OEF based systems are ... 1 Yes, cryptosystems like ElGamal or Shnorr based on the intractability of Dlog Problem are are indicated to be implemented on finite field, which is not the case of the RSA for which a model was proposed in the early$80^{ies}$, and immediatly broken. As you know, a finite field is denoted by$GF(q)$where$q=p^m$and p would be any Prime. But in the case ... 1 First, I think you have a typo in your question since in the original article$s = (M - x y)(r^{-1}) \mod p-1$, and not$s = (M - x^y)(r^{-1}) \mod p-1$. Knowing that, then we can construct$s_2$from$s, r, M$and$M_2$:$s_2 = s + (M_2 - M)r^{-1} = (M - x^y)r^{-1} + (M_2 - M)r^{-1} = (M - x^y + M_2 - M)r^{-1} = (M_2 - x y)r^{-1}\$ A valid signature for ...

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