Cryptography Reference
In-Depth Information
end if;
a := E[1];
b := E[2];
ifP=Qthen
m := ((3*x1ˆ2+a)/2*y1) mod p
else
m := ((y2-y1)/(x2-x1)) mod p
end if;
x3 := (mˆ2-x1-x2) mod p;
y3 := (m*(x1-x3)-y1) mod p;
[x3, y3]
end proc:
Example 11.11
We can now build the addition table corresponding to a (small)
elliptic curve group. Let us consider the group
E
(
F
7
)
corresponding to the elliptic
curve with equation
y
2
x
3
2. We compute the operation given as a map
and the set of points of the elliptic curve:
=
+
3
x
+
> ec327 := EllipticCurve(3, 2, 7);
op327 := proc (P, Q) -> EllipticAdd(P, Q, ec327);
ep327 := EllipticPoints(ec327);
[0, [0, 3], [0, 4], [2, 3], [2, 4], [4, 1], [4, 6], [5, 3], [5, 4]]
We see that the curve has order 9. Next we compute the group table using the
> tabl(ep327, op327);
⎡
⎣
⎤
⎦
]
[
0
,
3
][
2
,
3
]
0
[
5
,
4
][
0
,
4
][
5
,
3
][
4
,
1
][
2
,
4
][
4
,
6
]
[
0
,
4
]
0
[
2
,
4
][
0
,
3
][
5
,
3
][
4
,
6
][
5
,
4
][
4
,
1
][
2
,
3
]
[
2
,
3
][
5
,
4
][
0
,
3
][
4
,
6
]
0
[
2
,
4
][
5
,
3
][
0
,
4
][
4
,
1
]
[
2
,
4
][
0
,
4
][
5
,
3
]
0
[
4
,
1
][
5
,
4
][
2
,
3
][
4
,
6
][
0
,
3
]
[
4
,
1
][
5
,
3
][
4
,
6
][
2
,
4
][
5
,
4
][
0
,
3
]
0
[
2
,
3
][
0
,
4
]
[
4
,
6
][
4
,
1
][
5
,
4
][
5
,
3
][
2
,
3
]
0
[
0
,
4
][
0
,
3
][
2
,
4
]
[
5
,
3
][
2
,
4
][
4
,
1
][
0
,
4
][
4
,
6
][
2
,
3
][
0
,
3
][
5
,
4
]
0
[
0
,
3
][
0
,
4
][
2
,
3
][
2
,
4
][
4
,
1
][
4
,
6
][
5
,
3
][
5
,
4
0
[
5
,
4
][
4
,
6
][
2
,
3
][
4
,
1
][
0
,
3
][
0
,
4
][
2
,
4
]
0
[
5
,
3
]
In this table, the sum of the point in position
(
i
,
1
)
with the point in position
(
1
,
j
)
is the point in position
(
i
,
j
)
. We have, for example, that if we keep adding the point
P
=
(
0
,
3
)
to itself, we successively obtain:
2
P
=
(
2
,
3
),
3
P
=
(
5
,
4
),
4
P
=
(
4
,
6
),
5
P
=
(
4
,
1
),
6
P
=
(
5
,
3
),
7
P
=
(
2
,
4
),
8
P
=
(
0
,
4
),
9
P
=
O.
Thus we see that
P
has order 9 and hence
P
is a generator of the group which is,
therefore, cyclic.
(
,
)
Exercise 11.17
Use a loop that keeps adding the point
to itself by means of
EllipticAdd
, in the curve
ec327
, to compute the order of this point.
0
3
There is a theorem of Cassels on the structure of the group
E
(
F
q
)
that says that
this group is isomorphic to
Z
n
1
× Z
n
2
, where
n
1
and
n
2
are uniquely determined
