04-Chứng minh tính chất kết hợp của phép cộng điểm trên đường cong elliptic bằng phương pháp đại số

Mở đầu

Trong cuốn "Elliptic Curves Diophantine Analysis" năm 1978, Serge Lang đã phát biểu gây sốc rằng: “Có thể viết vô tận về đường cong elliptic!”. Đường cong elliptic là một đường cong có phương trình dạng $y^2=x^3+Ax+B$ (Hình 1). Một đường cong không quá phức tạp nhưng ẩn chứa bên trong vô vàn những điều kỳ diệu của toán học và không chỉ có toán học thuần túy mà các lý thuyết về elliptic này cũng đang len lỏi hàng ngày hàng giờ khi hàng tỷ người đang sử dụng Internet một cách vô thức, không biết rằng họ vẫn đang áp dụng thường xuyên các thuật toán của elliptic một cách tự động.

Hình 1: Đường cong elliptic và phép cộng điểm trên đường cong

Đường cong elliptic là cơ sở nền tảng để tạo ra Hệ mật dựa trên đường cong elliptic - Elliptic Curve Cryptography (ECC). Năm 1985, Victor S. Miller công bố bài báo đầu tiên về ứng dụng đường cong EC trong mật mã "Use of elliptic Curves in Cryptography"và sau đó là Neal Koblitz với "Elliptic curve cryptosystem" vào năm 1987. Từ đó cho đến nay đã có rất nhiều công bố nghiên cứu về ECC về lý thuyết và trong thực tiễn càng ngày ứng dụng ECC càng được sử dụng rộng rãi, và đã được đưa thành các tiêu chuẩn. ECC có độ dài khóa nhỏ hơn RSA khá nhiều (6 đến 30 lần tùy theo độ dài khóa), thời gian ký số và xác thực cơ bản cũng nhanh hơn so với thuật toán RSA vì thế ECC đang và sẽ được ứng dụng rất nhiều trong thực tế [4]:

• Ứng dụng ECC trong các trang web bảo mật: Hầu như tất cả các trang thương mại điện tử, cũng như chính phủ điện tử đều phải dùng giao thức HTTPS và TLS/SSL để mã hóa thông tin trên đường truyền. Để trao đổi khóa, giao thức ECDHE (Elliptic Curve Diffie Hellman Ephemeral) được sử dụng rất phổ biến. Theo [4] trong 100 trang web có lượng truy cập lớn nhất thế giới thì có đến 96% sử dụng trao đổi khóa bằng ECDHE. Hàng ngày chúng ta vào Facebook, Gmail,,,các trang này cũng đều sử dụng hệ mật ECC để trao đổi khóa phiên.
• Giao thức phân giải tên miền DNS mở rộng (DNS Security Extensions (DNSSEC)) cũng sử dụng chữ ký số dựa trên ECC để xác thực và chống tấn công DDoS [5].
• Các giao dịch remote access được dùng rất nhiều trong thế giới Unix, Linux là SSH (Secure SHell) cũng sử dụng ECC để trao đổi khóa. 
• ECC hiện đang được áp dụng trong một loạt các ứng dụng: chính phủ Mỹ sử dụng để bảo vệ thông tin liên lạc nội bộ, các dự án Tor sử dụng để giúp đảm bảo ẩn danh.
• Chữ ký số dựa trên ECC là ECDSA (Elliptic Curve Digital Signature Algorithm) được sử dụng trong gần như tất cả các nền tảng Blockchain (cả Private và Public). Apple cũng dùng ECDSA để ký số trong dịch vụ iMessage.
• Trong lĩnh vực IoT và thiết bị di động do tài nguyên phần cứng hạn chế nên hệ mật khóa công khai thường sử dụng ECC thay cho RSA.
• Về ứng dụng lý thuyết: đường cong elliptic được dùng để chứng minh định lý Fermat cuối cùng. Năm 1637, nhà toán học và vật lý học người Pháp Pierre de Fermat công bố định lý Fermat cuối cùng khi viết trên lề bản copy công trình của Diophant: Phương trình sau đây là vô nghiệm: 

  $x^n + y^n = z^n$

  Hơn ba thế kỷ, đã có rất nhiều nhà toán học cố gắng chứng minh định lý này nhưng đều thất bại, mãi cho đến năm 1994, Andrew Wiles, giáo sư trường Princeton đã gây một tiếng vang lớn trong cộng đồng toán học thế giới vào thời điểm đó khi sử dụng đường cong elliptic có dạng $y^2 = x(x-a^n)(x+b^n)$ cùng với lý thuyết về Modul để chứng minh định lý Fermat cuối cùng.
