TIÊU CHUẨN QUỐC GIA TCVN 12852-5:2020 (ISO/IEC 15946-5:2017) 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 5: SINH ĐƯỜNG CONG ELLIPIC

TIÊU CHUẨN QUỐC GIA

TCVN 12852-5 : 2020

ISO/IEC 15946-5 : 2017

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

Information technology – Security techniques – Cryptography based on elliptic curves – Part 5: Elliptic curve generation

Lời nói đầu

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

TCVN 12852-5 : 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 – Kỹ thuật mật mã dựa trên đường cong elliptic 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 (ISO/IEC 15946-5:2017) Phần 5: Sinh đường cong elliptic

Bô tiêu chuẩn này có thể có thêm 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 5: SINH ĐƯỜNG CONG ELLIPTIC

Information technology – Security techniques – Cryptography based on elliptic curves – Part 5: Elliptic curve generation

1  Phạm vi áp dụng

Các tiêu chuẩn trong bộ tiêu chuẩn này quy định các kỹ thuật mật mã khóa công khai dựa trên các đường cong elliptic được mô tả trong TCVN 12852-1.

Tiêu chuẩn này quy định các kỹ thuật sinh đường cong elliptic hiệu quả cho việc thực thi các cơ chế dựa trên đường cong elliptic được mô tả trong TCVN 12854-4, TCVN 12855-3, TCVN 7817-3, TCVN 12214-3 và TCVN 11367-2.

Tiêu chuẩn này được áp dụng cho các kỹ thuật mật mã dựa trên các đường cong elliptic định nghĩa trên trường hữu hạn có cấp là lũy thừa của một số nguyên tố (bao gồm cả các trường hợp đặc biệt của cấp nguyên tố và đặc số hai). Tiêu chuẩn này không áp dụng cho việc biểu diễn các phần tử của trường hữu hạn cơ sở (tức là cơ sở được sử dụng).

Bộ tiêu chuẩn này không quy định việc thực thi các kỹ thuật được định nghĩa. Khả năng tương thích của các sản phẩm phù hợp theo bộ tiêu chuẩn này 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ố, thi áp dụng phiên bản mới nhất (bao gồm cả các sửa đổi, bổ sung).

TCVN 12852-1, 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

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 quy định trong TCVN 15946-1 và các thuật ngữ và định nghĩa dưới đây.

3.1

Trường xác định của một đường cong elliptic (definition field of an elliptic curve)

Trường bao gồm tất cả các hệ số của phương trình mô tả một đường cong elliptic.

3.2

Hàm băm (hash-function)

Hàm ánh xạ các xâu bit có độ dài tùy ý (nhưng thường có cận trên) thành các xâu bit có độ dài cố định thỏa mãn hai tính chất sau:

– Với một đầu ra cho trước thì rất khó có thể tìm được một đầu vào mà ánh xạ tới đầu ra đó;

– Với một đầu vào cho trước thì rất khó có thể tìm được một đầu vào thứ hai mà ánh xạ tới cùng một đầu ra.

CHÚ THÍCH 1 về đầu vào: Tính khả thi về mặt tính toán phụ thuộc vào các yêu cầu và môi trường an toàn cụ thể. Tham khảo phụ lục C, ISO/IEC 10118-1:2016.

[TCVN 11816-1 (ISO/IEC 10118-1), 3.4]

3.3

Số gần nguyên tố (nearly prime number)

Số nguyên dương, n = m·r, trong đó m là một số nguyên tố lớn và r là một số nguyên trơn nhỏ (3.5).

CHÚ THÍCH 1 về đầu vào: Ý nghĩa của các thuật ngữ số nguyên tố nhỏ và lớn phụ thuộc vào ứng dụng và dựa trên các giới hạn do nhà thiết kế xác định.

3.4

Bậc của một đường cong elliptic (order of an elliptic curve)

E(F)

Số các điểm trên một đường cong elliptic E, định nghĩa trên một trường hữu hạn F.

3.5

Số nguyên trơn (smooth integer)

Số nguyên r, có tất cả các thừa số nguyên tố đều nhỏ (tức là nhỏ hơn giới hạn xác định).

4  Các Ký hiệu và hàm chuyển đổi

4.1  Ký hiệu

B	Bậc nhúng, là giá trị B nhỏ nhất sao cho số #E[F(q)]|qB – 1.
E	Đường cong elliptic, được cho bởi phương trình có dạng Y2 = X3 + aX + b trên trường F(pm) với p > 3, hoặc phương trình có dạng Y2 + XY = X3 + aX2 + b trên trường F(2m), hoặc phương trình có dạng Y2 = X3 + aX2 + b trên trường F(3m), cùng với một điểm OE được gọi là điểm tại vô hạn. Đường cong elliptic được ký hiệu là FE/F(pm), E/F(2m), hoặc E/F(3m) tương ứng. CHÚ THÍCH 1 Trong các ứng dụng không dựa trên một phép ghép cặp, E/F(p) hoặc E/F(2m) thường được sử dụng do hiệu quả hơn. Trong các ứng dụng sử dụng một phép ghép cặp, thì E/F(p) hoặc E/F(3m) lại hiệu quả hơn. CHÚ THÍCH 2 Đường cong elliptic không chỉ là tập hợp các điểm trên đường cong, mà còn là một nhóm dưới phép toán được định nghĩa trên các điểm này.
N	Số lượng điểm trên một đường cong elliptic E trên F(q), #E[F(q)].
n	Ước số nguyên tố của #E[F(q)].
OE	Điểm tại vô hạn của đường cong elliptic.
p	Số nguyên tố
q	Lũy thừa nguyên tố, pm đối với một số nguyên tố p và một số số nguyên m ≥ 1.
r	Đồng hệ số, tức là #E[F(q)] = rn.
#E[F(q)]	Cấp (hoặc lực lượng) của E[F(q)].
	Số nguyên nhỏ nhất lớn hơn hoặc bằng số thực x.
	Số nguyên lớn nhất lớn hơn hoặc bằng số thực x.

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

BS2IP	Nguyên thủy chuyển đổi xâu bit thành số nguyên.
BS2OSP	Nguyên thủy chuyển đổi xâu bit thành xâu bộ tám.
EC2OSPE	Nguyên thủy chuyển đổi điểm đường cong elliptic thành xâu bộ tám.
FE2IPF	Nguyên thủy chuyển đổi phần tử trường hữu hạn thành số nguyên.
FE2OSPF	Nguyên thủy chuyển đổi phần tử trường hữu hạn thành xâu bộ tám.
I2BSP	Nguyên thủy chuyển đổi số nguyên thành xâu bit.
I2OSP	Nguyên thủy chuyển đổi số nguyên thành xâu bộ tám.
I2ECP	Nguyên thủy chuyển đổi số nguyên thành đường cong elliptic.
OS2BSP	Nguyên thủy chuyển đổi xâu bộ tám thành xâu bit.
OS2FEPF	Nguyên thủy chuyển đổi xâu bộ tám thành phần tử trường hữu hạn.
OS2ECPE	Nguyên thủy chuyển đổi xâu bộ tám thành điểm trên đường cong elliptic.
OS2IP	Nguyên thủy chuyển đổi xâu bộ tám thành số nguyên.

5  Khuôn khổ cho việc sinh đường cong elliptic

5.1  Các kiểu đường cong elliptic tin cậy

Có một số cách người dùng có thể có được sự tin tưởng vào nguồn gốc của một đường cong elliptic, bao gồm:

– Đường cong có thể thu được từ một nguồn đáng tin cậy công bằng (ví dụ: tiêu chuẩn quốc tế hoặc quốc gia).

– Đường cong có thể được sinh và/hoặc kiểm tra bởi một bên thứ ba đáng tin cậy.

– Đường cong có thể được sinh và/hoặc kiểm tra bởi người dùng.

CHÚ THÍCH 1 Tham khảo Phụ lục A để biết thêm thông tin cơ bản về các đường cong elliptic.

CHÚ THÍCH 2 Tham khảo Phụ lục B để biết thêm thông tin cơ bản về các hệ mật trên đường cong elliptic.

5.2  Tổng quan về việc sinh đường cong elliptic

Có ba phương pháp chính để sinh các đường cong elliptic.

– Sinh một đường cong elliptic bằng cách áp dụng các thuật toán tính cấp (số điểm) đối với một đường cong elliptic được chọn (giả) ngẫu nhiên. Kỹ thuật này được đặc tả tại Mục 6.

– Sinh một đường cong elliptic bằng cách áp dụng phương pháp nhân phức. Kỹ thuật này được đặc tả tại Mục 7.

– Sinh một đường cong elliptic bằng cách nâng một đường cong elliptic trên một trường hữu hạn nhỏ lên trường có kích thước lớn hơn. Kỹ thuật này được đặc tả tại Điều 8.

CHÚ THÍCH 1 Tham khảo Phụ lục A để biết thêm thông tin cơ bản về các đường cong elliptic.

CHÚ THÍCH 2 Tham khảo Phụ lục B để biết thêm thông tin cơ bản về các hệ mật trên đường cong elliptic.

6  Sinh đường cong elliptic giả ngẫu nhiên kiểm tra được

6.1  Giới thiệu chung

Việc sinh các đường cong elliptic giả ngẫu nhiên kiểm tra được tập trung vào các đường cong trên trường nguyên tố và trường nhị phân (và do vậy không áp dụng với các đường cong trên các trường có đặc số 3).

6.2  Xây dựng đường cong elliptic giả ngẫu nhiên kiểm tra được (trường hợp trường nguyên tố)

6.2.1  Thuật toán xây dựng

Thuật toán sau đây tạo ra một tập hợp các tham số đường cong elliptic trên một trường F(p) được lựa chọn (giả) ngẫu nhiên từ các đường cong có cấp thích hợp, cùng với thông tin đầy đủ để người dùng khác có thể kiểm tra xem đường cong có thực sự được chọn giả ngẫu nhiên hay không.

CHÚ THÍCH 1 Thuật toán phù hợp với tài liệu tham khảo [9].

CHÚ THÍCH 2 Các phương pháp lựa chọn (giả) ngẫu nhiên một số nguyên tố p được mô tả trong tài liệu tham khảo [5].

Giả thiết rằng các đại lượng sau đây đã được chọn:

– Cận dưới, n_min, cho cấp của điểm cơ sở;

– Hàm băm mật mã, H, với độ dài đầu ra L_Hash bit;

– Độ dài bit, L, của đầu vào của H, thỏa mãn L ≥ L_Hash.

Ký hiệu sau được chấp nhận:

– w = v – sL_Hash – 1.

Đầu vào: một số nguyên tố p; cận dưới n_min cho n; giới hạn cho phép chia tầm thường l_max.

Đầu ra: một xâu bit X; các tham số EC a,b,n và G.

1. a) Chọn một xâu bit tùy ý X có độ dài bit
2. b) Tính h = H(X).
3. c) Đặt W₀ là xâu bit thu được bằng cách lấy w bit ngoài cùng bên phải của h.
4. d) Đặt Z = BS2IP(X).
5. e) Với i từ 1 đến s thực hiện:

1) Đặt X_i = I2BSP(Z + i mod 2^L).

2) Tính W_i = H(X_i).

1. f) Đặt W = W₀||W₁||…||W_s.
2. g) Đặt c = OS2FEP[BS2OSP(W)].
3. h) Nếu c = 0_F hoặc 4c + 27 = 0_F, thì quay lại bước a).
4. i) Chọn các phần tử trường hữu hạn a, b ϵ F(p) sao cho b ≠ 0_F và cb₂ – a₃ = 0_F. Chọn a = b = c sẽ đảm bảo các điều kiện được thỏa mãn và lựa chọn này được đề xuất sử dụng.

CHÚ THÍCH 3 Việc chọn a = b = c có thể không tối ưu về mặt hiệu suất.

CHÚ THÍCH 4 Nếu các giá trị mặc định được chọn như đề xuất, thì sẽ đảm bảo được tính ngẫu nhiên của đường cong đã sinh.

1. j) Tính cấp #E[F(p)] của đường cong elliptic E trên F(p) cho bởi y² = x³ + ax + b.
2. k) Kiểm tra xem #E[F(p)] có phải là một số gần nguyên tố hay không bằng cách sử dụng thuật toán được đặc tả trong 6.2.2. Nếu thỏa mãn, đầu ra của thuật toán được đặc tả trong 6.2.2 bao gồm các số nguyên r, n. Nếu không, thì quay lại bước a).

CHÚ THÍCH 5 Sự cần thiết của tính gần nguyên tố được quy định trong B.2.2.

2. l) Kiểm tra xem E[F(p)] có thỏa mãn điều kiện MOV quy định trong B.2.3 hay không, tức là số nguyên nhỏ nhất B thỏa mãn n chia hết q^B – 1 đảm bảo mức an toàn mong đợi. Nếu không, thì quay lại bước a).
3. m) Nếu #E[F(p)] = p, thì quay lại bước a).

CHÚ THÍCH 6 Việc kiểm tra này được thực hiện nhằm bảo vệ chống lại tấn công được mô tả trong B.2.2.

2. n) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện được quy định trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
3. o) Sinh một điểm G trên E có cấp n sử dụng thuật toán được mô tả trong 6.2.3.
4. p) Đầu ra là X, a, b, n,

CHÚ THÍCH 7: Các phương pháp tính cấp #E[F(p)] được mô tả trong tài liệu tham khảo [11], [30] và [31].

6.2.2  Kiểm tra tính gần nguyên tố

Cho trước một cận dưới n_min và một giới hạn cho phép chia tầm thường l_max, quá trình sau đây kiểm tra tính gần nguyên tố của N = #E[F(p)].

Đầu vào: Các số nguyên dương N, l_max và n_min.

Đầu ra: Nếu N là số gần nguyên tố, đầu ra là một số nguyên tố n với n_min ≤ n và một số nguyên trơn r sao cho N = rn. Nếu N không phải là một số gần nguyên tố, thì đầu ra là thông báo “không gần nguyên tố”.

1. a) Đặt n = N, r = 1.
2. b) For l from 2 to l_max do:

1) Nếu l là hợp số, thì chuyển sang bước 3).

2) While (l chia hết n)

1. Đặt n = n/l và r = rl.
2. Nếu n < n_min, thì đầu ra là “không gần nguyên tố” và dừng.

3) Next l.

1. c) Kiểm tra tính nguyên tố của n.
2. d) Nếu n là số nguyên tố, thì đầu ra là r và n và dừng.
3. e) Đầu ra “không gần nguyên tố”.

CHÚ THÍCH Các phương pháp kiểm tra tính nguyên tố được mô tả trong tài liệu tham khảo [5] và [10].

6.2.3  Tìm một điểm có cấp nguyên tố lớn

Nếu cấp #E[F(q)] của một đường cong elliptic E là gần nguyên tố, thì thuật toán sau đây sinh hiệu quả một điểm ngẫu nhiên trên E[F(q)] sao cho cấp của nó là một thừa số nguyên tố lớn n của #E[F(q)] = rn.

Đầu vào: Một đường cong elliptic E trên trường F(q), một số nguyên tố n và một số nguyên dương r không chia hết cho n.

Đầu ra: Nếu #E[F(q)] = rn, một điểm G trên E có cấp n; nếu không, thông báo “cấp sai.”

1. a) Sinh một điểm ngẫu nhiên P (khác O_E) trên E.
2. b) Đặt G = rP.
3. c) Nếu G = O_E, thì quay lại bước a).
4. d) Đặt Q = nG.
5. e) Nếu Q ≠ O_E, thì đầu ra là “cấp sai” và dừng.
6. f) Đầu ra là G.

6.2.4  Kiểm tra tính giả ngẫu nhiên của đường cong elliptic

Thuật toán sau đây xác định một đường cong elliptic trên F(p) có được sinh nhờ sử dụng phương pháp 6.2.1 hay không. Các đại lượng L_Hash,L,v,s và w và hàm băm H như trong 6.2.1.

