# TASK 5 - Elliptic Curve Cryptography
# 1. Kiến thức cơ sở.
## Định nghĩa
Đường cong Elliptic là một đối tượng hình học trừu tượng được định nghĩa bởi phương trình dạng $y^2 = x^3 + ax + b$, trong đó $a$ và $b$ là các hằng số được chọn trước đó.
Các đường cong này có những tính chất đặc biệt và rất phức tạp, tạo ra nhiều lý thuyết và ứng dụng thú vị. Trong lý thuyết số, đường cong Elliptic liên quan đến bài toán đường cong Elliptic, một trong những bài toán khó nhất trong lý thuyết số. Trong mật mã học, đường cong Elliptic được sử dụng trong các thuật toán mật mã hóa khóa công khai như ECDSA và ECDH.
Điều thú vị về đường cong Elliptic là chúng có tính chất đối xứng và liên quan đến các hệ thống điểm trên không gian affine và projective. Chúng cũng có mối liên hệ với các hàm lượng giác như tổng điểm và phép nhân điểm.
Do tính phức tạp của chúng, đường cong Elliptic được nghiên cứu sâu rộng trong toán học và có nhiều ứng dụng thực tế quan trọng.
VD:
E : $y^2$ = $x^3$ + $\frac{x}{2}$ +$\frac{5}{3}$
### Nhận xét
Một đường cong elip E trên một trường K được xác định bởi một phương trình
E : $y^2$ +$a_1xy$ +$a_3 y$ = $x^3$ +$a_2x^2$ +$a_4x$ +$a_6$ (1)
Trong đó a1,a2,a3,a4,a6 ∈ K and $\triangle$ $\neq$ 0, $\triangle$ là hệ số phân biệt (*discriminant*) của E được tính bằng công thức :
- Phương trình (1) được gọi là phương trình Weierstrass.
- Ta nói rằng E xác định trên K vì các hệ số a1,a2,a3,a4,a6 của phương trình xác định của nó là các phần tử của K. Đôi khi ta viết E/K để nhấn mạnh rằng E xác định trên K, và K là được gọi là trường cơ sở. Lưu ý rằng nếu E được xác định trên K, thì E cũng được xác định trên bất kỳ trường mở rộng nào của K.
- Điều kiện $\triangle$ $\neq$ 0 đảm bảo rằng đường cong elip là “trơn”, tức là không có điểm nào mà tại đó đường cong có hai hay nhiều tiếp tuyến phân biệt.
- Điểm ∞ là điểm duy nhất trên đường thẳng ở vô cực thỏa mãn dạng xạ ảnh của phương trình Weierstrass.
- Các điểm hữu tỷ L trên E là các điểm (x, y) thỏa mãn phương trình của đường cong và có tọa độ x và y thuộc L. Điểm ở vô cực được coi là điểm hữu tỷ L cho tất cả các trường mở rộng L của K.
## 1.1 Phương trình Weierstrass đơn giản
Simplified Weierstrass equations là dạng đơn giản của phương trình Weierstrass dùng để mô tả đường cong elliptic trên mặt phẳng phức. Dạng phương trình này được viết dưới dạng:
$y^2 = x^3 + ax + b$
Trong đó, a và b là các hằng số được gọi là các tham số Weierstrass và y và x là các biến số. Điều kiện để đường cong elliptic có thể được biểu diễn dưới dạng phương trình Simplified Weierstrass là đường cong này không có các đặc điểm đặc biệt (có thể được biểu diễn dưới dạng các điểm gốc hoặc các đường thẳng đứng) và không có điểm có toạ độ nhỏ hơn vô cùng.
Phương trình Simplified Weierstrass là một trong những công cụ quan trọng trong lý thuyết đường cong elliptic và được sử dụng để tìm kiếm các đặc tính của đường cong elliptic như điểm sinh, độ lớn của nhóm, tỷ lệ của các điểm trên đường cong elliptic.
Đường cong elliptic E1 và E2 được xác định trên trường K và được cho bởi phương trình Weierstrass như sau:
E1: $y^2$ + $a_1xy$ + $a_3y$ = $x^3$ + $a_2x^2$ + $a_4x$ + $a_6$
E2: $y^2$ + ${a'}_1xy$ + ${a'}_3y$ = $x^3$ + ${a'}_2x^2$ + ${a'}_4x$ + ${a'}_6$
Hai đường cong elliptic này được gọi là đồng dạng trên trường K nếu tồn tại các phần tử u, r, s và t trong trường K, với u khác 0, sao cho phép biến đổi sau chuyển đổi phương trình E1 thành phương trình E2:
$(x, y)$ → ($u^2x$ + $r$, $u^3y$ + $u^2sx$ + $t$)
Phép biến đổi này được gọi là phép biến đổi hợp lệ.
Từ định nghĩa này, chúng ta có thể kết luận rằng nếu hai đường cong elliptic E1 và E2 được định nghĩa trên cùng một trường K và có phương trình Weierstrass giống nhau, thì chúng sẽ là đồng dạng nếu có thể chuyển đổi phương trình của một đường cong thành phương trình của đường cong kia bằng một phép biến đổi hợp lệ.
## 1.2. Group law
Group law trên đường cong elliptic là một phép toán hai ngôi được sử dụng để thực hiện phép cộng giữa hai điểm trên đường cong elliptic và tính toán các phép nhân điểm trên đường cong. Group law này có tính chất đặc biệt và là cơ sở cho nhiều ứng dụng trong mật mã học và lý thuyết số học.
Cụ thể, để thực hiện phép cộng hai điểm P và Q trên đường cong elliptic, ta vẽ đường thẳng đi qua hai điểm đó. Đường thẳng này sẽ cắt đường cong elliptic tại một điểm R khác với P và Q. Ta sẽ định nghĩa R là kết quả của phép toán P + Q.
Việc tính toán phép cộng P + Q có thể được thực hiện bằng cách sử dụng các công thức tính toán đặc biệt dựa trên các đại lượng liên quan đến các điểm trên đường cong elliptic, bao gồm đạo hàm và phép nghịch đảo.
Group law trên đường cong elliptic cũng cho phép tính toán các phép nhân điểm bằng cách sử dụng phép cộng lặp đi lặp lại. Ví dụ, để tính toán phép nhân mP của một điểm P trên đường cong elliptic, ta có thể lặp lại phép cộng P với chính nó m lần.
Group law trên đường cong elliptic có tính chất đặc biệt và được sử dụng rộng rãi trong các ứng dụng mật mã học như mã hóa đường cong elliptic và chữ ký số đường cong elliptic.
**Group law cho E/K : $y^2$ = $x^3$ + $ax$ + $b$, char(K) $\not=$ 2,3**
- Đồng nhất. P + ∞ = ∞ + P = P đối với tất cả P ∈ E(K).
- Đối của một điểm. Nếu P = (x, y) ∈ E(K), thì (x, y) + (x, -y) = ∞. Điểm (x, -y) được ký hiệu là -P và được gọi là đối của P; chú ý rằng -P thực sự là một điểm trên E(K). Ngoài ra, -∞ = ∞.
- Phép cộng điểm. Cho P = ($x_1, y_1$) ∈ E(K) và Q = ($x_2, y_2$) ∈ E(K), trong đó P ≠ ±Q. Sau đó, P + Q = ($x_3, y_3$), trong đó
$x_3$ = ${(\frac{y_2 - y_1}{x_2 - x_1})}^2$ - $x_1$ - $x_2$ và $y_3$ = ${(\frac{y_2 - y_1}{x_2 - x_1})}*(x_1 - x_3)$ - $y_1$.
- Phép nhân đôi điểm. Cho P = (x1, y1) ∈ E(K), với P = -P. Sau đó 2P = (x3, y3), trong đó
$x_3$ = $(\frac{3x_1^2 + a}{2y_1})^2$ - $2x_1$ và $y_3$ = $(\frac{3x_1^2 + a}{2y_1})*(x_1 - x_3)$ - $y_1$.
## 1.3. Group order
Group order của đường cong elliptic là số lượng các điểm trên đường cong, kể cả điểm ở vô cùng. Tổng quát hơn, nó được ký hiệu là |E(K)| và được tính bằng cách sử dụng định lý Hasse.
Định lý Hasse cho biết rằng nếu E là một đường cong elliptic trên trường hữu hạn Fq, thì |𝐸(Fq)| được xác định bởi:
|𝐸($F_q$)| = $q$ + 1 - $t$
trong đó |$t$| ≤ $2*\sqrt{q}$. Cụ thể hơn, ta có thể tính toán Group order của E(K) bằng cách tìm số lượng điểm trên đường cong, sử dụng các thuật toán tìm điểm trên đường cong như phép cộng và phép nhân.
Việc tính toán Group order rất quan trọng trong việc áp dụng đường cong elliptic trong các ứng dụng mật mã, như tạo số nguyên tố trong mã hóa RSA.
### Định lí
Cho $q = p^m$ với $p$ là số nguyên tố cơ sở của $F_q$. Tồn tại một đường cong elliptic E được xác định trên Fq sao cho E($F_q$) = $q$ +$1$−$t$ nếu và chỉ nếu một trong các điều kiện sau đây được thỏa mãn:
(i) t ≡ 0 (mod p) và t^2^ ≤ 4q.
(ii) m là số lẻ và hoặc t = 0; hoặc t^2^ = 2q và p = 2; hoặc t^2^ = 3q và p = 3.
(iii) m là số chẵn và hoặc t^2^ = 4q; hoặc t^2^ = q và p ≡ 1 (mod 3); hoặc t = 0 và p ≡ 1 (mod 4).
## 1.4. Group structure
Chúng ta sử dụng Zn để chỉ một nhóm tuần hoàn có đơn vị số nguyên dương là n.
Giả sử E là một đường cong elliptic được xác định trên Fq. Khi đó E($F_q$) đồng cấu với $Z_{n_1}$ ⊕ $Z_{n_2}$ trong đó $n_1$ và $n_2$ là các số nguyên dương duy nhất sao cho $n_2$ chia hết cho cả $n_1$ và $q −1$.
Lưu ý rằng E($F_q$) = $n_1n_2$. Nếu $n_2$ = 1, thì E($F_q$) là một nhóm tuần hoàn. Nếu $n_2$> 1, thì E($F_q$) được gọi là có hạng là 2. Nếu $n_2$ là một số nguyên nhỏ (ví dụ: n = 2,3 hoặc 4), chúng ta có thể nói rằng E($F_q$) gần như là tuần hoàn. Vì $n_2$ chia hết cho cả $n_1$ và q - 1, ta có thể kỳ vọng rằng E($F_q$) là tuần hoàn hoặc gần như tuần hoàn đối với phần lớn các đường cong elliptic E trên Fq.
## 1.5. Isomorphism classes
Lớp đồng đẳng (Isomorphism classes) của đường cong elip là một khái niệm quan trọng trong hình học đại số và lý thuyết số.
Hai đường cong elliptic được cho là đẳng cấu nếu tồn tại một phép biến hình song ánh (một "bản đồ" giữa các dạng đại số) giữa chúng để bảo toàn cấu trúc nhóm của đường cong.
Nói cách khác, hai đường cong elliptic là đồng đẳng khi và chỉ khi có một phép đổi biến làm biến đổi cái này thành cái kia mà vẫn bảo toàn cấu trúc nhóm của đường cong.
Một cách khác là dùng dạng chuẩn tắc Weierstrass của đường cong elip, đây là một phương trình chuẩn mà tất cả các đường cong elip có thể chuyển thành. Hai đường cong elliptic là đồng đẳng khi và chỉ khi dạng chuẩn tắc Weierstrass của chúng là tương đương với nhau khi đổi biến.
Nhìn chung, việc nghiên cứu các lớp đồng đẳng của đường cong elliptic đã dẫn đến nhiều kết quả và ứng dụng quan trọng trong lý thuyết số, mật mã học và các lĩnh vực toán học khác.
### Định lí
Cho K = Fq là một trường hữu hạn với char(K) = 2,3.
- Các đường cong elliptic
E1: $y^2$ = $x^3$ + $ax$ + $b$ (1)
E2: $y^2$ = $x^3$ + ${a'}x$ + $b'$ (2)
được xác định trên K ,đồng đẳng trên K nếu và chỉ nếu tồn tại $u$ ∈ K∗ sao cho $u^4a'$ = $a$ và $u^6b'$ = $b$. Nếu có $u$ như vậy tồn tại, thì phép biến đổi hợp lệ
$(x, y)$ → $(u^2x, u^3 y)$
biến đổi phương trình (1) thành phương trình (2).
- Số lớp đồng đẳng của các đường cong elliptic trên K lần lượt là 2q +6, 2q +2, 2q +4, 2q, cho q ≡ 1,5,7,11 (mod 12).
# 2. Hệ mật dựa trên đường cong Elliptic và một số ứng dụng
## 2.1. Bài toán Logarithm rời rạc
Bài toán Logarithm rời rạc trên đường cong Elliptic (ECDLP):
Cho đường cong E trên trường hữu hạn $F_q$, điểm P ∈ E($F_q$) với bậc n (nP = O = ∞)
và điểm Q ∈ E($F_q$), tìm số nguyên k ∈ [0, n − 1] sao cho Q = kP. Số nguyên k được
gọi là Logarithm rời rạc của Q với cơ sở P, và thường được viết là k = $log_P Q$.
Bất kỳ một hệ mật khóa công khai nào cũng phải sử dụng một bài toán khó để
xây dựng hàm một chiều. Ý nghĩa một chiều ở đây có nghĩa là tính thuận thì dễ
(thuật toán giải trong thời gian đa thức) và tính ngược thì khó (thuật toán giải với
thời gian không phải là đa thức - thường là hàm mũ hoặc nửa mũ). Các tham số
của Hệ mật dựa trên đường cong Elliptic (ECC) cần phải được lựa chọn cẩn thận
để tránh được các tấn công đối với bài toán ECDLP. Thuật toán vét cạn để giải
bài toán ECDLP là lần lượt tính thử các điểm P, 2P, 3P, ... cho đến khi điểm mới
tính được đúng bằng điểm Q. Trong trường hợp xấu nhất sẽ phải cần đến n bước
thử, trung bình thường là n/2 là đạt được điểm Q, do đó cần phải chọn n đủ lớn để bài toán vét cạn là không khả thi (n ≥ 2^160^).
Thuật toán tốt nhất hiện nay để tấn công bài toán ECDLP là sự kết hợp của thuật toán Pohlih-Hellman và Pollard’s rho, thuật toán này có thời gian tính là O($\sqrt{p}$), với p là ước số nguyên tố lớn nhất của n do đó phải chọn số n sao cho nó chia hết số nguyên tố p lớn nhất có $\sqrt{p}$ đủ lớn để giải bài toán này là không khả
thi.
Cho G là nhóm các điểm trên đường cong E. P, Q ∈ G là các điểm trên đường
cong E, chúng ta cần giải bài toán kP = Q, N là bậc của G.
### 2.1.1 Phương pháp bước nhỏ, bước lớn
Thuật toán:
Dễ dàng nhận thấy Q = iP + jmP hay Q = (i + jm)P từ đó k = i + jm. Điểm iP được tính bằng cách cộng thêm P vào (i − 1)P và giá trị này được gọi là bước nhỏ. Q − jmP được tính bằng cách cộng thêm mP vào Q − (j − 1)mP và giá trị này
được gọi là bước lớn.
### 2.1.2 Phương pháp Pollard’s ρ và λ
Định nghĩa hàm *f : G → G* một cách ngẫu nhiên $P_{i+1}$ = $f(P_i)$ với $P_0$ cũng được
chọn một cách ngẫu nhiên. Bởi vì G là tập hữu hạn do đó sẽ có các chỉ số $i_0$ < $j_0$
mà $P_{i_0}$ = $P_{j_0}$, từ đó ta có:
$P_{i_0+1}$ = $f(P_{i_0})$ = $f(P_{j_0})$ = $P_{j_0+1}$
Tương tự sẽ có $P_{i_0+l}$ = $P_{j_0+l}$ với $l ≥ 0$, từ đó chuỗi $P_i$ là chuỗi tuần hoàn với chu kỳ là $j_0 − i_0$. Hàm biểu diễn chuỗi $P_i$ thường giống chữ cái Hi Lạp $ρ$ và đó là lý do tại sao phương pháp này có tên là phương pháp $ρ$.
Hàm f được chọn như sau: Chia tập G thành s tập con không trùng nhau
$S_1, S_2, . . . , S_s$ có kích thước tương đương nhau, s thường được chọn là 20, chọn 2s số ngẫu nhiên $a_i
, b_i$ *mod N*. Đặt: $M_i = a_iP + b_iQ$
Và định nghĩa: $f(g) = g + M_i$, $g ∈ S_i$
Biểu diễn $P_j$ dưới dạng $P_j = u_jP + v_jQ$, khi $P_{i_0} = P_{j_0}$
ta có:
$u_{j_0}P + v_{j_0}Q = u_{i_0}P + v_{i_0}Q$
$(u_{i_0} − u_{j_0})P = (v_{j_0} − {vx'}_{j_0})Q$
$k = (v_{j_0} − {vx'}_{j_0})^{-1}(u_{i_0} − u_{j_0})$ (*mod* $N$)
Phương pháp này cũng tương tự như phương pháp trên cần $\sqrt{N}$ bước, tuy nhiên không gian lưu trữ sẽ nhỏ hơn.
### 2.1.3 Phương pháp Pohlig-Hellman.
Nếu có thể phân tích bậc N của G thành các thừa số nguyên tố thì có thể viết:
N = $\Pi q_i^{e_i}$
Ý tưởng của phương pháp này là tìm k (mod $q_i^{e_i}$) với mỗi i, sau đó áp dụng định lý đồng dư Trung Hoa để tính k (mod N). Coi q là số nguyên tố và q^e^ là lũy thừa e của q được chia hết bởi N, viết k dưới dạng sau:
$k = k_0 + k_1q + k_2q^2 + · · · , 0 ≤ k_i < q$
Lý giải thuật toán như sau:
$\frac{N}{q}Q$ = $\frac{N}{q}(k_0 + k_1q + · · ·) P$
= $k_0\frac{N}{q}P$ + $(k_1 + k_2q + · · ·) NP$ = $k_0\frac{N}{q}P$
Bởi vì NP = ∞ và từ đây có thể tìm được $k_0$. Tiếp theo:
$Q1 = Q − k_0P$ = $(k_1q +k_2q^2+...)P$
N
$\frac{N}{q^2}Q_1$ = $\frac{N}{q}(k_1+k_2q+...)P$
= $k_1\frac{N}{q}P$ +$(k_2+k_3q+...)NP$ = $k_1\frac{N}{q}P$
Từ đó tìm được $k_1$, tương tự như vậy chúng ta sẽ tìm được $k_2, k_3 . . .$Thuật toán sẽ dừng khi *e = r + 1*, khi đó $N/q^{e+1}$ không còn là số nguyên nữa và chúng ta không thể nhân $Q_e$ với một số hữu tỷ.
Thuật toán:
### 2.1.4 Phương pháp tấn công MOV
Tấn công MOV là tên viết tắt của các tác giả Menezes, Okamoto, và Vanstone, sử dụng cặp Weil để chuyển đổi bài toán Logarithm rời rạc trong E($F_q$) thành
bài toán Logarithm rời rạc trong ${F×}_{q^m}$. Bởi vì giải bài toán Logarithm rời rạc trong
trường hữu hạn sẽ dễ dàng và nhanh hơn giải Logarithm rời rạc trong nhóm các
điểm trên đường cong Elliptic. Chọn $m$ sao cho: $E[N]$ ⊆ ${F×}_{q^m}$
Bởi vì tất cả các điểm trong $E[N]$ đều có tọa độ trong $F_q = ∪_j≥1F_{q^j}$, nên $m$ tồn tại. Theo định nghĩa về cặp Weil và các thuộc tính của cặp song tuyến tính:
$ζ_2 = e_N (Q, T_1) = e_N (kP, T_1) = e_N (P, T_1)^k = ζk_1$
Thuật toán:
## 2.2 Tham số của hệ mật ECC
Các tham số của hệ mật ECC cần được lựa chọn kỹ càng để tránh các tấn công
như MOV, trong quá trình lựa chọn hệ ECC cần phải đạt được một số tiêu chí:
Tham số hệ mật $D = (q, F R, S, a, b, P, n, h)$ là một tập hợp gồm:
1. Bậc của trường $F_q$ là $q$.
2. Phương pháp biểu diễn trường $FR$ (field representation) được sử dụng cho các phần tử của $F_q$.
3. $S$ là mầm được sử dụng trong trường đường cong Elliptic được tạo ra một cách ngẫu nhiên.
4. Hai hệ số $a, b ∈ F_q$ được dùng để định nghĩa đường cong $E$ trên $F_q$ (nghĩa là $y^2 = x^3 + ax + b$).
5. $P$ là một điểm có bậc nguyên tố $n$ và gọi là điểm cơ sở $P = (x_P , y_P ) ∈ E(F_q)$.
6. Đồng hệ số h = #$E(F_q)/n$.
## 2.3 Trao đổi khóa
### 2.3.1 Trao đổi khóa Diffie–Hellman ECDH
Hai bên A và B cần tạo khóa phiên bí mật trao đổi trong một kênh truyền công khai, hai bên cùng thỏa thuận điểm cơ sở $P$ trên $E$. Bên A tạo khóa bí mật $d_A$ và gửi giá trị $d_AP$ cho bên B, ngược lại bên B tạo khóa bí mật $d_B$ nhân với P sau đó gửi lại cho A. Khi đó khóa phiên của bên A sẽ là $K_A = d_Ad_BP$, và của bên B sẽ là
KB = $d_Bd_AP$. Dễ dàng nhận thấy $K_A = K_B$, khóa này chỉ riêng hai bên A và B có thể tính được. Xem sơ đồ dưới đây:
*Đánh giá bảo mật:* Để tìm được khóa chia sẻ $K_A$ hoặc $K_B$, Hacker buộc phải tìm được cả 2 khóa bí mật $d_A, d_B,$ trong khi chỉ có thể bắt được thông tin trên đường
truyền là $d_AP$ và $d_BP$, khi biết P, Hacker buộc phải giải bài toán Logarithm rời rạc $d_A = log_P (d_AP)$ và $d_B = log_P (d_BP)$ và đây là bài toán khó không giải được trong thời gian đa thức.
### 2.3.2 Tạo khóa bí mật chia sẻ ECMQV
Tên đầy đủ của giao thức là Elliptic Curve Menezes-Qu-Vanstone. Thuật toán đã được đưa vào trong các chuẩn ANSI X9.63, IEEE 1363-2000, và ISO/IEC 15946-3. Theo các tiêu chuẩn này điểm cơ sở được ký hiệu là $G$ thay vì là $P$ như thường gặp. Lược đồ này thường được sử dụng khi các bên A và B có cặp khóa công khai
và bí mật cố định, tương ứng là $(a, aG)$ và $(c, cG)$.
Bên A sinh cặp số ngẫu nhiên $(b, bG)$ và bên B tương ứng sinh cặp số ngẫu nhiên $(d, dG)$, và trao đổi 2 cặp này cho nhau giá trị $bG$ và $dG$. Kí hiệu hàm $x$ : $E → N$,lấy giá trị $x$ của một điểm trên đường cong $E$.
Thuật toán:
Bên $B$ có thể tính ra cùng số $Q$ bằng cách thay $(a, b, c, d)$ trong thuật toán trên bằng $(c, d, a, b)$. Bên A sẽ có các giá trị $u_A, v_A, s_A$ và bên B sẽ có $u_B, v_B, s_B$. Dễ dàng nhận thấy :
$u_A = v_B$
$u_B = v_A$
$Q_A = s_A(dG + v_A(cG)) = s_A(d + v_Ac)G$
= $s_A(d + u_Bc)G = s_As_BG$
$Q_B = s_B(bG + v_B(aG)) = s_B(b + v_Ba)G$
= $s_B(b + u_Aa)G = s_Bs_AG$
$Q_A = Q_B = Q$
*Đánh giá bảo mật*: Để hack được khóa chia sẻ, Hacker cần phải tính được các giá
trị $a, b, c, d$, muốn vậy Hacker phải giải các bài toán Logarithm rời rạc $a = log_G(aG),b = log_G(bG), c = log_G(cG), d = log_G(dG).$ Đây là các bài toán khó không thể giải được trong thời gian đa thức.
## 2.4 Xác thực - chữ ký số
### 2.4.1 ECDSA(The Elliptic Curve Digital Signature Algorithm)
Người ký sẽ chọn số $d$ làm khóa bí mật và tạo ra khóa công khai là $Q = dP$, sử dụng hàm băm $H$ để tạo ra giá trị tóm lược văn bản $e$ của văn bản $m$. Chữ ký số
sẽ là cặp $(r, s)$ được tính theo thuật toán:
Sau đó,Người xác thực chữ ký nhận được văn bản m′ và chữ ký số (r, s) của người ký,sẽ tính giá trị tóm lược e′
của văn bản nhận được là m′ và áp dụng thuật toán để xác định sự phù hợp của chữ ký số với văn bản nhận được, từ đó có thể khẳng định văn vản có do đúng người ký ký hay có sự giả mạo từ người khác hoặc văn bản có bị sửa đổi hay bị lỗi do đường truyền hay không.Thuật toán:
*Đánh giá bảo mật*: Để giả mạo được chữ ký, Hacker cần phải tìm được giá trị $k$ và khóa bí mật $d$, để tìm được 2 giá trị này Hacker buộc phải giải 2 bài toán Logarithm rời rạc $k = log_P R$ và $d = log_P Q$ và đây đều là 2 bài toán khó, chưa giải được trong thời gian đa thức.
### 2.4.2 Chữ ký số ElGamal
Định nghĩa hàm $f$ như sau:
$f : E(F_q) → Z$
Có thể chọn hàm $f(x, y) = x$, trong đó $x$ là số nguyên $0 ≤ x < q$. Cặp khóa bí mật và công khai của người ký là $(x, Y ) | Y = xP$. $N$ là bậc của điểm $P$ thường là
số nguyên tố lớn.
Thuật toán sinh chữ kí số ElGamal:
Thuật toán Xác thực chữ ký số Elgamal:
*Chứng minh tính đúng đắn của thuật toán: khi m′ = m:*
*Đánh giá bảo mật*: Muốn giả mạo chữ ký số, Hacker buộc phải tính được $s$, để tính được $s$ buộc phải tính được $k$ và khóa bí mật $x$, để tính được 2 giá trị này Hacker phải giải bài toán Logarithm rời rạc $k = log_P R$ và $x = log_P Y$, là 2 bài toán không giải được trong thời gian đa thức.
## 2.5 Mã hóa - Giải mã
### 2.5.1 Mã hóa Massey-Omura
Massey-Omura là hai tác giả để xuất lược đồ mã hóa được mô tả trong Patent vào năm 1986. Lược đồ mã hóa này ít được sử dụng trong thực tế nhưng nó có ý nghĩa về mặt lịch sử
Dễ dàng nhận thấy:
$m^{−1}_B m^{−1}_A m_Bm_AM = M$
*Đánh giá bảo mật*: Muốn phá khóa trong lược đồ này, Hacker phải tìm được giá trị $m_A, m_B$ để tìm được các giá trị này Hacker phải lần lượt giải 2 bài toán Logarithm rời rạc $m_A = log_M M_1$ và $m_B = log_{M_1} M_2$, và đây là 2 bài toán chưa giải được trong thời gian đa thức.
### 2.5.2 Mã hóa ElGamal
*Chứng minh tính đúng đắn của lược đồ mã hóa:*
$M = M_2 − x_BM_1 = M + kY_B − x_BM_1 = M + k(x_BP) − x_B(kP) = M$
*Đánh giá bảo mật*: Để giải mã được văn bản $M$, Hacker buộc phải tìm được $k$ và $x_B$, do đó Hacker cần phải giải 2 bài toán Logarithm rời rạc $k = log_P M_1$ và $xB = log_P Y_B$, và đây là 2 bài toán khó.
### 2.5.3 Mã hóa ECIES (The Elliptic Curve Integrated Encryption System)
Tham số $D = (q, FR, S, a, b, P, n, h)$ được chọn tương tự như với ECDSA. Ở đây cần lựa chọn thêm các hàm mã hóa/giải mã đối xứng ký hiệu là $E_k(m)$ và $D_k(c)$.
Trong đó $m$ là bản rõ cần mã hóa, $c$ là bản đã được mã. Thuật toán mã hóa đối xứng được chọn ở đây để phục vụ quá trình mã hóa/giải mã được dễ dàng hơn và nhanh hơn so với các thuật toán bất đối xứng. Ngoài ra thay vì sử dụng hàm băm đơn giản, ECIES sẽ sử dụng hai hàm băm sau:
Người nhận có cặp khóa công khai/bí mật là $(Y, x)$ trong đó $Y = xP$
Thuật toán mã hóa ECIES:
Bên giải mã sẽ nhận được tập hợp $(U, c, r)$ gồm các thành phần sau:
- $U$ cần thiết để tính khóa phiên Diffie–Hellman T.
- $c$ là bản đã được mã hóa.
- $r$ được dùng để xác thực mã văn bản.
Thuật toán giải mã ECIES:
Khóa phiên T sau khi được tính trong phần giải mã sẽ có giá trị giống như trong phần mã hóa. Thực vậy:
Đánh giá bảo mật: Để phá khóa được lược đồ này Hacker cần phải tìm được khóa bí mật x hoặc giá trị k bằng cách giải bài toán $x = log_P Y$ hoặc $k = log_P U$, và đây là 2 bài toán khó chưa giải được trong thời gian đa thức.
# Writeups ELLIPTIC CURVES - CRYPTOHACK
## Background Reading
"Thử thách" này chỉ cung cấp một lượng kiến thức nền tảng về đường cong elip. Nó giải thích các đường cong là gì, cách chúng ta thao tác trên chúng và một số thuộc tính. Đối với thử thách :
The flag is the name we give groups with a commutative operation.
Flag: `crypto{abelian}`.
## Point Negation
E: $Y^2 = X^3 + 497 X + 1768$, $p: 9739$
P(8045,6936), find the point Q(x,y) such that P + Q = O.
Q=-P= (8045, -6936 (mod 9739)) (P nghịch đảo là Q)
Q=(8045,2803)
## Point Addition
E: $Y^2 = X^3 + 497 X + 1768$, $p: 9739$
P = (493, 5564), Q = (1539, 4742), R = (4403,5202),
find the point S(x,y) = P + P + Q + R
Dùng thuật toán cộng điểm để tính điểm S = 2P + Q + R;
Sau khi tính được S có thể thay tọa độ S vào E để kiểm tra.
Ta dùng thuật toán cộng điểm đã ttrìnhbayf ở trên tiến hành cộng từng điểm 1,rồi lấy kết quả cộng với điểm tiếp theo.Cụ thể tính 2P trước sau đó tính 2P + Q và cuối cùng 2P + Q + R.
```python
from Crypto.Util.number import inverse
# Add 2 point in Eliptic Curve
E: $Y^2 = X^3 + 497 X + 1768$, $p: 9739$
p = 9739
a = 497
b = 1768
def add_points(p1,p2):
#p1 = (x1,y1),p2=(x2,y2)
if p1 == (0,0):
return p2
if p2 == (0,0):
return p1
x1,y1 = p1
x2,y2 = p2
if x1 == x2 and y1 == -y2: # p1 = -p2
return (0,0)
if p1 == p2 : # Dung thuat toan nhan doi diem
s1 = (3*pow(x1,2,p)+a) %p
s2 = (2*y1)%p
s = s1*inverse(s2,p)
else:
s1 = (y2-y1)%p
s2 = (x2-x1)%p
s = s1*inverse(s2,p)
x3 = ((s*s)-x1-x2)%p
y3 = (s*(x1-x3)-y1)%p
# s la lamda
return (x3,y3)
P = (493,5564)
Q = (1539,4742)
R = (4403,5202)
S = add_points(add_points(add_points(P,P),Q),R)
print(S)
assert pow(S[1],2,p) == (pow(S[0],3,p)+ a*S[0]+b)%p
```
Tìm được S =(4215, 2162)
Dùng sage
```python!
Z9739 = Zmod(9739)
E = EllipticCurve(Z9739, [497,1768])
P = E([493, 5564])
Q = E([1539, 4742])
R = E([4403,5202])
print(E)
print(" P + P + Q + R =", (P+P+Q+R).xy())
```
## Scalar Multiplication
E: $Y^2 = X^3 + 497 X + 1768$, $p: 9739$
Challnge cho thuật toán
points P = (2339, 2213), find the point Q(x,y) = 7863 P
Yêu cầu tìm điểm Q(x,y) = 7863P.
```python
from Crypto.Util.number import inverse
p = 9739
a = 497
b = 1768
def add_points(p1,p2):
#p1 = (x1,y1),p2=(x2,y2)
if p1 == (0,0):
return p2
if p2 == (0,0):
return p1
x1,y1 = p1
x2,y2 = p2
if x1 == x2 and y1 == -y2: # p1 = -p2
return (0,0)
if p1 == p2 : # Dung thuat toan nhan doi diem
s1 = (3*pow(x1,2,p)+a) %p
s2 = (2*y1)%p
s = s1*inverse(s2,p)
else:
s1 = (y2-y1)%p
s2 = (x2-x1)%p
s = s1*inverse(s2,p)
x3 = ((s*s)-x1-x2)%p
y3 = (s*(x1-x3)-y1)%p
# s la lamda
return (x3,y3)
def scalar_mult(n, P):
Q, R = P, (0, 0)
while n > 0:
if n % 2 == 1:
R = add_points(R, Q)
Q = add_points(Q, Q)
n //= 2
return R
x = (5323, 5438)
assert scalar_mult(1337, x) == (1089, 6931)
P = (2339, 2213)
Q = scalar_mult(7863,P)
print(Q) #(9467, 2742)
```
## Curves and Logs
```
Alice generates a secret random integer nA and calculates QA = nAG
Bob generates a secret random integer nB and calculates QB = nBG
Alice sends Bob QA, and Bob sends Alice QB. Due to the hardness of ECDLP, an onlooker Eve is unable to calculate nA/B in reasonable time.
Alice then calculates nAQB, and Bob calculates nBQA.
Due to the associativity of scalar multiplication, S = nAQB = nBQA.
Alice and Bob can use S as their shared secret.
Using the curve, prime and generator:
E: Y2 = X3 + 497 X + 1768, p: 9739, G: (1804,5368)
Calculate the shared secret after Alice sends you QA = (815, 3190), with your secret integer nB = 1829.
Generate a key by calculating the SHA1 hash of the x coordinate (take the decimal representation of the coordinate and cast it to a string). The flag is the hexdigest you find.
```
Challeng giới thiệu về cách Alice và Bob tọa ra $Q_A,Q_B$ với số nguyên ngẫu nhiên $n_A,n_B$ và 1 điểm cơ sở $G$
$Q_A = n_AG$ ,$Q_B = n_BG$
Để tạo ra shared secret : $S = n_A*Q_B = n_B*Q_A$
Flag = tọa độ x của S(x,y) ở dạng hash SHA1
Ta có thể dùng các hàm ở challenge trước để tìm flag
```python
from Crypto.Util.number import inverse
import hashlib
p = 9739
a = 497
b = 1768
def add_points(p1,p2):
#p1 = (x1,y1),p2=(x2,y2)
if p1 == (0,0):
return p2
if p2 == (0,0):
return p1
x1,y1 = p1
x2,y2 = p2
if x1 == x2 and y1 == -y2: # p1 = -p2
return (0,0)
if p1 == p2 : # Dung thuat toan nhan doi diem
s1 = (3*pow(x1,2,p)+a) %p
s2 = (2*y1)%p
s = s1*inverse(s2,p)
else:
s1 = (y2-y1)%p
s2 = (x2-x1)%p
s = s1*inverse(s2,p)
x3 = ((s*s)-x1-x2)%p
y3 = (s*(x1-x3)-y1)%p
# s la lamda
return (x3,y3)
def scalar_mult(n, P):
Q, R = P, (0, 0)
while n > 0:
if n % 2 == 1:
R = add_points(R, Q)
Q = add_points(Q, Q)
n //= 2
return R
G = (1804,5368)
nB = 1829
QA = (815, 3190)
S = scalar_mult(nB,QA)
print(S) # (7929, 707)
m = hashlib.sha1()
m.update(str(S[0]).encode())
print(m.hexdigest()) #80e5212754a824d3a4aed185ace4f9cac0f908bf
```
## Efficient Exchange
Challenge cho file
decrypt.py
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
shared_secret = ?
iv = ?
ciphertext = ?
print(decrypt_flag(shared_secret, iv, ciphertext))
```
```
For these challenges, we have used a prime p ≡ 3 mod 4, which will help you find y from y2.
E: Y^2 = X^3 + 497 X + 1768, p: 9739, G: (1804,5368)
Calculate the shared secret after Alice sends you q_x = 4726, with your secret integer nB = 6534.
Use the decrypt.py file to decode the flag
{'iv': 'cd9da9f1c60925922377ea952afc212c',
'encrypted_flag': 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'}
```
Challenge cho Tọa độ x của $Q_A$ ,$x_{Q_A}$ = 4726
Từ $x_{Q_A}$ ta có thể tính được ${y_{Q_A}}^2$ theo phương trình Y^2 = X^3 + 497 X + 1768
Theo điều kiện đã biết p ≡ 3 mod 4 ta có thể tìm được $y_{Q_A}$ từ ${y_{Q_A}}^2$
```python
q_x = 4726
y2 = q_x**3 + a*q_x +b #105557919766
y = pow(y2,(p+1)//4,p)#6287
```
Sau khi tìm được $Q_A$ = (4726,6287), ta tìm shared secret như challenge trước sau đó thay vào decrypt.py để tìm flag.
```python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from curveandlogs import add_points,scalar_mult,a,b,p
import hashlib
def is_pkcs7_padded(message):
padding = message[-message[-1]:]
return all(padding[i] == len(padding) for i in range(0, len(padding)))
def decrypt_flag(shared_secret: int, iv: str, ciphertext: str):
# Derive AES key from shared secret
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
# Decrypt flag
ciphertext = bytes.fromhex(ciphertext)
iv = bytes.fromhex(iv)
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = cipher.decrypt(ciphertext)
if is_pkcs7_padded(plaintext):
return unpad(plaintext, 16).decode('ascii')
else:
return plaintext.decode('ascii')
q_x = 4726
y2 = q_x**3 + a*q_x +b #105557919766
y = pow(y2,(p+1)//4,p)#6287
QA = (q_x,y)
nB = 6534
S = scalar_mult(nB,QA)
shared_secret = S[0]
iv = 'cd9da9f1c60925922377ea952afc212c'
ciphertext = 'febcbe3a3414a730b125931dccf912d2239f3e969c4334d95ed0ec86f6449ad8'
print(decrypt_flag(shared_secret, iv, ciphertext))
#crypto{3ff1c1ent_k3y_3xch4ng3}
```
Sign in with Wallet
Connect another wallet