Return to Answer

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.》

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.》

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 mod 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.》

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.》

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 mod 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.》

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 mod 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.》