0
$\begingroup$

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 ?

https://wandbox.org/permlink/uQltlj9Mu6rVPvym

#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{"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)};

    {
        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;
        is_address_correct = (left == right);
    }

    {
        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;
        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;
}

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

bmp::uint1024_t const y = bmp::sqrt(right) % p;

That's your problem; you want a modular square-root here, which is not an integer square root followed by a modulo operation.

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Another more mundane problem is that the question mentions secp256r1 but the code is using $p$ for secp256k1. $\endgroup$
    – fgrieu ♦
    Commented Jul 22, 2022 at 13:58
  • $\begingroup$ Why p should equal 3 mod 4 ? and not the recommended value 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f ? $\endgroup$
    – bladzio
    Commented Jul 22, 2022 at 15:12
  • $\begingroup$ 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) $\endgroup$
    – poncho
    Commented Jul 22, 2022 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.