paulmillr / noble-curves

Audited & minimal JS implementation of elliptic curve cryptography.
https://paulmillr.com/noble
MIT License
664 stars 62 forks source link

Negative scalar multiplication with curve point (ed25519, ristretto255) #100

Closed Tej81r closed 9 months ago

Tej81r commented 10 months ago

Hi, I'm developing code to generate pedersen commitments based on the ristretto255 curve. Pedersen's commitment is simply C = mG + rH, where G and H are two random elliptic curve points along a secret message m, and r is a random integer. To generate the commitment, I used the following code:

const mG = G.multiply(BigInt(m)); const rH = H.multiply(BigInt(r));

Using this lib, it is not permitted to have a scalar in the multiply function that is not in the range [1, max-1]. When I tried to pass the blinding factor or the secret value as negative, I received the following error:

Expected valid scalar < 7237005577332262213973186563042994240857116359379907606001950938285454250989, got bigint -12n

When the curve point multiplies with the scalar, I noticed a range check, as seen below:

assertInRange
  function assertInRange(n: bigint, max: bigint) {
// n in [1..max-1]
if (inRange(n, max)) return n;
throw new Error(`Expected valid scalar < ${max}, got ${typeof n} ${n}`);}

When we subtract the commitments, the blinding factor may become negative in some cases. During commitment verification, the commitment, blinding factor, and secret message will be passed, and commitments will be generated using the secret message and blinding factor and verified with the passed commitment.

How does one handle scenarios where the blinding factor is negative and you would like to verify the commitment? (We can't use ep.multiply(scalar) because scalar should be in the range [1, max])

Simply:

How to handle the below use case:

G. -- RisrettoPoint m -- -12( negative number) I want to multiply m with G as follows:

G.multiply(BigInt(m))

paulmillr commented 10 months ago

When we subtract the commitments, the blinding factor may become negative in some cases.

just do mod(-scalar, CURVE.n)