Tez No	İndirme	Tez Künye	Durumu
723627		Elliptic curves, group law, and efficient computation / Eliptik eğriler, grup kural ve verimli hesaplama Yazar:HÜSEYİN HIŞIL Danışman: PROF. DR. ED DAWSON Yer Bilgisi: Queensland Teknoloji Üniversitesi (QUT Gardens Point Campus) / Yurtdışı Enstitü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Açık anahtarlı kripto sistemler = Public key cryptosystems	Onaylandı Doktora İngilizce 2010 203 s.
Eliptik eğri teorisi ondokuzuncu yüzyıl matematikçileri tarafından ortaya atılmış, geliştirilmiştir ve canlı bir araştırma alanı olarak varlığını sürdürmüştür. Sonlu cisimler (finite fields) üzerine tanımlanmış eliptik eğriler 1980 yılında Miller ve Kobltiz'in bağımsız çalışmaları ile asimetrik kriptografide uygulama alanı bulmuştur. Miller ve Koblitz'in önerilerini takiben Elliptik Eğri Kriptografi (ECC) bilimi bir eliptik eğrinin rasyonel noktalarının oluşturduğu grup yapısının doğurduğu ayrık logaritma problemi (discrete logarithm problem) üzerine inşa edilmiştir. EEC'in gelişmi 1990'lardan başlayarak ticari kriptografik uygulamaların hızlanmasını sağlamıştır. Bu tezin hedefi elliptik eğri nokta toplama operasyonunun ve dolayısıyla ECC uygulamalarının hızlandırılmasıdır. Bu tez seçilen herhangi bir elliptik eğri üzerinde toplama kuralını türetmeyi ve eliptik eğri üzerindeki noktaların türetilen kural ile bilgisayar ortamında verimli bir şekilde toplanması üzerine bir çalışmadır. Bu çalışmanın sonuçları kriptografik uygulamalarda pratik avantajlar sunmaktadır. Belirlenen hedef beş aşamada başarılmıştır. Birinci adımda bir elliptik eğri üzerine tanımlanabilecek tek grup kuralını türetmeye yarayaracak cebirsel araçlar ve teknikler bir araya getirilmiştir. Bu adım aynı zamanda güncel bilgisayar destekli cebir programlarının incelenmesini de içermektedir. Grup kuralı tek olsa da bu kural sonsuz sayıda formül tarafından temsil edilebilmektedir. İkinci adımda en iyi formüllerin seçimi gösterilmiştir. Üçünçü adımda seçilen formüllerle grup kuralı eksiksiz olarak tanımlanmıştır. Dördüncü adımda grup kuralının verimli olarak hesaplanabilmesi için yeni algoritmalar sunulmuştur. Beşinci ve son adımda anılan algoritmalar en uygun hale getirilerek bilgisayar ortamında uygulanmıştır ve teorik olarak elde edilen bulguların deneysel olarak doğrulanmıştır. Anılan beş adım için büyük karakteristikli cisimler üzerine tanımlanmış beş ayrı elliptik eğri modeli üzerinde durulmuştur. Anılan beş modelin bir listesi aşağıda verilmiştir: (a) Kısa Weierstrass modeli, $y^2 = x^3 + a x + b$, (b) Genişletilmiş dördüncü dereceden Jacobi modeli, $y^2 = d x^4 + 2 a x^2 + 1$, (c) Bükülmüş Hessian modeli, $a x^3 + y^3 + 1 = d x y$, (d) Bükülmüş Edwards modeli, $a x^2 + y^2 = 1 + d x^2 y^2$, (e) Bükülmüş Jacobi kesişim modeli, $b s^2 + c^2 = 1, a s^2 + d^2 = 1$. Anılan modeller verimli hesaplamalar için en uygun olanlarıdır. Buna karşın bu tezde oluşturulan metodoloji tüm elliptik eğri modelleri için kullanılabilmektedir. Bu tezde bulunan bölümler aşağıdaki şekilde özetlenmiştir. Bölüm-1'de teze genel giriş yapılmış, literatür taraması sunulmuş ve bu tezdeki elde edlien bulgular kısaca anlatılmıştır. Literatürde yer almış sonuçlar özetlenerek bir araya getirilmiş ve bu sonuçlar daha ileri sonuçlarla desteklenmiştir. Pekçok incelemede verimli uygulamalarda kullanıma elverişli ve daha önceki çalışmalarda gözden kaçmış birçok yeni formül bulunmuş ve bu formüllere ilişkin elliptik eğri nokta temsil metodları ve yeni algoritmalar geliştirilmiştir. Bölüm-2 tezin ilerleyen bölümlerinde sıklıkla kullanılan kavramları içermekte ve kullanılacak notasyonu tanıtmaktadır. Örneğin tez için en önemli kavram olan eliptik eğri grup kuralı tanımlanmıştır. Ayrıca seçilen eliptik eğri modelleri ile Weierstrass modeli arasındaki iki yönlü denklik (birational equivalence) anlatılmıştır. Bölüm-3 secilen herhangi bir eliptik eğri modeli için grup kuralını türetecek matematiksel araçları biraraya getirmektedir. Anılan araçlar Bölüm-4, 5 ve 7'de sıkça kullanılmıştır. Bölüm-4 seçilen eliptik eğri modelleri için birçoğu yeni olan düşük dereceli nokta toplama formüllerini tanıtmaktadır ve grup kuralını sonsuzdaki noktaların dahil olduğu durumlarla eksiksiz olarak tanımlamaktadır. Farklı elliptik eğri modelleri arasındaki benzerlikler tespit edilmiştir. Örneğin, incelenen tüm elliptik eğri modellerinde iki adet formul takımının tüm afin noktaların toplamı için yeterli olduğu ortaya konmuştur. Bölüm-5 cisim elemanlarının terslerinin bulunmasını gerektirmeyen birçok yeni nokta toplama formülü ve anılan formüllere ilişkin işlem adımı bilgilerini içermektedir. Anılan bölüm aynı zamanda literatürdeki en hızlı formüller ile bu tezde ortaya konan yeni formüllerin de kıyaslamasını içermektedir. Literatürdeki alternatiflerinden daha verimli olan birçok yeni nokta toplama/çiftleme formülü ve algoritması tanıtılmıştır. En çok dikkat çeken iyileştirmeler genişletilmiş dördüncü dereceden Jacobi modeli, bükülmüş Hessian modeli, bükülmüş Edwards modeli ve bükülmüş Jacobi kesişim modelinde ortaya konmuştur. Ayrıca kısa Weierstrass modeli için hem nokta toplama hem de nokta çiftlemede kullanılabilen birleştirilmiş formüller bulunmuştur. İncelenen modeller için noktaların temsilini sağlayan ve kriptografi dünyası için yeni sayılan koordinat sistemleri kullanılmıştır. Bölüm-6 daha önceki bölümlerde ortaya konan yeni formüllerin ışığında eliptik eğri ölçekli-çarpma işleminin bilgisayar ortamındaki uygulamasına ilişkin detayları içermektedir. Anılan bölümde amaç; ortaya konan metotların ECC uygulamalarının performansı açısından yararlı olduğunu göstermektir. Genel amaçlı x86-64 mimarisi üzerinde C ve assembly dilleri kullanılarak kapsamlı bir uygulama geliştirilmiştir. Ortaya konan algortimaların pratik olarak yararları doğrulanmıştır. İkincil amaç ise farklı eliptik eğri modelleri arasında bilinen en performanslı formüllerin kıyaslamasının yapılmasıdır. Bölüm-7 j-sabiti sıfır olan $y^2 = c x^3 + 1$ eliptik eğrisi üzerinde kriptografik eşleme (pairing) işleminin yüksek performanslı olarak hesaplanması üzerine bu tezin önceki bölümlerinde kurulan alt yapıyı kullanmaya yönelik bir çalışmadır. Anılan bölüm özel olarak Tate eşlemesinin nasıl daha performanslı yapılabileceğini göstermektedir. Bölüm-8 bu tezin sonuçlarını özetlemekte ve cevaplanmayı bekleyen açık soruları sunmaktadır. Bu tezde üç adet ek vardır. Ek-A (Appendix A) tezin bölümlerinde kullanılan cebirsel kavramlar hakkında temel tanımları içermektedir. Ek-B kroptografik protokoller, ayrık logaritma problemi, vb. ECC'nin temel kavramlarını sunmaktadır. Ek-C ise bu tezde yer alan tüm formüllerin bilgisayar destekli cebir yazılımları ile doğrulanmasını sağlayan programları içermektedir.
This thesis is about the derivation of the addition law on an arbitrary elliptic curve and efficiently adding points on this elliptic curve using the derived addition law. The outcomes of this research guarantee practical speedups in higher level operations which depend on point additions. In particular, the contributions immediately find applications in cryptology. Mastered by the 19th century mathematicians, the study of the theory of elliptic curves has been active for decades. Elliptic curves over finite fields made their way into public key cryptography in late 1980's with independent proposals by Miller [Mil86] and Koblitz [Kob87]. Elliptic Curve Cryptography (ECC), following Miller's and Koblitz's proposals, employs the group of rational points on an elliptic curve in building discrete logarithm based public key cryptosystems. Starting from late 1990's, the emergence of the ECC market has boosted the research in computational aspects of elliptic curves. This thesis falls into this same area of research where the main aim is to speed up the additions of rational points on an arbitrary elliptic curve (over a field of large characteristic). The outcomes of this work can be used to speed up applications which are based on elliptic curves, including cryptographic applications in ECC. The aforementioned goals of this thesis are achieved in five main steps. As the first step, this thesis brings together several algebraic tools in order to derive the unique group law of an elliptic curve. This step also includes an investigation of recent computer algebra packages relating to their capabilities. Although the group law is unique, its evaluation can be performed using abundant (in fact infinitely many) formulae. As the second step, this thesis progresses the finding of the best formulae for efficient addition of points. In the third step, the group law is stated explicitly by handling all possible summands. The fourth step presents the algorithms to be used for efficient point additions. In the fifth and final step, optimized software implementations of the proposed algorithms are presented in order to show that theoretical speedups of step four can be practically obtained. In each of the five steps, this thesis focuses on five forms of elliptic curves over finite fields of large characteristic. A list of these forms and their defining equations are given as follows: (a) Short Weierstrass form, y2 = x3 + ax + b, (b) Extended Jacobi quartic form, y2 = dx4 + 2ax2 + 1, (c) Twisted Hessian form, ax3 + y3 + 1 = dxy, (d) Twisted Edwards form, ax2 + y2 = 1 + dx2y2, (e) Twisted Jacobi intersection form, bs2 + c2 = 1, as2 + d2 = 1, These forms are the most promising candidates for efficient computations and thus considered in this work. Nevertheless, the methods employed in this thesis are capable of handling arbitrary elliptic curves. From a high level point of view, the following outcomes are achieved in this thesis. - Related literature results are brought together and further revisited. For most of the cases several missed formulae, algorithms, and efficient point representations are discovered. - Analogies are made among all studied forms. For instance, it is shown that two sets of affine addition formulae are sufficient to cover all possible affine inputs as long as the output is also an affine point in any of these forms. In the literature, many special cases, especially interactions with points at infinity were omitted from discussion. This thesis handles all of the possibilities. - Several new point doubling/addition formulae and algorithms are introduced, which are more efficient than the existing alternatives in the literature. Most notably, the speed of extended Jacobi quartic, twisted Edwards, and Jacobi intersection forms are improved. New unified addition formulae are proposed for short Weierstrass form. New coordinate systems are studied for the first time. - An optimized implementation is developed using a combination of generic x86-64 assembly instructions and the plain C language. The practical advantages of the proposed algorithms are supported by computer experiments. - All formulae, presented in the body of this thesis, are checked for correctness using computer algebra scripts together with details on register allocations.