Beschleunigen Sie secp256k1 mithilfe von Endomorphismus / Sudo Null IT News

In diesem Artikel werden wir uns die Beschleunigungsfunktion secp256k1 mit Endomorphismus ansehen, die bei der Optimierung der ECDSA-Prüfung für die Bitcoin-Kryptowährung hilft, aber zuerst ein wenig Geschichte.

12. Januar 2009 Satoshi Nakamoto in den frühesten gesendeten Bitcoin-Transaktionen Hal Finney 10 BTC.

Dass Satoshi Nakamoto Hal als ersten Empfänger von Bitcoins auswählte, ist nicht verwunderlich. Satoshi hatte großen Respekt vor Hal, der sich durch die Entwicklung eines Verschlüsselungssystems als einer der klügsten Programmierer und Kryptographen der Welt etablierte. PGP. Hal legte auch einen wichtigen Grundstein für den wiederverwendbaren Proof-of-Work, den Satoshi bei der Entwicklung von Bitcoin verwenden würde.

Als einer der besten Kryptographen der Welt erkannte Hal sofort, nachdem er darüber gestolpert war, dass Bitcoin ein großer Durchbruch war.

Bereits 2008 rief er Bitcoin an „eine sehr vielversprechende idee“.

Dies twitternveröffentlicht am 11. Januar 2009, ist Beweis genug, dass Hal den Erfolg von Bitcoin vorhergesagt bevor viele überhaupt wussten, was es war.

Zwei Jahre vergingen und 2011 schrieb Hal Finney als Entwickler und Bitcoin-Enthusiast im Forum Bitcointalkwas Die secp256k1-Endomorphismusfunktion kann verwendet werden, um die ECDSA-Signaturüberprüfung zu beschleunigen

LAMBDA und BETA sind die Werte auf der secp256k1-Kurve, wobei:

λ^3 (mod n) = 1  β^3(modp)=1

secp256k1 verwendet die folgende Primzahl für seine x- und y-Koordinaten:

p = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc2f

und die Reihenfolge der Kurve:

n = 0xfffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

Der erste Schritt besteht darin, die LAMBDA- und BETA-Werte so zu berechnen, dass für jeden Punkt auf der Kurve Q = (x, y):

LAMBDA * Q = (BETA*x mod p, y)

Dies ist die sogenannte effektiv berechenbare Endomorphismusund es bedeutet, dass Sie jeden Punkt der secp256k1-Kurve sehr schnell mit diesem speziellen LAMBDA-Wert multiplizieren können, indem Sie eine einzelne mod p-Multiplikation durchführen.

Die von Hal Finney gefundene und veröffentlichte Bedeutung:

LAMBDA=0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72

Da wir schnell mit LAMBDA multiplizieren können, besteht der Trick darin, kQ zu berechnen. Zuerst verwenden wir die Berechnung Q’ = lambdaQ. Dann muss k in zwei Teile k1 und k2 aufgeteilt werden, die jeweils etwa halb so breit sind wie n, sodass:

k = k1 + k2*LAMBDA mod n

dann

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

Dieser letzte Ausdruck kann effizient mit dem doppelten Multiplikationsalgorithmus berechnet werden, und da k1 und k2 die halbe Länge haben, erhalten wir eine Beschleunigung.

Der fehlende Teil teilt k in k1 und k2. Es verwendet Folgendes 4 Werte:

a1 = 0x3086d221a7d46bcde86c90e49284eb15 b1 = -0xe4437ed6010e88286f547fa90abfe4c3 a2 = 0x114ca50f7a8e2f3f657c1108d9d44cfd8 b2 = 0x3086d68bc5

(es ist ok, dass a1 = b2)

Verwenden Sie sie so, um k:c1 = RoundToNearestInteger(b2*k/n) c2 = RoundToNearestInteger(-b1*k/n) k1 = k – c1*a1 – c2*a2 k2 = -c1*b1 – c2* b2

Aufgrund der Halbierung der Anzahl der Verdopplungen haben wir am Ende eine Beschleunigung von etwa 20 %.
Dadurch erhalten viele Algorithmen, die an mehreren Stellen gruppiert werden können, die Performance, die sie mit der doppelten Anzahl öffentlicher Schlüssel hätten.
Diese Beschleunigung bei gleicher Optimierungsstufe macht secp256k1 die am schnellsten zu testende aller gängigen Kurven.

Von der Existenz des Endomorphismus erfuhren wir in einer eingehenderen Untersuchung des Endlagers durch den Entwickler und Forscher Jean Luc Pons

