Ellipsel Eğri (Elliptic Curve)


Yazan : Şadi Evren ŞEKER

Elipsel eğri, gerçek sayılar kümesi (real numbers) üzerinde tanımlanan ve y2 = x3 + ax + b, genel denklemini x ve y gerçek sayıları için sağlayan eğrinin ismidir. Bu genel denklem için her a ve b değeri farklı bir eğri verir. Örneğin a = -4 ve b = 0.67 değerleri için y2 = x3 - 4x + 0.67 denkelemi elde edilir. Bu denklemin grafiği aşağıda verilmiştir:

ed2_0.gif

Şayet x3 + ax + b genel denkleminin tekrarlı kökü yoksa veya diğer bir ifadeyle 4a3 + 27b2 değeri 0 değilse , y2 = x3 + ax + b genel denklemi için bir grup oluşturacağı söylenebilir. Elipsel bir grup ile kast edilen, elipsel eğrinin üzerinde tanımlı olan noktalardır ve bu noktalar öyle bir O noktasında sonsuza gider.

Elipsel gruplar toplanabilir gruplardır. Aslında bu grupların en temel fonksiyonu toplamadır. Elipsel bir eğri üzerinde iki nokta geometrik olarak tanımlanabilir. Örneğin P=(xP,yP) noktasını tanımlamak aşağıdaki şekilde olduğu üzere mümkündür. Elipsel eğrilerin bir özelliği de x eksenine göre simetrik eğriler oluşudur. Örneğin P noktasının simetriği ve dolayısıyla eksi değeri -P = (xP,-yP) olarak tanımlanabilir.

ed2_1_1.gif

Örneğin yukarıdaki şekilde gösterilen iki nokta olan P ve Q noktalarının toplamını almak isteyelim. P ve Q noktalarının ikisinden de geçen bir doğru çizilir ( uzayda iki nokta bir doğru belirtir ve burada Q ≠ -P olmalıdır çünkü simetrik bir nokta alınması durumunda çizilen doğru y eksenine paralel olur)

Bu iki noktadan çizilen doğru, elipsel eğriyi 3. bir noktada kesmek zorundadır ve bu nokta -R olarak ifade edilirse P + Q = R ifadesi doğrudur.

Bir noktanın kendisi ile toplanması da elipsel eğrilerde mümkündür. Örneğin aşağıdaki eğride P noktasının değeri kendisi ile toplanmıştır.

ed2_1_3.gif

Yukarıdaki şekilde çizilen doğrunun yönü tek noktadan çıktığı için belirsizdir. Bir önceki örnekte iki nokta toplanırken iki noktadan geçen bir doğru çizildiğini hatırlayalım, şimdi tek nokta var ve dolayısıyla doğrunun açısı belirsizdir. Bu durum o noktadaki tanjant değeri alınarak çözülür. Başka bir değişle bir noktanın kendisi ile toplamı o noktadaki eğimin yönünde bir doğrunun yine elipsel eğri üzerindeki kestiği noktanın x eksenine göre tersini alarak bulunur.

Yukarıdaki P noktasının kendisi ile toplanması sırasında dikkat edilirse P noktasının y değeri 0′dan farklı kabul edilmiştir. Ancak bir noktanın y değeri 0 olsa bile kendisi ile toplanması mümkündür. Bu özel durumda noktanın eğimi y eksenine paralel olacağı için elipsel eğriyi ikinci bir noktadan kesemeyecektir. Bu durumda P noktasının kendisi ile toplamı O olacaktır. (Lütfen tanımdan bu noktanın sonsuz olduğunu hatırlayınız. Yani elipsel eğri üzerinde ancak sonsuzda bir değer bulunabilir. )

Şayet O değerine P noktası eklenecek olursa bu durumda sonuç yine P noktasına eşit olur. Bu durumda 3P = P , 4P = O , 5P = P olduğunu söylemek doğrudur.

Yukarıdaki bu toplam işlemlerini cebirsel olarak göstermek de mümkündür. Örneğin birbirinin x eksenine göre tersi olmayan iki nokta olan P = (xP,yP) ve Q = (xQ , yQ) noktalarını toplamak isteyelim. Bu iki noktanın toplamını daha önce R olarak tanımlamıştık yani P + Q = R olduğundan bahsetmiştik. Bu R noktasının x ve y koordinatları aşağıdaki şekilde bulunur:

xR = s2 - xP - xQ ve yR = -yP + s(xP - xR)

Yukarıdaki hesaplamada s değeri için s = (yP - yQ) / (xP - xQ) işlemi yapılır.

Benzer şekilde bir noktanın kendisi ile toplamının hesaplanması sırasında da şayet y değeri 0 değilse 2P = R olduğundan bahsetmiştik bu sefer s = (3xP2 + a) / (2yP ) denklemi için R noktasının koordinatları xR = s2 - 2xP ve yR = -yP + s(xP - xR) olarak hesaplanır.

Elipsel eğriler şifreleme ve veri güvenliğinde tam değer vermeleri özelliği ile kullanışlıdırlar. Genelde gerçek sayı kümesinde çalışan fonksiyonlar yuvarlama veya belirsizlik durumlarından dolayı şifreleme sistemlerinde tercih edilmemektedir. Ancak elipsel eğriler burada bir alternatif olarak kullanılabilir. Bu kullanım aşağıda anlatılmıştır:

Bir Fp grubu tanımlanırken 0 ile p-1 arasındaki tam sayılar kastedilir. Buradaki kasıt modulo p ile de ifade edilebilir. Örneğin F23 ifadesi ile 0 ile 22 arasındaki sayılar kastedilmiştir. Ayrıca bu kümede tanımlı olan herhangi bir işlem yine 0 ile 22 arasında bir sonuç üretebilir.

Bu durumda Fp grubunun üyesi olan her (x,y) ikilisi için yine Fp grubunda karşılık gelen bir sayı elipsel eğri üzerinde bulunabilir.

Örneğin, F23 grubu üzerinde tanımlı olan sayıları inceleyelim. a=1 ve b=0 durumu için y2 = x3 + x denklemi elde edilir. Burada (9,5) ikilisi denklemi aşağıdaki şekilde sağlar:

y2 mod p = x3 + x mod p

25 mod 23 = 729 + 9 mod 23

25 mod 23 = 738 mod 23

2 = 2

Denklemi sağlayan 23 nokta da aşağıda verilmiştir:

(0,0) (1,5) (1,18) (9,5) (9,18) (11,10) (11,13) (13,5)

(13,18) (15,3) (15,20) (16,8) (16,15) (17,10) (17,13) (18,10)

(18,13) (19,1) (19,22) (20,4) (20,19) (21,6) (21,17)

ed3.jpg

Yukarıdaki noktaların koordinat sistemi üzerinde çizilmiş halleri verilmiştir. Her ne kadar rasgele dağılmış bir grafik gibi görülsede y=11,5 doğrusundan bir simetri olduğu görülebilir.

Fp grubu üzerinde tanımlı elipsel eğriler ile gerçek sayılar kümesi üzerinde tanımlı eğriler arasındaki en önemli fark Fp grubundaki sayıların sonlu sayıda olmasıdır. Bu durum şifreleme için de tercih edilen bir özelliktir. Tam olarak bir eğri çizmenin ayrık noktalar için mümkün olmadığı aşikardır ancak bu dez avantajın yanında elipsel eğriler için geçerli olan bütün cebirsel kurallar Fp grubunda tanımlı elipsel eğriler için de geçerlidir. Ayrıca Fp grubundaki bütün sayılar tam sayı olduğu için gerçek sayılar kümesindeki yuvarlama ve belirsizlik durumu da söz konusu değildir.

Fp ayrık grubu üzerinde iki noktanın toplanması işlemi yukarıda anlatılan işlemin birebir aynısıdır:

P + Q = R olarak ifâde edilecek olursa

s = (yP - yQ) / (xP - xQ) mod p , değeri için

xR = s2 - xP - xQ mod p ve yR = -yP + s(xP - xR) mod p eşitlikleri yazılabilir.

Buradaki s değeri yukarıdaki durumun benzeri olarak P ve Q noktalarından geçen doğrunun eğimidir.

Bir noktanın kendisi ile toplanması durumu da yukarıdaki gerçek sayılara benzer şekilde:

2P = R olarak gösterilsin

s = (3xP2 + a) / (2yP ) mod p

xR = s2 - 2xP mod p ve yR = -yP + s(xP - xR) mod p

s değerinin bir önceki duruma benzer şekilde P noktasındaki eğim olduğu ve tanjant eğrisi olduğunu hatırlayalım.

Elipsel eğrilerin şifreleme sistemlerinde kullanılması aynı zamanda ayrık logaritma (discrete logarithm) hesaplamalarını da beraberinde getirmektedir. Buna göre bir sayının kendisi ile defalarca kere toplanması bir ahenk sınıfı için (congruence class) dairesel bir grup (Cyclic group) oluşturur ve bu dairesel grubu kullanan algoritmalarda kullanılabilir.

Elipsel eğriler üzerinde ayrık logaritma kullanımına bakalım:

y2 = x3 + 9x + 17 şeklinde F23 için tanımlanan bir elipse eğride

Q= (4,5) noktası için P = (16,5) noktasına göre ayrık logaritma nedir?

Bu sorunun çözümlerinden birisi Q değerine ulaşıncaya kadar P noktasının kendisi ile toplanmasıdır.  Bu işlem yapılırsa:

P = (16,5) 2P = (20,20) 3P = (14,14) 4P = (19,20) 5P = (13,10) 6P = (7,3) 7P = (8,7) 8P = (12,17) 9P = (4,5)

dolayısıyla P tabanında Q noktasının logaritma değeri  logp(Q) = 9 olarak bulunur.


« MD5 (Message Digest , Mesaj Özet)   |   Ayrık Logaritma (Discrete Logarithm) »



Yorumlar

Giriş yaparak yorum yazabilirsiniz.

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Ellipsel Eğri (Elliptic Curve)' isimli yazı 06 May 2008 tarihinde, saat: 12:18 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 306 defa okunmuştur.

Benzer yazıları Bilgisayar Matematiği, Veri Güvenliği(Cryptography) kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.


Eklenen Son Yazılar
Yapılan Son Yorumlar
Yakın Yazılar
Bağlantılar