橢圓曲線上SEA演算法之加速

Abstract

1985年，Miller與Koblitz先後提出將橢圓曲線使用在公開金鑰密碼系統上。橢圓曲線上的有理點會形成一個加法群，此加法群上 的離散對數問題稱為橢圓曲線離散對數問題(elliptic curve discrete logarithm problem)。目前沒有任何演算法可以快速的解決此問題，因此，橢圓曲線密碼系統基於此困難的問題上，只需比RSA還短的金鑰長度，就可達到與RSA相同的安全度。 在使用橢圓曲線密碼系統時，挑選一個安全性高的橢圓曲線是很重要的。選取橢圓曲線的方法共有三種。現在主要的方法是先隨機選取橢圓曲線，並計算曲線上的有理點個數，以判定此橢圓曲線是否符合安全要求。所以，在橢圓曲線密碼系統的設計上，計算一條橢圓曲線在有限體上的點數就扮演了很重要的角色。Schoof-Elkies-Atkin(SEA)演算法是用於計算點數上重要的方法。在本篇論文中，我們將分別提出對 於演算法中Atkin質數、Elkies質數及小步-大步(Baby-step-giant-step)的策略，用來計算定義於大質數體上橢圓曲線之點數，有很好 的改良。

In 1985, Miller proposed the use of elliptic curves in public-key cryptosystem, and so did Koblitz in 1987. The rational points of an elliptic curve forms an additive group. The discrete logarithm problem of this group is called elliptic curve discrete logarithm problem(ECDLP). There is no method to solve ECDLP efficiently. The security of elliptic curve cryptosystem(ECC) is based on ECDLP. Therefore, The key of ECC can be shorter than that of RSA in order to reach the same secure strength. In using the elliptic curve cryptosystem, it is important to select a secure elliptic curve. There are three methods to select secure elliptic curves. The suggested method is counting the number of rational points of elliptic curves generated randomly. Therefore, we can determine whether a randomly generated elliptic curve is suitable for the security consideration. Hence, solving the point counting problem plays a crucial role in the design of elliptic curve cryptosystems. Schoof-Elkies-Atkin(SEA) algorithm is an important method to solve the point counting problem. In this thesis, we propose strategies of Atkin primes, Elkies primes, and Baby-step-giant-step. It improves the original SEA algorithm a lot for elliptic curves defined over big prime fields.