Thanx!

I do not understand then, why whole crypto industry is in fear of an arrival of quantum computers?

Because what you write there is not known even public key to be cracked?

I read some articles and it is written that private key simply leaked from third-party-companies? Am I right?

So not using third parties one should be safe with cryptocurrency?

Almost sleeping but:  

I read somewhere that wallet address is the public key generated from private key:

34xp4vRoCGJym3xR7yCVPFHoCNxv4Twseo                               wallet address (richest in the world)
0523e522dfc6656a8fda3d47b4fa53f7585ac758cd7c0caa48         decoded wallet address

1P5ZEDWTKTFGxQjZphgWPQUpe554WKDfHQ
00f22f5563839ba6ba5aa8d3726fcbc675cb3e4c9e215b75ef

38UmuUqPCrFmQo4khkomQwZ4VbY2nZMJ67
054a782fe173a0b6718d39667b420d9c8b07e94262578fac8c


I know that public key for ecc secp256k1 is 64 bytes long, why then dcoded wallet has got only 25 bytes???

I try to learn something but I do not understand following:

It is said that bitcoin private keys from any generator are provided in BASE58 format

on this page I found many examples for private keys:  https://bitkeys.work/

It should be that bitcoin uses secp256k1 ECC  ?  So private key is 32 bytes?

here are some decoded private keys into hex from abovementioned page:

L52sDjGxf8Y5NHy5BjTpQHQUjHDjrqErHyTomskefFXrKPdjf7Di                                                        base58
80e91ed90e9a784499a4e37580de2f5d6b622ba96ff1f735f1992ce787575a44d9010c3e5e49               hex

L2HBA8KcR57PYoGCbZmKUNvmhu7SsrupYj172fQAGkgY75sGUjHQ
8096f833ea1ee11688ad8718e37b3ea81e76911eabed36bbeadb42b6e08b669ee4013cd4ac07

KwXvqELPvZUFgFZ5RhWWLQJQrPvEbk6WKktBk5smCqBeLc17uEvQ
80095f3f838b21709382525317062ada9231188e60304eaaf3d287ed7e7a8c825a01252f78ad

WTF, why private key is not 32 bytes long after decoding base58?  But it has got 6 bytes more?
Also 80 at the beginning seems to be very suspicious....

Any clarification will put me back to a sound sleep during the night...

I am a total newbie with GPU calculations so please be patient with my questions.

I have Nvidia Quadro P4000. I need to find private key from public key 256bit ecc.
The Kangaroo seems to be unable to cope with this task. I know it can be supported by GPU but here I do not understand how much of GPU is really used by Kangaroo. What I have seen here it uses maximum a few of tens of GPU threads. But gpu has got thousands of them? Also to be sure Kangaroo is bugless is a bit fantasy. Also difficult to debug. Does Nvidia card need monitor to be connected or to have that special dongle virtual monitor from Aliexpress? How is computer creating screen if nvidia is used for calculations?

So I have this idea, please try to understand and estimate if it is feasible? I want to use whole gpu, 1024 threads or more. Each thread would search in a brutal way the private key in very simple manner: instead of multiplying generator point every time with new possible private key I would start every thread on its own ?? -bit space. It would start from initial "private" key and continue with adding generator point, this would be much faster. After adding generator point (+1 gp) gpu will also check X coordinate if it fits already to public key. Easy to debug. So I would have 1024 gpus performing simple task adding generator point and compare just one coordinate, say X. If it would work but one gpu P4000 is not enough maybe GPU cloud rent for 1000euro for 1 month might be enough? At this moment I have no idea how much time would gpu need to perform one iteration step so I welcome any estimations from you.

I found a little time and uploaded files on:

https://github.com/sky59/Kangaroo-254-bit

I hope I have not broken any rules on github as I am not a regular user of it

If yes, I must be exused as I am toooo old already (edition 1959)

I do not understand why it reads over here I am "Jr.Member" ?

KANGAROO 254 bit
------------------

