橢圓曲線離散對數問題之 Index Calculus 演算法

Abstract

橢圓曲線密碼系統的安全性是建立於橢圓曲線離散對數問題 (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.