Cấu trúc dữ liệu và Giải thuật Bài 148: Định lý Coppersmith (Coppersmith's Method / Small Roots of Polynomials) - Ứng dụng thuật toán LLL tấn công và phá vỡ các lỗ hổng của hệ mật RSA.

Trong lý thuyết số và mật mã học khóa công khai, bài toán tìm nghiệm của một phương trình đa thức modulo một hợp số tổng quát $N$:

$$f(x) \equiv 0 \pmod N$$

về bản chất là một bài toán NP-hard nếu không biết trước phép phân tích thừa số nguyên tố của $N = p \cdot q$. Nếu ai đó có thể giải phương trình bậc hai $x^2 \equiv a \pmod N$ một cách hiệu quả, họ có thể phân tích thừa số $N$ ngay lập tức và phá vỡ hoàn toàn hệ mật RSA.

Tuy nhiên, vào năm 1996, Don Coppersmith đã công bố một định lý đột phá: Nếu đa thức $f(x)$ bậc $d$ có một nghiệm nguyên "nhỏ" $x_0$ thỏa mãn $\vert{}x_0\vert{} \le N^{1/d}$, thì nghiệm $x_0$ này có thể được tìm thấy chính xác trong thời gian đa thức.

Chìa khóa của phương pháp Coppersmith là biến đổi bài toán tìm nghiệm modulo $N$ thành bài toán tìm nghiệm trên vành số nguyên $\mathbb{Z}$ thông qua cấu trúc lưới đa chiều và thuật toán giảm cơ sở lưới LLL (Bài 147). Phương pháp này đã trở thành công cụ nền tảng để phân tích độ an toàn và khai thác hàng loạt lỗ hổng chí mạng của hệ mật RSA.

1. Cơ sở Lý thuyết: Nghịch lý Tìm nghiệm Modulo và Chặn Coppersmith

Giả sử $f(x) \in \mathbb{Z}[x]$ là một đa thức đơn tử (monic polynomial - hệ số bậc cao nhất bằng 1) bậc $d$:

$$f(x) = x^d + a_{d-1}x^{d-1} + \dots + a_1 x + a_0$$

và $N$ là một số nguyên dương chưa biết phân tích thừa số.

Ta muốn tìm tất cả các nghiệm nguyên $x_0 \in \mathbb{Z}$ sao cho:

$$f(x_0) \equiv 0 \pmod N \quad \text{và} \quad \vert{}x_0\vert{} \le X$$

• Nếu $X \approx N$, số lượng nghiệm có thể rất lớn và việc tìm kiếm tương đương với việc phân tích $N$.

• Định lý Coppersmith: Tồn tại thuật toán thời gian đa thức tìm được mọi nghiệm $x_0$ thỏa mãn $\vert{}x_0\vert{} \le X$ với cận trên lý thuyết:

  $$X = N^{1/d - \epsilon}$$

  với độ phức tạp đa thức theo $(d, 1/\epsilon, \log N)$.

2. Bổ đề Howgrave-Graham: Cầu nối từ $\mathbb{Z}_N$ sang $\mathbb{Z}$

Năm 1997, Nick Howgrave-Graham đã đơn giản hóa và hình thức hóa chứng minh ban đầu của Coppersmith bằng một bổ đề đại số trực quan.

Cho đa thức $g(x) = \sum_{i=0}^n c_i x^i \in \mathbb{Z}[x]$. Định nghĩa chuẩn Euclidean của đa thức $g(x X)$ là:

$$\Vert{}g(x X)\Vert{} = \sqrt{\sum_{i=0}^n (c_i X^i)^2}$$

Phát biểu Bổ đề Howgrave-Graham

Bổ đề: Cho $g(x) \in \mathbb{Z}[x]$ là đa thức có bậc không vượt quá $n$. Giả sử tồn tại các số nguyên dương $m$ và $X$ sao cho:

1. $g(x_0) \equiv 0 \pmod{N^m}$ với một số nguyên $x_0$ thỏa mãn $\vert{}x_0\vert{} \le X$.

2. Chuẩn của đa thức thỏa mãn điều kiện nhỏ:

   $$\Vert{}g(x X)\Vert{} < \frac{N^m}{\sqrt{n + 1}}$$

   Khi đó, $x_0$ là một nghiệm của $g(x)$ chính xác trên vành số nguyên $\mathbb{Z}$, tức là:

   $$g(x_0) = 0$$

Phác thảo chứng minh:

Áp dụng bất đẳng thức Cauchy-Schwarz:

$$\vert{}g(x_0)\vert{} = \left\vert{} \sum_{i=0}^n c_i x_0^i \right\vert{} \le \sum_{i=0}^n \vert{}c_i\vert{} X^i \le \sqrt{n + 1} \cdot \Vert{}g(x X)\Vert{}$$

Từ giả thiết $\Vert{}g(x X)\Vert{} < \frac{N^m}{\sqrt{n+1}}$, ta suy ra:

$$\vert{}g(x_0)\vert{} < \sqrt{n + 1} \cdot \frac{N^m}{\sqrt{n + 1}} = N^m$$

Mặt khác, theo giả thiết 1, $g(x_0)$ là một bội số nguyên của $N^m$, nghĩa là $g(x_0) = k \cdot N^m$ với $k \in \mathbb{Z}$.

Số nguyên duy nhất chia hết cho $N^m$ mà có giá trị tuyệt đối strictly nhỏ hơn $N^m$ chỉ có thể là $0$ ($k = 0$).

Do đó, $g(x_0) = 0$ tuyệt đối trên $\mathbb{Z}$.

Ý nghĩa cốt tử: Tìm nghiệm của một đa thức trên $\mathbb{Z}$ là bài toán dễ (dùng giải tích số, phương pháp chia đôi, hoặc thuật toán phân tích đa thức của Berlekamp / Cantor-Zassenhaus trong thời gian đa thức). Bổ đề Howgrave-Graham chỉ ra rằng: Chỉ cần ta tìm được một đa thức $g(x)$ có hệ số đủ nhỏ, bài toán modulo phức tạp sẽ lập tức được giải quyết.

3. Thiết lập Không gian Lưới và Tận dụng Thuật toán LLL

Làm thế nào để tìm ra đa thức $g(x)$ thỏa mãn đồng thời hai điều kiện của Howgrave-Graham? Câu trả lời là: Dựng một lưới chứa các đa thức nhận $x_0$ làm nghiệm modulo $N^m$, sau đó dùng thuật toán LLL để tìm vector ngắn nhất.

Xây dựng Họ Đa thức Phụ trợ

Với đa thức gốc $f(x)$ bậc $d$ thỏa mãn $f(x_0) \equiv 0 \pmod N$:

1. $f(x_0)^k \equiv 0 \pmod{N^k}$.

2. Để thu được các đa thức có nghiệm modulo $N^m$, ta xét hệ đa thức:

   $$g_{i, k}(x) = x^i \cdot N^{m - k} \cdot f(x)^k \quad (0 \le k \le m, \; 0 \le i < d)$$

   Mọi đa thức này đều có tính chất: $g_{i, k}(x_0)$ chia hết cho $N^m$.

3. Bất kỳ tổ hợp tuyến tính nguyên nào của các đa thức này:

   $$h(x) = \sum a_{i, k} g_{i, k}(x) \quad (a_{i, k} \in \mathbb{Z})$$

   cũng đều thỏa mãn $h(x_0) \equiv 0 \pmod{N^m}$.

Áp dụng LLL để tìm Vector Ngắn

Mỗi đa thức $p(x) = \sum c_j x^j$ được ánh xạ thành một vector hệ số có trọng số:

$$v_p = (c_0, c_1 X, c_2 X^2, \dots, c_n X^n) \implies \Vert{}v_p\Vert{} = \Vert{}p(x X)\Vert{}$$

Tập hợp tất cả các vector $v_{g_{i, k}}$ tạo thành một hệ cơ sở của một lưới $\Lambda$.

• Kích thước ma trận cơ sở là $M \times M$ với $M = m \cdot d$.

• Ma trận cơ sở có dạng tam giác dưới, cho phép tính định thức lưới $\det(\Lambda)$ bằng tích các phần tử trên đường chéo chính.

• Theo tính chất của thuật toán LLL (Bài 147), vector ngắn nhất $b_1$ tìm được thỏa mãn:

  $$\Vert{}b_1\Vert{} \le 2^{(M-1)/4} \cdot (\det(\Lambda))^{1/M}$$

• Đặt điều kiện để $\Vert{}b_1\Vert{}$ thỏa mãn chặn Howgrave-Graham $\Vert{}b_1\Vert{} < \frac{N^m}{\sqrt{M}}$, giải bất phương trình theo $X$ khi $m \to \infty$, ta thu được chặn tối ưu của Coppersmith:

  $$X < N^{1/d}$$

   Đa thức f(x) mod N                  Hệ đa thức g_{i, k}(x) mod N^m
   (Khó tìm nghiệm)      =======>      (Không gian Lưới đa chiều Λ)
                                                    ||
                                                    || Thuật toán LLL
                                                    v
   Nghiệm x0 trên Z      <=======      Vector ngắn nhất b1
   (Giải bằng Newton)                  (Thỏa mãn chuẩn Howgrave-Graham)

4. Hiện thực hóa Cuộc tấn công Coppersmith bằng Golang

Xét trường hợp kinh điển nhất trong phân tích RSA: Stereotyped Message Attack với số mũ công khai nhỏ $e = 3$.

• Người gửi mã hóa bản tin: $C \equiv (M + x_0)^3 \pmod N$.

• Kẻ tấn công biết cấu trúc tiền tố/hậu tố $M$ (bản tin mẫu dạng "User_ID_9999_Pass="), chỉ thiếu một phần nhỏ $x_0$ ở cuối.

• Đa thức cần tìm nghiệm nhỏ: $f(x) = (M + x)^3 - C \equiv 0 \pmod N$.

• Bậc $d = 3$. Chặn nghiệm: $\vert{}x_0\vert{} \le X \approx N^{1/3}$.

Chương trình Golang dưới đây xây dựng lưới bậc $4$ ($m=1$) với hệ cơ sở:

$$g_0(x) = N, \quad g_1(x) = N \cdot x, \quad g_2(x) = N \cdot x^2, \quad g_3(x) = f(x)$$

Áp dụng LLL để tìm đa thức $h(x)$ có nghiệm trên $\mathbb{Z}$, sau đó giải nghiệm nguyên bằng phương pháp tìm kiếm nhị phân (Bisection/Integer Newton):

Go

package main

import (
	"fmt"
	"math"
	"math/big"
)

// Cấu trúc LLL đơn giản hóa cho lưới số thực/nguyên
type LLLSolver struct {
	d     int
	basis [][]float64
	delta float64
}

func NewLLLSolver(basis [][]float64, delta float64) *LLLSolver {
	d := len(basis)
	cp := make([][]float64, d)
	for i := range basis {
		cp[i] = make([]float64, len(basis[i]))
		copy(cp[i], basis[i])
	}
	return &LLLSolver{d: d, basis: cp, delta: delta}
}

func dot(u, v []float64) float64 {
	var s float64
	for i := range u {
		s += u[i] * v[i]
	}
	return s
}

func (l *LLLSolver) Reduce() [][]float64 {
	n := len(l.basis[0])
	bStar := make([][]float64, l.d)
	mu := make([][]float64, l.d)
	gamma := make([]float64, l.d)
	for i := 0; i < l.d; i++ {
		bStar[i] = make([]float64, n)
		mu[i] = make([]float64, l.d)
	}

	updateGSO := func() {
		for i := 0; i < l.d; i++ {
			copy(bStar[i], l.basis[i])
			for j := 0; j < i; j++ {
				if gamma[j] > 1e-11 {
					mu[i][j] = dot(l.basis[i], bStar[j]) / gamma[j]
				} else {
					mu[i][j] = 0
				}
				for k := 0; k < n; k++ {
					bStar[i][k] -= mu[i][j] * bStar[j][k]
				}
			}
			mu[i][i] = 1.0
			gamma[i] = dot(bStar[i], bStar[i])
		}
	}

	updateGSO()
	k := 1
	for k < l.d {
		// Size reduction
		for j := k - 1; j >= 0; j-- {
			if math.Abs(mu[k][j]) > 0.5 {
				q := math.Round(mu[k][j])
				for i := 0; i < n; i++ {
					l.basis[k][i] -= q * l.basis[j][i]
				}
				updateGSO()
			}
		}

		// Lovasz condition
		if gamma[k] < (l.delta-mu[k][k-1]*mu[k][k-1])*gamma[k-1] {
			l.basis[k], l.basis[k-1] = l.basis[k-1], l.basis[k]
			updateGSO()
			if k > 1 {
				k--
			}
		} else {
			k++
		}
	}
	return l.basis
}

// Đánh giá giá trị đa thức trên Z: h(x) = c3*x^3 + c2*x^2 + c1*x + c0
func evalPoly(coeffs []float64, x int64) float64 {
	var res float64 = 0
	p := 1.0
	for _, c := range coeffs {
		res += c * p
		p *= float64(x)
	}
	return res
}

// Tìm nghiệm nguyên x0 trong đoạn [0, X]
func findIntegerRoot(coeffs []float64, X int64) (int64, bool) {
	// Kiểm tra các giá trị lân cận hoặc dùng tìm kiếm tuyến tính/nhị phân
	for x := int64(0); x <= X; x++ {
		val := evalPoly(coeffs, x)
		if math.Abs(val) < 1e-3 {
			return x, true
		}
	}
	return -1, false
}

func main() {
	// Mô phỏng RSA với e = 3
	// Hai số nguyên tố p, q
	p := big.NewInt(1000003)
	q := big.NewInt(1000033)
	N := new(big.Int).Mul(p, q) // N ≈ 10^12

	// Bản tin M đã biết một phần, phần bí mật nhỏ x0 cần khôi phục
	// Giả sử m = Base + x0
	baseMsg := big.NewInt(500000)
	secretX := int64(1234) // Nghiệm bí mật nhỏ cần tìm (|x0| < N^(1/3) ≈ 10000)
	actualM := new(big.Int).Add(baseMsg, big.NewInt(secretX))

	// Bản mã C = actualM^3 mod N
	e := int64(3)
	C := new(big.Int).Exp(actualM, big.NewInt(e), N)

	// Đa thức f(x) = (baseMsg + x)^3 - C (mod N)
	// Khai triển: x^3 + 3*baseMsg*x^2 + 3*baseMsg^2*x + (baseMsg^3 - C)
	three := big.NewInt(3)
	base2 := new(big.Int).Mul(baseMsg, baseMsg)
	base3 := new(big.Int).Mul(base2, baseMsg)

	a3 := big.NewInt(1)
	a2 := new(big.Int).Mul(three, baseMsg)
	a1 := new(big.Int).Mul(three, base2)
	a0 := new(big.Int).Sub(base3, C)

	a2.Mod(a2, N)
	a1.Mod(a1, N)
	a0.Mod(a0, N)

	// Chặn trên của nghiệm: X <= N^(1/3)
	nFloat, _ := new(big.Float).SetInt(N).Float64()
	X := int64(math.Pow(nFloat, 1.0/3.0))

	fmt.Printf("=== MÔ PHỎNG TẤN CÔNG COPPERSMITH RSA (e = 3) ===\n")
	fmt.Printf("Modulus N = %s\n", N.String())
	fmt.Printf("Khóa công khai e = %d\n", e)
	fmt.Printf("Chặn nghiệm tìm kiếm X = N^(1/3) = %d\n", X)
	fmt.Printf("Nghiệm bí mật thực tế cần tìm: x0 = %d\n\n", secretX)

	// Dựng ma trận lưới Coppersmith (Bậc 4):
	// g0(x) = N
	// g1(x) = N * x
	// g2(x) = N * x^2
	// g3(x) = f(x) = x^3 + a2*x^2 + a1*x + a0
	// Vector biểu diễn: (c0, c1*X, c2*X^2, c3*X^3)
	xFloat := float64(X)
	x2 := xFloat * xFloat
	x3 := x2 * xFloat

	a0F, _ := new(big.Float).SetInt(a0).Float64()
	a1F, _ := new(big.Float).SetInt(a1).Float64()
	a2F, _ := new(big.Float).SetInt(a2).Float64()

	basis := [][]float64{
		{nFloat, 0, 0, 0},
		{0, nFloat * xFloat, 0, 0},
		{0, 0, nFloat * x2, 0},
		{a0F, a1F * xFloat, a2F * x2, 1.0 * x3},
	}

	// Chạy LLL để tìm vector ngắn nhất
	lll := NewLLLSolver(basis, 0.75)
	reduced := lll.Reduce()

	// Vector ngắn nhất là hàng đầu tiên của ma trận đã giảm
	shortestVec := reduced[0]

	// Khôi phục lại các hệ số thực của đa thức h(x) trên Z bằng cách chia lại cho X^i
	polyCoeffs := []float64{
		shortestVec[0],
		shortestVec[1] / xFloat,
		shortestVec[2] / x2,
		shortestVec[3] / x3,
	}

	fmt.Println("Đa thức ngắn nhất h(x) thu được từ LLL:")
	fmt.Printf("h(x) = (%.2e)*x^3 + (%.2e)*x^2 + (%.2e)*x + (%.2e)\n",
		polyCoeffs[3], polyCoeffs[2], polyCoeffs[1], polyCoeffs[0])

	// Tìm nghiệm nguyên của h(x) trên Z
	recoveredRoot, found := findIntegerRoot(polyCoeffs, X)
	if found {
		fmt.Printf("\n[THÀNH CÔNG] Đã khôi phục chính xác nghiệm bí mật: x0 = %d\n", recoveredRoot)
		recoveredMsg := new(big.Int).Add(baseMsg, big.NewInt(recoveredRoot))
		fmt.Printf("Bản rõ hoàn chỉnh đã giải mã: %s\n", recoveredMsg.String())
	} else {
		fmt.Println("\n[THẤT BẠI] Không tìm thấy nghiệm trong phạm vi!")
	}
}

5. Phân tích Độ phức tạp và Ranh giới Ngưỡng Chặn

So sánh các Biến thể của Định lý Coppersmith

6. Các Kịch bản Tấn công RSA Kinh điển bằng Coppersmith

• Stereotyped Messages Attack (Bản tin rập khuôn): Khi người gửi mã hóa bản tin có định dạng cố định (chẳng hạn header giao thức chuẩn, timestamp hoặc nonce ngắn ở cuối), nếu số mũ $e$ nhỏ (ví dụ $e = 3$), kẻ tấn công chỉ cần biết phần lớn bản tin và dùng Coppersmith giải mã phần còn lại mà không cần phân tích khóa $N$.

• Tấn công Franklin-Reiter Related Message: Nếu hai bản tin có mối liên hệ tuyến tính $M_2 = a \cdot M_1 + b \pmod N$ được mã hóa bởi cùng khóa công khai $e = 3$, định lý Coppersmith cho phép khôi phục trọn vẹn cả hai bản rõ trong chớp mắt.

• Tấn công Khóa bí mật nhỏ Boneh-Durfee ($d < N^{0.292}$): Từ phương trình khóa RSA $e \cdot d - k \cdot \phi(N) = 1$, Dan Boneh và Glenn Durfee (1999) đã mô hình hóa thành đa thức hai biến $f(k, x)$ modulo $e$ và dùng Coppersmith chứng minh rằng: Mọi khóa bí mật $d$ có kích thước $d < N^{0.292}$ đều có thể bị bẻ khóa hoàn toàn trong thời gian đa thức. (Cải tiến vượt bậc so với chặn Wiener $d < \frac{1}{3} N^{1/4}$).

• Phân tích $N$ khi biết một phần số bit của $p$ (Partial Key Exposure / Factoring with Known Bits): Nếu kẻ tấn công thu thập được $1/4$ số bit cao nhất (hoặc thấp nhất) của thừa số nguyên tố $p$ (thông qua tấn công kênh kề Side-Channel Attacks hoặc lỗi rò rỉ bộ nhớ Heartbleed), đặt $p = P_0 + x_0$, đa thức $f(x) = P_0 + x$ modulo $p$ sẽ tìm ra $x_0$ và phân tích thành công $N$.