1
$\begingroup$

Reading "Security Arguments for Digital Signatures and Blind Signatures" paper, I confused by some questions.

  • Q1. when it refers to "El Gamal signature scheme",

    The key generation algorithm: it chooses a random large prime $p$, of length $n$ polynomial in $k$, and a generator $g$ of $(\mathbb{Z}/p\mathbb{Z})^*$, both public. Then, for a random secret key $x \in \mathbb{Z}/(p − 1)\mathbb{Z}$, it computes the public key $y = gx \mod p$

    why $x$ select from group $\mathbb{Z}_{p-1}$,but not $\mathbb{Z}_p$? what is the difference?

$\endgroup$
  • $\begingroup$ please check the update of your question with latex. $\endgroup$ – kelalaka Mar 31 at 10:00
3
$\begingroup$

$\mathbb{Z}_p=\mathbb{Z}/p\mathbb{Z}$ denotes a finite field that is just integers mod the prime $p$, i.e., $\{0,1,\ldots,p-1\}$. This field (by definition of a field) has two operations: addition and multiplication, where the multiplication group (denoted by $\mathbb{Z}_p^*$) is defined only on the non-zero elements $\{1,2,\ldots,p-1\}$. Then, since $g$ is a generator of the multiplicative group of size $p-1$, the exponent $x$ should be sampled from $\mathbb{Z}_{p-1}=\{0,1,\ldots,p-2\}$ (which by the way is not a finite field).

$\endgroup$
1
$\begingroup$

Because $\mathbb{Z}/{p\mathbb{Z}}$ when used for El-Gamal is used in its multiplicative form: we have a generator $g$ such that all powers of $g$ cycle through $\{1,2,\ldots,p-1\}$ (so $0$ is excluded) and as $g^{p-1} =1 \pmod{p}$ by Fermat's little theorem, the powers $x$ we use for the generator and which we use as the private key in the DL scheme essentially takes values in $\{0,\ldots,p-2\}$ (as $x=0$ and $x=p-1$ both yield $g^x=1$), i.e. $g^x = g^{x'} \pmod{p}$ iff $x = x'\pmod{p-1}$. Hence the fact we have $p-1$ choices for $x$.

$\endgroup$

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.