Diffie-Hellman Key Exchange - Thuật toán trao đổi khóa
Trong thực tế, khi trao đổi thông tin trên internet, chúng ta luôn phải bảo mật thông tin để tránh bị nghe lén hoặc nhìn trộm bằng cách mã hóa thông tin truyền tải trước khi gửi. Bên đầu nhận sẽ giải mã thông tin và đọc lại bản gốc. Nhưng một khi đầu gửi mã hóa thì đầu nhận phải có chìa khóa để giải mã. Giả sử như đầu nhận và đầu gửi không có cách nào để gặp trực tiếp nhau và thiết lập trao đổi khóa. Như vậy, làm cách nào họ có thể vẫn trao đổi chìa khóa thông qua internet?
Xin mượn một bức hình từ wiki để dễ liên tưởng về giải thuật này
Alice và Bob cùng công khai đồng thuật dùng màu vàng là màu chung. Alice có màu bí mật là màu đỏ, Bob có màu bí mật là màu xanh lá cây. Cả hai tự pha chế màu bí mật của mình bằng cách lấy màu dùng chung pha với màu bí mật của mình và gửi kết quả cho nhau. Alice gửi màu cam cho Bob và Bob gửi màu xanh da trời cho Alice. Sau khi nhận được màu của nhau, tiếp tục dùng màu bí mật của mình để pha chung với màu nhận được. Cuối cùng, cả Alice vào Bob đều có màu bí mật đồng thuận là màu nâu\=vàng+đỏ+xanh lá cây. Với giả định là màu đã pha trộn sẽ không thể bị tách ra thành màu thành phần, rõ ràng, kẻ nghe lén chỉ có thể biết màu vàng (công khai), màu cam (khi Alice gửi cho Bob) và màu xanh dương (khi Bob gửi Alice). Kẻ tấn công không thể biết các màu bí mật là gì (kể cả đối phương cũng không biết màu bí mật riêng của nhau).
Dựa vào mô tả trên, Whitfield Diffie và Martin Hellman đưa ra thuật toán trao đổi khóa vào năm 1976. Thuật này trở thành đồ được áp dụng trên nhiều cấu trúc đại số khác nhau.
Diffie-Hellman trên trường số nguyên tố
Thỏa thuận chung:
Trường số nguyên tố \(\mathbb F_p\)
Phần tử sinh generator \(g\)
Quá trình trao đổi khóa giữa Alice và Bob:
Alice chọn số ngẫu nhiên bí mật \(1 \le a \le p-1\), tính \(x = g^a \mod p\)
Bobchọn số ngẫu nhiên bí mật \(1 \le b \le p-1\), tính \(y=g^b \mod p\)
Alice gửi \(x\) cho Bob
Bob gửi \(y\) cho Alice
Alice nhận được \(y\), tính bí mật chung \(k = y^a=(g^b)^a = g^{ab} \quad (\mod p)\)
Bob nhận được \(x\), tính bí mật chung \(k = x^b=(g^a)^b = g^{ab} \quad (\mod p)\)
Diffie-Hellman trên đường cong elliptic
Elliptic Curve Diffie-Hellman (ECDH) là một phiên bản của giao thức Diffie-Hellman (DH) truyền thống, sử dụng toán học trên đường cong elliptic (Elliptic Curve Cryptography - ECC) thay vì trên trường số nguyên tố lớn vì một số lợi ích:
Độ an toàn cao hơn: Với cùng độ dài khóa, ECDH cung cấp độ an toàn cao hơn so với Diffie-Hellman truyền thống.
Hiệu suất tốt hơn: Yêu cầu ít tài nguyên tính toán hơn, giúp giảm tải cho CPU và tiết kiệm năng lượng.
Khóa ngắn hơn: ECDH có thể đạt được độ an toàn tương đương với khóa dài hơn trong Diffie-Hellman
Thỏa thuận chung:
Phương trình đường cong elliptic
Điểm cơ sở \(G\)
Số nguyên tố \(p\) là bậc của trường hữu hạn
Quá trình trao đổi khóa giữa Alice và Bob:
Alice chọn số ngẫu nhiên bí mật \(1 \le a \le p-1\), tính điểm \(A = aG\)
Bob chọn số ngẫu nhiên bí mật \(1 \le b \le p-1\), tính điểm \(B=bG\)
Alice gửi \(A\) cho Bob
Bob gửi \(B\) cho Alice
Alice nhận được \(B\), tính bí mật chung \(K = aB=a(bG)=abG\)
Bob nhận được A, tính bí mật chung \(K=bA=b(aG)=abG\)