超橢圓曲線密碼系統之攻擊

Abstract

1989年Koblitz 利用定義在有限域的超橢圓曲線上的jacobian加法群，基於超橢圓曲線離散對數問題的困難度，提出了超橢圓曲線密碼系統(HECC, Hyperelliptic curve cryptosystem)。在含有q個元素的有限域Fq中，genus為g的超橢圓曲線，其中形成離散對數問題的加法群大小為()gOq，大於橢圓曲線加法群。而且small genus的超橢圓曲線亦無時間複雜度為次指數的攻擊法，因此適當的設定超橢圓曲線密碼系統將可使用比橢圓曲線密碼系統更短的密鑰，來達到相同的安全度。 ()Oq 目前index calculus攻擊法在genus g遠大於log(q)時，呈現次指數的時間複雜度。當genus不大時，一般的生日攻擊法為2()gOq，而一般的index calculus為。Theriault的index calculus演算法加入」large prime」的概念，時間複雜度為2()Oq4221(gOq..；而Gaudry等人利用」double large prime」的index calculus攻擊法變形，則時間複雜度更進一步改進為22(gOq.。本計劃將針對small genus的超橢圓曲線離散對數問題，實作並改進現有的攻擊法，包含index calculus及其變形，以期歸納更安全的超橢圓曲線密碼系統。