Title: How to construct hardened ECDSA from ECDSA? Post by: garlonicon on November 16, 2023, 10:44:48 PM I didn't expect to get there, but here I am. It is possible to find a curve, which will have exactly X times more points, than a given curve. Which means, if everything is rolling around those prime numbers, then it is possible to find some prime number, and multiply it by (p-1) or (n-1), and find a new curve in this way.
For example, if we start from secp160k1, then we have those values: Code: p=0xfffffffffffffffffffffffffffffffeffffac73 Code: p=0x4bc54fffffffffffffffffc10c06797634b00230c031d Code: p=0xfffffffffffffffffffffffffffffffeffffac73 Code: 2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473 Title: Re: How to construct hardened ECDSA from ECDSA? Post by: digaran on November 18, 2023, 07:39:20 AM So we can't use 2 random p and n to generate a curve, right? Because just now I used a different n without changing p and G, and when I used this new n as my private key I got an error.
Code: my new n = And then secp256k1 n also returned an error, though by changing just 1 bit of G, there was no error. I would like to know the relation between p and n, because it seems that G is irrelevant in the curve calculations. Also this new n is not prime, it's just an odd number. But I have used other odd numbers before and I could get an error when I changed my private key to an even number, but this n works for all other than itself and it's bigger brother.(secp256k1 n) Note, I'm one of those dumb students that asks about something several times. So if I have asked this before just ignore.😅 Title: Re: How to construct hardened ECDSA from ECDSA? Post by: vjudeu on November 18, 2023, 08:42:23 AM Quote So we can't use 2 random p and n to generate a curve, right? Of course they are not random. As I often said: "just test it". Use "y^2=x^3+7" and nothing else. Start from p=1, and keep increasing it. Each time, try to count all points. Then, you will get all images from my repository: https://github.com/vjudeu/curves1000Quote Because just now I used a different n without changing p and G, and when I used this new n as my private key I got an error. Of course. Because n-value is not picked randomly. It is calculated. See, what Garlo Nicon did there: https://bitcointalk.org/index.php?topic=5459153.0When he picked p=79 and y^2=x^3+7, then he reached n=67. He couldn't put n=68 or n=70. He calculated n=67, based on p-value, and the curve equation. Quote I would like to know the relation between p and n, because it seems that G is irrelevant in the curve calculations. 1. Of course, G is irrelevant. So, if you pick a different generator, then your curve will be as safe as usual. It will only affect signatures at most, or some protocols like "mining public keys", but not much more than that.2. The relation between p and n is quite simple: you pick p-value, which is your modulo. Which means, if you calculate 2+2=4, and your p=3, then you have 2+2=1, because 4 mod 3 is equal to 1. And then, n-value is just the number of points for a given p-value. If you pick p=79, and create 79x79 bitmap, and then count all points, where y^2=x^3+7, then you will find 66 such points, and one point at infinity. Which means, n=67. But you cannot pick it, you have to calculate it. Quote Also this new n is not prime, it's just an odd number. Then your curve is less safe, because there is a high chance to see patterns. Which means, in that case, h=1 may not be the right choice.Quote Note, I'm one of those dumb students that asks about something several times. So if I have asked this before just ignore. I don't want to ignore all posts of all people, and stop posting forever. Every question was already answered, in 99% cases. But people still answer questions on forums, because it is needed. Also note that my own questions are already answered in different places. So, why I ask those questions? Because I care about spreading that knowledge, even if I know the answers.Title: Re: How to construct hardened ECDSA from ECDSA? Post by: garlonicon on November 18, 2023, 11:19:21 AM Quote I would like to know the relation between p and n, because it seems that G is irrelevant in the curve calculations. I can even give you some code to get n-value, based on p-value, and the curve equation. Of course, it is the simplest brute-force, and it will stop working if you use it on bigger numbers, but it is simple enough to understand it, and implement in any programming language you want.Code: #include <iostream> Title: Re: How to construct hardened ECDSA from ECDSA? Post by: Kpot87 on November 18, 2023, 03:07:07 PM Quote I would like to know the relation between p and n, because it seems that G is irrelevant in the curve calculations. I can even give you some code to get n-value, based on p-value, and the curve equation. Of course, it is the simplest brute-force, and it will stop working if you use it on bigger numbers, but it is simple enough to understand it, and implement in any programming language you want.Code: #include <iostream> ok? the question is how in 199x years it was possible to do it(brute-force). how this n and p was chosen? thanks Title: Re: How to construct hardened ECDSA from ECDSA? Post by: vjudeu on November 18, 2023, 05:31:01 PM Quote the question is how in 199x years it was possible to do it(brute-force). People just optimized it. You can read about those optimizations, and apply them, one by one: https://en.wikipedia.org/wiki/Counting_points_on_elliptic_curvesQuote how this n and p was chosen? "n" was never chosen. People simply picked "p" as the greatest prime value, that is below "2^x", for example below "2^256" in case of secp256k1, and then they calculated n-value, and they also required it to be prime.So, the algorithm was quite simple: 1. Start from p=2^256 (and subtract 2^32, because of Solinas primes (https://en.wikipedia.org/wiki/Solinas_prime)) 2. Decrement p-value, until it will be some prime number. 3. Calculate n-value. 4. Check if n-value is prime. 4.1. If n-value is not prime, try another p-value. 4.2. If n-value is prime, then print p-value and n-value. I can even write it in Sage: Code: bits=256 Code: failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9 Edit: Also note that this question was raised by Garlo Nicon, and answered here: https://bitcointalk.org/index.php?topic=5464362 |