Hot answers tagged

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


2

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack algorithm. The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything. Hashing the ...


1

In this state we have well known attack that is called invalid-curve attack. Let $E:y^2=x^3+ax+b$ and $E':y^2=x^3+ax+b'$ be two elliptic curves with reduced Weierstrass form. $E'$ is called an invalid curve relative to $E$. Since formulae for adding and doubling points on $E$ does not involve coefficient $b$ thus addition law for $E$ and $E'$ is same. In ...


1

For $c\ne0$, the definition of $a\equiv b\pmod c$ is: $\exists d\in\mathbb Z$ such that $a=b+cd$. Applying that definition to $H(m)\equiv xr+sk\pmod{p-1}$, we have that $\exists d\in\mathbb Z$ such that $H(m)=xr+sk+(p-1)d\;\text{ (equ. 1)}$. Fermat's little theorem is that for $p$ prime and $g\not\equiv0\pmod p$, it holds that $g^{p-1}\equiv1\pmod ...


1

In ElGamal Signature Scheme we have: $$\beta=\alpha^a \bmod p$$ The values $p,\alpha$ and $\beta$ are public key, and $a$ is private key. $$\operatorname{sig_k}(x,k)=(\gamma , \delta)$$ where $\gamma = \alpha^k \bmod p $ and $\delta = (x-a\gamma)k^{-1} \bmod {p-1}$.


1

Thanks to fgrieu's comment above and the following quote from here (PDF): Theorem: Let $p$ be a prime and let $a$ be a number not divisible by $p$. Then if $$ r \equiv s \pmod {p − 1} $$ we have $$ a^r \equiv a^s \pmod p$$ In brief, when we work $\mod p$, exponents can be taken $\mod{p − 1}$. I (think i) understood, how the first (implicit) ...


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