Topic: Kangaroo 254bit (secp256r1 / P256) (Read 659 times)

I don't think you broke any github rule (I'm not even sure which one you are referring to lol). You do not have enough activity for Member rank (min. 60).


Someone paid/is about to pay me (not really big money at all, around the ballpark of $100) to parallelize the division keysplitter I made so there's that.

Are you working on anything new with public keys?

yes, you can add the rseed()here:

.....
int main(int argc, char* argv[]) {

  // Global Init
  Timer::Init();
  rseed(Timer::getSeed32());

.....

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 ?   

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

I admit I never tested it on Windows, but felt the need to update the printf statements for Windows because I altered the DPmask. I now know that that is a terrible idea. N.B: *never try to make your own DPmask* because usually it'll just screw up the search.


JLP has a switch inside the program that runs a self-test containing add/mul/hashing/pk finding operations and reports the results. It's more of a benchmark program than a tester however, but at least it will throw an error and about if the operation fails.

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



 

Well, you had better wait, because at the moment it looks like there's a huge mountain of tasks for me to clear first before I can come back to this one.

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?

*me  

When I have time (as this is a pet project, I have more important work to do at the moment), i'll probably end up reverting the hashtable code and just extend all the 128-bit structs to 256-bit which will give us 254 bits of useable searching (the two bits at the right/end are reserved for other functions, in JLP kangaroo and also my kangaroo.

Thanx for info!

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

Yea, it is limited to search 125 bit.

This person attempted to make it search 256 bit but it needs a little more work to it. https://github.com/ZenulAbidin/Kangaroo-256

:-)
Does it mean that 128 MSB bits in search interval must be fixed?
If yes then what for is it worth?

EDIT:

I tried to put in config file 256 bit range and program was not complaining even shoved range as 2^256

what this limit means exactly??

CORRECTION: it is written in Readme file 125bit (not 128 as I wrote previously) so even more confusing.....

That mean its limited to search 128 bits.

Today I sucessfully migrated JLP kangaroo to R1 curve without gpu support to be able to compile on windows.
It was necessary in project C/C++ properties to remove flag WITHGPU. Then it compiled and it works.
I read in readme file that kangaroo is only for 128 bits. What does it mean?

I forgot to mention that AMD GPUs have nothing to do with the AMD CPUs... they have no relation to each other. So basically if you have only an AMD CPU but no GPU in your box then you got no GPU support.

Also if you have one of those machines with the "AMD A1" sticker or similar then you have both an AMD CPU *and* an AMD GPU stuffed inside together.

None of these have CUDA support however (which is strictly a GPU technology and has nothing to do with x86, x86_64, etc.)

CUDA technology was added inside GeForce 8000 (Tesla) and newer. However you will need GeForce 600 (Kepler) or newer to compile JLP Kangaroo with the latest CUDA - the one designed for Windows 10 and stuff.

Thank you both guys!

I thought AMD cpu... my mistake, I know only nvidia is supported

Today I had a closer look at kangaroo. Now I understood how JLP designed it.
For linux " make all" compiles without gpu support.

On windows I removed from vc.sln file all "cuda" entries so also windows compiled  exe without gpu support.

Anyway, if I understand correct you have to in command line use switch - gpu if you want to use it otherwise by default only cpu is used.

I have one quite old nvidia card. How many gpu cores would be worth to use it? All gpu cores can be used? Hundreds or even thousands?

I looked also in  .cu files and they look to me very familiar. So I am sure I can update them for r1 curve as well.

Cuda compiler is for all versions of nvidia cards? Then only drivers to make interface to cpu depend on gpu version?