Topic: Adding points on an Elliptic curve (Read 1844 times)

WRONG
privKeyDec: 23695310554196047209792918797392416191148132060917476866274911959533140016553
privKeyHex: 3463120c802f8bd7972aa996083fec011f387a61e55b7b507b9c68d2bc9f7da9

public key = privKeyDec * G:
pubKeyDec_x = 60306455975408622297239001036599486600287350729488590738949419698511411824492
pubKeyDec_y = 105340305216767447115881521734850141742815850841650003460985843120741726629417

pubKeyHex_x = 85543e964d2c63bb7caf42b8dedfa6b3e5a0d99bce28509472654c696a6a476c
pubKeyHex_y = e8e47ff840d46305bb1dc2ff173c14cefa0f7dc6a0d26fb10de264c243a52e29

OK (?)
pubKeyDec_x = 39874617776630327813190058413816560767734954098998567043224950074533143699292
pubKeyDec_y = 83115399533222200534442050051826386603242609920409430626876080623730665355556
or in hexa:
pubKeyHex_x = 58283bdf22456fffaa0b5f56abd7ad271815d31e44272c0460398540758cdf5c
pubKeyHex_y = b7c1a627a79a9000235382c650f23b6a7ebcd18529667dd674185d295e367924

// g++ ellipticCurve.cpp -lgmpxx -lgmp -std=c++11
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef pair point, fraction;
typedef pair fraction;

fraction computeSlope (point, point);
point addPoints (point, point);
string formatPoint (point);
string char2bin (string);
point doubledPoints (point);
tuple ExtGCD (mpz_class, mpz_class);
mpz_class frac2int (point);
string bigNumber2strHex (mpz_class);
mpz_class hexa2BigNum (const string);


// uncomment one of those 2 groups of 4 parameters
// parameters for Bitcoin
mpz_class baseEC("115792089237316195423570985008687907852837564279074904382605163141518161494337");
mpz_class G_x("55066263022277343669578718895168534326250603453777594175500187360389116729240");
mpz_class G_y("32670510020758816978083085130507043184471273380659243275938904335757337482424");
int a = 0;    // EC: y^2 = x^3 + 7

// parameters for http://www.royalforkblog.com/2014/09/04/ecc/
// mpz_class baseEC("29"); // change privKeyHex < 29 (0x1D)
// mpz_class G_x("0");
// mpz_class G_y("2");
// int a = -3;    // EC: y^2 = x^3 -3 x + 4

point pointG(G_x, G_y);
point pointP(0, 0);


main () {	
	// uncomment one of those 3 groups of 2 parameters 

	// from: http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#public_key_derivation (Antonopoulos)
// 	string privKeyHex     = "1E99423A4ED27608A15A2616A2B0E9E52CED330AC530EDCC32C8FFC6A526AEDD";
// 	mpz_class privKeyDec  = hexa2BigNum(privKeyHex);
	
	// from: http://www.royalforkblog.com/2014/09/04/ecc/    (big numbers)
	mpz_class privKeyDec("23695310554196047209792918797392416191148132060917476866274911959533140016553");
	string privKeyHex = bigNumber2strHex(privKeyDec);
 	
	// from: http://www.royalforkblog.com/2014/09/04/ecc/    (small numbers)
// 	mpz_class privKeyDec("26");
// 	string privKeyHex = bigNumber2strHex(privKeyDec);   // = "1A"
	
	// add and double algorithm : privKey = pubKey * G 
	mpz_class totG = 0; // keep track of "x2" and "+1" operations
	for (size_t i = 0; i < privKeyHex.size(); i++) {
		string theCharBin = char2bin(privKeyHex.substr (i,1));		
		for (size_t j = 0; j <= 3; j++) {
			totG += totG;  // double (x2)
			pointP = doubledPoints(pointP);
			
			if (theCharBin[j] == '1') {
				totG += 1;  // add (+1)
				pointP = addPoints(pointG, pointP);
			}
		}
	}
	cout << endl ;
	//cout << "totG should be = privKeyDec:" << endl;;
	//cout << "totG =      " << totG << endl;
	cout << "privKeyDec: " << privKeyDec << endl;
	cout << "privKeyHex: " << privKeyHex << endl;
	cout << endl << "public key = privKeyDec * G:" << endl;
	cout << "pubKeyDec_x = " << pointP.first << endl;
	cout << "pubKeyDec_y = " << pointP.second << endl << endl;
	cout << "pubKeyHex_x = " << bigNumber2strHex(pointP.first) << endl;
	cout << "pubKeyHex_y = " << bigNumber2strHex(pointP.second) << endl << endl;
}


point addPoints(point point1, point point2) {

	point point3, x3_frac, y3_frac;
	
	if (point1.first == 0 && point1.second == 0) {
		return point2;
	}
	if (point2.first == 0 && point2.second == 0) {
		return point1;
	}
	
	fraction slope = computeSlope(point1, point2);
	
	x3_frac.second = slope.second * slope.second;
	x3_frac.first  = slope.first * slope.first - ((point1.first + point2.first) * x3_frac.second);
	
	x3_frac.first = x3_frac.first % baseEC;
	x3_frac.first = (x3_frac.first < 0) ? x3_frac.first + baseEC : x3_frac.first;
	
	point3.first  = frac2int(x3_frac);
		
	y3_frac.first = slope.first * (point1.first - point3.first) - point1.second * slope.second;
	y3_frac.second = slope.second;
	
	y3_frac.first = y3_frac.first % baseEC;
	y3_frac.first = (y3_frac.first < 0) ? y3_frac.first + baseEC : y3_frac.first;
	
	point3.second = frac2int(y3_frac);
	
	return point3;
}

mpz_class frac2int(point theFrac) {
	mpz_class u;
	tie(ignore, u, ignore) = ExtGCD(theFrac.second, baseEC);	
	u = (u < 0) ? u + baseEC : u;
	return (u * theFrac.first) % baseEC;
}

point doubledPoints(point point1) {
	return addPoints(point1, point1);
}

fraction computeSlope(point pointA, point pointB) {
	// EC: y^2 = x^3 + 7      // Bitcoin
	// EC: y^2 = x^3 -3x + 4  // royalforkblog.com
	fraction slope;
	if (pointA == pointB) {
		slope.first  = 3 * pointA.first * pointA.first + a;
		slope.second = 2 * pointA.second;
	}
	else {
		slope.first  = pointB.second - pointA.second; // delta y
		slope.second = pointB.first - pointA.first;   // delta x
	}
	return slope;
}

string formatPoint(point thePoint) {
    ostringstream outs;
    outs << "(" << thePoint.first << ", " << thePoint.second << ")";
   return outs.str( );
}

string char2bin (string theChar) {
	int value;
	
 	istringstream ost(theChar);
 	ost >> hex >> value;
 
 	bitset<4> bits(value);
 	string binaryString (bits.to_string() );
	
	return binaryString;	
}

tuple ExtGCD (mpz_class a, mpz_class b) {
    if (a == 0)
        return make_tuple(b, 0, 1);
    mpz_class g, y, x;
    tie(g, y, x) = ExtGCD(b % a, a);
    return make_tuple(g, x-(b/a)*y, y);
}

string bigNumber2strHex (mpz_class theBigNumber) {
	ostringstream stream;
	stream << hex << theBigNumber;
	return stream.str();
}

mpz_class hexa2BigNum (const string myString)
{	
	mpz_class x;   
	stringstream stream;
	stream << hex << myString;
	stream >> x;
	return x;
}