Intro To Cryptography - Chapter 6

Problem 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$.

Solution:

$$\begin{align*}Y^2 &= (4)^2 = 16 = (-1)^3 + 17 &= X^3 + 17 \\ Y^2 &= (5)^2 = 25 = (2)^3 + 17 &= X^3 + 17 \end{align*}$$

(a) Compute the points $P \oplus Q$ and $P \ominus Q$.

Solution: Using Theorem 6.6:

$$\begin{align*} P\oplus Q :\qquad\qquad & \\ \lambda &= \frac{y_2 - y_1}{x_2 - x_2} = \frac{5-4}{2-(-1)} = \frac{1}{3} \\ x_3 &= \lambda^2 - x_1 - x_2 = \left(\frac{1}{3}\right)^2 - (-1) - 2 = \frac{-8}{9} \\ y_3 &= \lambda(x_1 - x_3) - y_1 = \frac{1}{3}\left(-1 - \left(\frac{-8}{9}\right)\right) - 4 = \frac{-109}{27} \\ \implies P \oplus Q &= \left(\frac{-8}{9}, \frac{-109}{27}\right)\end{align*}$$

To calculate $P \ominus Q$ we use the same algorithm for $\oplus$, but with $\ominus Q = (2, -5)$:

$$\begin{align*} P\ominus Q :\qquad\qquad & \\ \lambda &= \frac{y_2 - y_1}{x_2 - x_2} = \frac{-5-4}{2-(-1)} = \frac{-9}{3} = -3 \\ x_3 &= \lambda^2 - x_1 - x_2 = (-3)^2 - (-1) - 2 = 8 \\ y_3 &= \lambda(x_1 - x_3) - y_1 = -3\left(-1 - 8\right) - 4 = 23 \\ \implies P \ominus Q &= \left( 8, 23 \right)\end{align*}$$

(b) Compute the points $2P$ and $2Q$.

Solution:

$$\begin{align*} 2P :\qquad\qquad & \\ \lambda &= \frac{3x_1^2 + A}{2y_1} = \frac{3(-1)^{2} + 0}{2(4)} = \frac{3}{8} \\ x_3 &= \lambda^2 - x_1 - x_2 = \left(\frac{3}{8}\right)^2 - (-1) - (-1) = \frac{137}{64} \\ y_3 &= \lambda(x_1 - x_3) - y_1 = \frac{3}{8}\left(-1 - \frac{137}{64}\right) - 4 = \frac{-2651}{512} \\ \implies 2P &= \left( \frac{137}{64}, \frac{-2651}{512} \right)\end{align*}$$

$$\begin{align*} 2Q :\qquad\qquad & \\ \lambda &= \frac{3x_1^2 + A}{2y_1} = \frac{3(2)^{2} + 0}{2(5)} = \frac{6}{5} \\ x_3 &= \lambda^2 - x_1 - x_2 = \left(\frac{6}{5}\right)^2 - 2 - 2 = \frac{-64}{25} \\ y_3 &= \lambda(x_1 - x_3) - y_1 = \frac{6}{5}\left(2 - \frac{-64}{25}\right) - 5 = \frac{59}{125} \\ \implies 2Q &= \left( \frac{-64}{25}, \frac{59}{125} \right)\end{align*}$$

(bonus) How many points with integer coordinates can you find on $E$?

Solution: Well, via enumeration we can find some smaller ones:

$$\{ (-2, \pm 3), (-1, \pm 4), (2, \pm 5), (4, \pm 9), (8, \pm 23) \}$$

It's clear from the equation for $E$ that there are no more negative values of $X$ that lie on $E$. For finding more in the positive direction, I couldn't find a good analytic solution, so instead I brute forced it (see fn problem6_2 in the appendix) and found three additional points:

$$\{ (43, \pm 282), (52, \pm 375), (5234, \pm 378661) \}$$

Problem 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$.

Solution: First writing out the list of squares in $\mathbb{F}_7$

$$\{ x^2 : x \in \mathbb{F}_7 \} = \{ 0, 1,4,2,2,4,1 \} = \{ 0,1,2,4 \}$$

we plug in all possible values into the RHS and keep those which match the squares, in addition to the special point at $\mathcal{O}$:

$$\{ \mathcal{O}, (0, 3), (0, 4), (2, 3), (2, 4), (4, 1), (4, 6), (5, 3), (5, 4) \}$$

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

Solution: Using the same approach,

$$\{ x^2 : x \in \mathbb{F}_{11} \} = \{ 0,1,4,9,5,3,3,5,9,4,1 \} = \{ 0,1,3,4,5,9 \}$$

Plugging in all possible values for $X$, there's only two values $6, 10$, that lead to perfect squares. So all the points on $E(\mathbb{F}_{11})$ are:

$$\{ \mathcal{O}, (6, 2), (6, 9), (7, 1), (7, 10), (10, 2), (10, 9) \}$$

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

Solution: Using the same strategy and the table of squares from part (b), we find the points on $E$ are

