Topic: Smaller elliptic curves y^2=x^3+7, based on secp256k1 (Read 765 times)

Just check n-value in my tables. For example, for 256-bit curve, it is "ffffffff ffffffff ffffffff fffffffe baaedce6 af48a03b bfd25e8c d0364141", but for 255-bit, it is "7fffffff ffffffff ffffffff ffffffff 00f26097 ca79ff9a bcdac70f f2f55f6d". Just read the table: https://github.com/vjudeu/curves1000/blob/master/bits/bits256.txt

Of course it has to be less than in 256-bit case. For example, if you have secp160k1, then you obviously have 160-bit values: https://neuromancer.sk/std/secg/secp160k1

Sometimes it is the case, sometimes not. It depends on the curve.

I cannot crack anything. It is not about breaking things, it is about discovering, how the generator was picked. Also, if you will pick a different generator, it will be as strong as it is, because it will affect only mining public keys, and making signatures, but you will still stay on the same curve, and breaking any key will be as hard, as it was before.

@vjudeu


 ;)what is the order of find by you pubkezys ?

If it less then secp256k1 base point, but point belong to secp256k1 you make big work, and now you can crack btc mire easy...

Just make a little change to the code given by Garlo Nicon, and you will have it:
As you can see, it is easy to get an answer. And if you remove "is_running=False" from the inside of this loop, you will get a lot of points, until you CTRL+C your program, or it will timeout in Sage online server.

You can try, but I don't think the solution is there. But well, you can do a lot of things with elliptic curves. Another question is: does it make any sense? For example, here is another game I played some time ago:
But guess what: it is a funny game, but it will give you no solutions to any existing puzzles. And it will not reveal you any private keys, because it works purely on public keys, you don't have to even know n-value to play it!

Edit:
I am recalculating them, because I forgot that p%4==3. But I will publish recalculated version soon.

Do we have any algorithm to check for primes in either x or y coordinates? Also do you think there is any use going after p values existing in G and then see if those p values are a valid point on secp256k1 or not?

Btw thanks for the code to find n from p, rip Solinas for his primes.😉

Just to let you know: I created a list of 256-bit curves, with p-values, b-values, and n-values, as close to secp256k1, as I could. Also, in this case, secp160k1, secp192k1, and secp224k1 were reached with the same algorithm, so I hope it is correct. Feel free to grab it, and experiment with those curves: https://github.com/vjudeu/curves1000/blob/master/bits/bits256.txt

Still trying to create a generator, but I guess it will take some time, to explore the algorithm, which was used in the standardized curves. Also note that there is some anomaly nearby 32-bit curve, because of Solinas primes, but I guess everything up to 64-bit curve will be broken fast anyway, so the rest of the list should be good enough. In the puzzle, people are working on 130-bit, so I guess this list could be useful for 128-bit and above, or maybe even 160-bit and above (because the challenge ends on 160-bit public key, which means, breaking the whole challenge will probably make secp160k1 obsolete).

But the code I gave you is almost identical, if you want to use for example Sage Cell Server:
Which means, you need more detailed version only if you want to implement each part from scratch. But that is also easy, for example if you want to implement "powermod", then this is a good starting point: https://en.wikipedia.org/wiki/Modular_exponentiation

Tromp could u explain more what sort of coincidence you speak about on your link [1]

This sage script doesn't find that it is rare to have the property of the post linked when P and N are primes...:

any point of orger G is same. N and P is a order of point G  and curve. Find base point for curvevand order is easy...

For fing G point from P or N, have u script ?

You don't need "N" to do that. You only need "P".
Of course, this is not the original algorithm. I simply start from x=1, and then reach the nearest point. But in secp256k1, and with many other curves, it was done in a different way. The small x-value is just a hint for me to explore point generation later, and to have some starting point, to calculate n-value, based on that.

Also note, that in my code, I don't use n-value to calculate my base point. I can do that, based on p-value, and the curve equation, nothing else is needed to find any matching point. And then, by having that point, I use it to calculate n-value.

Could u pls post script for calculate base point from P and N
Thanks

Up to 39-bit curves? Sure, but it is not yet public. For 40-bit curves and bigger? Not really, because it works on uint64, so you need uint128, uint256, or BigInteger implementation to cover that. But if you want some basic implementation, then you can cover small curves quite easily, because then you don't need any optimizations, and you can for example use brute force to calculate inversions, and it will work fine for the smallest ones.

Do you happen to have a script for EC operations where we could change p, n, and G?  Set target for +, - , *, /?

I don't know. But those points seems to be generated, based on public key coordinates alone. And if this is true, then probably nobody knows the private key.

