Pollard's kangaroo ECDLP solver - page 59.

jacky19790729

jr. member

Activity: 82

Merit: 8

Quote from: math09183 on May 03, 2021, 03:25:08 AM

Quote from: ?? on ??

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 Grin

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.
Huh

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://bitcointalksearch.org/topic/half-of-any-bitcoin-crypto-public-key-public-key-half-4455904
https://bitcointalksearch.org/topic/presentation-of-my-ecc-calculator-5202064 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 ....

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: fxsniper on May 09, 2021, 09:44:57 PM

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.

Quote from: fxsniper on May 09, 2021, 10:26:20 PM

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.

fxsniper

member

Activity: 406

Merit: 47

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);

fxsniper

member

Activity: 406

Merit: 47

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

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

@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.

hskun

newbie

Activity: 9

Merit: 0

Quote from: NotATether on May 09, 2021, 08:37:04 AM

Quote from: hskun on May 09, 2021, 08:31:21 AM

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

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: hskun on May 09, 2021, 08:31:21 AM

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

newbie

Activity: 9

Merit: 0

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

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: fxsniper on May 08, 2021, 03:49:18 AM

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.

Quote from: fxsniper on May 08, 2021, 03:49:18 AM

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.

Quote from: peteruhv on May 08, 2021, 09:53:48 AM

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.

peteruhv

newbie

Activity: 2

Merit: 0

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"

fxsniper

member

Activity: 406

Merit: 47

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 ?

fxsniper

member

Activity: 406

Merit: 47

Quote from: bigvito19 on May 06, 2021, 04:57:24 PM

Quote from: NotATether on May 06, 2021, 12:39:15 PM

Quote from: bigvito19 on May 06, 2021, 06:50:22 AM

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]

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on May 07, 2021, 04:42:58 AM

What about the RTX 20s?

Never had one so don't have numbers for it. Even the RTX3090 speed was measured from one of my client's box so I don't have that either.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: NotATether on May 07, 2021, 03:33:26 AM

Quote from: bigvito19 on May 06, 2021, 04:57:24 PM

Quote from: NotATether on May 06, 2021, 12:39:15 PM

Quote from: bigvito19 on May 06, 2021, 06:50:22 AM

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?

A single RTX3090 can do 3 or 4 gigakeys/s, so it's not unreasonable to assume the other RTX 30s can search in excess of 1GK/s too.

What about the RTX 20s?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on May 06, 2021, 04:57:24 PM

Quote from: NotATether on May 06, 2021, 12:39:15 PM

Quote from: bigvito19 on May 06, 2021, 06:50:22 AM

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?

A single RTX3090 can do 3 or 4 gigakeys/s, so it's not unreasonable to assume the other RTX 30s can search in excess of 1GK/s too.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: NotATether on May 06, 2021, 12:39:15 PM

Quote from: bigvito19 on May 06, 2021, 06:50:22 AM

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?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: bigvito19 on May 06, 2021, 06:50:22 AM

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.

bigvito19

full member

Activity: 706

Merit: 111

Quote from: fxsniper on May 05, 2021, 07:25:53 PM

Quote from: bigvito19 on May 05, 2021, 08:56:03 AM

When you run kangaroo what are the speeds on the GTX 1060 and GTX 1050Ti?

I use GTX 1050 not Ti on laptop speed 120-150M

[204.56 MK/s][GPU 165.57 MK/s][Count 2^30.02][Dead 0][07s (Avg 01:28)][34.6/68.0MB]

GTX 1050 and GTX 1050Ti is difference right

GTX 1050Ti may be double speed to high more 50%

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

fxsniper

member

Activity: 406

Merit: 47

Quote from: bigvito19 on May 05, 2021, 08:56:03 AM

When you run kangaroo what are the speeds on the GTX 1060 and GTX 1050Ti?

I use GTX 1050 not Ti on laptop speed 120-150M

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 [2.3s]
[204.56 MK/s][GPU 165.57 MK/s][Count 2^30.02][Dead 0][07s (Avg 01:28)][34.6/68.0MB]

GTX 1050 and GTX 1050Ti is difference right

GTX 1050Ti may be double speed to high more 50%

bigvito19

full member

Activity: 706

Merit: 111

Quote from: WanderingPhilospher on May 01, 2021, 03:16:24 PM

Quote from: NotATether on May 01, 2021, 02:52:23 PM

Quote from: WanderingPhilospher on May 01, 2021, 10:46:01 AM

I don't know anyone mass buying V100s; it is just the example used to solve #120 because that is the type and number of cards that were used to solve #110 and #115.

I feel like #120 is going to be solved by large numbers of older cards lying around in people's garages somewhere, rather than with anything that can be rented with AWS or Vast. Even 100 of any high-end card just seems too expensive for someone with deep pockets to rent in the long run and you can get better results searching with a few thousand of people's Maxwell and Pascal cards (and even Radeons if Kangaroo ever gets ported to OpenCL).

Well, it will be me so I can tell you they are all RTX 20xx and 30xx, but I am using 1 GTX 1060 and 1 GTX 1050Ti to do the tedious work. Wink

EDIT: I'm not running it full time, just here and there, so anyone really has a chance.

When you run kangaroo what are the speeds on the GTX 1060 and GTX 1050Ti?

Topic: Pollard's kangaroo ECDLP solver - page 59. (Read 60095 times)