Trao đổi khóa Diffie-Hellman
Làm sao hai người chưa từng gặp nhau có thể thống nhất một khóa bí mật trong khi có người nghe từng lời họ nói? Năm 1976, Whitfield Diffie và Martin Hellman đã tìm ra câu trả lời mà ngày nay bảo vệ gần như mọi kết nối an toàn trên internet. Hãy theo Alice và Bob qua năm bước, một lần dưới dạng trộn sơn và một lần với những con số thật, rồi để kẻ nghe lén Eve tấn công: với số nhỏ, cô ấy thắng trong chớp mắt; với kích thước dùng trong thực tế, cô ấy sẽ cần lâu hơn cả tuổi của vũ trụ. Nhấn Bước tiếp để theo dõi Alice và Bob thống nhất một bí mật trong khi Eve đọc mọi thứ họ gửi; Quay lại lùi một bước. Mỗi giá trị được hiển thị vừa như một màu sơn vừa như một con số. Các giá trị bị khóa không bao giờ rời khỏi chủ của chúng. Hãy chọn một số nguyên tố lớn hơn hoặc các bí mật khác ở bên phải, hoặc nhấn Bí mật mới. Ở bước cuối, Để Eve tấn công khiến cô ấy thử mọi số mũ cho đến khi có một số khớp: dễ với các số nguyên tố nhỏ, vô vọng với các số nguyên tố thực tế.
Cách nó hoạt động
- Nhấn Bước tiếp để theo dõi quá trình trao đổi: thỏa thuận công khai, các bí mật, các thông điệp và kết quả chung.
- Quan sát mỗi giá trị dưới dạng màu sơn và dưới dạng con số, và xem giá trị nào vẫn riêng tư, giá trị nào Eve đọc được.
- Ở bước cuối, nhấn Để Eve tấn công, rồi chọn một số nguyên tố lớn hơn và xem cơ hội của cô ấy biến mất nhanh thế nào.
Cách phép trao đổi hoạt động
Trước tiên Alice và Bob thống nhất công khai một số nguyên tố p và một số g. Sau đó mỗi người chọn một số bí mật, a cho Alice và b cho Bob, và giữ riêng cho mình. Alice gửi cho Bob A = gᵃ mod p, còn Bob gửi cho Alice B = gᵇ mod p. Cuối cùng Alice tính Bᵃ mod p và Bob tính Aᵇ mod p. Cả hai kết quả đều bằng g mũ a·b mod p, nên giờ đây họ cùng có một con số chưa bao giờ đi qua đường truyền. Eve, người đã thấy p, g, A và B, không có lối tắt nào như vậy.
Vì sao Eve bế tắc
Tính gᵃ mod p rất nhanh, kể cả với những số có hàng trăm chữ số, nhờ phép bình phương liên tiếp. Đi ngược lại, tức là tìm số mũ a từ kết quả, là bài toán logarit rời rạc, và chưa có phương pháp nhanh nào được biết đến cho các số nguyên tố được chọn tốt. Với các số nguyên tố nhỏ trong bản demo này, Eve chỉ cần thử mọi số mũ; ứng dụng đếm số lần đoán của cô ấy và ước tính một cuộc tìm kiếm toàn bộ sẽ mất bao lâu. Mỗi bit thêm vào số nguyên tố làm công việc tăng gấp đôi, nên các số nguyên tố 2048 bit dùng trên internet đẩy việc tìm kiếm vét cạn ra xa ngoài tầm với. Phiên bản bằng sơn thể hiện cùng một ý tưởng: trộn màu thì dễ, nhưng tách một hỗn hợp trở lại thành các màu ban đầu thì gần như không thể.
Câu hỏi thường gặp
Vì sao phép so sánh với sơn lại hợp lý?
Trộn sơn thì dễ và không thể đảo ngược, giống như nâng g lên một lũy thừa mod p thì dễ làm mà khó đảo ngược. Alice và Bob mỗi người thêm màu bí mật của mình vào một màu chung rồi đổi hỗn hợp cho nhau; sau đó mỗi người thêm màu bí mật của mình vào hỗn hợp nhận được. Cả hai đều có màu chung cộng với cả hai bí mật, còn Eve chỉ thấy hai hỗn hợp hai màu và không thể tách chúng ra. Ở đây sơn được trộn theo phần bằng nhau, nên thứ tự không quan trọng, giống như (gᵃ)ᵇ = (gᵇ)ᵃ.
g là gì và vì sao nó phải là căn nguyên thủy?
g là phần tử sinh: các lũy thừa g¹, g², …, g^(p−1) mod p của nó đi qua mọi số từ 1 đến p − 1. Nhờ vậy các giá trị công khai trải đều trên mọi khả năng, nên Eve biết được ít nhất có thể từ chúng. Ứng dụng chọn số nhỏ nhất như vậy cho mỗi số nguyên tố, ví dụ g = 5 với p = 23.
Diffie-Hellman có mã hóa tin nhắn của tôi không?
Không. Nó chỉ thống nhất một bí mật chung. Bí mật đó sau đó được dùng làm khóa cho một thuật toán mã hóa đối xứng nhanh như AES, thứ mã hóa dữ liệu thực sự. Mọi kết nối HTTPS đều hoạt động như vậy: một phép trao đổi khóa, thường dùng đường cong elliptic, rồi đến mã hóa đối xứng.
Eve có thể giả làm Bob không?
Nếu chỉ dùng riêng nó, thì có. Kẻ tấn công xen giữa có thể thực hiện một phép trao đổi với Alice và một phép khác với Bob rồi chuyển tiếp mọi thứ. Các giao thức thực tế ngăn điều này bằng cách yêu cầu máy chủ chứng minh danh tính bằng chữ ký số và chứng chỉ, nhờ đó phép trao đổi được xác thực.
Có gì được gửi lên máy chủ không?
Không. Mọi con số, việc trộn sơn và cuộc tấn công của Eve đều được tính trong trình duyệt của bạn, và các thiết lập của bạn được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa