Đối với một đường cong elliptic E trên F(2^m) có phương trình Y² + XY = X³ + aX² + b:

- Nếu P = O_E và Q = O_E,

thì f(P,Q,R) = 1_F;

- ngược lại, nếu P = O_E,

thì f(P,Q,R) = x_R + x_Q;

- ngược lại, nếu Q = O_E,

thì f(P,Q,R) = x_R + x_P;

- ngược lại, nếu x_P ≠ x_Q,

thì f(P, Q, R) = (x_Q + x_P)y_R + (y_Q + y_P)x_R + x_Qy_P + x_Py_Q;

...

...

...

thì f(P,Q,R) = x_R + x_P;

- ngược lại, nếu x_P = x_Q = 0_F và y_P = y_Q = √b

thì f(P, Q, R) = x_R;

- ngược lại,

thì f(P, Q, R) = (y_P + x_P²)(x_R + x_P) + x_P(y_R + y_P) = (y_R + y_P)² + (x_R + x_P)[y_R + y_P + (x_R + x_P)(a + x_R)].

Đối với một đường cong elliptic E trên F(3^m) có phương trình Y² = X³ + aX² + b:

- Nếu P = O_E và Q = O_E,

thì f(P,Q,R) = 1_F;

- ngược lại, nếu P = O_E,

...

...

...

- ngược lại, nếu Q = O_E,

thì f(P,Q,R) = x_R - x_P;

- ngược lại, nếu x_P ≠ x_Q,

thì f(P,Q,R) = (x_Q - x_P)y_R - (y_Q - y_P)x_R - x_Qy_P + x_Py_Q;

- ngược lại, nếu y_P ≠ y₀,

thì f(P,Q,R) = x_R - x_P;

- ngược lại, nếu b = 0_F và x_P = y_P = x_Q = y_Q = 0_F

thì f(P,Q,R) = x_R;

- ngược lại,

...

...

...

Hàm g(P, Q ,P) định nghĩa với P, Q, R ϵ E(F(q^B)) là g(P, Q, R) = f(P, Q, P) / (P + Q, -P - Q, R).

Hàm d_n(P, Q) cho hai điểm P và Q trên E với cấp n > 2 được tính toán sử dụng thuật toán sau đây.

a) Cho n = n_l-12^l-1 + ... + n₁2 + n₀ (n_l-1 ≠ 0) là một biểu diễn nhị phân, trong đó n_i = 0,1.

b) Đặt Y := P, h := 1.

c) Với i = l - 2 đến 0, thực hiện:

1) h := h² ∙ g(Y, Y, Q),Y := 2Y;

2) Nếu n_i ≠ 0, thì

h := h ∙ g(Y, Y, Q);

Y := Y + P.

...

...

...

C.6.2  Thuật toán để tính phép ghép cặp Weil

Cho G₁ và G₂ là hai điểm trên E với nG₁ = nG₂ = O_E. Phép ghép cặp Weil e_n(G₁, G₂) được tính toán theo các bước sau:

a) Chọn ngẫu nhiên một điểm R trên E sao cho O_E, G₂, R, G₁ + R đều khác nhau.

b) Tính e_n(G₁, G₂) = [d_n(G₂, R)d_n(G₁, G₂ - R)] / [d_n(G₂, G₁ + R)d_n(G₁, -R)].

c) Nếu xuất hiện phép chia cho 0 trong quá trình tính toán ở trên, thì bắt đầu lại với một điểm R mới.

C.6.3  Thuật toán để tính phép ghép cặp Tate

Cho G₁ và G₂ là hai điểm trên E với nG₁ = nG₂ = O_E. Cặp Tate e_n(G₁, G₂) được tính toán theo các bước sau:

a) Chọn ngẫu nhiên một điểm R trên E.

b) Tính e_n(G₁, G₂) = dn(G₁, G₂ - R) / dn(G₁, -R).

...

...

...

C.7  Phê chuẩn tham số miền đường cong elliptic và khóa công khai (tùy chọn)

C.7.1  Giới thiệu chung