Đầu vào: Một xâu bit X có độ dài L, các tham số EC q = p,a,b,n, và G = (x_G,y_G), và một số nguyên dương n_min.

Đầu ra: “Đúng” hoặc “Sai”.

1. a) Tính h = H(X).
2. b) Đặt W₀ là xâu bit nhận được bằng cách lấy w bit ngoài cùng bên phải của h.
3. c) Đặt Z = BS2IP(X).
4. d) For i from 1 to s do:

1) Đặt X_i = I2BSP(Z + i mod 2^L).

2) Tính W_i = H(X_i).

1. e) Đặt W = W₀||W₁|| … ||W_s.
2. f) Chuyển đổi W thành một phần tử trường hữu hạn c = OS2FEP[BS2OSP(W)].
3. g) Kiểm tra các điều kiện sau đây:

1) n ≥ n_min.

2) n là một số nguyên tố.

3) c ≠ 0_F.

4) 4c + 27 ≠ 0_F.

5) b ≠ 0_F.

6) cb² – a³ = 0_F.

7) G ≠ O_E.

8)

9) nG = O_E.

1. h) Nếu tất cả các điều kiện trong bước g) thỏa mãn, thì đầu ra là “Đúng”; ngược lại đầu ra là “Sai”.

6.3  Xây dựng đường cong elliptic giả ngẫu nhiên kiểm tra được (trường hợp nhị phân)

6.3.1  Thuật toán xây dựng

Thuật toán sau đây sinh ra một tập hợp các tham số đường cong elliptic cho một đường cong giả ngẫu nhiên trên trường F(2^m), cùng với thông tin đầy đủ để người dùng khác có thể kiểm tra xem đường cong có thực sự được chọn giả ngẫu nhiên hay không. Xem Phụ lục C để biết thêm thông tin.

CHÚ THÍCH 1 Thuật toán phù hợp với tài liệu tham khảo [9].

Giả thiết rằng các đại lượng sau đây đã được chọn:

– Trường F(2^m);

– Cận dưới, n_min, cho cấp của điểm cơ sở;

– Hàm băm mật mã, H, với độ dài đầu ra L_Hash bit;

– Độ dài bit, L của đầu vào của H, thỏa mãn L > L_Hash.

Ký hiệu sau được chấp nhận:

– w = m – sL_Hash.

Đầu vào: một trường F(2^m); cận dưới n_min cho n; giới hạn cho phép chia tầm thường l_max.

Đầu ra: một xâu bit X; các tham số EC a, b, n và G.

1. a) Chọn một xâu bit tùy ý X có độ dài bit L.
2. b) Tính h = H(X).
3. c) Đặt W₀ là xâu bit nhận được bằng cách lấy w bit ngoài cùng bên phải của h.
4. d) Đặt Z = BS2IP(x).
5. e) For i from 1 to s, do:

1) Đặt X_i = I2BSP(Z + i mod 2^L).

2) Tính W_i = H(X_i).

1. f) Đặt W = W₀||W₁||…||W_s.
2. g) Đặt b = OS2FEP[BS2OSP(W)].
3. h) Nếu b = 0_F, thì quay lại bước a).
4. i) Lấy a là một phần tử tùy ý trong F(2^m). Chọn a = 0_F sẽ thỏa mãn các điều kiện, và lựa chọn này được đề xuất sử dụng.

CHÚ THÍCH 2 Các giá trị mặc định có thể không được lựa chọn vi các lý do hiệu suất.

CHÚ THÍCH 3 Nếu các giá trị mặc định được lựa chọn theo đề xuất, tinh ngẫu nhiên hoàn toàn được đảm bảo.

1. j) Tính cấp #E[F(2^m)] của đường cong E trên F(2^m) được cho bởi y² + xy = x³ + ax² + b.

CHÚ THÍCH 4 Các phương pháp tính cấp #E[F(2^m)] được mô tả trong tài liệu tham khảo [11], [30] và [33].

6. k) Kiểm tra xem #E[F(2^m)] có phải là một số gần nguyên tố hay không bằng cách sử dụng thuật toán mô tả trong 6.2.2. Nếu đúng, thì đầu ra của thuật toán được mô tả trong 6.2.2 bao gồm các số nguyên r, n. Nếu sai, thì quay lại bước a).
7. l) Kiểm tra xem E[F(2^m)] thỏa mãn điều kiện MOV quy định trong B.2.3. Nếu không thỏa mãn, thì quay lại bước a).
8. m) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện được quy định trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP, hoặc BDHP với các đầu vào phụ trợ trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
9. n) Sinh một điểm G trên E có cấp n sử dụng thuật toán được quy định trong 6.2.3.
10. o) Đầu ra là X, a, b, n, G.

CHÚ THÍCH 5 Sự cần thiết của tính gần nguyên tố được quy định trong B.2.2.

6.3.2  Kiểm tra tính giả ngẫu nhiên của đường cong elliptic

Thuật toán sau đây kiểm tra tính hợp lệ của một tập hợp các tham số đường cong elliptic. Ngoài ra, nó xác định xem đường cong elliptic trên F(2^m) có được sinh bởi phương pháp trong 6.3.1 hay không.

Các đại lượng L_Hash, L, s, và w, và hàm băm H như trong 6.3.1.

Đầu vào: Một xâu bit X có độ dài L, các tham số EC q = 2^m, a, b, n và G = (x_G, y_G) và một số nguyên dương n_min.

Đầu ra: “Đúng” hoặc “Sai”.

1. a) Tính h = H(X).
2. b) Đặt W₀ là xâu bit nhận được bằng cách lấy w bit ngoài cùng bên phải của h.
3. c) Đặt Z = BS2IP(x).
4. d) Với i từ 1 đến s thực hiện:

1) Đặt X_i = I2BSP(Z + i mod 2^L).

2) Tính W_i = H(X_i).

1. e) Đặt W = W₀||W₁||…||W_s.
2. f) Đặt b’ = OS2FEP[BS2OSP(W)]
3. g) Kiểm tra các điều kiện sau đây:

1) n ≥ n_min.

2) n là một số nguyên tố.

3) b ≠ 0_F.

4) b = b’.

5) G ≠ O_E.

6)

7) nG = O_E.

1. h) Nếu tất cả các điều kiện trong bước g) thỏa mãn, thì đầu ra là “Đúng”; ngược lại đầu ra là “Sai”.

7  Xây dựng đường cong elliptic bằng phép nhân phức

7.1  Cấu trúc chung (trường hợp trường nguyên tố)

Thuật toán sau đây sinh ra một đường cong E trên F(p) với số các điểm hữu tỷ đã cho trước N.

CHÚ THÍCH 1 Thuật toán dựa trên tài liệu tham khảo [17] được áp dụng để chứng minh tính nguyên tố ^[10].

Đầu vào: Trường xác định F(p) và số điểm N = rn, trong đó n là ước số nguyên tố lớn nhất của N và r là đồng hệ số.

Đầu ra: Các tham số đường cong của đường cong elliptic E với #E[F(p)] = N và điểm cơ sở G.

2. a) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện được quy định trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5 hay không. Nếu không thỏa mãn, thì thực thi với một đầu vào mới.
3. b) Đặt t = p + 1 – N.
4. c) Chọn một cặp số nguyên (D, V) sao cho 4p – t² = DV².
5. d) Xây dựng đa thức lớp Hilbert P_D(X).
6. e) Tìm một nghiệm j₀ trong F(p) của P_D(X) ≡ 0 mod p.
7. f) Chọn c ϵ F(p)* và xây dựng một đường cong elliptic trên F(p) với j- bất biến j₀.
8. g) Xây dựng một điểm ngẫu nhiên G trên E_D,j0,c[F(p)] sao cho G ≠ 0_E và r · G ≠ O_E.
9. h) Đặt G = r · G.
10. i) Nếu n · G = O_E, đưa ra các tham số đường cong của E_D,j0,c và điểm cơ sở G. Nếu n · G ≠ O_E, thì quay lại bước f) để lựa chọn giá trị c khác.

CHÚ THÍCH 2 Mọi cặp số nguyên (D, V) thỏa mãn 4p – t² = DV² có thể được sử dụng trong bước c).

