Tiêu chuẩn Quốc gia TCVN 12852-1:2020 ISO/IEC 15946-1:2016 Kỹ thuật mật mã dựa trên đường cong elliptic

TIÊU CHUẨN QUỐC GIA

TCVN 12852-1 : 2020

ISO/IEC 15946-1 : 2016

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

Information technology - Security techniques - Cryptography based on elliptic curves - Part 1: General

Lời nói đầu

TCVN 12852-1 : 2020 hoàn toàn tương đương với ISO/IEC 15946-1:2016.

TCVN 12852-1 : 2020 do Cục Quản lý mật mã dân sự và Kiểm định sản phẩm mật mã biên soạn, Ban Cơ yếu Chính phủ đề nghị, Tổng cục Tiêu chuẩn Đo lường Chất lượng thẩm định, Bộ Khoa học và Công nghệ công bố.

Bộ tiêu chuẩn TCVN 12852 (ISO/IEC 15946) Công nghệ thông tin - Các kỹ thuật an toàn - Mật mã hạng nhẹ gồm các tiêu chuẩn sau:

- TCVN 12852-1 : 2020 (ISO/IEC 15946-1:2016) Phần 1: Tổng quan

- TCVN 12852-5 : 2020 (TCVN 12852-5:2017) Phần 5: Sinh đường cong elliptic

Bộ tiêu chuẩn này có thể có các phần tiếp theo.

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

Information technology - Security techniques - Cryptography based on elliptic curves - Part 1: General

1  Phạm vi áp dụng

Tiêu chuẩn này mô tả nền tảng toán học và các kỹ thuật chung cần thiết để thực hiện các cơ chế mật mã trên đường cong elliptic được mô tả trong các tiêu chuẩn TCVN 12852-5, TCVN 12855-3, TCVN 7817-3, TCVN 12214-3, TCVN 11367-2 và các tiêu chuẩn có liên quan.

Tiêu chuẩn này không chỉ ra việc thực thi các kỹ thuật mà nó mô tả. Ví dụ, nó không mô tả phép biểu diễn cơ sở được sử dụng khi đường cong elliptic định nghĩa trên trường hữu hạn có đặc số hai. Do đó, các cơ chế bên trong của các sản phẩm tuân thủ theo tiêu chuẩn sẽ không được đảm bảo.

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

Các tài liệu viện dẫn sau rất cần thiết cho việc áp dụng tiêu chuẩn này. Đối với những tài liệu viện dẫn có năm công bố, thì áp dụng phiên bản được nêu. Đối với tài liệu viện dẫn không ghi năm công bố, thì áp dụng phiên bản mới nhất (bao gồm cả các sửa đổi, bổ sung).

TCVN 12852-5:2020 (ISO/IEC 15946-5), 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 5: Sinh đường cong elliptic.

3  Thuật ngữ và định nghĩa

Tiêu chuẩn này áp dụng các thuật ngữ và định nghĩa sau:

3.1

Nhóm Abel (abelian group)

Nhóm (S,*) sao cho a * b = b * a với mọi a, b ϵ S

3.2

Đường cong bậc ba (cubic curve)

Tập hợp các nghiệm, tạo ra bởi các cặp phần tử của một trường xác định, được biết như là các điểm, của một phương trình bậc ba ở dạng đặc biệt.

3.3

Đường cong elliptic (elliptic curve)

Đường cong bậc ba E mà không có điểm kỳ dị

CHÚ THÍCH 1  Tập các điểm E cùng với một phép toán được định nghĩa một cách thích hợp (xem mục 6.2) tạo thành một nhóm abel. Trường bao gồm tất cả các hệ số của phương trình mô tả E được gọi là trường định nghĩa của E. Trong tiêu chuẩn này, chỉ các trường hữu hạn F được sử dụng làm trường xác định. Khi cần biểu thị trường định nghĩa F của E một cách rõ ràng, đường cong được ký hiệu là E/F.

CHÚ THÍCH 2  Dạng của một phương trình đường cong bậc ba sử dụng để định nghĩa một đường cong elliptic thay đổi phụ thuộc vào trường. Dạng tổng quát của một phương trình bậc ba phù hợp cho tất cả các trường hữu hạn được định nghĩa trong 6.1

CHÚ THÍCH 3  Định nghĩa của một đường cong bậc ba được đưa ra trong tài liệu viện dẫn [15].

3.4

Trường (field)

Tập các phần tử S và một cặp các phép toán (+, *) định nghĩa trên S sao cho: (i) a*(b + c) = a*b + a*c với mọi a, b, c thuộc S, (ii) S cùng với phép toán + tạo thành một nhóm albel (với phần tử trung hòa 0) và (iii) S loại bỏ phần tử 0 cùng với phép toán * tạo thành một nhóm abel.

3.5

Trường hữu hạn (finite field)

Trường bao gồm một số hữu hạn các phần tử

CHÚ THÍCH  Với số nguyên dương m và số nguyên tố p tùy ý, tồn tại một trường hữu hạn chứa chính xác p^m phần tử. Trường này là duy nhất sai khác đẳng cấu và được ký hiệu là F(p^m) với p được gọi là đặc số của F(p^m).

3.6

Nhóm (group)

Tập hợp các phần tử S và một phép toán * xác định trên tập các phần tử sao cho (i) a * (b*c) = (a*b)*c với mọi a, b, c thuộc S, (ii) tồn tại một phần tử trung hòa e thuộc S sao cho a*e = e*a = a với mọi a thuộc S, và (iii) với mọi a thuộc S tồn tại phần tử nghịch đảo a^-1 trong S sao cho a*a^-1 = a^-1 * a = e

3.7

Ánh xạ mật mã song tuyến tính (cryptographic bilinear map)

Ánh xạ thỏa mãn tính không suy biến, song tuyến tính và có thể tính toán được.

CHÚ THÍCH 1  Định nghĩa của tinh không suy biến, song tuyến tính và có thể tính toán được được cho trong 6.4

3.8

Điểm kỳ dị (signular point)

Điểm mà tại đó một đối tượng toán học cho trước không được xác định.

4  Các ký hiệu

B          Số nguyên dương nhỏ nhất sao cho n chia hết q^B - 1

d          Khóa bí mật của người dùng (d là một số nguyên ngẫu nhiên trong tập [2, n-2])

E          Đường cong elliptic cho bởi phương trình có dạng Y² = X³ + aX + b trên trường F(p^m) với p > 3, hoặc cho bởi một phương trình có dạng Y² + XY = X³ + aX² + b trên trường F(2^m), hoặc cho bởi phương trình Y² = X³ + aX² + b trên trường F(3^m), cùng với một điểm O_E được gọi là điểm tại vô hạn; đường cong được ký hiệu là E / F(p^m), E / F(2^m) và E / F(3^m), tương ứng.

E(F(q))  Tập các điểm có tọa độ thuộc F(q) của E cùng với O_E

#E(F(q))  Cấp hoặc lực lượng của E(F(q))

E(n)  Nhóm n-xoắn của E, tức là {Q ϵ E| nQ = O_E}

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

|F|  Số phần tử trong F

F(q)  Trường hữu hạn gồm có chính xác q phần tử, bao gồm các trường hợp F(p), F(2^m) và F(p^m)

F(q)*  F(q)\{0_F}

G  Điểm cơ sở trên E với cấp nguyên tố n

<G>  Nhóm được sinh bởi G với cấp nguyên tố n

h  Đồng hệ số của E(F(q))

kQ  Bội thứ k của một điểm Q nào đó của E, tức là kQ = Q +...+ Q (k lần phép cộng) nếu k > 0, kQ = (-k)(-Q), nếu k < 0, và kQ = O_E nếu k = 0

µ_n  Nhóm cyclic cấp n gồm các căn bậc n của phần tử đơn vị trong bao đóng đại số của F(q)

n  Ước nguyên tố của #E(F(q))

O_E  Điểm của đường cong elliptic tại vô hạn

p  Số nguyên tố

P  khóa công khai của người dùng (P là một điểm đường cong elliptic trong <G>)

