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

wqsoz72f  于 2023-01-10  发布在  其他
关注(0)|答案(2)|浏览(170)

在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?
}
c++

2条答案

按热度按时间
v1l68za4

v1l68za41#

可以，库支持点的压缩和解压缩，解压缩时，库必须找到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;

最后会有一个点，图书馆警告过这一点。

/// 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>().
赞(0）分享  回复(0）举报  2023-01-10
fd3cxomn

fd3cxomn2#

尽管您已经有了有效且简单的answer，但我仍然决定用纯C从头开始实现我自己的解决方案，因为您的任务非常有趣。
我的大型解决方案没有使用Crypto，而是尝试用C从头开始实现所有算法。它只是出于好奇心和科学及教育目的。它并不打算像纯Crypto解决方案那样快速和简单。
众所周知，如果模是任意形式的任意素数，则可以通过众所周知的非常快速的Tonelli Shanks算法来求平方根，这是以下代码的主要部分。
如果模是p % 4 == 3形式的素数，则它的根也可以通过公式root = n^((p + 1) / 4) % p容易地找到，这比Shanks Tonelli算法短得多，但是Shanks Tonelli对所有情况都有效，即使当p % 4 != 3时。
除了上面提到的算法，我还使用了平方和Euler's Criterion的模指数。
曲线Secp256k1的参数取自here和here：

p      = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
a      = 0
b      = 7
base_x = 0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
base_y = 0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
q      = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

我的代码可以在编译后立即运行，它在控制台上显示所有计时和结果，请参见下面代码后的示例输出。出于测试目的，我迭代范围[0..50]内的所有X，并显示其中哪些为Y给予有效的根。众所周知，X的50%左右的值将给出正确的解决方案。
为了编译我的程序除了标准的C++库我只使用GMP库为任意整数算术。它可以安装在Linux通过sudo apt install libgmp-dev。并在Windows安装VCPKG包管理器后，你可以做vcpkg install gmp，加上Windows将需要手动提供vckpg包括路径和链接库。我测试了编译和工作的程序在CLang和MSVC。
也可以点击下面的Try it online!链接在GodBolt服务器上在线测试程序的运行。
Try it online!

#include <cstdint>
#include <vector>
#include <functional>
#include <string>
#include <stdexcept>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <mutex>

#include <gmpxx.h>

#define ASSERT_MSG(cond, msg) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "! Msg: '" + std::string(msg) + "'."); }
#define ASSERT(cond) ASSERT_MSG(cond, "")
#define COUT(code) { std::unique_lock<std::recursive_mutex> lock(cout_mux); std::cout code; std::cout << std::flush; }
#define LN { COUT(<< "LN " << __LINE__ << std::endl); }
#define JOIN0(x, y) x##y
#define JOIN(x, y) JOIN0(x, y)
#define TEST(name) static void JOIN(Test_##name, __LINE__)(); static bool const JOIN(reg_test_##name, __LINE__) = []{ g_tests.push_back(std::make_pair(#name, &JOIN(Test_##name, __LINE__))); return true; }(); static void JOIN(Test_##name, __LINE__)()
#define RUN_TESTS() { for (auto & [name, f]: g_tests) { std::cout << "Test " << name << " " << std::flush; auto tb = Time(); f(); tb = Time() - tb; std::cout << std::fixed << std::setprecision(3) << tb << " sec" << std::endl; } }

using u8  = uint8_t;
using u16 = uint16_t;
using i16 = int16_t;
using u32 = uint32_t;
using i32 = int32_t;
using u64 = uint64_t;
using i64 = int64_t;

static std::recursive_mutex cout_mux;
static std::vector<std::pair<std::string, std::function<void()>>> g_tests;

template <typename T> struct DWordOf;
template <> struct DWordOf<mpz_class> { using type = mpz_class; };

template <typename T>
u32 ToU32(T const & N) { return mpz_class(N).get_ui(); }

double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::duration<double>>(
        std::chrono::high_resolution_clock::now() - gtb).count();
}

template <typename T>
std::vector<T> Uniquize(std::vector<T> vec) {
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    return std::move(vec);
}

template <typename T, typename DT = typename DWordOf<T>::type>
DT DTMul(T const & a, T const & b) {
    return DT(a) * b;
}

template <typename T>
T PowMod(T a, T b, T const & c)  {
    // https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
    using DT = typename DWordOf<T>::type;
    T r = 1;
    while (b != 0) {
        if (ToU32<T>(b) & 1)
            r = T(DTMul(r, a) % c);
        a = T(DTMul(a, a) % c);
        b >>= 1;
    }
    return r;
}

template <typename T>
int EulerCriterion(T const & n, T const & p) {
    // https://en.wikipedia.org/wiki/Euler%27s_criterion
    if (n == 0)
        return 0;
    auto const val = PowMod<T>(n, (p - 1) >> 1, p);
    ASSERT_MSG(val == 1 || val == p - 1, "val " + IntToStr(val) + " p " + IntToStr(p));
    return val == 1 ? 1 : -1;
}

template <typename T>
std::vector<T> SquareRoot_Mod4_3(T n, T const & p) {
    using DT = typename DWordOf<T>::type;
    ASSERT(p % 4 == 3);
    n %= p;
    T const r = PowMod<T>(n, (p + 1) >> 2, p);
    if (DTMul(r, r) % p == n % p)
        return Uniquize<T>(std::vector<T>({r, p - r}));
    return {};
}

template <typename T>
std::vector<T> SquareRoot_TonelliShanks(T n, T p) {
    // https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm
    // see also https://eprint.iacr.org/2020/1407.pdf
    using DT = typename DWordOf<T>::type;
    n %= p;
    if (n == 0)
        return {0};
    if (p == 2)
        return {n};
    {
        auto const ec = EulerCriterion<T>(n, p);
        ASSERT(ec == 1 || ec == -1);
        if (ec == -1)
            return {};
    }
    if (p % 4 == 3) {
        return SquareRoot_Mod4_3<T>(n, p);
    }
    T Q = p - 1, S = 0;
    while ((Q & 1) == 0) {
        Q >>= 1;
        ++S;
    }
    T z = 0;
    for (z = 2; z < p; ++z) {
        if (EulerCriterion<T>(z, p) == -1)
            break;
    }
    ASSERT_MSG(z < p, "n " + IntToStr(n) + ", p " + IntToStr(p));
    T M = S, c = PowMod<T>(z, Q, p), t = PowMod<T>(n, Q, p), R = PowMod<T>(n, (Q + 1) / 2, p), r = 0;
    ASSERT(M < u32(-1));
    while (true) {
        if (t == 0) {
            r = 0;
            break;
        }
        if (t == 1) {
            r = R;
            break;
        }
        T sqt = t;
        u32 i = 0;
        for (i = 1; i < M; ++i) {
            sqt = T(DTMul<T>(sqt, sqt) % p);
            if (sqt == 1)
                break;
        }
        ASSERT(i < M);
        //ASSERT(M - i - 1 < BiSize(T));
        T b = PowMod<T>(c, T(1) << ToU32(M - i - 1), p);
        M = i;
        c = T(DTMul<T>(b, b) % p);
        t = T(DTMul<T>(t, c) % p);
        R = T(DTMul<T>(R, b) % p);
    }
    ASSERT(DTMul<T>(r, r) % p == n);
    return Uniquize<T>(std::vector<T>({r, p - r}));
}

mpz_class MpzFromStr(std::string const & s, size_t base = 0) {
    mpz_class r;
    mpz_set_str(r.get_mpz_t(), s.c_str(), int(base));
    return r;
}

std::string MpzToStr(mpz_class n, size_t base = 10) {
    std::string s(mpz_sizeinbase(n.get_mpz_t(), base) + 5, '\x00');
    mpz_get_str(s.data(), base, n.get_mpz_t());
    return s.c_str();
}

template <typename T>
std::string IntToStr(T const & n) { return MpzToStr(n); }

TEST(Main) {
    COUT(<< std::endl);
    // https://en.bitcoin.it/wiki/Secp256k1
    // https://www.secg.org/sec2-v2.pdf
    // secp256k1 params
    mpz_class const
        p  = MpzFromStr("0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F"),
        a  = 0,
        b  = 7,
        bx = MpzFromStr("0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798"),
        by = MpzFromStr("0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8"),
        q  = MpzFromStr("0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141");
    auto EllipticCurve = [&](auto const & x) {
        return mpz_class((x * x * x + a * x + b) % p);
    };
    auto const p_len = IntToStr(p).size();
    for (u32 ix = 0; ix <= 50; ++ix) {
        mpz_class const x = ix, ec_value = EllipticCurve(x);
        auto roots = SquareRoot_TonelliShanks<mpz_class>(ec_value, p);
        if (roots.empty())
            continue;
        ASSERT(DTMul(roots.at(0), roots.at(0)) % p == ec_value);
        COUT(<< "x = " << std::setw(3) << ix << ", y = " << std::setw(p_len) << IntToStr(roots.at(0)) << std::endl);
    }
}

int main() {
    try {
        RUN_TESTS();
        return 0;
    } catch (std::exception const & ex) {
        COUT(<< "Exception: " << ex.what() << std::endl);
        return -1;
    }
}

控制台输出：

Test Main 
x =   1, y =  29896722852569046015560700294576055776214335159245303116488692907525646231534
x =   2, y =  46580984542418694471253469931035885126779956971428003686700937153791839982430
x =   3, y =  21320899557911560362763253855565071047772010424612278905734793689199612115787
x =   4, y =  40508090799132825824753983223610497876805216745196355809233758402754120847507
x =   6, y =  19112057249303445409876026535760519114630369653212530612662492210011362204224
x =   8, y =  24055953608229461237864090884685780858714989825500507741703654067262135535697
x =  12, y =  31068864722486242021761838950999795945745157936084027215252040495978276421796
x =  13, y =  20267456347483554069520440766283645831919514026818877192810320909941447705364
x =  14, y =  44647516152956573151520437476900496747965187933683819148138195218441524686495
x =  16, y =   6086653149631013477190265492692874244435390487330439650246572165529255539543
x =  20, y =  20676141886993640210986884816394413846392747094661403271705441051670760124834
x =  22, y =  17384355509374335117451332188362459136087449825697451396219196747631138909398
x =  25, y =   1102551495006820024539592786237854453433258304779672753607085440481650452602
x =  27, y =  12150456207077715994570159310959166905435600970349836880310459338926638464144
x =  32, y =  25427332243426016000490343799988059539558736656305693852522166340470154069724
x =  33, y =  51173090447386785350599579912891887007487842540657484998530120736905211706882
x =  38, y =   9646363146228555846652555429881922614278153944052502987030828554623605767881
x =  39, y =  28197313212501135724540236089620685652765900040943429810123028520443371359923
x =  43, y =  56572214809736663028893280596571268084211571988499307500846727553699476699834
x =  44, y =  29878230023088480380896492456768186169213097553238389007631075402030495033678
x =  45, y =   9813211421898343856404272161982377846064062305226732735279529255438243343429
x =  47, y =  37644263369555793562992696144870056406951060257194647817532744844486199964398
x =  48, y =  22158093920271983590355401047321466603843412217042649359409719523363101162922
0.064 sec
赞(0）分享  回复(0）举报  2023-01-10
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com