1
$\begingroup$

Alice chooses

i) A large prime $p_A$ (say 200 to 300 digits)
ii) A primitive element $\alpha_A$ modulo $p_A$,
iii) A (possibly random) integer $d_A$ with $2 \le d_A \le p_A-2$.

Alice computes

iv) $\beta_A \equiv \alpha_A^{d_A} \pmod {p_A}$.

Alice's public key is $(p_A,\alpha_A,\beta_A)$. Her private key is $d_A$.

What is meant by the notation $\alpha_A$, $p_A$, and what is meant by a 'primitive element', does it mean a small number or something else entirely?

$\endgroup$
  • $\begingroup$ What do you mean by "a (subscript a)"? There is no a with a subscript anywhere in the quote? Do you mean $\alpha_A$? $\endgroup$ – CodesInChaos Jun 26 '13 at 10:09
3
$\begingroup$

The subscript $A$ indicates that these numbers ($p_A$, $\alpha_A$, etc.) are the ones involved in Alice's key. In a description of a protocol with more participants each having their own key, Bob's public key would be $(p_B, \alpha_B, \beta_B)$, and so on.

A primitive element of a finite field is a generator for the multiplicative group, i.e. the set $\{1, \alpha_A, \alpha_A^2, \alpha_A^3, \ldots, \alpha_A^{p_A-1}\}$ must be the whole set $\{1, 2, 3, \ldots, p-1\}$ of nonzero elements of the field $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$, i.e. any nonzero element of the field can be expressed as a power of $\alpha_A$. Another way of expressing this property is that $\alpha_A$ must have the order $p-1$ (the largest possible order of an element of the field), which means that none of the $\alpha_A^k$ for $1 \le k \le p-2$ are equal to $1$ modulo $p$.

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