超橢圓曲線密碼攻擊之研究

Abstract

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).