Chapter 3. Integer Factorization and RSA

Exercise (Câu 3.4)

Euler's phi function \(\phi(N)\) is the function defined by

\[\phi(N) = \lvert \{ 0 \leqslant k < N: \gcd(k, N)=1\} \rvert.\]

Chứng minh định lý Euler đã có trong bài viết về hàm Euler.

Exercise (Câu 3.5)

Properties of Euler's phi function

If \(p\) and \(q\) are distinct primes, how is \(\phi(pq)\) related to \(\phi(p)\) and \(\phi(q)\)?

Chứng minh tính chất nhân tính của hàm Euler đã có ở bài viết về hàm Euler.

Exercise (Câu 3.6)

Let \(N\), \(c\), and \(e\) be positive integers satisfying the conditions \(\gcd(N,c)=1\) and \(\gcd(e,\phi(N))=1\).

Explain how to solve the congruence \(x^e \equiv c \pmod{N}\) assuming that you know the value of \(\phi(N)\)

Vì \(\gcd(e, \phi(N)) = 1\), ta có thể tìm số \(d \in \mathbb{Z}\) sao cho \(ed \equiv 1 \pmod{\phi(N)}\) với thuật toán Euclid mở rộng.

Khi đó \(ed = k\phi(N) + 1\) với \(k \in \mathbb{Z}\).

Vì \(\gcd(N, c)=1\) nên \(\gcd(N,x)=1\), hay

\[c^d = \left(x^e\right)^d = x^{ed} = x^{k\phi(N) + 1} = (x^k)^{\phi(N)} x,\]

và ta đã biết \((x^k)^{\phi(N)} \equiv 1 \pmod{N}\) từ Câu 3.4.

Như vậy \(c^d \equiv x \pmod{N}\).

Exercise (Câu 3.11)

Alice chooses two large primes \(p\) and \(q\) and she publishes \(N=pq\). It is assumed that \(N\) is hard to factor. Alice also chooses three random numbers \(g\), \(r_1\), and \(r_2\) modulo \(N\) and computes

\[g_1 \equiv g^{r_1(p-1)} \pmod{N} \qquad \text{and} \qquad g_2 \equiv g^{r_2(q-1)} \pmod{N}\]

Her public key is the triple \((N, g_1, g_2)\) and her private key is the pair of primes \((p, q)\).

Now Bob wants to send the message \(m\) to Alice, where \(m\) is a number modulo \(N\). He chooses two random integers \(s_1\) and \(s_2\) modulo \(N\) and computes

\[c_1 \equiv mg_1^{s_1} \pmod{N} \qquad \text{and} \qquad c_2 \equiv mg_2^{s_2} \pmod{N}\]

Bob sends the ciphertext \((c_1, c_2)\) to Alice.

Decryption is extreamly fast and essy. Alice uses the Chinese remainder theorem to solve the pair of congruences

\[x \equiv c_2 \pmod{p} \qquad \text{and} \qquad x \equiv c_2 \pmod{q}\]

Prove that Alice's solution \(x\) is equal to Bob's plaintext \(m\).

Ta có

\[c_1 \equiv mg_1^{s_1} \pmod{N} \equiv mg_1^{s_1} \pmod{p} \equiv m \pmod{p}\]

do \(g_1^{s_1} = (g_1^{s_1 r_1})^{(p-1)} \equiv 1 \pmod{p}\).

Tương tự ta có \(c_2 \equiv m \pmod{q}\).

Nghiệm của hệ đồng dư là

\[x \equiv c_1 q q' + c_2 p p' \pmod N\]

với \(p p' + q q' = 1\).

\[\Rightarrow x \equiv m p p' + m q q' \equiv m(p p' + q q') \equiv m \pmod N\]

Ta có

\[g_1 \equiv g^{r_1 (p-1)} \pmod N \equiv g^{r_1 (p-1)} \pmod p \equiv 1 \pmod p.\]

Suy ra \(p = \gcd(g_1-1, N)\). Tương tự, \(q = \gcd(g_2-1, N)\).

Như vậy ta đã khôi phục lại private key.

Exercise (Câu 3.13)

Find \(x\), \(y\) such that \(x e_1 + y e_2 = 1 = \gcd(e_1,e_2)\).

\[\Rightarrow m = c_1^x c_2^y = m^{e_1 x + e_2 y} = m \pmod{N}\]

Exercise (Câu 3.14.)

[Exercise]

Because 3, 11 and 17 are primes number, \(a \equiv a^3 \pmod 3\), \(a \equiv a^{11} \pmod{11}\), \(a \equiv a^{17} \pmod{17}\). We have system congruence

