利用複乘法產生質數點數之橢圓曲線

Abstract

自從Koblitz和Miller於1985年首度利用橢圓曲線建構密碼系統以來，橢圓曲線密碼學因其較短之金鑰長度及較佳計算效率的優點吸引了許多密碼學家投入此研究領域中。如何有效率的產生符合安全需求之橢圓曲線來建構密碼系統一直是很重要的議題。基於雙線性配對之密碼系統為一種橢圓曲線密碼系統，而建構此密碼系統之橢圓曲線須符合具有較小的嵌入數(embedding degree)。在目前已知的方法中，只有複乘法能夠產生符合此種要求之橢圓曲線。 複乘法可允許使用者先決定了定義於有限體之橢圓曲線上的點數個數，而後再利用數學方法產生具有此點數之橢圓曲線。由於可事先決定點數個數，故可控制點數個數使得產生之橢圓曲線將會具有較小之嵌入數。另一方面，相較於隨機產生曲線再計算點數是否符合安全需求的方法，如Schoof演算法、SEA演算法，一旦所選定的點數符合數學定理的要求，複乘法便能準確的計算出曲線。在本篇論文中，我們詳細地介紹與複乘法相關之數學背景，並實作出計算Weber類別多項式(Weber class polynomial)之演算法，此部分在複乘法中為最占時間之計算步驟。

From the use of elliptic curves in cryptosystem first proposed by Koblitz and Miller in 1985, elliptic curve cryptography had attracted lots of cryptographic researchers. The benefits, such as shorter key size and efficient computation, make it become a popular and better solution to constructing cryptosystems. It is an important issue that efficiently generating the suitable elliptic curves for constructing the cryptosystem. One of the cryptosystems is the pairing based cryptosystem. For the pairing based cryptosystem, the smaller embedding degree is the main requirement of the elliptic curves. Currently, the only way to generate such curves is complex multiplication. The complex multiplication allows us to determine the number of points on the elliptic curves defined over finite field first, then compute the curves with the desired order. Comparing to the method that selects random curves and uses point counting algorithm to generate secure elliptic curves, complex multiplication is a deterministic algorithm. In this thesis, we summarize the mathematical backgrounds for complex multiplication and implement the algorithm of computing the Weber class polynomial which plays an important role in complex multiplication.