$$\{ \mathcal{O}, (0, 4), (0, 7), (3, 0), (6, 5), (6, 6), (9, 0), (10, 0) \}$$

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 for $P$ and $Q$. That is, find a positive integer $n$ such that $Q = nP$.

Solution: Let's just enumerate $nP$:

$2P = P \oplus P$:

$$\begin{align*}\lambda &= \frac{3x_1^2 + A}{2y_1}= \frac{3(4)^2 + 1}{4} = \frac{4}{4} = 1 \\ x_3 &= \lambda^2 - x_1 - x_2 = 1^2 -4 -4 = -7 = 3 \\ y_3 &= \lambda(x_1 - x_3) - y_1 = (4- 3) - 2 = -1 = 4 \\ \implies 2P &= (3, 4) \end{align*}$$

$3P = 2P \oplus P$:

$$\begin{align*}\lambda &= \frac{y_2 - y_1}{x_2 - x_1} = \frac{2-4}{4-3} = -2 = 3 \\ x_3 &= \lambda^2 - x_1 - x_2 = 3^2 -3 -4 = 2 \\ y_3 &= \lambda(x_1 - x_3) - y_1 = 3(3-2) - 4 = -1 = 4 \\ \implies 3P &= (2, 4) \end{align*}$$

$4P = 3P \oplus P$:

$$\begin{align*}\lambda &= \frac{y_2 - y_1}{x_2 - x_1} = \frac{2-4}{4-2} = -1 = 4 \\ x_3 &= \lambda^2 - x_1 - x_2 = 4^2 -2 -4 = 0 \\ y_3 &= \lambda(x_1 - x_3) - y_1 = 4(2-0) - 4 = 4 \\ \implies 4P &= (0, 4) \end{align*}$$

Note that we have now found $4P = \ominus Q$, however we do not know the size of $E(\mathbb{F}_5)$ nor the order of $P$, so we can't easily use this information to find $n$. So let's continue:

$5P = 4P \oplus P$:

$$\begin{align*}\lambda &= \frac{y_2 - y_1}{x_2 - x_1} = \frac{2-4}{4-0} = 3\cdot4 = 12 = 2 \\ x_3 &= \lambda^2 - x_1 - x_2 = 2^2 -0 -4 = 0 \\ y_3 &= \lambda(x_1 - x_3) - y_1 = 2(0-0) - 4 = 1 \\ \implies 5P &= (0, 1) \end{align*}$$

Therefore $\log_P(Q) = 5$.

Problem 6.14

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 + 171X + 853, \quad 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?

Solution: Using the program in the appendix, I found

$$n_B P = (1432, 667).$$

(b) What is their secret shared value?

Solution: The shared value is

$$n_B Q_A = (2424, 911).$$

