5
$\begingroup$

I'm going through the below snippet of code which does multiplication of point over the curve Curve25519:

bits256 curve25519(bits256 mysecret,bits256 basepoint)
{

    bits320 bp,x,z;
    mysecret.bytes[0] &= 0xf8,
    mysecret.bytes[31] &= 0x7f,
    mysecret.bytes[31] |= 0x40;
    bp = fexpand(basepoint);
    cmult(&x,&z,mysecret,bp);
    return(fcontract(fmul(x,crecip(z))));
}

Here I didn't understand why the few bits are set and few bits are cleared in the mysecret. Can't I perform multiplication of any point over the curve? Is there any restriction on it?

Is curve multiplication is commutative over curve25519?

Can you help me understand multiplication of points when using Curve25519?

$\endgroup$
  • 1
    $\begingroup$ It's simply a trick with bits to make sure the resulting value is in between a range. It has nothing to do with the multiplication itself. I'm pretty sure it is in the standard. You don't want to multiply with the value 1, I'm sure and modular multiplication with a value that is over the modulus isn't a good idea either. Generate, test until you get the right number is not constant time thus dangerous and CPU expensive as it requires branching. $\endgroup$ – Maarten Bodewes Nov 20 '17 at 12:47
  • $\begingroup$ Of course you throw away 5 bits that do not need to be brute forced, but as $2^{256 - 5} = \operatorname{plenty}$, who cares? PS should that not be bits256 bp,x,z or is additional space required for intermediate storage? $\endgroup$ – Maarten Bodewes Nov 20 '17 at 12:55
  • $\begingroup$ nope, bp,x,z are of size bits320. By setting so will the multiplication over curve is associative? I ran some test run, I'm getting different results which shows that ab is not equal to ba over the curve25519. $\endgroup$ – sg777 Nov 20 '17 at 13:14
  • 1
    $\begingroup$ Looks like you mean commutative. This is not commutative, because you're actually multiplying different things: a point (represented by its X coordinate) with a scalar. What you are actually doing here is add the point to itself mysecret times. Switching the operands doesn't make sense in this context. $\endgroup$ – Frank Denis Nov 20 '17 at 13:50
2
$\begingroup$

The Curve25519 paper gives you some hints about this. In Section3, it says:

Responsibilities of the user. The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32 uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte.

Curve25519 lets you use as secret key any 32-byte sequence that fulfills this restrictions. Although in principle multiplication assumes that you introduce a valid secret key fulfilling all these conditions, the code you mention tries to enforce this on its own. Note that it doesn't perform a validation check on the secret key, but directly modify it in case it didn't comply. So, clearing bits 0, 1, and 2 of the first byte is this line of code:

mysecret.bytes[0] &= 0xf8

Clearing bit 7 of the last byte is this one:

mysecret.bytes[31] &= 0x7f,

And setting bit 6 of the last one is the next line:

mysecret.bytes[31] |= 0x40;

With respect to your last question, I think there may be a misunderstanding. In the comments, you seem to be asking about commutativity of Curve25519 (i.e., $ab == ba$), rather than associativity. Remember that you are performing scalar multiplication. That is, the multiplication of a scalar $x$ by a base point $G$. In this case, the scalar is the secret key. Therefore, it doesn't make sense to think of commutativity.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, I mean to ask about commutative property. so it means adding a times of b over a curve doesn't equal to adding b times of a, am I right here? $\endgroup$ – sg777 Nov 20 '17 at 13:48
  • 1
    $\begingroup$ I think you mean $(ab)G == (ba)G$. Yes, this is true. In fact, this property is what ensures that DH exchange works at all. $\endgroup$ – cygnusv Nov 20 '17 at 13:54
  • $\begingroup$ One small doubt, in DH is it the case if either any of a or b is known, it is easy to find another. I mean say if a is known, one can compute aG and compute inverse(aG). Then does (ab)G*inverse(aG)=b(aG)*inverse(aG)=b. $\endgroup$ – sg777 Nov 20 '17 at 14:13
  • 1
    $\begingroup$ No, I think you have several misunderstandings. Scalar multiplication takes two different types of elements: a scalar (e.g., a, b, ..) and a point (e.g., G), and outputs another point (e.g., aG). The inverse of a point, is also a point. The inverse of a point, is also a point. And you cannot "multiply" a point by a point (or its inverse). $\endgroup$ – cygnusv Nov 20 '17 at 15:18

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.