CHÚ THÍCH 3 Định nghĩa phương trình Diophantine được sử dụng trong bước c) có trong A.5.

CHÚ THÍCH 4 Định nghĩa đa thức lớp Hilbert P_D(X) có trong A.2.

7.2  Đường cong Miyaji-Nakabayashi-Takano (MNT)

Thuật toán sau đây sinh một đường cong E trên F(p) với bậc nhúng B = 6, phù hợp cho các hệ mật dựa trên phép ghép cặp song tuyến tính. Phép ghép cặp và bậc nhúng được mô tả lần lượt trong A.3 và B.2.2. Các ví dụ số và so sánh có trong Phụ lục C và Phụ lục D tương ứng.

CHÚ THÍCH 1 Một số thông tin và một thuật toán để sinh một đường cong MNT với B = 3 có trong tài liệu tham khảo [24].

CHÚ THÍCH 2 Có thể xây dựng các đường cong MNT không chỉ cho B = 6, mà còn cho B = 3 và 4.

Đầu vào: Cận dưới và trên (số nguyên lẻ) p_min và p_max cho trường xác định (tính bằng bit) và cận trên D_max cho độ lớn của D.

Đầu ra: Số nguyên tố p, các tham số đường cong của đường cong elliptic E/F(p), cấp n = #E[F(p)] và điểm cơ sở G.

1. a) Chọn một số nguyên dương nhỏ D < D_max sao cho D ≡ 3(mod 8) và chuyển sang bước c).
2. b) Nếu không tồn tại giá trị D như vậy, thì dừng và cho đầu ra là “thất bại”.
3. c) Tìm một cặp số nguyên (T, U) với U > 0 nhỏ nhất thỏa mãn T² – 3DU² = 1 bằng cách sử dụng thuật toán liên phân số.
4. d) Tìm một cặp số nguyên (x,y) thỏa mãn x² – 3Dy² = -8 và 0 ≤ x < 2U√(2D),2√(2/D) ≤ y < 2T√(2/D), nhờ sử dụng thuật toán Lagrange. Nếu không tìm được, quay lại bước a).
5. e) i =
6. f) Tìm một cặp số nguyên tố (p, n) như sau:

1) Tính toán các số nguyên x_i và y_i sao cho x_i + y_i√(3D) = [x + y√(3D)][T + U√(3D)]ⁱ.

CHÚ THÍCH 3 Không phải tất cả các nghiệm đều có thể được tìm ra bằng cách này.

2) Nếu x_i ≡ 1(mod 6), thì s = (x_i – 1)/6 và p = 4s² + 1;

1. i) khác, nếu x_i ≡ -1(mod 6), thì s = (x_i + 1)/6 và p = 4s² + 1;
2. ii) khác, i = i + 1 và quay lại bước 1).

3) Nếu p < p_min, thì i = i + 1 và quay lại bước 1).

4) Nếu p > p_max, thì quay lại bước a).

5) Nếu p là số nguyên tố, thì n₁ = 4s² + 2s + 1 và n₂ = 4s² – 2s + 1;

1. i) khác, i = i + 1 và quay lại bước 1).

6) Nếu x_i ≡ 1(mod 6), thì n = n₁;

2. i) khác, n = n₂.

7) Nếu n là số nguyên tố thì chuyển đến bước g);

1. i) khác, i = i + 1 và quay lại bước 1).
2. g) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện được mô tả trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
3. h) Xây dựng đa thức lớp Hilbert P_D(X).
4. i) Tìm một nghiệm j₀ trong F(p) của P_D(x) = 0 mod p.
5. j) Chọn c ϵ F(p)* và xây dựng một đường cong elliptic trên F(p) với j- bất biến j₀.
6. k) Xây dựng một điểm ngẫu nhiên G trên E_D,j0,c[F(p)], khác điểm tại vô hạn O_E.
7. l) Nếu n G = O_E, đầu ra là p,E,n và G.
8. m) Nếu n G ≠ O_E, thì quay lại bước j) để chọn giá trị c ϵ F(p)* khác.

CHÚ THÍCH 4 Định nghĩa đa thức lớp Hilbert P_D(X) có trong A.2.

CHÚ THÍCH 5 Thuật toán liên phân số trong bước c) có trong tài liệu tham khảo [27].

CHÚ THÍCH 6 Thuật toán Lagrange trong bước d) có trong tài liệu tham khảo [22] và [25].

CHÚ THÍCH 7 Kỹ thuật giúp tăng tốc độ một giao thức dựa trên phép ghép cặp song tuyến tính được mô tả trong tài liệu tham khảo [12].

7.3  Đường cong Barreto-Naehrig (BN)

Thuật toán sau đây sinh một đường cong elliptic E trên F(p) với bậc nhúng B = 12, phù hợp cho các hệ mật dựa trên phép ghép cặp song tuyến tính. Bậc nhúng được mô tả trong B.2.2. Các ví dụ số và so sánh có trong Phụ lục C và Phụ lục D tương ứng.

CHÚ THÍCH 1 Thông tin chi tiết có trong tài liệu tham khảo [12].

CHÚ THÍCH 2: Phương pháp này luôn luôn sinh ra nhiều nhất một đường cong với một giá trị cho trước m.

Đầu vào: Độ lớn xấp xỉ mong đợi m của cấp đường cong (tính bằng bit) và cận trên (số nguyên lẻ) p_max cho trường xác định.

Đầu ra: Số nguyên tố p, các tham số đường cong của đường cong elliptic E/F(p), cấp n = #E[F(p)] và điểm cơ sở G.

1. a) Đặt P(u) = 36u⁴ + 36u³ + 24u² + 6u + 1.
2. b) Tính giá trị nhỏ nhất u ≈ 2^m/4 sao cho .
3. c) Lặp p ≤ p_max

1) t = 6u² + 1.

2) p = P(-u) và n = p + 1 – t.

3) Nếu p và n là số nguyên tố, thì chuyển sang bước e).

4) p = P(u) và n = p + 1 – t.

5) Nếu p và n là số nguyên tố, thì chuyển sang bước e).

6) u = u + 1 và quay lại bước 1).

1. d) Dừng và cho đầu ra là “thất bại”.
2. e) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện mô tả trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
3. f) b = 0.
4. g) Nếu b + 1 không được biểu diễn dưới dạng b + 1 = mod p đối với một số nguyên y₀, thì b = b + 1 và quay lại bước g).
5. h) Thiết lập một đường cong elliptic E: y² = x³ + b.
6. i) Tính một căn bậc hai y₀ ≡ √(b + 1) mod p.
7. j) Lấy điểm cơ sở G = (1, y₀) ϵ E.
8. k) Nếu n G ≠ O_E, thì đặt b = b + 1 và quay lại bước g).
9. l) Đầu ra là p, E, n và G.

CHÚ THÍCH 3 Kỹ thuật giúp tăng tốc độ một giao thức dựa trên phép ghép cặp song tuyến tính được mô tả trong tài liệu tham khảo [12].

7.4  Đường cong Freeman (đường cong F)

Thuật toán sau đây sinh một đường cong elliptic E trên F(p) với bậc nhúng B = 10, phù hợp cho các hệ mật dựa trên phép ghép cặp song tuyến tính. Bậc nhúng được mô tả trong B.2.2. Các ví dụ số và so sánh có trong Phụ lục C và Phụ lục D tương ứng.

CHÚ THÍCH 1 Thông tin chi tiết có trong tài liệu tham khảo [18].

Đầu vào: Cận dưới và trên p_min và p_max cho kích thước trường xác định (tính bằng bit) và cận trên D_max cho độ lớn của D.

Đầu ra: Số nguyên tố p, các tham số đường cong của đường cong elliptic E/F(p), cấp n = #E[F(p)] và điểm cơ sở G.

