I. Phương Trình ax + by = c
Phương trình dạng ax + by = c với a, b, c là các số nguyên cần tìm nghiệm nguyên (x, y). Đặt d = gcd(a, b) (ước chung lớn nhất), ta có thể chứng minh rằng tồn tại nghiệm nguyên cho phương trình ax + by = c nếu và chỉ nếu gcd(a, b) là ước của c. Bạn đọc nên tự suy luận và chứng minh điều này.
II. Thuật Toán Euclid Tìm ƯCLN
Chúng ta đã quen thuộc với bài toán tìm ước chung lớn nhất (ƯCLN) của hai số nguyên dương a và b bằng thuật toán Euclid, với tốc độ tính toán nhanh và hiệu quả. Ý tưởng của thuật toán như sau:
- Giả sử a > b. Chia a cho b được thương q và số dư r.
- Tiếp tục tìm ƯCLN của cặp số (b, r).
- Lặp lại cho đến khi số dư r = 0.
Dưới đây là đoạn mã minh họa bằng Python:
python
def euclidean_gcd(a, b):
while b != 0:
a, b = b, a % b
return aIII. Giải Thuật Euclid Mở Rộng và Phương Trình ax + by = c
Để giải phương trình Diophantine ax + by = c, chúng ta sử dụng giải thuật Euclid mở rộng kết hợp với thuật toán ƯCLN đã đề cập ở trên. Đặt d = gcd(a, b), trước tiên chúng ta tìm nghiệm (x0, y0) cho phương trình ax + by = d. Nếu phương trình này có nghiệm, ta có thể dễ dàng tìm nghiệm trong phương trình ax + by = c bằng cách tính (c * x0 / d, c * y0 / d).
Không mất tính tổng quát, giả sử a > b > 0. Đặt (a, b) = (r0, r1). Chia r0 cho r1 được thương q1 và dư r2. Tiếp tục chia r1 cho r2 tạo ra quy trình tương tự.
Trong từng bước, ta sẽ thu được dãy các số dư r, cùng với các giá trị (x, y) tương ứng. Cuối cùng, khi có nghiệm cho ax + by = d, ta có thể tính được nghiệm cho ax + by = c sâu hơn qua công thức truy hồi.
Dưới đây là mô tả thuật toán bằng mã giả:
plaintext
function gcd(a, b);
begin
while b ≠ 0 do
begin
r := a mod b; a := b; b := r;
end;
Result := a;
end;
function Extended_gcd(a, b);
begin
(xa, ya) := (1, 0);
(xb, yb) := (0, 1);
while b ≠ 0 do
begin
q := a div b;
r := a mod b; a := b; b := r;
(xr, yr) := (xa, ya) - q * (xb, yb);
(xa, ya) := (xb, yb);
(xb, yb) := (xr, yr);
end;
Result := (xa, ya);
end;IV. Ứng Dụng Trong Mật Mã RSA
1. Tìm Số Nghịch Đảo - Số Mũ Bí Mật d
Trong thuật toán RSA, sau khi chọn số mũ công khai e, chúng ta cần tìm số mũ bí mật d thỏa mãn phương trình: de ≡ 1 (mod ϕ(n)). Điều này dẫn đến phương trình dạng ax + by = c với c = 1. Để tìm được nghiệm, điều kiện cần là gcd(e, ϕ(n)) = 1.
2. Challenge CTF 1
David và George sử dụng RSA nhưng gửi cùng một thông điệp hai lần với các cặp e, d khác nhau. Từ đó, chúng ta có thể xây dựng hệ phương trình để giải mã thông điệp.
3. Challenge CTF 2 - sRSA (RaRCTF 2021)
Trong ví dụ này, e và n là hai số nguyên tố cùng nhau, từ đó ta có thể tìm được flag thông qua việc sử dụng thuật toán Euclid mở rộng và thực hiện các phép toán mod để lấy giá trị cuối cùng.
