# Tag Info

4

It seems that you mix things up. ElGamal signatures are existentially forgeable in various different ways if it's not using the hash-then-sign paradigm, i.e., you sign the message directly instead of signing the message $m=H(M)$ with $H$ being a secure cryptographic hash function. Given the type of forgery in your question that works, you compute your ...

3

Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.

2

With your proposed modification of the ElGamal signature scheme you can produce forgeries for arbitrary (hashed) messages $m$. By looking at the verification equation $$g^m = yr^s$$ you just have to set $r$ to $r=(g^my^{-1})^{s^{-1}}$ (just by rearranging the verification equation) which you can do for any $s$ from $\mathbb{Z}_{p-1}^*$, i.e., every $s$ ...

1

First you should know that Elgamal encryption and signature security is based on DDH problem (Decisional Diffie Hellman) which is tractable in some groups that CDH problem is believed to be hard (Computational Diffie Hellman). As in the case of $\mathbb{Z_q}$ in which CDH is believed to be hard but DDH is apparently tractable. Let $p = 2p_1 + 1$ where both ...

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