GPU ile Eliptik Eğri Aritmetiği ve Programlama Hakkında

[mamuu]

Merhaba

Uzun zamandır eliptik eğri kriptolojisi ile ilgileniyorum. Eğri Matematiğinde(sadece nokta toplama) ilgili kütüphaneler mevcut. Windows 10, Sage ve Python kullanabiliyorum.

C bilen bir arkadaşım benim için bu aşağıdaki aritmetik kodunu C de yazdı ve CPU ile gayet hızlı çalışıyor fakat GPU  kadar değil. C konudu GPU üzerinden çalıştırmak için yeterli bilgimiz yok bu yüzden çalıştracak bir yöntem arıyorum.

benzer şekilde pythonda fastecdsa(https://github.com/AntonKueltz/fastecdsa) gibi kütüphanelerde kullandım. Fastecdsa tıpkı Sage gibi pythonda kullanmaya imkan tanıyor. Biginteger problemini C üzerinde kendilerine has bir kütüphane ile çözebiliyorlar. Python u Tensorflow sayesinde GPU ile çalıştırabiliyorum. Fakat  tf-big (https://github.com/tf-encrypted/tf-big) gibi kütüphanelerin windows ta bir karşılığı yok. Tf-Big yeterli olacak mı emin değilim.


Özetle şöyle çıkmaza girdim.
GPU ile çalışmak istiyorum C bilmiyorum.
GPU ile python da çalışabiliyorum ama int64 ten yukarı çıkamıyorum. Biginteger Bitwise ile yapılabilir mi diye araştırdım ama kullanımını anlamadım.Amatör Matematik meraklısı olduğumda algoritma mantığı geliştirsemde bilgisayar limitlerini ve terimlerini anlamakta güçlük çekiyorum. (https://github.com/YulitaGap/BigInteger)


Bitwise bit üzerinden matematik işlemi yapılabilen bir 2 lik tabanda bir sistem midir ? 2 lik tabanda modüler aritmetik nasıl çalışır ?

Kısaca bitwise işlemi kafamı kurcaladı. Pratik olarak işlemi bitler halinde GPU çiplerine işletmek daha hızlı olacaktır diye düşünüyorum.

C üzerinde çalışan OpenCL destekli bir kütüphane de mevcut (https://github.com/ilaychen/ECDSA-OpenCL)

Eğri aritmetiğinde GPU nun  kullanıldığını test ettim. (Bitcrack,Kangaroo,Vanitysearch vs.)

Sorularımı genelde yabancılara soruyorum ilgili Türkler vardır Türkçe konuşalım diye buraya yazdım. Tekrar selamlar teşekkürler.




Bitcoinin kullandığı Eliptik Eğri Aritmetiğinin en basit Python Kodu :

Code:

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1 # The proven prime
N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # Number of points in the field
Acurve = 0; Bcurve = 7 # This defines the curve. y^2 = x^3 + Acurve * x + Bcurve
Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424
GPoint = (Gx,Gy) # This is our generator point. Tillions of dif ones possible


def modinv(a,n=Pcurve): #Extended Euclidean Algorithm/'division' in elliptic curves
    lm, hm = 1,0
    low, high = a%n,n
    while low > 1:
        ratio = high/low
        nm, new = hm-lm*ratio, high-low*ratio
        lm, low, hm, high = nm, new, lm, low
    return lm % n

def ECadd(xp,yp,xq,yq): # Not true addition, invented for EC. It adds Point-P with Point-Q.
    m = ((yq-yp) * modinv(xq-xp,Pcurve)) % Pcurve
    xr = (m*m-xp-xq) % Pcurve
    yr = (m*(xp-xr)-yp) % Pcurve
    return (xr,yr)

def ECdouble(xp,yp): # EC point doubling,  invented for EC. It doubles Point-P.
    LamNumer = 3*xp*xp+Acurve
    LamDenom = 2*yp
    Lam = (LamNumer * modinv(LamDenom,Pcurve)) % Pcurve
    xr = (Lam*Lam-2*xp) % Pcurve
    yr = (Lam*(xp-xr)-yp) % Pcurve
    return (xr,yr)

def EccMultiply(xs,ys,Scalar): # Double & add. EC Multiplication, Not true multiplication
    if Scalar == 0 or Scalar >= N: raise Exception("Invalid Scalar/Private Key")
    ScalarBin = str(bin(Scalar))[2:]
    Qx,Qy=xs,ys
    for i in range (1, len(ScalarBin)): # This is invented EC multiplication.
        Qx,Qy=ECdouble(Qx,Qy); # print "DUB", Qx; print
        if ScalarBin[i] == "1":
            Qx,Qy=ECadd(Qx,Qy,xs,ys); # print "ADD", Qx; print
    return (Qx,Qy)

[1714755335]

1714755335

[John_Ahmet]

Şöyle bir kod mu arıyorsun?

verilen bir string ifadeyi SHA256 ile hashleyip bunu private key olarak kullanarak public ve private adreslerini ekrana yazar. Her şey normal görünüyor fakat dikkat edersen passphrase olarak kullandığı "password" kelimesi için bu daha önce çalıştırılmış ve bu adrese bitcoin göndermişler. Çok ilginç değil mi? Daha bu şekilde 10 binlerce adres var. Bende tüm bunların bir veritabanı var.

Programın çıktısı şu şekilde;

Code:

address: 16ga2uqnF1NqpAuQeeg7sTCAdtDUwDyJav
private key: 5JXvHQfGHxUffo8BLRG1RBecRCZ2Jygtx5cNSiZoyk5Zcmhsdso

https://www.blockchain.com/btc/address/16ga2uqnF1NqpAuQeeg7sTCAdtDUwDyJav

Bu kodu bir text dosyasına gen.c ismiyle kaydettiğini varsayarsak. Şu şekilde executable hale getirebilirsin. Sonra ./gen şeklinde çalıştırabilirsin.

Code:

gcc -lcrypto -o gen gen.c

Bu kodda ilgili fonksiyonlar daha çok hızlandırılabilir. Başlangıç için bu kodla başlayabilirsin. Python çok daha yavaş kalacaktır. C daha iyi bir tercih olur.

Örneğin "password" yazan yere başka kelimeler girerek verdiği adreslerdeki bakiyeyi kontrol et. Hatta empty string i dene, o adrese bile daha önce bitcoin gönderdiklerini göreceksin. Sanırım bunlar programcıların yaptığı belli başlı hatalar.

Code:

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <openssl/sha.h>
#include <openssl/ssl.h>
#include <openssl/ec.h>
#include <openssl/ripemd.h>

int create_address_from_string(const unsigned char *string,
		unsigned char *address,
		unsigned char *priv_key,
		bool base58,
		bool debug,
		EC_GROUP *precompgroup);
void print_hex(u_int8_t * buffer, unsigned int len);
void base58_encode(unsigned char *data, unsigned int len, char *result);
void prepare_for_address(unsigned char *data, int datalen, char start_byte);


int main(int argc, char *argv[]) {
    unsigned char message[32] = "password";
    unsigned char address[64];
    unsigned char priv_key[64];

    if (create_address_from_string(message, address, priv_key, true, false, NULL) == 1) {
		printf("address: %s\n", address);
		printf("private key: %s\n", priv_key);
		return 0;
	}
	else {
		printf("Something went wront :(\n");
		return 1;
	}
}

/* creates a bitcoin address+private key from the SHA256
 *  hash of string. converts to base58 if base58 is 'true'
 *  returns 1 if successful, 0 if not*/
int create_address_from_string(const unsigned char *string,
		unsigned char *address,
		unsigned char *priv_key,
		bool base58,
		bool debug,
		EC_GROUP *precompgroup) {

    u_int8_t * hash = malloc(SHA256_DIGEST_LENGTH);
    BIGNUM * n = BN_new();

    //first we hash the string
    SHA256 (string, strlen(string), hash);
	//then we convert the hash to the BIGNUM n
    n = BN_bin2bn(hash, SHA256_DIGEST_LENGTH, n);

    BIGNUM * order = BN_new();
    BIGNUM * nmodorder = BN_new();
	BN_CTX *bnctx;
	bnctx = BN_CTX_new();

    //then we create a new EC group with the curve secp256k1
	EC_GROUP * pgroup;
	if (precompgroup == NULL)
		pgroup = EC_GROUP_new_by_curve_name(NID_secp256k1);
	else
		//unless one has been passed to this function. in which case we use that curve.
		pgroup = precompgroup;


    if (!pgroup) {
    	printf("ERROR: Couldn't get new group\n");
    	return 0;
    }

    //now we need to get the order of the group, and make sure that
    //the number we use for the private key is less than or equal to
    //the group order by using "nmodorder = n % order"
    EC_GROUP_get_order(pgroup, order, NULL);
    BN_mod(nmodorder, n, order, bnctx);

    if (BN_is_zero(nmodorder)) {
    	printf("ERROR: SHA256(string) %% order == 0. Pick another string.\n");
    	return 0;
    }

    //now we create a new EC point, ecpoint, and place in it the secp256k1
    //generator point multiplied by nmodorder. this newly created
    //point is the public key


    EC_POINT * ecpoint = EC_POINT_new(pgroup);

	if (!EC_POINT_mul(pgroup, ecpoint, nmodorder, NULL, NULL, NULL))
	{
    	printf("ERROR: Couldn't multiply the generator point with n\n");
    	return 0;
    }

    if (debug) {
        BIGNUM *x=NULL, *y=NULL;
        x=BN_new();
        y=BN_new();

        if (!EC_POINT_get_affine_coordinates_GFp(pgroup, ecpoint, x, y, NULL)) {
        	printf("ERROR: Failed getting coordinates.");
        	return 0;
        }

    	printf ("x: %s, y: %s\n", BN_bn2dec(x), BN_bn2dec(y));

        BN_free(x);
        BN_free(y);
    }

    //then we need to convert the public key point to data
    //first we get the required size of the buffer in which the data is placed
    //by passing NULL as the buffer argument to EC_POINT_point2oct
    unsigned int bufsize = EC_POINT_point2oct (pgroup, ecpoint, POINT_CONVERSION_UNCOMPRESSED, NULL, 0, NULL);
    u_int8_t * buffer = malloc(bufsize);
    //then we place the data in the buffer
    int len = EC_POINT_point2oct (pgroup, ecpoint, POINT_CONVERSION_UNCOMPRESSED, buffer, bufsize, NULL);
    if (len == 0) {
    	printf("ERROR: Couldn't convert point to octet string.");
    	return 0;
    }

    //next we need to hash the public key data. first with SHA256, then with RIPEMD160
    SHA256(buffer, len, hash);
    u_int8_t * ripemd = malloc(RIPEMD160_DIGEST_LENGTH+1+4);
    RIPEMD160(hash, SHA256_DIGEST_LENGTH, ripemd);

    if (base58 == true) {
		//here we add the version byte to the beginning of the public key and four checksum
		//bytes at the end
		prepare_for_address(ripemd, RIPEMD160_DIGEST_LENGTH, 0);


		if (debug)
			print_hex(ripemd, RIPEMD160_DIGEST_LENGTH+1+4);

		//and we convert the resulting data to base58
		base58_encode(ripemd, RIPEMD160_DIGEST_LENGTH+1+4, address);
    } else {
    	memcpy(address, ripemd, RIPEMD160_DIGEST_LENGTH);
    }


    //now we need to convert the big number nmodorder (private key) to data
    int buflen = BN_num_bytes(nmodorder);
    u_int8_t * buf = malloc(buflen+1+4);
    int datalen;

    //nmodorder is converted to binary representation
    datalen = BN_bn2bin(nmodorder, buf);


    if (base58 == true) {
		//and we add version byte and four byte checksum to the data
		prepare_for_address(buf, datalen, 0x80);

        //and convert this to base58
        base58_encode(buf, datalen+5, priv_key);
    } else {
    	memcpy(priv_key, buf, datalen+5);
    }

    free(hash);
    free(buffer);
    free(ripemd);
    free(buf);
    BN_free(n);
    BN_free(order);
    BN_free(nmodorder);
    if (precompgroup == NULL)
    	EC_GROUP_free(pgroup);
    EC_POINT_free(ecpoint);
    BN_CTX_free(bnctx);
    return 1;
}

/*prepares data to be converted to address. specifically, it adds
 start_byte to the beginning and a four-byte doubleSHA256 checksum to the end */
void prepare_for_address(unsigned char *data, int datalen, char start_byte) {
	unsigned char *tmpbuf = malloc(datalen);
    //get data into a temporary buffer
    memcpy(tmpbuf, data, datalen);
    //shift data one byte forward, to make room for star_byte
    memcpy(data+1, tmpbuf, datalen);
    data[0] = start_byte;

    unsigned char *hash = malloc(SHA256_DIGEST_LENGTH);
    SHA256(data, datalen+1, hash);
    SHA256(hash, SHA256_DIGEST_LENGTH, hash);

    //copy four first bytes from hash to the end of data (checksum bytes)
    memcpy(data+datalen+1, hash, 4);
    free(tmpbuf);
    free(hash);
}

void print_hex(u_int8_t * buffer, unsigned int len) {
	int x;
	for (x = 0; x < len; x++) {
		printf("%.2x",buffer[x]);
	}
	printf("\n");
}

/*return the base58 encoding of data*/
void base58_encode(unsigned char *data, unsigned int len, char *result) {
	const char code_string[] = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    BIGNUM *x, *rem, *base, *tmp, *tmp2;
    x = BN_new();
	rem = BN_new();
	base = BN_new();
	tmp = BN_new();
	char * output_string = malloc(64);

	x = BN_bin2bn(data, len, x);

	BN_set_word(rem, 1);
	BN_set_word(base, 58);

	BN_CTX *bnctx;
	bnctx = BN_CTX_new();

	int i = 0;
	while (!BN_is_zero(x)) {
		BN_div(tmp, rem, x, base, bnctx);
		output_string[i++] = code_string[BN_get_word(rem)];


		tmp2 = x;
		x = tmp;
		tmp = tmp2;
	}


	//public key
	int i2 = 0;
	while (data[i2] == 0) {
		output_string[i++] = code_string[0];
		i2++;
	}

	int base58len = i;
	while (i>=0) {
		result[base58len-i] = output_string[i-1];
		i--;
	}
	result[base58len] = 0;

	BN_free(x);
	BN_free(base);
	BN_free(rem);
	BN_free(tmp);
	BN_CTX_free(bnctx);
	free(output_string);
}

[John_Ahmet]

Verdiğim kod bu işlemleri zaten yapıyor.

Code:

//first we hash the string
SHA256 (string, strlen(string), hash);

Yukarıdaki kod satırını kaldırıp belirlediğin 0 ile (2 ^ 256 - 1) aralığındaki bir sayının 32 baytlık byte dizisini direk hash isimli değişkene verirsen zaten bu kod sana bu sayıya karşılık gelen priv ve pub keyleri verecektir. Bir döngü içerisinde senin belirleyeceğin matematikteki seyrek sayı dizilerinin bir kümesini test etmek isteyebilirsin. Malum bu brute force yönteminde birer birer artırmak yerine x artırarak işlemin daha hızlı sonuçlanmasını sağlayabiliyorsun. x ne kadar büyük olursa işlem o kadar çabuk tamamlanır. x elbette gerçekten çok büyük olursa

BigInt kullanmak yerine uint256 kullanmak çok fazla hız kazandırır.

Code:

uint256 N = 0;
uint256 X = [your magic number];
while(N < MAX_N) {
  N += X;
  if(checkPublicKeyInBlockChain(N)) {
    logger(N);
  }
}

Elbette büyük marketlerin programcıları bu ihtimalleri düşünerek N  sayısını asal bir sayı olarak seçmişlerdir gibi bir ön kabulum var. Ne de olsa asal olmayan bir sayı seçerlerse bu yöntemler ile blockchain deki işlem görmüş yaklaşık 900 milyon adresten birini denk getirmeniz daha kolay olurdu.

Dolayısıyla N için matematikteki seyrek sahte asalları kullanarak çok hızlı bir algoritma elde edebilirsin. Bu sayıların 256 bit içerisindeki karşılıkları gerçekten çok seyrektir ve kullanmış olma ihtimalleri de oldukça yüksektir.

Öncelikle karşılaştırma algoritmanı nasıl kurguladığın önemlidir. Geriye kalanlar zaten çözülmüş problemler...

GPU konusuna gelince, NVIDIA ekran kartları için CUDA, AMD anakartları için de OPENCL platformlarını kullanabilirsin. Örnek bir kod görmek istersen VanitySearch projesinin kodlarına bakabilirsin. Gerçekten daha iyi bir kod görmek istiyorsan xmrig projesinin kodlarını incele! Bu Monero madenciliğini GPU üzerinden yapmak için RandomX hash algoritmasını kullanıyor olsa da CUDA ve OPENCL kullanımının nasıl yapıldığını öğrenmen için sana referans olabilir. Alttan alta monero madenciliği yap daha çok kazanırsın gibi bir mesaj da veriyor olabilirim

[mamuu]

John_Ahmet değerli bilgiler için teşekkürler.



O kadar çok C kullanamıyorum daha çok matematik ve kriptografi ile ilgiliyim.

VanitySearch un kodunu inceledim. Pubkey i bitcoin adreslerine çeviren bana göre kodu okumamı zorlaştıran bir sürü karşılaştırma var ve kontrol var benim yapmak istediğim işlemler sadece Elliptic Curve de ve Matematiksel

 
Açıkçası Secp256k1 için C de GPU(Nvidia) ile çalışan 3 tane fonksiyon lazım EcAdd, Ecdouble, EcMultipy , İlgilenirsen VanitySearch i modifiye edecek C bilgin varsa yapar mısın ?

Selamlar..

[John_Ahmet]

Bende CUDA8 desteği olan eski bir grafik kartı var. CUDA8 ve CUDA 10.x arasında çok fark olabilir. Performans açısından pek çok farklılık oluyor. CUDA8 için çok vaktimi almazsa bir bakayım. CUDA 10.x için modifikasyon yapmak durumunda kalabilirsin.

[John_Ahmet]

Bu konudaki matematiği benden daha iyi biliyor olabilirsin. Sen de bana bu konuda daha detaylı bilgi verebilir misin?

Örneğin senin aradığın temel kodu ifade eden şöyle bir kod yazalım. Ancak burada x ve y kaç bitlik integer sayılar olmalı ve ECdouble için ne kadar duyarlı bir kayan noktalı sayı gerekiyor?

Bu temel kod üzerinden bana adım adım EllipticCurve'nin işlevini anlatabilir misin? ECdouble işlevi de Point mi döndürüyor?

Code:

class Point
{
    public:
        long long int x, y;

    public: Point(long long int _x, long long int _y)
    {
        x = _x;
        y = _y;
    }

    public: void print()
    {
        cout << "(";
        cout << x;
        cout << ", ";
        cout << y;
        cout ")";
    }
};

class EllipticCurve
{
    public:
        int a;
        int b;
        unsigned int m;

    public: EllipticCurve(int _a, int_b, unsigned int modul)
    {
        a = _a;
        b = _b;
        m = modul;
    }

    public: Point generate(unsigned long long int x)
    {
        // looks for Points on the curve with the given x coordinate
        // returns the first matching point
    }

    public: Point add(Point p, Point q)
    {
        // complex addition function with if-else trees
        // the function code is not needed for this question
    }

    public: Point mul(Point p, unsigned int n)
    {
        // see above
    }
};

[John_Ahmet]

Sen beni anlamamışsın. Örneğin ben RSA kriptolarının nasıl çalıştığını ve nasıl public key üretildiğini biliyorum.

Şimdi burada ilk belirlediğin sayı private keyimiz mi yoksa ona yakın bir asal sayı mı seçiyorsun? Sonraki ona yakın bir asal sayı daha var onu neden seçtin? Sonra hangi matematiksel işlemlerden sonra Gx ve Gy yi belirliyorsun. Örneğin RSA kriptolarında Fermat teoreminden faydalanılıyor. Ben burada ne yapıldığını hâlâ anlamadım. Daha açıklayıcı şekilde öncelikle özetle "EllipticCurve nedir?" ile başlayıp, (1  ile 2 ^ 256 - 2) aralığında seçtiğimiz private key ile Wif adresini ve tüm public key türlerini oluştururken EllipticCurve işlevinin tüm detaylarını daha açıklayıcı anlatabilir misin? Ayrıca tüm bunlar hangi teoremlere dayanıyor.

[mamuu]

Şifreleme yöntemlerini tanımlamak gerekiyor.

Simetrik şifreleme -> Veriyi şifrelediğin anahtarı kullanarak şifreli veriyi çözme için yine aynı anahtarı kullandığın şireleme metodudur. >- AES, DES ..gibi
Asimterik şifreleme -> Veriyi iki anahtar ile şifreleyen şifreleyen ve çözebilen şifreleme method  u olarak düşünebilirsin.-- >> ECDSA , RSA ... gibi


Devamında bunu okumanı öneririm.
https://medium.com/@muhammedkaralar/simetrik-ve-asimetrik-şifreleme-d57673284646#:~:text=Asimetrik%20şifreleme%20%2C%20simetrik%20şifrelemenin%20tersine,günümüzde%20oldukça%20yaygın%20olarak%20kullanılmaktadır.


ancak ECDSA da point işlemleri yapman için EllipticCurve Aritmetiğini kullanırsın.
EllipticCurve Aritmetiğide , Double ve Add üzerine kurulu bir point toplama aritmetiğidir. Nasıl çalıştığını önceki mesajımda bahsettim.


Ne yapmak istediğime gelince aslında girdiğim integer ile  nokta üretmek ve kontrol etmek istiyorum.Ör : 300 olsun

örneğin

Code:

inputInt = 300

i = inputInt % N

while True :
    i=i+1
    A = ((i + 1) % N)*G
    B = ((i * 2) % N)*G
    C = ((i + pow(2,i)) % N )*G
    
    
    if C.x % 35 == 5 :
        print (C,i)
    
    if B.x % 31 == 4 :
        print (B,i)
        
    if A.x % 27 == 17 :
        print (A,i)

[John_Ahmet]

Ne yapmak istediğime gelince aslında girdiğim integer ile  nokta üretmek ve kontrol etmek istiyorum.Ör : 300 olsun

Burada tam olarak ne yapıyoruz? Örneğin 300 senin public key'in ve merkeze uzaklığı tam 300 olan X ve Y koordinatlarını içeren bir point de senin private key'in mi oluyor? Peki imza nasıl doğrulanıyor? Ya da nasıl encode ve decode yapıyorsun?

Örneğin senin public keyin 300 olsun.
Benim ki de 500 olsun.

MPubKey = 300
JPubKey = 500

Örneğin A = 5 gibi bir bilgimiz olsun.

Ben sana A bilgisini şifreleyip göndermek istiyorum. Bunun için senin public key'in olan 300 ile şifrelemeliyim ki sen de sana ait 300 için X ve Y koordinatlarını içeren sahip olduğun private key ile bu bilgiyi deşifre edip gönderdiğim bilgiyi çözümleyip 5 bilgisini çözümleyip al. Sonra senin de bana B = 6 bilgisini göndermek istediğini farz edelim. Sen de bana benim public key imi kullanarak şifrele ve gönder. Bende de 500 public keyine ait X ve Y koordinatlarını içeren bir private key olması durumunda ben de bu şifreyi çözebilirim ki zaten benim public key im bu ilk olarak belirlenen bu x ve y koordinatlarını içeren private key den üretildiği için ben private keyim ile senin gönderdiğin bu 6 bilgisini gönderdiğin sayıdan oluşturabilmeliyim.


O halde Encode ve Decode işlemlerinin nasıl yapıldığını açıklayabilir misin?

C# için temel bir bir kod yazalım. Bu ECDSA keyini değil de basit bir merkeze uzaklık kodu olsun. ECDSA ile farkını anlatabilir misin? Ya da EllipticCurve bunu nasıl yapıyor?


Şimdi aşağıdaki kod simetrik mi yoksa asimetrik mi oldu? Bu basitlikte ve Point ve uzaklık yöntemiyle bu kodu asimetrik yapabilir miyiz? Zaten asimetrikse bu halde kalsın basit de olsa konuyu anlamak için örnek bir kod olabilir.

Code:

public class LLDSAKey 
{
     public double X;
     public double Y;

     public LLDSAKey(double X, double Y)
     {
        this.X = X;
        this.Y = Y;
     }

     public int GetPubKey() // Merkeze olan uzaklık (bir noktanın merkeze uzaklığı)
     {
        return Math.Floor(Math.Sqrt(this.X ^ 2 + this.Y ^ 2)); // Merkeze olan uzaklık için karelerinin toplamını al ve karekökünü hesaplayıp en yakın tam sayıya yuvarla...
     }
}

public class LLDSACrypto
{
    public int Encode(int message, int pubkey) 
    {
        return message * pubkey;
    }

    public int Decode(int cryptedMessage, LLDSAKey key) 
    {
       return cryptedMessage / Math.Floor(Math.Sqrt(key.X ^ 2 + key.Y ^ 2));
    }
}

[John_Ahmet]

Ayrıca dikkat edersen benim paylaştığım kodlarda literal bir değer yok, bu da anlaşılmasını kolaylaştırıyor fakat sen 5, 27, 31 gibi sayılar kullanıyorsun hiç bir şey anlamıyorum. Bu sayılar nereden geldi ve ne için oradalar?

[John_Ahmet]

RSA için Şadi hocanın videosunu izlemeni öneririm. http://bilgisayarkavramlari.com/2008/03/19/rsa/

Yıllar oldu izledim. Hatta 24-32 bitlik RSA kriptosu için kodlar yazıp public key den private key üreten kodlar da yazıp konunun temel mantığının anlaşılması için yayınladım.

Aslında sormak istediğim çok  detay var. Büyük harflerin noktayı küçük harflerin genelde çarpan olan sayıları ifade ettiğini anladım fakat örneğin xx ifadesi x * x ile aynı anlamamı geliyor yoksa xx ayrı bir değişken mi?

Ayrıca en baştaki soruna dönecek olursak ECdouble, ECadd ve ECmultiply methodlarını sormuştun. Hemen yazayım fakat burada Curve fonksiyonun secp256k1 olması ne anlama geliyor? Buradaki kodlara bakarak aradaki farkı anlatabilir misin?

Sana hemen ECdouble, ECadd ve ECmultiply işlevleri için bir C# kodu yazayım.

Programın çıktısı şöyle ana programa bakarsan bir curve fonksiyonu nasıl tanımlanır? Sonra bir point ile diğer bir point nasıl toplanır ve bir point ile bir skaler nasıl çarpılır aynı matematikte olduğu gibi bir hal aldı ve senin işini çok kolaylaştıracak.

Şimdi bana secp256k1 farkını anlatabilir misin? TODO yazığım yere yalnızca Main fonksiyonunu kullanarak prviate ve public key üretip gönderebilir misin?

O kısım nasıl oluyor?

Programın çıktısı şöyle;

Code:

Hello World!
Sample Add: (0,-4)
Sample Multiple: (-1,3)

Code:

using System;
using System.Text;
using System.Numerics;

namespace TestEllipticCurve
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            // TODO: generate private key and public key

            // Örnek CurveFp ve Point nasıl kullanılır?

            var curve = new CurveFp(5, 2, 3);

            var point = new Point(curve, 19, 23);

            var point2 = new Point(curve, 17, 11);

            var sampleAdd = point + point2;

            var skaler = 31;

            var sampleMultiple = point * skaler;

            Console.WriteLine("Sample Add: {0}", sampleAdd);
            Console.WriteLine("Sample Multiple: {0}", sampleMultiple);

            Console.ReadLine();
        }

        class Point
        {
            public static readonly Point INFINITY = new Point(null, default(BigInteger), default(BigInteger));
            public CurveFp Curve { get; private set; }
            public BigInteger X { get; private set; }
            public BigInteger Y { get; private set; }

            public Point(CurveFp curve, BigInteger x, BigInteger y)
            {
                this.Curve = curve;
                this.X = x;
                this.Y = y;
            }
            public Point Double()
            {
                if (this == INFINITY)
                    return INFINITY;

                BigInteger p = this.Curve.p;
                BigInteger a = this.Curve.a;
                BigInteger l = ((3 * this.X * this.X + a) * InverseMod(2 * this.Y, p)) % p;
                BigInteger x3 = (l * l - 2 * this.X) % p;
                BigInteger y3 = (l * (this.X - x3) - this.Y) % p;
                return new Point(this.Curve, x3, y3);
            }
            public override string ToString()
            {
                if (this == INFINITY)
                    return "infinity";
                return string.Format("({0},{1})", this.X, this.Y);
            }
            public static Point operator +(Point left, Point right)
            {
                if (right == INFINITY)
                    return left;
                if (left == INFINITY)
                    return right;
                if (left.X == right.X)
                {
                    if ((left.Y + right.Y) % left.Curve.p == 0)
                        return INFINITY;
                    else
                        return left.Double();
                }

                var p = left.Curve.p;
                var l = ((right.Y - left.Y) * InverseMod(right.X - left.X, p)) % p;
                var x3 = (l * l - left.X - right.X) % p;
                var y3 = (l * (left.X - x3) - left.Y) % p;
                return new Point(left.Curve, x3, y3);
            }
            public static Point operator *(Point left, BigInteger right)
            {
                var e = right;
                if (e == 0 || left == INFINITY)
                    return INFINITY;
                var e3 = 3 * e;
                var negativeLeft = new Point(left.Curve, left.X, -left.Y);
                var i = LeftmostBit(e3) / 2;
                var result = left;
                while (i > 1)
                {
                    result = result.Double();
                    if ((e3 & i) != 0 && (e & i) == 0)
                        result += left;
                    if ((e3 & i) == 0 && (e & i) != 0)
                        result += negativeLeft;
                    i /= 2;
                }
                return result;
            }

            private static BigInteger LeftmostBit(BigInteger x)
            {
                BigInteger result = 1;
                while (result <= x)
                    result = 2 * result;
                return result / 2;
            }
            private static BigInteger InverseMod(BigInteger a, BigInteger m)
            {
                while (a < 0) a += m;
                if (a < 0 || m <= a)
                    a = a % m;
                BigInteger c = a;
                BigInteger d = m;

                BigInteger uc = 1;
                BigInteger vc = 0;
                BigInteger ud = 0;
                BigInteger vd = 1;

                while (c != 0)
                {
                    BigInteger r;
                    //q, c, d = divmod( d, c ) + ( c, );
                    var q = BigInteger.DivRem(d, c, out r);
                    d = c;
                    c = r;

                    //uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc;
                    var uct = uc;
                    var vct = vc;
                    var udt = ud;
                    var vdt = vd;
                    uc = udt - q * uct;
                    vc = vdt - q * vct;
                    ud = uct;
                    vd = vct;
                }
                if (ud > 0) return ud;
                else return ud + m;
            }
        }

        class CurveFp
        {
            public BigInteger p { get; private set; }
            public BigInteger a { get; private set; }
            public BigInteger b { get; private set; }
            public CurveFp(BigInteger p, BigInteger a, BigInteger b)
            {
                this.p = p;
                this.a = a;
                this.b = b;
            }
        }
    }
}

