1
$\begingroup$

I am wondering how the precomputed table for scalar multiplication for elliptic curve (in my case 25519) is generated/precomputed?

I am talking about this [https://github.com/WhisperSystems/libsignal-protocol-javascript/blob/master/native/ed25519/base.h

The piece of code which uses this header file is:

/* base[i][j] = (j+1)*256^i*B */
/*static const ge_precomp base[32][8] = {
#include "base.h"
} ;*/

ge_precomp is defined as 

ge_precomp (Duif): (y+x,y-x,2dxy)

Is there a paper or a piece of code where I can see how this table is generated? I am not trying to learn more about elliptic curves, I simply want to precompute this myself because of the specifics of my project.

I guess I would have to add point B to itself for (j+1)*256^i mod p times for each i and j. Is there a less compute intensive way to do this on an e.g. Raspberry Pi?

Thanks in advance!

Improve this question
$\endgroup$
4
  • $\begingroup$ gist.github.com/CodesInChaos/ef914909941ce7caf514 $\endgroup$
    – CodesInChaos
    Commented Nov 15, 2017 at 10:49
  • $\begingroup$ From what I remember the above code runs in 15ms or so on a desktop computer. If that's not fast enough, you could switch to batch-inversion, but that'd complicate the code a bit. $\endgroup$
    – CodesInChaos
    Commented Nov 15, 2017 at 11:39
  • 1
    $\begingroup$ @CodesInChaos Thanks, ported the code to C, and it works like a charm. I owe you a beer. gist.github.com/irfansehic/9c0b204845370f372bdfccfb66ec5942 $\endgroup$
    – Irfan S
    Commented Nov 15, 2017 at 12:35
  • $\begingroup$ Could either of you pretty please create an answer with an extract for this question? $\endgroup$
    – Maarten Bodewes ♦
    Commented Nov 15, 2017 at 16:01

1 Answer 1

Reset to default
2
$\begingroup$

CodesInChaos created an exact gist in C# for this: https://gist.github.com/CodesInChaos/ef914909941ce7caf514

It worked for me, took around 8 seconds on a 48MHz 32bit device, but either way, works. My C port can be found here https://gist.github.com/irfansehic/9c0b204845370f372bdfccfb66ec5942

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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