• Năm 1987, Lenstra đề xuất thuật toán phân tích số nguyên ra thừa số nguyên tố sử dụng đường cong elliptic, đó là thuật toán nhanh, chạy với thời gian dưới hàm mũ và là thuật toán nhanh thứ 3 trong việc phân tích ra thừa số nguyên tố, sau phương pháp sàng đa thức toàn phương và phương pháp sàng trường số tổng quát.
• Hệ mật ECC có thể bị bẻ khóa với máy tính lượng tử (Quantum Computer) với cỡ khoảng 1000 qubit (Hiện nay máy lượng tử mạnh nhất mới chỉ có 72 qubit). Tuy nhiên dựa trên lý thuyết về đường cong elliptic có thể xây dựng một hệ mật mã khác có khả năng chống được tấn công của  máy tính lượng tử, đó là Elliptic Curve Isogeny Cryptography [6].
• Dựa trên lý thuyết về divisor (điểm ước) của đường cong elliptic có thể xây dựng được lý thuyết về cặp song tuyến tính từ đó phát triển được hệ mật mã dựa trên định danh (ID-Based), trong các hệ mật này có thể lấy số chứng minh thư hay địa chỉ email của người dùng làm khóa công khai, nhờ vậy không phải phân phối khóa, quản lý khóa công khai như các hệ mật khóa công khai hiện hành.
• Thông tư số 39/2017/TT-BTTTT ngày 15/12/2017 của Bộ trưởng Bộ Thông tin và Truyền thông Công bố Danh mục tiêu chuẩn kỹ thuật về ứng dụng công nghệ thông tin trong cơ quan nhà nước quy định Khuyến nghị áp dụng tiêu chuẩn ECC - Elliptic Curve Cryptography và được xếp vào nhóm Tiêu chuẩn về an toàn thông tin.

Cơ sở lý thuyết về đường cong elliptic

Mặc dù đường cong elliptic (EC) được ứng dụng rất nhiều trong Công nghệ thông tin (CNTT), ứng dụng hàng ngày, nhưng có rất ít người hiểu sâu sắc về nó, trong nước chỉ có khoảng 5 tác giả có các nghiên cứu và công bố đến EC, thậm chí nhiều chuyên gia về CNTT còn chưa từng nghe đến Elliptic Curve (EC).

Một trong những nguyên nhân của sự thiết hụt hiểu biết về EC là lý thuyết về đường cong Elliptic (EC) rất khó và đồ sộ, có thể kể ra một số lý thuyết liên quan đến EC:

• Lý thuyết nhóm, vành, trường trong đại số trừu tượng;
• Đa tạp Affine, đa tạp Jacobian và đa tạp xạ ảnh trong hình học đại số;
• Điểm Torsion, Divisor, cặp song tuyến tính Weil, Tate-Lichtenbaum;
• Lý thuyết trường Galois, tự đồng cấu-ánh xạ Frobenius;
• Lý thuyết Baker-Feldman, Baker-Tijdeman và lý thuyết Kummer;
• Số p-adic, Isogenies, hàm Sigma và hàm Zeta;
• Nhóm đối đồng điều, đối đồng điều Galois và đối đồng điều phi giao hoán (Topo đại số);
• Nhóm Mordell–Weil, Selmer và nhóm Shafarevich–Tate;
• Phương pháp hình học và Tựa tuyến tính (Quasilinear).

Lý thuyết quan trọng nhất để tạo ra các ứng dụng trong ECC là định nghĩa về phép cộng hai điểm trên đường cong elliptic. Điều kiện rất quan trọng là các điểm trên đường cong với phép cộng phải tạo nên nhóm (group), khi đó có phép cộng điểm phải có các tính chất sau:

1. Có tính giao hoán: $P_1+P_2=P_2+P_1$;
2. Tồn tại điểm 0; $P+0=P$.
3. Tồn tại điểm đối: $P + (-P) =0$.
4. Có tính chất kết hợp: $P_1+(P_2+P_3)=(P_1+P_2)+P_3$.

