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 2m(nếu chọn đường cong GF(2m)), và chọn 2 tham số a, b tương ứng để tạo thành nhóm Eq(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ố nA < n và giữ  bí mật số nA này. Sau đó trong Eq(a,b) Alice

Tính PA= nAG và gửi cho Bob.

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

3)  Alice tạo khóa phiên bí mật là  K=   nA PB = nA nBG

4)  Bob  tạo  khóa  phiên  bí  mật  là  K=   nB PA = nA nBG (nhóm  Abel  có

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

Trudy có thể chặn được PA và PB, 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  Eq(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 PM =(x, y). Bản mã  CM (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, PM + 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 PM 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 Z751 như sau:

y2 mod 751 =  (x3 + x + 188) mod 751 trong đó a,b,x,y  Z751

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

Giả sử Alice cần mã hóa bản rõ là điểm PM=(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(xp,yp) = kE

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

CM ={ c0, c1, c2 } ={kG, xpm1 mod p, ypm2 mod p}

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

P(xp,yp) = kdG

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

M ={m1,m2} = { xp-1  c1 mod p, yp-1 c2 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.

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 )

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: