+1

[Cryptography p9] Trao đổi khóa an toàn với Diffie-Hellman

Bài viết được lấy từ https://truongphuoc.wordpress.com/2024/07/28/blockchain-20-1-trao-doi-khoa-an-toan-voi-diffie-hellman/

Lời dẫn

Xin chào các bạn, trong bài viết trước mình đã hoàn thiện về cả toán học lẫn thực tế cách sử dụng RSA, ECC và ECDSA. Bẵng một thời gian xem lại, cảm thấy thật tiếc khi không tìm hiểu thêm về Diffie-Hellman (DH).

Trong bài viết này chúng ta sẽ cùng tìm hiểu về thuật toán DH để xem cách trao đổi khóa an toàn nhé.

Công thức số mũ

Khi chúng ta đi học, chắc hẳn phải học số mũ, trong đó có công thức nhân số mũ như sau:

(ab)c=abc(a^b)^c = a^{b*c}

Ví dụ

(23)4=234=4096(2^3)^4 = 2^{3*4} = 4096

Xong, thế là hết phần này, quá đơn giản phải không nào

Tính chất giao hoán trong phép nhân

Phép nhân có tính chất giao hoán như sau

ab=baa*b = b*a

Ví dụ: 23=32=62*3 = 3*2 = 6

Xong, cực kỳ đơn giản. Kết hợp với công thức số mũ ta có như sau:

(ab)c=abc=(ac)b=acb(a^b)^c = a^{b*c} = (a^c)^b = a^{c*b}

Kết hợp với module

Trong số học module công thức trên được viết lại như sau như sau:

(ab)c=abc=(ac)b=acb  (mod  𝑚)(a^b)^c = a^{b*c} = (a^c)^b = a^{c*b} \;(mod\; 𝑚)

Trao đổi khóa Diffie-Hellman

Thuật toán

Cho một số nguyên tố p, căn nguyên thủy g. An và Bình muốn chia sẻ một khóa bí mật chung nào đó, hai người sẽ làm như sau:

  1. Chọn khóa
    • An chọn một khóa bí mật của mình là a
    • Bình chọn một khóa bí mật của mình là b
  2. Trao đổi khóa:
    • An tính A=ga  mod  pA = g^a\; mod \;p gửi cho Bình
    • Bình tính B=gb  mod  pB = g^b\; mod \;p gửi cho An.
  3. Tính toán khóa
    • An tính s1=Ba  mod  p=(gb)a  mod  ps_1 = B^a\; mod\; p = (g^b)^a \;mod\; p
    • Bình tính s2=Ab  mod  p=(ga)b  mod  ps_2 = A^b\; mod\; p = (g^a)^b\; mod\; p
  4. Như đã nêu ở trên thì (gb)a=(ga)b  (mod  p)(g^b)^a = (g^a)^b \;(mod \; p) suy ra s1=s2=ss_1 = s_2 = s. Đo đó An và Bình cùng chia sẻ một bí mật chung là s.
  5. Do bài toán khó logarit rời rạc, nên người thứ ba là Công rất khó tìm ra
    • aa khi biết g,p,ga  mod  pg, p, g^a\; mod \;p
    • bb khi biết g,p,gb  modp  g, p, g^b\; mod p\;
    • a,ba,b khi biết g,p,(ga)b  mod  pg, p, (g^a)^b\; mod \;p
    • b,ab,a khi biết g,p,(gb)a  mod  pg, p, (g^b)^a\; mod\; p

Sau khi đã chia sẻ khóa bí mật chung, An và Bình có thể sử dụng nó để làm key cho một thuật toán mã hóa, ví dụ AES.

Nếu bạn chịu khó đọc bài những kiến thức cơ bản cần thiết trong mật mã học thì phỏng cũng không khó lắm phải không. Nếu chưa thì các bạn tìm lại đọc nha. Tiếp theo hãy cùng đến một ví dụ cụ thể nào.

Ví dụ

Chọn p=23p = 23 là một số nguyên tố, g=5g = 5 là căn nguyên thủy của 2323. Ta tính toán như sau

  1. Chọn khóa
    • An chọn khóa bí mật là 66
    • Bình chọn khóa bí mật là 1515
  2. Trao đổi khóa
    • An tính 56  mod  23=15625   mod   23=85^6\; mod\; 23 = 15625 \;mod\; 23 = 8 gửi cho Bình
    • Bình tính 515  mod  23=30517578125   mod   23=195^{15}\; mod\; 23 = 30517578125\; mod\; 23 = 19 gửi cho An
  3. Tính toán khóa
    • An tính 196  mod  23=47045881   mod   23=219^6\; mod \;23 = 47045881\; mod\; 23 = 2
    • Bình tính 815  mod  23=35184372088832   mod   23=28^{15}\; mod\; 23 = 35184372088832\; mod\; 23 = 2

Thế là An và Bình đã có chung một khóa bí mật là 2. Họ có thể sử dụng khóa này để làm khóa cho một thuật toán đối xứng nào đó, ví dụ AES. Hay họ có thể tính toán khóa cho AES dựa vào số này.

Ví dụ số 22 quá nhỏ, có thể thể thống nhất số này nhân với 12345=>(212345=24690)12345 => (2*12345=24690) để được khóa lớn hơn.

Ưu - nhược điểm của Diffie-Hellman

Ưu:

  • Nhanh: với p và g biết trước, chỉ cần lựa chọn số ngẫu nhiên a và b thôi.
  • Bảo mật cao: dựa vào bài toán khó logarit rời rạc.

Nhược:

  • Có thể bị tấn công man-in-the-middle.

Kết luận

Sử dụng Diffie-Hellman để trao đổi khóa an toàn rất phổ biến trong cuộc sống hiện nay nhờ sự nhanh, bảo mật của nó.

Link bài viết gốc https://truongphuoc.wordpress.com/2024/07/28/blockchain-20-1-trao-doi-khoa-an-toan-voi-diffie-hellman/


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí