Intro To Cryptography - Chapter 2

Problem 2.3

Let $g$ be a primitive root for $\mathbb{F}_p$.

(a) Suppose that $x = a$ and $x =b$ are both integer solutions to the congruence $g^x \equiv h \mod p$. Prove that $a \equiv b \mod p-1$. Explain why this means that the map (2.1) on page 65 is well-defined.

Proof: Let $a-b = (p-1)\cdot q + r$ such that $0 \le r < p - 1$. If we can show that $r = 0$, then by definition we can conclude $a \equiv b \mod p-1$. Notice that

$$h \equiv g^a = g^{b + (p-1)\cdot q + r} = g^b \cdot (g^{p-1})^q \cdot g^r \equiv h \cdot g^r \mod p.$$

To be pedantic, we know $h$ has an inverse $h^{p-2}$, so we can multiply both sides of this equivalence by the inverse to find that $1 \equiv g^r \mod p$. But recall $0 \le r < p-1$; because $g$ is a generator, it must be the case that $r = 0$, completing the proof.

Lastly, by definition $\log_g$ is a well-defined function if it maps deterministically; that is, $h = j \implies \log_g(h) = \log_g(j)$ for all $h, j \in \mathbb{F}_p^{\ast}$. Recall that $g$ is a generator, so we can write $h = g^a$ and $j = g^b$ for some $a, b \in \mathbb{Z}$. Equivalently, $g^a = g^b$ in $\mathbb{F}_q^{\ast}$. From the statement proved above, we know that this implies $a = b$ in $\mathbb{Z}/(p-1)\mathbb{Z}$. Therefore $\log_g(h) = \log_g(j)$ and $\log_g$ is well-defined.

(b) Prove that $\log_g(h_1h_2) = \log_g(h_1) + \log_g(h_2)$ for all $h_1, h_2 \in \mathbb{F}_p^\ast$.

Proof: Let $a, b \in \mathbb{Z}/(p-1)\mathbb{Z}$ such that $g^a = h_1$ and $g^b = h_2$. Then

$$\log_g(h_1h_2) = \log_g(g^ag^b) = \log_g(g^{a+b}) = a + b = \log_g(h_1) + \log_g(h_2).$$

(c) Prove that $\log_g(h^n) = n \log_g(h)$ for all $h \in \mathbb{F}_p^\ast$ and all $n \in \mathbb{Z}$.

Proof: First we'll handle $n \ge 0$ by induction. For the base case, clearly

$$\log_g(h^0) = \log_g(1) = 0 = 0 \cdot \log_g(h).$$

Next suppose for some $k >= 0$, $\log_g(h^k) = k\log_g(h)$. By part (b) we have

$$\log_g(h^{k+1}) = \log_g(h^kh) = \log_g(h^k) + \log_g(h)$$

and by the inductive hypothesis,

$$\log_g(h^{k+1}) = k\log_g(h) + \log_g(h) = (k+1)\log_g(h).$$

We conclude by induction that the statement holds for all $n \ge 0$. For negative numbers, let's do induction in reverse. First, let's consider the base case of a negative exponent:

$$h^{-1} = h^{-1}\cdot 1 = h^{-1}\cdot h^{p-1} = h^{p-2}$$

in $\mathbb{F}_p^\ast$, a fact which we've previously seen in the fast powering algorithm. Since we've already proved this for nonnegative integers, and $p - 2 \ge 0$, we have

$$\begin{align*} \log_g(h^{-1}) &= \log_g(h^{p-2}) = (p-2)\log_g(h) \\ &= (p-1)\log_g(h) - \log_g(h) \\ &= -1 \cdot \log_g(h). \end{align*}$$

Suppose our statement holds for some $k \le -1$. Then

$$\log_g(h^{k-1}) = \log_g(h^kh^{-1}) = \log_g(h^k) + \log_g(h^{-1})$$

and by the inductive hypothesis and base case, we know

$$\log_g(h^k) + \log_g(h^{-1}) = k\log_g(h) - \log_g(h) = (k-1)\log_g(h).$$

