Elliptic Curves and Cryptography

Prev: Combinatorics Probability and Information Theory Next: Lattices and Cryptography

Exercises

Section 6.1. Elliptic Curves

6.1

Let $E$ be the elliptic curve $E:Y^2=X^3-2X+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$.

6.2

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 $2P$ and $2Q$.

Bonus: How many points with integer coordinates can you find on $E$?

6.3

Suppose that the cubic polynomial $X^3+AX+B$ factors as

$$X^3+AX+B=(X-e_1)(X-e_2)(X-e_3).$$

Prove that $4A^3+27B^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$.

6.4

Sketch each of the following curves, as was done in Fig. 6.1 on page 300.

(a) $E:Y^2=X^3-7X+3$.

(b) $E:Y^2=X^3-7X+9$.

(c) $E:Y^2=X^3-7X-12$.

(d) $E:Y^2=X^3-3X+2$.

(e) $E:Y^2=X^3$.

Notice that the curves in (d) and (e) have ${\Delta }_E=0$, so they are not elliptic curves. How do their pictures differ from the pictures in (a), (b), and (c)? Each of the curves (d) and (e) has one point that is somewhat unusual. These unusual points are called singular points.

Section 6.2. Elliptic Curves over Finite Fields

6.5

For each of the following elliptic curves $E$ and finite fields ${\mathbb{F}}_p$, make a list of the set of points $E({\mathbb{F}}_p)$.

(a) $E:Y^2=X^3+3X+2$ over ${\mathbb{F}}_7$.

(b) $E:Y^2=X^3+2X+7$ over ${\mathbb{F}}_{11}$.

(c) $E:Y^2=X^3+4X+5$ over ${\mathbb{F}}_{11}$.

(d) $E:Y^2=X^3+9X+5$ over ${\mathbb{F}}_{11}$.

(e) $E:Y^2=X^3+9X+5$ over ${\mathbb{F}}_{13}$.

6.6

Make an addition table for $E$ over ${\mathbb{F}}_p$, as we did in Table 6.1.

(a) $E:Y^2=X^3+X+2$ over ${\mathbb{F}}_5$.

(b) $E:Y^2=X^3+2X+3$ over ${\mathbb{F}}_7$.

(c) $E:Y^2=X^3+2X+5$ over ${\mathbb{F}}_{11}$.

You may want to write a computer program for (c), since $E({\mathbb{F}}_{11})$ has a lot of points.

6.7

Let $E$ be the elliptic curve

$$E:y^2=x^3+x+1.$$

Compute the number of points in the group $E({\mathbb{F}}_p)$ 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({\mathbb{F}}_p)$$

and verify that $|t_p|$ is smaller than $2\sqrt{p}$.

Section 6.3. The Elliptic Curve Discrete Logarithm Problem

6.8

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=nP$.

6.9

Let $E$ be an elliptic curve over ${\mathbb{F}}_p$ and let $P$ and $Q$ be points in $E({\mathbb{F}}_p)$. Assume that $Q$ is a multiple of $P$ and let $n_0>0$ be the smallest solution to $Q=nP$. Also let $s>0$ be the smallest solution to $sP=O$. Prove that every solution to $Q=nP$ looks like $n_0+is$ for some $i\in \mathbb{Z}$. Hint: Write $n$ as $n=is+r$ for some $0\le r<s$ and determine the value of $r$.

6.10

Let $\{P_1,P_2\}$ be a basis for $E[m]$. The Basis Problem for $\{P_1,P_2\}$ is to express an arbitrary point $P\in E[m]$ as a linear combination of the basis vectors, i.e., to find $n_1$ and $n_2$ so that $P=n_1{P}_1+n_2{P}_2$. Prove that an algorithm that solves the basis problem for $\{P_1,P_2\}$ can be used to solve the ECDLP for points in $E[m]$.

6.11

Use the double-and-add algorithm (Table 6.3) to compute $nP$ in $E({\mathbb{F}}_p)$ for each of the following curves and points, as we did in Fig. 6.4.

(a) $E:Y^2=X^3+23X+13$, $p=83$, $P=(24,14)$, $n=19$.

(b) $E:Y^2=X^3+143X+367$, $p=613$, $P=(195,9)$, $n=23$.

(c) $E:Y^2=X^3+1828X+1675$, $p=1999$, $P=(1756,348)$, $n=11$.

(d) $E:Y^2=X^3+1541X+1335$, $p=3221$, $P=(2898,439)$, $n=3211$.

