Questions about the Curve25519-donna implementation

Question

I'm trying to understand the implementation of the following function: Please note questions in comments.

int curve25519_donna(u8 *mypublic, const u8 *secret, const u8 *basepoint) {
limb bp[5], x[5], z[5], zmone[5]; // why 5 elements in each?
uint8_t e[32];
int i;
for (i = 0;i < 32;++i) e[i] = secret[i];
e[0] &= 248;
e[31] &= 127;
e[31] |= 64;
fexpand(bp, basepoint);
cmult(x, z, e, bp);
crecip(zmone, z);
fmul(z, x, zmone);
fcontract(mypublic, z);
return 0;

}

1. Why do all the functions work on a polynomial form of a number? and thus require fexpand function? as I understand fcontract does the opposite.
2. e[0] &= 248; e[31] &= 127; e[31] |= 64; - I've found this suggested in the whitepaper, is there any particular reason behind doing this?
3. Why is cmult performed twice? what does crecip function achieve?

From what I read on curves in the Weierstrass form, in order to get a public key H, one needs to compute H = dG (where G is the base point of the subgroup). Then the situation is entirely different in case of Ed25519 (I know Montgomery Curve25519 is birationally equivalent to a twisted Edwards curve Ed25519), where generation of the public key involves hashing and results in a non-linear key-space.

4. In contrast with Ed25519, Can private/public keys in Curve25519 be said to form a linear space? I was wondering whether it would be possible to generate public keys independently to the corresponding private keys using a common index in case of Curve25519.

Update: besides the excellent answer provided by Lery; those of you not familiar with projective coordinates might find this useful.

Answer 1

You have 5 limbs because it is based on DJB's papers and as the Ed25519 paper mentions, it's using a $2^{51}$ radix representation for performance reasons.

It does so in order to avoid carries when performing field multiplication. Because otherwise the carry bits need to be handled by subsequent additions, which slows down even modern CPUs.

So according to the paper, to reduce the number of expensive adc/subc instructions, they represent an element $x$ of $\mathbb{F}_{2^{255}−19}$ as $(x_0,x_1,x_2,x_3,x_4)$ with $x =\sum_{i=0}^{4} x_i 2^{51i}$.

So in the end the multiplication should be accepting inputs with each limb having up to 54 bits.

Working with polynomial form allows to efficiently perform computation modulo the field's order. It allows to simplify the code required to implement the different arithmetic operations and thus is more comfortable to work with. Polynomial form is the natural way to represent integers modulo something.

Now regarding the bit manipulations done on the secret key, they are done in order to convert (random) 32 bytes into integer scalar.

The bit manipulation are there to set the three least significant bits of the first byte and the most significant bit of the last to zero, set the second most significant bit of the last byte to 1. This means that the resulting integer is of the form $2^{254}$ plus eight times a value between $0$ and $2^{251} - 1$ (inclusive).

Now, as for why they are performed, the lower three bits are cleared to prevent a small subgroups attack. And now regarding the MSB, it is set to 1 in order to avoid timing leaks.

Regarding the reason for the presence of two multiplication cmul first and fmul next, that's because cmul is actually computing, for an integer $n$ and a point $V$ the value $Curve(nV)=x/z$, so we have that $z\cdot Curve(nV) = x$.

Since we don't want the x-coordinate of the resulting point in this short form $x/z$, we need to convert it into the actual x-coordinate value, hence the crecip and fmul calls.

Finally, yes you should be able to derive private key and public keys independently of each other à la BIP32.