By induction, we conclude the statement holds for all negative integers $n$. We have thus tediously and pedantically completed the proof.

Problem 2.6

Alice and Bob agree to use the prime $p = 1373$ and the base $g = 2$ for a Diffie-Hellman key exchange. Alice sends Bob the value $A = 974$. Bob asks your assistance, so you tell him to use the secret exponent $b = 871$. What value $B$ should Bob send to Alice, and what is their secret shared value? Can you figure out Alice's secret exponent?

Solution: Bob should send

$$B = g^b \mod p = 2^{871} \mod 1373 = 805$$

Their secret shared value is

$$S = A^b \mod p = 974^{871} \mod 1373 = 397.$$

Since there are at most 1372 values to search for $p = 1373$, it is quite easy to find $a = 587$:

const A: u32 = 974;
const P: u32 = 1373;
let e = (1..P).find(|&e| mod_pow(2, e, P) == A);
assert_eq!(e, Some(587));

Problem 2.9

Suppose that Eve is able to solve the Diffie-Hellman; that is, given $g^u, g^v \mod p$, then she is able to compute $g^{uv} \mod p$. Show that Eve can break the Elgamal PKC.

Proof: Suppose Alice and Bob are communicating via Elgamal with parameters $g, p$, where Alice has chosen private key $a$ and public key $A$. Suppose further that Bob has used random element $k$ in his encryption of ciphertext $(c_1, c_2)$. We need to show that Eve can recover the underlying plaintext $m$.

Eve can do this by using her Diffie-Hellman oracle with values $A = g^a$ and $c_1 = g^k$ to obtain $s = g^{ak}$. Then she can compute the inverse $s^{-1}$ (via the $s^{p-2}$ and fast powering algorithm for example) and use it to find $m$:

$$c_2 \cdot s^{-1} \equiv mA^k \cdot (g^{ak})^{-1} \equiv m\cdot g^{ak}\cdot (g^{ak})^{-1} \equiv m \mod p$$

Problem 2.14

Prove that each of the following maps is a group homomorphism.

(a) The map $\phi: \mathbb{Z} \to \mathbb{Z}/N\mathbb{Z}$ that sends $a\in \mathbb{Z}$ to $a\mod N$.

Proof: Let $a = N\cdot q_a + r_a$ and $b = N\cdot q_b + r_b$ such that $0 \le r_a, r_b < N$. It follows that $\phi(a) = r_a$ and $\phi(b) = r_b$. Finally

$$\begin{align*} \phi(a+b) &= \phi(N\cdot q_a + r_a + N\cdot q_b + r_b) \\ &= N\cdot q_a + r_a + N\cdot q_b + r_b \mod N \\ &\equiv r_a + r_b \\ &\equiv \phi(a) + \phi(b) \mod N \end{align*}$$

(b) The map $\phi: \mathbb{R}^\ast \to GL_2(\mathbb{R})$ defined by

$$\phi(a) = \begin{pmatrix} a & 0 \\ 0 & a^{-1} \end{pmatrix}.$$

Proof: Let $a, b \in \mathbb{R}^\ast$.

$$\begin{align*} \phi(a)\phi(b) &= \begin{pmatrix}a & 0 \\ 0 & a^{-1}\end{pmatrix}\begin{pmatrix}b & 0 \\ 0 & b^{-1}\end{pmatrix} \\ &= \begin{pmatrix}ab & 0 \\ 0 & a^{-1}b^{-1}\end{pmatrix} \\ &= \begin{pmatrix}ab & 0 \\ 0 & (ab)^{-1}\end{pmatrix} \\ &= \phi(ab) \end{align*}$$

(c) The discrete log map $log_g: \mathbb{F}_p^\ast \to \mathbb{Z}/(p-1)\mathbb{Z}$ where $g$ is a primitive root modulo $p$.

Proof: This follows immediately from Problem 2.3(b) proved above.

Problem 2.19

