Đã đăng vào thg 7 29, 1:59 SA 10 phút đọc

[Cryptography p6] Hệ mật Elliptic curve

Bài viết được lấy từ https://truongphuoc.wordpress.com/2023/03/21/blockchain-19-he-mat-duong-cong-elliptic/

Chào các bạn, trong bài viết trước mình đã trình bày về hệ mật RSA. RSA đầy bảo mật nhưng có nhược điểm là quá trình mã hóa và giải mã chậm. Trong bài viết này mình sẽ trình bày về hệ mật đường cong Elliptic (Elliptic curve cryptography).

Đường cong Elliptic

Trong mật mã học, đường cong Elliptic được định nghĩa với biểu thức sau: ${y}^{2} = {x}^{3} + ax + b$ .

Đồ thị của đường cong Elliptic: ${y}^{2} = {x}^{3} + x + 7$

Tại vì $y^2$ nên đồ thị hàm số đối xứng qua một trục nào đó. Khá đơn giản phải không nào, sau đây là một vài chuẩn của đường cong được sử dụng trong mã hóa.

Đường con Elliptic trong trường Galois (Galois Fields)

Đồ thị hàm số $y^2 = x^3 + x + 7$ ta thấy ở trên là xét trong tập R, nên ta thấy đồ thị liền mạch. Trong mật mã chúng ta chỉ làm việc với các số nguyên, nên chúng ta không thể xét trong tập R. Chúng ta có thể sử dụng trường Galois để chắc chắn rằng chúng ta chỉ làm việc với số nguyên.

Hàm số Elliptic trong trường Galois $F_p$ được định nghĩa như sau:

$y^2 ≡ x^3 + ax + b (mod\;p)$

Với $0 <= x,y < p$ và p là một số nguyên tố, a và b là các số nguyên dương, nhỏ hơn p và thỏa mãn điều kiện:

$4a^3 + 27b^2\; mod\; p ≠ 0$

Ví dụ với $p = 23, a = 1, b = 1$ ta có như sau:

$4a^3 + 27b^2\; mod\; p = 4 × 1^3 + 27 × 1^2\; mod\; 23\\ 4a^3 + 27b^2\; mod\; p = 4 + 27 \;mod\; 23 = 31\; mod\; 23\\ 4a^3 + 27b^2\; mod\; p = 8 ≠ 0$

Nên $a = 1, b = 1$ hợp lệ => Hàm số $y^2 ≡ x^3 + x + 1\; (mod\; 23) ∈ F_{23}$ . Ta có thể ký hiệu hàm số như sau: $E_{23}(1, 1)$ .

Với đường cong $E_{23}(1, 1)$ thì $y^2$ được định nghĩa thuộc $Q_{23}$ lập trong bảng sau:

Tính như sau: với $x = 2 \Rightarrow x^2\; mod\; p = 2^2\; mod\; 23 = 4\; mod\; 23 = 4$ , tương tự với các trường hợp còn lại.

$\Rightarrow Q_{23} = \{0, 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 16, 18\}$

Vì $x ∈ F_{23}$ nên $0<= x < 23$ , với hàm số $y^2 ≡ x^3 + x + 1\; (mod \;23)$ trên ta thay x vào sẽ tìm được y như sau:

Tính như sau: Với $x = 1$ thay vào biểu thức $\\y^2 = x^3 + x + 1\; mod \;23 = 3 ∈ Q_{23}\\$ Đối chiếu với bảng trên ta được $y = 7$ hoặc $y =16$

Ta có đồ thị sau:

Phép cộng hai điểm trên đường cong Elliptic

Về mặt hình học, phép cộng hai điểm P và Q trên đường cong Elliptic được định nghĩa như sau:

Người ta định nghĩa phép cộng hai điểm trên đường cong Elliptic như sau: Cho hai điểm P và Q thuộc đường cong Elliptic, đường thằng đi qua P và Q cắt đường cong Elliptic tại một điểm -R, lấy R đối xứng với -R qua trục của đường cong, ta nói P + Q = R.

$P + Q = R$

Phép cộng trong trường Galois

Còn trong trường Galois:

Cho hai điểm $P(x_1, y_1)$ và $Q(x_2, y_2)$ nằm trong đường cong $E_p(a, b)$ . Và O là điểm vô cực. Phép cộng hai điểm được định nghĩa như sau:

$P + O = O + P = P$ .
Nếu $x_2$ = $x_1$ và $y_2$ = $-y_1$ , tức $P = (x_1, y_1)$ và $Q = (x_2, y_2) = (x_1, -y_1) = -P$ . Khi đó $P + Q = O$ .
Nếu $Q ≠ -P$ thì $P + Q = (x_3, y_3)$ với $x_3, y_3$ được tính như sau:

