Chapter 5

Let \(E\) be the elliptic curve \(E: Y^{2}=X^{3}-2 X+4\) and let \(P=(0,2)\) and \(Q=(3,-5) .\) (You should check that \(P\) and \(Q\) are on the curve \(E .)\) (a) Compute \(P \oplus Q\). (b) Compute \(P \oplus P\) and \(Q \oplus Q\). (c) Compute \(P \oplus P \oplus P\) and \(Q \oplus Q \oplus Q\).

Check that the points \(P=(-1,4)\) and \(Q=(2,5)\) are points on the elliptic curve \(E: Y^{2}=X^{3}+17\). (a) Compute the points \(P \oplus Q\) and \(P \ominus Q\). (b) Compute the points \(2 P\) and \(2 Q\). (Bonus. How many points with integer coordinates can you find on \(E ?\) )

Suppose that the cubic polynomial \(X^{3}+A X+B\) factors as $$ X^{3}+A X+B=\left(X-e_{1}\right)\left(X-e_{2}\right)\left(X-e_{2}\right) . $$ Prove that \(4 A^{3}+27 B^{2}=0\) if and only if two (or more) of \(e_{1}, e_{2}\), and \(e_{3}\) are the same. (Hint. Multiply out the right-hand side and compare coefficients to relate \(A\) and \(B\) to \(e_{1}, e_{2}\), and \(e_{3 .)}\)

For each of the following elliptic curves \(E\) and finite fields \(\mathbb{F}_{p}\), make a list of the set of points \(E\left(\mathbb{F}_{p}\right)\). (a) \(E: Y^{2}=X^{3}+3 X+2\) over \(\mathbb{F}_{7}\). (b) \(E: Y^{2}=X^{3}+2 X+7\) over \(\mathbb{F}_{11}\). (c) \(E: Y^{2}=X^{3}+4 X+5\) over \(\mathbb{F}_{11}\). (d) \(E: Y^{2}=X^{3}+9 X+5\) over \(\mathbb{F}_{11}\). (e) \(E: Y^{2}=X^{3}+9 X+5\) over \(\mathbb{F}_{13}\).

Make an addition table for \(E\) over \(\mathbb{F}_{p}\), as we did in Table 5.1. (a) \(E: Y^{2}=X^{3}+X+2\) over \(\mathbb{F}_{5}\). (b) \(E: Y^{2}=X^{3}+2 X+3\) over \(\mathbb{F}_{7}\). (c) \(E: Y^{2}=X^{3}+2 X+5\) over \(\mathbb{F}_{11}\). You may want to write a computer program for (c), since \(E\left(\mathbb{F}_{11}\right)\) has a lot of points!

Let \(E\) be the elliptic curve $$ E: y^{2}=x^{3}+x+1 $$ Compute the number of points in the group \(E\left(\mathbb{F}_{p}\right)\) for each of the following primes: (a) \(p=3\). (b) \(p=5\). (c) \(p=7\). (d) \(p=11\). In each case, also compute the trace of Frobenius $$ t_{p}=p+1-\\# E\left(\mathbb{F}_{p}\right) $$ and verify that \(\left|t_{p}\right|\) is smaller than \(2 \sqrt{p}\).

Let \(E\) be the elliptic curve $$ E: y^{2}=x^{3}+x+1 $$ and let \(P=(4,2)\) and \(Q=(0,1)\) be points on \(E\) modulo 5 . Solve the elliptic curve discrete logarithm problem for \(P\) and \(Q\), that is, find a positive integer \(n\) such that \(Q=n P\).

Let \(E\) be an elliptic curve over \(\mathbb{F}_{p}\) and let \(P\) and \(Q\) be points in \(E\left(\mathbb{F}_{p}\right)\). Assume that \(Q\) is a multiple of \(P\) and let \(n_{0}>0\) be the smallest solution to \(Q=n P\). Also let \(s>0\) be the smallest solution to \(s P=\mathcal{O}\). Prove that every solution to \(Q=n P\) looks like \(n_{0}+i s\) for some \(i \in \mathbb{Z}\). (Hint. Write \(n\) as \(n=i s+r\) for some \(0 \leq r

Alice and Bob agree to use elliptic Diffie-Hellman key exchange with the prime, elliptic curve, and point $$ p=2671, \quad E: Y^{2}=X^{3}+171 X+853, \quad P=(1980,431) \in E\left(\mathbb{F}_{2671}\right) . $$ (a) Alice sends Bob the point \(Q_{A}=(2110,543)\). Bob decides to use the secret multiplier \(n_{B}=1943\). What point should Bob send to Alice? (b) What is their secret shared value? (c) How difficult is it for Eve to figure out Alice's secret multiplier \(n_{A}\) ? If you know how to program, use a computer to find \(n_{A}\). (d) Alice and Bob decide to exchange a new piece of secret information using the same prime, curve, and point. This time Alice sends Bob only the \(x\)-coordinate \(x_{A}=2\) of her point \(Q_{A}\). Bob decides to use the secret multiplier \(n_{B}=875\). What single number modulo \(p\) should Bob send to Alice, and what is their secret shared value?

A shortcoming of using an elliptic curve \(E\left(\mathbb{F}_{p}\right)\) for cryptography is the fact that it takes two coordinates to specify a point in \(E\left(\mathbb{F}_{p}\right)\). However, as discussed briefly at the end of Section 5.4.2, the second coordinate actually conveys very little additional information. (a) Suppose that Bob wants to send Alice the value of a point \(R \in E\left(\mathbb{F}_{p}\right)\). Explain why it suffices for Bob to send Alice the \(x\)-coordinate of \(R=\left(x_{R}, y_{R}\right)\) together with the single bit $$ \beta_{R}= \begin{cases}0 & \text { if } 0 \leq y_{R}<\frac{1}{2} p, \\ 1 & \text { if } \frac{1}{2} p

Let \(E\) be an elliptic curve given by a generalized Weierstrass equation $$ E: Y^{2}+a_{1} X Y+a_{3} Y=X^{3}+a_{2} X^{2}+a_{4} X+a_{6} . $$ Let \(P_{1}=\left(x_{1}, y_{1}\right)\) and \(P_{2}=\left(x_{2}, y_{2}\right)\) be points on \(E\). Prove that the following algorithm computes their sum \(P_{3}=P_{1}+P_{2}\). First, if \(x_{1}=x_{2}\) and \(y_{1}+y_{2}+a_{1} x_{2}+a_{3}=0\), then \(P_{1}+P_{2}=\mathcal{O} .\) Otherwise define quantities \(\lambda\) and \(\nu\) as follows: $$ \begin{array}{lll} {\left[\text { If } x_{1} \neq x_{2}\right]} & \lambda=\frac{y_{2}-y_{1}}{x_{2}-x_{1}}, & \nu=\frac{y_{1} x_{2}-y_{2} x_{1}}{x_{2}-x_{1}}, \\ {\left[\text { If } x_{1}=x_{2}\right]} & \lambda=\frac{3 x_{1}^{2}+2 a_{2} x_{1}+a_{4}-a_{1} y_{1}}{2 y_{1}+a_{1} x_{1}+a_{3}}, & \nu=\frac{-x_{1}^{3}+a_{4} x_{1}+2 a_{6}-a_{3} y_{1}}{2 y_{1}+a_{1} x_{1}+a_{3}} . \end{array} $$ Then $$ P_{3}=P_{1}+P_{2}=\left(\lambda^{2}+a_{1} \lambda- a_{2}-x_{1}-x_{2},-\left(\lambda+a_{1}\right) x_{3}-\nu-a_{3}\right) . $$

Let \(\tau(\alpha)=\alpha^{p}\) be the Frobenius map on \(\mathbb{F}_{p^{k}}\). (a) Prove that $$ \tau(\alpha+\beta)=\tau(\alpha)+\tau(\beta) \quad \text { and } \quad \tau(\alpha \cdot \beta)=\tau(\alpha) \cdot \tau(\beta) \quad \text { for all } \alpha, \beta \in \mathbb{F}_{p^{k}} $$ (Hint. For the addition formula, use the binomial theorem (Theorem 4.10).) (b) Prove that \(\tau(\alpha)=\alpha\) for all \(\alpha \in \mathbb{F}_{p}\). (c) Let \(E\) be an elliptic curve over \(\mathbb{F}_{p}\) and let \(\tau(x, y)=\left(x^{p}, y^{p}\right)\) be the Frobenius map from \(E\left(\mathbb{F}_{p^{k}}\right)\) to itself. Prove that $$ \tau(P+Q)=\tau(P)+\tau(Q) \quad \text { for all } P \in E\left(\mathbb{F}_{p^{k}}\right) $$

Let \(E\) be an elliptic curve over \(\mathbb{F}_{q}\) and let \(P, Q \in E\left(\mathbb{F}_{q}\right)[\ell]\). Prove that the Weil pairing and the Tate pairing are related by the formula $$ e_{\ell}(P, Q)=\frac{\tau(P, Q)}{\tau(Q, P)}, $$ provided that the Tate pairings on the right-hand side are computed properly. Thus the Weil pairing requires approximately twice as much work to compute as does the Tate pairing.

Let \(E\) be an elliptic curve over \(\mathbb{F}_{p}\) and let \(\ell\) be a prime. Suppose that \(E\left(\mathbb{F}_{p}\right)\) contains a point of order \(\ell\) and that \(\ell>\sqrt{p}+1\). Prove that \(E\left(\mathbb{F}_{p}\right)[\ell] \cong \mathbb{Z} / \ell \mathbb{Z}\).

Let \(E\) be an elliptic curve over a finite field \(\mathbb{F}_{q}\) and let \(\ell\) be a prime. Suppose that we are given four points \(P, a P, b P, c P \in E\left(\mathbb{F}_{q}\right)[\ell]\). The (elliptic) decision DiffieHellman problem is to determine whether \(c P\) is equal to \(a b P\). Of course, if we could solve the Diffie-Hellman problem itself, then we could compute \(a b P\) and compare it with \(c P\), but the Diffie-Hellman problem is often difficult to solve. Suppose that there exists a distortion map \(\phi\) for \(E[\ell]\). Show how to use the modified Weil pairing to solve the elliptic decision Diffie-Hellman problem without actually having to compute \(a b P\).

Let \(E\) be the elliptic curve \(E: y^{2}=x^{3}+x\) and let \(\phi(x, y)=(-x, \alpha y)\) be the map described in Proposition 5.51. Prove that \(\phi(\phi(P))=-P\) for all \(P \in E\). (Intuitively, \(\phi\) behaves like multiplication by \(\sqrt{-1}\) when it is applied to points of \(E\).)

Let \(E\) be the elliptic curve \(E: y^{2}=x^{3}+x\) and let \(\phi(x, y)=(-x, \alpha y)\) be the map described in Proposition 5.51. Prove that \(\phi(\phi(P))=-P\) for all \(P \in E\). (Intuitively, \(\phi\) behaves like multiplication by \(\sqrt{-1}\) when it is applied to points of \(E\).)

Let \(E\) be the elliptic curve $$ E: y^{2}=x^{3}+1 $$ over a field \(K\), and suppose that \(K\) contains an element \(\beta \neq 1\) satisfying \(\beta^{3}=1\). (We say that \(\beta\) is a primitive cube root of unity.) Define a map \(\phi\) by $$ \phi(x, y)=(\beta x, y) \quad \text { and } \quad \phi(\mathcal{O})=\mathcal{O} . $$ (a) Let \(P \in E(K)\). Prove that \(\phi(P) \in E(K)\). (b) Prove that \(\phi\) respects the addition law on \(E\), i.e., \(\phi\left(P_{1}+P_{2}\right)=\phi\left(P_{1}\right)+\phi\left(P_{2}\right)\) for all \(P_{1}, P_{2} \in E(K)\).