Hệ mật đường cong Elliptic (Elliptic Curve Cryptography)

Mật mã đường cong elliptic (Elliptic Curve Cryptography) là một kỹ thuật mã hóa khóa công khai dựa trên lý thuyết đường cong elliptic có thể được sử dụng để tạo các khóa mật mã nhanh hơn, nhỏ hơn và hiệu quả hơn. ECC tạo khóa thông qua các thuộc tính của phương trình đường cong elliptic thay vì phương pháp tạo truyền thống như là tích của các số nguyên tố rất lớn. Đặc biệt ECC được ứng dụng rất nhiều trong Blockchain. Để hiểu về khái niệm đường cong elliptic, các bạn đọc bài viết tại Khái niệm đường cong Eliptic

1.  Trao đổi khóa EC Diffie-Hellman

Trước tiên ta chọn một  số  nguyên  q  lớn, với  q  là số  nguyên tố  (nếu sử  dụng đường cong Elliptic Zp) hoặc q có dạng 2^m(nếu chọn đường cong GF(2^m)), và chọn 2 tham số a, b tương ứng để tạo thành nhóm E_q(a,b). Ta gọi G là điểm cơ sở của nhóm nếu tồn tại một số nguyên n sao cho nG=0. Số nguyên n nhỏ nhất như vậy được gọi là hạng của G.

Trong trao đổi khóa EC Diffie-Hellman, ta chọn một điểm G  có hạng  n  lớn, và giao thức trao đổi khóa giữa Alice và Bob tiến hành như sau:

1)  Alice chọn một số n_A < n và giữ  bí mật số n_A này. Sau đó trong E_q(a,b) Alice

Tính P_A= n_AG và gửi cho Bob.

2)  Tương tự Bob chọn một số bí mật n_B, tính  P_B và gửi P_B  cho Alice.

3)  Alice tạo khóa phiên bí mật là  K=   n_A P_B = n_A n_BG

4)  Bob  tạo  khóa  phiên  bí  mật  là  K=   n_B P_A = n_A n_BG (nhóm  Abel  có

tính giao hoán) giống với khóa của Alice.

Trudy có thể chặn được P_A và P_B, tuy nhiên chỉ có thể tính được điều này là bất khả thi như ta đã thấy ở phần trên.

Chú ý: khóa phiên K là một điểm trong đường cong Elliptic, để sử dụng khóa này cho mã hóa đối xứng như DES hay AES, ta cần chuyển K về dạng số thường.

2. Mã hóa và giải mã EC

Tương tự  như vấn đề  trao đổi khóa, trong vấn đề  mã hóa/giải mã, ta cũng chọn các tham số để tạo một nhóm Abel  E_q(a,b) và chọn một điểm cơ sở G có hạng n lớn.

Các thành phần khóa khóa riêng và công khai trong mã hóa EC được định nghĩa như sau:

Trong đó d<n và  E=dG  với d là một số bí mật do người sinh khóa chọn. Do tính

chất của hàm một chiều từ E và G không thể suy ra được d.

Từ đó chúng ta có hai cách thức thực hiện mã hóa/ giải mã như sau:

1. Phương pháp Elgamal:

Giả  sử  Alice  muốn  gửi  một  thông  điệp  M  cho  Bob,  trước  tiên  Alice  chuyển  M  từ dạng dãy bít sang dạng điểm P_M =(x, y). Bản mã  C_M (dùng khóa công khai  của Bob)  được tính là một cặp điểm như sau:

C _{M =} {kG, P_M + kE}với k là một số ngẫu nhiên do Alice chọn

Để  giải mã dùng khóa riêng,  Bob  sẽ  nhân điểm thứ  nhất trong  C _M với  d, sau đó lấy điểm thứ hai trừ cho kết quả:

Trong phương thức mã hóa, Alice đã che giấu PM bằng cách cộng P_M với kE. Để giải mã, Bob cần trừ  ra lại  kE. Thay vì gửi trực tiếp  k  cho Bob để  Bob tính  kE  (Trudy có thể chặn  được),  Alice  gửi  một  dấu  hiệu  là  kG  .  Dựa  vào  kG  và  d,  Bob  có  thể  tính  kE.  Còn Trudy, dù biết  G  và  kG,  tuy  nhiên vẫn không thể  tính được  k  do tính chất của hàm một chiều.

Ví dụ: chọn p = 751, a = 1, b = 188 ta có đường cong Elliptic trên Z₇₅₁ như sau:

y² mod 751 ₌  (x³ + x + 188) mod 751 trong đó a,b,x,y  Z₇₅₁

Chọn điểm cơ sở là G=(0,376)

Giả sử Alice cần mã hóa bản rõ là điểm P_M=(562,201) dùng khóa công khai E=(201,5). Alice chọn k=386. Ta có

386(0,36)=(676,58)

(562,201)+368(201,5)=(385,328)

Vậy bản mã là cặp điểm {(676,58), (385,328)}

• Phương pháp Menezes – Vanstone:

Thông điệp M  của Alice được tách thành hai phần M=(m1, m2) sao cho  m1, m2    Zp. Alice chọn một số  ngẫu nhiên  k,  kết  hợp với khóa công khai của Bob, Alice  tính  điểm P như sau:

P(x_p,y_p) = kE

Bản mã C_M gồm 3 thành phần:

C_{M =}{ c_0, c_1, c₂ } ={kG, x_pm₁ mod p, y_pm₂ mod p}

Để giải mã dùng khóa riêng, từ dấu hiệu kG, Bod tính:

P(x_p,y_p) = kdG

Và từ đó tính nghịch đảo của x_p^-1  và y_p^-1  trong phép modulo p. Cuối cùng bản giải mã là:

M ={m_1,m₂} = { x_p^-1  c₁ mod p, y_p^-1 c₂ mod p}

Tương tự như phương pháp Elgamal, dù biết G và kG, Trudy cũng không thể tính được k để tính P.

3. Độ an toàn của ECC so với RSA

Hiện nay, phương pháp nhanh nhất để  tính logarit đường cong Elliptic (tính  k  biết  G và  kG) là phương pháp Pollar rho. Bảng sau đây liệt kê  kích thước hóa của phương pháp ECC và phương pháp RSA dựa trên sự tương đương về chi phí phá mã.

Như vậy với cùng một độ  an toàn thì mã hóa ECC chỉ  dùng các phép tính có số  bít nhỏ hơn nhiều lần so với mã hóa RSA.