q  Lũy thừa nguyên tố p^m của một số nguyên tố p và số nguyên m ≥ 1 nào đó

Q  Điểm trên E với các tọa độ (x_Q, y_Q)

Q₁ + Q₂  Tổng của hai điểm Q₁ và Q₂ trên đường cong elliptic

x_Q  Tọa độ x của Q ≠ O_E

y_Q  Tọa độ y của Q # O_E

[0,k]  Tập các số nguyên từ 0 đến k

0_F  Phần tử trung hòa của F(q) đối với phép cộng

1_F  Phần tử trung hòa của F(q) đối với phép nhân

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

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

Với số nguyên tố p bất kỳ, tồn tại một trường hữu hạn chứa chính xác p phần tử. Trường này được xác định duy nhất sai khác đẳng cấu và trong tiêu chuẩn này nó được gọi là trường nguyên tố hữu hạn F(p).

Các phần tử của trường nguyên tố hữu hạn F(p) có thể được đồng nhất với tập [0, p-1] gồm tất cả các số nguyên không âm nhỏ hơn p. F(p) được cung cấp 2 phép toán gọi là phép toán cộng và phép toán nhân sao cho các điều kiện sau được thỏa mãn:

- F(p) là một nhóm abel đối với phép toán cộng "+”

Với a,b ϵ F(p) tổng a + b được định nghĩa là a + b:= r, trong đó r ϵ F(p) là phần dư thu được khi lấy số nguyên tổng a + b chia cho p.

- F(p)\{0}, ký hiệu F(p)* là một nhóm abel với phép toán nhân “x”.

Với a, b ϵ F(p) tích a x b được định nghĩa là a x b := r, trong đó r ϵ F(p) là phần dư thu được khi lấy số nguyên tích a x b chia cho p. Khi không sợ gây nhầm lẫn, thì dấu x được lược bỏ và ký hiệu thay thế là a.b hoặc ab được sử dụng.

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

Với số nguyên dương m và số nguyên tố p bất kỳ, tồn tại một trường hữu hạn có chính xác p^m phần tử. Trường này là duy nhất sai khác đẳng cấu và trong tiêu chuẩn này nó được gọi là trường hữu hạn F(p^m)

CHÚ THÍCH 1  F(p^m) là định nghĩa tổng quát bao gồm cả F(p) với m = 1 và F(2^m) với p = 2.

CHÚ THÍCH 2  Nếu p = 2 thì các phần tử của trường có thể được đồng nhất với các xâu bit có độ dài m và tổng của hai phần tử trường là phép loại trừ XOR theo từng bit của hai xâu bit.

Trường hữu hạn F(p^m) có thể được đồng nhất với tập các xâu p-phân với độ dài m theo cách sau đây.

Mỗi trường hữu hạn F(p^m) chứa ít nhất một cơ sở {z₁, z₂..., z_m} trên trường F(p) sao cho mọi phần tử a ϵ F(p^m) có một biểu diễn duy nhất dưới dạng a = a₁z₁ + a₂z₂ +... + a_mz_m, trong đó a_i ϵ F(p) với i = 1, 2..., m. Khi đó phần tử α có thể được đồng nhất với xâu p-phân (a₁, a₂,..., a_m). Việc chọn cơ sở nằm ngoài phạm vi của tiêu chuẩn này. F(p^m) được bổ sung hai phép toán gọi là phép toán cộng và phép toán nhân thỏa mãn các điều kiện sau:

- F(p^m) là nhóm abel với Phép toán cộng “+”

Với α = (a₁, a₂,..., a_m) và β = (b₁, b₂,..., b_m), tổng α + β được cho bởi α + β := g = (c₁, c₂,..., c_m), trong đó c_i = a_i + b_i là tổng trong F(p). Phần tử trung hòa của phép cộng là 0_F = (0, 0,...0).

- F(p^m) \ {0} ký hiệu bởi F(p^m) * là một nhóm abel với phép toán nhân “x”.