Solve the 1700-year-old Chinese remainder theorem problem from the Sun Tzu Suan Ching:

We have a number of things, but we do not know exactly how many. If we count them by threes, we have two left over. If we count them by fives, we have three left over. If we count them by sevens, we have two left over. How many things are there?

Solution: This translates to the following system of congruences:

1. $x \equiv 2 \mod 3$
2. $x \equiv 3 \mod 5$
3. $x \equiv 2 \mod 7$

We can satisfy the first congruence generally with $x = 2 + 3y$. Substituting this into the second congruence,

$$2 + 3y \equiv 3 \mod 5 \implies 3y \equiv 1 \mod 5$$

and, using the program written for 1.34c, we find $3^{-1} \equiv 2 \mod 5$, so

$$y \equiv 2 \mod 5$$

and this gives the value

$$x = 2 + 3y = 2 + 3\cdot 2 = 8$$

as a solution to the first two congruences. A general solution is thus

$$x = 8 + 15z.$$

Substituting this into the third equation yields

$$8 + 15z \equiv 2 \mod 7 \implies z \equiv 1.$$

Finally,

$$x = 8 + 15z = 8 + 15 = 23.$$

A quick sanity check shows that indeed:

1. $23 \equiv 2 \mod 3$
2. $23 \equiv 3 \mod 5$
3. $23 \equiv 2 \mod 7$

Problem 2.35

Let

$$\textbf{a} = x^5 + 3x^4 - 5x^3 - 3x^2 + 2x + 2$$

$$\textbf{b} = x^5 + x^4 - 2x^3 + 4x^2 + x + 5$$

Use the Euclidean algorithm to compute $\gcd(\textbf{a}, \textbf{b})$ in each of the following rings.

(a) $\mathbb{F}_2[x]$

1. $\textbf{a} = \textbf{b}\cdot1 + (x^3 + x^2 + x + 1)$
2. $\textbf{b} = (x^3 + x^2 + x + 1)\cdot (x^2 + 1) + 0$

Therefore $\gcd(\textbf{a}, \textbf{b}) = x^3 + x^2 + x + 1.$

(b) $\mathbb{F}_3[x]$

1. $\textbf{a} = \textbf{b}\cdot 1 + (2x^4 + 2x^2 + x)$
2. $\textbf{b} = (2x^4 + 2x^2 + x)\cdot (2x + 2) + (x^2 + 2x + 2)$
3. $(2x^4 + 2x^2 + x) = (x^2 + 2x + 2)\cdot (2x^2 + 2x) + 0$

Therefore $\gcd(\textbf{a}, \textbf{b}) = x^2 + 2x + 2.$

(c) $\mathbb{F}_5[x]$

1. $\textbf{a} = \textbf{b}\cdot 1 + (2x^4 + 2x^3 + 3x^2 + x + 2)$
2. $\textbf{b} = (2x^4 + 2x^3 + 3x^2 + x + 2)\cdot (3x) + (4x^3 + x^2)$
3. $(2x^4 + 2x^3 + 3x^2 + x + 2) = (4x^3 + x^2)\cdot (3x + 1) + (2x^2 + x + 2)$
4. $(4x^3 + x^2) = (2x^2 + x + 2)\cdot (2x + 2) + (4x + 1)$
5. $(2x^2 + x + 2) = (4x + 1)\cdot (2x + 2) + 0$

Therefore $\gcd(\textbf{a}, \textbf{b}) = x + 4$, the monic version of polynomial $4x + 1.$

(d) $\mathbb{F}_7[x]$

1. $\textbf{a} = \textbf{b}\cdot1 + (2x^4 - 3x^3 + x - 3)$
2. $\textbf{b} = (2x^4 - 3x^3 + x - 3)\cdot(4x + 3) + 3x$
3. $4x + 3 = 3x\cdot 6 + 3$
4. $3x = 3\cdot x + 0$

Since $1$ is the monic version of polynomial $3$, $\gcd(\textbf{a} + \textbf{b}) = 1$.