Topic: Kangaroo 254bit (secp256r1 / P256) (Read 731 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?

AMD gpus only support the GPU programming technology "OpenCL", however the hardware does not support the "CUDA" technology that is required to run Kangaroo with GPUs. That's why it only works with NVIDIA cards.

BSGS and Kangaroo are focussing on different aspects to solve the disrecte logarithm problem. BSGS is about speeding up by using a huge lookup table. So you need a lot of RAM for fast solution finding. The more RAM you have, the more entries you have in the lookup table the faster is BSGS.

Kangaroo on the other hand is the way to go if you have more processing power and less ram.

https://en.m.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm

thanx for helping me!

Do you think kangaroo might be better than bsgs?  Anyway, I will try to compile it and if "yes" I adapt it to the R1 curve  (simply replacing a few files I have already in bsgs for R1)

What do you mean by " not working with OpenCL"?  AMD is not standard x86 architecture?

Etar's code in basic is unreadable for me as he in fact programmed in x86 assembler inlining milions asm instructions inside basic code.... I can not imagine adapting this to R1 curve

Yeah, JLP kangaroo will work without CUDA (that's actually the default compilation mode anyway so if you just type make that's what you get).

It currently doesn't work with OpenCL (so no AMD support).

BSGS doesn't have any GPU support whatsoever, but I'm sure you saw Etar's thread where he made a version for CUDA (win64) (here).

It is clear that secp must be correct

I could not wait until tomorrow so I corrected windows version. Added "a" and "a*z*z" into double functions. It works now!! JLP bravo!

If I calculate k1k2 interval and needed time to find k it is equivalent as if one brutal force try would last about 5picoseconds. On stupid windows 2core 8gb very old hp notebook. I needed to decrease 4 times number of baby steps otherwise pc crashed.

Now I start to think about JLP kangaroo. The files seems to be the same as for BSGS regarding k1 curve.
This kangaroo has got cuda support. Then I do not understand why also normal cpu code for curve is there? What is graphic card suppose to do? Can I compile JLP kangaroo just for cpu without cuda?

If your point doubling funcs are not written for general-purpose SEC2 curves then it doesn't matter what interval you choose, the key will never be found.

So you should change this part of the double function:


to be +a, instead of 0 (same with doubledirect func).

Thnx
I also already found out about affine/projective coordinates

So it means z is only denominator

There are two functions for point doubling in SECP256K1. cpp:
Doubledirect - in affine coords, here I must add only "a" from ecc equation to already existing 3*x*x  which is derivation of ecc equation   x*x*x

Double - in projective coords, here I must add a*Z*Z
The fun is it is already in JLP code just he forced z*z to be zero because for k1 "a" is zero in equation, so also him must have used someone,'s code and optimized it for k1

So now I need to return back to full code for nonzero a in ecc equation

Does it mean that if I provide wrong k1 k2 interval the k is not found?
But I still can provide huge interval? It will be slow but there is a non zero chance?

Kangaroo is better? I can simply replace few files and it is done....

Tomorrow I want to try bsgs with corrected doubling, i let you know later

BSGS is supposed to be used when you know a private key is between a minimum and maximum value, of course it is not efficient if you don't have a bounding range because 256-bit space is too large to search.


Does this mean you basically forgot to add terms for "a" (which is 0 for k1)?


JLP must has disappeared so it's unlikely you can reach him.

---

Warning - rocket math ahead

"Guide to Elliptic Curve Cryptography" (DOI 10.1.1.394.3037) says that Z is the third of a set of three Jacobian (the book calls them projective) coordinates (so X,Y, and Z) coordinates which can be "transformed" from normal - affine, in book terminology - (x,y) coords. i.e. from the elliptic curve in 3D to 2D.

So basically:

y2 = x3 + ax + b -- this we already know.

Apprently, it can also be represented as Y²Z = X³+aX Z² +bZ³ (according to example 3.19, page 87).

So the Z is probably anything that reduces the above to "y2 = x3 + ax + b" - so it's always 1, in other words. Not sure why you think you need the Z coord though, it's not necessary for r1.

If you ever manage to get a copy of the book (whether by google search or just through sci-hub) you'll also be able to see this info for yourself.

Then can I select as interval whole 256 bit space (0000000....fffffffff....) and to leave it running forvever?

Then I start to doubt if bsgs algo is somehow usefull?

Wiki does not say anything about knowing interval before? Neither do any other docs, they just say select random interval. I do not know if Jean would be willing to communicate this?

OOOOOPS!
I just realized I have not finished yet!
Yes, Montgomery math is ok, also reading 149 public keys is confirmed they lie on the r1 curve, it is simple test that y*y=x*x*x+a*x+b for each public key

But for k1 a=0 and b is 7, so I think I have to "unoptimize" points add, double functions to count also with a*x and b as I did for entry public keys test

But I do not understand what is the z-coordinate of a point. Does anybody know? JLP surely knows but can I contact him somehow?

EDIT: It seems z is the sign of y coordinates?
Also, probably a, b will not have any impact on point addition but only on point doubling where a is coming into calculations
It seems b does not have any effect on points arithmetic? It doesnot come into any calculations?...

Hey, sorry for the late reply, but since the README of BSGS says that k must lie between the k1..k2 interval, the private key must definitely be in this range.

I do not know. I do not think so. R1 is used in Europa for digital signature so called gr**npass.

r1 is less difficult to find a privkey ?

Thx.

Thank you for info!

In a meantime I managed to compile also on Ubuntu. Because windows is stupid as it crashes though there is enough RAM and also limits cpu usage for BSGS.

I was a bit surprised as I needed to make some changes to code from JeanLucPons and add some "includes". As he would never translated it on Linux (ubuntu?)

Now on ubuntu "top" shows 800% cpu usage and 76% ram usage. Also fans started to boost :-)

