2
$\begingroup$

On a homework assignment, we're asked to give an example in which scenario one would use an ElGamal-Signature over an RSA-Signature. I found this question, but the answer also only describes why RSA is superior. I searched a while now, but I don't really find any reason why one would use a Schoolbook-ElGamal (not DSA or elliptic curves) instead of RSA.

Does anyone have an additional idea?

$\endgroup$
  • $\begingroup$ PKCS#1 v1.5 signatures are deterministic, which is something you may not always want. RSA-PSS solves that issue though. The keys seem to be smaller if you assume that $p$ and $g$ are known in advance. Just guessing here. $\endgroup$ – Maarten Bodewes Jan 25 '18 at 22:25
2
$\begingroup$

ElGamal signature works as follows. Define a large prime $p = 2qs + 1$ where $q$ is a prime. Let $g$ be an element of order $q$ and a hash function $H\colon \{0,1\}^* \to \mathbb{Z}_q$. The public key is $y = g^x \bmod p$ and the private key is $x \in \mathbb{Z}_q$. The signature of a message $m$ is given by a pair $(r,s)$ where $$r=g^k \bmod p\quad\text{and}\quad s = k^{-1}(H(m) - xr) \bmod q$$ for a random integer $k \in \mathbb{Z}_q$. The validity of a signature $(r,s)$ on message $m$ is checked by verifying that $r^sy^r \equiv g^{H(m)} \pmod p$.

It is worth to see that the two expensive operations in the signature generation, namely computing $g^k \bmod p$ and $k^{-1} \bmod q$, are independent of the message to be signed. They can therefore be precomputed. ElGamal signatures can be preferred when signing should be done very fast, like for example to authenticate a car at a toll bridge. In this mode (called off-line/on-line),

  1. [off-line phase] several coupons $(r_i, t_i)$, with $r_i = g^{k_i} \bmod p$ and $t_i = k_i^{-1} \bmod q$, for random integers $k_i \in \mathbb{Z}_q$ are pre-computed;
  2. [on-line phase] when a message $m$ has to be signed, the signer takes a fresh coupon $(r_i, t_i)$ and computes the signature as $r = r_i$ and $s = t_i(H(m) - xr_i) \bmod q$.

Notes.

  1. A coupon can only be used once. Each signature needs a fresh coupon.

  2. In the on-line phase, the cost of an ElGamal signature is only a couple of multiplications modulo $q$ (which is much faster than a full modular exponentiation in the case of RSA).

$\endgroup$
  • $\begingroup$ Precompution and time-memory-tradeoff... You're absolutely right, thank you (and +1) for leading me to my blind spot. $\endgroup$ – Andreas H. Jan 26 '18 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.