Maths: What the Core Methods Really Do

The mathematics of Privacy Pass is translated into code in this project. Read on to learn what the equations in the code are doing.

ECCurveHash.cs

public static ECPoint? HashToWeierstrassCurve(ECCurve curve, byte[] t)

This function takes a (presumably random) number t, and creates a point on the curve from it. All elliptic curve representations in Bouncy Castle are currently on Weierstrass form, which means that they satisfy the formula

y² = x³ + ax + b

within some field, and where x and y are variables and a and b are fixed field elements determining the curve. Arithmetics on the field is handled by Bouncy Castle. The variable x is filled with the BigInteger representation of SHA-256(t), after which the right hand side of the above equation is computed. This gives a value for the left hand side, y². Now, there is a 50 % chance of that element having a square root in the field. We attempt to compute it. If it doesn't exist, the function returns null, otherwise we have a known pair (x, y) which is indeed on the elliptic curve. Finally, we ensure that the point is not a member of a small-order subgroup, in which case we return null. If all checks have succeeded, we have created a point on the curve, and which belongs to the correct group.

ECCurveRandomNumberGenerator.cs

public static BigInteger GenerateRandomNumber(ECCurve curve, SecureRandom random)

We wish to choose a number between 0 and the order of the subgroup we use. To do so, we use the provided randomness generator to choose a number approximately as large as the order of the curve. However, using a random number on a cyclic group can be likened to wrapping a piece of string around a cylinder. Our random number ("the string") is likely to be slightly longer than the order ("the circumference of the cylinder"), and so certain parts of the cylinder would have a greater chance of being covered, hence skewing the randomness slightly away from a uniform distribution. To avoid this, we keep choosing a random number until it is within bounds, rather than reducing it modulo the group order.