ECC Sample Problems 1

Tools needed before the problemsSearch on YouTubeBookmarkSaved

This page solves Assignment 1 (25 marks). It has four problems. Each problem needs one of three computations. Learn the setup lines first. Then each problem is only arithmetic.

RSA key generationSearch on YouTubeBookmarkSaved

Given primes $p$ and $q$ and a public key $e$:

$n = p \cdot q, \qquad \varphi(n) = (p-1)(q-1)$

The private key $d$ satisfies $e \cdot d \equiv 1 \pmod{\varphi(n)}$, so $d = e^{-1} \bmod \varphi(n)$.

Diffie-Hellman key exchangeSearch on YouTubeBookmarkSaved

Common open parameters are a prime $q$ and a primitive root $\alpha$ of $q$. Party A picks a private key $X_A$ and publishes:

$Y_A = \alpha^{X_A} \bmod q$

Party B does the same with $X_B$ and secretly computes:

$K = Y_B^{X_A} \bmod q = Y_A^{X_B} \bmod q$

Both raise the other party's public key to their own private key, so the shared key is equal on both sides.

Elliptic curve point additionSearch on YouTubeBookmarkSaved

For $P = (x_P, y_P)$ and $Q = (x_Q, y_Q)$ with $P \neq Q$ on the curve $y^2 = x^3 + ax + b$ over a field of modulus $p$:

$\lambda = \frac{y_Q - y_P}{x_Q - x_P} \bmod p$

$x_R = (\lambda^2 - x_P - x_Q) \bmod p$

$y_R = \left(\lambda(x_P - x_R) - y_P\right) \bmod p$

$P + Q = (x_R, y_R)$

The slope $\lambda$ contains a division modulo $p$. To divide, multiply by the inverse: $\dfrac{5}{7} \bmod p = 5 \cdot (7^{-1}) \bmod p$. For point doubling, with $P = Q$:

$\lambda = \frac{3x_P^2 + a}{2y_P} \bmod p$

Problem 1: RSA private key (5 marks)Search on YouTubeBookmarkSaved

Statement. Participant A in an RSA cryptosystem uses primes $p = 13$ and $q = 17$. The public key of A is $e = 35$. Find the private key of A.

Step 1, modulus and totient.

$n = 13 \times 17 = 221$

$\varphi(n) = (13-1)(17-1) = 12 \times 16 = 192$

Step 2, invert $e$ modulo $\varphi(n)$. Find $d$ with $35\,d \equiv 1 \pmod{192}$.

Step 3, answer.

$d = 11$

$35 \times 11 = 385 = 2 \times 192 + 1$, so $35 \cdot 11 \equiv 1 \pmod{192}$ and the private key of A is 11.

Problem 2: Diffie-Hellman key exchange (5 marks)Search on YouTubeBookmarkSaved

Statement. A and B agree on prime $q = 17$ and primitive root $\alpha = 5$. A chooses $X_A = 4$ and B chooses $X_B = 6$. Find the key they exchange.

Step 1, public key of A.

$Y_A = 5^4 \bmod 17 = 625 \bmod 17$

$17 \times 36 = 612$, so $625 - 612 = 13$:

$Y_A = 13$

Step 2, public key of B.

$Y_B = 5^6 \bmod 17 = 15625 \bmod 17$

$17 \times 919 = 15623$, so $15625 - 15623 = 2$:

$Y_B = 2$

Step 3, shared key from B's side. A computes $K = Y_B^{X_A} \bmod q$:

$K = 2^4 \bmod 17 = 16$

Step 4, cross-check from A's side. B computes $K = Y_A^{X_B} \bmod q$:

$K = 13^6 \bmod 17 = (13^2)^3 \bmod 17 = 169^3 \bmod 17 = 16^3 \bmod 17 = 4096 \bmod 17 = 16$

$17 \times 240 = 4080$, and $4096 - 4080 = 16$. Both paths give the same value:

$K = 16$

Problem 3: point addition on an elliptic curve (10 marks)Search on YouTubeBookmarkSaved

Statement. An elliptic curve is defined over a finite field of integer modulus 23: $y^2 = x^3 + 3x + 8$, with $p = 23$. Given $P = (0, 10)$ and $Q = (7, 2)$, compute $P + Q$.

Step 1, slope $\lambda$.

$\lambda = \frac{y_Q - y_P}{x_Q - x_P} \bmod p = \frac{2 - 10}{7 - 0} \bmod 23 = \frac{-8}{7} \bmod 23$

Step 2, invert 7 modulo 23. Solve $7x \equiv 1 \pmod{23}$ by trial:

So $7^{-1} \bmod 23 = 10$. Then:

$\lambda = -8 \times 10 \bmod 23 = -80 \bmod 23$

