Giải thích trao đổi khóa Diffie-Hellman
Suốt hàng nghìn năm, gửi một thông điệp bí mật có nghĩa là trước hết phải chia sẻ một khóa bí mật trực tiếp hoặc qua người đưa tin. Năm 1976, hai nhà nghiên cứu ở Stanford đã chỉ ra rằng hai bên có thể tạo ra một khóa chung từ hư không, bằng cách trao đổi thông điệp ngay trước mắt bất kỳ ai. Ý tưởng này mở ra kỷ nguyên mật mã khóa công khai và vẫn đang hoạt động mỗi khi trình duyệt hiện biểu tượng ổ khóa.
Bài toán phân phối khóa
Một thuật toán mã hóa như AES chỉ an toàn ngang với khóa của nó, và cả hai bên cần cùng một khóa. Trước năm 1976, khóa phải được chuyển giao bí mật: bằng túi ngoại giao, người đưa tin tin cậy hoặc sổ mã in sẵn từ trước. Với hai người lạ muốn trò chuyện an toàn ngay lúc này, chẳng hạn một cửa hàng và một khách hàng trên internet, điều đó là không thể. Bài báo New Directions in Cryptography của Whitfield Diffie và Martin Hellman đã giải quyết vấn đề bằng một phương pháp hoàn toàn không cần bí mật nào từ trước.
Số học trên mặt đồng hồ
Phép trao đổi dùng số học đồng dư: các phép tính trên một chiếc đồng hồ có p giờ, trong đó p là một số nguyên tố lớn. Lũy thừa trên chiếc đồng hồ này hoạt động theo một cách đáng chú ý. Nếu g là căn nguyên thủy, các số g, g², g³, … mod p nhảy khắp nơi và ghé qua mọi giờ từ 1 đến p − 1 trước khi lặp lại, theo một thứ tự trông như ngẫu nhiên. Tính gᵃ mod p rất nhanh, chỉ cần số phép nhân xấp xỉ số chữ số nhị phân của a. Đảo ngược nó thì không.
Phép trao đổi từng bước
Alice và Bob thống nhất công khai p và g. Alice chọn một bí mật a và gửi A = gᵃ mod p; Bob chọn một bí mật b và gửi B = gᵇ mod p. Alice tính Bᵃ = (gᵇ)ᵃ còn Bob tính Aᵇ = (gᵃ)ᵇ, đều theo mod p. Vì thứ tự các số mũ không quan trọng, cả hai đều được g^(ab) mod p. Với ví dụ nhỏ kinh điển p = 23, g = 5, a = 6 và b = 15, Alice gửi 8, Bob gửi 19, và cả hai cùng đến được bí mật chung 2.
Bài toán logarit rời rạc
Eve thấy p, g, A và B. Nếu tìm được a từ A = gᵃ mod p, cô ấy có thể tính bí mật giống hệt Alice. Đây là bài toán logarit rời rạc. Các thuật toán cổ điển tốt nhất đã biết, chẳng hạn sàng trường số, nhanh hơn nhiều so với thử mọi số mũ nhưng vẫn cần thời gian tăng nhanh hơn mọi lũy thừa của số chữ số. Với số nguyên tố 2048 bit, bài toán nằm ngoài tầm với của bất kỳ máy tính nào hiện có. Liệu có cách nào nhanh hơn hay không vẫn chưa ai biết, và độ an toàn của phép trao đổi dựa trên niềm tin đó.
Kẻ đứng giữa
Diffie-Hellman bảo vệ trước kẻ nghe lén nhưng không bảo vệ trước kẻ mạo danh. Mallory, đứng giữa Alice và Bob, có thể thực hiện một phép trao đổi riêng với từng người và chuyển tiếp các thông điệp, đọc được mọi thứ. Cách phòng vệ là xác thực: trong HTTPS, máy chủ ký phần của mình trong phép trao đổi bằng một khóa được một tổ chức đáng tin cậy chứng nhận, nhờ đó trình duyệt biết mình thực sự đang giao tiếp với đúng trang web. Trao đổi khóa và chữ ký số luôn đi cùng nhau.
Ai đã phát minh ra nó?
Diffie và Hellman công bố năm 1976, dựa trên các ý tưởng của Ralph Merkle, người mà sau này Hellman đề nghị cũng được ghi công. Năm 1997, cơ quan tình báo GCHQ của Anh tiết lộ rằng các nhà toán học của họ đã đến đích trước: James Ellis có ý tưởng về mật mã khóa công khai năm 1970, Clifford Cocks tìm ra một hệ thống giống RSA năm 1973, và Malcolm Williamson khám phá ra chính phép trao đổi khóa này năm 1974, tất cả đều được giữ bí mật trong hơn hai mươi năm.
Diffie-Hellman ngày nay
Các kết nối hiện đại chủ yếu dùng Diffie-Hellman trên đường cong elliptic, mang lại cùng độ an toàn với những con số ngắn hơn nhiều, ví dụ đường cong X25519 trong TLS 1.3, Signal và WhatsApp. Dùng một cặp bí mật mới cho mỗi kết nối mang lại bí mật chuyển tiếp: ngay cả khi khóa dài hạn của máy chủ sau này bị đánh cắp, các cuộc trò chuyện trước đó vẫn an toàn. Tham số yếu vẫn là mối nguy, như cuộc tấn công Logjam năm 2015 đã cho thấy với các số nguyên tố 512 bit cũ, và một máy tính lượng tử lớn chạy thuật toán Shor sẽ phá được cả Diffie-Hellman cổ điển lẫn trên đường cong elliptic, đó là lý do các phương pháp trao đổi khóa hậu lượng tử hiện đang được triển khai song song với chúng.
Tự khám phá
Hãy mở mô phỏng Diffie-Hellman để theo dõi năm bước trên một bảng cho thấy Alice, kênh công khai và Bob biết gì, dưới dạng sơn và dưới dạng số. Chọn số nguyên tố từ 23 đến 2.147.483.647, tự đặt các bí mật và để Eve tấn công bằng cách thử mọi số mũ: xem cô ấy thành công ngay lập tức với các số nguyên tố nhỏ và thấy thời gian tìm kiếm ước tính tăng lên thế nào khi số nguyên tố dài hơn.
Câu hỏi thường gặp
Diffie-Hellman có giống RSA không?
Không, dù cả hai đều là phương pháp khóa công khai từ những năm 1970. RSA, công bố năm 1977, có thể mã hóa và ký bằng một khóa công khai và một khóa riêng, và dựa trên độ khó của việc phân tích các số lớn ra thừa số. Diffie-Hellman chỉ thống nhất một bí mật chung và dựa trên bài toán logarit rời rạc.
Trong thực tế các con số lớn đến mức nào?
Diffie-Hellman cổ điển dùng số nguyên tố ít nhất 2048 bit, khoảng 617 chữ số thập phân, và thường là 3072 hoặc 4096 bit. Các phiên bản trên đường cong elliptic dùng khóa khoảng 256 bit cho độ an toàn tương đương.
Vì sao mỗi bit thêm vào làm công việc của Eve tăng gấp đôi?
Một số nguyên tố dài hơn một bit thì lớn gấp khoảng hai lần, nên số số mũ cần thử cũng nhiều gấp khoảng hai lần. Các cuộc tấn công thực tế khéo léo hơn việc thử mọi số mũ, nhưng chi phí của chúng vẫn tăng rất nhanh theo kích thước của số nguyên tố.
Vì sao Alice và Bob cần một số nguyên tố?
Với mô-đun nguyên tố, mọi số từ 1 đến p − 1 đều có nghịch đảo và căn nguyên thủy tồn tại, nên các lũy thừa của g phủ hết mọi khả năng. Người ta thường chọn số nguyên tố an toàn, tức là số mà (p − 1)/2 cũng là số nguyên tố, để loại bỏ các lối tắt lợi dụng ước nhỏ của p − 1.
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.
Mở mô phỏng Diffie-Hellman