How to construct hardened ECDSA from ECDSA?

[garlonicon]

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
n=0x100000000000000000001b8fa16dfab9aca16b6b3

Imagine that one day, they could be unsafe. The same "hardening" can be done on secp256k1, but using secp160k1 is easier for demonstration, because then calculations are faster, if we have smaller numbers. If we try to harden p-value, we will get something different, than if we try to harden n-value. So far, I calculated those values:

Code:

p=0x4bc54fffffffffffffffffc10c06797634b00230c031d
n=0x4bc54fffffffffffffffffffffffffffb43a9744ff9db

p=0x12ec50000000000000002098a5f6f768fa8844f0092fb
n=0x12ec500000000000000020bb39f6453ea5c52f7847577

It is not hard to notice, how I constructed them, if you factor all (p-1) and (n-1) values:

Code:

p=0xfffffffffffffffffffffffffffffffeffffac73
n=0x100000000000000000001b8fa16dfab9aca16b6b3
print(factor(p-1))
print(factor(n-1))

p=0x4bc54fffffffffffffffffc10c06797634b00230c031d
n=0x4bc54fffffffffffffffffffffffffffb43a9744ff9db
print(factor(p-1))
print(factor(n-1))

p=0x12ec50000000000000002098a5f6f768fa8844f0092fb
n=0x12ec500000000000000020bb39f6453ea5c52f7847577
print(factor(p-1))
print(factor(n-1))

Then, you can see, what is going on:

Code:

2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 42918291593381467397 * 128449012680369359431471
2^2 * 3 * 419 * 1262416996310492089 * 71459956825976057860836930052391
2 * 3 * 5 * 7 * 113 * 310357 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 77509 * 42918291593381467397 * 128449012680369359431471
2 * 3 * 5 * 1669 * 8724787 * 49895748288437600389 * 5197033008695820090287

As you can easily note, the first value is just divisible by 310357, and the second one is divisible by 77509. Depending on, whether we want to convert public or private keys, we can use the former, or the latter. But, there is more: we can combine (p-1) with (n-1), and upgrade from 160-bit into 320-bit curve, and add some additional factor, just to be sure.

[digaran]

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 =
0xebaaedce6af48a03bbfd25e8cd0364141
Private key = 
0xebaaedce6af48a03bbfd25e8cd0364141

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

[vjudeu]

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/curves1000

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

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

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.

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.

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.

[garlonicon]

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>

int get_n_from_p(int p)
{
    int n=1; //we start from n=1, and not n=0, because of the point at infinity
    for(int y=0;y<p;++y)
    {
        for(int x=0;x<p;++x)
        {
            int y_square=(y*y)%p;
            int x_cube=(x*x*x)%p;
            int x_cube_plus_seven=(x_cube+7)%p;
            if(y_square==x_cube_plus_seven)
            {
                ++n;
            }
        }
    }
    return n;
}

int main()
{
    for(int p=1;p<=1000;++p)
    {
        std::cout<<"p="<<p<<", n="<<get_n_from_p(p)<<'\n';
    }
}

See? No generator is used there. Every single point is checked, and you can just create an image, and put a black pixel, if there is no point on a given curve, or put a white pixel, when you can find a match. This is basically what vjudeu did in his repository. As you can see, in this brute-force algorithm, there is no need to even pick any specific point, because all of them are checked.

[Kpot87]

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>

int get_n_from_p(int p)
{
    int n=1; //we start from n=1, and not n=0, because of the point at infinity
    for(int y=0;y<p;++y)
    {
        for(int x=0;x<p;++x)
        {
            int y_square=(y*y)%p;
            int x_cube=(x*x*x)%p;
            int x_cube_plus_seven=(x_cube+7)%p;
            if(y_square==x_cube_plus_seven)
            {
                ++n;
            }
        }
    }
    return n;
}

int main()
{
    for(int p=1;p<=1000;++p)
    {
        std::cout<<"p="<<p<<", n="<<get_n_from_p(p)<<'\n';
    }
}

See? No generator is used there. Every single point is checked, and you can just create an image, and put a black pixel, if there is no point on a given curve, or put a white pixel, when you can find a match. This is basically what vjudeu did in his repository. As you can see, in this brute-force algorithm, there is no need to even pick any specific point, because all of them are checked.

ok? the question is how in 199x years it was possible to do it(brute-force). how this n and p was chosen? thanks 

[vjudeu]

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_curves

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)
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
p=2^bits-2^32
n=4
while not is_prime(n):
    p=previous_prime(p)
    P=GF(p)
    aP=P(0x0)
    bP=P(0x7)
    curve=EllipticCurve(P,(aP,bP))
    n=curve.order()
    if not is_prime(n):
        print("failed: p="+hex(p))
        print("n="+hex(n))
print("success: p="+hex(p))
print("n="+hex(n))

This is the standard output:

Code:

failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffef9
n=0xffffffffffffffffffffffffffffffff9d70b40e72725ad652cd62c55808d873
failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe99
n=0x100000000000000000000000000000000b3c017eacf02babf49040910abee2e35
failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe97
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe98
failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe19
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffe1a
failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1d
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffd1e
failed: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4b
n=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc4c
success: p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

You can also try "bits=160", and see, what will happen.

Edit: Also note that this question was raised by Garlo Nicon, and answered here: https://bitcointalk.org/index.php?topic=5464362