Cryptography Reference
In-Depth Information
The version of the ElGamal cryptosystem that we described in Section 5.3 also
relies on modular arithmetic. We only need to explain one further concept in
order to understand the basic mathematics behind ElGamal.
A.4.1
ElGamal public keys
Recall from Section 5.3.1 that each ElGamal public key involves three numbers.
The first is a prime
p
, while the second number
g
has the special property that it
is a
primitive
element. We now explain the significance of this.
PRIMITIVE ELEMENTS
Let
p
be a prime. A number
g
between 1 and
p
−
1 is said to be
primitive
(or is a
primitive element
) modulo
p
if the numbers:
g
2
g
3
g
4
g
5
g
6
g
p
−
1
mod
p
g
,
,
,
,
,
,...,
,
are all different. If this is the case then, since there are
p
−
1 of them, they must
consist of 1
1 in some order.
Table A.2 indicates the powers of 11 modulo 23. The first and third rows
indicate the powers that 11 is being raised to, while the rows below show
the result of computing 11 raised to that power, modulo 23. For example,
11
2
,
2
,
3
,...,
p
−
6mod 23, so 6 appears below 11
2
in Table A.2.
We can see from inspecting Table A.2 that 11 is a primitive element modulo 23.
Note, however, that not every number between 1 and
p
=
121
=
−
1 is primitive modulo
p
.
Table A.3 indicates the powers of 2 modulo 23. In this case, not all the numbers
1
22 appear amongst the second and fourth rows of Table A.3 (in fact
only half of them do) and so 2 is not a primitive element modulo 23.
,
2
,
3
,...,
IMPORTANCE OF PRIMITIVE ELEMENTS TO ElGamal
The ElGamal public-key component
g
must be a primitive element modulo
p
. The
main reason that this restriction is made is in order to make sure that when we
Table A.2:
Powers of 11 modulo 23
11
1
11
2
11
3
11
4
11
5
11
6
11
7
11
8
11
9
11
10
11
11
11
6
20
13
5
9
7
8
19
2
22
11
12
11
13
11
14
11
15
11
16
11
17
11
18
11
19
11
20
11
21
11
22
12
17
3
10
18
14
16
15
4
21
1
