Cryptography Reference
In-Depth Information
Elliptic Curve Facts
We assume that
E
(
given by
y
2
=
x
3
+
ax
+
b
Q
) is an elliptic curve over
Q
where
a,b
∈
Z
, and o denotes the point at infinity.
(1) (
Addition of points
): For any two points
P
=(
x
1
,y
1
) and
Q
=(
x
2
,y
2
)
on
E
, with
P,Q
−
= o and
P
=
Q
, define
P
+
Q
=(
x
3
,y
3
)=(
m
2
−
x
1
−
x
2
,m
(
x
1
−
x
3
)
−
y
1
)
,
(A.12)
where
m
=
m
1
/m
2
=(
y
2
−
y
1
)
/
(
x
2
−
x
1
) f
P
=
Q
,
(A.13)
m
1
/m
2
=(3
x
1
+
a
)
/
(2
y
1
)
if
P
=
Q
,
and
if
P
= o, for instance, then
P
+
Q
=
Q
for all points
Q
on
E,
and
if
P
=
−
Q
, then
P
+
Q
= o
.
(2) (
Reduction modulo
n
): Let
n>
1 be given and fixed with gcd(
n,
6) = 1,
and gcd(4
a
3
+27
b
2
,n
) = 1. Then we refer to
E
reduced modulo
n
when the
coeGcients
a,b
are reduced modulo
n
, and each point
P
on
E
is reduced
modulo
n
in the following fashion. If
P
=(
r
1
/r
2
,s
1
/s
2
) where
gcd(
r
1
,r
2
) = gcd(
s
1
,s
2
) = gcd(
r
2
s
2
,n
)=1
,
then
r
1
r
−
1
s
1
s
−
1
P
=(
t
1
,t
2
), where
t
1
≡
(mod
n
) and
t
2
≡
(mod
n
)
,
2
2
with
r
−
1
2
and
s
−
2
being the multiplicative inverses of
r
2
and
s
2
modulo
n
, respectively. We denote the reduced curve by
E
(
Z
/n
Z
), and if
n
is a
prime, then this is a group.
(3)
(
Modular group law
): Suppose that
P
1
,P
2
are points on
E
(
Q
) where
P
1
+
P
2
= o and the denominators of
P
1
,P
2
are prime to
n
. Then
P
1
+
P
2
has coordinates having denominators prime to
n
if and only if there does
not exist a prime
p
n
such that
P
1
+
P
2
= o (mod
p
) on the elliptic curve
E
(
Z
/p
Z
).
For a more in-depth description of elliptic curve theory as it applies to cryp-
tology, see [169, pages 221-251].
Search WWH ::
Custom Search