Hot answers tagged

5

TL;DR: The main reasons to prefer RSA over ElGamal signatures boild down to speed, signature size, standardization, understandability of the method and historical establishment as the result of a lot of lobby work. The main technical advantage of RSA is speed. With RSA you only need to do a small-exponent exponentation to verify a signature, where as with ...


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

I wonder, is there any real-world applications of ElGamal signatures and encryption? Rarely. ElGamal encryption is used very rarely, with GPG being nearly the only common tool, not library, to historically support ElGamal due to patent restrictions with RSA. Other than that it sees little use due to RSA being better promoted, supported and standardized. ...


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

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

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 p\;\text{...


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



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