My question was about k1-k2 interval. Does this interval have to be the exact one in which searched k is lying?

Here is the part of in.txt file, i ask about 2 and 3 line
First line means amount of baby steps in memory?
(the lines probably shows wrapped as they are 64 bytes long, 04 start three public codes for r1 curve)

40000000
eaac53eac48add30e17961474c191fbdea28461b545aa12a0000000000000000
eaac53eac48add30e17961474c191fbdea28461b545aa12affffffffffffffff
046f1950fd44f3d00c59585fb142cfb0fb1bdeab911c85ef737f5e8b9c315863f2bca59ea5eac6f 62a55f0f19fe4c28a73cdbbf92c25f55712ec18ef51b3d3b32e
04e44b586cebbe46e51c140bb534dd6baacb8aa8dce997463a6e083dc0d29c9952f37c13bcd631f 675cba91ed2a5a7b332e4a1a30b20402af8c951213f7e70dde6
0451d3cfb24f71cd8d6f335cdd8e0bc70ec442493e7963d489049517239baa19be9c9294fbc5014 66e6f96190b8527d134c37672caa6fd3ff6ec309426264ae992

If you are referring to


Then you should use the same size for secp256k1 because larger steps means more time is spent searching for keys per step. Smaller steps means you're wasting GPU cycles.

Done!
I sucessfully migrated from k1 code to r1 elliptic curve. Now it even passes check that all provided public keys lie on curve r1.
It was necessary to perform 9 reduction steps instead of 2 in Montgomery reduction

I modified this code https://github.com/JeanLucPons/BSGS

Still I have a question. Do I have to provide interval for k?
Or it can be whatever interval? I use BSGS code.

Are you sure that you can't just write Montgomery mult in this format described at https://bitcointalksearch.org/topic/m.56709429 ?


Except you need to add & ~yes checks to d[4,5,6]. d[7] won't need it because it's still all F's.

Thnx for reaction (this is clear)

I am already much further than this.
I need to rewrite "reduction" in Montgomery maths from 512 bit to 256bit by two muls and some additions...

The reason is for k1 the difference from p to 2**256 is only 0x1000003d1 so there is optimized program

But for r1 due to f**ing p value the difference is not only 64bits but 256bits, now I am sure it was p value selected like this for the purpose

But I NEVER give up!

The values of a and b in secp256r1 are different:


In other words you are dealing with an x3 + ax + b form with a non-zero a.

Your N will be FFFFFFFF 00000000 FFFFFFFF FFFFFFFF BCE6FAAD A7179E84 F3B9CAC2 FC6325 (according to SEC2) and your P will be FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF .

Also your new generator point is

03 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C2

or equivalently 04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0 F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE3357 6B315ECE CBB64068 37BF51

I hope I will pass on this forum with my question though it is not about secp256k1

I want to adapt BSGS algo for eliptic curve secp256r1

Order n is smaller value than for k1 curve. Also it is claimed n is prime for r1. So I hope the m value for Montgomery arithmetic should fit directly also for r1?

I know I need to change some constants like 10003D1 and so on...

Anybody has experience implementing eliptic curve r1?