How to find a point of an elliptic curve in crypto++ (with given x)? Or how to compute a root in finite field? Or root of Polynomial Ring?

Question

Is there any way in crypto++ to check if an EC contains a point with a given x-coordinate?

One solution would be solving the EC polynomial for given x. One side of the equation already done in code. I 'just' need to compute the root of it (over a finite field)

//clang++ -o ectest ectest.cpp -lcryptopp
#include "cryptopp/eccrypto.h"
#include "cryptopp/oids.h"

int main(int argc, char* argv[]) {
    using namespace CryptoPP;
    typedef DL_GroupParameters_EC<ECP> GroupParameters;
    typedef DL_GroupParameters_EC<ECP>::Element Element;
    
    GroupParameters group;
    group.Initialize(ASN1::secp256k1());
        
    //I want to check if the EC has a point with x-cooridnate x=13
    Integer x = 13;
    
    Integer ecmod = group.GetCurve().GetField().GetModulus();
    ModularArithmetic ma = ModularArithmetic(ecmod);

    //the following equation need to be solved:
    //y^2 = x^3 + Ax + B \mod ecmod
    Integer x3 = ma.Multiply(x,x);
    x3 = ma.Multiply(x3,x);
    Integer xa = ma.Multiply(group.GetCurve().GetA(),x);
    Integer xb = group.GetCurve().GetB();
    Integer sr = ma.Add(x3,xa);
    sr = ma.Add(sr,xb);

    //y^2 = sr
    //how to compute the root out of sr?
    //or is there any other way to check if the EC contains a point with x?
}

Answer 1

Yes, you can. The library has support for compression and decompression of points. During the decompression, the library must find y if it can.

The header of the DecodePoint

bool ECP::DecodePoint(ECP::Point &P, BufferedTransformation &bt, size_t encodedPointLen) const

The error returned with

if (Jacobi(P.y, p) !=1)
    return false;

You can construct your point as compressed, or better use this part from DecodePoint; just add the below lines into your code;

//include these
#include "cryptopp/nbtheory.h"
#include <iostream>

using namespace CryptoPP;

Integer getSquareRoot( Integer &y, Integer &mod) {

   if (Jacobi(y, mod) !=1)
        return -1;

    return y  = ModularSquareRoot(y, mod);
     
}

    // In the main
    //After sr = ma.Add(sr,xb);

    Integer y  = getSquareRoot(sr, ecmod);
    if ( y != -1 ) {
        std::cout << IntToString<Integer>(y) << std::endl;
    } else {         
        std::cout << IntToString<Integer>(sr);
        std::cout << " has not square root to " << ecmod << std::endl;
    }

outputs

20267456347483554069520440766283645831919514026818877192810320909941447705364

---

Note: if you print with

std::cout << y << std::endl;

There will be a dot in the end. The library warns about this.

/// The output includes the suffix \a h (for hex), \a . (\a dot, for dec)
/// and \a o (for octal). There is currently no way to suppress the suffix.
/// \details If you want to print an Integer without the suffix or using an arbitrary base, then
///   use IntToString<Integer>().