IV054 Coding, Cryptography and Cryptographic Protocols
2012 - Exercises VIII.
1. Consider the elliptic curve E : y2
= x3
+ 3x2
+ 6x + 17 over Z23.
(a) Verify that the point P = (2, 7) lies on E.
(b) Using a transformation into the form y2
= x3
+ ax + b compute the point 2P.
2. Consider the following primality test. An integer n > 0 is a prime if and only if n divides 2n
− 2.
Prove or disprove both implications.
3. Consider the elliptic curve
E = {O} ∪ {(x, y) ∈ Z2
7 | y2
= x3
+ 2x + 1}.
(a) Find all points of E. Compare the number of points with the Hasse’s theorem.
(b) For each point P ∈ E, compute −P and check that it lies on the curve as well.
(c) Show that (E, +) is isomorphic to Z|E|.
4. Suppose n = pq, where p, q are primes. Let integers i, j, k and L with k = 0 satisfy
L = i(p − 1), L = j(q − 1) + k and ak
≡ 1 (mod q).
Let a be a randomly chosen integer satisfying p a and q a. Prove that
gcd(aL
− 1, n) = p.
5. (a) Use the ρ-algorithm with f(x) = x2
+ 1 and x0 = 2 to find a factor of n = 8383.
(b) Try to factorize n = 551 using the elliptic curve E : y2
= x3
+ 4x + 4 and
(i) point P1 = (1, 3),
(ii) point P2 = (0, 2).
6. Prove the following theorems.
(a) If n is even and n > 2, then 2n
− 1 is composite.
(b) If 3 | n and n > 3, then 2n
− 1 is composite.
(c) If 2n
− 1 is a prime, then n is a prime number.
7. Let n = pk
where p is a prime and k > 0. Compute the sum of all positive divisors of n.
8. Consider the elliptic curve variant of the Diffie-Hellman key exchange protocol. Suppose Alice
chooses random secret na = 11, Bob chooses nb = 7. Public information contains an elliptic curve
E : y2
= x3
+ 4x + 20 (mod 29) and its point P = (1, 5). Show in detail steps of the protocol.