Kangaroo 254bit (secp256r1 / P256)

[sky59sky59]

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?

[NotATether]

The values of a and b in secp256r1 are different:

Code:

a = FFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFC
b = 5AC635D8 AA3A93E7 B3EBBD55 769886BC 651D06B0 CC53B0F6 3BCE3C3E 27D2604B

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

[sky59sky59]

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!

[NotATether]

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

Are you sure that you can't just write Montgomery mult in this format described at https://bitcointalk.org/index.php?topic=5328393.msg56709429#msg56709429 ?

Code:

SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) {
    int yes = 0;
    int no = 0;
    no |= (a->d[7] < SECP256K1_N_7); /* No need for a > check. */
    no |= (a->d[6] < SECP256K1_N_6); /* No need for a > check. */
    no |= (a->d[5] < SECP256K1_N_5); /* No need for a > check. */
    no |= (a->d[4] < SECP256K1_N_4);
    yes |= (a->d[4] > SECP256K1_N_4) & ~no;
    no |= (a->d[3] < SECP256K1_N_3) & ~yes;
    yes |= (a->d[3] > SECP256K1_N_3) & ~no;
    no |= (a->d[2] < SECP256K1_N_2) & ~yes;
    yes |= (a->d[2] > SECP256K1_N_2) & ~no;
    no |= (a->d[1] < SECP256K1_N_1) & ~yes;
    yes |= (a->d[1] > SECP256K1_N_1) & ~no;
    yes |= (a->d[0] >= SECP256K1_N_0) & ~no;
    return yes;
}

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.

[sky59sky59]

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.

[NotATether]

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.

If you are referring to

Babystep size

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.

[sky59sky59]

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

[COBRAS]

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

r1 is less difficult to find a privkey ?

Thx.

[sky59sky59]

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

[NotATether]

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.

[sky59sky59]

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

[NotATether]

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

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

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.

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

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

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

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.

[sky59sky59]

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

[NotATether]

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?

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:

Double - in projective coords, here I must add a*Z*Z

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

[sky59sky59]

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?

[NotATether]

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?

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

[sky59sky59]

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

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

[a.a]

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

[NotATether]

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

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.

[sky59sky59]

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?