1. a) Chọn một số nguyên dương nhỏ D < D_max sao cho D ≡ 43 hoặc 67 (mod 120) và 15D là số không có ước chính phương và chuyển sang bước c).
2. b) Nếu không tồn tại giá trị D như vậy, thì dừng và cho đầu ra là “thất bại”.
3. c) Tìm một cặp số nguyên (T, U) với U > 0 nhỏ nhất thỏa mãn T² – 15DU² = 1 bằng cách sử dụng thuật toán liên phân số.
4. d) Đặt g = T – U√(15D).
5. e) Tìm một cặp số nguyên (x, y) thỏa mãn x² – 15Dy² = -20 và 0 ≤ x < 10U√(3D),2√1/(3D) ≤ y < 2T√1/(3D) bằng cách sử dụng thuật toán Lagrange.
6. f) Đối với nghiệm hiện tại (x, y).

1) Nếu x = ±5(mod 15), thì:

15. i) Đặt s = (-5 ± x)/15.
16. ii) Đặt p = 25s⁴ + 25s³ + 25s² + 10s + 3.

iii) Đặt n = 25s⁴ + 25s³ + 15s²+ 5s + 1.

2) khác, chuyển sang bước 6).

3) Nếu p > p_max, quay lại bước a) để chọn một giá trị D mới.

4) khác nếu p < p_min, then chuyển sang bước 6).

5) Nếu p và n là các số nguyên tố, thì chuyển sang bước g).

6) Tìm một cặp số nguyên (x’, y’) sao cho x’ + y’√15D = (x + y√15D) · g.

CHÚ THÍCH 2 Không phải tất cả các nghiệm đều có thể được tìm ra bằng cách này.

7) Đặt x = x’ và y = y’ và quay lại bước 1).

2. g) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện mô tả trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
3. h) Xây dựng đa thức lớp Hiibert P_D(X).
4. i) Tìm một nghiệm j₀ trong F(p) của P_D(X) ≡ 0 mod p.
5. j) Chọn c ϵ F(p)* và xây dựng một đường cong elliptic trên F(p) với j- bất biến j₀.
6. k) Xây dựng một điểm ngẫu nhiên G trên E_D,j0,c[F(p)], khác điểm tại vô hạn O_E.
7. l) Nếu n G = O_E, đầu ra là p, E, n và G.
8. m) Nếu n G ≠ O_E, thì quay lại bước j) để chọn giá trị c ϵ F(p)* khác.

CHÚ THÍCH 3 Định nghĩa đa thức lớp Hilbert P_D(X) trong bước…) có trong A.2.

CHÚ THÍCH 4 Thuật toán liên phân số trong bước c) có trong tài liệu tham khảo [27].

CHÚ THÍCH 5 Thuật toán Lagrange trong bước f) có trong tài liệu tham khảo [22] và [25].

CHÚ THÍCH 6 Kỹ thuật giúp tăng tốc độ một giao thức dựa trên phép ghép cặp song tuyến tính được mô tả trong tài liệu tham khảo [12].

7.5  Đường cong Cocks-Pinch (CP)

Thuật toán sau đây sinh một đường cong elliptic E trên F(p) với bậc nhúng B tùy ý, phù hợp cho các hệ mật dựa trên phép ghép cặp song tuyến tính. Bậc nhúng được mô tả trong B.2.2.

CHÚ THÍCH 1 Thông tin chi tiết có trong tài liệu tham khảo [13].

Đầu vào: Một số nguyên dương B và một tập hợp R các số nguyên tố n (n – 1 chia hết cho B).

Đầu ra: Số nguyên tố p, các tham số đường cong của đường cong elliptic E/F(p), cấp n · r = #E[F(p)] và điểm cơ sở G.

1. a) Chọn một số nguyên dương không có ước chính phương, nhỏ D và n trong R sao cho -D là số chính phương theo mô-đun n.
2. b) Tìm một căn nguyên thủy bậc B của phần tử đơn vị z trong F(n).
3. c) t‘ = z + 1.
4. d) y’ = (t‘ – 2)/√(-D)(mod n).
5. e) Lấy t là một số nguyên sao cho t bằng t’ mod n và lấy y là một số nguyên sao cho y bằng y’ mod n.
6. f) p = (t² + Dy²)/4.

CHÚ THÍCH 2 Có thể sử dụng t = t’ và y = y’.

1. g) Nếu p không phải là số nguyên tố, thì quay lại bước a).
2. h) Kiểm tra xem ước số nguyên tố n có thỏa mãn điều kiện mô tả trong B.2.4 cho các hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5 hay không. Nếu không thỏa mãn, thì quay lại bước a).
3. i) Xây dựng đa thức lớp Hilbert P_D(X).
4. j) Tìm một nghiệm j₀ trong F(p) của P_D(X) ≡ 0 mod p.
5. k) Chọn c ϵ F(p)* và xây dựng một đường cong elliptic trên F(p) với j- bất biến j₀.
6. l) Thiết lập đồng hệ số r = (p + 1 – t)/n.
7. m) Xây dựng một điểm ngẫu nhiên G trên E_D,j0,c[F(p)] sao cho G ≠ O_E và r G ≠ O_E
8. n) Đặt G = r · G.
9. o) Nếu n G = O_E, đầu ra là n, G, và đường cong elliptic E.
10. p) Ngược lại, quay lại bước k) để chọn giá trị c ϵ F(p)* khác.

CHÚ THÍCH 3 Định nghĩa đa thức lớp Hilbert P_D(X) trong bước c) có trong A.2.

CHÚ THÍCH 4 Kỹ thuật giúp tăng tốc độ một giao thức dựa trên phép ghép cặp song tuyến tính được mô tả trong tài liệu tham khảo [12].

8  Xây dựng đường cong elliptic bằng phép nâng

Thuật toán sau đây sinh một đường cong elliptic E trên F(p^m) bằng cách nâng một đường cong elliptic E trên F(p).

CHÚ THÍCH Thuật toán dựa trên tài liệu tham khảo [33].

Đầu vào: Trường hữu hạn nhỏ F(p), đường cong elliptic E trên F(p), cận dưới và cận trên N_min và N_max cho cấp của đường cong elliptic (tính bằng bit).

Đầu ra: Bậc mở rộng m, cấp N_m = #E[F(p^m)], điểm cơ sở G và cấp n của G.

1. a) Tính cấp N = #E[F(p)], điều này là dễ dàng thực hiện khi F(p) nhỏ.
2. b) Đặt t = p + 1 – N và tính các số nguyên đại số α và β thỏa mãn t = α + β và p = αβ.
3. c) Đặt m = 1.
4. d) Tìm một bộ ba (m, N_m,n) như sau:

1) Tính N_m = pm + 1 – (α^m + β^m) và q = p^m là một số nguyên.

2) Nếu N_m < N_min, thì m = m + 1 và quay lại bước 1).

3) Nếu N_m > N_max, thì dừng và cho đầu ra là “thất bại”.

4) Kiểm tra xem N_m có là một số gần nguyên tố hay không bằng cách sử dụng thuật toán được mô tả trong 6.2.2. Nếu thỏa mãn, đầu ra của 6.2.2 bao gồm các số nguyên r và n. Nếu không thỏa mãn, thì m = m+ 1 và quay lại bước 1).

5) Kiểm tra xem E[F(q)] có thỏa mãn điều kiện MOV quy định trong B.2.3, tức là số nguyên B nhỏ nhất sao cho n chia hết q^B – 1 đảm bảo mức độ an toàn mong đợi hay không. Nếu không thỏa mãn, thì m = m + 1 và quay lại bước 1).

6. e) Sinh một điểm G trên E[F(q)] có cấp n sử dụng thuật toán được mô tả trong 6.2.3.
7. f) Đầu ra là một bậc mở rộng m, cấp N_m = #E[F(q)], một điểm cơ sở G và cấp n.

 

Phụ lục A

(tham khảo)

Thông tin cơ bản về các đường cong elliptic

A.1  j-bất biến

Cho F(q) là một trường hữu hạn với q = p^m, trong đó số nguyên tố p > 3. Cho E là một đường cong elliptic trên F(q) xác định bởi phương trình Weierstrass dạng rút gọn:

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

thỏa mãn bất đẳng thức 4a³ + 27b² ≠ 0_F trong F(g). Khi đó, j- bất biến được định nghĩa như sau:

j = 1728 · (4a³)/(4a³ + 27b²).

Cho F(2^m), với giá trị m ≥ 1 nào đó, là một trường hữu hạn. Gọi E là một đường cong elliptic trên F(2^m) xác định bởi công thức:

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

trong đó b ≠ 0F. Khi đó, j- bất biến được định nghĩa như sau:

j = 1/b.

Cho F(3^m), với giá trị m ≥ 1 nào đó, là một trường hữu hạn. Gọi E là một đường cong elliptic trên F(3^m) xác định bởi công thức:

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

sao cho a, b ≠ 0_F. Khi đó, j- bất biến được định nghĩa như sau:

j = -a³/b.

A.2  Đa thức lớp Hilbert

Xây dựng đường cong elliptic bằng phép nhân phức sử dụng lý thuyết trường toàn phương ảo Q(√-D). Đối với trường toàn phương ảo Q(√-D), trường lớp Hilbert K là một trường mở rộng của Q(√-D), cũng chính là phần mở rộng abel không rẽ nhánh của Q(√-D). Đa thức lớp Hilbert P_D(X) được xác định bằng đa thức tối tiểu của K trên Q(√-D). Trong việc xây dựng đường cong elliptic bằng phép nhân phức, j-bất biến của đường cong E/F(p) được cho như một nghiệm của đa thức lớp Hilbert P_D(X) mod p.

CHÚ THÍCH 1 Những điều này được mô tả trong tài liệu tham khảo [13] và [16].

CHÚ THÍCH 2 Cơ sở dữ liệu trực tuyến của đa thức lớp Hilbert có trong tài liệu tham khảo [21].

A.3  Phép ghép cặp mật mã

Một phép ghép cặp mật mã e_n thỏa mãn các điều kiện không suy biến, song tuyến tính và tính toán được. Một phép ghép cặp e_n được định nghĩa trên < G₁ > x < G₂ > như sau:

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

trong đó < G₁ > và < G₂ > là các nhóm cyclic có cấp n và µ_n là nhóm cyclic gồm các căn bậc n của phần tử đơn vị. Một phép ghép cặp e_n nhận được bằng cách hạn chế miền xác định của các phép ghép cặp Weil hoặc Tate.

A.4  Phương trình Pell

Phương trình Pell là phương trình có dạng:

trong đó d là một số nguyên cố định. Trong việc xây dựng các đường cong elliptic bằng phép nhân phức sử dụng phương trình Pell với một số nguyên dương d không phải là một số chính phương. Khi đó, tất cả các nghiệm nguyên dương (T,U) được tính bằng cách sử dụng nghiệm dương nhỏ nhất (T₀,U₀) với U₀ > 0 nhỏ nhất như sau:

với k = 1,2,…

CHÚ THÍCH Những điều này được mô tả trong tài liệu tham khảo [28].

A.5  Phương trình Diophantine, x² – dy² = n

Trong việc xây dựng đường cong elliptic bằng phép nhân phức, phương trình Diophantine, x² – dy² = n được sử dụng. Trong đó, n là một số nguyên và d là một số nguyên dương không phải là một số chính phương. Số lượng các nghiệm nguyên của công thức này bằng 0 hoặc vô hạn. Số lượng vô hạn các nghiệm nguyên (x, y) được cho bằng cách sử dụng nghiệm dương nhỏ nhất (T₀, U₀) với U₀> 0 nhỏ nhất của phương trình Pell tương ứng T² – dU² = 1.

CHÚ THÍCH Thông tin chi tiết được mô tả trong tài liệu tham khảo [28].

 

Phụ lục B

(tham khảo)

Thông tin cơ bản về các hệ mật trên đường cong elliptic

B.1  Định nghĩa các bài toán mật mã

B.1.1  Bài toán lôgarit rời rạc trên đường cong elliptic (ECDLP)

Đối với một đường cong elliptic E/F(q), điểm cơ sở G ϵ E[F(q)] có cấp n và một điểm P ϵ E[F(q)], bài toán lôgarit rời rạc trên đường cong elliptic (với điểm cơ sở G) là tìm số nguyên x ϵ (0, n – 1) sao cho P = xG nếu tồn tại x như vậy.

Độ an toàn của các hệ mật trên đường cong elliptic là dựa trên độ khó được tin tưởng của bài toán lôgarit rời rạc trên đường cong elliptic.

B.1.2  Bài toán Diffie-Hellman tính toán trên đường cong elliptic (ECDHP)

Đối với một đường cong elliptic E/F(q), điểm cơ sở G ϵ F[F(g)] có cấp n và các điểm aG, bG ϵ E[F(q)], bài toán Diffie-Hellman tính toán trên đường cong elliptic là tính abG.

Độ an toàn của một số hệ mật trên đường cong elliptic là dựa trên độ khó được tin tưởng của bài toán Diffie-Hellman tính toán trên đường cong elliptic.

B.1.3  Bài toán Diffie-Hellman quyết định trên đường cong elliptic (ECDDHP)

Đối với một đường cong elliptic E/F(q), điểm cơ sở G ϵ E[F(q)] có cấp n và các điểm aG, bG, Y ϵ E[F(q)], bài toán Diffie-Hellman quyết định trên đường cong elliptic là quyết định xem liệu Y = abG hay không.

Độ an toàn của một số hệ mật trên đường cong elliptic là dựa trên độ khó được tin tưởng của bài toán Diffie-Hellman quyết định trên đường cong elliptic.

B.1.4  Bài toán Diffie-Hellman song tuyến tính (BDHP)

Các bài toán Diffie-Hellman song tuyến tính được mô tả theo hai cách tùy thuộc vào các ánh xạ song tuyến tính mật mã tương ứng.

– Cho hai nhóm < G₁ > và < G₂ > có cấp n, một ánh xạ song tuyến tính mật mã e_n: < G₁ > x < G₂ > → µ_n, aG₁, bG₁ ϵ < G₁ >, và aG₂, bG₂ ϵ < G₂ >, bài toán Diffie-Hellman song tuyến tính là tính toán e_n(G₁,G₂)^abc.

– Cho một nhóm < G₁ > có cấp n, một ánh xạ song tuyến tính mật mã e_n: < G₁ > x < G₁ > → µ_n, aG₁, bG₁, cG₁ ϵ < G₁ >, bài toán Diffie-Hellman song tuyến tính là tính toán e_n(G₁, G₁)^abc.

Độ an toàn của một số hệ mật trên đường cong elliptic là dựa trên độ khó được tin tưởng của bài toán Diffie-Hellman song tuyến tính trên đường cong elliptic.

B.1.5  Bài toán lôgarit rời rạc trên đường cong elliptic với các đầu vào phụ trợ (ECDLP với các đầu vào phụ trợ)

Độ an toàn của một số hệ mật dựa trên bài toán lôgarit rời rạc trên đường cong elliptic với các đầu vào phụ trợ.

– ECDLP với các đầu vào bổ sung x²G, x³G, …, x^kG

– ECDHP với các đầu vào bổ sung a²G, a³G, …, a^kG

– BDHP với các đầu vào bổ sung a²G₁, a³G₁, …, a^kG₁

Ba ví dụ về các bài toán trên đường cong elliptic với các đầu vào phụ trợ được trình bày sau đây (tuân thủ ký hiệu từ phần định nghĩa chính thức của các bài toán trong B.1.1, B.1.2 và B.1.4).

B.2  Các thuật toán xác định lôgarit rời rạc trên đường cong elliptic

B.2.1  Độ khó của ECDLP

Độ khó của ECDLP phụ thuộc vào đường cong elliptic E/F(q) được chọn và độ lớn của giá trị n là cấp của điểm cơ sở G. Độ lớn của n phải là lớn hơn hoặc bằng 160 bit để đảm bảo mức an toàn mong đợi trong các hệ mật dựa trên độ khó của ECDLP.

Đường cong elliptic E/F(q) phải được chọn đáp ứng các mục tiêu an toàn xác định chống lại các thuật toán sau đây để giải ECDLP. Độ lớn của n phải được thiết lập đáp ứng các mục tiêu an toàn xác định chống lại thuật toán bước nhỏ – bước lớn và các biến thể khác của thuật toán p của Pollard.

