用自同態加速secp256k1

Crypto Deep Tech

secp256k1 在本文中，我們將研究有助於優化比特幣加密貨幣驗證的自同態 加速函數 ECDSA ，但首先要了解一點歷史。

12 января 2009 года 中本聰 在最早的比特幣交易中 派出了哈爾芬尼 10 BTC。

中本聰選擇 Hal 作為比特幣的第一個接收者並不奇怪。中本聰非常尊重 Hal，他通過開發 PGP加密系統確立了自己作為世界上最聰明的程序員和密碼學家之一的地位。Hal 還為中本聰在比特幣開發中使用的可重用工作量證明奠定了重要基礎。

作為世界上最好的密碼學家之一，哈爾在偶然發現比特幣後立即意識到比特幣是一個巨大的突破。

他還 2008 году 稱比特幣為 “一個非常有前途的想法”。

用自同態加速secp256k1

由 發布的 這條 推文11 января 2009 года足以證明哈爾  甚至在許多人知道比特幣是什麼之前就預測到了比特幣的成功。

兩年過去了， 2011 году 作為開發者和比特幣愛好者的 Hal Finney 在 Bitcointalk論壇上寫道，  secp256k1 自同態函數可用於加速 ECDSA 簽名驗證

LAMBDA和BETA是secp256k1曲線上的值，其中：

λ^3 (mod n) = 1
b ^ 3 (mod p) = 1

secp256k1 使用以下質數作為其 x 和 y 坐標：

p = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc2f

和曲線的順序：

n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

第一步是計算 LAMBDA 和 的值BETA，這樣對於曲線上的任意點 Q = (x, y)：

LAMBDA * Q = (BETA*х mod р, у)

這就是所謂的有效可計算 自同態，它意味著您可以通過一次乘法 非常快速地將曲線上的任何點乘以 secp256k1 這個特殊值 。LAMBDAmod p

Hal Finney發現並發表的意義：

LAMBDA = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

BETA = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee

鑑於我們可以快速相乘， LAMBDA, 訣竅是計算 kQ。 先用計算吧。然後  你需要分成兩部分  和 ，每部分大約是 寬度的一半 ，這樣： Q' = lambdaQkk1k2n

k = k1 + k2*LAMBDA  mod  n

然後

k*Q = (k1 + k2*LAMBDA)*Q = k1*Q + k2*LAMBDA*Q = k1*Q + k2*Q'

最後一個表達式可以使用雙倍乘法算法高效地計算，並且由於 k1 和 k2 是長度的一半，我們得到了加速。

缺少的部分拆分 k 為 k1 和 k2。以下4 個值用於此 ：

а1 = 0x3086d221a7d46bcde86c90e49284eb15
b1 = -0xe4437ed6010e88286f547fa90abfe4c3
а2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
b2 = 0x3086d221a7d46bcde86c90e49284eb15

（沒關係，a1 = b2）

我們按如下方式使用它們來劃分 k：

c1 = RoundToNearestInteger(b2*k/n)
c2 = RoundToNearestInteger(-b1*k/n)

k1 = k - c1*a1 - c2*a2
k2 = -c1*b1 - c2*b2

20%-е 由於加倍次數減半，我們最終得到了大致的 加速。這為許多可以在多個點上分組的算法提供了它們在使用兩倍數量的公鑰時所具有的性能。
這種在同等優化水平上的加速使其成為 secp256k1 所有常用曲線中測試速度最快的曲線。

我們從開發人員和研究員 Jean Luc Pons 那裡對存儲庫進行了更詳細的研究，了解了自同態的存在

用自同態加速secp256k1

我們之前發表過一篇文章：  “Pollard’s Kangaroo find solutions to the discrete logarithm of secp256k1 PRIVATE KEY + NONCES in a known range”， 其中 我們使用了Jean Luc Pons構建 Kangaroo 的 源代碼。

基於加速機制 Jean Luc Pons 指出 VanitySearch

打開 main.cpp

主.cpp
主.cpp

