Cryptography and computer security - Tutorial 12.1.2021

Elliptic curves

Groups on elliptic curves over prime fields

• General form: \(E : y^2 \equiv x^3 + ax + b \pmod{p}\), \(p\) prime, \(4a^3 + 27b^2 \not\equiv 0 \pmod{p}\)
• \(E = \lbrace (x, y) \in {\mathbb{Z}_p^2} \mid y^2 \equiv x^3 + ax + b \pmod{p} \rbrace \cup \lbrace \mathcal{O} \rbrace\)
• For \(P = ({P_x}, {P_y}), Q = ({Q_x}, {Q_y}) \in E\):
  • \(-P = ({P_x}, -{P_y})\)
  • \(P + \mathcal{O} = \mathcal{O} + P = P\)
  • \(P + (-P) = \mathcal{O}\)
  • \(P + Q = R = ({R_x}, {R_y})\), where
    • if \(P \ne Q\), then \(\lambda = { {P_y} - {Q_y} \over {P_x} - {Q_x}}\)
    • if \(P = Q\), then \(\lambda = {3 {P_x^2} + a \over 2 {P_y}}\)
    • \({R_x} = \lambda^2 - {P_x} - {Q_x}\)
    • \({R_y} = \lambda ({P_x} - {R_x}) - {P_y}\)

Simplified ECIES

• Domain parameters:
  • elliptic curve \(E : y^2 \equiv x^3 + ax + b \pmod{p}\), where \(p\) is prime
  • group generator \(P\) of prime order \(n\) (i.e., \(E = \langle P \rangle = \lbrace kP \mid 0 \le k \le n-1 \rbrace\))
• Key generation:
  • private key \(d \stackrel{R}{\in} {\mathbb{Z}_n^{*}}\)
  • public key \(Q = dP\)
• Encryption of \(m \in {\mathbb{Z}_n^{*}}\):
  • choose \(r \stackrel{R}{\in} {\mathbb{Z}_n^{*}}\)
  • compute \(R = rP\)
  • compute \(S = rQ = ({S_x}, {S_y}) \ne \mathcal{O}\)
  • output \(c = (R, m {S_x} \bmod{p})\)
• Decryption of \(c = (R, z) \in E \times {\mathbb{Z}_p^{*}}\):
  • compute \(S = dR = ({S_x}, {S_y}) \ne \mathcal{O}\)
  • output \(m = z {S_x^{-1}} \bmod{p}\)

Exercise 1

Does the elliptic curve equation \(y^2 = x^3 + 10x + 5\) define a group over \({\mathbb{Z}_{17}}\)?

• \(a = 10\), \(b = 5\), \(p = 17\)
• \(4a^3 + 27b^2 \bmod{p} = 40 \cdot 100 + 27 \cdot 25 \bmod{17} = 6 \cdot (-2) + 10 \cdot 8 \bmod{17} = 5 + (-5) \bmod{17} = 0\)
• The given elliptic curve equation does not define a group.

Exercise 2

Find all points on the elliptic curve \(y^2 = x^3 + x + 6\) over \({\mathbb{Z}_{11}}\).

Points on the elliptic curve:

1. \(\mathcal{O}\)
2. \((2, 4) = 4P = -8Q = 5Q\)
3. \((2, 7) = -4P = 8Q\)
4. \((3, 5) = P + Q = -Q = 12Q\)
5. \((3, 6) = Q\)
6. \((5, 2) = 5P = -10Q = 3Q\)
7. \((5, 9) = -5P = 8P = 10Q\)
8. \((7, 2) = -2P = 4Q\)
9. \((7, 9) = 2P = -4Q = 9Q\)
10. \((8, 3) = P = -2Q = 11Q\)
11. \((8, 8) = -P = 12P = 2Q\)
12. \((10, 2) = 10P = 6Q\)
13. \((10, 9) = 3P = 7Q\)

(\(P\) and \(Q\) from exercise 3)

Exercise 3

Let \(P = (8, 3)\) and \(Q = (3, 6)\) be points on the elliptic curve \(y^2 = x^3 + x + 6\) over \({\mathbb{Z}_{11}}\). Compute \(P + Q\) and \(5P\).

• \(P = (8, 3)\), \(Q = (3, 6)\)
• \(P + Q = R = (3, 5)\)
  • \(\lambda = {3 - 6 \over 8 - 3} = -3 \cdot 5^{-1} = -3 \cdot (-2) = 6\)
  • \({R_x} = 6^2 - 8 - 3 = 3\)
  • \({R_y} = 6 (8 - 3) - 3 = -3 - 3 = 5\)
• \(5P = (4 + 1)P = (2^2 + 2^0)P\)
  • \(2P = P + P = (7, 9)\)
    • \(\lambda = {3 \cdot 8^2 + 1 \over 2 \cdot 3} = 6/6 = 1\)
    • \({(2P)_x} = 1^2 - 2 \cdot 8 = 7\)
    • \({(2P)_y} = 1(8 - 7) - 3 = 9\)
  • \(4P = 2P + 2P = (2, 4)\)
    • \(\lambda = {3 \cdot 7^2 + 1 \over 2 \cdot 9} = {5 \over 7} = 5 \cdot 8 = 7\)
    • \({(4P)_x} = 7^2 - 2 \cdot 7 = 2\)
    • \({(4P)_y} = 7(7 - 2) - 9 = 4\)
  • \(5P = P + 4P = (5, 2)\)
    • \(\lambda = {3 - 4 \over 8 - 2} = {-1 \over 6} = -2 = 9\)
    • \({(5P)_x} = 9^2 - 8 - 2 = 4 - 10 = 5\)
    • \({(5P)_y} = 9(8 - 5) - 3 = 9 \cdot 3 - 3 = 2\)

Exercise 4

Let \(P = (2, 4)\) be a generator of order \(n = 13\) of the group on the elliptic curve \(y^2 = x^3 + x + 6\) over \(\mathbb{Z}{_{11}}\). The Simplified ECIES has \(\mathbb{Z}{_{11}^{*}}\) as its plaintext space. Suppose that the private key is \(d = 3\).

1. Compute the public key \(Q = dP\).
2. Encrypt the plaintext \(m = 7\) and then decrypt the obtained ciphertext. Use the random value \(r = 4\).

1. \(Q = dP = 3P = 2P + P = (8, 8)\)

   • \(2P = P + P = (5, 9)\)
     • \(\lambda = {3 \cdot 2^2 + 1 \over 2 \cdot 4} = {2 \over 8} = 3\)
     • \({(2P)_x} = 3^2 - 2 \cdot 2 = 9 - 4 = 5\)
     • \({(2P)_y} = 3(2 - 5) - 4 = -3 \cdot 3 - 4 = 9\)
   • \(3P = 2P + P = (8, 8)\)
     • \(\lambda = {9 - 4 \over 5 - 2} = {5 \over 3} = 5 \cdot 4 = 9\)
     • \({(3P)_x} = 9^2 - 2 - 5 = 8\)
     • \({(3P)_y} = 9(5 - 8) - 9 = 9 \cdot (-3) - 9 = 8\)
2. • \(R = rP = 4P = 2P + 2P = (10, 9)\)
     • \(\lambda = {3 \cdot 5^2 + 1 \over 2 \cdot 9} = {-1 \over -4} = 3\)
     • \({R_x} = 3^2 - 2 \cdot 5 = 10\)
     • \({R_y} = 3(5 - 10) - 9 = -3 \cdot 5 - 9 = 9\)
   • \(S = rQ = 4Q = (2, 7)\)
   • \(z = {S_x} m = 2 \cdot 7 = 3\)
   • \(c = (R, z) = ((10, 9), 3)\)

Exercise 5

We will show how computing a multiple of a point on an elliptic curve can be sped up.

1. Show that subtraction over elliptic curves has the same complexity as addition.

2. Show that any integer \(n\) can be written as

   \[ n = \sum_{i=0}^{\ell-1} c_i 2^i , \]

   where for all \(i\), \({c_i} \in \lbrace -1, 0, 1 \rbrace\), and \({c_i} \ne 0\) implies \({c_{i+1}} = 0\). How many bits do we need to store a number in this format?

3. Show how computing a multiple of a point on an elliptic curve can be done using the format above. What is the expected speedup?