B.2.2  Tổng quan về các thuật toán

Các kỹ thuật sau đây cho phép tính lôgarit rời rạc trên đường cong elliptic:

– Thuật toán Pohlig-Silver-Hellman. Đây là phương pháp “chia để trị” nhằm rút gọn bài toán lôgarit rời rạc trên một đường cong elliptic E định nghĩa trên F(q) thành bài toán lôgarit rời rạc trong các nhóm con cyclic có cấp nguyên tố chia hết #E[F(q)].

– Thuật toán bước nhỏ – bước lớn và các biến thể khác của thuật toán p của Pollard.

CHÚ THÍCH 1 Các biến thể khác của thuật toán p của Pollard được mô tả trong tài liệu tham khảo [33].

– Thuật toán của Frey-Rück ^[19] và thuật toán Menezes-Okamoto-Vanstone ^[23] đều chuyển đổi bài toán lôgarit rời rạc trong một nhóm con cyclic của E với cấp nguyên tố n thành bài toán lôgarit rời rạc trong trường mở rộng nhỏ nhất F(q^B) của F(q) sao cho n chia hết (q^B – 1), trong đó B được gọi là bậc nhúng. Thuật toán Frey-Rück chạy trong các điều kiện yếu hơn so với thuật toán được công bố bởi Menezes-Okamoto-Vanstone.

– Thuật toán của Araki-Satoh ^[29], Smart ^[32] và Semaev ^[31] giải quyết bài toán loogarit rời rạc đối với đường cong elliptic E xác định trên F(p^m) trong trường hợp #E[F(p^m)] = p^m.

Không giống với trường hợp lôgarit rời rạc trong nhóm nhân của một trường hữu hạn nào đó, không tồn tại thuật toán “tính toán chỉ số” đối với trường hợp đường cong elliptic. Về các tấn công sử dụng phép phủ đối với kiểu phủ đặc biệt, ví dụ: tấn công hạ bậc Weil, tấn công GHS,… xem chương 22 của tài liệu tham khảo [11].

CHÚ THÍCH 2 Các thuật toán Pohlig-Silver-Hellman và bước nhỏ – bước lớn làm việc trên tất cả các loại đường cong elliptic trong khi đó các thuật toán Frey-Rück, Menezes-Okamoto-Vanstone, Araki-Satoh, Smart, và Semaev chỉ làm việc trên các đường cong có các thuộc tính đặc biệt.

B.2.3  Điều kiện MOV

Cho n được định nghĩa như trong tập hợp các tham số miền đường cong elliptic, trong đó n là một ước số nguyên tố của #E[F(q)] và q là lũy thừa của một số nguyên tố p. Một giá trị B, được sử dụng cho điều kiện MOV, là số nguyên nhỏ nhất sao cho n chia hết p^B – 1. Như CHÚ THÍCH ở phần trên, các thuật toán Frey-Rück và Menezes-Okamoto-Vanstone biến đổi bài toán lôgarit rời rạc trên một đường cong elliptic trên F(q) thành bài toán lôgarit rời rạc trong trường hữu hạn F(p^B) với một số giá trị B ≥ 1. Qua việc sử dụng tấn công, tính khó của bài toán lôgarit rời rạc trên một đường cong elliptic E/F(q) liên quan đến bài toán lôgarit rời rạc trên một trường hữu hạn F(p^B). Điều kiện MOV đã điều chỉnh theo trường con mô tả bậc B mà đảm bảo mức an toàn của bài toán lôgarit rời rạc trên đường cong elliptic bằng bài toán lôgarit rời rạc trên trường hữu hạn. Đối với một số ứng dụng dựa trên phép ghép cặp Weil và Tate, một giá trị nhỏ hợp lý của B, chẳng hạn lớn hơn hoặc bằng 6, là thích hợp hơn cả.

CHÚ THÍCH Thông tin về bậc B được mô tả trong tài liệu tham khảo [20].

B.2.4  Điều kiện ước số nguyên tố, n

Đối với một số hệ mật dựa trên ECDLP, ECDHP hoặc BDHP với các đầu vào phụ trợ như trong B.1.5, ước số nguyên tố n phải thỏa mãn các điều kiện sau đây: không tồn tại ước số d của n – 1 sao cho (log n)² < d < n^1/2 và không tồn tại ước số e của n + 1 sao cho (log n)² < e < n^1/2. Các ước số d và e có thể là hợp số.

CHÚ THÍCH Độ lớn của d phụ thuộc vào k trong B.1.5, tức là giá trị lớn nhất của ước số lớn nhất của n – 1 không vượt quá giá trị nhỏ nhất giữa k và √n. Thông tin chi tiết thêm về d và e có trong tài liệu tham khảo [14].

 

Phụ lục C

(tham khảo)

Các ví dụ số

C.1  Ví dụ số cho các đường cong elliptic giả ngẫu nhiên kiểm tra được

C.1.1  Giới thiệu chung

Tham chiếu tài liệu tham khảo [8] cho mục này. Các tham số được chọn từ một mầm sử dụng SHA-1.

C.1.2  Đường cong elliptic trên trường nguyên tố (192 bit)

C.1.3  Đường cong elliptic trên trường nguyên tố (224 bit)

C.1.4  Đường cong elliptic trên trường nguyên tố (256 bit)

C.1.5  Đường cong elliptic trên trường nguyên tố (384 bit)

C.1.6  Đường cong elliptic trên trường nguyên tố (521 bit)

C.2  Ví dụ số cho đường cong MNT

C.2.1  Giới thiệu chung

Thông tin cụ thể về các ví dụ cho đường cong Miyaji-Nakabayashi-Takano (MNT) trong 7.2 có trong tài liệu tham khảo [26].

C.2.2  Đường cong elliptic trên trường nguyên tố (160 bit)

C.2.3  Đường cong elliptic trên trường nguyên tố (256 bit)

C.3  Ví dụ số cho đường cong BN

C.3.1  Giới thiệu chung

Tất cả các ví dụ sau đây được chọn sao cho p là số nguyên tố lớn nhất thỏa mãn p = 3 (mod 4) và p = 4 (mod 9) đối với tham số lớn nhất u có trọng số Hamming nhỏ nhất, cho phép trường mở rộng F(p²) được biểu diễn thành F(p)[i]/(i² + 1) và trường mở rộng F(p^2m) được biểu diễn thành F(p²)[z]/(z^m – v) với m = 2,3,6 và v = 1 + i. Việc tính các căn bậc hai (hoặc bậc ba) cần thiết cho việc nén điểm và/hoặc phép ghép cặp cũng được đơn giản hóa trong cả F(p) và F(p²). Ngoài ra, phương trình đường cong có dạng E: y² = x³ + 3 với điểm cơ sở hiển nhiên G = (1,2) và xoắn bậc sáu E’/F(p²) có dạng E’: y’² = x’³ + 3v chứa một nhóm con có cấp n và đồng hệ số h = 2p – n, với điểm cơ sở G’ = hG’₀, trong đó G’₀ là điểm với tọa độ x là x’₀ = 1. Cuối cùng, đẳng cấu ψ: E’/F(p²) → E/F(p¹²) có dạng ψ/(x’,y’) = (x’v^-1z⁴,y’v^-1z³), với z⁶ = v. Những đặc tính này tạo điều kiện thuật lợi cho việc thực thi cặp Tate hoặc Weil (thuần túy hoặc nén) e: E x E’ → F(p^2m), với các cặp tối ưu đặc biệt được hưởng ưu thế từ dạng thưa của u. Thông tin chi tiết cho những ví dụ này có trong tài liệu tham khảo [12].

C.3.2  Đường cong elliptic trên trường nguyên tố (160 bit)

C.3.3  Đường cong elliptic trên trường nguyên tố (192 bit)

C.3.4  Đường cong elliptic trên trường nguyên tố (224 bit)

C.3.5  Đường cong elliptic trên trường nguyên tố (256 bit)

C.3.6  Đường cong elliptic trên trường nguyên tố (384 bit)

