c++ - 如何在crypto++中找到椭圆曲线的一个点(给定x)？或者如何计算有限域中的根？还是多项式环的根？

Question

在crypto++中有什么方法可以检查EC是否包含具有给定x坐标的点？
一种解决方案是求解给定 x 的 EC 多项式。等式的一侧已经在代码中完成。我“只”需要计算它的根(在有限域上)

//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

是的你可以。该库支持点的压缩和解压缩。在解压过程中，如果可以，库必须找到y。
DecodePoint 的头部

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

错误返回

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

您可以将您的点构造为压缩的，或者更好地使用来自 DecodePoint 的这部分；只需将以下几行添加到您的代码中；

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

输出 20267456347483554069520440766283645831919514026818877192810320909941447705364
注意 :如果你用

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

最后会有一个点。图书馆 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>().