Cryptography Reference
In-Depth Information
Table A.3:
Powers of 2 modulo 23
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
2
10
2
11
2
4
8
16
9
18
13
3
6
12
1
2
12
2
13
2
14
2
15
2
16
2
17
2
18
2
19
2
20
2
21
2
22
2
4
8
16
9
18
13
3
6
12
1
raise
g
to different powers, which we do when computing the third component
y
of an ElGamal public key as well as during the encryption process itself, the result
can be
any
number modulo
p
.If
g
is not primitive then the security of ElGamal is
greatly reduced.
For example, if the non-primitive element
g
=
2 is used as part of an ElGamal
public key alongside
p
23 then we can see from Table A.3 that
g
k
can only
take half of the possible values. An attacker who tries to decrypt a ciphertext by
exhaustively searching for the value
k
that was used when forming
C
1
=
=
g
k
will
have a much easier job than if we had used a primitive element for
g
, since there
are two different values of
k
that will work, halving the effort required.
A.4.2
Why ElGamal works
Recall that an ElGamal public key is of the form (
p
,
g
,
y
), where
x
is the
corresponding private key and
y
g
x
. In Section 5.3.2 we also learnt that ElGamal
encryption consists of randomly generating a value
k
and then computing
C
1
=
=
g
k
Py
k
, where
P
is the plaintext. We then observed that decryption
consists of dividing
C
2
and
C
2
=
by the answer to (
C
1
)
x
mod
p
. We now explain why
this works.
Suppose that Bob receives the ciphertext (
C
1
,
C
2
). Bob begins by using his
private key
x
to transform
C
1
into something more useful. He thus computes:
(
C
1
)
x
(
g
k
)
x
(
g
x
)
k
y
k
mod
p
=
=
=
.
This follows because it does not matter in which order the two exponentiations
are computed. Thus raising
g
to the power
k
and then to the power
x
is the same
as raising
g
to the power
x
and then to the power
k
.
Bob now divides this value into
C
2
. Of course we now know that such 'division'
is done bymultiplying by themodular inverse. Thus Bob needs to find themodular
inverse of
y
k
modulo
p
, which we denote by (
y
k
)
−
1
. Bob can find this using the