Add a multiple of the modulus: $-80 + 92 = 12$, so:

$\lambda = 12$

Step 3, $x_R$.

$x_R = (\lambda^2 - x_P - x_Q) \bmod p = (144 - 0 - 7) \bmod 23 = 137 \bmod 23 = 22$

Because $137 - 115 = 22$.

Step 4, $y_R$.

$y_R = \left(\lambda(x_P - x_R) - y_P\right) \bmod p = \left(12(0 - 22) - 10\right) \bmod 23 = (-264 - 10) \bmod 23$

$264 = 23 \times 11 + 11$, so $-264 \equiv -11 \equiv 12 \pmod{23}$, hence $12 - 10 = 2$:

$y_R = 2$

Answer.

$P + Q = (22, 2)$

Problem 4: membership on an elliptic curve (5 marks)Search on YouTubeBookmarkSaved

Statement. Check whether the points $(1, 6)$ and $(1, 5)$ lie on the elliptic curve $y^2 = x^3 + 5x + 7$ over the finite field with modulus 23.

Test for $(1, 6)$. Left side and right side, both reduced by 23:

$y^2 \bmod 23 = 6^2 \bmod 23 = 36 \bmod 23 = 13$

$x^3 + 5x + 7 \bmod 23 = (1 + 5 + 7) \bmod 23 = 13$

$13 = 13$, so $(1, 6)$ is on the curve.

Test for $(1, 5)$.

$y^2 \bmod 23 = 5^2 = 25 \bmod 23 = 2$

The right side is again $13$, and $2 \neq 13$, so $(1, 5)$ is not on the curve.

Error pattern to avoidSearch on YouTubeBookmarkSaved

The four problems share one trap. Each division is a multiplication by a modular inverse. Each result must be in the range 0 to $p-1$: $-80 \bmod 23$ is $12$, $137 \bmod 23$ is $22$, $-274 \bmod 23$ is $2$.

Quick self-testSearch on YouTubeBookmarkSaved

In the RSA problem, what are $n$, $\varphi(n)$ and $d$ for $p = 13$, $q = 17$, $e = 35$?

$n = 221$, $\varphi(n) = 12 \times 16 = 192$, and $d = 11$, because $35 \times 11 = 385 = 2 \times 192 + 1$.

In the Diffie-Hellman problem with $q = 17$, $\alpha = 5$, $X_A = 4$, $X_B = 6$, what are $Y_A$, $Y_B$ and $K$?

$Y_A = 5^4 \bmod 17 = 13$, $Y_B = 5^6 \bmod 17 = 2$, $K = 2^4 \bmod 17 = 16$, and the same $16$ follows from $13^6 \bmod 17 = 16$.

How do you divide 5 by 7 in the field of modulus 23?

Find $7^{-1} \bmod 23 = 10$, because $70 \equiv 1 \pmod{23}$. Then $5 \cdot 10 = 50 \equiv 7 \pmod{23}$.

Give the three element formulas for $P + Q$ on $y^2 = x^3 + ax + b \bmod p$.

$\lambda = (y_Q - y_P)/(x_Q - x_P) \bmod p$, then $x_R = (\lambda^2 - x_P - x_Q) \bmod p$, then $y_R = (\lambda(x_P - x_R) - y_P) \bmod p$, and the sum is $(x_R, y_R)$.

For $P = (0,10)$ and $Q = (7,2)$ on $y^2 = x^3 + 3x + 8$ with $p = 23$, what is $P + Q$?

$\lambda = -8 \cdot 7^{-1} = -80 \bmod 23 = 12$, $x_R = 144 - 7 = 137 \bmod 23 = 22$, $y_R = 12(0-22) - 10 = -274 \bmod 23 = 2$. The sum $(22, 2)$ follows.

Which of $(1,6)$ and $(1,5)$ lies on $y^2 = x^3 + 5x + 7$ mod 23, and why?

$(1, 6)$ lies on it: $36 \bmod 23 = 13$ equals $(1 + 5 + 7) \bmod 23 = 13$. $(1, 5)$ does not: $25 \bmod 23 = 2$ differs from $13$.

When must the doubling slope $\lambda = (3x_P^2 + a)/(2y_P)$ be used instead of the secant slope?

When $P = Q$, that is point doubling. The secant $\lambda = (y_Q - y_P)/(x_Q - x_P)$ divides by $x_Q - x_P$, which is zero there.

What is the slope formula for doubling, and how is it different from the addition slope?

Doubling uses $\lambda = (3x_P^2 + a)/(2y_P) \bmod p$, where $a$ is the $x$-coefficient of the curve. Addition uses the difference of the $y$ values over the difference of the $x$ values.