Cryptography Reference
In-Depth Information
y
P
•
x
−
P
Fig. 9.6
The inverse of a point
P
on an elliptic curve
E
:
y
2
x
3
+ 2
x
+ 2 mod 17
.
≡
We want to double the point
P
=(5
,
1).
2
P
=
P
+
P
=(5
,
1)+(5
,
1)=(
x
3
,
y
3
)
3
x
1
+
a
2
y
1
1)
−
1
(3
5
2
+ 2)=2
−
1
s
=
=(2
·
·
·
9
≡
9
·
9
≡
13 mod 17
x
3
=
s
2
x
2
= 13
2
−
x
1
−
−
5
−
5 = 159
≡
6 mod 17
y
3
=
s
(
x
1
−
x
3
)
−
y
1
= 13(5
−
6)
−
1 =
−
14
≡
3 mod 17
2
P
=(5
,
1)+(5
,
1)=(6
,
3)
For illustrative purposes we check whether the result 2
P
=(6
,
3) is actually a point
on the curve by inserting the coordinates into the curve equation:
y
2
x
3
+ 2
≡
·
x
+ 2 mod 17
3
2
6
3
+ 2
≡
·
6 + 2 mod 17
9 = 230
≡
9 mod 17
9.2 Building a Discrete Logarithm Problem with Elliptic Curves
What we have done so far is to establish the group operations (point addition and
doubling), we have provided an identity element, and we have shown a way of
finding the inverse for any point on the curve. Thus, we now have all necessary
requirements in place to motivate the following theorem:
