Cryptography Reference
In-Depth Information
The size of
p
should be, depending on the application, 1024 bits or longer (see
Table 17-1), and for the encryption of different messages
M
1
and
M
2
unequal
random values
y
1
=
y
2
should be chosen, since otherwise, from
β
1
β
2
=
M
1
b
y
M
2
b
y
=
M
1
M
2
it would follow that knowledge of
M
1
was equivalent to knowledge of
M
2
. In view
of the practicability of the procedure one should note that the cryptogram
C
is
twice the size of the plain text
M
, which means that this procedure has a higher
transmission cost than others.
The procedure of ElGamal in the form we have presented has an interesting
weak point, which is that an attacker can obtain knowledge of the plain text with
a small amount of information. We observe that the cyclic group
Z
p
contains
the subgroup
U
:=
{ a
x
of order
(
p −
1)
/
2
(cf. [Fisc], Chapter 1). If
now
b
=
a
x
or
α
=
a
y
lies in
U
, then this holds, of course, for
a
xy
. If this is the
case and the encrypted text
β
is also in
U
, then
M
=
βa
−
xy
is in
U
as well. The
same holds if
a
xy
and
β
are both not contained in
U
. In the other two cases, in
which precisely one of
a
xy
and
β
does not lie in
U
, then
M
is also not in
U
. The
following criteria provide information about this situation:
1.
a
xy
| x
even
}
∈ U ⇔
(
a
x
∈ U
or
a
y
∈ U
)
. This, and whether also
β ∈ U
, is tested
with
2.
For all
u ∈
Z
×
p
,
u ∈ U ⇔ u
(
p
−
1)
/
2
=1
.
One may ask how bad it might be if an attacker could gain such information
about
M
. From the point of view of cryptography it is a situation difficult to
accept, since the message space to be searched is reduced by half with little effort.
Whether in practice this is acceptable certainly depends on the application.
Surely, it is a valid reason to be generous in choosing the length of a key.
Furthermore, one can take some action against the weakness of the
procedure, without, one hopes, introducing new, unknown, weaknesses: The
multiplication
Mb
y
mod
p
in step 2 of the algorithm can be replaced with an
encryption operation
V
(
H
(
a
xy
)
,M
)
using a suitable symmetric encryption
procedure
V
(such as Triple-DES, IDEA, or Rijndael, which has become the
new advanced encryption standard; cf. Chapter 11) and a hash function
H
(cf.
page 398) that so condenses the value
a
xy
that it can be used as a key for
V
.
So much for our examples of the application of modular exponentiation. In
number theory, and therefore in cryptography as well, modular exponentiation
is a standard operation, and we shall meet it repeatedly later on, in particular
in Chapters 10 and 17. Furthermore, refer to the descriptions and numerous
applications in [Schr] as well as in the encyclopedic works [Schn] and [MOV].