[John_Ahmet]

Tekrar merhaba
anlattıklarım için python da örnek yazdım.

pythonda fastecdsa kütüphanesini kururyoruz

Merhaba!

Yazdıklarımı alıntının içerisine yazmışım. Neyse önemli değil. Python sanırım ne kadar hızlı bir kütüphane oluştursan da çok yavaş kalır. Bunun yerine C# önerebilirim. Sana çok hızlı uint256 kütüphanesi gösterebilirim. BigInteger yerine onu kullanırsın.

Paylaştığım kod hakkında ne düşünüyorsun? Orada public key ve private key nasıl üretilir farazi Base58Encode ve Base58Decode fonksiyonları olduğunu düşünüp örnek bir main fonksiyonu yazabilir misin?

private key de (2 ^ 256) - (2 ^ 32) olsun mesela... Gerçekten secp256k1 farkını anlamadım ve bilmiyorum. Sen biliyorsan lütfen bu kısmı anlat ki net şekilde anlamış olalım.

Code:

using System;
using System.Text;
using System.Numerics;

namespace TestEllipticCurve
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            // TODO: generate private key and public key

            // Örnek CurveFp ve Point nasıl kullanılır?

            var curve = new CurveFp(5, 2, 3);

            var point = new Point(curve, 19, 23);

            var point2 = new Point(curve, 17, 11);

            var sampleAdd = point + point2;

            var skaler = 31;

            var sampleMultiple = point * skaler;

            Console.WriteLine("Sample Add: {0}", sampleAdd);
            Console.WriteLine("Sample Multiple: {0}", sampleMultiple);

            Console.ReadLine();
        }

        class Point
        {
            public static readonly Point INFINITY = new Point(null, default(BigInteger), default(BigInteger));
            public CurveFp Curve { get; private set; }
            public BigInteger X { get; private set; }
            public BigInteger Y { get; private set; }

            public Point(CurveFp curve, BigInteger x, BigInteger y)
            {
                this.Curve = curve;
                this.X = x;
                this.Y = y;
            }
            public Point Double()
            {
                if (this == INFINITY)
                    return INFINITY;

                BigInteger p = this.Curve.p;
                BigInteger a = this.Curve.a;
                BigInteger l = ((3 * this.X * this.X + a) * InverseMod(2 * this.Y, p)) % p;
                BigInteger x3 = (l * l - 2 * this.X) % p;
                BigInteger y3 = (l * (this.X - x3) - this.Y) % p;
                return new Point(this.Curve, x3, y3);
            }
            public override string ToString()
            {
                if (this == INFINITY)
                    return "infinity";
                return string.Format("({0},{1})", this.X, this.Y);
            }
            public static Point operator +(Point left, Point right)
            {
                if (right == INFINITY)
                    return left;
                if (left == INFINITY)
                    return right;
                if (left.X == right.X)
                {
                    if ((left.Y + right.Y) % left.Curve.p == 0)
                        return INFINITY;
                    else
                        return left.Double();
                }

                var p = left.Curve.p;
                var l = ((right.Y - left.Y) * InverseMod(right.X - left.X, p)) % p;
                var x3 = (l * l - left.X - right.X) % p;
                var y3 = (l * (left.X - x3) - left.Y) % p;
                return new Point(left.Curve, x3, y3);
            }
            public static Point operator *(Point left, BigInteger right)
            {
                var e = right;
                if (e == 0 || left == INFINITY)
                    return INFINITY;
                var e3 = 3 * e;
                var negativeLeft = new Point(left.Curve, left.X, -left.Y);
                var i = LeftmostBit(e3) / 2;
                var result = left;
                while (i > 1)
                {
                    result = result.Double();
                    if ((e3 & i) != 0 && (e & i) == 0)
                        result += left;
                    if ((e3 & i) == 0 && (e & i) != 0)
                        result += negativeLeft;
                    i /= 2;
                }
                return result;
            }

            private static BigInteger LeftmostBit(BigInteger x)
            {
                BigInteger result = 1;
                while (result <= x)
                    result = 2 * result;
                return result / 2;
            }
            private static BigInteger InverseMod(BigInteger a, BigInteger m)
            {
                while (a < 0) a += m;
                if (a < 0 || m <= a)
                    a = a % m;
                BigInteger c = a;
                BigInteger d = m;

                BigInteger uc = 1;
                BigInteger vc = 0;
                BigInteger ud = 0;
                BigInteger vd = 1;

                while (c != 0)
                {
                    BigInteger r;
                    //q, c, d = divmod( d, c ) + ( c, );
                    var q = BigInteger.DivRem(d, c, out r);
                    d = c;
                    c = r;

                    //uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc;
                    var uct = uc;
                    var vct = vc;
                    var udt = ud;
                    var vdt = vd;
                    uc = udt - q * uct;
                    vc = vdt - q * vct;
                    ud = uct;
                    vd = vct;
                }
                if (ud > 0) return ud;
                else return ud + m;
            }
        }

        class CurveFp
        {
            public BigInteger p { get; private set; }
            public BigInteger a { get; private set; }
            public BigInteger b { get; private set; }
            public CurveFp(BigInteger p, BigInteger a, BigInteger b)
            {
                this.p = p;
                this.a = a;
                this.b = b;
            }
        }
    }
}

