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)
]
);
}
}