臺灣博碩士論文加值系統

1989年Koblitz 利用定義在有限域的超橢圓曲線上的Jacobian加法群，基於超橢圓曲線離散對數問題的困難度，提出了超橢圓曲線密碼系統。在含有q個元素的有限域Fq中，虧格(genus)為g的超橢圓曲線，其中形成離散對數問題的加法群大小為O(q^g) ，大於橢圓曲線加法群O(q) 。而且小虧格的超橢圓曲線亦無時間複雜度為次指數的攻擊法，因此適當的設定超橢圓曲線密碼系統將可使用比橢圓曲線密碼系統更短的密鑰，來達到相同的安全度。
目前index calculus攻擊法在虧格 g遠大於log(q)時，呈現次指數的時間複雜度。當虧格不大時，一般的生日攻擊法為O(q^(g/2))，而一般的index calculus為O(q^2)。Thériault的index calculus演算法加入”大質數”的概念，時間複雜度降為O(q^(2-4/(2g-1)))；而Gaudry等人利用兩個大”質數”的index calculus攻擊法變形，則時間複雜度更進一步改進為O(q^(2-2/g))。本文將針對小虧格的超橢圓曲線離散對數問題，實作並改進index calculus攻擊法。我們亦提出一個更快的演算法來解虧格為2的超橢圓曲線離散對數問題，其時間複雜度為O(q)。

