Inverse in ElGamal signature

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?

• Try both, see what happens. Feb 16 '16 at 8:27

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

• The question was how k^-1 is calculated from k. Feb 16 '16 at 9:33
• @franz1, from answer it's evident that $k^{-1}$ calculated from mod p-1. Feb 16 '16 at 9:45

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.》
• I don't know why you gave a huge answer for this question. Clearly, the OP just asked where the inverse of $k$ is calculated. And the Meryem's answer already indicated that it is in $p-1$ by the last line. Please firstly check the other answers. We are in a question/answer site. In general, if not satisfies, the OP can comment for clarification. Oct 3 '19 at 16:27
• The Meryem's answer really indicated that it is $p-1$。 I give it why this is. That is ok? And I guess robert want to know why it is $p-1$, not $p$ If there is any downside, I apologize. I am a newcomer.
– 孙海城
Oct 3 '19 at 16:40
• They why is also clear, the equation is working on $\bmod p-1$. Oct 3 '19 at 16:42
• Sorry when I answered it ,I thinked it is not so obvious , I want to clarify it to the robert. Then the answer should be voted to be deleted?
– 孙海城
Oct 3 '19 at 16:49
• I cannot enforce you delete. You are giving many answers that are a cold case. Concentrate mostly on new ones? Oct 3 '19 at 17:00