Crypto.PubKey.ECC.Prim

Generate a valid scalar for a specific Curve

The inverse of a scalar modulo the order of the curve, without letting the scalar steer how long the work takes. This is what signing needs for its nonce, which is as worth hiding as the private key itself: a handful of signatures whose nonces are partly known give the key away.

On P-256 the C implementation does it; elsewhere it is inverseSafe. Nothing means the scalar has no inverse, which for the curves in use here means it was a multiple of the order.

Addition modulo the order of the curve.

On P-256 this is the C implementation's arithmetic, which works in a fixed width and so does not let the values steer it; elsewhere it is Integer arithmetic, whose cost follows the values.

Multiplication modulo the order of the curve, as scalarAdd.

Elliptic Curve point addition.

WARNING: Vulnerable to timing attacks.

Elliptic Curve point negation: pointNegate c p returns point q such that pointAdd c p q == PointO.

Elliptic Curve point doubling.

WARNING: Vulnerable to timing attacks.

This perform the following calculation: > lambda = (3 * xp ^ 2 + a) / 2 yp > xr = lambda ^ 2 - 2 xp > yr = lambda (xp - xr) - yp

With binary curve: > xp == 0 => P = O > otherwise => > s = xp + (yp / xp) > xr = s ^ 2 + s + a > yr = xp ^ 2 + (s+1) * xr

Elliptic curve point multiplication using the base

On P-256 this reaches the C implementation, which multiplies the base point through a table of its own.

WARNING: On every other curve, vulnerable to timing attacks.

Elliptic curve point multiplication.

Over a prime field this goes to C, four bits of scalar at a time, with the multiple to add taken from a table read by touching every entry of it. Over a binary field it also goes to C, as Montgomery's ladder: it carries the x coordinates of two consecutive multiples -- their difference being the point is what lets it carry no more than that -- and spends one addition and one doubling on every bit whichever way the bit goes, with the two exchanged by a mask rather than chosen by a branch. Either way the work follows the width of the curve's order and not the scalar.

What falls back on the Integer arithmetic below is a point that is not on the curve, the one point of a binary curve that has no x, and a prime the C will not take.

Multiplying the base point of a curve over a prime field -- which is what signing and making a key do, and nothing else does -- goes through a table of its multiples, built when that curve is first asked for one and kept afterwards. The build is a few milliseconds and the table a few hundred kilobytes, and a multiplication that uses it takes about a third of what one without it takes.

On P-256 the multiplication goes to the C implementation in Crypto.PubKey.ECC.P256, which has a table for the base point.

WARNING: What is left of the Integer arithmetic below -- a point off the curve, the one point of a binary curve with no x, a prime or a polynomial the C will not take -- has uniform operation counts at best, and uniform operation counts are not constant time: those operations cost what the values they are given cost.

Elliptic curve double-scalar multiplication.

pointAddTwoMuls c n1 p1 n2 p2 == pointAdd c (pointMul c n1 p1)
                                            (pointMul c n2 p2)

which, apart from P-256, is how it is done: the two multiplications separately, and then one addition. P-256 has a double multiplication of its own in C and takes it.

This used to be Shamir's trick, one pass over the bits of both scalars at once, which shares the doublings between them and is the right thing to do when the two multiplications would cost the same. They no longer do. pointMul goes to C, and over a prime field it multiplies the base point through a table of its multiples, which is a third of the price of an ordinary multiplication -- and the base point is one of the two here, since signature verification is what asks for this. Sharing the doublings with a pass in Integer arithmetic gives that up and more: on P-384 it costs twice what two multiplications in C cost, and on the curves over a binary field, whose addition needs an inversion where the C has a ladder that needs none, it costs two hundred times as much.

Both scalars are public wherever this is called from, so nothing here is meant to hide them.

WARNING: Vulnerable to timing attacks.

Decompose a point into index, residue, and parity.

Adapted from SEC 1: Elliptic Curve Cryptography, Version 2.0, section 2.3.3.

Compose a point from index, residue, and parity.

Adapted from SEC 1: Elliptic Curve Cryptography, Version 2.0, section 2.3.4.

Check if a point is the point at infinity.

check if a point is on specific curve

This perform three checks:

• x is not out of range

• y is not out of range

• the equation y^2 = x^3 + a*x + b (mod p) holds

over a prime curve, and the corresponding checks over a binary curve: the coordinates reduce to themselves in the field, and y^2 + x*y = x^3 + a*x^2 + b holds.

This is the check to make on a point that arrives from elsewhere, before multiplying it by a private number. Without it the multiplication is carried out in whatever group the supplied point generates rather than the curve group, and if that group is small the private number can be recovered from the result.

Two things it does not establish:

• The point at infinity is reported as valid, since it is a member of the curve group. It is not a usable peer value: multiplying it by anything yields the point at infinity again, which has no coordinates. Reject it separately where a peer is not allowed to send it.

• Being on the curve is not membership of the subgroup generated by the base point. The two coincide only when the cofactor is 1. Of the curves in CurveName that holds for every prime curve except SEC_p112r2 and SEC_p128r2, whose cofactor is 4, and for no binary curve, whose cofactor is 2 or 4. Where the cofactor is above 1 a point on the curve may still generate a small subgroup, and ruling that out needs a further check -- multiplying by the group order and requiring the point at infinity, or clearing the cofactor -- that this function does not make.

Check that a point is in the subgroup the base point generates, which is the further check isPointValid does not make. A point that is on the curve but outside that subgroup answers a multiplication modulo an order smaller than the group's, so the multiplier -- a private number, where the point came from a peer -- is revealed modulo that small order.

Where the cofactor is 1 the subgroup is the whole curve group and the answer is True for any point on the curve, at no cost. Otherwise the point is multiplied by the group order and the answer is whether that reaches the point at infinity, which costs one scalar multiplication. This is the check OpenSSL's EC_KEY_check_key makes.

The point at infinity is reported as in the subgroup, as isPointValid reports it valid; it is a member, and unusable for other reasons.

A point that is not on the curve at all has no meaningful answer here, so check isPointValid first.