C.3.7  Đường cong elliptic trên trường nguyên tố (512 bit)

C.4  Ví dụ số cho đường cong Freeman

C.4.1  Giới thiệu chung

Thông tin cụ thể về các ví dụ trong 7.4 có trong tài liệu tham khảo [18].

C.4.2  Đường cong elliptic trên trường nguyên tố (234 bit)

C.4.3  Đường cong elliptic trên trường nguyên tố (252 bit)

 

Phụ lục D

(tham khảo)

Tóm tắt các thuộc tính của các đường cong elliptic được sinh bằng phương pháp nhân phức

Trong phụ lục này, các thuộc tính của bốn phương pháp sinh đường cong bằng phương pháp nhân phức cho các đường cong MNT, đường cong BN, đường cong F và đường cong CP được tổng hợp, trong đó sử dụng những ký hiệu sau đây.

– E[F(p)], #E[F(p)] = rn (r: đồng hệ số, n: ước số nguyên tố)

– B: bậc nhúng

– 4p – t² = Dy² (t: vết, D: số nguyên không có ước chính phương)

Bảng D.1 là bảng tóm tắt các thuộc tính của các đường cong được sinh bởi bốn phương pháp.

Bảng D.1 – Tóm tắt các đường cong elliptic được sinh bởi phương pháp nhân phức tạp

	B	D	log2p/log2n	Đặc tính
Đường cong MNT	3, 4, 6	D ≡ 3(mod 8)	1	Có thể xây dựng tất cả các đường cong elliptic cấp nguyên tố với B = 3,4,6.
Đường cong BN	12	3	1	Xây dựng được một đường cong elliptic với D = 3 và B = 12 (không phải tất cả).
Đường cong F	10	D ≡ 43 hoặc 47 (mod 1 và 15D là số không chính phương	1	Xây dựng được một đường cong elliptic với B = 10 (không phải tất cả).
Đường cong CP	Tùy chọn	Tùy chọn	> 2	log2p > 2log2n

 

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

[1] ISO/IEC 9796-3, Information technology – Security techniques – Digital signature schemes giving message recovery – Part 3: Discrete logarithm based mechanisms

[2] ISO/IEC 10118 (all parts), Information technology – Security techniques – Hash-functions

[3] ISO/IEC 11770-3, Information technology – Security techniques – Key management – Part 3: Mechanisms using asymmetric techniques

[4] ISO/IEC 14888-3, Information technology – Security techniques – Digital signatures with appendix – Part 3: Discrete logarithm based mechanisms

[5] ISO/IEC 18032, Information technology – Security techniques – Prime number generation

[6] ISO/IEC 18033-2, Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers

[7] ISO/IEC 29192-4, Information technology – Security techniques – Lightweight cryptography – Pad 4: Mechanisms using asymmetric techniques

[8] FIPS. 186-2, Digital Signature Standard. Federal Information Processing Standards Publication 186-2, 2000. Available from: http://csrc.nist.gov/

[9] IEEE P1363-2000, Standard Specifications for Public-Key Cryptography

[10] ATKIN A.O.L., & MORAIN F. Elliptic curves and primality proving. Math. Comput. 1993, 61 pp. 29-68

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

[12] BARRETO P.S.L.M., & NAEHRIG M. Pairing-friendly elliptic curves of prime order. In: Selected Areas in Cryptography-SAC’2005, LNCS 3897. Springer-Verlag, 2006, pp. 319-31.

[13] BLAKE I., SEROUSSI G., SMART N. “Advances in elliptic curve cryptography”, London Mathematical Society Lecture Note Series 317

[14] CHEON J. Security Analysis of the Strong Diffie-Hellman Problem. In: Eurocrypt 2006, LNCS 4004. Springer-Verlag, 2006, pp. 1-11.

[15] COHEN H. “A course in computational algebraic number theory”, Graduate Texts in Math. 138, Springer-Verlag, 1993, Third corrected printing, 1996.

[16] Cox D A. “Primes of the form x² + ny²“, A Wiley-lnterscience Publication, 1989

[17] DEURING M. Die Typen der Multiplikatorenringe elliptischer Funktionenkorper. Abh. Math. Sem.Hamburg. 1941, 14 pp. 197-272

[18] FREEMAN D. “Constructing pairing-friendly elliptic curves with embedding degree 10”, In ANTS-V11, Springer- Verlag, LNCS 4076, Berlin, 2006, 452-465

[19] 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

[20] HITT L. “On the minimal embedding field”, In Proceedings of the International Conference on Pairing-Based Cryptography 2007 (Pairing 2007), LNCS 4575 (2007), Springer-Verlag, 294-301

[21] KOHEL D.R. “Algorithms for Algebra and Geometry Experimentation” http://echidna.maths.usvd.edu.au/~kohel/dbs/

[22] MATTHEWS K. The Diophantine equation x²Dy² = N, D> 1. Expo. Math. 2000, 18 pp. 323-331

[23] MENEZES A., OKAMOTO T., VANSTONE S. “Reducing elliptic curve logarithms to logarithms in a finite field”, Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing (1991), 80-89

[24] MIYAJI A., NAKABAYASHI M., TAKANO S. “New explicit conditions of Elliptic Curve Traces under FR reduction”, IEICE Trans. Fundamentals. 2001, E84-A (5) pp. 1234-1243

[25] MOLLIN R. Fundamental Number Theory with Applications. CRC Press, Boca Raton, 1998

[26] PAGE D Smart N.P., Vercauteren F. A comparison of MNT curves and supersingular curves”, AAECC, 17. Springer-Verlag, 2006, pp. 379-392

[27] ROBERTSON J. “Solving the generalized Pell equation”, Unpublished manuscript (2004), available at http://www.jpr2718.org/pell.pdf

[28] ROSEN K.H. Elementary number theory and its applications. Addison Welsley Longman, 1999

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

[30] ScHooF R. Elliptic Curves Over Finite Fields and the Computation of Square Roots mod Math.Comput. 1985, 44 pp. 483-494

[31] SEMAEV I.A. Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Math. Cornput. 1998, 67 pp. 353-356

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

[33] WASHINGTON L.C. Elliptic Curves-Number Theory and Cryptography. Chapman & Hall/CRC, Second Edition, 2008

 

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

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

4  Các Ký hiệu và hàm chuyển đổi

4.1  Ký hiệu

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

5  Khuôn khổ cho việc sinh đường cong elliptic

5.1  Các kiểu đường cong elliptic tin cậy

5.2  Tổng quan về việc sinh đường cong elliptic

6  Sinh đường cong elliptic giả ngẫu nhiên kiểm tra được

6.1  Giới thiệu chung

6.2  Xây dựng đường cong elliptic giả ngẫu nhiên kiểm tra được (trường hợp trường nguyên tố)

6.2.1  Thuật toán xây dựng

6.2.2  Kiểm tra tính gần nguyên tố

6.2.3  Tìm một điểm có cấp nguyên tố lớn

6.2.4  Kiểm tra tính giả ngẫu nhiên của đường cong elliptic

6.3  Xây dựng đường cong elliptic giả ngẫu nhiên kiểm tra được (trường hợp trường nhị phân)

6.3.1  Thuật toán xây dựng

6.3.2  Kiểm tra tính giả ngẫu nhiên của đường cong elliptic

7  Xây dựng đường cong elliptic bằng phép nhân phức

7.1  Cấu trúc chung (trường hợp trường nguyên tố)

7.2  Đường cong Miyaji-Nakabayashi-Takano (MNT)

7.3  Đường cong Barreto-Naehrig (BN)

7.4  Đường cong Freeman (đường cong F)

7.5  Đường cong Cocks-Pinch (CP)

8  Xây dựng đường cong elliptic bằng phép nâng

Phụ lục A (tham khảo) Thông tin cơ bản về các đường cong elliptic

Phụ lục B (tham khảo) Thông tin cơ bản về các hệ mật trên đường cong elliptic

Phụ lục C (tham khảo) Các ví dụ số

Phụ lục D (tham khảo) Tóm tắt các thuộc tính của các đường cong elliptic được sinh bằng phương pháp nhân phức

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