Ellipsel Eğri (Elliptic Curve)

Yazan : Şadi Evren ŞEKER

Elipsel eğri (Eliptic curve) , gerçek sayılar kümesi (real numbers) üzerinde tanımlanan ve y² = x³ + 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 y² = x³ – 4x + 0.67 denkelemi elde edilir. Bu denklemin grafiği aşağıda verilmiştir:

Şayet x³ + ax + b genel denkleminin tekrarlı kökü yoksa veya diğer bir ifadeyle 4a³ + 27b² değeri 0 değilse , y² = x³ + 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.

Ö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.

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 = s² – x_P – x_Q ve y_R = -y_P + s(x_P – x_R)

Yukarıdaki hesaplamada s değeri için s = (y_P – y_Q) / (x_P – x_Q) 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 = (3x_P² + a) / (2y_P ) denklemi için R noktasının koordinatları x_R = s² – 2x_P ve y_R = -y_P + s(x_P – x_R) 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 F_p 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 F₂₃ 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 F_p grubunun üyesi olan her (x,y) ikilisi için yine F_p grubunda karşılık gelen bir sayı elipsel eğri üzerinde bulunabilir.

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

y² mod p = x³ + 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)

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.

F_p grubu üzerinde tanımlı elipsel eğriler ile gerçek sayılar kümesi üzerinde tanımlı eğriler arasındaki en önemli fark F_p 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 F_p grubunda tanımlı elipsel eğriler için de geçerlidir. Ayrıca F_p 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.

F_p 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 = (y_P – y_Q) / (x_P – x_Q) mod p , değeri için

x_R = s² – x_P – x_Q mod p ve y_R = -y_P + s(x_P – x_R) 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 = (3x_P² + a) / (2y_P ) mod p

x_R = s² – 2x_P mod p ve y_R = -y_P + s(x_P – x_R) 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:

y² = x³ + 9x + 17 şeklinde F₂₃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 log_p(Q) = 9 olarak bulunur.

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

Yorumlar

Toplam 4 yorum var.

hercumartesi | 03 Jun 2008, 19:17
2P = R olarak gösterip
s için (3xP^2 + a) / (2yP ) mod p

denklemlerini vermişsiniz. örnek olarak verdiğiniz çözümlü soruda P(16,5) noktasını kendisiyle toplayıp P(20,20) sonucuna ulaşmışsınız. verdiğiniz denklemde her şeyi yerine yerleştirip eğimi bulmaya çalıştığımda sonuca ulaşamıyorum. s’i bulmak istediğimde, 3.16^2+9/2.5 mod23 işlemi 77,7mod23 olarak çıkıyor. ondalıklı bir sayının modunu almak? işte burada tıkanıyorum, ondalıklı bir sayının modu diye bir şey olmaz sanırım, mantıksız görünüyor. ya bir yerde yanlış yapıyorum, ya formülü yanlış vermişsiniz ya da ondalıklı sayının modu diye bir şey var.. nerde hata yapıyorum? yardımcı olursanız sevinirim..
hercumartesi | 03 Jun 2008, 20:22
777/10 mod23 işleminde takıldığım için soru sormuştum fakat az önce nereyi atladığımın farkına vardım. sonuçta 23′lük sistemdeyiz.. 777+23/10 mod23 dediğim zaman burdan 20 sonucuna ulaşabiliyorum.. mesajım onaylanmadan silinebilir..
Menezes-Qu-Vanstone Şifrelemesi (Cipher) : bilgisayar.kavramlari.com | 08 Jun 2008, 18:09
[...] şifrelemesi ellipsel eğri (elliptic curve) üzerinde çalışır ve anahtar üretimini verilen eğri üzerinden [...]
iskender tosun | 01 Dec 2009, 02:56
P ve Q noktalarının toplanmasından elde edilecek olan R noktasının kordinat değerlerinin hesaplanmasında kullanılan XR=s^2-Xp-Xq ve YR=-Yp+s*(Xp-Xr) formüllerinin matematiksel olarak nasıl çıkarıldığının detaylarına inerseniz çok sevinirim. Teşekkür Ederim

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 1645 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.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar