臺灣博碩士論文加值系統

橢圓曲線密碼系統的安全性是建立於橢圓曲線離散對數問題 (ECDLP) 的困難度。
二元有限體 ECDLP 最具發展性的是一種 index calculus 演算法,它運用了 Semaev 加法多項式還有 Weil descent 產生出一個可用 Gröbner 基底演算法求解的多項式系統。在本篇論文中,我們用 SageMath 實作了 index calculus 演算法,對其做詳細的介紹並記錄了實作的結果。

The security of elliptic curve cryptosystems is based on the hardness of the elliptic curve discrete logarithm problem(ECDLP). The most promising algorithm for ECDLP in binary fields is the index calculus method using Semaev’s summation polynomials and Weil Descent to create a polynomial system that is subsequently solved with Gröbner basis method. In this thesis we use SageMath to implement this type of index calculus method, discuss the algorithm in details and record the results.

1 Introduction 1
2 Background 2
2.1
2.2
Arithmetic on finite field . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.1 Group, Ring and Field . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1.2 Extension field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.1 Weierstrass equation . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2.2 Elliptic curves over binary fields . . . . . . . . . . . . . . . . . . . . 5
2.2.3 Points operations on elliptic curves over binary field . . . . . . . . . 6
3 Algorithms for Discrete Logarithm Problem
7
3.1 Discrete logarithm problem (DLP) . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Baby-step giant-step algorithm . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 Pollard’s rho method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4 Pollard’s lambda(kangaroo) method . . . . . . . . . . . . . . . . . . . . . . 9
3.5 Index calculus method for DLP . . . . . . . . . . . . . . . . . . . . . . . . 10
4 Index Calculus for ECDLP
12
4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 Semaev’s Summation polynomials . . . . . . . . . . . . . . . . . . . . . . . 14
4.3 Weil Descent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4.4 Gröbner basis method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5 Implementation and Evaluation
5.1
21
SageMath . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215.2
5.1.1 Fields and rings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.1.2 Elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.1.3 Points on elliptic curves . . . . . . . . . . . . . . . . . . . . . . . . 23
5.1.4 SageMath file extension . . . . . . . . . . . . . . . . . . . . . . . . 24
Implementation code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.1 Function code explanation . . . . . . . . . . . . . . . . . . . . . . . 25
5.2.2 Main function explanation . . . . . . . . . . . . . . . . . . . . . . . 28
5.3 Example when m=2 over finite field F 2 11 . . . . . . . . . . . . . . . . . . . 31
5.4 Experimental results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6 Conclusion 36
Appendices 37
A f x i , i= 1 to 10 in Section 5.3 38
B Source Code 42

[1] ARM. ECC on RAMs. url: http://infocenter.arm.com/help/index.jsp?
topic=/com.arm.doc.ddi0458c/BABCGIII.html.
[2] D. Shanks. “Class Number, a Theory of Factorization and Genera”. In: Proceedings of Symposium of Pure Mathematics, Vol. 20, 1971, pp. 415–440.
[3] J. M. Pollard. “Monte Carlo Methods for Index Computation (mod p)”. In: MATHEMATICS OF COMPUTATION, VOLUME 32, NUMBER 143, 1978, pp. 918–924.
[4] M. Kraitchik. “Théorie des nombres”. In: Gauthier–Villards, 1922.
[5] L. M. Adleman. “A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography”. In: the 20th Annual Symposium on Foundations of Computer Science, SFCS ’79, 1979, pp. 55–60.
[6] R. W. Floyd. “Non-deterministic Algorithms”. In: Journal of the Association for Computing Machinery, Vol. 14, No 4, 1967, pp. 636–644.
[7] Igor Semaev. “Summation polynomials and the discrete logarithm problem on elliptic curves”. In: 2004.
[8] Pierrick Gaudry. “Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem”. In: J. Symb. Comput., 2009.
[9] Claus Diem. “On the Discrete Logarithm Problem in Elliptic Curves”. In: Composition Mathematica, 147, 2011, pp. 75–104.
[10] Christophe Petit and Jean-Jacques Quisquater. “On Polynomial Systems Arising from a Weil Descent”. In: 2012.
[11] Bruno Buchberger. “Groebner Bases: A Short Introduction for Systems Theorists”. In: 2001.53
[12] Jean-Charles Faugère. “A new efficient algorithm for computing Gröbner bases (F4)”. In: ournal of Pure and Applied Algebra, 139(1-3), pp. 61–88.
[13] Jean-Charles Faugère. “A new efficient algorithm for computing Gröbner bases without reduction to zero (F5)”. In: 2002 international symposium on Symbolic and algebraic computation, ISSAC ’02, pp. 75–83.
[14] The SageMath Project. SageMath. url: http://www.sagemath.org/.
[15] The SageMath Project. Finite Fields. url: http://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/finite_field_constructor.html.
[16] The SageMath Project. Polynomials. url: http://doc.sagemath.org/html/en/tutorial/tour_polynomial.html.
[17] The SageMath Project. Elliptic curves. url: http://doc.sagemath.org/html/en/constructions/elliptic_curves.html.
[18] The SageMath Project. Points on elliptic curves. url: http://doc.sagemath.org/html/en/reference/plane_curves/sage/schemes/elliptic_curves/ell_point.html.
[19] Python. Python. url: https://docs.python.org/3/library/functions.html#exec.