Trong C.7.1 mô tả các tham số miền đường cong elliptic và cách thức kiểm tra các tham số này. Một tập hợp các tham số miền cụ thể có thể được các bên liên quan thỏa thuận để sử dụng cho một mục đích hoặc cho nhiều mục đích.

Nếu một tập hợp các tham số miền ứng viên là không hợp lệ, thì tất cả các giả thiết về độ an toàn sẽ được giả định là vô hiệu, bao gồm độ an toàn dự kiến cho mọi hoạt động mật mã tùy ý và tính bí mật của khóa riêng. Do đó, trước khi sử dụng một tập hợp các tham số miền ứng viên, người dùng phải đảm bảo rằng nó là hợp lệ. Đảm bảo này có thể đạt được vì:

- Các tham số miền được sinh bởi người dùng hoặc cho người dùng bởi bên thứ ba đáng tin cậy, hoặc

- Các tham số miền đã được người dùng hoặc bên thứ ba đáng tin cậy kiểm tra kỹ lưỡng.

C.7.2  Phê chuẩn tham số miền đường cong elliptic trên F(q)

Các điều kiện sau đây phải được người dùng các tham số đường cong elliptic kiểm tra.

a) Kiểm tra q là một lũy thừa của một số nguyên tố, p^m.

...

...

...

c) Kiểm tra 4a³ + 27b² ≠ 0 nếu q = p^m với p > 3, b ≠ 0 nếu q = 2^m, và a, b ≠ 0 nếu q = 3^m.

d) Nếu đường cong elliptic được sinh giả ngẫu nhiên, kiểm tra rằng a và b được dẫn xuất từ MẦM.

e) Nếu q = p^m với p > 3, kiểm tra trong F(q). Nếu q = 2^m, kiểm tra trong F(2^m).

Nếu q = 3^m, kiểm tra trong F(3^m).

f) Kiểm tra n là số nguyên tố và n > 4√q.

LƯU Ý: n là tham số an toàn chính. Các giới hạn cụ thể có trong mô tả của các thuật toán.

g) Kiểm tra nG = O_E.

h) Tính h' = [( + 1)² / n] và kiểm tra h = h'.

i) Kiểm tra danh sách để loại trừ các đường cong yếu đã biết:

...

...

...

- Kiểm tra đường cong không phải là đường cong bất quy tắc, tức là #E(F(q)) ≠ q.

Nếu bất kỳ bước kiểm tra nào ở trên không thành công, thì tham số miền được coi là không hợp lệ.

C.7.3  Phê chuẩn khóa công khai (tùy chọn)

Cho trước một tập hợp các tham số miền đường cong elliptic hợp lệ và một khóa công khai được xác nhận có liên quan Q với các tọa độ nhất định và một cấp nhất định, khóa công khai được phê chuẩn như sau:

a) Kiểm tra Q không phải là điểm tại vô hạn O_E.

b) Kiểm tra x_Q và y_Q là các phần tử trong trường F(q), trong đó x_Q và y_Q là tọa độ x và y của Q tương ứng.

c) Nếu q = p^m với p > 3, kiểm tra trong F(q). Nếu q = 2^m, kiểm tra hoặc trong F(2^m). Nếu q = 3^m, kiểm tra hoặc trong F(3^m).

d) Kiểm tra nQ = O_E.

Nếu bất kỳ bước kiểm tra nào ở trên không thành công, thì khóa công khai được coi là không hợp lệ.

...

...

...

- Khóa công khai được người dùng phê chuẩn một cách rõ ràng,

- Khóa công khai được phê chuẩn một cách rõ ràng bởi TTP cho người dùng,

- Người dùng chấp nhận rủi ro khi sử dụng khóa công khai không được phê chuẩn,

LƯU Ý 1: Điều này bao gồm một phân tích cho thấy tiềm năng an toàn bị hạn chế trong ứng dụng cụ thể. Việc chấp nhận rủi ro đó có thể phù hợp với khóa công khai tức thời hơn so với khóa công khai dài hạn. Lưu ý rằng việc thực hiện phê chuẩn khóa công khai EC là một mặc định an toàn, vì không có hậu quả an toàn tiêu cực tiềm ẩn nào khi thực hiện.

