Pollard's kangaroo ECDLP solver

[fxsniper]

Ok, the 204.56 MK/s and 165.57 MK/s are those 2 speeds are added together to equal 370.13 MK/s?

No. The first value on the left is the combined speed of both the CPU and GPU.

The second value (165) is measuring the GPU speed only. it means the CPU speed is actually about 39 MK/s.

Oh ok then, so what gpu's can go at least or close to 1 billion keys with kangaroo?

Sorry for run at begin CPU is hike  normal GPU run  110-130 MK/s

SolveKeyCPU Thread 4: 1024 kangaroos
GPU: GPU #0 GeForce GTX 1050 (5x128 cores) Grid(10x256) (32.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.32 kangaroos [3.4s]
[153.63 MK/s][GPU 124.59 MK/s][Count 2^31.55][Dead 0][22s (Avg 698.857y)][95.9/131.1MB]


kangaroo without GPU is very slow
kangaroo with GPU is high up  10x  ten time CPU
kangaroo with GPU is power


DP size: 10 [0xFFC0000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 5: 1024 kangaroos
SolveKeyCPU Thread 6: 1024 kangaroos
SolveKeyCPU Thread 4: 1024 kangaroos
SolveKeyCPU Thread 2: 1024 kangaroos
SolveKeyCPU Thread 3: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 7: 1024 kangaroos
[24.12 MK/s][GPU 0.00 MK/s][Count 2^29.16][Dead 0][28s (Avg 08:43)][19.9/50.5MB]

[fxsniper]

Reference with script python kangaroo
http://bitchain.pl/100btc/pollard_kangaroo.txt

(now host down) backup
https://github.com/secoc/Pollard-Rho-kangaroo/blob/master/Pollard_Rho_kangaroo_with_Python2.7_demo.py
http://fe57.org/forum/thread.php?board=4&thema=1#1


What is DP_rarity ?
DP_rarity = 1 << (problem - 2 * kangoo_power) // 2 - 2

Is DP_rarity  same  DP method  (distinguished point DP) right?

if P.x % DP_rarity == 0:

What is code check ? Modulus to zero  this mean collision ?

[peteruhv]

Where are people finding the compressed or uncompresssed public keys for the puzzle transactions?

Additionally, what settings are people using on an RTX 3070, I am only getting 252.33 MK/s. I see people with much more, Currently using "-g 128,256"

[NotATether]

What is DP_rarity ?
DP_rarity = 1 << (problem - 2 * kangoo_power) // 2 - 2

Is DP_rarity  same  DP method  (distinguished point DP) right?

Yeah this is just a fancy way of making a DP mask.

if P.x % DP_rarity == 0:

What is code check ? Modulus to zero  this mean collision ?

No it checks whether the point is a DP with its x-coordinate.

Where are people finding the compressed or uncompresssed public keys for the puzzle transactions?

Every fifth transaction starting at #65 also has a spending transaction that reveals the public key.

[hskun]

I tried to
make gpu=1 ccap=53 all
compile on nVidia jetson nano, but since it is ARM architecture, there is no x86 -m64 -mssse3, and i removed  -m64 -mssse3 the compile has error.
Has anyone tried to compile on ARM?

GPU: 128-core NVIDIA Maxwell™ architecture-based GPU
CPU: Quad-core ARM® A57
Memory: 4 GB 64-bit LPDDR4; 25.6 gigabytes/second

[NotATether]

I tried to
make gpu=1 ccap=53 all
compile on nVidia jetson nano, but since it is ARM architecture, there is no x86 -m64 -mssse3, and i removed  -m64 -mssse3 the compile has error.
Has anyone tried to compile on ARM?

GPU: 128-core NVIDIA Maxwell™ architecture-based GPU
CPU: Quad-core ARM® A57
Memory: 4 GB 64-bit LPDDR4; 25.6 gigabytes/second

Kangaroo uses some Intel assembly instructions baked inside the integer classes so you'd have to find their ARM equivalents and put a macro in them like this:

Code:

void Int::add(Int& a, In& b, Int& c) {
#ifdef ARM_CPU
/* Arm instructions */
#else
/* Intel instructions */
}

And then compile with ARM version of GCC or cross-compile using Clang.

[hskun]

I tried to
make gpu=1 ccap=53 all
compile on nVidia jetson nano, but since it is ARM architecture, there is no x86 -m64 -mssse3, and i removed  -m64 -mssse3 the compile has error.
Has anyone tried to compile on ARM?

GPU: 128-core NVIDIA Maxwell™ architecture-based GPU
CPU: Quad-core ARM® A57
Memory: 4 GB 64-bit LPDDR4; 25.6 gigabytes/second

Kangaroo uses some Intel assembly instructions baked inside the integer classes so you'd have to find their ARM equivalents and put a macro in them like this:

Code:

void Int::add(Int& a, In& b, Int& c) {
#ifdef ARM_CPU
/* Arm instructions */
#else
/* Intel instructions */
}

And then compile with ARM version of GCC or cross-compile using Clang.

yes, I see kangaroo use Intel __builtin_ia32_addcarryx_u64  _addcarry_u64 etc.
I try to search the way to replace those functions.
Thanks.

The follow error code:

Code:

In file included from SECPK1/IntGroup.h:21:0,
                 from SECPK1/IntGroup.cpp:18:
SECPK1/Int.h: In function ‘void imm_mul(uint64_t*, uint64_t, uint64_t*, uint64_t*)’:
SECPK1/Int.h:253:32: error: ‘__builtin_ia32_addcarryx_u64’ was not declared in this scope
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:279:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c, _umul128(x[1], y, &h), carry, dst + 1); carry = h;
       ^~~~~~~~~~~~~
