# Tag Info

## Hot answers tagged elgamal-signature

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

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