[Cryptography Basics] Tìm hiểu về Diffie Hellman

Trao đổi khóa Diffie–Hellman (D-H) là một phương pháp trao đổi khóa được phát minh sớm nhất trong mật mã học. Phương pháp trao đổi khóa Diffie–Hellman cho phép hai bên (người, thực thể giao tiếp) thiết lập một khóa bí mật chung để mã hóa dữ liệu sử dụng trên kênh truyền thông không an toàn mà không cần có sự thỏa thuận trước về khóa bí mật giữa hai bên. Khóa bí mật tạo ra sẽ được sử dụng để mã hóa dữ liệu với phương pháp mã hóa khóa đối xứng.

Ý tưởng cơ bản

Điểm chủ chốt của ý tưởng này là Alice và Bob trao đổi màu sơn bí mật thông qua hỗn hợp sơn.

• Đầu tiên Alice và Bob trộn màu đã biết chung (màu vàng) với màu bí mật riêng của mỗi người.
• Sau đó, mỗi người chuyển hỗn hợp của mình tới người kia thông qua một kênh vận chuyển công cộng.
• Khi nhận được hỗn hợp của người kia, mỗi người sẽ trộn thêm với màu bí mật của riêng mình và nhận được hỗn hợp cuối cùng.

Hỗn hợp sơn cuối cùng là hoàn toàn giống nhau cho cả hai người và chỉ có riêng hai người biết. Mấu chốt ở đây là đối với một người ngoài sẽ rất khó (về mặt tính toán) cho họ để tìm ra được bí mật chung của hai người (nghĩa là hỗn hợp cuối cùng). Alice và Bob sẽ sử dụng bí mật chung này để mã hóa và giải mã dữ liệu truyền trên kênh công cộng. Lưu ý, màu sơn đầu tiên (màu vàng) có thể tùy ý lựa chọn, nhưng được thỏa thuận trước giữa Alice và Bob. Màu sơn này cũng có thể được giả sử là không bí mật đối với người thứ ba mà không làm lộ bí mật chung cuối cùng của Alice và Bob.

Giao thức được diễn giải dưới dạng toán học như sau:

Giao thức sử dụng nhóm nhân số nguyên modulo p, trong đó p số nguyên tố, và g là căn nguyên thủy mod p. Trong ví dụ dưới đây, giá trị không bí mật được viết bằng chữ nghiêng, và giá trị bí mật viết bằng chữ đậm:

1. Alice và Bob thỏa thuận sử dụng chung một số nguyên tố p=23 và căn nguyên thủy g=5.
2. Alice chọn một số nguyên bí mật a=6, và gửi cho Bob giá trị A = g^a mod p
   • A = 5⁶ mod 23
   • A = 15,625 mod 23
   • A = 8
3. Bob chọn một số nguyên bí mật b=15, và gửi cho Alice giá trị B = g^b mod p
   • B = 5¹⁵ mod 23
   • B = 30,517,578,125 mod 23
   • B = 19
4. Alice tính s = B ^a mod p
   • s = 19⁶ mod 23
   • s = 47,045,881 mod 23
   • s = 2
5. Bob tính s = A ^b mod p
   • s = 8¹⁵ mod 23
   • s = 35,184,372,088,832 mod 23
   • s = 2
6. Như vậy Alice và Bob cùng chia sẻ bí mật chung là số 2 vì 6*15 cũng bằng 15*6.

Cả Alice và Bob đều có được giá trị chung cuối cùng vì (g^a)^b = (g^b)^a mod p. Lưu ý rằng chỉ có a, b và g^ab = g^ba mod p là được giữ bí mật. Tất cả các giá trị khác như p, g, g^a mod p và g^b mod p được truyền công khai. Sau khi Alice và Bob tính được bí mật chung, cả hai có thể sử dụng nó làm khóa mã hóa chung chỉ có hai người biết để gửi dữ liệu trên kênh truyền thông mở.

Trong thực tế để giao thức được an toàn, người ta sử dụng giá trị lớn hơn nhiều cho a, b, và p, vì trong ví dụ trên chỉ có tổng cộng 23 kết quả khác nhau cho n mod 23 (do đó kẻ tấn công chỉ cần thử hết 23 trường hợp là tìm ra khóa bí mật). Nếu số nguyên tố p có ít nhất 300 chữ số, còn a và b có ít nhất 100 chữ số, thì ngay cả những máy tính hiện đại nhất hiện nay cũng không thể tìm được a nếu chỉ biết g, p, g^b mod p và g^a mod p. Bài toán này, gọi là bài toán Lôgarit rời rạc, hiện chưa có cách giải hiệu quả bằng máy tính (vì vậy được sử dụng để tạo khóa công khai).

Lưu ý, g không cần thiết là một căn nguyên thủy có giá trị lớn. Trong thực tế người ta hay sử dụng các giá trị 2, 3 hoặc 5.

Giải bài tập

Giả sử A và B trao đổi khóa bằng giao thức Diffie-Hellman sử dụng bộ tham số p=89, g=15; trong quá trình đó A và B lần lượt sinh được các giá trị ngẫu nhiên x_a=10 và x_b=20. Bạn hãy:

a. tính giá trị công khai Y_a của A và Y^b của B

b. tính giá trị của khóa chia sẻ Z_ab giữa A và B

Lưu ý: mọi người cần ghi nhớ tính chất phân phối của Modulo là [(a mod n) + (b mod n)] mod n.

Giải:

a.

Giá trị công khai Y_a là: Y_a = g^xa mod p = 15¹⁰ mod 89

i	1	2	4	8
15i mod 89	15	47	73	78

Y_a = [(15²) mod 89 × (15⁸) mod 89] mod 89= (47×78) mod 89 = 17

Gía trị công khai Y_b là: Y_b = g^xb mod p = (15¹⁰)² mod 89 = 17² mod 89 = 22

b.

Phía A: Z_ab = Y_b^xa mod p = 22¹⁰ mod 89 

i	1	2	4	8	16
22i mod 89	22	39	8	64	2

Z_ab = 22¹⁰ mod 89 = [(22⁸) mod 89×(22²) mod 89 ] mod 89= (64×39) mod 89 = 4

Phía B: Z_ab = Y_a^xb mod p = 17²⁰ mod 89

i	1	2	4	8	16
17i mod 89	17	22	39	8	64

Z_ab = 17²⁰ mod 89 = [(17¹⁶) mod 89×(17⁴) mod 89 ] mod 89 = (64×39) mod 89 = 4