[curves] Point validation (was: Twist security for elliptic curves)
Trevor Perrin
trevp at trevp.net
Sat Jun 20 16:59:41 PDT 2015
On Sat, Jun 20, 2015 at 4:17 PM, Mike Hamburg <mike at shiftleft.org> wrote:
>
> Actually, checking point on curve and point not in small subgroup is cheapish if the scalar is a multiple of the cofactor, as in x25519. At the end you need to compute x/z. If you compute (x/sqrt (xz))^2 and bail if the invsqrt doesn't exist, it rejects small order and twist points.
I think Lochter et al would argue for point validation at the *start*
of the computation, since they're thinking about fault and sidechannel
attacks.
If they'd be happy just rejecting small-order points that's cheap and
fairly easy [1]. But if they want point-in-main-subgroup validation,
then for cofactor>1 curves typically a scalar-multiply by the main
subgroup's order would be needed. Perhaps that's why they continue to
argue for Weierstrass (cofactor=1)?
> On a related note, I figured out a sane way to decaffeinate a cofactor-8 curve like curve25519. Working on implementing it. Of course, it's still a lot more complicated than not checking.
Interesting...
Trevor
[1] http://cr.yp.to/ecdh.html#validate
More information about the Curves
mailing list