\[\begin{split}a & \equiv a^3 \pmod 3 \\ a & \equiv a^{11} \pmod{11} \\ a & \equiv a^{17} \pmod{17}\end{split}\]

Consider that \(a^3 \equiv a \pmod 3\), \(a^{3^2} \equiv a^3 \equiv a \pmod 3\), \(\cdots\), \(a^{3^i} \equiv a \pmod 3\). And \(561 = 2 \cdot 3^5 + 2 \cdot 3^3 + 2 \cdot 3^2 + 3^1\), \(a^{561} \equiv a^2 \cdot a^2 \cdot a^2 \cdot a \equiv a^9 \equiv a \pmod 3\).

Similarly, \(a^{561} \equiv a \pmod{11}\), \(a^{561} \equiv a \pmod{17}\). From system congruence:

\[\begin{split}a^{561} & \equiv a \pmod 3 \\ a^{561} & \equiv a \pmod{11} \\ a^{561} & \equiv a \pmod{17}\end{split}\]

Using CRT, \(a^{561} = (187 \cdot 1 \cdot a + 51 \cdot 8 \cdot a + 33 \cdot 16 \cdot a) \pmod{561} = a \pmod{561}\)

Suppose that \(n\) is even (\(n \geqslant 4\)), we have

\[(n-1)^{n-1} = (-1)^{n-1} = -1 \pmod n,\]

but \(a^{n-1} \equiv 1 \pmod n\) for all \(a\), which is contrary. So \(n\) must be odd.

Suppose that \(n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}\) (\(p_i\) is odd prime). Because \(a^{p^{e-1} (p-1)} \equiv 1 \pmod{p^e}\) and \(a^{n-1} \equiv 1 \pmod n\), we have \(a^{n-1} \equiv 1 \pmod{p^e}\).

\(\Rightarrow p^{e-1}(p-1) \mid (n-1) \Rightarrow p^{e-1} \mid (n-1)\), but \(p^{e-1} \mid n\), which is contrary if \(e \geqslant 2\). Hence \(e\) must be 1.

Therefore \(n = p_1 p_2 \cdots p_r\)

Exercise (Câu 3.37)

[EXERCISE]

\[ \begin{align}\begin{aligned}\left(a^{\frac{p-1}{2}}\right)^2 \equiv a^{p-1} \equiv 1 \pmod p\\\Rightarrow \binom{a}{p} = \pm 1\\\Rightarrow \left(a^{\frac{p-1}{2}} - 1\right)\left(a^{\frac{p-1}{2}} + 1\right) \equiv 0 \pmod p\\\Rightarrow a^{\frac{p-1}{2}} \equiv \pm 1 \pmod p.\end{aligned}\end{align} \]

If \(a\) is quadratic residue, then \(a \equiv b^2 \pmod p\)

\(\Rightarrow a^{\frac{p-1}{2}} \equiv (b^2)^{\frac{p-1}{2}} = b^{p-1} \equiv 1 \pmod p\)

If \(a^{\frac{p-1}{2}} \equiv 1 \pmod p\)

Let \(g\) be generator modulo \(p\), then \(a \equiv g^m \pmod p\)

If \(m\) is even \(\Rightarrow a \equiv g^{2k} \pmod p \Rightarrow a^{\frac{p-1}{2}} \equiv 1 \pmod p\)

If \(m\) is odd \(\Rightarrow a = g^{2k+1} \pmod p \Rightarrow a^{\frac{p-1}{2}} \equiv g^{(2k+1)\frac{p-1}{2}} \equiv g^{p-1} g^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}}\not\equiv 1 \pmod p\), because \(p-1\) is smallest number that \(g^{p-1} \equiv 1 \pmod p\)

From (a) and (b) \(\binom{-1}{p} \equiv (-1)^{\frac{p-1}{2}} \pmod p\), if \(p=4k+1 \Rightarrow (-1)^{\frac{p-1}{2}} \equiv (-1)^{2k} \equiv 1 \pmod p\) \ If \(p=4k+3 \Rightarrow (-1)^{\frac{p-1}{2}} \equiv (-1)^{2k+1} \equiv -1 \pmod p\)

Exercise (Câu 3.38)

Prove that the three parts of the quadratic reciprocity theorem are equivalent to the following three concise formulas, where \(p\) and \(q\) are odd primes.

\(\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}\).

With \(p \equiv 1 \pmod 4 \Rightarrow \left(\frac{-1}{p}\right) = 1 = (-1)^{\frac{p-1}{2}} \pmod p\).

Similarly with \(p \equiv 3 \pmod 4\) \(\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\).

First we need a lemma (Gauss lemma): suppose \(p\) is an odd prime, and \(a \in \mathbb{Z}\), \(\gcd(a, p) = 1\). Consider the set

\[a, 2a, 3a, \cdots, \frac{p-1}{2} a.\]

If \(s\) of those residues are greater than \(\frac{p}{2}\), then \(\binom{a}{p} = (-1)^s\)

Proof of lemma

Among smallest residues of \(a\), \(2a\), \(3a\), ..., \(\dfrac{p-1}{2}a\), suppose that \(u_1\), \(u_2\), ..., \(u_s\) are residues greater than \(\dfrac{p}{2}\), and \(v_1\), \(v_2\), ..., \(v_t\) are residues smaller than \(\frac{p}{2}\).

Because \(\gcd(ja, p) = 1\) for all \(j\), where \(1 \leqslant j \leqslant \dfrac{p-1}{2}\), all \(u_i, v_j \neq 0\), then

\[u_i, v_j \in \{1 , 2,\cdots,p-1\}.\]

We will prove that, the set

\[\{p-u_1, p-u_2, \cdots, p-u_s, v_1, v_2, \cdots, v_t\}\]

is a permutation of \(\{1,2,\cdots,\frac{p-1}{2}\}\)

It is clear that there are no \(2\) numbers \(u_i\) or \(2\) numbers \(v_j\) simultaneously congruent modulo \(p\). Because if \(ma \equiv na \pmod p\) and \(\gcd(a, p) = 1\), then \(m\equiv n \pmod p\) and it is contrast with \(m, n \leqslant \dfrac{p-1}{2}\).

Similarly, we see that there are no numbers \(p-u_i\) congruent with \(v_j\), so

\[(p-u_1)(p-u_2)\cdots(p-u_s)v_1 v_2 \cdots v_t \equiv \left(\frac{p-1}{2}\right)! \pmod p.\]

On the other hand, \(u_1\), \(u_2\), ..., \(u_s\), \(v_1\), \(v_2\), ..., \(v_t\) are smallest residues of \(a\), \(2a\), \(3a\), ..., \(\dfrac{p-1}{2}\), so

\[u_1 u_2 \cdots u_s v_1 v_2 \cdots v_t \equiv a^{\frac{p-1}{2}} \left(\frac{p-1}{2}\right)! \pmod p.\]

Therefore

\[(-1)^s a^{\frac{p-1}{2}} \left(\frac{p-1}{2}\right)! \equiv \left(\frac{p-1}{2}\right)! \pmod p\]

And because

\[\gcd(p, \left(\frac{p-1}{2}\right)!) = 1 \Rightarrow (-1)^s a^{\frac{p-1}{2}} \equiv 1 \pmod p,\]

then

\[a^{\frac{p-1}{2}} \equiv (-1)^s \pmod p, \ \binom{a}{p} = a^{\frac{p-1}{2}},\]

and \(\binom{a}{p} = (-1)^s \pmod p\).

Return to problem: using theorem above, we need to find the number of residues, which are greater than \(\frac{p}{2}\) among \(1 \cdot 2\), \(2 \cdot 2\), \(\cdots\), \(\frac{p-1}{2} \cdot 2\). Therefore we only need to know which numbers are greater than \(\frac{p}{2}\)

\(\Rightarrow\) there are \(s = \frac{p-1}{2} - \left[\frac{p}{4}\right] \Rightarrow \left(\frac{2}{p}\right) = (-1)^{\frac{p-1}{2} - \left[\frac{p}{4}\right] }\)

With \(p \equiv 1, 3, 5, 7 \pmod 8\), we have

\[ \begin{align}\begin{aligned}\frac{p-1}{2} - \left[\frac{p}{4}\right] \equiv \frac{p^2-1}{8} \pmod 2\\\Rightarrow \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}\end{aligned}\end{align} \]
\[\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\]

We need a lemma: Suppose \(p\) is an odd prime, \(a\) is odd and \(\gcd(a, p) = 1\), then \(\left(\frac{a}{p}\right) = (-1)^{T(a, p)}\), with

\[T(a, p) = \sum_{j=1}^{\frac{p-1}{2}}\left[\frac{ja}{p}\right].\]

Proof of lemma