- Một khóa công khai không được kiểm tra có thể được sử dụng trong các điều kiện khóa được sinh hoặc xác nhận tính hợp lệ một cách rõ ràng bởi một thực thể được người dùng tin cậy trong suốt vòng đời của khóa.

LƯU Ý 2: Phê chuẩn khóa công khai không đảm bảo rằng chủ sở hữu đã xác nhận quyền sở hữu khóa riêng là chủ sở hữu thực sự của khóa.

Phụ lục D

(tham khảo)

...

...

...

Các tính chất của các hệ tọa độ khác nhau được tổng hợp lại. Trong trường hợp E(F(q)) với p > 3, có năm hệ tọa độ, tọa độ affine, tọa độ xạ ảnh, tọa độ Jacobi, tọa độ Jacobi sửa đổi và tọa độ hỗn hợp. Trong các trường hợp của F(F(2^m)) và F(F(3^m)), có hai hệ tọa độ, tọa độ affine và tọa độ xạ ảnh.

Ký hiệu tọa độ affine, tọa độ xạ ảnh, tọa độ Jacobi và tọa độ Jacobi sửa đổi bằng A, P, J và J_m; thời gian cho phép cộng hai điểm theo tọa độ C₁ và C₂ cho kết quả trong tọa độ C₃ là t(C₁ + C₂ = C₃); thời gian cho phép nhân đôi một điểm theo tọa độ C₁ cho kết quả trong tọa độ C₂ là t(2C₁ = C₂); và phép nhân (tương ứng, nghịch đảo, tương ứng, bình phương) trong F(q) bằng M (tương ứng, I, tương ứng, S_q). Bảng D.1 tổng hợp các tọa độ của E(F(q) với p > 3. Bảng D.2 tổng hợp các tọa độ của F(F(2^m)). Bảng D.3 tổng hợp các tọa độ của E(F(3^m)).

Bảng D.1 - Tổng hợp các tọa độ của E(F(q)) với p > 3

Phép nhân đôi điểm

Phép cộng điểm

Hoạt động

Thời gian tính toán

Hoạt động

Thời gian tính toán

...

...

...

7M + 5S_q

t(J_m + J_m)

13 M + 6S_q

t(2J)

4M + 6S_q

t(J + J)

12M + 4S_q

t(2J_m)

7M + 5S_q

...

...

...

12M + 2S_q

t(2J_m = J)

7M + 5S_q

t(J + A = J_m)

9M + 5S_q

t(2A = J_m)

3M + 4S_q

t(J_m + A = J_m)

9M + 5S_q

...

...

...

2M + 4S_q

t(J + A = J)

8M + 3S_q

-

-

t(J_m + A = J)

8M + 3S_q

-

-

...

...

...

5M + 4S_q

t(2A)

2M + 2S_q + I

t(A + A)

2M + S_q + I

Bảng D.2 - Tổng hợp các tọa độ của E(F(2^m))

Phép nhân đôi điểm

Phép cộng điểm

Hoạt động

...

...

...

Hoạt động

Thời gian tính toán

t(2P)

7M + 5S_q

t(P + P)

16M + 2S_q

t(2A)

2M + S_q + 1

t(A + A)

...

...

...

Bảng D.3 - Tổng hợp các tọa độ của E(F(3^m))

Phép nhân đôi điểm

Phép cộng điểm

Hoạt động

Thời gian tính toán

Hoạt động

Thời gian tính toán

t(2P)

9M + 3S_q

...

...

...

15M + 2S_q

t(2A)

3M + S_q + I

t(A + A)

2M + S_q + I

Thư mục tài liệu tham khảo

[1] ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)

[2] ANSI X9.63-2001, Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography

...

...

...

[4] AVANZI R., COHEN H., DOCHE C., FREY G., LANGE T., NGUYEN K. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Chapman & Hall/CRC, 2005

[5] COHEN H. "A course in computational algebraic number theory", Graduate Texts in Math. 138, Springer-Verlag, 1993, Fourth printing, 2000

