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

Question

crypto++ 中是否有任何方法可以检查 EC 是否包含具有给定 x 坐标的点？

一种解决方案是求解给定 x 的 EC 多项式。等式的一侧已经用代码完成了。我 'just' 需要计算它的根（在有限域上）

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

的header

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>().

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

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?

c++

cryptography

elliptic-curve

crypto++