I implemented a solution using the Extended Euclidien algorithm,
I have the right results with small numbers but not with large numbers
Here is my solution:
I can add any points whitout problems, but with large numbers,
using
http://www.royalforkblog.com/2014/09/04/ecc/, I get
WRONG
privKeyDec: 23695310554196047209792918797392416191148132060917476866274911959533140016553
privKeyHex: 3463120c802f8bd7972aa996083fec011f387a61e55b7b507b9c68d2bc9f7da9
public key = privKeyDec * G:
pubKeyDec_x = 60306455975408622297239001036599486600287350729488590738949419698511411824492
pubKeyDec_y = 105340305216767447115881521734850141742815850841650003460985843120741726629417
pubKeyHex_x = 85543e964d2c63bb7caf42b8dedfa6b3e5a0d99bce28509472654c696a6a476c
pubKeyHex_y = e8e47ff840d46305bb1dc2ff173c14cefa0f7dc6a0d26fb10de264c243a52e29
The results on the web page are:
OK (?)
pubKeyDec_x = 39874617776630327813190058413816560767734954098998567043224950074533143699292
pubKeyDec_y = 83115399533222200534442050051826386603242609920409430626876080623730665355556
or in hexa:
pubKeyHex_x = 58283bdf22456fffaa0b5f56abd7ad271815d31e44272c0460398540758cdf5c
pubKeyHex_y = b7c1a627a79a9000235382c650f23b6a7ebcd18529667dd674185d295e367924
I also have a wrong result with (Antonopoulos)
http://chimera.labs.oreilly.com/books/1234000001802/ch04.html#public_key_derivationCan you see the problem in my code (below) or at least can somebody give me
the result of the addition of 2 points: 1 * G + 1 * G with Bitcoin parameters, then I will be able
to track my code because now I have the result of a very large number of additions.
// g++ ellipticCurve.cpp -lgmpxx -lgmp -std=c++11
#include <stdio.h>
#include <bitset>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <tuple>
#include <gmpxx.h>
using namespace std;
typedef pair<mpz_class, mpz_class> point, fraction;
typedef pair<mpz_class, mpz_class> fraction;
fraction computeSlope (point, point);
point addPoints (point, point);
string formatPoint (point);
string char2bin (string);
point doubledPoints (point);
tuple<mpz_class, mpz_class, mpz_class> 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<mpz_class, mpz_class, mpz_class> 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;
}