I spent today whole day to migrate kangaroo 2.2 JLP 125bit  to  254 bits
I keep DP only 64bits as original (to avoid huge changes) I think it should be enough?  (no need for 254 bit mask?)

It seems like a "huge" success but of course I have some questions about the code, if anybody knows the answer (anyway it behaves in a consistend way)

I noticed that hash in the code is just bits  191..128 of x value masked with 17 lsb bits, am I right or I overlooked something?

if the hash is 64bit variable why is it then masked with 17bits lsb?

the code is updated for CPU but GPU should not be affected at all,  I have no CUDA compiler so I can not try it to compile for cuda

if anybody is interested I can upload the code on git (but next Tuesday now I rush on holidays....)


(for k1 curve just folder SECPK1 must be replaced with original)

here is the reason for Rand() not to work:

in BSGS code the function rseed() in Random.cpp is never called

so, without seeding no harvest.....

Here is the story of Check():

JLP wanted to use also for BSGS this Check() function but finally he gave up as Rand() is always returning 0  (zero)
as it was not working also command line switch -check is not implemented so you can not call this Check() function
because Rand() is not used for algorithmus in no way JLP left it unresolved for BSGS 

but for Kangaroo 2.2 125bit the story is different:
the Rand() is used also for algorithmus so JLP must had solved this problem and he did (so far I have not found what was corrected/changed)
now the whole Check() function works properly even for both k1 and r1 curves (different curve-p parameters affecting all mod operations)

b.SetBase16("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F");        k1
b.SetBase16("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");        r1


PS: I hope NotATether will find some day a bit of free time and willingness to forget existing Kangaroo256 code and
instead take JLP Kangaroo 125bit and extend it to the 254bit without any additional changes
(no DP change, no Div() and others optimizations....)

I believe this would be the easiest way, do you agree NAT ?   

In a meantime I found that your updated Div() is faulty, why not to keep original functions? And it seems more functions are faulty that are tested in Check()

you can try this:  (gives wrong results)

