Yeah probably possible. On the other hand, why would you listen for potentially few years on the nodes with ready to crack hardware to get 1.2 btc to make a potentially successful double spent attack?
|
|
|
Your signing method seems to be wrong. Shouldn't you be using curve.p instead of curve.n?
|
|
|
strange. It is correct. Btw. I modified your script: import collections import hashlib import random import os
EllipticCurve_1 = collections.namedtuple('EllipticCurve', 'name p a b g n h')
curve = EllipticCurve_1( 'secp256k1', # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141, # Subgroup cofactor. h=1, )
# Modular arithmetic ##########################################################
def inverse_mod(k, p): """Returns the inverse of k modulo p. This function returns the only integer x such that (x * k) % p == 1. k must be non-zero and p must be a prime. """ if k == 0: raise ZeroDivisionError('division by zero')
if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p)
# Extended Euclidean algorithm. s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = p, k
while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t
gcd, x, y = old_r, old_s, old_t
assert gcd == 1 assert (k * x) % p == 1
return x % p
# Functions that work on curve points #########################################
def is_on_curve(point): """Returns True if the given point lies on the elliptic curve.""" if point is None: # None represents the point at infinity. return True
x, y = point
return (y * y - x * x * x - curve.a * x - curve.b) % curve.p == 0
def point_neg(point): """Returns -point.""" assert is_on_curve(point)
if point is None: # -0 = 0 return None
x, y = point result = (x, -y % curve.p)
assert is_on_curve(result)
return result
def point_add(point1, point2): """Returns the result of point1 + point2 according to the group law.""" assert is_on_curve(point1) assert is_on_curve(point2)
if point1 is None: # 0 + point2 = point2 return point2 if point2 is None: # point1 + 0 = point1 return point1
x1, y1 = point1 x2, y2 = point2
if x1 == x2 and y1 != y2: # point1 + (-point1) = 0 return None
if x1 == x2: # This is the case point1 == point2. m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # This is the case point1 != point2. m = (y1 - y2) * inverse_mod(x1 - x2, curve.p)
x3 = m * m - x1 - x2 y3 = y1 + m * (x3 - x1) result = (x3 % curve.p, -y3 % curve.p)
assert is_on_curve(result)
return result
def scalar_mult(k, point): """Returns k * point computed using the double and point_add algorithm.""" assert is_on_curve(point)
if k % curve.n == 0 or point is None: return None
if k < 0: # k * point = -k * (-point) return scalar_mult(-k, point_neg(point))
result = None addend = point
while k: if k & 1: # Add. result = point_add(result, addend)
# Double. addend = point_add(addend, addend)
k >>= 1
assert is_on_curve(result)
return result
# Keypair generation and ECDSA ################################################
def make_keypair(private): """Generates a random private-public key pair.""" private_key = private#random.randrange(1, curve.n) public_key = scalar_mult(private_key, curve.g)
return private_key, public_key
def hash_message(message): """Returns the truncated SHA512 hash of the message.""" message_hash = hashlib.sha512(message).digest() e = int.from_bytes(message_hash, 'big')
# FIPS 180 says that when a hash needs to be truncated, the rightmost bits # should be discarded. z = e >> (e.bit_length() - curve.n.bit_length())
assert z.bit_length() <= curve.n.bit_length()
return z
def sign_message(private_key, message,nonce): z = hash_message(message)
r = 0 s = 0 half_mod=57896044618658097711785492504343953926418782139537452191302581570759080747169 while not r or not s: k = nonce# random.randrange(1, curve.n) x, y = scalar_mult(k, curve.g)
r = x % curve.n s = ((z + r * private_key) * inverse_mod(k, curve.n)) % curve.n if s> half_mod: s=curve.n -s if s<0: s=s%curve.n return r, s,z
def verify_signature(public_key, message, signature): z=message r, s = signature
w = inverse_mod(s, curve.n) u1 = (z * w) % curve.n u2 = (r * w) % curve.n
x, y = point_add(scalar_mult(u1, curve.g), scalar_mult(u2, public_key))
if (r % curve.n) == (x % curve.n): return 'signature matches' else: return 'invalid signature'
def egcd(a, b): "Euclidean greatest common divisor" if a == 0: return (b, 0, 1) else: g, y, x = egcd(b % a, a) return (g, x - (b // a) * y, y)
def modinv(a, m): "Modular inverse" # in Python 3.8 you can simply return pow(a,-1,m) g, x, y = egcd(a, m) if g != 1: raise Exception('modular inverse does not exist') else: return x % m
def make_val(priv,nonce,msg,id):
private, public = make_keypair(priv) r,s,z = sign_message(private, msg,nonce) print() print("tra"+str(id)+"=", id) print("z"+str(id)+"=",z) print("r"+str(id)+"=",r) print("s"+str(id)+"=",s) return private,public,nonce,r,s,z import random
a=2**119 # min nonce range c=2**120 # max nonce range priv=random.randrange(a,c) # here put real privatekey for testing address
print("priv=",priv)
for i in range(1,22): priv=priv nonce=random.randrange(a,c) war= str(os.urandom(25)) + str(nonce) # message for hash you can change msg= bytes(war, 'utf-8') make_val(priv,nonce,msg,i)
|
|
|
I did not save the nonce. I just have the privatekey. Please provide the privatekey
|
|
|
Lets test:
tra1= 1 z1= 80432933230601221097993727756010017129787501550380567129597359178965598318961 r1= 95781203938134771654748299032707231792956540686382340872008587989453366815619 s1= 7534182813406032375639570543805434153582981540120020674256382120866612731545
tra2= 2 z2= 85680514558167908477786333863388893581378252427409848818380410461316229181866 r2= 84387110444751472823093034301289748550849649710026789889116612056105290236666 s2= 15868173206225036603686021099703018179590395525753258826877174594462501530079
tra3= 3 z3= 102548060755430092557032225125812044091702107450760273047035460895048062052718 r3= 27406416767577587294750316503826186048488400834507872051943779772307226633113 s3= 29649827600148630504342805875898663176877984669003820299263529443079802600071
tra4= 4 z4= 112762186256989393169437822071227972337950204496999027396617246293615417123739 r4= 24533641989102775196628594221334796778083883960590329762923456368413461852299 s4= 16882387067703002986567484296970150975533444813169171948956607802923870347023
tra5= 5 z5= 102279196193793343325884084378657993486468399648088512512988733890200957279784 r5= 4186715484844983123419598414866818539075061038431735919514226083013167756155 s5= 8262954510115071207116675186488512957332248957748965006108287723178501039896
tra6= 6 z6= 76599337534901405117822248198667485404482686031169748143178670259003848287439 r6= 15851496704632343532719173064913915530730795724303043380989972174875820919342 s6= 26576261782157862061451463273657755133732897768366490380590654547180621157141
tra7= 7 z7= 74398756248746214977130745318145828522823513476562434939314347317864019408104 r7= 82938562188044339921427613336772663621899602829543541692100956778620655883715 s7= 39276923828201170271310196305299508032465347755337674976758619924891700833905
tra8= 8 z8= 93862483065024393549379332456158503628205024790587502021315239071043175114663 r8= 7411568948143399435509900026903834934761258989831647943158886146811354079538 s8= 23454514152056767665551790603659948673144210777974558960318258587233196371568
tra9= 9 z9= 87212835189063827733529626354248276448977979158329199208629242026076557818917 r9= 20889553213233893265958705672668442429273166902005987737459335431141560894844 s9= 27423452166008738427798130440666854429824905865512438279454635509066007514682
tra10= 10 z10= 83526908368291586317385663590170015031851022781584948450170378394060055282190 r10= 1551267817981681426867155210843143173739922432355325773348926277065615199124 s10= 7684997265909350501172737349863748207353273631798032611769190263974310544153
tra11= 11 z11= 70216054243675114296838106735481510568779895968275843537650562550505875665884 r11= 3576215969366506200887064213959692679458469437850773397125768328709003892693 s11= 8491746974080525764648769152663569501948698616778822026514700690845755846036
tra12= 12 z12= 89733062301906218205525418189137256626216977972801843205374974324400215840828 r12= 97313926167509765235969476588879256253496420668224173139454279120159942879086 s12= 19295737902082704812304176269762588020355607076724374854491642265193141823115
tra13= 13 z13= 96800310781779757299975867336276488799196141063184958927190190798527008705916 r13= 42070356969267196115116156358237620445959087770740309235322030690855700545810 s13= 10926583446370215596799000534456164698973709500742209976903140188036054436449
tra14= 14 z14= 81714449254712760707918304846809454665088582912931981051864732182561582298238 r14= 58073695671307170568419102195235996994583777317992518220245717338070878674156 s14= 19792817965853054888446030958771606050153179370949846426265966672150489443411
tra15= 15 z15= 76759150958316466797868455117596604431612737464895047156570412248139660287052 r15= 94586485973446155887959040710048915448470773770617838635783959877240432721656 s15= 28063041539553628419746310379638058010152764036311466792055721311420803812447
tra16= 16 z16= 92499754792222738144216780989904991819554086516524559478651643395189700685794 r16= 71939545401850453214874187169856165961828003540145583228587282096343059531899 s16= 27303410094905761075542191840103815065728404615300353026335925873266028888452
tra17= 17 z17= 71671985408282064775019373629276105193987188816974581745032636341614355842016 r17= 70383727207956972699666680095479428342891345798684662625048123721946335076625 s17= 47376653716826238909420876991580731676243753307099848962332872802844323211717
tra18= 18 z18= 63591528578379679141238250400599292221541599192036303519731712765210919464422 r18= 45500365351118977211406259758768764026063563859084757156591595546165493014663 s18= 34307171799239851805904487103725658652610855118455933742836940770589902022672
tra19= 19 z19= 107164927559473669756603524613052219740269009154417431689890768133047622836166 r19= 96627369325043872501790129338116851490620103479332311256810063548097534320654 s19= 31968298917126978087049365043290119448833740147636323787180781572364723707202
tra20= 20 z20= 85970834890705013834585655218850010892371629752141337733506872715042255792872 r20= 71829258547144965070289411632492360722073814888969159867632514135612440224933 s20= 17138487813600668308567888594176245081979974822887521540058184000576581472868
tra21= 21 z21= 105716729965293059122180239654378367863923370279795705920594244675929611838995 r21= 66046519851205321846729811244825018910171992561559320851253372782475190437050 s21= 15407097485325905671745310982896688957624093301348612787111637570846813762301
|
|
|
k = nonce# random.randrange(1, curve.n)
Does this not mean that we reuse the nonce for all transactions?
|
|
|
Can you please clarify for Cobras, that it has to be outgoing transactions and not incoming transactions? He is kind of a very slow fella
|
|
|
Oh man... Cobras, are you stupid? He needs at least 70 outgoing transactions from a 240 bit address. Why outgoing you may ask? Because when you sign a transaction you use your privatekey, but when receiving a transaction you use just an address.
So your request is bullshit, because 1LdRcdxfbSnmCYYNdeYpUnztiYzVfBEQeC has supposedly more than a 240 bit privatekey and even if it had 240bit or less, never had any outgoing transaction.
Stop wasting our time Cobras!
|
|
|
Does it only work when secret of transaction is also less than 240 bit?
How many transactions do you need for 128 bit?
And what result do you get when you provide less than 70 transactions?
|
|
|
Why not steal from some big wallet a small amount?
|
|
|
So let's say we switch the x and y coordinates and search for the y value, we get e.g. the value 15. Then we could theoretically determine that x can be
225 = x^3 + 7 218 = x^3
3✓218 = x
X= 6.01..
( I am now to lacy to find a solution were we get an integer result for x)
|
|
|
This is the symmetry in secp256k1.
0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c 4655da4fbfc0e1108a8fd17b448a68554199c47d08 is the uncompressed privatekey of 1. The other one is the uncompressed privatekey of -1.
-1 => N - 1
|
|
|
I think I made myself not clear. My native language is German. I apologize. I Looked at it with my programmers eyes. As you already explained few days ago, cuda BSGS is searching the keys one after another, not in parallel. I know that, I read carefully . With my previous post I meant that even if it would run in parallel it would slow down as described. So read my post in conjunctive and if someone would modify it to process in parallel I expect that behaviours.
|
|
|
Interesting List you have. I would have given merits If I had some.
I don't think that they can be effectively searched in parallel. You have to divide each pubkey and check it with the babysteps. So not only do you need to make very expensive global memory lookup (GPU has slow global and super fast local memory) and load each key.
So if you would search multiple keys you would effectively reduce the performance by them. Like 10 keys in parallel means 10 times slower. 2800 keys means 2800 times slower.
|
|
|
If you feel wasting your time you should not react at all
I was answering nice to even reach out to someone who asks such uninformed questions. Anyway, your answer is like saying baby steps must find it (what) first. Total bullshit.
To understand babystep giantstep read the wiki article https://en.wikipedia.org/wiki/Baby-step_giant-stepIf you search in a range, you just need to generate a small babystep lookup table, with potential steps in that range. But if you are looking for a value outside the provided range, the babystep lookup table wont contain the necessary value! So you are having no hit. The english WP contains no example, but the german one contains an example: https://de.wikipedia.org/wiki/Babystep-Giantstep-Algorithmus#Beispiel
|
|
|
Actually my original answer was kind of rough and was basically Like: your questions are stupid, first inform yourself what the different cracking methods are doing on Wikipedia and then ask again before wasting our time. Then I thought, I should be friendly and removed the toxic part. Now to read your answer encourages me to give you a rough answer. So yes your question about BSGS is total bullshit. BSGS looks for the right babysteps. If It finds the right babysteps, then it can determine by doing the giant steps the actual value of the private key. This is clearly described in wikipedia. Do you mean to say that bsgs algo gives you 100% information if key is or is not in s given range k1-k2?
This question is stupid. Obviously if BSGS ran a range and did or did not find a solution it means that the key is or is not in range k1-k2. Or you say bsgs would find private key even if k1 k2 interval is incorrect?
How is this even possible, when already babysteps don't find a value? This question is totally stupid. Please first do some fundamental research. Maybe then you won't waste your and our time by asking totally stupid questions and blaming others for giving supposedly stupid answer despite the fact reading wikipedia and using your own brain would give you the logical answer.
|
|
|
There is already a small python script for your needs here in this thread.
|
|
|
You should read the articles about Pollards Kangaroo Algorithm and BSGS. If you find the key with BSGS in range, than you know 100% for sure, that the key is in range. And if a baby step is not found in the defined range for the pubkey than it will find no solution.
|
|
|
|