0
$\begingroup$

I want to implement Elliptic Curves arithmetics (for edu purpose and better understanding) for special NIST primes: point addition, exponentiation, etc.. all operations needed for EC encryption/decryption, digital signatures, and key exchanges. I'm interested in only special NIST primes, not in implementation for a general curve. Do I need to implement a multi-precision arithmetic for some fixed word size (32, 64) such as add/sub, reduction, inversion, Montgomery reduction, and so on? As far as I understand these primes are selected so that implementation is fast comparing to a general implementation.

$\endgroup$
5
  • 1
    $\begingroup$ have you ever heard GNU/MP? $\endgroup$ – kelalaka May 22 at 22:16
  • $\begingroup$ @kelalaka yeah, I heard. It is a multiprecision library. So? I'm asking whether or not we need MP library, not about existing libraries. $\endgroup$ – HardFork May 22 at 22:21
  • 1
    $\begingroup$ Did you look at the NIST curves field-sizes? Currently, we need around at least 112-bit secure curves that imply 224 bit filed sizes, like P244, and larger.. $\endgroup$ – kelalaka May 22 at 22:26
  • $\begingroup$ Yes I looked at it before a couple of times. But couldn't find helpful implementation details rather than recommended domain parameters the curves. I have already implemented MP arithmetic: ADD/SUB/MUL, POW using bin exp, reduction using Montgomery alg, Inv using GCD alg. But those curves are special. For example reduction is different as far as I understand. I guess general MP implementation is too much for those curves. $\endgroup$ – HardFork May 22 at 22:37
  • 1
    $\begingroup$ What is the reduction different? Why should be general MP is too much? It is a library, use whatever you need, left there rest. It is a library of 30 years. Even some of the parts of the library implemented in constant time. $\endgroup$ – kelalaka May 22 at 22:41
1
$\begingroup$

Whatever the curve, it's needed to use multi-precision integer arithmetic in ECC cryptography, at least for a few modular operations modulo the Ellitic Curve group order, since that's large (192-bit is the bare modern minimum). For the field, where the most compute-intensive operations are, there are alternatives with fields other than prime order groups. See for example Thomas Pornin's Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions (note: in this work, extensions applies to field, not microcontrollers).

For curves on prime-order field (as in the question), it's indispensable to have multi-precision integer arithmetic for field operations, and the performance of modular operations is central to the overall performance. Special attention to side channels, including timing, must be taken when manipulating confidential information (when signing and decrypting, and to some degree when encrypting; that's usually not a concern for signature verification).

For prime field using special NIST primes (as in the question), speed optimizations are possible. That's the reason to use such primes. All correct generic multi-precision integer arithmetic techniques and libraries (including GMP) work with these primes, but in general do not take advantage of the special form for speedup. Such techniques and libraries are thus adequate to get correct results, but not to get the best possible performance. More often that not, they also do not give adequate protection against side-channel leakage. Only some functions of GMP are written with this in mind.

$\endgroup$
5
  • $\begingroup$ Thank you. Isn't side-channel leakage hardware specific? How can we prevent this leakage at software level? $\endgroup$ – HardFork May 23 at 7:01
  • $\begingroup$ One more question though a bit off-topic. Do you follow NIST round3 on postquantum finalists algs? As far as I know lattice based algs seems to be promising. What is your take on this subject? Do you know any implementation worth to look at? $\endgroup$ – HardFork May 23 at 7:23
  • 1
    $\begingroup$ Data-dependent timing variations can be avoided with careful software design making all execution paths and memory accesses data-independent. Some other side channel leakage mitigations are possible in software. I don't closely follow PQC advances. @HardFork $\endgroup$ – fgrieu May 23 at 8:57
  • $\begingroup$ I reviewed a couple of implementations of p256 curves. There is no generic MP routines. Since we are dealing with numbers no more than 256 bits, for addition it is enough 5-6 words (on 32 bit arch.), for mul the result is 512 bits (12 words at most) followed by reduction which does not require generic E-GCD. There is no for loops, ifs etc. $\endgroup$ – HardFork May 24 at 7:07
  • $\begingroup$ @HardFork: about "There is no for loops, ifs etc.": No, there are! The point against timing and some of the other classes of side channels is that the control variable of tests does not depend on anything dependent on anything secret. And that restriction is often not needed (and not made, for performance reasons) in signature verification. Independently: implementation using GMP is quite possible, and has been done. For verification, that's one of the easiest way, and performance can be fair despite the lack of optimization for NIST primes. $\endgroup$ – fgrieu May 24 at 7:58

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.