3
$\begingroup$

In NaCl and libsodium, the crypto_scalarmult function implements the operation $Q = kP$ (scalar/point multiplication). There doesn't seem to be a function for point addition $K = P + Q$ though.

Something like point addition must be implemented somewhere I think, as part of the implementation of scalar multiplication. It would be useful to be able to access this for developing some protocols on top of Curve25519.

  • Is it deliberate that point addition isn't mentioned anywhere in the API or documentation? (Don't the authors want people implementing research-level protocols using their library?)
  • crypto_scalarmult delegates to crypto_scalarmult_curve25519 declared (in libsodium) in crypto_scalarmult_curve25519.h but I can't seem to find the definition in a .c file anywhere (in the latest version on GitHub)?
  • Is there a safe way to implement, or reuse an internal implementation, of point addition in libsodium?
Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ NaCl isn't an ECC library, it only offers higher level operations like key-exchange and signatures and doesn't have point addition in its public API. You should be able to find an edwards form point addition function in its Ed25519 implementation. $\endgroup$
    – CodesInChaos
    Jul 27, 2015 at 9:19
  • 2
    $\begingroup$ This is on purpose. The philosophy behind NaCl is that allowing low-level access leads to many implementation errors. If you only allow people "encrypt" and "decrypt" and you make this CCA-secure, then it's hard to mess things up. However, this does mean that you can't use the library for anything else... $\endgroup$
    – Yehuda Lindell
    Jul 27, 2015 at 13:00
  • $\begingroup$ You make a good point - perhaps I need to look for a different library. I was hoping for something to code a small ElGamal-based voting scheme based on ECC. $\endgroup$
    – user2552
    Jul 27, 2015 at 14:07
  • $\begingroup$ You can try OpenSSL $\endgroup$
    – Yehuda Lindell
    Jul 27, 2015 at 21:16
  • $\begingroup$ I like the Git concept of Plumbing and Porcelain API, say one easy and safe to use API, and another one for experts, enabling anything $\endgroup$
    – lalebarde
    Nov 7, 2016 at 12:22

2 Answers 2

Reset to default
1
$\begingroup$

Is it deliberate that point addition isn't mentioned anywhere in the API or documentation?

Yes. The idea is to offer a minimal API that makes doing the right thing for security easy, while avoiding low level operations that allow shooting yourself in the foot.

To quote this primer (pdf) on NaCl:

A typical cryptographic library is a collection of many different functions and supports a plethora of parameter sets. It is left to the software developer to choose from these functions and parameters, and combine them in a way that offers the desired security. These choices come with various pitfalls, not only because most libraries still contain highly insecure functions for ‘historical’ or ‘compatibility’ reasons, but also because it is easy to combine secure functions in an insecure way

The Eindhoven researchers have found that this level of complication is unnecessary for most applications. NaCl offers an easy-to-use high-level interface for exactly what applications need: secure authenticated encryption.

Is there a safe way to implement, or reuse an internal implementation, of point addition in libsodium?

You shouldn't even try to reuse the internal implementation by calling it from outside, because it's not a public interface. You can, of course, copy parts of the implementation (it's under the ISC license) and modify it to use in your own software, but then you are on your own with respect to using it safely.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ It's public domain if you copy it out of NaCl or SUPERCOP. $\endgroup$
    – CodesInChaos
    Jul 31, 2015 at 6:44
  • $\begingroup$ @CodesInChaos, true, though ISC license lets you do anything with it in any case. $\endgroup$
    – otus
    Jul 31, 2015 at 10:37
  • 1
    $\begingroup$ After a bit more research, there's another reason why Curve25519 doesn't do point addition - the implementation only stores the $x$-coordinates of points (not even a sign bit for $y$), which is sufficient for Diffie-Hellman but not for addition. It might be to avoid patent issues, or it might just be because that's sufficient for the intended applications. Long story short: using the Ed25519 implementation in NaCl instead does exactly what I was looking for and gives the same security guarantees. $\endgroup$
    – user2552
    Jul 31, 2015 at 12:10
  • $\begingroup$ @Bristol, you could post that as another answer if you like, or edit it into this one. $\endgroup$
    – otus
    Aug 3, 2015 at 8:53
2
$\begingroup$

Recent versions of libsodium have crypto_core_ed25519_add() and more: https://download.libsodium.org/doc/advanced/point-arithmetic

Improve this answer
$\endgroup$
3
  • $\begingroup$ This only works for Ed25519 though right? You'd have to start with Ed, add the points then birationally map them to curve25519? $\endgroup$
    – Woodstock
    Feb 24, 2021 at 11:54
  • 1
    $\begingroup$ If you need more than scalar multiplication, just do everything over Edwards25519. $\endgroup$
    – Frank Denis
    Feb 24, 2021 at 12:12
  • $\begingroup$ thanks you're a legend. $\endgroup$
    – Woodstock
    Feb 24, 2021 at 12:17

Your Answer

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