Cryptography Reference
In-Depth Information
Problems
9.1.
Show that the condition 4
a
3
+ 27
b
2
= 0mod
p
is fulfilled for the curve
y
2
x
3
+ 2
x
+ 2 mod 17
≡
(9.3)
9.2.
Perform the additions
1. (2
,
7)+(5
,
2)
2. (3
,
6)+(3
,
6)
in the group of the curve
y
2
x
3
+ 2
x
+ 2 mod 17. Use only a pocket calculator.
≡
9.3.
In this chapter the elliptic curve
y
2
x
3
+ 2
x
+ 2 mod 17 is given with #
E
= 19.
≡
Verify Hasse's theorem for this curve.
9.4.
Let us again consider the elliptic curve
y
2
x
3
+ 2
x
+ 2 mod 17. Why are
all
≡
points primitive elements?
Note
: In general it is not true that all elements of an elliptic curve are primitive.
9.5.
Let
E
be an elliptic curve defined over
Z
7
:
E
:
y
2
=
x
3
+ 3
x
+ 2
.
1. Compute all points on
E
over
Z
7
.
2. What is the order of the group? (Hint: Do not miss the neutral element
O
.)
3. Given the element
α
=(0
,
3), determine the order of
α
.Is
α
a primitive element?
2
150
2
250
, and computing
T
=
a
9.6.
In practice,
a
and
k
are both in the range
p
≈
···
·
P
and
y
0
=
k
·
P
is done using the Double-and-Add algorithm as shown in Sect. 9.2.
1. Illustrate how the algorithm works for
a
= 19 and for
a
= 160. Do
not
perform
elliptic curve operations, but keep
P
a variable.
2. How many (i) point additions and (ii) point doublings are required on average for
one “multiplication”? Assume that all integers have
n
=
bit.
3. Assume that all integers have
n
= 160 bit, i.e.,
p
is a 160-bit prime. Assume one
group operation (addition or doubling) requires 20
log
2
p
μ
sec. What is the time for one
double-and-add operation?
9.7.
Given an elliptic curve
E
over
Z
29
and the base point
P
=(8
,
10):
E
:
y
2
=
x
3
+ 4
x
+ 20 mod 29
.
·
Calculate the following point multiplication
k
P
using the Double-and-Add algo-
rithm. Provide the intermediate results after each step.
1.
k
= 9
2.
k
= 20