---
tags: vaje, kirv, ec
hackmd: https://hackmd.io/cBbo_MHgQbq-Dmmnc7FuQg
plugins: mathjax
---
# 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:
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 <i>$\mathbb{Z}{_{11}}$</i>.
The Simplified ECIES has <i>$\mathbb{Z}{_{11}^{*}}$</i> 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?