I am trying to check if some compressed public key corresponds to an elliptic curve equation (secp256k1). As far as I know it should be valid once the following equation is fulfill y^2 = x^3 + ax + b or y^2 % p = (x^3 +ax +b) % p. Supposing that I have the following key:
pubkey = 027d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef
I am able to extract x-coordinate (do to it in this case I strip 02), in theory to calculate y without sqrt operation (due to losing precision) we can do in this case: y = (x^exp) % p, where exp = (p+1)/4 based on https://crypto.stackexchange.com/questions/101142/proof-that-user-compressed-public-key-corresponds-the-curve-equation-secp256k1
Now based on how I calculate y:
bmp::uint1024_t const y = bmp::powm(x, pp, p);
//or
bmp::uint1024_t const yy = (x^pp) % p;
I have other results, which impact later computations, generally the second example gives correct final result, but it seems, that for some reasons it doesn't work as it should... for power operation it gives the following result:
bmp::pow(x, pp): 5668936922878426254536308284732873549115769122415677675761389126416312181579**1**
x^pp: 5668936922878426254536308284732873549115769122415677675761389126416312181579**0**
Even in python3 code for x^pp I have the same result as the second one, so should I use something other than boost::multiprecision ? or do these computation in other way ?
Code can be test here: https://wandbox.org/permlink/JQ3ipCq6yQjptUet
#include <numeric>
#include <iostream>
#include <string>
#include <boost/multiprecision/cpp_int.hpp>
namespace bmp = boost::multiprecision;
bool verify(std::string const& address, std::size_t const stripped_prefix_size)
{
auto is_address_correct{false};
bmp::uint1024_t const p = bmp::uint1024_t{"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"} % 4;//3 % 4;//{"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"};
bmp::uint1024_t const a{"0x0000000000000000000000000000000000000000000000000000000000000000"};
bmp::uint1024_t const b{"0x0000000000000000000000000000000000000000000000000000000000000007"};
bmp::uint1024_t x{std::string{"0x"} + address.substr(2, address.size() - stripped_prefix_size)};
auto const right = (bmp::pow(x, 3) + (a * x) + b) % p;
//bmp::uint1024_t const y = bmp::sqrt(right) % p;
bmp::uint1024_t pp = (p + 1) / 4;
bmp::uint1024_t const y = bmp::powm(x, pp, p);
bmp::uint1024_t const yy = (x^pp) % p;//bmp::powm(x, pp, p);
auto const left = bmp::powm(y, 2, p);
auto const left2 = bmp::powm(yy, 2, p);
std::cout << "x: " << x << std::endl;
std::cout << "y pow pp: " << bmp::pow(x, pp.convert_to<int>()) << std::endl;
std::cout << " y^pp: " << bmp::uint1024_t{x^pp} << std::endl;
std::cout << "yy mod p: " << yy << std::endl;
std::cout << " y mod p: " << y << std::endl;
std::cout << "yy: " << yy << std::endl;
std::cout << "right: " << right << std::endl;
std::cout << " left: " << left << std::endl;
std::cout << "left2: " << left2 << std::endl;
is_address_correct = (left == right);
return is_address_correct;
}
int main()
{
auto const res = verify("027d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef", 2);
std::cout << "\nis valid: " << res << std::endl;
return 0;
}
Output:
x: 56689369228784262545363082847328735491157691224156776757613891264163121815791
y pow pp: 56689369228784262545363082847328735491157691224156776757613891264163121815791
y^pp: 56689369228784262545363082847328735491157691224156776757613891264163121815790
yy mod p: 2
y mod p: 0
yy: 2
right: 1
left: 0
left2: 1
is valid: 0
For the compressed key
027d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef
the uncompressed representation is
047d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60effbb6217403fe57ff1b2f84f74086b413c7682027bd6ddde4538c340ba1a25638
i.e.
x = 0x7d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef = 56689369228784262545363082847328735491157691224156776757613891264163121815791
y = 0xfbb6217403fe57ff1b2f84f74086b413c7682027bd6ddde4538c340ba1a25638 = 113852322045593354727100676608445520152048120867463853258291211042951302108728
This is also confirmed by the following code using the Boost library:
bool verify(std::string const& address, std::size_t const stripped_prefix_size)
{
auto is_address_correct{false};
bmp::uint1024_t const p = bmp::uint1024_t{"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"};
bmp::uint1024_t const a{"0x0000000000000000000000000000000000000000000000000000000000000000"};
bmp::uint1024_t const b{"0x0000000000000000000000000000000000000000000000000000000000000007"};
bmp::uint1024_t x{std::string{"0x"} + address.substr(2, address.size() - stripped_prefix_size)};
bmp::uint1024_t right = (bmp::powm(x, 3, p) + (a * x) + b) % p;
bmp::uint1024_t y = bmp::powm(right, (p + 1) / 4, p); // even, i.e. equals the searched y value because of leading 0x02 byte
bmp::uint1024_t left = bmp::powm(y, 2, p);
std::cout << "x: " << x << std::endl; // x: 56689369228784262545363082847328735491157691224156776757613891264163121815791
std::cout << "y: " << y << std::endl; // y: 113852322045593354727100676608445520152048120867463853258291211042951302108728
std::cout << "right: " << right << std::endl; // right: 33769945388650438579771708095049232540048570303667364755388658443270938208149
std::cout << "left: " << left << std::endl; // left: 33769945388650438579771708095049232540048570303667364755388658443270938208149
is_address_correct = (left == right);
return is_address_correct;
}
The code contains the following fixes/considerations:
y, not x but right must be applied.+y.p must not be taken modulo 4 (see comment by President James K. Polk). The congruence of the modulus to 3 modulo 4 is only relevant for finding the correct solution path. A more detailed explanation can be found here.