[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 = ga mod p
    • A = 56 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 = gb mod p
    • B = 515 mod 23
    • B = 30,517,578,125 mod 23
    • B = 19
  4. Alice tính s = B a mod p
    • s = 196 mod 23
    • s = 47,045,881 mod 23
    • s = 2
  5. Bob tính s = A b mod p
    • s = 815 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ì (ga)b = (gb)a mod p. Lưu ý rằng chỉ có ab và gab = gba mod p là được giữ bí mật. Tất cả các giá trị khác như pgga mod p và gb 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 ab, 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 gpgb mod p và ga 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 xa=10 và xb=20. Bạn hãy:

a. tính giá trị công khai Ya của A và Yb của B

b. tính giá trị của khóa chia sẻ Zab 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 Ya là: Ya = gxa mod p = 1510 mod 89

i1248
15i mod 8915477378

Ya = [(152) mod 89 × (158) mod 89] mod 89= (47×78) mod 89 = 17

Gía trị công khai Yb là: Yb = gxb mod p = (1510)2 mod 89 = 172 mod 89 = 22

b.

Phía A: Zab = Ybxa mod p = 2210 mod 89 

i124816
22i mod 8922398642

Zab = 2210 mod 89 = [(228) mod 89×(222) mod 89 ] mod 89= (64×39) mod 89 = 4

Phía B: Zab = Yaxb mod p = 1720 mod 89

i124816
17i mod 89172239864

Zab = 1720 mod 89 = [(1716) mod 89×(174) mod 89 ] mod 89 = (64×39) mod 89 = 4

Published by Nhat Truong

Hi

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: