證明使用者壓縮公鑰對應曲線方程（secp256k1）

我正在嘗試檢查某些壓縮公鑰是否對應於橢圓曲線方程（secp256r1）。據我所知，一旦滿足以下等式 y^2 = x^3 + ax + b或y^2 % p = (x^3 +ax +b) % p，它應該是有效的。假設我有以下密鑰：

公鑰 = 027d550bc2384fd76a47b8b0871165395e4e4d5ab9cb4ee286d1c60d074d7d60ef

我能夠提取 x 座標（在這種情況下我去除 02），所以理論上我應該能夠以下列方式計算它（如下所示），但 id 不能按預期工作。我不知道它是否與 sqrt 操作期間的回合有關，有人知道我做錯了什麼嗎？

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

程序輸出：

############# with MODULO ################ x: 56689369228784262545363082847328735491157691224156776757613891264163121815791 y: 183766007163050801754608903653841862618 right: 33769945388650438579771708095049232540048570303667364755388658443270938208149 left: 33769945388650438579771708095049232539920934980046904834800557419775585813924

############# without MODULO ################ x: 56689369228784262545363082847328735491157691224156776757613891264163121815791 y: 13497472057468355938572038677065615761097144061311551195730691629950308697806550176813818086835150901176637717416722 right: 182181751942139053636431558335628486248480898622843767538654320228825581987479906778155585847291878917907922072895611492267301384350099726325450762811050934436031042086671820982050911377912589308184841627685631347496623032412958678 left: 182181751942139053636431558335628486248480898622843767538654320228825581987479906778155585847291878917907922072895585240175884415988084178980651571231083458654830397520853615320131308334828726829265223601702424747233734581005225284

有效：0

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

那是你的問題; 你需要一個模平方根，它不是一個整數平方根，後跟一個模運算。

您可以將其計算為 $ y = x^{(p+1)/4} \bmod p $ （這是因為 $ p $ 是素數並且 $ p \equiv 3 \pmod 4 $ ); 我沒有使用過這個特定的 bignum 庫，所以我不能說如何表達它；它不應該那麼困難。

引用自：https://crypto.stackexchange.com/questions/101142