1
$\begingroup$

Am implementing x25519 (in 64 bit and 512 bit assembly) following the specifications in RFC 7748 (and its errata list !).

Need two clarifications please.

  1. The private key is randomly generated 32 byte string with MSB set to 0 and MSB-1 set to 1, and, last 3 bits set to zero. Now, once a random 256 key has been generated, it is made compliant to these specified requirements, and the corresponding public key has been computed. The clarification being sought is : does the private key remain this 32 byte string after the MSB/MSB-1 is set ? Does this imply that the actual count of universe of random private keys is restricted to 2^251 (256 - MSB - [MSB-1] - 3 LSB - all these bits are fixed) ? If an external user were to specify a key that is not compliant with this requirement, and the software modifies it to become complaint, does the external user specified private key needs to be updated with this post compliant string ?

  2. Most implementers (e.g. Michael Dull (apologies for not being able to type the umlaut in the surname) et. al. in paper "High speed Curve25519...") have mentioned that the last inversion step (Z^(p-2)) requires 254 squaring steps and 11 multiplications. I understand the 254 squaring steps, but am not sure what algorithm is used to restrict the count of multiplications to such a small number. If this is not a state secret, can I be directed towards the actual algorithm that generates the inversion mod p-2 with (just) 11 multiplications ?

Thanks for your attention and time.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

About your first question, yes, the set of private keys is restricted to those $2^{251}$ values that are always a multiple of $8$ and that's security by design:

  • By making sure the input scalar of the scalar multiplication algorithm is a $255$-bit value will the algorithm specified in the RFC will always perform 254 loops and each of those loops will perform the exact same operations (one addition, one doubling): it's a simple protection against simple side-channel analysis

  • To prevent against the invalid point attack (Bob giving to Alice a point of low order on another curve), only the $x$-coordinate is used, so the point belongs either to the curve or its quadratic twist. The only points of low order on those curves have order $2$, $4$ or $8$, so if Bob submits one of those, Alice will always get $0$ (representing the infinity point in the X25519 function) as an output of the key-exchange and detect that it is invalid. Invalid point attack and small subgroup attack are prevented.

You might want to read the original papers on it: Curve25519:new Diffie-Hellman speed records and Can we avoid tests for zero in fast elliptic-curve arithmetic?

About your second question, it is just fast exponentiation. Look at the binary decomposition of $p-2 = 2^{255} - 19 - 2$. Or look at some already written code (most of Curve25519 implementation come from the same reference).

Improve this answer
$\endgroup$
2
  • $\begingroup$ The binary decomposition of $p-2$ if full of ones. The naive implementation would lead to more than 200 multiplications. How these addition chains were computed? $\endgroup$
    – Conrado
    Sep 25, 2019 at 18:50
  • 1
    $\begingroup$ @Conrado Yes, it's not a simple square-and-multiply. Since it's a fixed exponentiation, a chain with less multiplication (squarings are cheaper) has been used. Maybe it was optimized by hand. $\endgroup$
    – user69015
    Sep 26, 2019 at 6:59

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.

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