[mamuu]

RSA için Şadi hocanın videosunu izlemeni öneririm. http://bilgisayarkavramlari.com/2008/03/19/rsa/

Yıllar oldu izledim. Hatta 24-32 bitlik RSA kriptosu için kodlar yazıp public key den private key üreten kodlar da yazıp konunun temel mantığının anlaşılması için yayınladım.

Aslında sormak istediğim çok  detay var. Büyük harflerin noktayı küçük harflerin genelde çarpan olan sayıları ifade ettiğini anladım fakat örneğin xx ifadesi x * x ile aynı anlamamı geliyor yoksa xx ayrı bir değişken mi?

Ayrıca en baştaki soruna dönecek olursak ECdouble, ECadd ve ECmultiply methodlarını sormuştun. Hemen yazayım fakat burada Curve fonksiyonun secp256k1 olması ne anlama geliyor? Buradaki kodlara bakarak aradaki farkı anlatabilir misin?

Sana hemen ECdouble, ECadd ve ECmultiply işlevleri için bir C# kodu yazayım.

Programın çıktısı şöyle ana programa bakarsan bir curve fonksiyonu nasıl tanımlanır? Sonra bir point ile diğer bir point nasıl toplanır ve bir point ile bir skaler nasıl çarpılır aynı matematikte olduğu gibi bir hal aldı ve senin işini çok kolaylaştıracak.

