Cryptography Reference
In-Depth Information
3
d
(
a
2
b
2
α
2
)and
r
dividing the order of
Q
=(
a
+
bα
:
a
−
−
bα
:1)
∈H
(
F
p
k
).
Note that
F
p
u
). The point
Q
constructed in this way can be ap-
plied to identity based cryptosystems [3]. Even if we restrict the point
Q
as
(
a
+
bα
:
a
∀
u
|
k
,
Q
∈H
(
bα
: 1), it does not affect the security of the ID-based protocol since
the point
Q
is a public point.
To describe clearly, in Algorithm 1, we call
f
−
l
1
(
Q
)
←
f
·
l
2
(
Q
)
,
R
←
R
+
P
addition
l
1
(
Q
)
l
2
(
Q
)
,
R
f
2
and
f
←
·
←
2
R
is referred as doubling. Since
l
2
(
Q
)=(
Y
3
Z
3
−
X
3
Z
3
)(
X
+
Y
)+(
X
3
−
Y
3
∈
F
p
k/
2
, it follows
that
l
2
(
Q
)
(
p
k
−
1)
/r
= 1. Therefore we only need to consider numerator
l
1
(
Q
)in
additions and doublings.
Y
3
)
Z
=(
Y
3
Z
3
−
X
3
Z
3
)2
a
+
X
3
−
4.1 Addition
Let
R
=(
X
1
:
Y
1
:
Z
1
)and
P
=(
X
2
:
Y
2
:
Z
2
)betwopointson
H
(
F
p
).
f
·
l
1
(
Q
)
=
f
·
[
c
X
(
a
+
bα
)+
c
Y
(
a
−
bα
)+
c
Z
]
=
f
·
[(
c
X
+
c
Y
)
a
+(
c
X
−
c
Y
)
bα
+
c
Z
]
where
c
X
=
Y
1
Z
2
−
Z
1
Y
2
,
c
Y
=
Z
1
X
2
−
X
1
Z
2
,
c
Z
=
X
1
Y
2
−
Y
1
X
2
. So the explicit
l
1
(
Q
)
formulas for computing
f
←
f
·
l
2
(
Q
)
,
R
←
R
+
P
are given as follows:
A
=
Y
1
·
Z
2
,
B
=
Z
1
·
Y
2
,
C
=
Z
1
·
X
2
,
D
=
X
1
·
Z
2
,
E
=
X
1
·
Y
2
,
F
=
Y
1
·
X
2
,
c
X
=
A
−
B
,
c
Y
=
C
−
D
,
c
Z
=
E
−
F
,
f
=
f
·
[(
c
X
+
c
Y
)
a
+(
c
X
−
c
Y
)
bα
+
c
Z
],
X
3
=
A
D
.
The cost of these formulas is 1M+km+12m, where M denotes the cost of a
multiplication in
·
F
−
B
·
E
,
Y
3
=
D
·
E
−
C
·
F
,
Z
3
=
B
·
C
−
A
·
F
p
k
while m is the cost of a multiplication in
F
p
. Multiplications
by
a, b
∈
F
p
k/
2
need (
k/
2)
m
each. If the base point
P
has
Z
2
=1,theabove
costs reduce to 1M+km+10m.
4.2 Doubling
l
1
(
Q
)
l
2
(
Q
)
will not
change if the numerator and the denominator are multiplied by 2 simultaneously,
we can consider:
F
p
). Since the result of
f
2
Let
R
=(
X
1
:
Y
1
:
Z
1
)beapointon
H
(
·
f
2
·
2
l
1
(
Q
)
=
f
2
·
2[(
c
X
+
c
Y
)
a
+(
c
X
−
c
Y
)
bα
+
c
Z
]
where
c
X
=3
X
1
−
=3
Y
1
−
3
dX
1
Z
1
,
c
Z
=3
Z
1
−
3
dY
1
Z
1
,
c
Y
3
dX
1
Y
1
. Hence the
f
2
explicit formulas for computing
f
←
·
l
1
(
Q
),
R
←
2
R
are given as follows:
A
=
X
1
,
B
=
Y
1
,
C
=
Z
1
,
D
=(
Y
1
+
Z
1
)
2
C
,
E
=(
X
1
+
Z
1
)
2
−
B
−
−
A
−
C
,
F
=(
X
1
+
Y
1
)
2
−
A
−
B
,2
c
X
=6
A
−
3
dD
,2
c
Y
=6
B
−
3
dE
,2
c
Z
=6
C
−
3
dF
,
f
=
f
2
·
[(2
c
X
+2
c
Y
)
a
+(2
c
X
−
2
c
Y
)
bα
+2
c
Z
],
X
3
=(
F
−
D
)(
E
+2
A
+2
C
),
Y
3
=(
E
−
F
)(
D
+2
B
+2
C
),
Z
3
=(
D
−
E
)(
F
+2
A
+2
B
).
Search WWH ::
Custom Search