Yazan : Şadi Evren ŞEKER

Elipsel eğri (Eliptic curve) , 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.

Yorumlar

  1. hercumartesi

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

  2. hercumartesi

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

  3. iskender tosun

    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

  4. Huseyin Erenköy

    Türkçe’ye çeviri sırasında bir hatanın oluştuğunu düşünüyorum. Çünkü karşılaştığım bir ders notundan direk aktarmak istiyorum

    First and foremost, elliptic curves have nothing to do with ellipses.
    Ellipses are formed by quadratic curves. Elliptic curves are always
    cubic. [Note: Elliptic curves are called elliptic because of their relationship to
    elliptic integrals in mathematics. An elliptic integral can be used to determine the
    arc length of an ellipse. ]

    Çevirinin Eliptik Eğri olarak yapılmasının daha doğru olacağı kanısındayım.

    Saygılarımla, Hüseyin

  5. Huseyin Erenköy

    Elliptic Curve’lerin GF(p) üzerindeki hali çok güzel anlatılmış, rica etsem “Elliptic Curves over GF(2^k)” konusunada değinebilirmisiniz.

hercumartesi için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir