Efficient computation of elliptic curve primitives
Elliptik eğri primitiflerinin verimli hesaplanması
- Tez No: 755646
- Danışmanlar: DR. ÖĞR. ÜYESİ HÜSEYİN HIŞIL
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Yaşar Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 133
Özet
Eliptik eğri kriptografisinde, eliptik eğriler ile ilgili hesaplamaların verimli yapılabilmesi büyük önem taşımaktadır. Bunu başarmak için, eliptik eğri skaler çarpması ve eliptik eğri nokta sayımı gibi eliptik eğri kriptografisinin primitifleri hızlı yöntemler kullanılarak yapılmalıdır. Eliptik eğri skaler çarpımı eliptik bir eğri üzerindeki basit olmayan bir noktayı bir skaler ile çarpma işlemidir. Bu, eliptik eğri kriptografisinde darboğaz oluşturan zorluklardan biridir ve Montgomery merdiveni gibi verimli yöntemler bu zorluğun üstesinden gelmek için kullanılır. Bu tezin ilk bölümünde, tüm Montgomery eğrileri ile çalışan hızlı 4 kanallı vektörleştirilmiş bir Montgomery merdiveni sunulmaktadır. Bu tezde üzerinde durulan diğer temel primitiflerden biri de eliptik eğriler üzerindeki noktaları sayma işlemidir. Sonlu bir Fp alanı üzerinde tanımlanan bir eliptik eğri üzerindeki noktaların sayısını doğru bir şekilde belirlemek, her zaman gerçekleştirmesi önemli ve yorucu bir görev olmuştur. Eliptik eğri kriptografisinde kullanılan ayrık logaritma probleminin zorluk derecesi, ve dolayısıyla güvenliği, eliptik eğri üzerindeki nokta sayısı ile doğrudan ilişkilidir. Bu nedenle, güvenli bir eğri seçiminde nokta sayımı büyük önem taşımaktadır. 1985 yılında, ilk polinomsal zamanda çalışan eliptik eğri nokta sayma algoritması Rene Schoof tarafından bulunmuştur. Bunu Atkin ve Elkies'in geliştirmeleri izlemiştir ve 1995'te SEA algoritması ortaya konmuştur. Bugün bile, geniş bir sonlu alan üzerinde tanımlanan bir eliptik eğri üzerindeki noktaların sayısını bulmak için SEA algoritmasının geliştirilmiş versiyonları kullanılmaktadır. İki eliptik eğrinin izojen olup olmadığının tespiti, nokta sayımı ile doğrudan ilişkilidir ve bu tespit genellikle SEA algoritması kullanılarak yapılır. Sato-Tate'in 1966 tarihli İzojeni Teoremi'ne göre, iki eliptik eğri, ancak ve ancak üzerlerindeki noktaların sayısı eşitse izojendir. Bu teoreme dayanarak, bu tezin ikinci bölümünde Schoof'un ve SEA algoritmaları ayrıntılı olarak açıklanmış, ilgili uygulamalar verilmiş ve izojen eliptik eğrileri tespit etmek için yeni bir erken iptal yöntemi sunulmuştur.
Özet (Çeviri)
In elliptic curve cryptography, it is of great importance to be able to perform computations associated with elliptic curves efficiently. To achieve this, the primitives of the elliptic curve cryptography, such as elliptic curve scalar multiplication and elliptic curve point counting, should be done using fast methods. Elliptic curve scalar multiplication is the process of multiplying a non-trivial point on an elliptic curve with a scalar. It is one of the bottleneck-forming challenges in elliptic curve cryptography, and different efficient methods, such as the Montgomery ladder, are used to overcome this challenge. A fast 4-way vectorized Montgomery ladder that works with all types of Montgomery curves is presented in the first part of this thesis. One of the other fundamental primitives emphasized in this thesis is the point counting operation on elliptic curves. Accurately determining the number of points on an elliptic curve defined over a finite field Fp has always been an essential and exhausting task. The difficulty level of the discrete logarithm problem, which is used in elliptic curve cryptography, and thus its security, is related to the number of points on the elliptic curve. Therefore, point counting is an essential operation in choosing a safe curve. In 1985, the first polynomial time elliptic curve point counting algorithm was found by Rene Schoof. The developments of Atkin and Elkies followed this, and in 1995, the SEA algorithm was introduced. Even today, improved versions of the SEA algorithm are used to find the number of points on an elliptic curve defined over a large finite field. Detecting whether two elliptic curves are isogenous is related to point counting, and this detection is generally done using the SEA algorithm. According to Sato-Tate's Isogeny Theorem from 1966, two elliptic curves are isogenous if and only if the numbers of points on them are equal. Based on this theorem, Schoof's and SEA algorithms are explained in detail, the implementations of these algorithms are given, and a new early abort method for detecting (non-)isogenous elliptic curves is presented in the second part of this thesis.
Benzer Tezler
- Faster point addition formulas for Huff form of elliptic curves
Huff eliptik eğri modeli üzerinde hızlı nokta toplama formülleri
NERİMAN GAMZE ORHON
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYaşar ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. HÜSEYİN HIŞIL
- Elliptic curves, group law, and efficient computation
Eliptik eğriler, grup kural ve verimli hesaplama
HÜSEYİN HIŞIL
Doktora
İngilizce
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolQueensland Teknoloji Üniversitesi (QUT Gardens Point Campus)Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ED DAWSON
- Elliptic curves and use of their endomorphism rings in cryptography
Eliptik eğriler ve onların endomorfizma halkalarının kriptografide kullanımı
ALİ MERT SÜLÇE
Yüksek Lisans
İngilizce
2019
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. ERSAN AKYILDIZ
- FPGA based cryptography computation platform and the basis conversion in composite finite fields
FPGA tabanlı kriptografi işlem platformu ve bileşik sonlu cisimlerde baz dönüşümü
RIAZ MUHAMMAD SIAL
Doktora
İngilizce
2013
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. ERSAN AKYILDIZ
- Compact, flexible and fast coprocessor design for elliptic curve pairing operation on reconfigurable hardware
FPGA üzerinde eliptik eğri pairing operasyonu için esnek, kompakt ve hızlı işlemci tasarımı
ERTUĞRUL MURAT
Yüksek Lisans
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSabancı ÜniversitesiBilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
DOÇ. DR. ERKAY SAVAŞ