[6] COHEN H., MIYAJI A., ONO T. "Efficient elliptic curve exponentiation using mixed coordinates", Advances in Cryptology -Proceedings of ASIACRYPT'98, Lecture Notes in Computer Science, 1514 (1998), Springer-Verlag, 51-65

[7] FREY G., & RUCK H.G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 1994, 62 pp. 865-874

[8] KILLMANN W., LANGE T., LOCHTER M., THUMSER W., WICKE G. "Minimum Requirements for Evaluating Side-Channel Attack Resistance of Elliptic Curve Implementations", version 1.0.4 Federal Office for Information Security, 2011

[9] PETER L. Montgomery, "Speeding up the Pollard and elliptic curve methods offactorization", Mathematics of Computation. Fundamentals. 1987, 48 (177) pp. 243-264

[10] MENEZES A., OKAMOTO T., VANSTONE S. "Reducing elliptic curve logarithms to logarithms in a finite field", Proc. twenty-third Annual ACM Symposium on the Theory of Computing (1991), 80-89

[11] MAMIYA H., MIYAJI A., MORIMOTO H. "Secure elliptic curve exponentiation against RPA, ZRA, DPA, and SPA", IEICE Trans. Fundamentals. 2006, 89-A (8) pp. 2207-2215

[12] SATOH T., & ARAKI K. Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Commentarii Math. Univ. St. Pauli. 1998, 47 pp. 81-92

...

...

...

[14] SMART N.P. The discrete logarithm problem on elliptic curves of trace one.J. Cryptol. 1999, 12 pp. 193-196

[15] WASHINGTON L.C. Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, 2003

[16] WATERHOUSE W. “Abelian varieties over finite fields”, Ann. scient. Éc. Norm. Sup. 1969, 2 pp. 521-560

[17] GOUNDAR R., JOYE M., MIYAJI A., RIVAIN M., VENELLI A. "Scalar multiplication on weierstrass elliptic curves from Co-Z arithmetic”, Journal of Cryptographic Engineering, vol. 1 (2011), Springer-Verlag, 161-176

MỤC LỤC

Lời nói đầu

1  Phạm vi áp dụng

2  Tài liệu viện dẫn

...

...

...

4  Các ký hiệu

5  Quy ước cho các trường

5.1  Trường nguyên tố hữu hạn F(p)

5.2  Các trường hữu hạn F(pm)

6  Các quy ước trên đường cong elliptic

6.1  Định nghĩa các đường cong elliptic

6.2  Luật nhóm trên các đường cong elliptic

6.3  Sinh các đường cong elliptic

6.4  Ánh xạ song tuyến tính mật mã

...

...

...

7.1  Chuyển đổi xâu bộ tám/xâu bit: OS2BSP và BS2OSP

7.2  Chuyển đổi xâu bit/số nguyên: BS2IP và I2BSP

7.3  Chuyển đổi xâu bộ tám/số nguyên: OS2IP và I2OSP

7.4  Chuyển đổi phần tử trên trường hữu hạn/số nguyên: FE2IPF

7.5  Chuyển đổi xâu bộ tám/phần tử của trường hữu hạn: OS2FEPF và FE2OSPF

7.6  Chuyển đổi điểm đường cong elliptic/xâu bộ tám: EC2OSPE và OS2ECPE

7.7  Chuyển đổi số nguyên/đường cong elliptic: I2ECP

8  Các tham số miền đường cong Elliptic và khóa công khai

8.1  Các tham số miền đường cong elliptic trên F(q)

...

...

...

Phụ lục A (tham khảo) Kiến thức cơ bản về các trường hữu hạn

Phụ lục B (tham khảo) Kiến thức cơ bản về các đường cong elliptic

Phụ lục C (tham khảo) Kiến thức cơ bản về các hệ mật trên đường cong elliptic

Phụ lục D (tham khảo) Tổng hợp các hệ tọa độ

Thư mục tài liệu tham khảo

Tiêu chuẩn quốc gia TCVN 12852-1:2020 (ISO/IEC 15946-1:2016) về Công nghệ thông tin - Các kỹ thuật an toàn - Kỹ thuật mật mã dựa trên đường cong elliptic - Phần 1: Tổng quan