Với α = (a₁, a₂,..., a_m) và β = (b₁, b₂,..., b_m) tích α x β được cho bởi một xâu p-phân α x β := g = (c₁, c₂,... c_m) trong đó , với z_jz_k = d_1,j,kz₁ + d_2,j,kz₂ + ... + d_m,j,kz_m (1 ≤ j, k ≤ m). Khi không sợ gây nhầm lẫn thì ký hiệu phép nhân “x” được bỏ qua và ký hiệu ab được sử dụng. Cơ sở có thể chọn theo cách sao cho phần tử trung hòa của phép nhân là 1_F = (1, 0, 0,..., 0).

CHÚ THÍCH 3  Việc chọn cơ sở được mô tả trong tài liệu viện dẫn [4].

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

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

6.1.1  Đường cong elliptic trên trường F(p^m)

Cho F(p^m) là một trường hữu hạn với số nguyên tố p > 3 và một số nguyên dương m. Trong tiêu chuẩn này, ta giả sử rằng E được mô tả bằng một phương trình Weierstrass (dạng affine) rút gọn, tức là phương trình có dạng:

Y² = X³ + aX + b với a, b ϵ F(p^m)

sao cho 4a³ + 27b² ≠ 0_F trong trường F(p^m).

CHÚ THÍCH  Đường cong trên với 4a³ + 27b² = 0_F được gọi là đường cong kỳ dị và đó không phải là một đường cong elliptic.

Tập các điểm với tọa độ trong F(p^m) (các điểm F(p^m) - giá trị) của E được đưa ra bởi công thức (1):

trong đó O_E là điểm đặc biệt được gọi là điểm tại vô hạn của E.

6.1.2  Các đường cong elliptic trên F(2^m)

Cho F(2^m), với m ≥ 1 nào đó, là một trường hữu hạn. Trong tiêu chuẩn này, ta giả sử E được mô tả bởi một phương trình có dạng:

Y² + XY = X³ + aX² + b với a, b ϵ F(2^m)

sao cho b ≠ 0_F là đúng trong F(2^m).

Để sử dụng trong lĩnh vực mật mã, m phải là một số nguyên tố để chống lại được các loại tấn công vào các hệ mật mã.

CHÚ THÍCH  Đường cong trên với b = 0_F được gọi là đường cong kỳ dị, không phải đường cong elliptic.

Tập các điểm với tọa độ trong F(2^m) (các điểm F(2^m) - giá trị) của E được cho bởi công thức (2)

với O_E là điểm đặc biệt, được gọi là điểm tại vô hạn của E.

6.1.3  Các đường cong elliptic trên trường F(3^m)

Cho F(3^m) là một trường hữu hạn với một số nguyên dương m. Trong tiêu chuẩn này, ta giả sử rằng E được mô tả bởi một phương trình có dạng:

Y² = X³ + aX² + b với a, b ϵ F(3^m)

sao cho a,b ≠ 0_F trong F(3^m)

CHÚ THÍCH  Đường cong trên với a hoặc b = 0_F được gọi là đường cong kỳ dị, không phải là đường cong elliptic.

Tập các điểm với tọa độ trong F(3^m) (các điểm F(3^m) - giá trị) của E được cho bởi công thức (3)

với O_E là điểm đặc biệt được gọi là điểm tại vô hạn của E.

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

Đường cong elliptic được cung cấp phép toán cộng + : E x E ® E, xác định đối với mỗi cặp {Q₁,Q₂} các điểm trên E một điểm thứ 3 Q₁ + Q₂. Với phép toán cộng này, E là một nhóm abel với phần tử trung hòa O_E. Bội số k lần của Q được định nghĩa là kQ, trong đó kQ = Q + ... + Q (tổng k lần) nếu k > 0,kQ = (-k)(-Q) nếu k < 0, và kQ = O_E nếu k = 0. Số dương nhỏ nhất k với kQ = O_E được gọi là cấp của Q.

CHÚ THÍCH  Công thức của luật nhóm và Q được đưa ra trong B.3, B.4 và B.5

6.3  Sinh các đường cong elliptic