(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$.

Solution: Since p is only $2671$, the size of $E(\mathbb{F}_q)$ is not too large, so we can just exhaustively loop until we find a value of $n$ that works. Doing so yields $n_A = 726$.

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

Solution: Bob should send the number $161$ to Alice. Their secret shared value is $1708$.

Problem 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, 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{cases} 0 & \text{ if } 0 \le y_R < \frac{1}{2}p, \\ 1 & \text{ if } \frac{1}{2}p < y_R < p. \end{cases}$$

(You may assume Alice is able to efficiently compute square roots modulo $p$.)

Solution: The tuple $(x_R, \beta_R)$ is enough to identify the point $(x_R, y_R)$ on $E$ because there are only two points that share the same $x$-coordinate: $(x_R, y_R)$ and $(x_R,-y_R )$. Furthermore, in $\mathbb{F}_p$ we have

$$0 \le y < \frac{1}{2}p \quad \iff \quad \frac{1}{2}p < -y < p,$$

that is, we can say that those values less than $\frac{1}{2}p$ are the "positive" numbers and the ones greater than $\frac{1}{2}p$ are the "negative" numbers. This way, we only need one bit of information which informs which one of the two possible $y$ values (i.e. the positive or negative one) we want to convey. (Small note that we're assuming $p$ is some large prime, so it is odd, and we don't have to worry about equality on the $\frac{1}{2}p$ boundary.)

Thus, Alice simply needs to plug the $x_R$ value into the equation for $E$ and she can find the value $s = y_R^2$. After this she computes the square root (if $p\equiv 3\mod4$ then she can just compute $s^{(p+1)/4}\mod p$) to find $\pm y_R$. She then chooses the $y$ that satisfies the $\beta_R$ condition.

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

Solution: When $\beta = 0$, Bob is trying to convey the point $(278, 487)$. When $\beta = 1$, the point conveyed is $(278, 636)$.

Appendix

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum Point {
    Coord(u64, u64),
    Zero,
}

pub struct Curve {
    pub p: u64,
    pub a: u64,
    pub b: u64,
    pub pk: Point,
}

impl Curve {
    /// Make an n multiple of a point, using the doulbe-and-add algorithm
    fn multiple(&self, n: u64, pt: Point) -> Point {
        let mut n = n;
        let mut q = pt;
        let mut r = Point::Zero;
        while n > 0 {
            if n % 2 == 1 {
                r = self.add(r, q);
            }
            q = self.add(q, q);
            n /= 2;
        }
        r
    }

    /// Add two points together
    fn add(&self, p1: Point, p2: Point) -> Point {
        match (p1, p2) {
            (Point::Zero, _) => p2,
            (_, Point::Zero) => p1,
            (Point::Coord(x1, y1), Point::Coord(x2, y2)) if x1 == x2 && y1 == self.neg(y2) => {
                Point::Zero
            }
            (Point::Coord(x1, y1), Point::Coord(x2, y2)) => {
                let lambda = if p1 != p2 {
                    (y2 + self.neg(y1)) * self.inv(x2 + self.neg(x1))
                } else {
                    (3 * (x1 * x1) + self.a) * self.inv(2 * y1)
                } % self.p;

                let x3 = ((lambda * lambda) + self.neg(x1) + self.neg(x2)) % self.p;
                let y3 = (lambda * (x1 + self.neg(x3)) + self.neg(y1)) % self.p;

                Point::Coord(x3, y3)
            }
        }
    }

    /// Return the "positive" y coordinate of E at the given x.
    fn eval_at(&self, x: u64) -> u64 {
        let y_sq = (x * x * x) + self.a * x + self.b % self.p;
        assert_eq!(
            self.p % 4,
            3,
            "this method does not work unless p = 3 mod 4"
        );
        mod_pow(y_sq, (self.p + 1) / 4, self.p)
    }

    /// Get additive inverse mod p.
    fn neg(&self, x: u64) -> u64 {
        (self.p - x) % self.p
    }

    /// Get multiplicative inverse mod p.
    fn inv(&self, x: u64) -> u64 {
        crate::fast_inv(x, self.p)
    }
}

fn mod_pow(base: u64, exp: u64, modulus: u64) -> u64 {
    let mut out = 1;
    for _ in 0..exp {
        out = out * base % modulus
    }
    out
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn example_6_16() {
        let curve = Curve {
            p: 3623,
            a: 14,
            b: 19,
            pk: Point::Coord(6, 730),
        };
        let n = 947;

        assert_eq!(curve.multiple(n, curve.pk), Point::Coord(3492, 60))
    }

    #[test]
    fn problem6_14_a() {
        let curve = Curve {
            p: 2671,
            a: 171,
            b: 853,
            pk: Point::Coord(1980, 431),
        };
        let n = 1943;

        assert_eq!(curve.multiple(n, curve.pk), Point::Coord(1432, 667))
    }

    #[test]
    fn problem6_14_b() {
        let curve = Curve {
            p: 2671,
            a: 171,
            b: 853,
            pk: Point::Coord(1980, 431),
        };
        let n = 1943;
        let q = Point::Coord(2110, 543);

        assert_eq!(curve.multiple(n, q), Point::Coord(2424, 911))
    }

    #[test]
    fn problem6_14_c() {
        let curve = Curve {
            p: 2671,
            a: 171,
            b: 853,
            pk: Point::Coord(1980, 431),
        };
        let q = Point::Coord(2110, 543);

        let n = (1..).find(|&n| curve.multiple(n, curve.pk) == q).unwrap();
        assert_eq!(n, 726);
    }

    #[test]
    fn problem6_14_d() {
        let curve = Curve {
            p: 2671,
            a: 171,
            b: 853,
            pk: Point::Coord(1980, 431),
        };

        let n = 875;
        let qb = curve.multiple(n, curve.pk);
        assert_eq!(qb, Point::Coord(161, 2040));

        let qx = 2;
        let qy = curve.eval_at(qx);
        let q = Point::Coord(qx, qy);
        let secret = curve.multiple(n, q);
        assert_eq!(secret, Point::Coord(1708, 1419));
    }

    #[test]
    fn problem6_16_b() {
        let curve = Curve {
            p: 1123,
            a: 54,
            b: 87,
            pk: Point::Zero,
        };

        let y_pos = curve.eval_at(278);
        assert_eq!(y_pos, 487);

        let y_neg = curve.p - y_pos;
        assert_eq!(y_neg, 636);
    }

    #[test]
    fn problem6_2() {
        let e = |x: u64| x.checked_pow(3).and_then(|x3| x3.checked_add(17));
        let mut sols = vec![];

        // For x > 0, y is increasing as a function of x, so once we find the
        // smallest x such that e(x) >= y^2, we can start the search for (y+1)^2
        // at e(x).
        let mut x: u64 = 0;
        // Ran with u64::MAX first, then replaced with the max y value found.
        for y in 1..=378661u64 {
            let ys = match y.checked_mul(y) {
                Some(ys) => ys,
                None => break,
            };
            while matches!(e(x), Some(e) if e < ys) {
                x += 1;
            }
            match e(x) {
                Some(e) if e == ys => {
                    sols.push((x, y));
                }
                None => break,
                _ => continue,
            }
        }
        assert_eq!(
            sols,
            vec![
                (2, 5),
                (4, 9),
                (8, 23),
                (43, 282),
                (52, 375),
                (5234, 378661)
            ]
        );
    }
}