Cryptography Reference
In-Depth Information
F
q
,andthepoints
P
and
B
are Bob's public key. They are made public.
Bob'sprivatekeyistheinteger
s
.
To send a message to Bob, Alice does the following:
1. Downloads Bob's public key.
2. Expresses her message as a point
M
∈
E
(
F
q
).
3. Chooses a secret random integer
k
and computes
M
1
=
kP
.
4. Computes
M
2
=
M
+
kB
.
5. Sends
M
1
,M
2
to Bob.
Bob decrypts by calculating
M
=
M
2
− sM
1
.
This decryption works because
M
2
−
sM
1
=(
M
+
kB
)
−
s
(
kP
)=
M
+
k
(
sP
)
−
skP
=
M.
The eavesdropper Eve knows Bob's public information and the points
M
1
and
M
2
. If she can calculate discrete logs, she can use
P
and
B
to find
s
,
which she can then use to decrypt the message as
M
2
− sM
1
. Also, she could
use
P
and
M
1
to find
k
. Then she can calculate
M
=
M
2
−
kB
. If she cannot
calculate discrete logs, there does not appear to be a way to find
M
.
It is important for Alice to use a different random
k
each time she sends
a message to Bob. Suppose Alice uses the same
k
for both
M
and
M
.Eve
recognizes this because then
M
1
=
M
1
.
She then computes
M
2
−
M
2
=
M
−M
. Suppose
M
is a sales announcement that is made public a day later.
Then Eve finds out
M
, so she calculates
M
=
M − M
2
+
M
2
. Therefore,
knowledge of one plaintext
M
allows Eve to deduce another plaintext
M
in
this case.
The ElGamal Public Key system, in contrast to the ElGamal signature
scheme of the next section, does not appear to be widely used.
6.5 ElGamal Digital Signatures
Alice wants to sign a document. The classical way is to write her signature
on a piece of paper containing the document. Suppose, however, that the
document is electronic, for example, a computer file. The naive solution
would be to digitize Alice's signature and append it to the file containing the
document. In this case, evil Eve can copy the signature and append it to
another document. Therefore, steps must be taken to tie the signature to
Search WWH ::
Custom Search