Để sử dụng đường cong elliptic cho các hệ mật mã, việc sinh một đường cong elliptic thích hợp là cần thiết. TCVN 12852-5 là tài liệu tham chiếu cho các phương pháp sinh đường cong elliptic.

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

Ánh xạ song tuyến tính mật mã e_n được sử dụng trong một số ứng dụng mật mã, chẳng hạn như các lược đồ ký số hoặc lược đồ thỏa thuận khóa. Một ánh xạ song tuyến tính mật mã e_n được xác định qua việc lấy hạn chế trên miền xác định của các phép ghép cặp Weil hoặc Tate như sau.

e_n :< G₁ > x < G₂ > ® µ_n

trong đó ánh xạ song tuyến tính mật mã e_n thỏa mãn các tính chất sau:

- Tính song tuyến tính: e_n(aG₁, bG₂) = e(G₁,G₂)^ab (Ɐ a,b ϵ [0, n - 1]);

- Không suy biến: e_n(G₁, G₂) ≠ 1;

- Có thể tính toán được: Tồn tại một thuật toán hiệu quả đến tính toán e_n.

CHÚ THÍCH 1  Mối liên hệ giữa ánh xạ song tuyến tính mật mã với phép ghép cặp Weil hoặc Tate được chỉ ra trong B.7

CHÚ THÍCH 2  Công thức cho các phép ghép cặp Weil và Tate được chỉ ra trong C.6

CHÚ THÍCH 3  Có hai kiểu ghép cặp:

- Trường hợp G₁ = G₂;

- Trường hợp G₁ ≠ G₂.

7  Các hàm chuyển đổi

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

Các nguyên thủy OS2BSP và BS2OSP dùng để chuyển đổi giữa các xâu bộ tám và các xâu bit được định nghĩa như sau:

- Hàm OS2BSP(x) lấy đầu vào là xâu bộ tám x, biểu diễn nó thành một xâu bit y và đầu ra xâu bit y. Thiết lập bit đầu tiên của xâu bit là bit có trọng số cao nhất (bên trái nhất) của bộ tám đầu tiên, bit thứ hai là bit có trọng số cao nhất tiếp theo của bộ tám đầu tiên, tiếp tục như vậy, và cuối cùng thiết lập bit cuối cùng là bit có trọng số thấp nhất (bên phải nhất) của bộ tám cuối cùng.

- Hàm BS2OSP(y) lấy đầu vào một xâu bit y với độ dài xâu là bội của 8 và đầu ra là một xâu bộ tám x duy nhất sao cho y = OS2BSP(x).

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

Các nguyên thủy BS2IP và I2BSP dùng để chuyển đổi giữa các xâu bit và các số nguyên được định nghĩa như sau:

- Hàm BS2IP(x) ánh xạ một xâu bit x tới một giá trị nguyên x’, như sau:

Nếu x = (x_l-1, ..., x₀) trong đó x₀, ..., x_l-1 là các bit, thì x’ được xác định .

- Hàm l2BSP(m,l) lấy hai số nguyên không âm m và l làm đầu vào và đầu ra duy nhất là một xâu bit x có độ dài l, sao cho BS2IP(x) = m, nếu một xâu x như vậy tồn tại. Ngược lại hàm cho đầu ra là một thông điệp lỗi.

Độ dài theo bit của một số nguyên không âm m là số bit của m trong phép biểu diễn nhị phân, tức là [log₂(m + 1)]. Để cho tiện Oct(m) được xác định là Oct(m) = I2BSP(m, 8).

CHÚ THÍCH  I2BSP(m, l) thất bại khi và chỉ khi độ dài theo bit của m lớn hơn l.

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

Các nguyên thủy OS2IP và I2OSP dùng để chuyển đổi giữa các xâu bộ tám và các số nguyên được định nghĩa như sau:

- Hàm OS2IP(x) lấy xâu bộ tám x làm đầu vào và đưa ra số nguyên BS2IP[OS2BSP(x)].

- Hàm I2OSP(m, l) lấy hai số nguyên không âm m và I làm đầu vào và đưa ra đầu ra duy nhất là một xâu bộ tám x có độ dài l, sao cho O52IP(x) = m, nếu tồn tại xâu x như vậy. Trong các trường hợp khác hàm sẽ trả về một thông điệp lỗi.

