Cryptography Reference
In-Depth Information
3 d ( a 2
b 2 α 2 )and r dividing the order of Q =( a + : a
: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 + : a
u
|
k , Q
∈H
(
: 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 + )+ c Y ( a
)+ c Z ]
= f
·
[( c X + c Y ) a +( c X
c Y ) + 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 ) + 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 ) + 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 ) +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