với

Bạn có thể tính phép cộng tại đây

Phép nhân vô hướng trên đường cong Elliptic

Phép nhân vô hướng trên đường cong Elliptic thực chất là phép cộng với chính nó. Ví dụ $2P = P + P, 3P = P + P + P = 2P + P$ .

Ví dụ như sau: $P = (3, 10)$ nằm trong $E_{23}(1, 1)$ , ta tính 2P như sau:

$2P = P + P = (x_1, y_1) + (x_2, y_2)$

Theo công thức ở trên ta có:

Nên $2P = (x_3, y_3) = (7, 12)$

Chú ý ở trên có phép toán $4^{-1}\; mod\; 23$ tức là $\frac{1}{4}\; mod\; 23$ nhé, cách tính mình đã nói ở phần trước rồi.

Bạn có thể tính phép nhân tại đây

*Ngoài phép cộng điểm và phép nhân vô hướng thì trên đường cong Elliptic không có các phép tính khác.

Một bài toán thú vị

Mình có một bài toán như sau: Cho điểm $P(3, 10)$ và điểm $H(3,13)$ cùng nằm trong đường cong $E_{23}(1, 1)$ . Tìm $k$ biết rằng có tồn tại một $k$ thỏa mãn: $k*P = Q$ .

Bài toán trên cũng đơn giản phải không nào, do đường cong Elliptic chỉ có phép cộng điểm và phép nhân vô hướng, nên ta không thể lấy $k = \frac{Q}{P}$ được. Do đó để tìm $k$ không có cách nào khác chúng ta phải vét cạn thôi (tức là thử từng trường hợp một đó). Với $k = 2 \Rightarrow 2P = (7, 12) ≠ Q, k = 3 => 3P = (19,5) ≠ Q$ ,.. tương tự với các k khác ta có bảng dưới đây

Ta thấy rằng với $k = 27$ thì $27P = (3, 13) = Q$ . Do đó ta kết luận $k = 27$ .

Bài toán trên đã được chứng minh là có nghiệm duy nhất.

Có vẻ đơn giản phải không nào, giờ chúng ta sẽ tăng $k$ lên thành $123412183249183241$ thì sao nhỉ? lúc này thì tính toán sẽ khó hơn nhỉ, nếu $k$ là một số 256 bit thì sao nhỉ? Lúc đó $k < 2^{256}$ . Các bạn đã nhìn thấy $2^{256}$ chưa, nó như vầy này:

2^256 = 115,792,089,237,316,195,423,570,985,008,687,907,853,269,984,665,640,564,039,457,584,007,913,129,639,935
      = 1.15e77

Ta thử tính thời gian vét cạn với không gian $2^{256}$ bit này nhé. Với siêu máy tính mạnh nhất thế giới 2006 là Hệ thống Blue Gene/L, được lắp đặt tại Phòng thí nghiệm Quốc gia Lawrence Livermore tính toán được 280,6 nghìn tỉ phép tính trên giây ( $2,806e^{14}$ ), suy ra một năm (1 năm = 31.556.952 giây) siêu máy tính này tính được $2.806e^{14} * 31.556.952 = 8.854e^{21}$ phép tính. Thế cần bao lâu để siêu máy tính này vét cạn được với $k = 2^{256}$ ? Ta cùng tính nhé: $1.15e^{77} / 8.854e^{21} = 1.298e^{55}$ tức là 12 tỷ tỷ tỷ tỷ tỷ tỷ năm đó các bạn, trong đó thiên hà của chúng ta mới được có 14 tỷ năm thôi à 🤣.

Chúng ta thấy rằng nếu có thể áp dụng đường cong Elliptic vào trong mật mã, k là Private key và kG là Public key với G là một điểm trên đường cong $E_p(a, b)$ thì cực kỳ khó, hay có thể nói là bất khả thi để tìm ra Private key k khi biết Public key kG. (Giống bài toán trên cho điểm Q và P thì khó có thể tìm được k vậy)

Hệ mật đường cong Elliptic

Dựa vào tính chất chỉ có phép cộng của đường cong Elliptic cùng sự khó khăn trong việc vét cạn với số lớn, người ta tạo ra hệ mật được cong Elliptic.

Trong hệ mật đường cong Elliptic, quá trình mã hóa Plain text M thành Cypher text C trong $E_p(a, b)$ được thực hiện như sau:

Encryption