Consider smallest residues of \(a\), \(2a\), \(3a\), \(\cdots\), \(\frac{p-1}{2} \cdot a\). As Gauss's lemma, \(u_1\), \(u_2\), \(\cdots\), \(u_s\), \(v_1\), \(v_2\), \(\cdots\), \(v_t\) are residues greater and less than \(\frac{p}{2}\) respectively. According to Euclidean divisor:

\[ja = p \left[\frac{ja}{p}\right] + \text{remainder},\]

remainder is \(u_i\) or \(v_j\). We have such \(\frac{p-1}{2}\) equations and add them together

\[\Rightarrow \sum_{j=1}^{\frac{p-1}{2}}ja = \sum_{j=1}^{\frac{p-1}{2}}p\left[\frac{ja}{p}\right] + \sum_{i=1}^{s}u_i + \sum_{j=1}^{t}v_j\]

As we pointed out in Gauss's lemma, the set \(p-u_1\), \(p-u_2\), \(\cdots\), \(p-u_s\), \(v_1\), \(v_2\), \(\cdots\), \(v_t\) is a permutation of the set 1, 2, \(\cdots\), \(\frac{p-1}{2}\)

\[\sum_{j=1}^{\frac{p-1}{2}}j = \sum_{i=1}^{s}(p-u_i) + \sum_{j=1}^{t}v_t = ps - \sum_{i=1}^{s}u_i + \sum_{j=1}^{t}v_t\]
\[\Rightarrow \sum_{j=1}^{\frac{p-1}{2}}ja - \sum_{j=1}^{\frac{p-1}{2}}j = \sum_{j=1}^{\frac{p-1}{2}}p\left[\frac{ja}{p}\right] - ps + 2\sum_{i=1}^{s}u_i\]

From formula of \(T(a, p)\), \((a-1)\sum_{j=1}^{\frac{p-1}{2}}j = pT(a, p) - ps + 2 \sum_{i=1}^{s}u_i\)

Because \(a\), \(p\) are odd, \(T(a, p) \equiv s \pmod 2\). From Gauss's lemma we finish.

Return to problem: Consider pairs \((x, y)\), where \(1 \leqslant x \leqslant \frac{p-1}{2}\) and \(1 \leqslant y \leqslant \frac{q-1}{2}\), there are \(\frac{p-1}{2}\cdot\frac{q-1}{2}\) pairs. We divide those pairs into 2 groups, depending on the magnitude of \(px\) and \(qy\).

Because \(p\), \(q\) are two different primes, \(px \neq qy\), \(\forall (x, y)\).

We consider pairs with \(qx > py\). With every fixed element of \(x\) (\(1 \leqslant x \leqslant \frac{p-1}{2}\)), exist \(\left[\frac{qx}{p}\right]\) elements \(y\) satisfying \(1 \leqslant y \leqslant \frac{qx}{p}\). Therefore, there are \(\sum_{i=1}^{\frac{p-1}{2}}\left[\frac{iq}{p}\right]\) pairs. When \(qx < py\), similarly, there are \(\sum_{j=1}^{\frac{q-1}{2}}\left[\frac{jp}{q}\right]\) pairs. Because there are \(\frac{p-1}{2} \cdot \frac{q-1}{2}\) pairs, we have equation

\[\sum_{i=1}^{\frac{p-1}{2}}\left[\frac{iq}{p}\right] + \sum_{j=1}^{\frac{q-1}{2}}\left[\frac{jp}{q}\right] = \frac{p-1}{2} \cdot \frac{q-1}{2}\]

From definition of \(T(p, q)\), we have result

\[(-1)^{T(p, q) + T(q, p)} = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}\]

Exercise (Câu 3.39)

Let \(p\) be a prime satisfying \(p \equiv 3 \pmod 4\).

Let \(a\) be a quadratic residue modulo \(p\). Prove that the number

\[b \equiv a^{\frac{p+1}{4}} \pmod p\]

has the property that \(b^2 \equiv a \pmod p\). (Hint. Write \(\dfrac{p+1}{2}\) as \(1+\dfrac{p-1}{2}\) and use Exercise 3.37.) This gives an easy way to take square roots modulo \(p\) for primes that are congruent to 3 modulo 4.

Dùng Câu 3.37, \(a^{\frac{p-1}{2}} \equiv 1 \pmod p\) vì \(a\) là thặng dư chính phương modulo \(p\).

Khi đó

\[b^2 \equiv a^{\frac{p+1}{2}} \equiv a^{1+\frac{p-1}{2}} \equiv a \cdot a^{\frac{p-1}{2}} \equiv a \cdot 1 \equiv 1 \pmod p\]