Şimdi bana secp256k1 farkını anlatabilir misin? TODO yazığım yere yalnızca Main fonksiyonunu kullanarak prviate ve public key üretip gönderebilir misin?

O kısım nasıl oluyor?

Programın çıktısı şöyle;

Code:

Hello World!
Sample Add: (0,-4)
Sample Multiple: (-1,3)

Code:

using System;
using System.Text;
using System.Numerics;

namespace TestEllipticCurve
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            // TODO: generate private key and public key

            // Örnek CurveFp ve Point nasıl kullanılır?

            var curve = new CurveFp(5, 2, 3);

            var point = new Point(curve, 19, 23);

            var point2 = new Point(curve, 17, 11);

            var sampleAdd = point + point2;

            var skaler = 31;

            var sampleMultiple = point * skaler;

            Console.WriteLine("Sample Add: {0}", sampleAdd);
            Console.WriteLine("Sample Multiple: {0}", sampleMultiple);

            Console.ReadLine();
        }

        class Point
        {
            public static readonly Point INFINITY = new Point(null, default(BigInteger), default(BigInteger));
            public CurveFp Curve { get; private set; }
            public BigInteger X { get; private set; }
            public BigInteger Y { get; private set; }

            public Point(CurveFp curve, BigInteger x, BigInteger y)
            {
                this.Curve = curve;
                this.X = x;
                this.Y = y;
            }
            public Point Double()
            {
                if (this == INFINITY)
                    return INFINITY;

                BigInteger p = this.Curve.p;
                BigInteger a = this.Curve.a;
                BigInteger l = ((3 * this.X * this.X + a) * InverseMod(2 * this.Y, p)) % p;
                BigInteger x3 = (l * l - 2 * this.X) % p;
                BigInteger y3 = (l * (this.X - x3) - this.Y) % p;
                return new Point(this.Curve, x3, y3);
            }
            public override string ToString()
            {
                if (this == INFINITY)
                    return "infinity";
                return string.Format("({0},{1})", this.X, this.Y);
            }
            public static Point operator +(Point left, Point right)
            {
                if (right == INFINITY)
                    return left;
                if (left == INFINITY)
                    return right;
                if (left.X == right.X)
                {
                    if ((left.Y + right.Y) % left.Curve.p == 0)
                        return INFINITY;
                    else
                        return left.Double();
                }

                var p = left.Curve.p;
                var l = ((right.Y - left.Y) * InverseMod(right.X - left.X, p)) % p;
                var x3 = (l * l - left.X - right.X) % p;
                var y3 = (l * (left.X - x3) - left.Y) % p;
                return new Point(left.Curve, x3, y3);
            }
            public static Point operator *(Point left, BigInteger right)
            {
                var e = right;
                if (e == 0 || left == INFINITY)
                    return INFINITY;
                var e3 = 3 * e;
                var negativeLeft = new Point(left.Curve, left.X, -left.Y);
                var i = LeftmostBit(e3) / 2;
                var result = left;
                while (i > 1)
                {
                    result = result.Double();
                    if ((e3 & i) != 0 && (e & i) == 0)
                        result += left;
                    if ((e3 & i) == 0 && (e & i) != 0)
                        result += negativeLeft;
                    i /= 2;
                }
                return result;
            }

            private static BigInteger LeftmostBit(BigInteger x)
            {
                BigInteger result = 1;
                while (result <= x)
                    result = 2 * result;
                return result / 2;
            }
            private static BigInteger InverseMod(BigInteger a, BigInteger m)
            {
                while (a < 0) a += m;
                if (a < 0 || m <= a)
                    a = a % m;
                BigInteger c = a;
                BigInteger d = m;

                BigInteger uc = 1;
                BigInteger vc = 0;
                BigInteger ud = 0;
                BigInteger vd = 1;

                while (c != 0)
                {
                    BigInteger r;
                    //q, c, d = divmod( d, c ) + ( c, );
                    var q = BigInteger.DivRem(d, c, out r);
                    d = c;
                    c = r;

                    //uc, vc, ud, vd = ud - q*uc, vd - q*vc, uc, vc;
                    var uct = uc;
                    var vct = vc;
                    var udt = ud;
                    var vdt = vd;
                    uc = udt - q * uct;
                    vc = vdt - q * vct;
                    ud = uct;
                    vd = vct;
                }
                if (ud > 0) return ud;
                else return ud + m;
            }
        }

        class CurveFp
        {
            public BigInteger p { get; private set; }
            public BigInteger a { get; private set; }
            public BigInteger b { get; private set; }
            public CurveFp(BigInteger p, BigInteger a, BigInteger b)
            {
                this.p = p;
                this.a = a;
                this.b = b;
            }
        }
    }
}

merhaba C# ta da olsa baska bir yerde de

Point1 + Point1  sonucu  "return PointNew"  için dönmesi EliptikEğriAritmetiğinde -> ECdobuble  kullanman gerekir

Point1 + Point2  sonucunu return etmen için EliptikEğriAritmetiğinde -> ECadd kullanman gerekir

Peki Point Nasıl olusacak ?

Onuda GeneratorPoint olarak Gx ve Gy ile üstteki python kodunda yazdım.

[John_Ahmet]

merhaba C# ta da olsa baska bir yerde de

Point1 + Point1  sonucu  "return PointNew"  için dönmesi EliptikEğriAritmetiğinde -> ECdobuble  kullanman gerekir

Point1 + Point2  sonucunu return etmen için EliptikEğriAritmetiğinde -> ECadd kullanman gerekir

Peki Point Nasıl olusacak ?

Onuda GeneratorPoint olarak Gx ve Gy ile üstteki python kodunda yazdım.

Sanırım gözünden kaçırmışsın yalnızca main fonksiyonda ilgili ECdouble işlevine de örnek gösterip hemen paylaşayım. secp256k1 farkını anlatabilir misin?

Code:

static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            // TODO: generate private key and public key

            // Örnek CurveFp ve Point nasıl kullanılır?

            var curve = new CurveFp(5, 2, 3);

            var point = new Point(curve, 19, 23);

            var point2 = new Point(curve, 17, 11);

            var sampleAdd = point + point2;

            var skaler = 31;

            var sampleMultiple = point * skaler;

            var doublePoint = point.Double();

            Console.WriteLine("Sample Add: {0}", sampleAdd);
            Console.WriteLine("Sample Multiple: {0}", sampleMultiple);
            Console.WriteLine("Sample Double: {0}", doublePoint);

            Console.ReadLine();
        }

[John_Ahmet]

Ya da şöyle yapalım. Ben benim verdiğim kodlara göre C# ile kodu yazayım fakat oradaki p, a, b sayıları secp256k1 Curve fonksiyonunda hangi sabitleri kullanıyor. Bunu secp256k1 için nasıl modifiye etmek gerekiyor?

Sanırım benim için en önemli kısım burası... Senin kodunu C# ile düzenleyip hazırladım. Burada secp256k1 için hangi sabitleri vermem gerekiyordu ya da curve G H ve N olarak ifade edilen curve sabitleri neler? Bunlar sabit mi yoksa nasıl belirleniyor?

Ayrıca Gx ve Gy ve x arasında bir bağıntı var mı yoksa random mu seçiliyor? Gx ve Gy için birbirlerine yakın aralarında asal iki sayı seçmek gerekiyorsa bu benim için sorun olmaz. Fermat'ın Little teoremiyle kolaylıkla çok büyük sayılar için seçebilirim. ModPow kullanarak fakat x ile aralarında bir bağıntı varsa onu öğrenmek isterim.

Code:

static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            BigInteger p = BigInteger.Parse("0FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", NumberStyles.HexNumber);
            BigInteger a = BigInteger.Zero; 
            BigInteger b = (BigInteger)7;


            var secp256k1 = new CurveFp(p, a, b);

            var G = new Point(secp256k1, 
                BigInteger.Parse("55066263022277343669578718895168534326250603453777594175500187360389116729240"), 
                BigInteger.Parse("32670510020758816978083085130507043184471273380659243275938904335757337482424"));

            var x = BigInteger.Parse("8723493475893459873498759834758934759837458973497593847598347598734985798982374987234");

            var PrivateKey = x;
            var GeneratorPoint = G;

            var PublicPoint = GeneratorPoint * PrivateKey;

            var xx = PublicPoint.X.ToString("X");

            var xy = PublicPoint.Y.ToString("X");

            var UncompressedPublicKey = "04" + xx + xy;

            var CompressedPublicKey = "";

            if (PublicPoint.Y % 2 == 0)
                CompressedPublicKey = "02" + xx;

            if (PublicPoint.Y % 2 == 1)
                CompressedPublicKey = "03" + xx;

            Console.WriteLine("Uncompressed Public Key: {0}", UncompressedPublicKey);
            Console.WriteLine("Compressed Public Key: {0}", CompressedPublicKey);

            Console.ReadLine();
        }