6.12

Convert the proof of Proposition 6.18 into an algorithm and use it to write each of the following numbers $n$ as a sum of positive and negative powers of 2 with at most $\frac{1}{2}\lfloor \log n\rfloor +1$ nonzero terms. Compare the number of nonzero terms in the binary expansion of $n$ with the number of nonzero terms in the ternary expansion of $n$.

(a) $349$.

(b) $9337$.

(c) $38728$.

(d) $8379483273489$.

6.13

In Sect. 5.5 we gave an abstract description of Pollard’s rho method, and in Sect. 5.5.2 we gave an explicit version to solve the discrete logarithm problem in ${\mathbb{F}}_p$. Adapt this material to create a Pollard rho algorithm to solve the ECDLP.

Section 6.4. Elliptic Curve Cryptography

6.14

Alice and Bob agree to use elliptic Diffie-Hellman key exchange with the prime, elliptic curve, and point

$$p=2671,E:Y^2=X^3+171X+853,P=(1980,431)\in E({\mathbb{F}}_{2671}).$$

(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?

6.15

Exercise 2.10 on page 109 describes a multistep public key cryptosystem based on the discrete logarithm problem for ${\mathbb{F}}_p$. Describe a version of this cryptosystem that uses the elliptic curve discrete logarithm problem. You may assume that Alice and Bob know the order of the point $P$ in the group $E({\mathbb{F}}_p)$, i.e., they know the smallest integer $N\ge 1$ with the property that $NP=O$.

6.16

A shortcoming of using an elliptic curve $E({\mathbb{F}}_p)$ for cryptography is the fact that it takes two coordinates to specify a point in $E({\mathbb{F}}_p)$. However, as discussed briefly at the end of Sect. 6.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({\mathbb{F}}_p)$. Explain why it suffices for Bob to send Alice the $x$-coordinate of $R=(x_R,y_R)$ together with the single bit

$${\beta }_R=\{\begin{array}{ll}0& \text{if }0\le y_R<\frac{1}{2}p,\\ 1& \text{if }\frac{1}{2}p<y_R<p.\end{array}$$

You may assume that Alice is able to efficiently compute square roots modulo $p$. This is certainly true, for example, if $p\equiv 3(\mathrm{mod}4)$; see Proposition 2.26.

(b) Alice and Bob decide to use the prime $p=1123$ and the elliptic curve

$$E:Y^2=X^3+54X+87.$$

Bob sends Alice the $x$-coordinate $x=278$ and the bit $\beta =0$. What point is Bob trying to convey to Alice? What about if instead Bob had sent $\beta =1$?

6.17

The Menezes-Vanstone variant of the elliptic Elgamal public key cryptosystem improves message expansion while avoiding the difficulty of directly attaching plaintexts to points in $E({\mathbb{F}}_p)$. The MV-Elgamal cryptosystem is described in Table 6.13 on page 365.

(a) The last line of Table 6.13 claims that $m_1^{\prime }=m_1$ and $m_2^{\prime }=m_2$. Prove that this is true, so the decryption process does work.

(b) What is the message expansion of MV-Elgamal?

(c) Alice and Bob agree to use

$$p=1201,E:Y^2=X^3+19X+17,P=(278,285)\in E({\mathbb{F}}_p),$$

for MV-Elgamal. Alice’s secret value is $n_A=595$. What is her public key? Bob sends Alice the encrypted message $((1147,640),279,1189)$. What is the plaintext?

6.18

This exercise continues the discussion of the MV-Elgamal cryptosystem described in Table 6.13 on page 365.

(a) Eve knows the elliptic curve $E$ and the ciphertext values $c_1$ and $c_2$. Show how Eve can use this knowledge to write down a polynomial equation modulo $p$ that relates the two pieces $m_1$ and $m_2$ of the plaintext. In particular, if Eve can figure out one piece of the plaintext, then she can recover the other piece by finding the roots of a certain polynomial modulo $p$.

(b) Alice and Bob exchange a message using MV-Elgamal with the prime, elliptic curve, and point in Exercise 6.17(c). Eve intercepts the ciphertext

$$((269,339),814,1050),$$

and through other sources she discovers that the first part of the plaintext is $m_1=1050$. Use your algorithm in (a) to recover the second part of the plaintext.

6.19

Section 6.4.3 describes ECDSA, an elliptic analogue of DSA. Formulate an elliptic analogue of the simpler Elgamal digital signature algorithm described in Table 4.2 in Sect. 4.3.

6.20

This exercise asks you to compute some numerical instances of the elliptic curve digital signature algorithm described in Table 6.7 for the public parameters

$$E:y^2=x^3+231x+473,p=17389,q=1321,G=(11259,11278)\in E({\mathbb{F}}_p).$$

You should begin by verifying that $G$ is a point of order $q$ in $E({\mathbb{F}}_p)$.

(a) Samantha’s private signing key is $s=542$. What is her public verification key? What is her digital signature on the document $d=644$ using the random element $e=847$?

(b) Tabitha’s public verification key is $V=(11017,14637)$. Is $(s_1,s_2)=(907,296)$ a valid signature on the document $d=993$?

(c) Umberto’s public verification key is $V=(14594,308)$. Use any method that you want to find Umberto’s private signing key, and then use the private key to forge his signature on the document $d=516$ using the random element $e=365$.

MV-Elgamal summary from Table 6.13:

Public parameters: prime p, elliptic curve E over F_p, point P in E(F_p).
Alice chooses secret n_A, computes Q_A = n_A P, and publishes Q_A.
Bob encrypts plaintext values m_1,m_2 modulo p:
  choose random k,
  R = kP,
  S = kQ_A = (x_S,y_S),
  c_1 = x_S m_1 mod p,
  c_2 = y_S m_2 mod p,
  ciphertext = (R,c_1,c_2).
Alice decrypts:
  T = n_A R = (x_T,y_T),
  m'_1 = x_T^{-1} c_1 mod p,
  m'_2 = y_T^{-1} c_2 mod p.

Section 6.6. Lenstra’s Elliptic Curve Factorization Algorithm

6.21

Use the elliptic curve factorization algorithm to factor each of the numbers $N$ using the given elliptic curve $E$ and point $P$.

(a) $N=589$, $E:Y^2=X^3+4X+9$, $P=(2,5)$.

(b) $N=26167$, $E:Y^2=X^3+4X+128$, $P=(2,12)$.

(c) $N=1386493$, $E:Y^2=X^3+3X-3$, $P=(1,1)$.

(d) $N=28102844557$, $E:Y^2=X^3+18X-453$, $P=(7,4)$.

Section 6.7. Elliptic Curves over ${\mathbb{F}}_2$ and over ${\mathbb{F}}_{2^k}$

6.22

Let $E$ be an elliptic curve given by a generalized Weierstrass equation

$$E:Y^2+a_{1}XY+a_{3}Y=X^3+a_2{X}^2+a_{4}X+a_6.$$

Let $P_1=(x_1,y_1)$ and $P_2=(x_2,y_2)$ 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=O$.

Otherwise define quantities $\lambda$ and $\nu$ as follows:

$$\begin{array}{lll}\text{If }{x}_1\ne x_2:& \lambda =\frac{y_2-y_1}{x_2-x_1},& \nu =\frac{y_1{x}_2-y_2{x}_1}{x_2-x_1},\\ \text{If }{x}_1=x_2:& \lambda =\frac{3x_1^2+2a_2{x}_1+a_4-a_1{y}_1}{2y_1+a_1{x}_1+a_3},& \nu =\frac{-x_1^3+a_4{x}_1+2a_6-a_3{y}_1}{2y_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,-(\lambda +a_1)x_3-\nu -a_3\right).$$

6.23

Let ${\mathbb{F}}_8={\mathbb{F}}_2[T]/(T^3+T+1)$ be as in Example 6.28, and let $E$ be the elliptic curve

$$E:Y^2+XY+Y=X^3+TX+(T+1).$$

(a) Calculate the discriminant of $E$.

(b) Verify that the points

$$P=(1+T+T^2,1+T),Q=(T^2,T),R=(1+T+T^2,1+T^2),$$

are in $E({\mathbb{F}}_8)$ and compute the values of $P+Q$ and $2R$.

(c) Find all of the points in $E({\mathbb{F}}_8)$.

(d) Find a point $P\in E({\mathbb{F}}_8)$ such that every point in $E({\mathbb{F}}_8)$ is a multiple of $P$.

6.24

Let $\tau (\alpha )={\alpha }^p$ be the Frobenius map on ${\mathbb{F}}_{p^k}$.

(a) Prove that

$$\tau (\alpha +\beta )=\tau (\alpha )+\tau (\beta )\text{and}\tau (\alpha \cdot \beta )=\tau (\alpha )\cdot \tau (\beta )\text{for all }\alpha ,\beta \in {\mathbb{F}}_{p^k}.$$

Hint: For the addition formula, use the binomial theorem (Theorem 5.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)=(x^p,y^p)$ be the Frobenius map from $E({\mathbb{F}}_{p^k})$ to itself. Prove that

$$\tau (P+Q)=\tau (P)+\tau (Q)\text{for all }P,Q\in E({\mathbb{F}}_{p^k}).$$

6.25

Let $E_0$ be the Koblitz curve $Y^2+XY=X^3+1$ over the field ${\mathbb{F}}_2$, and for every $k\ge 1$, let

$$t_k=2^k+1-\#E({\mathbb{F}}_{2^k}).$$

(a) Prove that $t_1=-1$ and $t_2=-3$.

(b) Prove that $t_k$ satisfies the recursion

$$t_k=t_1{t}_{k-1}-2t_{k-2}\text{for all }k\ge 3.$$

You may use the formula (6.12) that we stated, but did not prove, on page 334.

(c) Use the recursion in (b) to compute $\#E({\mathbb{F}}_{16})$.

(d) Program a computer to calculate the recursion and use it to compute the values of $\#E({\mathbb{F}}_{2^{11}})$, $\#E({\mathbb{F}}_{2^{31}})$, and $\#E({\mathbb{F}}_{2^{101}})$.

6.26

Let $E$ be an elliptic curve over ${\mathbb{F}}_p$, and for $k\ge 1$, let

$$t_k=p^k+1-\#E({\mathbb{F}}_{p^k}).$$

(a) Prove that

$$t_k=t_1{t}_{k-1}-p{t}_{k-2}\text{for all }k\ge 2,$$

where by convention we set $t_0=2$.

(b) Use (a) to express $t_2$, $t_3$, and $t_4$ in terms of $p$ and $t_1$.

Hint: Use Theorem 6.29(a). This generalizes Exercise 6.25.

6.27

Let $\tau$ satisfy ${\tau }^2=-2-\tau$. Prove that the following algorithm gives coefficients $v_i\in \{-1,0,1\}$ such that the positive integer $n$ is equal to

$$n=v_0+v_1\tau +v_2{\tau }^2+\cdots +v_{\ell }{\tau }^{\ell }.\text{\hspace{1em}(6.19)}$$

Further prove that $\ell \le 2\lfloor \log (n)\rfloor +1$.

[1]  Set n0 = n and n1 = 0 and i = 0.
[2]  Loop while n0 != 0 or n1 != 0.
[3]      If n0 is odd:
[4]          Set v_i = 2 - (n0 - 2n1) mod 4.
[5]          Set n0 = n0 - v_i.
[6]      Else:
[7]          Set v_i = 0.
[8]      End If.
[9]      Set i = i + 1.
[10]     Set (n0,n1) = (n1 - n0/2, -n0/2).
[11] End Loop.

6.28

Implement the algorithm in Exercise 6.27 and use it to compute the $\tau$-expansion (6.19) of the following integers. What is the highest power of $\tau$ that appears and how many nonzero terms are there?

(a) $n=931$.

(b) $n=32755$.

(c) $n=82793729188$.

Section 6.8. Bilinear Pairings on Elliptic Curves

6.29

Let $R(x)$ and $S(x)$ be rational functions. Prove that the divisor of a product is the sum of the divisors, i.e.,

$$\mathrm{div}(R(x)S(x))=\mathrm{div}(R(x))+\mathrm{div}(S(x)).$$

6.30

This exercise sketches a proof that if $P=(\alpha ,0)\in E$, then $\mathrm{div}(X-\alpha )=2[P]-2[O]$.

(a) Prove that

$$\mathrm{div}(X-\alpha )=m[P]-m[O]$$

for some integer $m\ge 1$.

(b) Prove that the Weierstrass equation of $E$ can be written in the form

$$E:Y^2=(X-\alpha )(X^2+aX+b),$$

and that the polynomials $X-\alpha$ and $X^2+aX+b$ have no common roots.

(c) Prove that

$$\mathrm{div}(X-\alpha )=2n[P]-2n[O]$$

for some integer $n\ge 1$. Hint: Take the divisor of both sides of $Y^2=(X-\alpha )(X^2+aX+b)$ and use (b).

(d) Prove that

$$\mathrm{div}(X-\alpha )=2[P]-2[O].$$

Warning: This part requires some knowledge of discrete valuation rings that is not developed in this book.

6.31

Prove that the Weil pairing satisfies

$$e_m(P,Q)=e_m(Q,P{)}^{-1}\text{for all }P,Q\in E[m].$$

Hint: Use the fact that $e_m(P+Q,P+Q)=1$ and expand using bilinearity.

6.32

This exercise asks you to verify that the Weil pairing $e_m$ is well-defined.

(a) Prove that the value of $e_m(P,Q)$ is independent of the choice of rational functions $f_P$ and $f_Q$.

(b) Prove that the value of $e_m(P,Q)$ is independent of the auxiliary point $S$. Hint: Fix the points $P$ and $Q$ and consider the quantity

$$F(S)=\frac{f_P(Q+S)}{f_P(S)}\frac{f_Q(P-S)}{f_Q(-S)}$$

as a function of $S$. Compute the divisor of $F$ and use the fact that every nonconstant function on $E$ has at least one zero.

You might also try to prove that the Weil pairing is bilinear, but do not be discouraged if you do not succeed, since the standard proofs use more tools than we have developed in the text.

6.33

Choose a basis $\{P_1,P_2\}$ for $E[m]$ and write each $P\in E[m]$ as a linear combination $P=a_P{P}_1+b_P{P}_2$. Use the basic properties of the Weil pairing described in Theorem 6.38 to prove that

$$e_m(P,Q)=e_m(P_1,P_2{)}^{\det \left(\begin{array}{cc}{a}_P& a_Q\\ b_P& b_Q\end{array}\right)}=e_m(P_1,P_2{)}^{a_P{b}_Q-a_Q{b}_P}.$$

6.34

Complete the proof of Proposition 6.52 by proving that $\varphi (2P)=2\varphi (P)$.

6.35

For each of the following elliptic curves $E$, finite fields ${\mathbb{F}}_p$, points $P$ and $Q$ of order $m$, and auxiliary points $S$, use Miller’s algorithm to compute the Weil pairing $e_m(P,Q)$. See Example 6.43.

	$E$	$p$	$P$	$Q$	$m$	$S$
(a)	$y^2=x^3+23$	1051	$(109,203)$	$(240,203)$	5	$(1,554)$
(b)	$y^2=x^3-35x-9$	883	$(5,66)$	$(103,602)$	7	$(1,197)$
(c)	$y^2=x^3+37x$	1009	$(8,703)$	$(49,20)$	7	$(0,0)$
(d)	$y^2=x^3+37x$	1009	$(417,952)$	$(561,153)$	7	$(0,0)$

Notice that (c) and (d) use the same elliptic curve. Letting $P^{\prime }$ and $Q^{\prime }$ denote the points in (d), verify that

$$P^{\prime }=2P,Q^{\prime }=3Q,e_7(P^{\prime },Q^{\prime })=e_7(P,Q{)}^6.$$

6.36

Let $E$ over ${\mathbb{F}}_q$ and $\ell$ be as described in Theorem 6.44. Prove that the modified Tate pairing is symmetric, in the sense that

$$\hat{\tau }(P,Q)=\hat{\tau }(Q,P)\text{for all }P,Q\in E({\mathbb{F}}_q)[\ell ].$$

6.37

Let $E$ be an elliptic curve over ${\mathbb{F}}_q$ and let $P,Q\in E({\mathbb{F}}_q)[\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 consistently. Thus the Weil pairing requires approximately twice as much work to compute as does the Tate pairing.

Section 6.9. The Weil Pairing over Fields of Prime Power Order

6.38

Prove Proposition 6.52(b) in the case $P_1=P_2$.

6.39

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

6.40

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$, $aP$, $bP$, $cP\in E({\mathbb{F}}_q)[\ell ]$. The elliptic decision Diffie-Hellman problem is to determine whether $cP$ is equal to $abP$. Of course, if we could solve the Diffie-Hellman problem itself, then we could compute $abP$ and compare it with $cP$, but the Diffie-Hellman problem is often difficult to solve.

Suppose that there exists a distortion map $\varphi$ for $E[\ell ]$. Show how to use the modified Weil pairing to solve the elliptic decision Diffie-Hellman problem without actually having to compute $abP$.

6.41

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

6.42

Let $p\equiv 3(\mathrm{mod}4)$, let $E:y^2=x^3+x$, let $P\in E({\mathbb{F}}_p)[\ell ]$, and let $\varphi (x,y)=(-x,\alpha y)$ be the $\ell$-distortion map for $P$ described in Proposition 6.53. Suppose further that $\ell \equiv 3(\mathrm{mod}4)$. Prove that $\varphi$ is an $\ell$-distortion map for every point in $E[\ell ]$. In other words, if $Q\in E$ is any point of order $\ell$, prove that $e_{\ell }(Q,\varphi (Q))$ is a primitive $\ell$th root of unity.

6.43

Let $E$ be the elliptic curve

$$E:y^2=x^3+1$$

over a field $K$, and suppose that $K$ contains an element $\beta \ne 1$ satisfying ${\beta }^3=1$. We say that $\beta$ is a primitive cube root of unity. Define a map $\varphi$ by

$$\varphi (x,y)=(\beta x,y)\text{and}\varphi (O)=O.$$

(a) Let $P\in E(K)$. Prove that $\varphi (P)\in E(K)$.

(b) Prove that $\varphi$ respects the addition law on $E$, i.e., $\varphi (P_1+P_2)=\varphi (P_1)+\varphi (P_2)$ for all $P_1,P_2\in E(K)$.

6.44

Let $E:y^2=x^3+1$ be the elliptic curve in Exercise 6.43.

(a) Let $p\ge 3$ be a prime with $p\equiv 2(\mathrm{mod}3)$. Prove that ${\mathbb{F}}_p$ does not contain a primitive cube root of unity, but that ${\mathbb{F}}_{p^2}$ does contain a primitive cube root of unity.

(b) Let $\beta \in {\mathbb{F}}_{p^2}$ be a primitive cube root of unity and define a map $\varphi (x,y)=(\beta x,y)$ as in Exercise 6.43. Suppose that $E({\mathbb{F}}_p)$ contains a point $P$ of prime order $\ell \ge 5$. Prove that $\varphi$ is an $\ell$-distortion map for $P$.

6.45

Let $E$ be the elliptic curve $E:y^2=x^3+x$ over the field ${\mathbb{F}}_{691}$. The point $P=(301,14)\in E({\mathbb{F}}_{691})$ has order $173$. Use the distortion map on $E$ from Exercise 6.42 to compute ${\hat{e}}_{173}(P,P)$ (cf. Example 6.55). Verify that the value is a primitive $173$rd root of unity.

6.46

Continuing with the curve $E$, prime $p=691$, and point $P=(301,14)$ from Exercise 6.45, let

$$Q=(143,27)\in E({\mathbb{F}}_{691}).$$

Use the MOV method to solve the ECDLP for $P$ and $Q$, i.e., compute ${\hat{e}}_{173}(P,Q)$ and express it as the $n$th power of ${\hat{e}}_{173}(P,P)$. Check your answer by verifying that $nP$ is equal to $Q$.

Section 6.10. Applications of the Weil Pairing

6.47

Alice, Bob, and Carl use tripartite Diffie-Hellman with the curve

$$E:y^2=x^3+x\text{over the field }{\mathbb{F}}_{1723}.$$

They use the point

$$P=(668,995)\text{of order }431.$$

(a) Alice chooses the secret value $n_A=278$. What is Alice’s public point $Q_A$?

(b) Bob’s public point is $Q_B=(1275,1550)$ and Carl’s public point is $Q_C=(897,1323)$. What is the value of ${\hat{e}}_{431}(Q_B,Q_C)$?

(c) What is their shared value?

(d) Bob’s secret value is $n_B=224$. Verify that ${\hat{e}}_{431}(Q_A,Q_C{)}^{n_B}$ is the same as the value that you got in (c).

(e) Figure out Carl’s secret value $n_C$. Since $P$ has order 431, you can do this on a computer by trying all possible values.

6.48

Show that Eve can break tripartite Diffie-Hellman key exchange as described in Table 6.10.1 if she knows how to solve the Diffie-Hellman problem (page 69) for the field ${\mathbb{F}}_q$.

6.49

In this exercise we consider what is required to break the identity-based encryption scheme described in Table 6.12 on page 360.

(a) Show that if Eve can solve the discrete logarithm problem in either $E({\mathbb{F}}_q)$ or in ${\mathbb{F}}_q^{\ast }$, then she can recover Tom’s secret key $s$, which means that she can do anything that Tom can do, including decrypting everyone’s ciphertexts.

(b) Suppose that Eve only knows how to solve the elliptic curve Diffie-Hellman problem in $E({\mathbb{F}}_q)$, as described on page 318. Show that she can decrypt all ciphertexts.

(c) What if Eve only knows how to solve the Diffie-Hellman problem in ${\mathbb{F}}_q^{\ast }$? Can she still decrypt all ciphertexts?