Phép cộng 2 điểm trên đường cong $P+Q$ là điểm đối xứng qua trục $x$ của điểm cắt giữa đường cong với đường thẳng đi qua $P$ và $Q$ (Hình 1). Ba tính chất đầu có thể dễ dàng suy ra từ định nghĩa hoặc dễ dàng nhận thấy. Duy nhất tính chất 4 (tính kết hợp) là phần khó nhất. Tiếp theo chúng ta sẽ bàn về một số phương pháp chứng minh tính kết hợp của phép cộng trên EC. 

Chứng minh tính chất kết hợp của phép cộng trên đường cong elliptic

Có hai phương pháp chính để chứng minh tính chất kết hợp của phép cộng trên EC là a/ Chứng mình bằng lý thuyết về hình học đại số và b/ Chứng minh bằng đại số.

Chứng minh bằng hình học: W. Fulton dùng định lý Bézout (hai đường cong elliptic sẽ giao nhau ở nhiều nhất là 9 điểm): Hai điểm $P_1, P_2$ sẽ cắt đường cong E tại điểm $P_1P_2$ và đối xứng của điểm này chính là điểm tổng $P_1+P_2$ như vậy 4 điểm này nằm trên cùng đường cong $E$, tương tự vậy hai điểm $P_3, P_2$ sẽ cắt đường cong E tại điểm $P_3P_2$ và đối xứng của điểm này chính là điểm tổng $P_3+P_2$ do đó 4 điểm này cũng nằm trên cùng đường cong $E'$, như vậy 2 điểm $P_3$ và $(P_1+P_2)$  sẽ cắt đường cong tại $R$, tương tự vậy $P_1$ và $(P_3+P_2)$  sẽ cắt đường cong tại $R'$. Hai đường cong $E$ và $E'$ đã cắt nhau ở 8 điểm (4+4), thì sẽ cắt nhau ở 1 điểm nữa  và vì thế buộc $R=R'$, do đó 2 điểm tổng này phải bằng nhau (Hình 2).

Hình 2: Chứng minh tính kết hợp của EC bằng hình học

Cách chứng minh này cũng khá khó hình dung và đặc biệt để chứng minh định lý Bézout cần phải có kiến thức nền tảng về hình học đại số (Algebaraic Geometry) và các khái niệm về không gian xạ ảnh và đường cong xạ ảnh (projective plan curves) và các khái niệm về không gian Affine, đa tạp Affine (Varieties). Các khái niệm này đều khá xa lạ với các chuyên gia trong lĩnh vực Công nghệ Thông tin (CNTT).

Ngoài cách chứng minh định lý Bézout của Fulton [7], còn có cách khác của Shafarevich [8] dùng một số định lý và bổ đề liên quan đến khái niệm divisor  (điểm ước) của đường cong elliptic, cũng là những khái niệm khó hiểu đối với sinh viên ngành CNTT.

Chứng minh bằng đại số: đựa vào công thức tính tổng hai điểm trên đường cong elliptic, có thể xem trong [1] hay trong http://j.mp/elliptic20 :

 $P_{12}(x_{12},y_{12})=P_1(x_1,y_1)+P_2(x_2,y_2)$ 

Tiếp theo áp dụng công thức này cho việc tính các tổng  $P_{32}=P_3+P_2$ , $P_{123}=P_{12}+P_3$, $P_{321}=P_{32}+P_1$. Ta phải chứng minh rằng $P_{123}=P_{321}$, muốn chứng minh điều này ta chỉ cần chứng minh $x_{123}=x_{123}$ và $x_{321}=x_{321}$.

Phương pháp chứng minh đại số này người viết đã đăng tải trên Tạp chí Epsilon năm 2016 [1]. Năm sau đó (2017) có 2 nhóm tác giả là K. Fujii, H. Oike [2] và  S. Friedl [3] cũng công bố phương pháp chứng minh tương tự bằng đại số, tuy nhiên các công bố này cũng chỉ nêu các ý tưởng chính, mà chưa trình bày các kết quả cụ thể, vì vậy trong bài viết này người viết sẽ trình bày phần chứng minh một cách đầy đủ bằng phương pháp đại số. Toàn văn file PDF chứng minh có thể download hoặc xem ở đây.

Đây là phần chứng minh rất dài, bao gồm 363 trang A4, có nhiều công thức và biểu thức rất phức tạp, có một công thức dài tới 100 trang A4. 

Hình 3: Công thức đệ lệch tọa độ của điểm $P_{123}$ và $P_{321}

Tuy chỉ là công thức tính tọa độ giữa ba điểm $P_1,P_2,P_3$ nhưng vì trong đó có hệ số góc là các phân số, thành phần mẫu số và tử số của các phân số này lại có tọa độ của các điểm được tính từ trước đó cũng liên quan đến hệ số góc là các phân số, do đó có thể đến 6 tầng phân số khác nhau, khi quy đồng các mẫu số này sẽ dẫn tới bùng nổ các toán hạng, và theo thống kê thì có đến hơn 30 ngàn các phép tính để ra được kết quả cuối cùng.

Hình 4: Tài liệu chứng minh tính kết hợp của phép cộng trên EC ở đây 

Kết luận

Hệ mật dựa trên đường cong elliptic đã và đang được sử dụng ngày càng nhiều trong các hoạt động thực tiễn khi phải trao đổi thông tin trong môi trường Internet cần đến các phương pháp mã hóa dữ liệu. Bài viết này là một trong các nỗ lực để giúp cho các bạn quan tâm tìm hiểu sâu các cơ sở toán học nền tảng phía sau các công nghệ bảo mật thông tin cụ thể là hệ mật đường cong elliptic. Bài viết để cập đến phần chứng minh một trong những tính chất cơ bản nhất của cơ sở toán học và mật mã của đường cong elliptic, phần lớn trong các tài liệu chỉ thừa nhận kết quả này mà ít có phần chứng minh, hoặc các chứng minh đòi hỏi một nền tảng toán học rất xa so với các hiểu biết thông thường của ngành CNTT. Người viết muốn trình bày một cách chi tiết và đầy đủ cách chứng minh tính kết hợp của phép cộng trên đường cong elliptic bằng phương pháp đại số, qua đó cũng cho người đọc thấy đó là phương pháp rất dài phức tạp. Từ những nghiên cứu này người viết đã có một cách chứng minh mới ngắn gọn hơn rất nhiều, chỉ  với 1 trang A4 thay cho 393 trang như cách thông thường đã trình bày ở trên. Cách chứng minh mới này sẽ được đăng tải trên một tạp chí có uy tín trong thời gian tới đây.

Đặng Minh Tuấn, tuanvietkey@gmail.com

Tài liệu tham khảo

[1] Đ. M. Tuấn, “Hệ mật mã khóa công khai dựa trên đường cong Elliptic - Một số ứng dụng (1),” Epsilon Magazine, vol. 9, pp. 17–35, 2016.

[2] K. Fujii and H. Oike, “An Algebraic Proof of the Associative Law of Elliptic Curves,” Advances in Pure Mathematics, vol. 07, no. 12, pp. 649–659, 2017.

[3] S. Friedl, “An elementary proof of the group law for elliptic curves,” Groups, Complexity, Cryptology, vol. 9, no. 2, pp. 117–123, 2017.

[4] R. Harkanson and Y. Kim, “Applications of elliptic curve cryptography: A light introduction to elliptic curves and a survey of their applications,” ACM International Conference Proceeding Series, no. 1, 2017.

[5] Roland van Rijswijk-Deij, Kaspar Hageman, Anna Sperotto, and Aiko Pras. "The Performance Impact of Elliptic Curve Cryptography on DNSSEC Validation". IEEE/ACM Transactions on Networking, pp 99 (Sep. 2016).

[6] Brian Koziel, Reza Azarderakhsh, Mehran Mozaffari Kermani, and David Jao. 2016. “Post-Quantum Cryptography on FPGA Based on Isogenies on Elliptic Curves”. IEEE Transactions on Circuits and Systems I: Regular Papers 64, 1 (Oct. 2016).

[7] William Fulton, Algebraic Curves - An Introduction to Algebraic Geometry, Wesley, 1969.

[8] Igor R. Shafarevich,Basic Algebraic Geometry 1, Springer, 2013.