Wir haben zuvor einen Artikel veröffentlicht: “Pollard’s Kangaroo findet Lösungen für den diskreten Logarithmus von secp256k1 PRIVATE KEY + NONCES in einem bekannten Bereich” , wo wir den Quellcode verwendet haben, um Kangaroo von Jean Luc Pons zu bauen.

Basierend auf einem beschleunigten Mechanismus wies Jean Luc Pons auf VanitySearch hin

Öffnen wir es main.cpp

main.cppmain.cpp

In Linien 255 und 256 Wir können sehen, dass Jean Luc Pons die elliptische Kurvenbeschleunigungsfunktion secp256k1 angewendet hat Endomorphismus.

lambda.SetBase16(“5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72”); lambda2.SetBase16(“ac9c52b33fa3cf1f5ad9e3fd77ed9ba4a880b9fc8ec739c2e0cfc810b51283ce”);

Kommen wir zum experimentellen Teil:

Wie wir uns aus dem Artikel erinnern, haben wir Transaktionen mit Bitcoin-Adressen analysiert 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
von der Liste Liste der Bitcoin-Reichen für insgesamt über 10 Millionen US-Dollarnehmen Sie diese Bitcoin-Adresse als Beispiel

Öffnen Sie Google Colab im Terminal [TerminalGoogleColab] und das Repository verwenden “07EndomorphismusSecp256k1”

git clone cd CryptoDeepTools/07EndomorphismSecp256k1/ pip3 install base58

öffnen Sie den Code Endomorphismus.py in der Reihe 145 Wir verwenden alle kurzen Werte, um die Verwendung von secp256k1 zu beschleunigen Endomorphismus

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 zurück (k1neg, k1, k2neg, k2)

Kopieren wir den privaten Schlüssel im HEX-Format, das wir im Artikel veröffentlicht haben

HEX: 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401bЗапустим Python-скрипт endomorphism.py указав закрытый ключ:python3 endomorphism.py 23d4a09295be678b21a5f1dceae1f634a69c1b41775f680ebf8165266471401b > pubkey.txt
Результат публичного ключа сохранится в файл: pubkey.txtОткроем файл: pubkey.txt и проверим: cat pubkey.txt 04ca5606a1e820e7a2f6bb3ab090e8ade7b04a7e0b5909a68dda2744ae3b8ecbfa280a47639c811134d648e8ee8096c33b41611be509ebca837fbda10baaa1eb15
Rufen Sie als Nächstes die Bitcoin-Adresse ab, indem Sie das Python-Skript pubtoaddr.pypython3 pubtoaddr.py ausführen. Öffnen Sie die Datei: BitcoinAddress.txt und überprüfen Sie: cat BitcoinAddress.txt 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE
ADDR: 14NWDXkQwcGN1Pd9fboL8npVynD5SfyJAE WIF: 5J64pq77XjeacCezwmAr2V1s7snvvJkuAz8sENxw7xCkikceV6e HEX: 23d4a09295be678b21a5f1dceae1f634a69c1b417f78f66Überprüfung des privaten Schlüssels auf der Bitadresse-WebsiteÜberprüfung des privaten Schlüssels auf der Bitadresse-Website

Blockchain:

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

Zu diesem Thema können Sie die Literatur lesen:

  • Gallant, Robert P., Robert J. Lambert und Scott A. Wanston. “Schnellere Punktmultiplikation auf elliptischen Kurven mit effizienten Endomorphismen”. Annual International Conference on Cryptology, S. 190–200. Springer, Berlin, Heidelberg, (2001)

  • Hankerson, Darrell, Alfred J. Menezes und Scott Wanston. “Ein Leitfaden zur Kryptografie mit elliptischen Kurven”. Computer Reviews 46, No. 1 (2005)

  • Hal Finney. bitcointalk- “Signaturprüfung beschleunigen”. (2011) https://bitcointalk.org/index.php?topic=3238.0

  • Blahut, Richard E. “Kryptographie und sichere Kommunikation”. Cambridge University Press, (2014)

Dieses Video wurde für das Portal erstellt KRYPTO-DEEP-TECH für Finanzdatensicherheit und secp256k1 Elliptische-Kurven-Kryptographie gegen schwache ECDSA-Signaturen in der BITCOIN-Kryptowährung

Quelle

Telegramm: https://t.me/cryptodeeptech

Filmaufnahme: https://youtu.be/DH6FyNY-Gh0

Quelle: https://cryptodeep.ru/endomorphism

Similar Posts

Leave a Reply

Your email address will not be published.