search

BjoernMHaase / AuCPace

10 stars 1 forks source link

Test vector should be added to RFC for overflow checks for inverse_scalarmult_25519 #2

Open BjoernMHaase opened 4 years ago

BjoernMHaase commented 4 years ago

As Steve Thomas has pointed out,

when carrying out arithmetic modulo the sc25519 field (modulo the prime order subgroup of Curve25519), one might be tempted to drop the most significant bit.

After sc25519_invert(), the scalar is modulo 0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed then it is multiplied by 8 without modulo thus has a max value of 0x80000000000000000000000000000000a6f7cef517bce6b2c09318d2e7ae9f60.

The for loop in the montgomery ladder implementation might ignore the highest order bit.

There should be a test vector added to the RFC to check for this corner case (it won't be detected in random tests!).

BjoernMHaase commented 4 years ago

There should also be a test vector that inserts a point that is not on the prime order subgroup of the curve where the inverse scalar (1/r) % 8 is nonzero. The inverse_scalarmult function should be checked to always return a point on the prime-order subgroup, just as X25519 does.

BjoernMHaase commented 4 years ago

The jupyter notebook already has the corresponding code for generating the test vectors.