-
Notifications
You must be signed in to change notification settings - Fork 1
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.
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
y2 = x3 + 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, y2. 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.
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.
public static bool PointIsValid(ECPoint point, ECCurve curve)It is important to check the validity of any of the data one receives. This method uses the built-in point validation in Bouncy Castle to ensure that the pair (x, y) is in satisfying the curve equation and that it is a member of the large, correct subgroup. In addition, we verify that the point object claims to belong to the same curve as the one used in the application.
The methods in the class Initiator implement all actions performed by the user side: initiating a new token, verifying that the response is correct, and randomising it for submission.
public (byte[] t, BigInteger r, ECPoint P) Initiate(ECCurve curve)This function computes the point P as described in list item (2) in Introduction to Privacy Pass. It chooses a random r, and then selects random t until t generates a valid curve point T.
public bool VerifyProof(X9ECParameters ecParameters, ECPublicKeyParameters K, ECPoint P, ECPoint Q, BigInteger c, BigInteger z)When a token is received from the token generator, one must verify that it is well-formed. VerifyProof generates the prover's commitments based on what it should be, given the challenge c. It then uses those to regenerate c using the strong Fiat-Shamir transform, and verify that it is equal to the one that was given. Readers familiar with the textbook invocation of the Fiat-Shamir-transform will notice that this differs, but is equivalent.
public ECPoint RandomiseToken(X9ECParameters ecParameters, ECPublicKeyParameters K, ECPoint P, ECPoint Q, BigInteger c, BigInteger z, BigInteger r)Using the previous function, RandomiseToken checks that the point Q is a valid token (i.e., that , and then computes a finalised token W in accordance to item (4) in Introduction to Privacy Pass.
The class TokenGenerator implements the functionality to turn a elliptic curve point P into a token Q, and provide a proof that Q is indeed kP, using the private key k.
public (ECPoint Q, BigInteger c, BigInteger z) GenerateToken(BigInteger k, ECPoint K, X9ECParameters ecParameters, ECPoint P)First, verify that P is a valid point on the curve. If so, compute Q = kP, and create the Chaum-Pedersen proof, which guarantees in zero knowledge that logG K = logP Q, where G is the generator of the cyclic group.
private (BigInteger c, BigInteger z) CreateProof(X9ECParameters ecParameters, BigInteger k, ECPoint K, ECPoint P, ECPoint Q)In order to prove the relation logG K = logP Q, generate a random number r, and create two commitments X = rG, Y = rP. Instead of sending these to the verifier in order to get a challenge in return, use the strong Fiat-Shamir transform (see the next entry) to generate a random number. Finally, compute the response z, modulo the order of the correct subgroup.
public static BigInteger CreateChallenge(ECPoint G, ECPoint P, ECPoint K, ECPoint Q, ECPoint X, ECPoint Y)This routine acts as the oracle in the Fiat-Shamir transform. It encodes the input data used in the proof protocol this far as bytes, and prefixes it with the bytes from a fixed string, in order to get domain separation. Finally, the complete byte array is hashed using SHA-256, interpreted as a number, and reduced modulo the curve order to interpret it as an element of the underlying field. The probability distribution over the field is slightly non-uniform due to this, but since the value is not used in the discrete log problem, this should not be a problem. In fact, it would probably suffice to use a significantly shorter number, as long as it was effectively unpredictable.
public async Task<bool> VerifyTokenAsync(BigInteger k, ECCurve curve, byte[] t, ECPoint W)In order to verify the token, take the seed t, generate the point T, and check that W = kT. However, if t was used before, the function will always return false. The seed store may be cleared whenever the key k is rotated.