Alpaste
Jr. Member
Offline
Activity: 37
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 10:49:43 AM |
|
Yes you are right, but one point i don't get it. why would i scan 2^256 range? isn't it scanning only 2^160 using for example BSGS to find any specific publickey with its private key? (since all publickeys and all private keys are in the range of 2^160.)
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 11:05:15 AM |
|
If we talking about bruteforce like bitCrack, you have to check 2^97 keys in average to find specific address (not the specific public key)
No, you have to check 2^(256-96) = 2^160 keys in average to find the private key to a specific address. Yes you are right, but one point i don't get it. why would i scan 2^256 range? isn't it scanning only 2^160 using for example BSGS to find any specific publickey with its private key? (since all publickeys and all private keys are in the range of 2^160.)
More or less. You don't know for sure that all addresses have a private key in range [1, ..., 2^160]
|
|
|
|
_Counselor
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 107
Merit: 61
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 11:18:27 AM |
|
No, you have to check 2^(256-96) = 2^160 keys in average to find the private key to a specific address.
yeah, you're right here, I wrote it wrong.
|
|
|
|
Alpaste
Jr. Member
Offline
Activity: 37
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 11:27:01 AM |
|
arulbero, i'm wondering, how does these 2^96 collisions happen? does the 2^96 addresses each address share all the same public key or how does 2^96 addresses can generate the same address?
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 11:34:47 AM Last edit: December 24, 2021, 12:33:31 PM by arulbero |
|
arulbero, i'm wondering, how does these 2^96 collisions happen? does the 2^96 addresses each address share all the same public key or how does 2^96 addresses can generate the same address?
The same address is related to 2^96 different public keys (and 2^96 different private keys) An address is only the hash of a public key; different public keys (256 bit) have the same hash (160bit).
|
|
|
|
Alpaste
Jr. Member
Offline
Activity: 37
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 11:51:38 AM |
|
That's insane! Thank you for clarifying! may i ask but, how is it possible to an same address to relate to another completely different public keys and private keys? how do they match to same address, if they're completely different? Thanks again.
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 24, 2021, 12:48:51 PM Last edit: December 26, 2021, 04:58:20 PM by arulbero |
|
That's insane! Thank you for clarifying! may i ask but, how is it possible to an same address to relate to another completely different public keys and private keys? how do they match to same address, if they're completely different? Thanks again.
A: the set of 2^256 public keys B: the set of 2^160 addresses (hashes of the public keys) the hash function maps the set A into the set B hash : A -> B when the # of keys > # of hashes, collisions are inevitable ![](https://ip.bitcointalk.org/?u=https%3A%2F%2Fi.postimg.cc%2FGmQPPvWp%2FHash-table-4-1-1-0-0-1-0-LL.png&t=665&c=bDPWCkQAzoNjAw) source: https://en.wikipedia.org/wiki/Hash_function
|
|
|
|
akaki
Newbie
Offline
Activity: 23
Merit: 35
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 26, 2021, 12:43:28 AM |
|
Hi, One question regarding the performance of the algorithm. It's stated that for puzzle #120, the : Expected time: ~2 months on 256 Tesla V100. This is really mind boggling ![Shocked](https://bitcointalk.org/Smileys/default/shocked.gif) . But does someone know how long it took (or a time approximation) to solve puzzle #115 using 4 Tesla V100 ? To me it took (60/2^5)*(256/4)= 4 months, which is surely not reasonnable.
|
|
|
|
mausuv
Jr. Member
Offline
Activity: 70
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 26, 2021, 06:18:45 AM |
|
https://github.com/ragestack/EC-Point-Operations/blob/master/EC_Math.pyhttps://bitcointalk.org/index.php?topic=5244940.msg58488513#msg58488513Point1 = (x1,y1) Point2 = (x2,y2)
Point3 = sub(Point1,Point2) Point4 = add(Point1,Point2) Point5 = div(Point1,2) # remove Scalar option, i need two point use div Point5 = div(Point1,Point2) Point6 = mul(Point1,2) # remove Scalar option, i need two point use mul Point6 = mul(Point1,Point2)
i need two point use div Point5 = div(Point1,Point2) #remove Scalar option i need two point use mul Point6 = mul(Point1,Point2) # remove Scalar option eny method Point1,Point2 use div and mul get therd point #mybadenglish read my top 2 link modify please.. its posible remove scalar #modify please def ECdiv(Qx,Qy,Scalar): # EC point division remove Scalar option A = (N-1)/Scalar Px,Py = ECmul(Qx,Qy,A) Py = P-Py return Px,Py Dx,Dy = ECdiv(Cx,Cy,2) print (Dx,Dy)
|
|
|
|
|
jacky19790729
Jr. Member
Offline
Activity: 82
Merit: 8
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 26, 2021, 04:09:16 PM Last edit: December 27, 2021, 11:31:05 AM by Mr. Big |
|
Hi, One question regarding the performance of the algorithm. It's stated that for puzzle #120, the : Expected time: ~2 months on 256 Tesla V100. This is really mind boggling ![Shocked](https://bitcointalk.org/Smileys/default/shocked.gif) . But does someone know how long it took (or a time approximation) to solve puzzle #115 using 4 Tesla V100 ? To me it took (60/2^5)*(256/4)= 4 months, which is surely not reasonnable. #110 about 2 days on 256 Tesla V100 #115 about 11 days on 256 Tesla V100 4 Tesla V100 ~~ should be 256/4=64 It takes 64 times ~~~ about 1 day (very lucky) ~ 704 days ( maybe it will take longer )
i need two point use div Point5 = div(Point1,Point2) #remove Scalar option i need two point use mul Point6 = mul(Point1,Point2) # remove Scalar option eny method Point1,Point2 use div and mul get therd point #mybadenglish read my top 2 link modify please.. its posible remove scalar
python 3
Gx = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 PG = Point(Gx, Gy) P1 = Point(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8) P2 = Point(0xc6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,0x1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a) P3 = Point(0xf9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9,0x388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672) P4 = Point(0xe493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13,0x51ed993ea0d455b75642e2098ea51448d967ae33bfbdfe40cfe97bdc47739922)
# Puzzle 63 $$$ 1NpYjtLira16LfGbGwZJ5JbDPh3ai9bjf4 Puzzle_63 = Point(0x65ec2994b8cc0a20d40dd69edfe55ca32a54bcbbaa6b0ddcff36049301a54579, 0x5a1b76ab01e9edd0de24157ceff77bcb0f615560b250b365a5d435873eaa4625 )
# Puzzle 120 $$$ 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT Puzzle_120 = Point(0xceb6cbbcdbdf5ef7150682150f4ce2c6f4807b349827dcdbdd1f2efa885a2630, 0x2b195386bea3f5f002dc033b92cfc2c9e71b586302b09cfe535e1ff290b1b5ac )
# Puzzle 115 $$$ Puzzle_115 = mulk( 0x60F4D11574F5DEEE49961D9609AC6, P1 ) print ("[#115] %064x %064x" % (Puzzle_115.x,Puzzle_115.y) )
P_add = add( P1 , P2 ) print ("[add ] %064x %064x" % (P_add.x,P_add.y) )
P_sub = sub( P3 , P1 ) print ("[sub ] %064x %064x" % (P_sub.x,P_sub.y) )
P_mul2 = mul2( P1 ) print ("[mul2] %064x %064x" % (P_mul2.x,P_mul2.y) )
P_mulk = mulk( 0x3, P1 ) print ("[mulk] %064x %064x" % (P_mulk.x,P_mulk.y) )
# 0x4 / 0x2 = 0x2 P_div = div( P4 , 0x2 ) print ("[div ] %064x %064x" % (P_div.x,P_div.y) )
# 0x4 / 0x4 = 0x1 P_div = div( P4 , 0x4 ) print ("[div ] %064x %064x" % (P_div.x,P_div.y) )
# 0x7CCE5EFDACCF6808 / 0x3E672F7ED667B404 = 0x2 P_div = div( Puzzle_63 , 0x3E672F7ED667B404 ) print ("[div ] %064x %064x" % (P_div.x,P_div.y) )
===========output============ [#115] 48d313b0398d4923cdca73b8cfa6532b91b96703902fc8b32fd438a3b7cd7f55 66f0742c24f5ff80c799d691d756ad8e5aa7f6d8f986abd9eeef45514637c0d4 [add ] f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 [sub ] c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a [mul2] c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a [mulk] f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9 388f7b0f632de8140fe337e62a37f3566500a99934c2231b6cb9fd7584b8e672 [div ] c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a [div ] 79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798 483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8 [div ] c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5 1ae168fea63dc339a3c58419466ceaeef7f632653266d0e1236431a950cfe52a
|
|
|
|
darangus
Newbie
Offline
Activity: 9
Merit: 0
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 30, 2021, 09:38:17 AM |
|
Hi all, i've started up a dedicated kangaroo box, and i was trying all different combinations, i was just wondering what would be a good random combination to just leave running for a year, i'm looking to strike it lucky, not looking to solve specific puzzles.
Throw some ideas at me.
|
|
|
|
fxsniper
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 406
Merit: 47
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 03, 2022, 03:11:39 PM |
|
Can possible do calculate kangaroo by do manual ? puzzle120 I would like to try my range by do manual made kangaroo
tame and wild is public key (point) and do multiply to number right? I will try do python script generate tame and wide each one a million line of set and compare it both by manual too
|
|
|
|
batareyka
Jr. Member
Offline
Activity: 38
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 05, 2022, 12:11:48 PM |
|
Just silly question ![Grin](https://bitcointalk.org/Smileys/default/grin.gif) is it possible to know this public key is from this range? like 110 or 115? is there any way to identify? No, otherwise you would be able to find the upper bits of every private key in existence. Hi. Can you explain how you can learn the upper bits by knowing the range? Hi. I once asked the question of whether it is possible to calculate mathematically in which range the key is. To which I received a response from NotATether. If you know the range you can calculate the upper bits of the key. The question logically asks for answers. If we know, and we know in what range the key lies (like puzzle 120). Then why not calculate the upper bits? What is the calculation algorithm? Thanks.
|
|
|
|
Alpaste
Jr. Member
Offline
Activity: 37
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 05, 2022, 02:10:15 PM |
|
I think it's impossible to calculate the upper bits of the key, even if you know that this private key lies in the 2^120 bits-range. The only way to get the key, is to use kangaroo, or BSGS, but the chances that you find the key is extremely low. Cheers!
|
|
|
|
batareyka
Jr. Member
Offline
Activity: 38
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 05, 2022, 02:26:24 PM |
|
Alpaste I also hold this opinion. But I doubted, re-reading the forum posts because NotATether claimed that it is possible to calculate .. NotATether can dispel the myth?
|
|
|
|
Alpaste
Jr. Member
Offline
Activity: 37
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 05, 2022, 03:51:28 PM |
|
Alpaste I also hold this opinion. But I doubted, re-reading the forum posts because NotATether claimed that it is possible to calculate .. NotATether can dispel the myth?
This claim might be not true at all. If it's possible then, why he himself "NotATether" didn't calculate the private key for the puzzle transactions and withdraw its funds?
|
|
|
|
batareyka
Jr. Member
Offline
Activity: 38
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 05, 2022, 03:54:01 PM |
|
Let's wait, maybe NotATether will answer and dispel the myth.
|
|
|
|
Feron
Jr. Member
Offline
Activity: 56
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 09, 2022, 04:27:05 PM Last edit: January 09, 2022, 05:04:56 PM by Feron |
|
Hi all this code guess random public key problem this code is slow play with it and try to improve and speed it up code: import collections import random
EllipticCurve = collections.namedtuple('EllipticCurve', 'name p a b g n h') # here we define our elliptic curve curve = EllipticCurve( 'secp256k1', # curve type # Field characteristic. p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f, # Curve coefficients. a=0, b=7, # Define the base point. g=(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8), # Subgroup order. n=0x000000000000000000000000000000000000000000000000000000000000ffff,######important###### this manipulate public key maximum guess range up and down # Subgroup cofactor. h=1,) # Modular arithmetics application def inverse_mod(k, p): # Returns the inverse of k mod p # returns x such that (x * k) % p == 1 # k <> 0 and p = prime if k == 0: raise ZeroDivisionError('division by zero') # zero division error! if k < 0: # k ** -1 = p - (-k) ** -1 (mod p) return p - inverse_mod(-k, p) # return the inverse # 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 applied 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 (P1 + P2) according to the group law assert is_on_curve(point1) assert is_on_curve(point2) if point1 is None: # 0 + P2 = P2 return point2 if point2 is None: # P1 + 0 = P1 return point1 x1, y1 = point1 x2, y2 = point2 if x1 == x2 and y1 != y2: # P1 + (-P2) = 0 return None if x1 == x2: # if (P1 == P2) m = (3 * x1 * x1 + curve.a) * inverse_mod(2 * y1, curve.p) else: # if (P1 != P2). 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 * P) computed using the double-and-add algorithm assert is_on_curve(point) if k % curve.n == 0 or point is None: return None if k < 0: # k * P = -k * (-P) 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 ECDHE def make_keypair(): # Generate random private-public key pair private_key = random.randrange(10000, curve.n)######important###### this equivalent start public key range manipulate this you up and down start public key range momental start is 10000 decimal public_key = scalar_mult(private_key, curve.g) return private_key, public_key for xxx in range(1000000): aaaa_private_key, aaaa_public_key = make_keypair() bbbb_private_key, bbbb_public_key = make_keypair() if (str("02{:x}".format(*aaaa_public_key))).endswith("7a"): print("aaaa' private key:",hex(aaaa_private_key),"02{:x}".format(*aaaa_public_key),xxx) if (str("02{:x}".format(*aaaa_public_key))) == "029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a": #any public key use this line# i use test key f=open("von.txt","a") f.write(str(aaaa_private_key)+"<-decimal key-"+(str("02{:x}".format(*aaaa_public_key)))+"\n") f.close() if (str("02{:x}".format(*bbbb_public_key))).endswith("7a"): print("bbbb' private key:",hex(bbbb_private_key),"02{:x}".format(*bbbb_public_key),xxx) if (str("02{:x}".format(*bbbb_public_key))) == "029d8c5d35231d75eb87fd2c5f05f65281ed9573dc41853288c62ee94eb2590b7a": #any public key use this line# i use test key f=open("von.txt","a") f.write(str(bbbb_private_key)+"<-decimal key-"+(str("02{:x}".format(*bbbb_public_key)))+"\n") f.close() # aaaa and bbbb now exchange their public keys and verify the shared secret s1 = scalar_mult(aaaa_private_key, bbbb_public_key) s2 = scalar_mult(bbbb_private_key, aaaa_public_key) assert s1 == s2
|
|
|
|
NotATether
Legendary
Offline
Activity: 1708
Merit: 7184
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
January 10, 2022, 04:00:03 AM |
|
Hi all this code guess random public key problem this code is slow play with it and try to improve and speed it up ...
I know this probably sounds very trivial but a good place to start optimization is to convert that Python code to C/C++ using Bitcoin's libsecp256k1 and libbitcoin (I think Bitcoin Core exports its address functions to libbitcoin).
|
|
|
|
|