2
$\begingroup$

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.

  1. 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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ also is the notion of a 'limb' widespread in cryptography? where does it come from? $\endgroup$ – Vega4 Aug 10 '18 at 13:20
  • 1
    $\begingroup$ @Vega4: some crypto, particularly asymmetric crypto like RSA DSA DH and as here ECC, uses numbers larger than a computer can handle in one unit, which are usually called bignums; crypto is an important use of bignums but not the only one. 'Limb' is used for bignums as an analogy to 'digit'; see crypto.stackexchange.com/questions/59839/… . $\endgroup$ – dave_thompson_085 Aug 11 '18 at 4:06
  • $\begingroup$ in the code above; cmult returns x and z as separate variables. isn't x already the public key? I understand that we use projective coordinates instead of affine coordinates to cut on the number of divisions. is that correct? what does crecip do? (it takes z and what's the result in zmone?) - the most misterious thing to me right now. The fmul function just seems to multiply two number which are in the 'polynomial' form. Actually from what I see seems like the 'real' Z-coordinate is in zmone; but then what's the format of z returned by cmult? how do these two differ? $\endgroup$ – Vega4 Aug 11 '18 at 10:04
  • $\begingroup$ zmone is multiplied by x in a call to fmul(z, x, zmone) which results in the 'real' X coordinate to be put into the 'z' variable.(right?) with call to fcontract we convert the 'polynomial form' back to little-endian. Thank you dave_thompson_085. $\endgroup$ – Vega4 Aug 11 '18 at 10:04

Your Answer

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

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