SECPK1/Int.h:253:32: note: suggested alternative: ‘__builtin_isnand64’
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:279:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c, _umul128(x[1], y, &h), carry, dst + 1); carry = h;
       ^~~~~~~~~~~~~
SECPK1/Int.h: In function ‘void imm_imul(uint64_t*, uint64_t, uint64_t*, uint64_t*)’:
SECPK1/Int.h:253:32: error: ‘__builtin_ia32_addcarryx_u64’ was not declared in this scope
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:298:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c,_umul128(x[1],y,&h),carry,dst + 1); carry = h;
       ^~~~~~~~~~~~~
SECPK1/Int.h:253:32: note: suggested alternative: ‘__builtin_isnand64’
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:298:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c,_umul128(x[1],y,&h),carry,dst + 1); carry = h;
       ^~~~~~~~~~~~~
SECPK1/Int.h: In function ‘void imm_umul(uint64_t*, uint64_t, uint64_t*)’:
SECPK1/Int.h:253:32: error: ‘__builtin_ia32_addcarryx_u64’ was not declared in this scope
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:318:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c, _umul128(x[1], y, &h), carry, dst + 1); carry = h;
       ^~~~~~~~~~~~~
SECPK1/Int.h:253:32: note: suggested alternative: ‘__builtin_isnand64’
 #define _addcarry_u64(a,b,c,d) __builtin_ia32_addcarryx_u64(a,b,c,(long long unsigned int*)d);
                                ^
SECPK1/Int.h:318:7: note: in expansion of macro ‘_addcarry_u64’
   c = _addcarry_u64(c, _umul128(x[1], y, &h), carry, dst + 1); carry = h;
       ^~~~~~~~~~~~~
Makefile:80: recipe for target 'obj/SECPK1/IntGroup.o' failed

[NotATether]

@hskun

You might find these two resources helpful:

https://developer.arm.com/architectures/instruction-sets/simd-isas/neon/intrinsics:  This is ARM's NEON intrinsics reference.

https://docs.microsoft.com/en-us/cpp/intrinsics/arm-intrinsics?view=msvc-160: This is Microsoft's list of NEON intrinsics so you can compare if any are missing from the ARM list, some Intel intrinsics had to be faked on Windows because it did not have them natively, so hat may be the case for ARM too.

According to https://gcc.gnu.org/onlinedocs/gcc-4.4.1/gcc/ARM-NEON-Intrinsics.html you may have to pass -mfpu=neon to use them.

[fxsniper]

I try Pydroid 3 - IDE for Python 3 to compile both kangaroo and bitcrack on mobile phone android
still error all
may be good for canc ompile everywhere

[fxsniper]

I would like to know tame and wide that solve puzzle #110 and puzzle #115
Did anyone know?

puzzle #110
tame  = ?
wild  = ?

puzzle #115
tame  = ?
wild  = ?

just want to know example of tame and wild  for high bits is on high or low range


I looking for line that calculate   private key = tame - wild (or  private key = wild - tame ) on kangaroo.exe
where is this line code


