Yazan : Şadi Evren ŞEKER

Bu yazının amacı bilgisayar bilimlerinde özellikle veri güvenliği ve şifreleme konularında (kriptoloji) oldukça önemli bir yeri olan çarpanlara ayırma işleminin hızlı bir şekilde gerçekleşmesi için kullanılan eliptik eğri ile çarpanlara ayırma metodunu açıklamaktır.

Literatürde Elliptic Curve Factorization Method olarak geçen ve bazan ECM olarak kısaltılan yöntem, aşağıdaki adımlardan oluşmaktadır.

Öncelikle sistemin çalışacağı bir eliptik eğri belirlenir. Bu eğrinin karakteristik denklemi aşağıdaki şekildedir:

y 2 = x3 + ax + b (mod n)

Ardından P=(x,y) şeklinde bir nokta belirlenir.

Bu eğrinin ve denklemin canlandırılması için yukarıda, örnek bir denklem ve çizimi verilmiştir.

Eliptik eğrilerde toplama işlemi daha önce Elipsel Eğri (Elliptic Cuve) başlıklı yazımızda açıklanmıştır. Bu yazıda anlatıldığı üzere bir toplama işlemi tanımlıyoruz.

Toplama işlemini ilerleterek kP = P + P + … + P şeklinde k adet toplama işlemini yapıp sonuçlarının ürettiği grup üzerinde, çarpanlarına ayırmak istediğimiz n sayısını tam bölen bir değer olup olmadığını arıyoruz.

Bu ilerleme sırasında herhangi bir eP değeri (e kadar toplanmış P noktası) sonsuz çıkabilir. ( Eliptik eğrilerde asimptotik değerlerin O ile gösterildiğini ve sonsuz olarak kabul edildiğini hatırlayınız. )

Bu durumda yeni bir P noktası seçerek ilerleme işlemini bu yeni P noktası üzerinden tekrarlamamız gerekir.

Örnek

Çarpanlarına ayırmak istediğimiz sayı 455839 olsun. Eliptik eğri olarak aşağıdaki denklemi seçiyoruz:

y2 = x3 + 5x – 5

Ayrıca başlangıç noktası olarak bu eğri üzerinde bulunan P(1,1) değerini seçelim. (12 = 13 + 5.1 – 5 denklemi çözülerek 1 =1 olduğu ve eğri üzerine bulunan bir nokta olduğu sınanabilir)

Öncelikle P+ P = 2P değerini hesaplayalım.

s=(3x2+5)/(2y)= (3 + 5) / 2 = 4 (x ve y değerleri P(1,1) noktası için 1’dir)

x′=s2-2x=14 ve y′=s(xx′)-y=4(1-14)-1=-53 değerleri bulunarak 2P = (x’, y’) yani 2P = (14, -53) değeri bulunur.

Şimdi 2P değeri için eğimi (Slope veya s olarak geçen değer) bulalım.

s=(3x2+5)/(2y)=(3 142 + 5) / 2(-53) = -593 / 106 olarak bulunur. Bulduğumuz bu eğim değerinin paydası bize çarpanlardan birisini önermektedir. Buna göre bulduğumuz eğim değerinin paydasının çarpanlarını aradığımız n değerini tam bölüp bölmediğini kontrol ediyoruz :

gcd ( 455839 , 106) = 1 olarak bulunuyor. Görüldüğü üzere sayımızı bölmüyor, bu durumda ilerlemeye devam ediyor ve bir sonraki noktayı bulmaya çalışıyoruz. Algoritmamız bundan sonraki adımlarda 3P, 4P, … şeklinde noktaları bulup bu noktaların eğimlerinin, çarpanlarını aradığımız n sayısını tam bölüp bölmediğine bakacağız.

Bu işlemlere devam edilirse, 8P değeri için s değerinin paydasının 599 olduğu görülebilir. Bu sayı 455839 sayısının çarpanlarından birisidir ve 455839 = 599 x 761 olarak bulunur.

Yukarıdaki sayısal örnek aşağıdaki kaynaktan alınmış ve Türkçeye çevirilmiştir. Trappe, W.; Washington, L. C. (2006). Introduction to Cryptography with Coding Theory (Second ed.). Pearson Prentice Hall. ISBN 0-13-186239-1.

 

