2
$\begingroup$

For educational purposes I would need to work on an elliptic curve that has a small field, but holds the safety futures of a real curve. Is that possible to have such a curve!?

For example for the curve of secp256k1, is that possible to find small $P$, $N$ and $G$ so that the mini curve does still have safety features of the real curve? By safety features I mean those features that come from the difficulty of solving the discrete logarithm problem. Of course I know that a curve with a small field is vulnerable through brute-force attacks.

To do so, first I read about properties of the prime $P$. It seems that it is a SAFE prime which is equal to $3 \bmod 4$. If I search for a small prime with the same two properties am I getting the correct mini curve?

How are $G$ and $N$ decided then?

I need a curve that lets me do point manipulations (adding, doubling, halving,...) with plotable easy-to-work-with integers, not those 78-digits of secp256k1.

$\endgroup$
3
$\begingroup$

The curve parameters include:

$p$: The prime modulus of the underlying field

$a$ and $b$: These are used in the curve equation, $y^2 = x^3 + ax + b$

$G$: a point on the curve that generates a subgroup

$n$: the order (number of points) of that subgroup

Once you have decided on your $p$, the process is basically try different curve parameters and a point-counting algorithm to find a curve with a large, prime order subgroup.

You can do this all automatically using SageMath

Here is a script that will generate a curve for you with the given bit size: https://github.com/brichard19/ecdl/blob/master/scripts/gencurve.sage

$\endgroup$
  • $\begingroup$ How is p decided!? I assume it should be A safe prime which is $p=3 mod 4$. Anything more to consider?! $\endgroup$ – PouJa Jan 25 at 18:53
1
$\begingroup$

I would need to work on an elliptic curve that has a small field, but holds the safety futures of a real curve. Is that possible to have such a curve!?

No, it is not possible. A necessary condition for a curve to be "safe" is that it has enough points on it. But the number of points is closely correlated to the size of the base field; namely if the size of the base field is $q$ then the curve will have between $q +1 \pm 2 \cdot \sqrt q$ points (this is the so-called Hasse bound).

By safety features I mean those features that come from the difficulty of solving the discrete logarithm problem. Of course I know that a curve with a small field is vulnerable through brute-force attacks.

So you want a curve where solving the discrete log is difficult even though it is vulnerable to brute-force attacks. This makes no sense. A brute-force attack is just one way of solving the discrete log problem; if such an attack can be done on a curve, then the curve does not have "those features that come from the difficulty of solving the discrete logarithm problem".

$\endgroup$
  • $\begingroup$ I do not want a safe curve. I need a model curve. $\endgroup$ – PouJa Jan 25 at 18:50
  • 1
    $\begingroup$ @PouJa Make up your mind. Do you want "safety features", or do you not? $\endgroup$ – fkraiem Jan 26 at 1:24
  • $\begingroup$ I do not want a safe curve. I want a curve on which I can explain with easy to show small numbers that this elliptic curve gives an irreversible public key unless we have to check all possible private keys. $\endgroup$ – PouJa Jan 27 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.