After more optimizations, I noticed "p" and "n" values can be above or below some N-bit number. In this way, getting valid curves is faster, and it seems other curves were generated in a similar way, for example, for secp160k1, p-value is less than 2^160, but n-value is bigger:
That means, to reproduce secp256k1 more accurately, I adjusted my code, to jump above and below 2^N, and reached those results:
Edit: Wow, that was fast, I didn't expect it. After optimizing finding base point, and applying Hasse to find "n" based on "p", I quickly reached next curves:

You seem to be interested in these stuff, so I thought maybe you could figure out which key belongs to the following public keys?


And I just found out that if we multiply n/2 by 3

You will get half+1, or 0.5 plus 1 which is n/2+1 =
😉

---

Ps, G divided by 2 is not actually n/2, it just happens that since G is odd, aka 0x1 dividing it by 2 would divide n-1 by 2, I'm waiting to  see the secret behind G revealed, so chop chop crypto experts, and thanks.

I implemented some optimizations, and I can now get more values. Thank you all for your hints, more improvements are ongoing:

Edit:Few months ago, I thought x-value is some kind of hash, potentially having more than 160 bits (for example 192 bits). However, when I tried to implement everything by myself from scratch, I discovered more interesting things. For smaller values, the whole procedure of generating a curve does not involve hashing at all! It is not needed. It is described in PDFs, but if you want to generate any curve with certain properties, you don't have to implement any hash function. So, I wonder if that was the case in secp256k1. Maybe the creator didn't implement any hashing, and all values we can see, are just produced by taking modulo square roots, modulo cube roots, counting "n" based on "p", and things like that?

Some example: you pick some "p", as in secp256k1. Then you calculate the only valid "n" for that "p". And then, if you observe the last 128 bits of "n", and take only that, then you cannot see, if it was some result of some 128-bit hash function or not.
Then, by seeing only "baaedce6 af48a03b bfd25e8c d0364141" you could think "hey, someone just used 128-bit hash function here". But what if this was not the case? Another interesting thing is that according to PDFs, the base point is picked after calculating "n". However, in my code, it is now done the other way around: first I pick some base point, and then I can reach "n". So, I still have to learn, how it is possible to calculate "n" without touching any points (because if you touch some of them, then why not make it a base point? Unless the creator thought that picking x=1 was unsafe, and getting temporary points, and then discarding them, is needed anyway).

Definitely not. P is the range of acceptable values for (x,y) coordinates. If you have the simplest case, p=79, n=67, then it doesn't mean you have 79 points. That only means if you take any (x,y) point, then they all can be placed on a 79x79 square monochromatic bitmap, with (0,0) point in the top left corner, and all other points somewhere in the middle.

He cannot, because there are no such points. For all of those smaller curves, listed by garlonicon, you can just compute all points, count them, and see that "n" properly reflects the number of points for any given "p". If you have p=79, and you start from any valid point, where y^2=x^3+7, then if you start incrementing it, you will reach only 67 points, not 79. You always start from some prime "p", and then you reach your "n" by checking that if you multiply it by your base point, then you will reach (0,0) as your result.

Also note that if you picked some "p", then you cannot use some arbitrary "n". You should calculate it. For p=79, the only valid result is n=67. And for p=67, you will reach only n=79 (that also can show you, why P is not the number of points, as you cannot have 67 points with 79 private keys, and you can check that such elliptic curve is valid).

The only reason for that is modulo bias, introduced by "r=(k*G).x", where x-value has range from 1 to p-1, but r-value should be between 1 and n-1. It is true for all curves, where p!=n. However, it doesn't mean we have less keys, it only means some of them will wrap around, exactly in the same way as any hash between "n" and 2^256 will be wrapped into the proper range, when you calculate your z-value, used in signatures.

It is more difficult to handle other cases properly. Only for those pairs, you can safely assume, that h=1, exactly as in secp256k1. Of course, you can use for example "p=109, n=43, base=(2,48)", but then "h=1" is probably not the right choice.