Độ dài theo bộ tám của một số nguyên không âm m là số các chữ số trong phép biểu diễn theo cơ số 256, tức là [log₂₅₆(m + 1)].

CHÚ THÍCH 1  I2OSP(m, l) thất bại khi và chỉ khi độ dài theo bộ tám của m là lớn hơn l.

CHÚ THÍCH 2  Một bộ tám x thường được viết theo dạng thập lục phân với độ dài 2; khi OS2IP(x) < 16, “0” biểu diễn cho xâu bit 0000. Ví dụ số nguyên 15 được viết là 0f trong hệ thập lục phân.

CHÚ THÍCH 3  Độ dài theo bộ tám của một số nguyên không âm m được kí hiệu là L(m).

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

Nguyên thủy FE2IP_F dùng để chuyển đổi các phần tử của F thành các giá trị nguyên được định nghĩa như sau:

- Hàm FE2IP_F ánh xạ một phần tử a ϵ F thành một giá trị nguyên a’ như sau:

Nếu một phần tử a của F được đồng nhất với một bộ gồm m thành phần (a₁ ... a_m) trong đó lực lượng của F là q = p^m và a_i ϵ [0,p - 1] với 1 ≤ i ≤ m thì giá trị a’ được định nghĩa là a’ = Σ_1≤i<ma_ip^i-1_.

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

Các nguyên thủy OS2FEP_F và FE2OSP_F dùng để chuyển đổi giữa các xâu bộ tám và phần tử của trường hữu hạn đã xác định rõ ràng F được định nghĩa như sau:

- Hàm OS2FEP_F(a) lấy một phần tử a của trường F làm đầu vào và cho đầu ra là xâu bộ tám I2OSP(a’, l) trong đó a’ = FE2IP_F(a) và l = L(|F| - 1). Như vậy đầu ra của FE2OSP_F(a) luôn là một xâu bộ tám có độ dài chính xác là [log₂₅₆|F|].

CHÚ THÍCH 1  L(x) biểu diễn độ dài theo bộ tám của số nguyên x hoặc xâu bộ tám x (số nguyên không âm)

- Hàm OS2FEP_F(x) lấy xâu bộ tám x làm đầu vào và đưa ra đầu ra (duy nhất) là phần tử trường a ϵ F sao cho FE2OSP_F(a) = x, nếu a như vậy tồn tại, nếu không sẽ trả lại kết quả lỗi.

CHÚ THÍCH  OS2FEP_F(x) lỗi khi và chỉ khi x không có độ dài chính xác bằng [log₂₅₆|F|] hoặc OS2lP(x) ≥ |F|.

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

7.6.1  Các điểm đường cong elliptic dạng nén

Cho E là một đường cong elliptic trên một trường hữu hạn đã cho F, trong đó F có đặc số p. Một điểm P ≠ O_E có thể được biểu diễn dưới dạng nén, không nén hoặc lai ghép. Nếu P = (x,y) thì (x,y) là dạng không nén của P. Dạng nén của P là cặp (x,y), với  ϵ {0,1} và được xác định như sau:

- Nếu p ≠ 2 và y = 0_F thì  = 0;

