Faster point addition formulas for Huff form of elliptic curves / Huff eliptik eğri modeli üzerinde hızlı nokta toplama formülleri

Abstract

Onceden yalnızca matematiksel amaclar icin kullanılan eliptik e˘griler, 1985 yılında Miller ve Koblitz'in yayınladıgı ayrı calısmalar sayesinde kripto dunyasına giris yaptı. Bu gelisme ile birlikte eliptik egriler kriptografinin en onemli araclarından biri haline geldi. 1990'lardan sonra eliptik e˘gri tabanlı kriptografi ticari amaclar icin kullanılmaya ba¸sladı. Eliptik egri tabanlı kripto-sistemler, RSA gibi sıkca kullanılan asimetrik kripto sistemlerin sagladıgı guvenlik seviyesini, daha kısa anahtarlar ile saglayabildigi icin, bu denli hızlı bir gelisim gosterdi. Fakat, sagladıgı yuksek seviyeli guvenlige karsın, verimlilik konusunda yol kat etmesi gerekmektedir. Bu nedenle, eliptik egri tabanlı kripto-sistemlerin verimliligini arttırmak uzere bir cok calı¸sma yapılıyor. Hız ama¸clı kullanılan e˘gri modelleri, eliptik egri tabanlı kriptografinin temel i¸slemi olan, skalar ¸carpım i¸slemi i¸cin kullanılacak, daha d¨u¸s¨uk dereceli form¨uller elde edilmesi konusunda b¨uy¨uk yol kat etti. Fakat, bu egri modellerinden sayılan Huff egrisi bu vakte kadar yapılan bir cok calısmaya ragmen, twisted Edwards, Jacobi Quartic gibi egrilerle rekabet icinde olmadı. Bu tezin amacı, matemtaiksel ve bilgisayımsal temelleri kullanarak Huff e˘gri modelinin verimliligini arttırmaktır.Bu amac cercevesinde, y(1 + ax2 ) = cx(1 + dy2). olarak ifade edilen Huff egrisi uzerinde, bolmesiz nokta toplama ve nokta ciftleme islemleri onerildi. Bu amaca ulasmak icin kullanılan ilk yontem, bolmesiz nokta toplama ve nokta ¸ciftleme i¸slemleri elde edebilmek i¸cin, bu egri modelinde daha onceki calısmalarda tercih edilenden baska bir projektif uzay kullanılmasıdır. Ikinci yontem ise, alternatif bir nokta ciftleme formulu elde etmek icin isogenilerden faydalanmaktır. Bu iki y¨ontem sayesinde, dikkate de˘ger bir geli¸sim kaydedilmistir. Huff egrisi ¨uzerinde, bilinen en hızlı nokta ciftleme formulu ile, islem 6M + 5S'de 2 hesaplanabiliyordu. Bu tezde sunulan alternatif nokta ciftleme formulu sayesinde 8M'de hesaplanabiliyor. Nokta toplama formulunun i¸slem sayısı da 10M'den 8M'ye dusuruldu. Bu iki formulde de 2M'lik hızlanma sa˘glanmı¸stır. Ayrıca sunulan her iki formul de 4-yonlu paralel olarak islenebilmektedir. Anahtar Kelimeler: Eliptik e˘griler, 2-isogeny, verimli, skalar çarpım, Huff eğrisi, ters almasız nokta toplama işlemi, paralel hesaplama. Elliptic curves were being used only for mathematical studies until Miller and Koblitz introduced elliptic curves to crypto-community in 1985 with independent works. Since then, elliptic curves became one of the most significant tools in cryptography. Elliptic curve cryptography (ECC) started to be used for commercial purposes after 1990's. It provides a better level of security with the same key size than the widely used public key crypto-systems such as RSA. Nevertheless, time complexity is not at the desired stage. Hence, there have been several studies so far that aims to increase the time efficiency. The curve forms that are being used for speed oriented operations came a long way in terms of gathering lower degree formulas for scalar multiplication which is the core operation of ECC. However, one of the curve forms which is called Huff curve could not get competitive with the other forms such as Twisted Edwards, Jacobi Quartic, despite the studies have been made so far. This thesis focuses on increasing the efficiency of Huff form of elliptic curve by making use of mathematical and computational primitives. Inversion-free point addition and doubling formulas which are being used in scalar multiplication algorithms, are proposed for the Huff curve which is defined y(1 + ax2 ) = cx(1 + dy2 ) First idea is rather to embed the curve into a different projective space than the preferred for Huff curve previously. Thus, P 1×P 1 embedding is used instead of P 2 embedding. The second idea is to make the use of isogenies in order to obtain an alternative doubling formula. Thanks to these two ideas, an improvement is achieved. The best algorithm for point doubling on Huff curve was computed with 6M+ 5S. 1 The proposed doubling formula in this thesis can be computed with 8M. Also, operation count of mixed addition is decreased from 10M to 8M. Both sets of formulas are leading to an effective cost of 2M. Furthermore, they are shown to be 4-way parallel. Key Words: Elliptic curves, 2-isogeny, efficient, scalar multiplication, Huff curves, inversion-free point addition, parallel computation.