2
$\begingroup$

For a simple proof of concept project i'm (attempting!) to do, i've started looking into openSSL elliptic curve cryptography.

However instead of the standard key lengths, 160-512. I'm interested in a resultant key of just 64 bits (less secure I know but that's my projects purpose). Is it possible using elliptic curve cryptography?

I'm quite a novice, is there anything fundamentaly wrong with instead generating say a 256 key and cutting it size to 64bit?

Any advice would be greatly appreicated thanks.

$\endgroup$
  • $\begingroup$ Apart from being broken in a few minutes on a standard computer, there is nothing wrong with using a 64 bit field. The bigger problem is that you need to find curve parameters which requires understanding the mathematics behind ECC (Unless there are some standard SAGE scripts which do it for you). $\endgroup$ – CodesInChaos Mar 7 '14 at 11:43
  • $\begingroup$ Point counting on such a small curve might not be that difficult - you could use a pretty naive/simple algorithm and not worry about it taking years to complete. $\endgroup$ – pg1989 Mar 8 '14 at 2:14
3
$\begingroup$

I'm not sure if I get your question correctly. Do you like to use a 256 bit curve to generate a (secret) key of this size and later drop 192 bits? If this is the case your 64 bits will be useless because you secret key will not have any relation with the public. Furthermore, in a magic case that this works, your field operations will continue living in a 256 finite field.

If you like to use a 64 bits EC cryptosystem, first thing you need is to stablish the "setup": a tuple that 'configures' this set up. You may like to check the IEEE P1363 for details, but to have a cryptographically good curve (ignoring the fact that 64 bit is very few). As an example for a finite field:

  1. Generate $p$: random big prime of your 64 bits.
  2. Generate $a$ and $b$: in $\mathbb{F}_{p}$
  3. Check non zero discriminant: $\Delta\neq 0$
  4. Calculate the cardinal $|E(\mathbb{F}_p)|$
  5. Check this cardinal is in the hasse interval
  6. Check this cardinal factorises in $n$ and $h$ where $h<<<n$ and $h\in[1,2,4]$

If steps 3, 5 and 6 fails, go back to step 2 or even 1.

At this point you have a cryptographically good curve, then you need the cyclic subgroup where the ECDLP will protect your secrets.

  1. Generate a random $x\in_R \mathbb{F}_p$ until you find a valid point in your curve. (for a valid $x$ there will be two $y$, select at random).
  2. Check $[n]G=\mathcal{O}_E$

Same than before, if you random point doesn't pass check 2, repeat. But the probability to find a good one is bigger as your cofactor $h$ is smaller.

As you can see, this process is not light and it becomes heavier and heavier (exponentially) when you increase your 64 bits.

$\endgroup$
  • $\begingroup$ Thanks yeah I quickly realized trimming the private key would mess things up! Thanks for your help, i'll look into this. $\endgroup$ – James Rattray Mar 7 '14 at 18:23
  • $\begingroup$ Hasse's theorem guarantees that the cardinality $|E(\mathbb F_p)|$ is in the interval $p + 1 \pm 2 \sqrt p$. If step (5) fails, you've done something terribly wrong… There's also many more criteria for secure elliptic curve selection, depending on application; see safecurves.cr.yp.to for criteria for DH functions and Schnorr signatures. $\endgroup$ – Squeamish Ossifrage 2 days ago
2
$\begingroup$

No nothing. Elliptic curve cryptography can be done on any discrete field. Hence, if you choose a 64-bit key, the DL-problem in the group induced by elliptic curves might be not that hard, but still it is valid to do.

$\endgroup$

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.