在第 255 和 256行中，  我們看到 Jean Luc Pons secp256k1 使用 自同態應用了橢圓曲線加速函數。

  lambda.SetBase16("5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72");
  lambda2.SetBase16("ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce");

讓我們繼續進行實驗部分：

用自同態加速secp256k1

正如我們在 文章中所記得的 ，我們分析了比特幣富豪榜中比特幣地址 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE 的交易 總額 超過1000 萬 美元，以該比特幣地址為例

在終端中打開 Google Colab  [TerminalGoogleColab] 並使用存儲庫 “07EndomorphismSecp256k1”

git clone https://github.com/demining/CryptoDeepTools.git

cd CryptoDeepTools/07EndomorphismSecp256k1/

pip3 install base58
用自同態加速secp256k1

145行打開代碼 endomorphism.py我們使用 所有 的short值來加速  endomorphism  secp256k1

def split_scalar_endo(k):
    n = N
    a1 = 0x3086d221a7d46bcde86c90e49284eb15
    b1 = -0xe4437ed6010e88286f547fa90abfe4c3
    a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8
    b2 = a1
    c1 = div_nearest(b2 * k, n)
    c2 = div_nearest(-b1 * k, n)
    k1 = mod(k - c1 * a1 - c2 * a2, n)
    k2 = mod(-c1 * b1 - c2 * b2, n)
    k1neg = k1 > POW_2_128
    k2neg = k2 > POW_2_128
    if k1neg:
        k1 = n - k1
    if k2neg:
        k2 = n - k2
    return (k1neg, k1, k2neg, k2)

以我們在文章HEX中發布的格式複制 私鑰 

HEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b

讓我們運行指定私鑰的 Python 腳本 endomorphism.py：

python3 endomorphism.py 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b > pubkey.txt
用自同態加速secp256k1

公鑰的結果將保存到文件：pubkey.txt

Откроем файл: pubkey.txt и проверим:

cat pubkey.txt

04ca5606a1e820e7a2f6bb3ab090e8ade7b04a7e0b5909a68dda2744ae3b8ecbfa280a47639c811134d648e8ee8096c33b41611be509ebca837fbda10baaa1eb15
用自同態加速secp256k1

接下來，通過運行 Python 腳本 pubtoaddr.py 獲取比特幣地址

python3 pubtoaddr.py

Откроем файл: BitcoinAddress.txt и проверим:

cat BitcoinAddress.txt

14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
用自同態加速secp256k1
ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
WIF:  5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e
HEX:  23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b
在bitaddress網站上查看私鑰
在bitaddress網站上查看私鑰

區塊鏈：

www.blockchain.com/btc/address/14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
www.blockchain.com/btc/address/14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE

關於這個話題，你可以閱讀文獻：

  • Gallant、Robert P.、Robert J. Lambert 和 Scott A. Wanston。 “具有有效自同態的橢圓曲線上的更快點乘法”。年度國際密碼學會議，第 190-200 頁。斯普林格，柏林，海德堡，(2001)
  • Hankerson、Darrell、Alfred J. Menezes 和 Scott Wanston。 “橢圓曲線密碼學指南”。計算機評論 46，沒有。1 (2005)
  • 哈爾·芬尼。bitcointalk –  “加速簽名驗證”。(2011)  https://bitcointalk.org/index.php?topic=3238.0
  • Blahut, Richard E.  “密碼學和安全通信”。劍橋大學出版社，（2014）

該視頻是為 CRYPTO DEEP TECH門戶網站創建的 ，以確保橢圓曲線上的數據和密碼學的金融安全性 免受 加密貨幣中 secp256k1 弱簽名的影響 ECDSABITCOIN

來源

電報：  https: //t.me/cryptodeeptech

視頻素材：  https: //youtu.be/DH6FyNY-Gh0

資料來源：  https ://cryptodeep.ru/endomorphism

 密碼分析

Ускорение secp256k1 с помощью эндоморфизма

Crypto Deep Tech