Information Technology Reference
In-Depth Information
This point multiplication method can be used in those cryptographic protocols that
do not take solving equations modulo
r
. Such protocols can be implemented for
2
−
-ary exponent representation.
Protocol 1. Diffie-Hellman Key Agreement.
Elliptic curve
E
(
K
) and generator
Q
∈
E
(
K
) are publicly known.
Users
A
and
B
can agree the secret session key:
1.
A
chooses exponent
u
A
∈
O
K
at random, computes
u
A
Q
and sends this point to
B
.
2.
B
chooses exponent
u
B
∈
O
K
at random, computes
u
B
Q
and sends this point to
A
.
3.
B
multiplies received point
u
A
Q
by his exponent
u
B
and obtains point
u
B
u
A
Q
.
4.
A
multiplies received point
u
B
Q
by his exponent
u
A
and obtains point
u
A
u
B
Q
.
Point
u
A
u
B
Q
=
u
B
u
A
Q
is the desired secret key.
Protocol 2. ElGamal Public Key Encryption.
Elliptic curve
E
(
K
), generator
Q
∈
E
(
K
) and public key
P
∈
E
(
K
) are publicly known. Exponent
l
∈
O
K
such that
P
=
lQ
is the user's
B
secret key. Users
A
and
B
can implement public-key
encryption/decryption for message
m
, 1
≤
log
2
m
< log
2
|
ρ
| - 1
(|
ρ
| is integer,
corresponding to vector ρ with binary coefficients).
1.
A
chooses exponent
k
∈
O
K
at random, computes points
R
=
kQ
,
S
=
kP
, computes
XOR-sum
c
=
x
S
⊕
m
and sends ciphertext (
c
,
x
R
) to
B
.
2.
B
computes ±
y
R
as a square root of
x
R
3
+
Ax
R
+
B
and obtains point ±
R
; multiplies
this point by
l
, obtains point ±
S
= (
x
S
, ±
y
S
) and decrypts a message
m
=
x
S
⊕
c
.
Digital signature protocols such as DSS take computation modulo ρ in
O
K
. Compu-
tation can be implemented in two steps: usual computing in
Z
/
r
Z
and mapping the
result into the field
O
ρ
O
.
K
K
Any exponent admits of unique minimal
−
2
-ary representation with the length
log
2
r
at most. Prime fields
F
r
and
consist of
r
elements and hence are iso-
morphic. So exponent minimization is equivalent to reduction modulo
O
ρ
O
K
K
ρ
in
O
K
. Note
that
σ
+
τρ
≡
σ
(mod
ρ
) for
σ
,
τ
∈
O
K
.
Norm
N
of quadratic integer
s
+
t
−
2
is
2
2
. Norm function
N
(
s
+
t
−
2
)
=
s
+
2
t
is multiplicative and gives isomorphism from (
)
*
to
F
r
*
. Reduction
O
ρ
O
K
K
(
k
∈
F
r
) → (
k
(mod ρ) ∈
) is performed as norm minimization. The follow-
ing algorithm reduces integer modulo ρ.
Input
. Integer
k
;
O
ρ
O
K
K
ρ
=
c
+
d
−
2
.
Output
.
k
≡
k
+
k
−
2
(mod
ρ
)
, where
k
<
r
,
k
<
r
.
0
1
0
1
Method
.
1. Set
k
0
←
k
,
k
1
← 0,
κ
←
k
+
k
−
2
.
0
1