- Nếu p ≠ 2 và y ≠ 0_F thì  = [(y'/p^f) mod p] mod 2, với y' = FE2IPF_F(y) và f là số nguyên không âm lớn nhất sao cho p^f|y’;

CHÚ THÍCH 1  Nếu p ≠ 2 và y = (y₁, ... y_m) ≠ 0_F thì việc này tương đương với việc lấy j là chỉ số nhỏ nhất với y_j ≠ 0 và định nghĩa  = y_j mod 2.

- Nếu p = 2 và x = 0_F thì  = 0;

- Nếu p = 2 và x ≠ 0_F thì  = [z'/2^f] mod 2 trong đó z = y/x, với z’ = FE2lP_F(z) và f là số nguyên không âm lớn nhất sao cho 2^f chia hết FE2lP_F(1_F).

CHÚ THÍCH 2  Nếu p = 2 và x ≠ 0_F thì điều này tương đương với việc lấy y/x = (z₁, ... z_m) và định nghĩa  = z₁.

Dạng lai ghép của P = (x,y) là bộ ba (x, ,y) với  được định nghĩa như trong đoạn trước.

7.6.2  Các thuật toán giải nén điểm

Tồn tại các thủ tục hiệu quả để giải nén điểm, tức là tính toán y từ (x, ). Các thủ tục đó được mô tả tóm tắt như sau:

- Nếu p ≠ 2 , cho (x, ) là dạng nén của (x,y) trong đó điểm (x,y) thỏa mãn phương trình Weierstrass y² = f(x) định nghĩa trong 6.1.1 hoặc 6.1.3. Nếu f(x) = 0_F thì chỉ có duy nhất một lựa chọn cho y, chính là y = 0­_F. Ngược lại, nếu f(x) ≠ 0_F thì có hai lựa chọn cho y, hai lựa chọn này chỉ khác nhau về dấu và việc chọn đúng được xác định bởi . Có một số thuật toán đã biết để tính căn bậc hai trong trường hữu hạn, do vậy hai lựa chọn cho y là dễ dàng tính toán được.

- Nếu p = 2 , cho (x, ) là dạng nén của (x,y) trong đó điểm (x,y) thỏa mãn phương trình Weierstrass y² + xy = x³ + ax² + b. Nếu x = 0_F thì phương trình là y² = b, từ đó y được xác định một cách duy nhất và dễ dàng tính toán được. Ngược lại, nếu x ≠ 0_F , khi đó đặt z = y/x thì phương trình trở thành z² + z = g(x) với g(x) = x + a + bx^-2. Giá trị của y được xác định duy nhất, và dễ dàng tính toán được từ các giá trị z và x, và do vậy ta chỉ cần tính toán z là đủ. Để tính z, với x cố định, nếu z là một nghiệm của phương trình z² + z = g(x), thì có chính xác một nghiệm khác, cụ thể là z + 1_F. Việc tính toán hai giá trị có thể của z là khá dễ dàng, và việc lựa chọn giá trị z đúng đắn là đơn giản với việc sử dụng .

7.6.3  Các hàm chuyển đổi

Gọi E là một đường cong elliptic trên một trường hữu hạn đã cho F.

Các nguyên thủy EC2OSP_E và OS2ECP_E dùng để chuyển đổi giữa các điểm trên đường cong E và các xâu bộ tám được định nghĩa như sau:

- Hàm EC2OSP_E(P, fmt) nhận đầu vào là một điểm P trên E và một kiểu định dạng cụ thể fmt - một trong các giá trị tượng trưng cho kiểu nén, không nén, hoặc lai ghép. Đầu ra là một xâu bộ tám, EP được tính như sau:

- Nếu P = O_E thì EP = Oct(0);

- Nếu P = (x,y) ≠ O_E với dạng nén (x, ) thì EP = H||X||y, trong đó:

- H là một bộ tám đơn có dạng Oct[4U + C(2 +)], trong đó

- U = 1 nếu fmt hoặc là dạng không nén hoặc lai ghép và ngược lại U = 0;

- C = 1 nếu fmt hoặc là dạng nén hoặc dạng lai ghép, và ngược lại C = 0

- X là xâu bộ tám FE2OSP_F(x);

- Y là xâu bộ tám FE2OSP_F(y) nếu fmt hoặc ở dạng không nén hoặc dạng lai ghép, và ngược lại Y là xâu bộ tám rỗng.

- Hàm OS2ECP_E(CP) nhận đầu vào là xâu bộ tám EP. Nếu tồn tại một điểm P trên đường cong E và một kiểu định dạng fmt, sao cho EC2OSP_E(P, fmt) = EP thì cho đầu ra là P (ở dạng không nén), và ngược lại, hàm thất bại. Chú ý rằng điểm P, nếu tồn tại, được xác định duy nhất và do đó hàm OS2ECP_E(CP) được định nghĩa tốt.

CHÚ THÍCH  Nếu kiểu định dạng fmt là không nén, thì cả x và y được sử dụng; và giá trị  không cần phải tính toán.

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

Cho E là một đường cong elliptic trên trường hữu hạn đã biết F. Nguyên thủy I2ECP dùng để chuyển đổi các số nguyên thành các điểm trên đường cong elliptic được định nghĩa như sau:

a) Hàm I2ECP(x) lấy đầu vào là một số nguyên x.

b) Chuyển đổi số nguyên x thành một xâu bộ tám X = I2OSP[x,L(|F| - 1)].

c) Nếu tồn tại một điểm P trên đường cong E sao cho EC2OSP_E(P,nén) = 03 || X, thì đầu ra của hàm là P, và ngược lại, hàm lỗi.