Yorumlar

  1. Hadi Borozan

    Bu yöntem alternatif yöntemlere göre ne kazandırıyor bize? örneğin brute force ile gerçekleştirilen işlem ile karşılaştırılırsa? Teşekkürler

  2. Şadi Evren ŞEKER Article Author

    basitçe zaman kazandırıyor 🙂

    bakın aynı soruyu brute force ile çözecek olsaydık ( 455839 sayısını asal çarpanlarına ayırmak). Bu sayının kareköküne kadar olan değerlere bakmamız gerekecekti. Bu değerde yaklaşık olarak 676’dır ve bunun anlamı 676 bölme denemesi yapılacağıdır.

    Yukarıdaki eliptik eğri ile çarpanlara ayırma işlemi sırasında eğri üzerinde 4 noktanın koordinatları hesaplanıp bu noktaların eğiminin paydası ile en büyük ortak bölen değeri (gcd) hesaplanmıştır. Basit bir hesapla bu değer 20 bölme işleminin altında işlem gerektirir. Yani çok kaba hesapla 676 işleme göre 30 misli hızlıdır denilebilir.

  3. Bahar Doğan

    Ben İstanbul Teknik Üniversitesi, Matematik Mühendisliği 3. Sınıf öğrencisiyim. Şu an Danimarkada erasmus programıyla bulunuyorum. Burada Mathematical aspects of Cryptology adında bir ders alıyorum ve çarşamba günü sınavım var. Öncelikle belirtmek isterim ki web sayfanızın çalışmalarım sırasında bana çok yararı oldu. Çok teşekkürler fakat Eliptic curve factarization ile ilgili anlayamadığım bir kısım var.

    s=(3×2+5)/(2y)= (3 + 5) / 2 = 4 (x ve y değerleri P(1,1) noktası için 1′dir)
    x′=s2-2x=14 ve y′=s(x-x′)-y=4(1-14)-1=-53 değerleri bulunarak 2P = (x’, y’) yani 2P = (14, -53) değeri bulunur.

    x üssü ile y üssünü bir formül kullanarak mı hesaplıyoruz? eğer öyleyse formülü yazmanız mümkün mü?
    bir de x 2 üssü ve y 2 üssü olarak bulduğumuz koordinatlar 3p nin koordinatlarımı oluyor?

    Şimdiden çok teşekkürler,
    İyi Çlışmalar

  4. Şadi Evren ŞEKER Article Author

    Evet formül kullanılıyor. Formül yazıda zaten bulunuyor ve siz de yorumunuza almışsınız :

    s değeri hesaplanırken formülün türevi alınıyor, sizin yorumunuzda da yer alan değer budur:
    3x^2 + 5 değeri elipsel eğrinin denkleminin sağ tarafının x’e göre türevi
    2y ise sol tarafın türevidir.
    aslında s değeri tam olarak eğimi verir.
    x’ değeri ise sabit bir değerdir ve x = s^2-2x olarak hesaplanır.
    y’ ise x’ değerine bağlı bir değerdir. Yine yukarıdaki yazıda verilmiş.

    Ayrıca bütün bu formüller, aşağıdaki adreste detaylıca anlatılmıştır:

    http://www.bilgisayarkavramlari.com/2008/05/06/ellipsel-egri-elliptic-curve/

    Yazıdan da bağlantı vermiştim ama sanırım dikkatten kaçabiliyor, ayrıca yorum olması iyi oldu.

    Yukarıdaki yazıda özel olarak hesaplanan değer P+P değeridir. Yani, aynı nokta kendisi ile toplanıp 2P değeri bulunmuştur.

    3P = 2P + P olduğu için, bu değerleri bir kere daha mevcut P değeri ile toplamanız gerekir. kendisi ile toplamanız halinde 4P bulursunuz. Yukarıdaki örnekte P+R gibi farklı noktaların toplamını gerekmediği için anlatmamışım, bu toplama işlemini bağlantısını verdiğim yazıda açıklamıştım oradan bakabilirsiniz.

    x” ve y” olarak bulacağınız değerler ise 4P değerleridir. Çünkü burada 2P+2P işlemi yapılmaktadır. Yani 3P değil 4P bulunur.

    başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

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