this line is check compare right
endOfSearch = CheckKey(Td,Wd,0) || CheckKey(Td,Wd,1) || CheckKey(Td,Wd,2) || CheckKey(Td,Wd,3);

[NotATether]

I try Pydroid 3 - IDE for Python 3 to compile both kangaroo and bitcrack on mobile phone android
still error all
may be good for canc ompile everywhere

Again, you cannot just stick it in an Android IDE and press Compile; you must substitute the Intel instinsics with ARM, since all mobile phones have ARM cores not x86 cores.

I looking for line that calculate   private key = tame - wild (or  private key = wild - tame ) on kangaroo.exe
where is this line code

this line is check compare right
endOfSearch = CheckKey(Td,Wd,0) || CheckKey(Td,Wd,1) || CheckKey(Td,Wd,2) || CheckKey(Td,Wd,3);

The third parameter toggles one or both of the Td,Wd to be negative mod the secp256k1 order so barring these negative mods there is only one Td,Wd pair that'll collide for any given private key.

I don't think information about the numerical values of Td,Wd will be helpful without research into the math properties of each subsequent pair or kangaroos.

[jacky19790729]

2548/2 = 1274
2548/10 = 254.8
2548/100= 25.48
2548/1000= 2.548

next
10 - 2.548 = 7.452
....

Looks like a math from primary school  
Do you write in English by yourself or you use translator? It is difficult to understand you because you do not use full sentences, just a few words all the time.
At the end - what do you say you are able to accomplish? Find private key from public key (on any range)? What database you have - database of public keys in some range? Please, for the moment, think what you want to write and write it down slowly and carefully, maybe use google translator if you need.
 

I had understand his idea.....
but  #120  private key  is unknown number...this method must know unknown private key number is even or odd ..
#120 ( we can't know private key is even or odd from public key )
CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630 , 2B195386BEA3F5F002DC033B92CFC2C9E71B586302B09CFE535E1FF290B1B5AC

https://bitcointalk.org/index.php?topic=4455904.0
https://bitcointalk.org/index.php?topic=5202064.0 ECC Calculator
ex:
public key
4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97 , 12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A

Code:

use ecc_double_point ( G * 1/2 ) 

4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97 , 12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A     (20)
A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7 , 893ABA425419BC27A3B6C7E693A24C696F794C2ED877A1593CBEE53B037368D7     (10)
2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4 , D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6  (5)
5699B93FC6E1BD29E09A328D657A607B4155B61A6B5FCBEDD7C12DF7C67DF8F5 , 3EB81178EBCDAB6894D1ACB3196FD8B7D5A3CC237988CD5AF7CC70F98CC978A7    ( 2.5 )
1B53B6CD7378AD80BFE00A7737F8FD1FC3A417FD80A5F334B1793E40D09AC841 , 0D524B528812140D7D0B8314DDCED0D0B5B5DF618A5C4B4EF67E0C8079EE8061     ( 1.25 )
D06A2686686048A42F1DF9F46D376DEEC6F22D3DECF7659137FB02F779CAB2B8 , C607576EC851D8C049CA0782C9F2EE71B657D1857884D1D0BC8EA79ADEA91779     ( 0.625 )
all point lies on the elliptic curve