There's a reason why you can't take an arbitrary public key and find the private key for it (let's assume you do not know the range at all), as the values are practically unknown.

It just hit me, that those subset of P-N points have two distinct (R,s) pairs* when making a signature from that private key [well technically, they have twice that amount, but the other two are from taking the negative of S which is non-standard and not allowed by Bitcoin anyway].

So you since those points are generated extremely rarely and there are almost no instances of them in the wild, you can say, for practical purposes, that their private keys are virtually non-existent.

*it all starts with the R value, which is calculated by R = G*x coord of the public key. So P-N of these keys have another public key point somewhere in secp256k1 that you can form by calculation but not necessarily from the standard EC point generation.

can you explain : Naturally, P is larger than N, which means those points don't have private keys.

if P is how much points are on curve, N -> max privkeys , so There are d=P-N , points without privatekeys? can you show that point?

The bitcoin cryptographic curve has two constants P and N.

P is the number of points on the curve and N is the number of private keys on the curve. Naturally, P is larger than N, which means those points don't have private keys.

OP is trying to find smaller values of P and N that work for this curve equation x^2 = y^3 + 7 used in Bitcoin, because it uses enormous P and N values.


Prime factorization is your friend, and I'm sure all those people running Prime95 over the past 2 decades have a table of prime numbers stored somewhere (all less than 2^256).

Don't do that. If for each prime "p" you are trying to generate the full table of all inverse values, from 1 to p-1, then this is one of your bottlenecks. Just use the extended Euclidean algorithm, and calculate all values on-the-fly, when they are needed.

How do you find that point? If by brute force, then it could be optimized. For example, if you guess that x=1, then you need to calculate just sqrt(8), which means raising 8 to the power of 0.5. If you replace 0.5 by the right number, depending on "p", then you could do it faster than by checking every point. Also, when raising numbers to powers, you don't have to go through all of them, but you can use modular exponentiation algorithms.

You don't have to go through all points. Imagine checking 115792089237316195423570985008687907852837564279074904382605163141518161494337 points in secp256k1. That means, your current program can only show you curves you can fully break. Better use Hasse's theorem. Even if you start from "p=n", and then jump between "p+value" and "p-value" for consecutive values, like 0, 1, 2, then you will get there much faster than by checking every point (but of course, for secp256k1, that would still mean checking around 2^128 possible values, so for bigger curves, you still have to implement Hasse's theorem properly, as mentioned in the previous link).

How do you check if some number is prime? If you check every single number, odd or even, then it could be also optimized. For those 2-cycle curves, you can start from some odd prime, and check every sixth value, because in all cases you need only primes of the form "p=6k+1", and "n=6m+1". Also, you can check numbers only to the point, where the square is less or equal than your potential prime. For bigger curves like secp256k1, even that is not enough, and there are more estimations. For example, if you want to find 256-bit "p", then you pick a range between 2^256-2^32-2^10, and 2^256-2^32. Then, you find prime numbers only in this range, so you will get only a few possible values, where 115792089237316195423570985008687907853269984665640564039457584007908834671663 is the biggest prime, that is less than 2^256-2^32.

The short answer is: you have to estimate more, and brute force less. For example, if you have "p" and "n" in secp256k1, then you don't have 100% guarantee that both values are prime. They probably are, but it is based on estimation, and not on some hard, mathematical proof, because that would require checking 2^128 values, and that would mean breaking the curve. If you want to make safe curves, and not break them at the same time, then you have to estimate things, not compute them exactly, for all cases, all points, all inverse values, etc.

it looks like the same what ecdsa123 has wrote in https://bitcointalksearch.org/topic/m.62280944

You didn't explain why you want these properties of 2 curves forming a 2-cycle.

Is it just because this is the case for secp256k1, as noted for example (together with other interesting properties) in [1] ?

[1] https://hackmd.io/@dJO3Nbl4RTirkR2uDM6eOA/Bk0NvC8Vo

How to get the full list of the elliptic curves, that could fit on N bits, based on secp256k1 used in Bitcoin? Now I can brute force some of the smaller ones, but I wonder, how to get some bigger values, and generate for example some 128-bit, 64-bit, or even 32-bit curves, without going through all points.

My current algorithm is something like that:
1. Pick some prime value "p".
2. Generate table of inverse values.
3. Starting from (1,1), find the nearest point, where y^2=x^3+7, and make it your base point.
4. Go through all points to calculate "n", it will be reached after trying to add (baseX,-baseY) to the (baseX,baseY).
5. Check if "n" is prime.
6. Make sure that "n" is different than "p".
7. Validate that if you pick "n" as the starting prime, and go through all steps, you will reach "p".
8. If there are many N-bit curves, pick the one where "p" is closest to 2^N-1, and "n
After some bruteforcing, I reached those smaller curves. The question is: how to generate them faster, without going through all points, and reach the full list of elliptic curves, from 15-bit to 255-bit, based on secp256k1?

Code:

p=   79, n=   67, base=(1,  18)    7-bit
p=  967, n=  907, base=(1,  88)   10-bit
p= 1303, n= 1249, base=(1, 201)   11-bit
p= 3853, n= 3739, base=(3, 534)   12-bit
p= 7537, n= 7369, base=(1,3725)   13-bit
p=14071, n=13933, base=(1,3660)   14-bit