Tümevarım Mod işlemini ters çevirme

Arkadaşlar merhaba

Elimizde şöyle bir mod hesaplama nokta bulma kodu var

mod = 17
x = 15
y = 13
başlama = 1
bitiş = 18



field = SubGroup(p=mod, g=(x, y), n=30, h=1)
curve = Curve(a=0, b=7, field=field, name=' ')
#print('curve:', curve)

for k in range(başlama, bitiş):
    p = k * curve.g
    print(f"{k} * x = {p.x}\n{k} * y = {p.y} \n")

kodun çalıştırdığımız zaman çıktısı şu şekilde

1 * x = 15
1 * y = 13 

2 * x = 2
2 * y = 10 

3 * x = 8
3 * y = 3 

4 * x = 12
4 * y = 1 

5 * x = 6
5 * y = 6 

6 * x = 5
6 * y = 8 

7 * x = 10
7 * y = 15 

8 * x = 1
8 * y = 12 

9 * x = 3
9 * y = 0 

10 * x = 1
10 * y = 5 

11 * x = 10
11 * y = 2 

12 * x = 5
12 * y = 9 

13 * x = 6
13 * y = 11 

14 * x = 12
14 * y = 16 

15 * x = 8
15 * y = 14 

16 * x = 2
16 * y = 7 

17 * x = 15
17 * y = 4 

Şimdi bu kodu tanıtacak olursak şöyle ki;

mod = modunu almak istediğimiz sayı
x = 1. noktanın grafik üzerindeki x değeri
y = 1. noktanın grafik üzerindeki y değeri
başlama = eliptic curve üzerindeki ilk nokta
bitiş = eliptik curve üzerindeki son nokta

örneğin
koda başlama 3, bitiş 5 değeri yazarsak programın çıktısı şu şekilde olacak

3 * x = 8
3 * y = 3 

4 * x = 12
4 * y = 1 

bizim amacımıza gelince
yapmak isteyip te bir türlü yapamadığımız işlem şu

örneğin koda başlama ve bitiş değil de
x = 8 ve y = 3 yazarsak kod bize bunun 3. nokta olduğunu hesaplayıp versin

Bunun için acaba ne yapmamız lazım ?

sanırım biraz meşakatli
:thinking:

Bkz Soru Sorarken Sıkça Düşülen Hatalar #6

1 Beğeni

Kodun ham hali aşağıda paylaştığımız şekildeydi
bizde biraz daha sadeleştirip işimize yarayacak hale getirmeye çalıştık
ki öyle kullanmaya da devam ettik

from tinyec.ec import SubGroup, Curve

P = 17
N = 115
A = 0
B = 7
Gx = 15
Gy = 13
G = (Gx, Gy)



field = SubGroup(p=P, g=(Gx, Gy), n=N, h=1)
curve = Curve(a=0, b=7, field=field, name='p1707')
#print('curve:', curve)

for k in range(0, 5):
    p = k * curve.g
    print(f"{k} * Gx = {p.x}\n{k} * Gy = {p.y} \n")

Ama dediğiniz gibi
Belki de biz daha önce ham haliyle çalıştırdığımız için
sadeleştirince dahi pek etki hissetmemiş olabiliriz

İnş bu defa sizin bilgisayarda da çalışır

Sadelestirirken kutuphane import eden satiri silmissiniz. Kodun calismamasina yol acmakla beraber okumaya calisan insanlardan da SubGroup ve Curve’un ne olduklari onemli bilgisini sakiniyor.

Yani mod, x, y, vs. parametrelerini tanitmadan once SubGroup ve Curve’u tanitmak lazim.


Neyse,

matematiksel olarak mi, bir tablodan bakarak mi?

1 Beğeni

Haklısınız böylelikle istemeden de olsa yeni olduğumuz yine belli oldu :slight_smile:

Matematiksel olarak sonucu almamız gerekiyor

X ve Y değerleri girince bir nevi ya kendisi çok hızlı deneyerek sonucu bulabilmesi lazım

Veyahut bizim için en hızlısı ve iyisi işlem yaparak sonucu bulabilirse daha iyi olurdu

Hmm, kutuphanenin kaynak koduna baktiniz mi?

Yok gibi duruyor ama benim anladigim bir alan degil.

Hatta matematiksel cevap icin de ayni seyi soyleyecektim… Sanki alanda bilgisi olan birinin cevaplamasi gerekiyor.

Benim tek diyebilecegim… EC uzerinde nokta bulmanin tersi zor bir islem degil mi? Hatta bu yuzden kriptografik imzalama islemlerinde kullanilmiyor mu? (Belki parametreler basit/ufak diye kolaydir da… yine, bilemeyecegim :confused: )

Dediğiniz gibi biraz zor bi işlem
Elle yapmaya çalıştık çok zaman alıyor ve sonuca ulaşmak imkansız gibi
Küçük sayılarda biraz daha deneme yanılmayla bulabiliyoruz ama mod değeri büyüdükçe hesaplamak imkansız gibi

peki x ve y değerlerini girsek, kendisi süratle belirlenen koordinatı arayıp bulsa ve bu 3. noktadır dese
Hatta biraz daha kodun işini kolaylaştırmak için biz tahmin ettiğimiz başlangıç ve bitiş noktaları versek daha hızlıda bulabilir.

Çünkü dikkat edersek mod(17) sayısının sayısal değerinin ilk yarısı(1 ile 8 arası) ve ikinci yarısındaki(10 ile 17 arası) x değerleri aynı tekrar ediyor ama y değerleri farklı

Bu nedenle biz ilk aralıkta olmadığını tahmin ediyorsak ikinci aralığın başlangıç(10) ve bitişini(17) yazarsak
kod o aralıkta görevi gereği sırayla noktaları hesaplasa ve kendisinden istenen noktayı bulunca sadece o noktanın kaç olduğunu bize verirse yine problem çözülmüş olur

Aynen dediğiniz gibi yine de gayretiniz için çok teşekkür ederiz

Brute-force dedigimiz yaklasim bu. (Sonucu bulana kadar butun degerleri tek tek denemek.)

Yukarida “tablo kullanmak” dedigim de bunun [hafiza el verdigince] sonuclar yazilarak, ezberlenerek yapilani.

a=0 eliptik egrinin X eksenindeki simetrisinden kaynaklaniyor olsa gerek.

Demekki brute-force dedikleri yöntem buymuş.
Bizde araştırma yaparken bazı sitelerde buna denk geliyorduk türkçeyede kaba kuvvet diye google ceviriyordu ama bu mantıkla hareket ettiğini bilmiyorduk

O zaman bu kodu brute-force çevirmek lazım

Aynen dediğiniz gibi x ekseninde simetrik olmasından kaynaklanıyor

Tekrardan çok teşekkür ederiz

başkanım soruyu da düzeltik
:wink:

Burası Huş’tur yolu yokuştur

Giden gelmiyor acep ne iştir?

----- Burası -----

:thinking:

1 Beğeni

Sizin sorular için var ya bir hafta ders çalışmak gerekiyor. :slight_smile:

GitHub - alexmgr/tinyec: A tiny ellliptic curve library

Buraya kadar geldim, tabi kütüphaneye yine göz ucuyla baktım.

Kendimi buralarda buldum:

download (psu.edu)

Draft NIST SP 800-186, Recommendation for Discrete Logarithm-Based Cryptography: Elliptic Curve Domain Parameters

Sonra ilk verdiğim kütüphane linkinin altındaki şu koda baktım.

>>> import tinyec.ec as ec
>>> field = ec.SubGroup(97, (1, 2), 5, 1)
>>> curve = ec.Curve(2, 3, field)
tinyec/ec.py:115: UserWarning: Point (1, 2) is not on curve "undefined" => y^2 = x^3 + 2x + 3 (mod 97)
  warnings.warn("Point (%d, %d) is not on curve %s" % (self.x, self.y, self.curve))
>>> # Warning is generated because the generator point does not belong to the curve
>>> p1 = ec.Point(curve, -5, 3)
>>> p1.on_curve
False
>>> p2 = ec.Point(curve, 22, 5)
>>> p2.on_curve
True
>>> print(p1 + p2)
(18, 42) off "undefined" => y^2 = x^3 + 2x + 3 (mod 97)

Burada yapılabilecek tek şey var.

p2.on_curve den faydalanarak true olanları almak.

Tabi hazır kod istemeden kendiniz uğraşacaksınız :wink:

1 Beğeni

Biraz daha açayım mı?

İki tane içi içe for döngüsü oluşturun, 0 dan modüle kadar. Buradaki örnekte modül 97

x ve y için.

Sonra p1= ec.Point(curve,x, y)
ile noktayı alın.

p1.on_curve True olursa x ve y ikilisini yazdırın yada bir yere kaydedin.

Yani bilgisayar için en çok yapmayı şeyi yaptırın, tüm değerleri denettirmek.

Siz birde bizi düşünün sormadan önce ne kadar çalışıyoruz
:smile:

Çok teşekkür ederiz abi yine döktürmüşsünüz :+1:

Açabilirseniz çok iyi olur :sweat_smile:

import tinyec.ec as ec

field = ec.SubGroup(97, (1, 2), 5, 1) # (burada sırasıyla mod, g(gx,gy), n ve h değerleri var)

curve = ec.Curve(2, 3, field) #(buda büyük ihtimalle referans alınacak ilk x ve y değeri)

tinyec/ec.py:115: UserWarning: Point (1, 2) is not on curve “undefined” => y^2 = x^3 + 2x + 3 (mod 97)
warnings.warn(“Point (%d, %d) is not on curve %s” % (self.x, self.y, self.curve))

Warning is generated because the generator point does not belong to the curve

p1 = ec.Point(curve, -5, 3) #(burayı çözemedim, acaba aranan değermi yoksa alt ve üst sınırmı )
p1.on_curve
False
p2 = ec.Point(curve, 22, 5) #(burayıda çözemedim, acaba aranan değermi yoksa alt ve üst sınırmı)**
p2.on_curve
True
print(p1 + p2)
(18, 42) off “undefined” => y^2 = x^3 + 2x + 3 (mod 97)

Orada x v y noktaları.

Bunları sayısal yerine x ve y adında iki değişkenle iki iç içe for döngüsü içerisine alırsanız, true yazanlar eğrinin üzerindeki p1 veya p2 sayısal değerleridir.

Önce denkleminizi tanımlayın

for x 1 den modüle kadar.
for y 1 den modüle kadar.

p=ex.Point(curve, x,y)
if p.on_curve
x ve y değerini yazdır.

Taslak kod böyle bir şey.

Abi ne kadar değişiklik yapsamda veya yapmasamda hep aynı uyarıyı veriyor

Input In [12]
tinyec/ec.py:115: UserWarning: Point (1, 2) is not on curve “undefined” => y^2 = x^3 + 3 (mod 17)
^
SyntaxError: illegal target for annotation

Bunu çözemedim