« nazaj
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}}$.
| $x$ |
$x^2$ |
$x^3 + x + 6$ |
| 0 |
0 |
$6$ |
| 1 |
1 |
$8$ |
| 2 |
4 |
$5 = 4^2 = 7^2$ |
| 3 |
9 |
$3 = 5^2 = 6^2$ |
| 4 |
5 |
$8$ |
| 5 |
3 |
$4 = 2^2 = 9^2$ |
| 6 |
3 |
$8$ |
| 7 |
5 |
$4 = 2^2 = 9^2$ |
| 8 |
9 |
$9 = 3^2 = 8^2$ |
| 9 |
4 |
$7$ |
| 10 |
1 |
$4 = 2^2 = 9^2$ |
Points on the elliptic curve:
- $\mathcal{O}$
- $(2, 4) = 4P = -8Q = 5Q$
- $(2, 7) = -4P = 8Q$
- $(3, 5) = P + Q = -Q = 12Q$
- $(3, 6) = Q$
- $(5, 2) = 5P = -10Q = 3Q$
- $(5, 9) = -5P = 8P = 10Q$
- $(7, 2) = -2P = 4Q$
- $(7, 9) = 2P = -4Q = 9Q$
- $(8, 3) = P = -2Q = 11Q$
- $(8, 8) = -P = 12P = 2Q$
- $(10, 2) = 10P = 6Q$
- $(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$.
- Compute the public key $Q = dP$.
- Encrypt the plaintext $m = 7$ and then decrypt the obtained ciphertext. Use the random value $r = 4$.
- $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$
-
- $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.
-
Show that subtraction over elliptic curves has the same complexity as addition.
-
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?
-
Show how computing a multiple of a point on an elliptic curve can be done using the format above. What is the expected speedup?