Plain text M được chuyển đổi thành một điểm nằm trong $E_p(a, b)$ , gọi là điểm $P_M$ .
Chọn một điểm G nằm trong $E_p(a, b)$ sao cho số n trong biểu thức nG = O là một số rất lớn (O là điểm vô cực). G được gọi là điểm cơ sở.
$E_p(a, b)$ và G là công khai.
Bình muốn tạo cặp khóa (key pair) cho mình, Bình chọn một số k sao cho k < n. Sau đó tính kG được kết quả là $P_B$ . Lúc này k là Private key của Bình và $P_B$ là Public key của Bình.
An muốn mã hóa Plain text $P_M$ $P_{M}$ với Public key của Bình thì làm như sau: An chọn một số ngẫu nhiên r , sau đó chuyển Plain text $P_M$ $P_{M}$ thành Cypher text $P_C$ $P_{C}$ với công thức:
- $P_C = [(r*G), (P_M + r*P_B)]$

Decryption

Sau đó An gửi $P_C$ cho Bình. Sau khi nhận được $P_C$ từ An, Bình giải mã với công thức sau:

$P_M = (P_M + r*P_B) - [k*(r*G)] = (P_M + r*(k*G - [r*(k*G)]$

Thế là hết về phần lý thuyết, tiếp theo tới ví dụ nào (các bạn có thể sử dụng tool mình link ở trên để tính toán phép cộng và nhân cho nhanh nhé)

Ví dụ với đường cong $E_{23}(1, 1)$ , ta chọn G = (3, 10). Với G này thì ta được 28G = O.

Bình muốn tạo cặp khóa của mình thì đầu tiên phải chọn ngẫu nhiên một số k với $0 < k < 28$ . Ví dụ Bình chọn $k = 13 => k*G = 13*G = 13(3, 10) = (1, 7)$ . Vậy Private key của Bình là 13 và Public key của Bình là $P_B = (1, 7)$ .

An muốn gửi Plain text $P_M = (6, 4)$ thì làm như sau: An chọn một số ngẫu nhiên r = 3, sau đó sử dụng Public key của Bình $P_B = (1, 7)$ để tính Cypher text $P_C$ như sau:

$P_C$ = [(r*G), ( $P_M + r*P_B)$ ]
$P_C$ = [3 × (3, 10), (6, 4) + 3 × (1, 7)]
$P_C$ = [(19, 5), (6, 4) + (18, 20)]
$P_C$ = [(19, 5), (11, 20)]

An gửi Cypher text $P_C$ cho Bình, sau khi nhận được $P_C$ Bình giải mã như sau:

$P_M= (P_M + r*P_B) - [k*(r*G)] = (11, 20) - [13(19, 5)]\\ P_M =(P_M + r*P_B) - [k*(r*G)] = (11, 20) - (18, 20)\\ P_M =(P_M + r*P_B) - [k*(r*G)] = (11, 20) + (18, -20) (vì -P = (x_1, -y_1) = -(18, 20) = (18, -20))\\ P_M =(P_M + r*P_B) - [k*(r*G)] = (11, 20) + (18, 3) (vì -20 ≡ 3 (mod \;23))\\ P_M =(P_M + r*P_B) - [k*(r*G)] = (6, 4)$

Thế là Bình đã tìm được $P_M$ chính xác rồi.

Còn bạn nào thắc mắc về cách quy từ Plain text ra $P_M$ . Cũng có nhiều cách làm phần này. Ví dụ An và Bình cùng thống nhất một bảng mapping giữa số và các điểm trên $E_{23}(1, 1)$ . Ví dụ ta có các điểm sau nằm trên $E{23}(1, 1): (6, 4), (1, 7), (19, 18),....$ . An và Bình có thể quy ước như sau:

Poin	Symbol
(6, 4)	a
(1, 7)	b
(19, 18)	c
...	...

Bảng mapping điểm và ký tự

Như vậy là mình đã trình bày về hệ mật đường cong Elliptic, cũng không khó lắm phải không nào. Hệ mật này được sử dụng rộng rãi ngày nay nhờ sự bảo mật và khả năng tính toán nhanh của nó.

Còn một vấn đề nữa là trao đổi khóa công khai an toàn, việc trao đổi khóa công khai an toàn trong Elliptic curve cryptography cũng giống như trong RSA mình đã giới thiệu ở bài trước. Đó cũng là cơ chế chung của việc trao đổi khóa an toàn trong hệ mật bất đối xứng.

Bài tập về nhà: Bạn hãy mapping chuỗi AYE sau đó thực hiện mã hóa và giải mã sử dụng hệ mật Elliptic curve. Bạn nên làm bài tập này, bài tiếp theo nói về một chủ đề rất hay là chữ ký điện tử, có sử dụng kiến thức của bài này, thế nên nếu bạn không làm bài tập thì khó lòng mà hiểu sâu sắc được bài tiếp theo đó.

Link bài viết gốc https://truongphuoc.wordpress.com/2023/03/21/blockchain-19-he-mat-duong-cong-elliptic/