# Proof that user compressed public key corresponds the curve equation (secp256k1)

I am trying to check if some compressed public key corresponds to an elliptic curve equation (secp256r1). 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), so in theory I should be able to calculate it in the following way (as below), but id doesn't work as expected. I don't know if it is related to round during sqrt operation or not, does anyone have any idea what I am doing wrong ?

#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)
{
bmp::uint1024_t const p{"0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"};
bmp::uint1024_t const a{"0x0000000000000000000000000000000000000000000000000000000000000000"};
bmp::uint1024_t const b{"0x0000000000000000000000000000000000000000000000000000000000000007"};

{
std::cout << "############# with MODULO ################" << std::endl;

auto const right = (bmp::pow(x, 3) + (a * x) + b) % p;
bmp::uint1024_t const y = bmp::sqrt(right) % p;
auto const left = bmp::pow(y, 2);

std::cout << "x: " << x << std::endl;
std::cout << "y: " << y << std::endl;
std::cout << "right: " << right << std::endl;
std::cout << " left: " << left << std::endl;
}

{
std::cout << std::endl << "############# without MODULO ################" << std::endl;
auto const right = (bmp::pow(x, 3) + (a * x) + b);
bmp::uint1024_t const y = bmp::sqrt(right);
auto const left = bmp::pow(y, 2);

std::cout << "x: " << x << std::endl;
std::cout << "y: " << y << std::endl;
std::cout << "right: " << right << std::endl;
std::cout << " left: " << left << std::endl;
}

}

int main()
{
auto const res = verify("027d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef", 2);
std::cout << "\nis valid: " << res << std::endl;

return 0;
}


Program output:

############# with MODULO ################ x: 56689369228784262545363082847328735491157691224156776757613891264163121815791 y: 183766007163050801754608903653841862618 right: 33769945388650438579771708095049232540048570303667364755388658443270938208149 left: 33769945388650438579771708095049232539920934980046904834800557419775585813924

############# without MODULO ################ x: 56689369228784262545363082847328735491157691224156776757613891264163121815791 y: 13497472057468355938572038677065615761097144061311551195730691629950308697806550176813818086835150901176637717416722 right: 182181751942139053636431558335628486248480898622843767538654320228825581987479906778155585847291878917907922072895611492267301384350099726325450762811050934436031042086671820982050911377912589308184841627685631347496623032412958678 left: 182181751942139053636431558335628486248480898622843767538654320228825581987479906778155585847291878917907922072895585240175884415988084178980651571231083458654830397520853615320131308334828726829265223601702424747233734581005225284

is valid: 0

You can compute it as $$y = x^{(p+1)/4} \bmod p$$ (which works because $$p$$ is prime and $$p \equiv 3 \pmod 4$$); I haven't worked with this specific bignum library, so I can't say how to express it; it shouldn't be that difficult.
• Another more mundane problem is that the question mentions secp256r1 but the code is using $p$ for secp256k1.
• 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f mod 4 = 3, and so it is the recommended value. That was merely a comment that $x^{(p+1)/4} \bmod p$ doesn't always work, but only for some values of $p$ and the prime used in sec256k1 (and the prime used in sec256r1) 'just happen' to fall in that category (scare quotes because the designers of those two curves knew of this trick and so deliberately selected primes that made it work) Jul 22 at 16:18