1
$\begingroup$

I have been exploring and studying the EDDSA algorithm for curve 25519 and curve 448 in RFC 8032 (https://www.rfc-editor.org/rfc/rfc8032) as well as for curves 414 and 521 from this (https://eprint.iacr.org/2015/677.pdf ) and with respect to the rules for pruning a scaler before multiplying the base point, I noticed two things of particular interest:

  1. The value of N for the highest scaler bit to be set is different in RFC8032 for EDDSA 448 than in the paper "EdDSA for more curves" (https://eprint.iacr.org/2015/677.pdf. In the RFC it gives N = 447 and in the paper it gives N = 448. A search through popular public reference code shows the value of N = 447 as per the RFC is the one being used. Can anyone confirm which of these two values is "correct" in the sense of its impact on security? Is this simply an error in the paper?
  2. After pruning as per the rules for each curve, the final maximum possible scaler value can be larger than L - 1, where L is the sub-group order, a prime. As I understand things, multiplying a base point by L yields neutral and multiplying by L + 1 is equivalent to multiplying by 1 (ie: it is cyclic and the points restart from the base point). Assuming my understanding of this is correct, is there a particular advantage to multiplying by a value larger than L-1 that I am not aware of?

To guarantee a neutral point value can never be generated (although virtually impossible if a good random number generator is used to get the initial scaler multiplier), would it not make more sense to take the initial random bits and perform R mod L, masking the lower bits as per pruning rules to stay in the same sub-group, checking for a zero result and choosing another random value if zero?

Or does the defined pruning method somehow guarantee that the result will never be a multiple of L in a way that is not obvious to a non-expert? If it does, I would see this as a way to avoid doing a modular reduction by L and everything would make sense.

$\endgroup$
4
  • $\begingroup$ Did you check the errata? rfc-editor.org/errata_search.php?rfc=8032 $\endgroup$
    – kelalaka
    May 2 at 8:37
  • $\begingroup$ 2) No there is not. And note that it is called scalar multiplication and usually denoted by $[\ell]G$ with small letters for scalars and capital for the points. The pruning is to make sure that we are not in the small group, too $\endgroup$
    – kelalaka
    May 2 at 9:35
  • $\begingroup$ @kelalaka "... not in small group...". Thanks, that part was clear. I wanted to understand if there was something about the pruning that would also protect against multiples of (l) so as to avoid generating the NEUTRAL value. $\endgroup$ May 3 at 12:42
  • $\begingroup$ @kellaka I was unaware there was an RFC errata resource, Thanks! I checked it and there is nothing there with respect to the value of 'n'. I suspect the authors of the paper made a typo as all the reference source (python, c , c++, etc) that I found uses the value in the RFC. $\endgroup$ May 3 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.