Inverse in ElGamal signature

Question

I am learning about ElGamal signature verification. During the signature generation one has to choose a k such that 1 < k < p − 1 and gcd(k, p − 1) = 1. I am using the notation from the Wikipedia site. Later it is used the inverse of k. I assume this is a modular inverse. Learning materials I have found does not state whether this is a modular inverse regarding p or p-1. Can somebody clarify this?

Answer 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}$.

Answer 2

It is $p-1$. I now give a detailed explanation as to why this is:

1. First, I give a corollary which is used to prove the ElGamal signature verification.

Corollary If $a$ and $p$ are relative prime integers, and $p$ is a prime integer,then $a^i \equiv a^j \pmod p$,where i and j are non-negative integers, if and only if $i \equiv j \pmod {p-1}$.

This corollary gives the relationship of $p$ and $p-1$.

One of the methods to prove it is based on a theorem.

This theorem can be found in Elementary Number Theory and Its Application, (6th ed.), by Kenneth Rosen (p. 349). Theorem 9.2. It can also be used to prove DSA.

Theorem 9.2 If $a$ and $n$ are relative prime integers with $n>0$, then $a^i \equiv a^j \pmod n$, where i and j are non-negative integers, if and only if $i \equiv j \pmod {ord_n^a}$

Specially, when $p$ is a prime integer, ${ord_p^a}=\varphi(p)=p-1$ , so we prove the corollary.

hence:

$$i \equiv j \pmod {p-1} \Leftrightarrow a^i \equiv a^j \pmod p.$$

2. Now, we review the ElGamal signature, and prove it using the corollary.

2.1 Key Generation for an ElGamal Digital Signature

1. Choose a large prime $p$.
2. Choose a primitive element $\alpha$ of $Z_p^*$.
3. Choose a random integer $d \in \{2,3, . . . , p-2\}$.
4. Compute$\beta = \alpha^d \pmod p$.
   The public key is $k_{pub}=(p, \alpha, \beta)$, and private key $k_{pr}=d$

2.2 ElGamal Signature Generation

The signing consists of two main steps: choosing a random value $k$, which forms an ephemeral private key, and computing the actual signature of $x$.

1. Choose a random ephemeral key $k \in \{0,1,2, . . . , p-2\}$ such that $gcd(k, p-1) = 1$.
2. Compute the signature parameters: $$r \equiv \alpha^k \pmod p$$ $$s \equiv (x-d\cdot r)k^{-1} \pmod {p-1}$$

Hence, the signature is: $$sig_{k_{pr}}(x,k)=(r,s)$$

2.3 ElGamal Signature Verification

1. Compute the value $$t \equiv \beta^r \cdot r^s \pmod p$$
2. The verification follows from: $$ t\begin{cases} \equiv \ \alpha^x \pmod p\ \ \ \ \Rightarrow \ \ \ \ valid \ \ signature\\\\ \not \equiv \ \alpha^x \ \pmod p\ \ \ \ \Rightarrow \ \ \ \ invalid \ \ signature \end{cases} $$

2.4 Proof

Prove that: $$ \alpha^x \equiv \beta^r \cdot r^s \pmod p$$ since:
$$ \beta^r \cdot r^s \pmod p \equiv (\alpha^d)^r(\alpha^k)^s \pmod p \equiv \alpha^{d\cdot r+k\cdot s} \pmod p$$

So, we require that :

$$\alpha^x \equiv \alpha^{d\cdot r+k\cdot s} \pmod p$$

According the corollary shown above, the relationship holds if and only if:

$$ x \equiv d\cdot r+k\cdot s \pmod {p-1}$$
hence, we get $s$:

$$s\equiv (x - d \cdot r)k^{-1} \pmod {p-1}$$

This is just the construction rule of the signature parameters $s$ follows from.
The condition that $gcd(k, p-1) = 1$ is required since we have to invert the ephemeral key modulo $p-1$ when computing $s$.

3. Conclusion

From the description above, we now know why it is $p-1$, not $p$.

References

1. 《Rosen, K. H. (2011). Elementary Number Theory and Its Applications (6th ed.). Pearson.》
2. 《Paar, C., & Pelzl, J. (2010). Understanding Cryptography. Springer-Verlag.》