**Nội dung được xuất bản từ trang Substack của mình, mọi người nhớ bấm subscribe để không bỏ lỡ bài viết nào cả. **
Trong mã hoá đối xứng, điều đầu tiên 2 bên cần phải trao đổi khoá bí mật cho nhau, với điều kiện đây là kênh an toàn, không để lộ khoá. Cách đơn giản nhất là gặp nhau và trao đổi trực tiếp với nhau. Nhưng trên môi trường mạng, mọi thứ đều phải qua Internet, với cáp và các máy chủ, một kênh thực sự không an toàn, vậy làm thế nào để 2 bên có thể trao đổi khoá cho nhau mà không sợ bên thứ ba biết được
Đây chính là lúc trao đổi khoá bí mật trở thành một nhu cầu thiết yếu — và bạn sẽ bất ngờ khi thấy toán học, đặc biệt là logarit rời rạc, đứng sau trò chơi này.
Giả sử trong trường hợp sau
- Alice và Bob muốn lập kế hoạch tổ chức sinh nhật bất ngờ cho Charlie.
- Nhưng họ chỉ có thể trao đổi qua bưu điện — nơi mọi thư từ đều bị nhân viên tò mò đọc trộm.
- Làm sao họ có thể chia sẻ một “mật mã” bí mật, để từ đó mọi tin nhắn đều được mã hoá?
Câu trả lời chính là thuật toán Diffie–Hellman, một trong những ứng dụng nổi bật nhất của bài toán logarit rời rạc.
Định nghĩa
Cho một cyclic group G với một phép toán nhóm (thường là phép nhân hoặc phép cộng), một generator element α ∈ G , và một phần tử khác β ∈ G, bài toán logarit rời rạc tổng quát yêu cầu:
Vì α là một generator của group G nên x luôn luôn tồn tại. Số nguyên x này được gọi là logarit rời rạc của β theo cơ số α, và ta có thể viết một cách chính thức:
Ví dụ: Tìm số nguyên dương x sao cho: 5^x ≡ 41 mod 47
Thử 1 đoạn code bằng Python để tìm x bằng phương pháp vét cạn
alpha = 5
beta = 41
mod = 47 for x in range(1, mod): if pow(alpha, x, mod) == beta: print(f"Found: x = {x}") break
else: print("No solution found.") Found: x = 15
Tại sao bài toán logarit rời rạc lại là một chiều(one-way function) ?
Từ x, ta dễ dàng tính được β = α^x mod p
Nếu chỉ có β, α và p, rất khó để tìm được x sao cho α^x ≡ β mod p trong trường hợp p rất lớn. Hiện tại không có thuật toán nào tính theo thời gian đa thức có thể tim được x
Trao đổi khóa Diffie-Hellman (Diffie–Hellman key exchange)
Là một giao thức cho phép hai bên (Alice và Bob) tạo ra chung một khóa bí mật, mà không cần gửi khóa đó qua mạng — ngay cả khi kẻ tấn công thấy toàn bộ thông tin trao đổi, hắn cũng không thể biết được khoá bí mật giữa Alice và Bob.
Đầu tiên 2 bên phải setup public parameters p and g. Đây là public parameter nên bất kỳ ai cũng có thể biết được thông tin này.
Thiết lập ban đầu
- Chọn số nguyên tô p
- Chọn sô g ∈{2,3,...,p−2}. - Công khai p và g
Sau đó mỗi bên chọn khóa bí mật. Note: a, b được giữ bí mật với Alice và Bob. Họ không cần chia sẻ a,b cho nhau.
- Alice chọn a và tính A = g^a mod p
- Bob chọn b và tính B = g^b mod p Tiếp tục gửi công khai A và B cho nhau.
Tính khóa chung
- Alice tính: K = B^a mod p = (g^b)^a mod p = g^(ab) mod p
- Bob tính: K = A^b mod p = (g^a)^b mod p = g^(ab) mod p
Sau khi tính khoá chung, 2 bên có thể dùng nó để làm key cho các thuật toán đối xứng.
Ví dụ: ` Tham số công khai: p = 23 g = 5
Alice chọn a = 4 → A = 5^4 mod 23 = 4 Bob chọn b = 3 → B = 5^3 mod 23 = 10
Trao đổi: Alice gửi A = 4 cho Bob Bob gửi B = 10 cho Alice
Tính khóa chung: Alice: K = 10^4 mod 23 = 18 Bob: K = 4^3 mod 23 = 18
=> Cả hai đều có khóa bí mật chung K = 18
Một người thứ 3 tấn công họ sẽ thấy gì?
- Thấy g = 5, p = 23, A = 4, B = 10
- Nhưng không thể tìm được a hoặc b nếu không giải được vì đây là bài toán logarit rời rạc 5^a ≡ 4 mod 23 5^b ≡ 10 mod 23
Một hình vẽ mô hình hoá quá trình chia sẻ khoá bí mật giữa Alice và Bob. Quá trình bắt đầu khi hai bên, Alice và Bob, cùng thống nhất công khai một màu gốc, không cần giữ bí mật. Trong ví dụ này, màu được chọn là vàng.
Sau đó, mỗi người tự chọn một màu bí mật mà chỉ mình họ biết — ở đây là đỏ (Alice) và xanh cyan (Bob).
Điểm then chốt của quá trình là:
Alice và Bob trộn màu bí mật của mình với màu chung (màu vàng), tạo ra lần lượt các màu cam-nâu và xanh nhạt,
Sau đó, họ trao đổi công khai hai màu đã trộn này.
Cuối cùng,
Mỗi người trộn màu đã nhận được từ đối phương với màu bí mật ban đầu của mình.
Kết quả là cả hai đều thu được một màu cuối giống hệt nhau — trong ví dụ này là vàng-nâu.
Kết luận
Qua các ví dụ đơn giản trên, chúng ta đã thấy cách Diffie–Hellman cho phép hai bên tạo ra một khóa bí mật chung, dù chỉ trao đổi thông tin công khai qua một kênh không an toàn.
Sức mạnh của phương pháp này đến từ bài toán logarit rời rạc, một bài toán "một chiều": dễ tính theo chiều xuôi (nhân mũ), nhưng cực kỳ khó đảo ngược nếu không biết khóa riêng.
👉 Đây là nền tảng cho rất nhiều giao thức bảo mật hiện đại như TLS (HTTPS), VPN, SSH, và hơn thế nữa.
🧠 Nếu bạn hiểu được Diffie–Hellman, bạn đã chạm đến trái tim của mật mã học hiện đại. Bạn muốn bước tiếp đến chữ ký số hay mã hóa ElGamal? Hẹn gặp ở phần tiếp theo!
Hãy subscribe trang Substack của mình để không bỏ lỡ bài viết nào cả: https://cryptography101.substack.com/p/bai-toan-logarit-roi-rac-phan-2-khi