The Security of Curves for Elliptic Curve Cryptosystems

現今許多密碼系統的安全性, 是以橢圓曲線離散對數問題(ECDLP) 的困難度為基礎。這些密碼系統的安全性, 通常取決於曲線的選擇。在這篇論文中, 我們對現在針對橢圓曲線離散對數問題的攻擊法做一個整理, 找出弱曲線的條件, 也提出一些安全曲線應該有的條件。另外, 我們也會討論一些其他的攻擊法, 這些攻擊法對ECDLP 是失敗的。The elliptic curve discrete logarithm problem (ECDLP) forms the basis of numerous cryptosystems today. The security of these cryptosystems usually depends on the choice of curves. In this thesis, we give a summary of recent attacks on the ECDLP, find the criteria of weak curves, and suggest the conditions that a secure curve should have. We will also discuss some attacks which works on the DLP but may fail to the ECDLP.Contents試委員會審定書i謝iibstract in Chinese iiibstract in English iv Introduction 1 General Attacks on the ECDLP 4.1 Baby Step, Giant Step . . . . . . . . . . . . . . . . . 4.2 The Pollard Method. . . . . . . . . . . . . . . . . . . 5.2.1 Pollard’s ρ Method. . . . . . . . . . . . . . . . . 5.2.2 Pollard’s λ Method. . . . . . . . . . . . . . . . . 9.3 Pohlig-Hellman Attack. . . . . . . . . . . . . . . . . 11 Isomorphism Attacks on the ECDLP 15.1 Attacks on Anomalous Curves. . . . . . . . . . . . . . 15.1.1 Smart’s Method. . . . . . . . . . . . . . . . . . . 15.1.2 Semaev’s Method . . . . . . . . . . . . . . . . . . 18.2 MOV Attack . . . . . . . . . . . . . . . . . . . . . . 22.3 Tate Pairing Attack. . . . . . . . . . . . . . . . . . 26.4 Weil Descent . . . . . . . . . . . . . . . . . . . . . 29 Other Attacks 33.1 Index Calculus on the ECDLP. . . . . . . . . . . . . . 33.2 Xedni Calculus on the ECDLP. . . . . . . . . . . . . . 36.3 Semaev’s Summation Polynomials. . . . . . . . . . . . 44.4 Further Results. . . . . . . . . . . . . . . . . . . . 47 Conclusions 50eferences 52 Computation of the Parings 5