Title: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on July 09, 2023, 11:20:50 AM 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<p". 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 Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: tromp on July 09, 2023, 02:36:31 PM 6. Make sure that "n" is different than "p". You didn't explain why you want these properties of 2 curves forming a 2-cycle.7. Validate that if you pick "n" as the starting prime, and go through all steps, you will reach "p". 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 Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: ripemdhash on July 09, 2023, 03:14:00 PM it looks like the same what ecdsa123 has wrote in https://bitcointalk.org/index.php?topic=5453079.msg62280944#msg62280944 (https://bitcointalk.org/index.php?topic=5453079.msg62280944#msg62280944)
Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: vjudeu on July 14, 2023, 07:35:26 PM Quote 2. Generate table of inverse values. 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 (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm), and calculate all values on-the-fly, when they are needed.Quote 3. Starting from (1,1), find the nearest point, where y^2=x^3+7, and make it your base point. 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 (https://en.wikipedia.org/wiki/Modular_exponentiation).Quote 4. Go through all points to calculate "n", it will be reached after trying to add (baseX,-baseY) to the (baseX,baseY). 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 (https://en.wikipedia.org/wiki/Hasse's_theorem_on_elliptic_curves). 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).Quote 5. Check if "n" is prime. 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.Quote 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? 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.Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: NotATether on July 15, 2023, 10:54:01 AM I dont understand anything here lol... How could this be useful for you or us? 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. Quote 5. Check if "n" is prime. 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.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). Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: ripemdhash on July 15, 2023, 10:57:52 AM I dont understand anything here lol... How could this be useful for you or us? 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. 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? Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: NotATether on July 15, 2023, 02:14:54 PM 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? 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. Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: ertil on July 15, 2023, 04:21:31 PM Quote 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. 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.Quote 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? 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). Quote 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]. 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.Quote You didn't explain why you want these properties of 2 curves forming a 2-cycle. 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.Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on July 20, 2023, 09:50:32 PM I implemented some optimizations, and I can now get more values. Thank you all for your hints, more improvements are ongoing:
Code: p= 0x4f, n= 0x43, base=(0x1, 0x12) 7-bit Edit: Quote You didn't explain why you want these properties of 2 curves forming a 2-cycle. Because I want to recreate the whole generation procedure for secp256k1. And to do that, I think it is important to learn things gradually, starting from the smallest elliptic curves, and then applying more and more optimizations, to finally reach the same results as in secp256k1.Quote Is it just because this is the case for secp256k1 Yes, but by doing it in this way, it can also reveal the procedure for smaller elliptic curves, for example secp160k1, secp192k1, and secp224k1. It is also about solving the mystery behind the half of the base point (https://bitcointalk.org/index.php?topic=5432902.msg61656271#msg61656271): Quote Code: u1= 48ce563f89a0ed9414f5aa28ad0d96d6795f9c62 (160-bit) 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. Code: p=ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff fffffffe fffffc2f Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: digaran on July 23, 2023, 02:04:47 AM You seem to be interested in these stuff, so I thought maybe you could figure out which key belongs to the following public keys?
Code: 0200000000000000000000000000000000fc86e7e6d4f8be0f638ac81b54025a4e And I just found out that if we multiply n/2 by 3 Code: 0300000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63 You will get half+1, or 0.5 plus 1 which is n/2+1 = Code: 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a2 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. Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on July 27, 2023, 08:32:57 PM Quote You seem to be interested in these stuff, so I thought maybe you could figure out which key belongs to the following public keys? 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: Code: p= 0xfffffffffffffffffffffffffffffffeffffac73 Code: p= 0x3c7, n= 0x38b, base=(0x1, 0x58) 10-bit Code: p= 0x3ffff667, n= 0x4000c14d, base=(0x1, 0x1d02cd83) 30-bit n>p Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: digaran on September 01, 2023, 09:54:56 AM Do you happen to have a script for EC operations where we could change p, n, and G? Set target for +, - , *, /?
Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on September 01, 2023, 02:19:35 PM 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.
Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: brainless on September 09, 2023, 12:07:50 PM Could u pls post script for calculate base point from P and N
Thanks Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on September 09, 2023, 12:56:32 PM Quote Could u pls post script for calculate base point from P and N You don't need "N" to do that. You only need "P".Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f 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. Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: brainless on September 11, 2023, 09:26:55 AM Quote Could u pls post script for calculate base point from P and N You don't need "N" to do that. You only need "P".Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f 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. Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: COBRAS on September 11, 2023, 09:28:51 PM Quote Could u pls post script for calculate base point from P and N You don't need "N" to do that. You only need "P".Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f 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. 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... Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: CrunchyF on September 11, 2023, 09:57:39 PM 6. Make sure that "n" is different than "p". You didn't explain why you want these properties of 2 curves forming a 2-cycle.7. Validate that if you pick "n" as the starting prime, and go through all steps, you will reach "p". 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 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...: Code: ROUNDS=10000 Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: garlonicon on September 12, 2023, 12:27:28 PM Quote For fing G point from P or N, have u script ? But the code I gave you is almost identical, if you want to use for example Sage Cell Server (https://sagecell.sagemath.org/):Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: vjudeu on November 20, 2023, 08:55:48 AM 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). Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: digaran on November 20, 2023, 10:15:20 AM 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.😉 Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: vjudeu on November 20, 2023, 10:35:08 AM Quote Do we have any algorithm to check for primes in either x or y coordinates? Just make a little change to the code given by Garlo Nicon, and you will have it:Code: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f Code: 0xe9b 0xe22c56c79e9d1ab0357f4348aadb53006efeb69fd3f1924ea0bfe8201d2e1d23 Quote 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? 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:Code: True 0x1 0x4218f20ae6c646b363db68605822fb14264ca8d2587fdd6fbc750d587e76a7ee Edit: Quote 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. I am recalculating them, because I forgot that p%4==3. But I will publish recalculated version soon.Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: COBRAS on November 23, 2023, 11:05:37 AM @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... Title: Re: Smaller elliptic curves y^2=x^3+7, based on secp256k1 Post by: vjudeu on November 23, 2023, 12:14:36 PM Quote what is the order of find by you pubkezys ? 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.txtQuote If it less then secp256k1 base point 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/secp160k1Quote but point belong to secp256k1 Sometimes it is the case, sometimes not. It depends on the curve.Quote you make big work, and now you can crack btc mire easy... 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. |