In 1989, Koblitz proposed using the Jacobian of a hyperelliptic curve defined over a finite field to implement discrete logarithm cryptographic protocols. The discrete logarithm problem of the Jacobian is called hyperelliptic curve discrete logarithm problem (HCDLP). For a hyperelliptic curve of genus g over the finite field Fq, the group order of the Jacobian is O(q^g) which is larger than that of the additive group ,which is O(q), in an elliptic curve over Fq. Since there is no subexponential algorithm to solve HCDLP of small genus, hyperelliptic curve cryptosystem under applicable setting requires shorter key size than elliptic curve cryptosystem to achieve the same security level.
When genus g is large enough, the index calculus attack has subexponential time complexity. For small genus HCDLP, the algorithms based on birthday paradox is of time complexity O(q^(g/2)), and the basic index calculus attack is O(q^2). Thériault improves it by using the large prime method, and get a running time of O(q^(2-(4/(2g-1))). Furthermore, Gaudry et al use a double large prime variation for small genus hyperelliptic index calculus, and the time complexity is O(2-2/g). In this thesis, we focus on the hyperelliptic curve discrete logarithm problem of small genus, implement and improve index calculus and its variations. We propose a faster algorithm for solving genus 2 HCDLP which time complexity is O(q).

Chapter 1 Introduction 1
1.1 History 1
1.2 The organization of the thesis 2
Chapter 2 Mathematical Background 4
2.1 Abstract algebra 4
2.2 Algebraic geometry 8
2.3 Divisor theory 12
Chapter 3 Hyperelliptic Curves 16
3.1 Definitions and properties 17
3.2 Reduced divisors 19
3.3 Representation 20
3.4 Group law 22
3.5 Hyperelliptic curve discrete log problem (HCDLP) 23
Chapter 4 Algorithms for HCDLP 26
4.1 Introduction 26
4.2 Index calculus algorithm for small genus HCDLP 28
4.2.1 Reduced factor base 35
4.2.2 Single large prime variation 36
4.2.3 Double large prime variation 40
4.3 Computational comparison 43
4.3.1 Solving large sparse linear system 43
4.3.2 Curve selection 44
4.3.3 Comparisons 46
Chapter 5 A Fast Algorithm for Genus 2 HCDLP 48
5.1 Introduction 48
5.2 The algorithm 51
5.3 Time complexity 54
5.4 Computational comparison 55
Chapter 6 Conclusion and Future Research 57
6.1 Summary 57
6.2 Future work 58

[1] L. Adleman, J. DeMarrais and M. Huang, “A Subexponential Algorithm for Discrete Logarithms over the Rational Subgroup of the Jacobians of Large Genus Hyperelliptic Curves over Finite Fields,” Algorithmic Number Theory, LNCS 877 (1994), 28-40.
[2] D. Cantor, “Computing in the Jacobian of a Hyperelliptic Curve,” Mathematics of Computation, 48 (1987), 95-101.
[3] David G. Cantor and Hans Zassenhaus, “A New Algorithm for Factoring Polynomials Over Finite Fields,” Mathematics of Computation, 36:587-592, 1981.
[4] H. Cohen and G. Frey, Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman & Hall/CRC, 2006.
[5] D. Coppersmith, “Solving Linear Equations over GF(2) via Block Wiedemann Algorithm,” Math. Comp., 62(205):333-350, 1994.
[6] A. Enge, “Computing Discrete Logarithms in High-genus Hyperelliptic Jacobians in Provably Subexponential Time,” Math. Comp., 71, no. 238, pp. 729-742, 2002.
[7] A. Enge and P. Gaudry, “A General Framework for Subexponential Discrete Logarithm Algorithms”, Acta Arithmetica, 102 (2002), 83-103.
[8] P. Flajolet, D. Knuth and B. Pittel, “The First Cycles in an Evolving Graph,” Discrete Math., 75:167-215, 1989.
[9] R. Flassenberg and S. Paulu, “Sieving in function fields,” Experimental Mathematics, 8, No. 4, 339-349, 1999.
[10] John B. Fraleigh, A First Course in Abstract Algebra, seventh edition, Addison-Wesley, 2003.
[11] W. Fulton, Algebraic Curves, Benjamin, New York, 1969.
[12] S.D. Galbraith and N.P. Smart, “A Cryptographic Application of Weil Descent,” Cryptography and Coding, 7th IMA Conference. LNCS 1746, pp. 191–200. Springer-Verlag, Berlin, 1999.
[13] P. Gaudry, “An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves,” Advances in Cryptology－EUROCRYPT 2000, LNCS 1807 (2000), 19-34.
[14] P. Gaudry and R. Harley, “Counting Points on Hyperelliptic Curves over Finite Fields,” Algorithmic Number Theory－ANSI-IV, LNCS 1838 (2000), 313-332.
[15] P. Gaudry, F. Hess, and N. Smart, “Constructive and Destructive Facets of Weil Descent on Elliptic Curves,” Journal of Cryptology, 15:19-46, 2002.
[16] P. Gaudry and E. Thomé, “A Double Large Prime Variation for Small Genus Hyperelliptic Index Calculus,” Crypto ePrint Archive, Report 2004/153.
[17] C. Guyot, K. Kaveh, V.M. Patankar, “Explicit Algorithm for The Arithmetic on The Hyperelliptic Jacobians of Genus 3,” Journal of Ramanujan Mathematical Society, 19 (2004), No.2, 119-159.
[18] M. Jacobson and A. van der Poorten, “Computational Aspects of NUCOMP,” Algorithmic Number Theory－ANTS-IV, LNCS 2369 (2002), 120-133.
[19] N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, 48 (1987), 203-209.
[20] N. Koblitz, “Hyperelliptic Cryptosystems,” Journal of Cryptology, 1 (1989), 139-150.
[21] B. A. LaMacchia and A. M. Odlyzko, “Solving Large Sparse Linear Systems over Finite Fields,” In A. J. Menezes and S. A. Vanstone, editors, Advances in Cryptology, volume 537 of Lecture Notes in Comput. Sci., pages 109–133. Springer–Verlag, 1990. Proc. Crypto ’90, Santa Barbara, August 11–15, 1988.
[22] T. Lange, “Efficient Arithmetic on Genus 2 Hyperelliptic Curves over Finite Fields via Explicit Formulae,” Cryptology ePrint Archive: Reprot 2002/121, 2002.
[23] Niels Lubbes, “The Hyperelliptic Curve Discrete Logarithm Problem,” Master’s thesis, Universiteit van Amsterdam, 2004.
[24] A. Menezes, Elliptic Curve Public Key Cryptosystems, Kluwer Academic Publishers, 1993.
[25] A. Menezes, Y. Wu and R. Zuccherato, “An Elementary Introduction to Hyperelliptic Curves” appendix in Algebraic Aspects of Cryptography by N. Koblitz, Springer-Verlag, 1998, 155-178.
[26] V. Muller, A. Stein, and C. Thiel, “Computing Discrete Logarithms in Real Quadratic Congruence Function Fields of large genus,” Math. Comp., 68(226):807–822, 1999.
[27] D. Mumford, Tata Lectures on Theta II, Birkhauser, Boston, 1984.
[28] K. Nagao, “Improvement of Thériault Algorithm of Index Calculus for Jacobian of Hyperelliptic Curves of Small Genus,” Cryptology ePrint Achieve, Report 2004/161.
[29] J. Pelzl, T. Wollinger, and C. Paar, “Low cost security: Explicit formulae for genus-4 hyperelliptic curves,” In M. Matsui and R. Zuccherato, editors, Selected Areas in Cryptography -- SAC 2003, volume 3006 of LNCS, pages 1--16. Springer-Verlag, 2004.
[30] Sakai, Y., and K. Sakurai, “On the Practical Performance of Hyperelliptic Curve Cryptosystems in Software Implementation,” IECE Trans. Fundamentals, vol. E83-A, No. 4, April 2000.
[31] Victor Shoup, NTL: A Library for doing Number Theory, available on web http://shoup.net/ntl/.
[32] N. Thériault, “Index Calculus Attack for Hyperelliptic Curves of Small Genus,” Advances in Cryptology－ASIACRYPT 2003, LNCS 2894 (2003), 75-92.
[33] D. H. Wiedemann, “Solving Sparse Linear Equations over Finite Fields,” IEEE Trans. Inform. Theory, IT-32(1):54-62, 1986.