if we can know unknown number is even or odd  
 ( G public key  only use  + - * /  Addition, subtraction, multiplication and division operator  , can't use modulus  %  )
bitcoin private key will can crack from a public key ....

[hskun]

you do not know the private even or odd.
you can find the public key even or odd.
https://learnmeabitcoin.com/technical/images/public-key/public-key-compressed.png

2548/2 = 1274
2548/10 = 254.8
2548/100= 25.48
2548/1000= 2.548

next
10 - 2.548 = 7.452
....

Looks like a math from primary school  
Do you write in English by yourself or you use translator? It is difficult to understand you because you do not use full sentences, just a few words all the time.
At the end - what do you say you are able to accomplish? Find private key from public key (on any range)? What database you have - database of public keys in some range? Please, for the moment, think what you want to write and write it down slowly and carefully, maybe use google translator if you need.
 

I had understand his idea.....
but  #120  private key  is unknown number...this method must know unknown private key number is even or odd ..
#120 ( we can't know private key is even or odd from public key )
CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630 , 2B195386BEA3F5F002DC033B92CFC2C9E71B586302B09CFE535E1FF290B1B5AC

https://bitcointalk.org/index.php?topic=4455904.0
ex:
public key
4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97 , 12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A

Code:

use ecc_double_point ( G * 1/2 ) 

4CE119C96E2FA357200B559B2F7DD5A5F02D5290AFF74B03F3E471B273211C97 , 12BA26DCB10EC1625DA61FA10A844C676162948271D96967450288EE9233DC3A     (20)
A0434D9E47F3C86235477C7B1AE6AE5D3442D49B1943C2B752A68E2A47E247C7 , 893ABA425419BC27A3B6C7E693A24C696F794C2ED877A1593CBEE53B037368D7     (10)
2F8BDE4D1A07209355B4A7250A5C5128E88B84BDDC619AB7CBA8D569B240EFE4 , D8AC222636E5E3D6D4DBA9DDA6C9C426F788271BAB0D6840DCA87D3AA6AC62D6  (5)
5699B93FC6E1BD29E09A328D657A607B4155B61A6B5FCBEDD7C12DF7C67DF8F5 , 3EB81178EBCDAB6894D1ACB3196FD8B7D5A3CC237988CD5AF7CC70F98CC978A7    ( 2.5 )
1B53B6CD7378AD80BFE00A7737F8FD1FC3A417FD80A5F334B1793E40D09AC841 , 0D524B528812140D7D0B8314DDCED0D0B5B5DF618A5C4B4EF67E0C8079EE8061     ( 1.25 )
D06A2686686048A42F1DF9F46D376DEEC6F22D3DECF7659137FB02F779CAB2B8 , C607576EC851D8C049CA0782C9F2EE71B657D1857884D1D0BC8EA79ADEA91779     ( 0.625 )
all point lies on the elliptic curve

if we can know unknown number is even or odd  
 ( G public key  only use  + - * /  Addition, subtraction, multiplication and division operator  , can't use modulus  %  )
bitcoin private key will can crack from a public key ....

[fxsniper]

bitcoin private key will can crack from a public key ....

it not easy (never happen)

not yet have any record for both bitcrack and kangaroo can crack on real key
kangaroo still can use on puzzle only (on low bit)

if crack mean calculate, it not correct at all

because method to use now is not calculate back to private key or calculate reverse it
kangaroo no any calculate to reverse key direct

kangaroo still RANDOM at all

now we still using method bruteforce on kangaroo
compare with bitcrack bitcrack use scan every private key on keyspace range

but kangaroo use method random by jump  may be call smart random by using algorithm
if you read code and know how it works, you can see random command on kangaroo code work for random key

kangaroo not work with 256bit real key , until kangaroo scan to close up to nearly key around under 2**70 far form key and kangaroo jump to that fit center to key too
kangaroo still works only on low range low keyspace because still RANDOM it is slow like bitcrack

[fxsniper]

What is fast between use kangaroo scan all and split?

between

kangaroo scan whole range 2**120   (start from 2**119 to end 2**120)
waiting kangaroo jump

and

kangaroo scan keyspace 2**60  size and split all to 2**60   (2**60 x 2**60 = 2**120

between two scan what is method will scan found first
87600 minute (2 month)


some my test about keyspace

small key space
start = 1
stop = 1000
key = 500
result = found fast

small key space
start = 1
stop = 1000
key = 200
result = found fast

small key space
start = 1
stop = 1000
key = 800
result = found fast


large key space
start = 1
stop = 1000000
key = 100
result = very slow
(this case bitcrack will found first)


large key space
start = 1
stop = 1000000
key = 1000
result = very slow
(this case bitcrack will found first)

large key space
start = 1
stop = 1000000
key = 500000
result = very slow

large key space
start = 1
stop = 1000000
key = 999000
result = very slow

test keyspace (key = on center)
2**5 = slow
2**10 = slow
2**20 = fast
2**30 = fast
2**40 = fast
2**50 = very slow
2**60 = very  slow
(dp = default or dp = 10  nearly result)


do not believe me, test you self first to know face

you can see large key space kangaroo will be random to all keyspace
in case key is nearly start point, if use bitcrack will be found key immediately
key under the nose , but kangaroo scan to alll keyspace and found


can possible to make double agent kangaroo
first agent kangaroo random to keypsace and next will original kangaroo  and scan normal
something like that

[WanderingPhilospher]

What is fast between use kangaroo scan all and split?

between

kangaroo scan whole range 2**120   (start from 2**119 to end 2**120)
waiting kangaroo jump

and

kangaroo scan keyspace 2**60  size and split all to 2**60   (2**60 x 2**60 = 2**120

between two scan what is method will scan found first
87600 minute (2 month)


some my test about keyspace

small key space
start = 1
stop = 1000
key = 500
result = found fast

small key space
start = 1
stop = 1000
key = 200
result = found fast

small key space
start = 1
stop = 1000
key = 800
result = found fast


large key space
start = 1
stop = 1000000
key = 100
result = very slow
(this case bitcrack will found first)


large key space
start = 1
stop = 1000000
key = 1000
result = very slow
(this case bitcrack will found first)

large key space
start = 1
stop = 1000000
key = 500000
result = very slow

large key space
start = 1
stop = 1000000
key = 999000
result = very slow

test keyspace (key = on center)
2**5 = slow
2**10 = slow
2**20 = fast
2**30 = fast
2**40 = fast
2**50 = very slow
2**60 = very  slow
(dp = default or dp = 10  nearly result)


do not believe me, test you self first to know face

you can see large key space kangaroo will be random to all keyspace
in case key is nearly start point, if use bitcrack will be found key immediately
key under the nose , but kangaroo scan to alll keyspace and found


can possible to make double agent kangaroo
first agent kangaroo random to keypsace and next will original kangaroo  and scan normal
something like that

None of what you said makes sense....if you could run one 2^60 keyspace range in 1 second, how many days would it take to run 2^60 ranges??
Random = starting point for each tame and wild then they jump uniformly.
You should really stop comparing the two programs, they are different.

[math09183]

you do not know the private even or odd.
you can find the public key even or odd.

hahahahhahaha 

Guys, I do not know who hskun and fxsniper are, if they are this same person in real or not, but please... stop posting so stupid things. Stop dreaming that you will suddenly have an IDEA and break ECDSA. You have no idea about Bitcoin and you have no idea about math behind it. Please, stop compromise yourself and waste internet for your imaginations.
I do not know... maybe go to back to school or find a legal job. I understand you would like to get free easy money, buy you have no skills, no knowledge. Wrong way

[fxsniper]

None of what you said makes sense....if you could run one 2^60 keyspace range in 1 second, how many days would it take to run 2^60 ranges??
Random = starting point for each tame and wild then they jump uniformly.
You should really stop comparing the two programs, they are different.

I just think if still run kangaroo all keyspace 2**120 still can not solve his puzzle
I not have power with Tesla V100 or any GTX 30xx
I just got new GPU GTX 1080 (not ti) for working graphics 3D render
just looing for strategy for small card can do. and can run on some free time
if method notworking I change to other method can possible

[fxsniper]

hahahahhahaha 

Guys, I do not know who hskun and fxsniper are, if they are this same person in real or not, but please... stop posting so stupid things. Stop dreaming that you will suddenly have an IDEA and break ECDSA. You have no idea about Bitcoin and you have no idea about math behind it. Please, stop compromise yourself and waste internet for your imaginations.
I do not know... maybe go to back to school or find a legal job. I understand you would like to get free easy money, buy you have no skills, no knowledge. Wrong way

Sorry I am not same person with hskun,

Don't judge people is better. (open freedom no judge)

Really, I know it can not break bitcoin. it can not possible to crack very large number. (right can not break ECDSA.)

just try challenge with puzzle not real bitcoin 256bit

I don't think is free, every thing have cost

if not do challenge is bored, challenge  puzzle help to spend time
record puzzle #115 on wikipedia  that record for destroy records to new one better

if no one try to crack bitcoin, it worst , it make bitcoin stop to continue develop, upgrade to more secure
(try crack to make it better)

I think just like research Vulnerability (Bug Bounty Programs) for fun
(Ten-year-old receives reward for finding Instagram bug)

comment like this make challenge people, make more people do it
good way to stop is support to do until leave themselves (give up)  (you know already it is never happen and it is can not possible)

talk about it make activity

I may be give up in future (sure, possible) but not for this time (however I have limited time)

(news) IRS Hiring Hackers Who Can Crack Bitcoin Wallets , I just want to apply this job (legal job)
Sorry just kidding

Think positive please.

[NotATether]

(news) IRS Hiring Hackers Who Can Crack Bitcoin Wallets
~

I believe they are looking for people who can exploit vulnerabilities in hardware wallets, not general-purpose private key crackers.

However, the consensus among security researchers appears to be that hardware wallets have very few vulnerabilities to successfully hack them, which means that the IRS's effort will likely ultimately end up being futile.