I would be probably the happiest man in universe if with all your knowledge and experience just updated 125bit version to 254bit version, just absolutely unnecessary staff without any improvements   then I see your great success!!


 // Div -------------------------------------------------------------------------------------------
  tTotal = 0.0;
  ok = true;
  for (int i = 0; i < 2 && ok; i++) {


    a.SetBase16("D51263D15FC81DE32C5CB69070ABDF3D58A2028184E15F3A6C56EB8A787C81DB");
    b.SetBase16("2AED15B34BE1B98EE4246FB3F447059A");
    // a.Rand(BISIZE);
    //b.Rand(BISIZE/2);
    d.Set(&a);
    e.Set(&b);

 printf("a= %s\n", a.GetBase16().c_str());
 printf("b= %s\n", b.GetBase16().c_str());
 printf("d= %s\n", d.GetBase16().c_str());
 printf("e= %s\n", e.GetBase16().c_str());

    t0 = Timer::get_tick();
    a.Div(&b, &c);
 printf("a/b= %s\n", a.GetBase16().c_str());   
 printf("rem= %s\n", c.GetBase16().c_str());
   
    t1 = Timer::get_tick();
    tTotal += (t1 - t0);

    a.Mult(&e);
    a.Add(&c);
    if (!a.IsEqual(&d)) {
     ok = false;
      printf("Div() Results Wrong \nN: %s\nD: %s\nQ: %s\nR: %s\n",
        d.GetBase16().c_str(),
        b.GetBase16().c_str(),
        a.GetBase16().c_str(),
        c.GetBase16().c_str()
        
      );
      return;
    }

yes it is, he informed me already about some problems and I should wait until he corrects them

but as I have written already, I could not resist and I migrated it to R1 curve just to try what it does...

yes, you are right, as it is now it behaves a bit non repetitive way, for me it found the keys but solving the same problem more time the time to resolve was from zero (!) seconds to minutes, but I tried only fewer bits search as it was considerably slower than JLP 125b version searching more bits range

I also noticed he changed DP mask meaning (not from left to rigth as original but from right to left) and he "regrets" this as it made me confused

also I noticed there is a problem when having public key in configuration file to solve in 03 mode (only x coordinate)  something is wrong as it falsely reports "point not lie on curve", when in 04 mode it seems to be ok

but let us see and wait if NotATether manages to bring it to life

I was already thinking if there is any way as to test the program before starting it for months..., would it be a change to provide instead of random numbers where algo starts some precalculated values so program would find a test private key in hours? or is there already a way to test the code?

Sorry, I do not understand abbreviation "IMO"  what does it mean?

Thank you for exhausting explanation!

I hope I understand correct both JLP and "cuda" BSGS work up to 256bit size search

Maybe you noticed I migrated JLP bsgs from curve k1 to r1. It was success. I started it for interval almost 256bit:
1000000000....0000000
EFFF.....................FFFFF

I know it will probably not succeed in this century but it is not impossible I want to try to find private key for gr**npass

I continue to work to migrate also  Kangaroo256 to r1 curve but I was told by the author to wait a bit until he updates hastables (?)
Anyway, I migrated cpu part already just to see how is the behaviour of the code. I already reported him my findings, it is here on the forum

Thank you

If you feel wasting your time you should not react at all

Anyway, your answer is like saying baby steps must find it (what) first. Total bullshit.

I do not know if you are joking or serious.
Your answer is totally useless and does not even touch any of my questions.
Claiming that if you find key in range then you are sure 100% is there is childisch and raising my doubts for your mental health

Do you mean to say that bsgs algo gives you 100% information if key is or is not in s given range k1-k2?

Or you say bsgs would find private key even if k1 k2 interval is incorrect?

I had a closer look at JLP bsgs code (not cuda you speak about) and it seems there is no limit to 125 or 128 bit for search interval? Is bsgs by nature searching whole 256 bit range?

Does it search whole 256bit space? Or limited only to few lsb bits?

just to came to my mind:

There is a Int::Check() inside (may be under the switch you mentioned) but I put it in main to call it always at start

Only in JLP 125b Kangaroo it works and passes all tests. For all other versions it always fail, first on Div()

I want to try to find the reason why...

@ NotATether:

I know and keep in my mind some more work is needed on 256b version.
But I could not resist and migrated your code to R1 curve just to see...

So I changed parameters for curve and added/changed  a & b parameters  (K1 a=0 b=7)
For R1 much more strange numbers

I changed also precalculated constants like "R2o" and some more

Also a bit bigger task was copy/paste from my previous R1 codes for Montgomery reduction (3x)

With text editor I removed from vxcproject everything regarding CUDA and deleted WITHGPU globalflag

So I compiled it on Windows and it works in general, here are the findings: (just to share info with you now)

- in "printf" for DP size one X slipped to the right a few positions 
- it seems you changed DP meaning comparing to JLP code? his mask is from left like FFFE000.....
   and yours is from right like .....00000007  ??  (or it is a small bug?)
   
- the bigest surprise for me was that my altered code (99,99999% yours) is happy with input conf file
  and provided public key "lies on the curve" but your code as it is complains that it "not lie on the curve"
  at this moment I do not know if CPU always makes this check so in your case maybe GPU calculates also this
  input check and it is correct?

My code even finds a private key but (of course) it is slower than JLP 125b version. What I do not understand is
that JLP behaves everytime about the same, but your version finds solution for the same config input file in time
between, say, zero (!) time to 5 minutes  (?)


I was also thinking how it would be possible to check the program. Do you think it would be possible instead
of those random numbers to use some precalculated values in program so it can quickly find a test private key?
This only for testing reasons.

I keep my fingers crossed for your work! 



 

Are you ZenulA?

I had a look today at the 256b code and I will try tomorrow to migrate it to the r1 curve. First step only cpu code.

Or should I wait? Some more work is neede from you on this 256b code?

Thanx for info!

EDIT: So it is not able to search 254bits yet?