There are a few systems like the GNU Name System and the Sphinx mixnet packet format that employ a series of curve25519 scalars all multiplied together as a private key.

Are there any caveats to multiplying several together like this? What about adding them or doing other arithmetic operations on scalars?

Another form of this question is : There are a several bits twiddled when a scalar is produced for Ed25519. What is the mathematical reasoning behind these modifications? How does it translate to producing a private key scalar for curve25519?

I found a partial answer here. At least the lower three bits are cleared to prevent a small subgroups attack, although there is debate over the effectiveness of this attack. I presume the small subgroup attack is a threat to the curve formulations used in both Ed25519 and curve25519 equally.

Now if one of the scalars being multiplied together is a multiple of 8 then they all are, so that's good. If all are multiples of 8, then addition looks good too, but addition with values that are not multiples of 8 could be problematic. Is this correct? What about the bit operations on higher bits? Why are they there? etc.

  • $\begingroup$ I've voted for this question. I do however think that the second paragraph makes the question harder to read / answer rather than to enhance it. It does show clearly what you tried, but it's too open. I know this because it is usually the biggest mistake I make when asking questions :) $\endgroup$
    – Maarten Bodewes
    Oct 12 '15 at 20:19
  • $\begingroup$ Your other question regarding the higher bits is answered here. $\endgroup$ Oct 13 '15 at 11:09
  • $\begingroup$ Alright, I suppose that answers everything then. In particular, one should not subtract curve25519 scalars because doing so would wipe out the most significant bit. And multiplication might get tricky too. Although one could protect against this by checking that the implementation does not fuck up and start with the most significant bit. $\endgroup$ Oct 13 '15 at 12:06
  • $\begingroup$ Yes; it is perfectly fine to multiply scalars together, but you will have to ensure implementation correctness yourself. $\endgroup$ Oct 13 '15 at 13:26
  • $\begingroup$ Most issues regarding computations on these field elements relate to the cofactor. If you eliminate the cofactor by using Decaf / Ristretto and if I understand this correctly, you should be safe. You might want to ask @ isislovecruft and @ hdevalence for confirmation. $\endgroup$
    – cypherfox
    Mar 9 '18 at 9:23

Browse other questions tagged or ask your own question.