Exercise (Câu 3.40)

Let \(p\) be and odd prime, let \(g \in \mathbb{F}^{*}_p\) be a primitive root, and let \(h \in \mathbb{F}^{*}_p\). Write \(p - 1 = 2^sm\) with \(m\) odd and \(s \geqslant 1\), and write the binary expansion of \(\log_g(h)\) as

\[log_g(h) = \varepsilon_0 + 2\varepsilon_1 + 4\varepsilon_2 + 8\varepsilon_3 + \cdots \quad \text{with} \quad \varepsilon_0, \varepsilon_1, \cdots \in \{0, 1\}\]

Give an algorithm that generalizes Example 3.69 and allows you to rapidly compute \(\varepsilon_0, \varepsilon_1, \cdots, \varepsilon_{s-1}\), thereby proving that the first \(s\) bits of the discrete logarithm are insecure.

Thuật toán 2 (Thuật toán tìm \(s\) least significant bit (LSB) của \(x\) trong \(g^x \equiv h \pmod p\))

Input: \(g\), \(h\), \(p\) (\(p-1=2^s m\))

Output: \(s\) least significant bits của \(x\) trong \(g^x \equiv h \pmod p\)

  1. Ta sẽ tìm mảng \(\varepsilon_0, \varepsilon_1, \cdots, \varepsilon_{s-1}\)

  2. For \(i = 0, \ldots, s-1\)

    1. If \(h\) là thặng dư chính phương

      1. \(\varepsilon_i = 0\), \(h = \sqrt{h} \pmod p\)

    2. ElseIf \(\varepsilon_i = 1\)

      1. \(h = \sqrt{g^{-1}h} \pmod p\)

    3. EndIf

  3. EndFor

Exercise (Câu 3.41)

Let \(p\) be a prime satisfying \(p \equiv 1 \pmod 3\). We say that \(a\) is a cubic residue modulo :math:`p` if \(p \nmid a\) and there is an integer \(c\) satisfying \(a \equiv c^3 \pmod p\).

  1. Let \(a\) and \(b\) be cubic residues modulo \(p\). Prove that \(ab\) is a cubic residue modulo \(p\).

  2. Give an example to show that (unlike the case with quadratic residues) it is possible for none of \(a\), \(b\) and \(ab\) to the a cubic residue modulo \(p\)

  3. Let \(g\) be a primitive root modulo \(p\). Prove that \(a\) is a cubic residue modulo \(p\) if and only if \(3 \mid \log_g(a)\), where \(\log_g(a)\) is the discrete logarithm of \(a\) to the base \(g\).

  4. Suppose instead that \(p \equiv 2 \pmod 3\). Prove that for every integer \(a\) there is an integerr \(c\) satisfying \(a \equiv c^3 \pmod p\). In other words, if \(p \equiv 2 \pmod 3\), show that every number is a cube modulo \(p\).

  1. Ta có \(a \equiv x^3 \pmod p\) và \(y \equiv y^3 \pmod p\) với \(x\) và \(y\) nào đó thuộc \(\mathbb{F}_p\).

Suy ra \(ab \equiv x^3 y^3 = (xy)^3 \pmod p\) cũng là thặng dư bậc ba.

  1. Gọi \(g\) là primitive root modulo \(p\).

Ta chọn \(a \equiv g^{3k+1} \pmod p\) và \(b \equiv g^{3k'+1} \pmod p\).

Khi đó \(ab \equiv g^{(3k+1)+(3k'+1)} \equiv g^{3(k+k')+2} \pmod p\) không phải thặng dư bậc ba.

  1. Quên làm.

Điều kiện đủ. Nếu \(a\) là thặng dư bậc ba modulo \(p\), giả sử \(a \equiv c^3 \pmod 3\) và \(c \equiv g^u = \pmod p\).

Khi đó \(a = g^{3u} \pmod p\) và theo định lý Lagrange thì \(3 \mid \log_g(a)\).

Điều kiện cần. Nếu \(3 \mid \log_g(a)\) thì làm ngược lại bước chứng minh điều kiện đủ.

  1. Vì \(p \equiv 2 \pmod 3\) nên \(\gcd(p-1, 3) = 1\). Khi đó tồn tại phần tử \(d\) là nghịch đảo của \(3\) modulo \(p-1\).

Suy ra phương trình \(x^3 \equiv a \pmod p\) có nghiệm \(a^d = x \pmod p\).

Nói cách khác mọi phần tử đều là số bậc ba modulo \(p\).