CHÚ THÍCH 1  Điểm P đầu ra, nếu tồn tại thì được xác định duy nhất.

CHÚ THÍCH 2  Hàm I2ECP sẽ thất bại với đầu vào x nếu không tồn tại một điểm P trên đường cong E sao cho EC2OSP_E(P, nén) = 03 || X

CHÚ THÍCH 3  Miền giá trị của I2ECP là xấp xỉ một nửa của E(F). Tức là, I2ECP luôn đưa ra các điểm P = (x,y) trên đường cong elliptic với dạng nén (x, 1). Hàm này sẽ không đưa ra hoặc điểm tại vô hạn hoặc điểm trên đường cong elliptic P = (x,y) với dạng nén (x, 0).

CHÚ THÍCH 4  Một vài ứng dụng dựa trên đường cong elliptic có thể cần một hàm, mà ánh xạ các xâu bộ tám tới các điểm trên đường cong elliptic. Hàm I2ECP được sử dụng như một thành phần cùng với OS2IP hoặc một hàm băm.

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)

Các tham số miền đường cong elliptic trên F(q) [bao gồm cả các trường hợp đặc biệt F(p) và F(2^m)] sẽ bao gồm các thành phần sau:

Nếu m > 1 thì nên có một thỏa thuận về việc lựa chọn cơ sở giữa các bên tham gia liên lạc.

- Kích thước trường q = p^m xác định trường hữu hạn cơ sở F(q), với p là một số nguyên tố và một chỉ dẫn rõ ràng về cơ sở được sử dụng để biểu diễn các phần tử của trường trong trường hợp m > 1;

- Nếu q = p^m với p > 3, hai phần tử a và b của trường F(q) định nghĩa phương trình đường cong elliptic E: y² + xy = x³ + ax² + b;

- Nếu q = 2^m, hai phần tử a và b của trường F(2^m) định nghĩa phương trình đường cong elliptic E: y² + xy = x³ + ax² + b;

- Nếu q = 3^m, hai phần tử a và b trong F(3^m) định nghĩa phương trình đường cong elliptic E: y² = x³ + ax² + b;

- Hai phần tử x_G và y_G của trường F(q) xác định một điểm G = (x_G, y_G) có cấp nguyên tố trên E;

- Cấp n của điểm G:

- Đồng hệ số h = #E(F(q))/n (khi được yêu cầu bởi lược đồ cơ sở).

CHÚ THÍCH  Việc tính toán #E(F(q)) được mô tả trong tài liệu viện dẫn [4].

8.2  Sinh khóa đường cong elliptic

Cho một tập các tham số miền đường cong elliptic hợp lệ, một khóa bí mật và một khóa công khai tương ứng có thể được tạo ra như sau:

a) Chọn một số nguyên d trong tập [2, n - 2] một cách ngẫu nhiên hoặc giả ngẫu nhiên. Số nguyên d phải được bảo vệ khỏi việc tiết lộ trái phép và không thể đoán trước được.

b) Tính điểm P = (xp, yp) = dG.

c) Cặp khóa là (P, d), với P sẽ được sử dụng như khóa công khai và d là khóa bí mật.

Trong một số ứng dụng, khóa công khai có thể là eG, với de ≡ 1 mod n.