2
$\begingroup$

My implementation requires me to generate randomly a valid scalar on the curve. As far as I understand it is not a random number generation but more complicated thing.

I have to generate such scalars on the server and the client side according following scheme:

Client:

X = x × G + w0 × M

where

  • x - generated scalar!

  • G - curve base point

  • w0 - a number represented by 32-byte array

  • M - constant point on the curve

  • X - resulted point

Server:

Y = y × G + w0 × N

where

  • y - generated scalar!
  • G - curve base point
  • w0 - a number represented by 32-byte array
  • N - constant point on the curve
  • Y - resulted point

Then client and server exchanges X and Y points.

And calculate point Z as follows:

  • Client: Z = x × (Y − w0 × N)
  • Server: Z = y × (X − w0 × M)

Question#1: what the mechanism is for valid scalar random generation on the curve?

Question#2: what is the math operation behind points subtraction?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Scalars are not "on the curve". Scalars are just positive integers (including zero) less than the group order $\ell$ of the curve generator. E.g. for the Ed25519 curve, the group order $\ell$ is $2^{252} + 27742317777372353535851937790883648493$.

To generate an unbiased random scalar, use "rejection sampling". This means to use a mechanism to securely generate a uniformly random integer within a range that is at least as large as $\ell$, and accept it only if it is less than $\ell$.

All scalar operations, including addition, multiplication, and subtraction are done $mod\ \ell$. Division is achieved by finding something called the "modular multiplicative inverse".

Point operations, such as point subtraction, will be handled by your EC library. See here for more.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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