Eliptik Eğri Şifreleme Hakkında
MARMARA ÜNİVERSİTESİ
FEN BİLİMLERİ FAKÜLTESİ
SİBER GÜVENLİK
Yeni başlayanlar için ElipticCurve Şifreleme Algoritması
Şebnem SÖNMEZ
Samet ERTÜRK
Tuğba AYDIN
Ders: Kriptolojiye Giriş & Kriptoloji ve Güvenlik Protokolleri
Eğitmen: Mehmet Fatih ZEYVELİ
Haziran 2021
İçindekiler
1. KONU ÖZET………………………………………………………………………..……….. 3
1.1. ÖZET ………………………………………………………………………………………. 3
2. ELİPTİK EĞRİ ŞİFRELEME………………………………………………………………… 4
2.1. ELİPTİK EĞRİ ŞİFRELEME TARİHÇESİ ……………………………………………….. 4
2.2. ELİPTİK EĞRİ ŞİFRELEMEYE GİRİŞ ………………………………………………….. 4
2.3. NEDEN ELİPTİK EĞRİ ŞİFRELEME ……………………………………………………. 5
2.4. ELİPTİK EĞRİ ŞİFRELEME ÇALIŞMA MANTIĞI ……………………………………… 6
2.5. ELİPTİK EĞRİ ŞİFRELEME KULLANIM ALANLARI…………………………………. 8
2.5.1. BLOCKCHAIN …………………………………………………………………………… 8
2.5.2. DİJİTAL İMZA UYGULAMALARI ………………………………………………………10
3. ELİPTİK EĞRİ ŞİFRELEME KRİPTOANALİZ ……………………………………………. 10
3.1. KRİPTOANALİZ SALDIRILARI …………………………………………………………. 10
3.1.1. ARKA KAPI ………………………………………………………………………………. 10
3.1.2. KUANTUM BİLGİSAYAR ATAĞI……………………………………………………….. 10
3.1.3. YAN KANAL SALDIRILARI…………………………………………………………….. 10
3.2. DEĞERLENDİRME VE SONUÇ ………………………………………………………….. 10
4. KAYNAKÇA ………………………………………………………………………………….. 11
1. KONU ÖZET
1.1. ÖZET
İnsanlık tarihi ile başlayan bilgiyi koruma ve sadece istenilen kişiler ile paylaşma ihtiyacı günümüzde de devam etmektedir. Kriptografinin ana amacını oluşturan sahip olunan bilgiyi koruma dürtüsü gelişen teknoloji ile birlikte çok farklı algoritmalar ile şifrelenmektedir.
Simetrik ve asimetrik şifreleme algoritmaları olarak iki ana başlıkta incelenen bu yöntemlerde gönderici ve alıcı arasındaki şifreleme ve şifre çözme metotları farklılık göstermektedir.
1976 Diffie ve Hellman tarafından ilk asimetrik şifreleme yöntemleri bulunmuş olup sonrasında 1977 yılında Rivest, Shamir ve Adleman tarafından isimlerinin baş harflerinin kısaltması olan RSA olarak da bildiğimiz algoritma geliştirilmiştir. Asimetrik yani açık anahtarlı şifrelemede amaç; belirli bir anahtar üzerinde anlaşmak ve alıcı taraf ile herhangi başka bir anahtar paylaşma ihtiyacı duymamaktadır. Mesaj alıcısı herkesin bildiği bir “açık anahtar” ve sadece kendisinde bulunan “gizli anahtar” dan oluşan bir anahtar çiftine sahip olmaktadır.
Bu makalemizde anlatacağımız Eliptik Eğri Şifrelemesi (EEŞ), sonlu cisimler üzerinde yer alan eliptik eğrilerin matematiksel olarak hesaplanması esasına dayanan bir açık anahtar şifrelemesidir. 1985 yılında Victor Miller ve Neal Koblitz tarafından keşfedilen bu şifreleme; şifreyi oluşturan asal sayıların çarpanlarına ayrılması sistemi üzerine kurulan RSA yerine konumlandırılmak üzere geliştirilmiştir.
2. ELİPTİK EĞRİ ŞİFRELEME
2.1. ELİPTİK EĞRİ ŞİFRELEME TARİHÇESİ
Eliptik eğriler ve özellikleri 2. ya da 3. yüzyıldan beri üzerinde çalışılan saf bir matematik konusu olarak düşünülmüş olup kriptografi olarak kullanılması yakın tarihe dayanmaktadır. Eliptik eğri ilk kez Diophantus’un “Arithmetica” kitabında ortaya çıkmıştır. Diophantus’un kitabında eliptik eğri ile ilgili yazdığı problem “belirli bir sayıyı, çarpımı küp eksi kenarı olacak şekilde iki sayıya bölmek” idi, bu da kılık değiştirmiş bir eliptik eğri olan Y (a- Y) = X3 — X formülünü göstermektedir.
Fransız matematikçi Bachet, Diophantus’un Arithmetica’sının Latince çevirisini 1621 yılında yayımlamıştır. Fermat ise 1630 yılında Arithmetica’nın bir kopyasını edinmiş ve eliptik eğrileri içeren toplu bir çalışma yayınlamıştır. Euler ise Fermat’ın çalışmalarının üzerine çalışmalar yaparak sayılar teorisi kapsamını genişletmiştir. Euler eş sayı problemi üzerinde çalışmalar yaparak eliptik integraller hakkında birçok sonuç elde etmiştir. 1670’lerde Newton kübik eğrileri sınıflandırmak için yakın zamanda geliştirilen analitik geometri araçlarını kullanmıştır. Bunu yaparken de hem Diophantus’un Arithmetica’sını hem de Bachet’in eliptik eğrinin rasyonel çözümüne ilişkin teoreminin ardındaki gizemlerini de açıklamıştır. 19. yüzyılda Jacobi ve Weirstrass bu çabaları eliptik integraller ve eliptik fonksiyonlarla ilişkilendirmiştir. 1901’de ise Poincare bu çalışmayı cebirsel eğri ile birleştirerek genelleştirmiştir.
Bu eğrilere, bir elipsin yay uzunluğunu bulma problemini incelerken ortaya çıkması nedeniyle “eliptik” adı verilmiştir. 1984 yılına kadar eliptik eğrinin kriptografide kullanımı ile ilgili herhangi bir çalışma yapılmamıştır. Kriptografide ilk uygulaması Lenstra tarafından tamsayı çarpanlarına ayırma yönteminde bulunmuştur. 1985 yılında ise Victor Miller ve Neal Koblitz tarafından eliptik eğrilerin kriptografide tamamen farklı bir şekilde kullanılması önerilmiştir.
2.2. ELİPTİK EĞRİ ŞİFRELEMEYE GİRİŞ
Asimetrik şifreleme algoritmalarının en belirgin özelliği; açık anahtarın (public key) ve ona bağlı şifrelenmiş metnin herkese açık ve güvensiz bir kanal üzerinden iletilebilmesidir.
Resim 1: Asimetrik Şifreleme Algoritmalarının Yapıları
Eliptik Eğri Şifreleme’nin (EEŞ) temellerinden biri iletilmek istenen mesajda bulunan karakterlerin iki boyutlu uzaydaki noktalara dönüştürülmesidir. Bu dönüşüm sadece noktalar ile sınırlı olmamakla birlikte tekrar düz metni oluşturacak karakterlere geri dönüşü yani orijinal metnin oluşturulmasını da kapsar.
Resim 2: Asimetrik Şifreleme Algoritması
Eliptik Eğri Şifreleme yöntemi eliptik eğrilerin matematiksel özelliklerini kullanarak açık anahtarlı kriptografik sistemler üretir. Açık anahtarlı şifreleme yöntemlerinin hepsi gibi EEŞ de tek yönde hesaplaması basit olmasına rağmen tersine çevirmesi çok zor olan matematiksel hesaplamaya dayanır. İşbu EEŞ yönteminde, rastgele bir eliptik eğri elemanının herkesçe açık olarak bilinen bir taban noktasına göre hesaplanamaması esasına dayanır.
Resim 3: Eliptik Eğri
2.3. NEDEN ELİPTİK EĞRİ ŞİFRELEME
Bir uygulama için ortak bir anahtar şifreleme sistemi seçerken öncelikli kriterler; işlevsellik, güvenlik ve performanstır. Bu açık anahtarlı şifreleme sistemlerinin başında; RSA, Ayrık Logaritma ve Eliptik Eğri gelmektedir. Araştırmacılar bu açık anahtarlı şifreleme sistemlerinin güvenliğini kanıtlamak için birçok teknik geliştirdiler.
Açık anahtar algoritmalarının performansları, temelde yatan matematiksel ifadelerin zorluğu ile doğru orantılıdır. Bir kriptografik sistemi kırmak için, öncelikle altta yer alan matematiksel problemin çözülmesi gereklidir. RSA ve Ayrık Logaritma‘nın tamsayılı çarpanlarına ayırma problemini çözmek için bilinen en hızlı algoritmaların alt üssel beklenen çalışma süresi vardır. Eliptik Eğri Ayrık Logaritmalarını da çözmek için aynı beklenen çalışma süresinden bahsedebiliriz. Aynı anahtar boyutları kullanıldığında Eliptik Eğri Ayrık Logaritması’nı çözmek RSA ve Ayrık Logaritma’dan daha fazla süre almaktadır. Bu avantaj, Eliptik Eğri Şifrelemesinin daha küçük anahtar boyutları ve daha yüksek hesaplama verimliliğini göz önüne serip aynı güvenlik düzeyine ulaştığını göstermektedir.
Açık anahtarlı bir şifreleme sisteminin altında yatan matematiksel problem, bir şekilde şifreleme sisteminin verimliliğini belirlemektedir. Çünkü bu problemler, açık anahtarlı kripto algoritmalarının aritmetik işlemlerinin performansını etkileyen etki alanı parametrelerinin ve anahtarların boyutlarını belirlemektedir. Genellikle anahtar boyutları olarak adlandırılan parametre boyutları Resim 4 de gösterilmektedir. Bu tabloda Eliptik Eğri Şifreleme Algoritmasının aynı güvenlik seviyeleri için RSA ve DSA (Digital Signature Algorithm) ‘dan daha küçük anahtar boyutları kullandığını göstermektedir. Eliptik Eğri Şifreleme Algoritması’nda yer alan bu avantaj, daha hızlı hesaplama, daha küçük anahtar ve sertifikalar anlamına gelmektedir. Daha küçük anahtar boyutları da bant genişliği tasarrufu sağlamaktadır.
Resim 4: Algoritmaların Anahtar Uzunluklarının Karşılaştırılması
Anahtar boyutuna göre Eliptik Eğri Şifrelemesi’nin bant genişliği gereksinimleri diğer çarpanlara ayırma ya da ayrık logaritma sistemlerinden daha fazla verimlilik sağlamaktadır. Böylece daha yüksek hızların, daha düşük güç tüketiminin ve daha düşük kod boyutunun Eliptik Eğri Şifrelemesi ile birlikte gelen avantajlar olduğunu göstermektedir. Ayrıca altta yatan matematiksel problemin zorluk seviyesi de hem birçok araştırmacının ilgisini çekmiş hem de Eliptik Eğri Şifrelemesi’ni daha cazip hale getirmiştir.
2.4. ELİPTİK EĞRİ ŞİFRELEME ÇALIŞMA MANTIĞI
Eliptik Eğri şifreleme algoritmasındaki temel birimler, eğri üzerindeki (x, y) noktalarıdır.
x, y, a ve b sayıları gerçek sayılar olmak üzere; y2 = x3 + ax + b olarak gösterilmektedir. Gerçek sayılar üzerindeki eğri grubu diğer benzer eliptik eğriler üzerindeki noktalardan oluşmakta ve O ile ifade edilen sonsuzluk noktasını beraberinde getirmektedir.
x, y, a, b Є IFp = {1, 2, 3, . . . , p − 2, p − 1} (2)
a ve b ‘nin her farklı seçiminde farklı bir eliptik eğri oluşmaktadır.
y2=x3 + ax + b (mod p)
Yukarıdaki eşitlik sağlanıyorsa P(x,y), eliptik eğri üstünde bir noktadır denir.
Eliptik eğriler gerçek, tamsayı veya kompleks cisimlerden herhangi birisi ile tanımlanabilir. Ancak eliptik eğriler bir kriptosistem için kullanılıyorsa tamsayı ve asal mod değerine göre işlemler yapılacağı için sonlu cisimler tercih edilmelidir. Kullanılan asal sayının büyüklüğü ve polinom ile cisim üzerinde sağlanan noktaların sayıca çok olmalarına dikkat edilmesi gereklidir. Toplama ve çarpma gibi işlemlerde sonlu sayıda eleman içeren bir sonlu cisim yerine kriptografik uygulamalarda bilgisayar ortamında işlemlerin hızlandırılması sebebiyle ikili sonlu cisimler (F2m) tercih edilir. P ve Q gibi iki noktadan geçen bir doğru, üçüncü bir noktada eliptik eğriyi keser. Bu durum matematiksel olarak (P+Q) olarak ifade edilir ve üçüncü bir nokta elde edilmiş olur. Eliptik eğri üzerindeki bir noktadan başlayarak diğer noktaların da oluşması ile birlikte sonlu sayıda elemana sahip bir cisim elde edilir.
Şifreleme mantığıyla düşünüldüğünde bu cismin eleman sayısının çok fazla olması beklenir ve bu eleman sayısı uygulamanın güvenlik seviyesinde büyük önem taşır. Eliptik Eğri Şifreleme bu yönüyle tek yönlü bir kapan fonksiyonudur. Bu fonksiyonda;
P — başlangıç noktası,
E — eliptik eğri polinomu,
F(q) — sonlu cisim gibi bilgiler kamuya açıktır.
Asimetrik şifreleme mantığı ile düşünüldüğünde, Q noktasını üretmek için seçilen x değeri private anahtarı oluştururken, Q noktası ise public anahtarı verir.
ÖRNEK;
Formüldeki a ve b elemanlarına a = -4 ve b = 0,67 değerleri verildiğinde, formül
y2 = x3–4x + 0,67 eliptik eğri denklemini vermektedir.
Eğer x3 + ax + b denklemi tekrarlamayan çarpanlar içerirse ya da 4a3 + 27b2 ≠ 0 ise eliptik eğri y2 = x3 + ax + b grup formunda kullanılabilir.
ÖRNEK;
Eliptik eğri üzerindeki bir noktanın verilen bir sayı ile çarpımı yine aynı eğri üzerindeki başka bir noktayı oluşturur.
P ve Q eliptik eğri üzerinde iki farklı nokta olsun. Bu P ve Q noktalarını toplamak üzere P ve Q noktalarından geçen bir doğru çizilmelidir. Çizilen doğru eliptik eğri üzerinde -R ile belirtilen bir noktada kesmektedir. -R noktasının x eksenine göre tersi bize R noktasını verir. Bu nokta P ve Q noktasının toplamını gösterir.
P ile belirtilen bir noktayı çift katlı yapmak için, teğet çizgisi çizilir ve eğriyi kestiği diğer nokta bulunur. Bu noktayı R ile adlandırırsak P+P=R eşitliği sağlanır.
Yine Eliptik eğri üzerinde bulunan bir P(x,y) noktası kendini tekrar ediyorsa “n” kere,
P+P+P+…….+P=nP=Q (n kere) ile gösterilir ve tekrarlanır.
Eliptik eğride kullanılan P(x,y) ve Q(x,y) noktaları bulunması kolay olsa dahi “n” yi bulmak zordur. Çünkü P ve Q noktaları bilinse de “n” yi hesaplamak oldukça zordur. Ayrık logaritma problemi (ECDLP) çok sayıda eliptik eğri ile birleşerek güvenlik sistemi olan Eliptik Eğri Şifreleme Sisteminin temelini oluşturur.
2.5. ELİPTİK EĞRİ ŞİFRELEME KULLANIM ALANLARI
2.5.1. BlockChain
Eliptik eğri şifreleme algoritmaları, blockchain zincirleri ve mobil imzalar gibi açık anahtarlı şifreleme sistemlerine uygun olan alanlarda kullanılmaktadır.
Eliptik eğrilerin güçlü matematiksel özelliklerini kullanan eliptik eğri şifreleme algoritması, RSA standardına göre çok daha güçlü ve anahtar uzunluğu çok daha kısadır. Örneğin; 3072bit RSA anahtarına karşılık 256bit anahtar üretmekte ve bu anahtar üretimini RSA’den çok daha kısa sürede gerçekleştirmektedir.
Çok çeşitli bilgi işlem platformlarında verimli kriptografinin benimsenmesi için ticari standartlar geliştirmek üzere 1998 yılında kurulan Standards for Efficient Cryptography (SEC) grubu, açık anahtarlı kriptografide kullanılan eliptik eğri Secp256k1 standardını oluşturmuştur. Bu standardın formülü;
y2=x3+7 olarak belirlenmiştir.
Bitcoin popüler olmadan önce kullanımı az olan secp256k1 standardı, günümüzde blockchain yapısı geliştikçe kullanım oranı da artmaktadır. Rastgele yapıya sahip olan eliptik eğriler çok sık kullanılsa dahi, secp256k1 standardı ile üretilen eğriler rastgele olmayan ve verimli hesaplamaya izin veren eğrilerdir.
Eliptik eğri şifreleme algoritmaları; Bitcoin, Ethereum ve EOS gibi birçok blok zincirinde kullanılmaktadır.
Resim 5: secp256k1 Eliptik Eğri Grafiği
2.5.2. Dijital İmza Uygulamaları
El yazısı imzaların dijital karşılığı, kriptografideki imza şemalarıdır. Kimlik doğrulama, veri bütünlüğü ve reddedilemezlik gibi güvenlik kriterlerini sağlamak için dijital imzalar kullanılmaktadır. Dijital imzalar, gönderenin kimliğini ve değişmeyen verileri doğrulayarak belgenin geçerliliğini sağlamaktadır. Goldwasser, Micali ve Rivest’a göre bir imza şemasının güvenliği hakkında tanımlanan bir kavram bulunmaktadır. Bir imza şemasının, uyarlanabilir bir seçilmiş mesaj saldırısı gerçekleştirebilen, sayısal olarak sınırlandırılmış bir düşman tarafından varoluşsal olarak taklit edilemez olması durumunda güvenli olduğu söylenmektedir. Bu, saldırganın herhangi bir mesajın imzasını alabileceği ancak herhangi yeni bir mesajın geçerli bir imzasını üretemeyeceği anlamına gelmektedir. Bu konsepti oluşturmak için bir imza şeması dört algoritmadan oluşmaktadır. Bunlar; etki alanı parametresi oluşturma, anahtar oluşturma, imza oluşturma ve imza doğrulama algoritmalarıdır.
Dijital İmza Algoritması’nın analog versiyonuna Eliptik Eğri Dijital İmza Algoritması denmektedir. ANSI X9.62, FIPS 186–2 ve IEEE 1363–2000, ISO/IEC 15946–2 standartlarında standartlaştırılmış eliptik eğri tabanlı imza şemasıdır. İmza şemalarının ilki “alan parametre üretimi” dir. Alan parametreleri, alan sırası (q), alan gösterimi, eliptik eğri denklem parametreleri(a,b), temel eliptik eğri noktası (G), noktanın asal sırası ve kofaktördür (h=N/n).
3. ELİPTİK EĞRİ ŞİFRELEME KRİPTOANALİZ
3.1. KRİPTOANALİZ SALDIRILARI
3.1.1. Arka Kapı
1952 yılında kurulan Ulusal Güvenlik Ajansı (NSA) ‘nın eski bir çalışanı olan Edward Snowden tarafından sızdırılan notlarda NSA’nın Dual_EC_DRBG Dual_EC_DRBG (Çift Eliptik Eğri Belirleyici Rastgele Bit Üreteci) standardında bir arka kapı koyduğunu gözlemlenmiştir. Bu arka kapı için yapılan analizlerde, algoritmanın private anahtarına sahip olan bir kişinin 32 bayt şifreli metinle şifreleme anahtarlarını da elde edebileceğini göstermektedir.
Bu arka kapının ifşa olmasından sonra NSA, güvenli bir şekilde uygulaması kolay olan ve halka açık formatta tasarlanmış eğrileri kataloglamak için SafeCurves projesi başlatmıştır.
3.1.2. Kuantum Bilgisayar Atağı
Kuantum mekaniğinin etkilerini inceleyen Richard Feynman, 1982 yılında bu etkileri kendi faydasına kullanabileceği bir kuantum bilgisayar fikrini geliştirmiştir. 0 ve 1 bitlerinden farklı olarak, kuantum bilgisayarlarda kubit olarak adlandırılan kuantum bitleri kullanılır. Yani bir kubit üzerindeki bir işlem her iki değer olan 0 ve 1’e etki eder.
1994 yılında Amerikalı matematikçi Peter W. Shor tarafından geliştirilen Shor algoritması, bir kuantum bilgisayardaki ayrık logaritmaları hesaplayarak eliptik eğri kriptografisini kırmak için kullanılabilir. 256 bitlik bir modül ile bir eliptik eğriyi kırmak için 2330 kubit ve 126 milyar Toffoli gerekmektedir. 2048 bit RSA algoritmasını kırmak için 4098 kubit ve 5.2 trilyon Toffoli gerektirmektedir. Bu sonuçlar hesaplandığında Eliptik Eğri Şifrelemesi’nin RSA’den daha kolay bir hedef olduğu gözlemlenmektedir. Tüm bu rakamlar değerlendirildiğinde, henüz bu kadar güçlü bir kuantum bilgisayarın olmadığı ve önümüzdeki on yıldan daha uzun bir sürede olmayacağı anlamına da gelmektedir.
3.1.3. Yan Kanal Saldırıları
Aynı yöntem kullanılarak karesini alma ve çarpma işlemlerinin mümkün olduğu ayrık logaritma sistemlerinin aksine, eliptik eğri toplama işlemi çift(P=Q) ve genel toplam (P ≠ Q) bakımından farklılıklar göstermektedir. Bu sebepledir ki “fixed pattern window” gibi yöntemleri kullanarak yan kanal saldırılarının etkilerini ortadan kaldırmak büyük önem kazanmaktadır.
Alternatif bir çözüm olarak, yan kanal saldırı risklerini ortadan kaldırmak için çift ve toplama işlemlerinin aynı anda yapılabildiği Edward eğrisi de kullanılabilir.
3.2. DEĞERLENDİRME VE SONUÇ
Teknolojik gelişmelerin artması ile birlikte güvenilirlik kriterine olan ihtiyaç sürekli artmakta ancak paralelde hızına yetişilmekte de güçlükler yaşanmaktadır. Eliptik eğrilerin başlangıcından bu yana olan yolculuğu ve kriptografideki kullanımı oldukça başarılıdır. Eliptik eğri kriptografi uygulamalarının güvenliğini, uygulamasını ve performansını inceledikten sonra en uygun açık anahtar şifreleme şeması olduğu sonucuna varılmaktadır. Verimliliği ve güvenliği onu geleneksel şifreleme sistemi olan RSA’e karşı bir alternatif haline getirmiştir. Güvenli ve hızlı olarak nitelendirilen diğer şifreleme algoritmalarına karşı aynı güvenlik seviyesine sahip ve diğer şifreleme tekniklerine göre daha düşük anahtar uzunluğunu kullanması eliptik eğri şifreleme tekniklerinin gelecekte daha çok kullanıma sahip olacağını göstermektedir.
4. KAYNAKÇA
http://dspace.yildiz.edu.tr/xmlui/bitstream/handle/1/7280/0023898.pdf?sequence=1&isAllowed=y
https://tr.xcv.wiki/wiki/Elliptic-curve_cryptography
https://tr.esc.wiki/wiki/Elliptic_curve_cryptography
https://doczz.biz.tr/doc/93394/pdf-ps-tez-%C5%9Fifreleme-e%C4%9Frisi-eliptik-%C3%BCcretsiz
https://silo.tips/download/elptk-er-krptosstem-yazilim-uygulamalarinda-hiz-problem