Cryptography Reference
In-Depth Information
If the message is signed correctly, the verification equation holds:
V
=
u
1
G
+
u
2
Q
=
s
−
1
mG
+
s
−
1
xQ
=
s
−
1
(
mG
+
xaG
)=
kG
=
R.
The main difference between the ECDSA and the ElGamal system is the
verification procedure. In the ElGamal system, the verification equation
f
(
R
)
B
+
sR
=
mA
requires three computations of an integer times a point.
These are the most expensive parts of the algorithm. In the ECDSA, only two
computations of an integer times a point are needed. If many verifications
are going to be made, then the improved e
ciency of the ECDSA is valuable.
This is the same type of improvement as in the van Duin system mentioned
at the end of the previous section.
6.7 ECIES
The Elliptic Curve Integrated Encryption Scheme (ECIES) was invented
by Bellare and Rogaway [2]. It is a public key encryption scheme.
Alice wants to send a message
m
to Bob. First, Bob establishes his public
key. He chooses an elliptic curve
E
over a finite field
F
q
such that the discrete
log problem is hard for
E
(
F
q
), and he chooses a point
A
on
E
, usually of large
prime order
N
. He then chooses a secret integer
s
and computes
B
=
sA
.
The public key is (
q, E, N, A, B
). The private key is
s
.
The algorithm also needs two cryptographic hash functions,
H
1
and
H
2
,
and a symmetric encryption function
E
k
(depending on a key
k
)thatare
publicly agreed upon.
To encrypt and send her message, Alice does the following:
1. Downloads Bob's public key.
2. Chooses a random integer
k
with 1
≤ k ≤ N −
1.
3. Computes
R
=
kA
and
Z
=
kB
.
4. Writes the output of
H
1
(
R, Z
)as
k
1
k
2
(that is,
k
1
followed by
k
2
),
where
k
1
and
k
2
have specified lengths.
5. Computes
C
=
E
k
1
(
m
)and
t
=
H
2
(
C, k
2
).
6. Sends (
R, C, t
)toBob.
To decrypt, Bob does the following:
1. Computes
Z
=
sR
, using his knowledge of the secret key
s
.
2. Computes
H
1
(
R, Z
) and writes the output as
k
1
k
2
.
Search WWH ::
Custom Search