IV. Một Số Kỹ Thuật Tấn Công N - Phân Tích Số Lớn Ra Tích Hai Thừa Số Nguyên Tố (Tiếp Theo)
2. Tấn Công Với Số N Không Phải Tích Hai Số Nguyên Tố Lớn
Nhiều người có thể thắc mắc rằng, mặc dù mật mã RSA thực chất là bài toán lũy thừa trong module số n, nhưng tại sao cần phải chọn n là tích hai thừa số nguyên tố lớn? Liệu có thể chọn n chỉ là một số đủ lớn hay thậm chí chỉ là một số nguyên tố lớn không?
Khi n không tuân thủ nguyên tắc là tích của hai thừa số nguyên tố lớn, điều này sẽ ảnh hưởng nghiêm trọng đến tính bảo mật của giá trị ϕ(n). Ví dụ, nếu n có các ước là hợp số, chúng ta có thể tiếp tục phân tích các ước hợp số đó ra thành thừa số nguyên tố, từ đó làm giảm độ khó của bài toán phân tích n xuống các ước của n và tiếp tục giảm sâu hơn nữa. Điều này dẫn tới việc tính toán ϕ(n) dễ dàng hơn, và kiẻ tấn công có thể dễ dàng tìm ra số mũ bí mật d.
Nếu n chỉ được chọn là một số nguyên tố lớn, thì giá trị ϕ(n) sẽ có giá trị ngay lập tức bằng n−1.
Challenge luyện tập cho trường hợp này: Monoprime
Nếu n được tính bằng tích của nhiều thừa số nguyên tố: so với trường hợp n có cùng độ lớn được tạo bằng tích của hai thừa số nguyên tố, trường hợp này có xác suất cao hơn bị phân tích thành công do độ lớn của các thừa số nguyên tố tỉ lệ nghịch với số lượng thừa số.
Challenge luyện tập cho trường hợp này: Manyprime
Do đó, khi xây dựng bộ khóa cho RSA, cần đảm bảo rằng n là tích của hai thừa số nguyên tố lớn. Mục đích chính là làm cho việc phân tích số n thành tích các thừa số nguyên tố trở nên khó khăn - một công việc bắt buộc phải thực hiện để tính ϕ(n).
3. Tấn Công Số N Với Cặp Số Nguyên Tố Giống Nhau
Một vấn đề tiếp theo từ phần trước là liệu có an toàn khi chúng ta chỉ chọn một số nguyên tố p và sử dụng nó hai lần để tạo ra n, tức là n là bình phương của một số nguyên tố lớn?
Khi áp dụng công thức tính hàm ϕ(n), chúng ta có ϕ(n) = p(p−1). Trong trường hợp này, bài toán trở thành việc khai căn bậc hai một số nguyên lớn, mà việc này dễ dàng hơn so với việc phân tích ra thừa số nguyên tố. Ví dụ, chúng ta có thể sử dụng hàm isqrt() trong module math để tìm căn bậc hai.
python
a = isqrt(1024)
print(a) # 32Độc giả có thể luyện tập với challenge Square Eyes.
4. Tấn Công Fermat
Khi hai số nguyên tố p và q được chọn có độ lớn gần nhau, tức là ∣p−q∣ khá nhỏ, chúng ta có thể áp dụng kỹ thuật tấn công Fermat để tìm ra chúng. Nếu chúng ta giả sử p > q, thì có:
- p + q = 2a
- p − q = 2b
Từ đó, ta viết lại n như sau:
n = p × q = (a+b)(a−b) = a2−b2 → b^2 = a^2 − n.
Bởi vì b = (p−q)/2 nhỏ, ta có thể coi:
a ≈ √n
- a ≥ √n
Từ đó, chỉ cần thử giá trị a bắt đầu từ ⌊√n⌋ và tăng dần cho đến khi a^2−n là số chính phương.
Cài đặt hàm tấn công Fermat trong Python như sau:
python
def fermat(n):
a = isqrt(n)
check = n - a * a
b = isqrt(check)
while b * b != check:
a = a + 1
check = a * a - n
b = isqrt(check)
p = a + b
q = a - b
return p, qĐiều kiện để phương pháp tấn công Fermat hoạt động hiệu quả là khi ∣p−q∣ < n^{1/4}. Bài tập dành cho độc giả: Tìm flag với bộ khóa công khai sau:
python
n = 966808932627497190635859236054960349099463975227350...
c = 168502910088858295634315070244377409556567637139736...
e = 65537V. Thuật Toán Pollard
1. Tấn Công Phân Tích Nhân Tử Theo Thuật Toán Pollard ρ−1
Trước tiên, cần hiểu khái niệm B-powersmooth. Xác định một số nguyên dương M, giả sử phân tích M ra tích các thừa số nguyên tố như sau:
M = p1^s1 × p2^s2 × ... × pk^sk,
trong đó pisi = max{p1^s1, p2^s2, ..., pk^sk}, ta gọi M là số pisi−powersmooth.
Ví dụ: Số 1302 = 2 × 3 × 7 × 31 là số 31−powersmooth, còn số 3696 = 24 × 3 × 7 × 11 là số 16−powersmooth.
Tính chất của khái niệm này cho thấy rằng:
M ∣ B!
Nếu M là số B−powersmooth, thì giai thừa B! sẽ là bội của M.
Để hiểu rõ ý tưởng của thuật toán Pollard's p - 1, chúng ta sẽ tìm một ước nguyên tố của n. Thay vì tìm trực tiếp, chúng ta sẽ tìm một số s không nguyên tố cùng nhau với n. Giả sử p là một ước nguyên tố của n, thì số s cần tìm là một bội của p.
Thực hiện theo các bước như đã trình bày, cuối cùng chúng ta có thể tính toán được ước nguyên tố của n thông qua việc tính toán số B. Cài đặt kỹ thuật tấn công Pollard's p - 1 bằng Python khá đơn giản như sau:
python
a = 2
B = 2
while True:
a = pow(a, B, N)
res = gcd(a - 1, N) # hàm gcd()
if res != 1 and res != N:
q = N // res
print("B = ", B)
print("p = ", res)
print("q = ", q)
break
B += 1Độ hiệu quả của phương pháp này càng cao khi p−1 hoặc q−1 có thể phân tích thành tích của nhiều thừa số nguyên tố.
Challenge dành cho bạn đọc:
python
N = 122454262037320...
c = 145742860621666...
e = 0x10001