I've been studying Bitcoin's use of private/public keys and ECDSA, and I'm a bit confused at the moment about when to use mod(p) vs. mod(n).
For example, when doing a EC point multiplication (i.e., to compute Q=d*G), are the point coordinates modulo p?
Everything is mod(p) when doing the point multiplication which involves additions, subtractions (negations), multiplications, squarings, and division (multiplication by the inverse) all mod(p). Inversions are particularly expensive which is why it is a common technique to project the points into Jacobian coordinates to eliminate the divisions needed during the intermediate field arithmetic (the mod(p) stuff) followed by a final inversion to convert the answer back to affine coordinates. The main reason I mention that is one of the most popular techniques for performing the inversion mod(p) is to use extended Euclidean algorithm which essentially is repeatedly calculating successively smaller remainders (i.e modular arithmetic with arbitrary characteristics). So, while the overall answer when performing the inversion is mod(p), the actual intermediate steps of calculating the multiplicative inverse using the extended Euclidean algorithm essentially are modding with other numbers.
Is anything ever modulo n?
Yes, mod(n) is used during signature generation and verification. In particular, the signature verification involves calculating the multiplicative inverse of the 's' component of the signature mod(n) and signature generation involves calculating the multiplicative inverse of the private key mod(n). Do keep in mind that the private key itself is a field element in Fp (that is to say it is a value in the range [1, mod(p)-1]) .
And while on that topic, could someone explain the purpose of p (as in Fp) and n (as in the "order n of the generator point G", but this description is a little lost on me...)? If we never need to use mod(n), then p makes perfect sense as the number of elements in the field, but as soon as mod(n) is used, it seems that there is a range of numbers in Fp that are not used.
As I pointed out above, all of the base arithmetic needed to perform point multiplication (and point doubling) is mod(p). The mod(n) only happens during the signature generation and verification.
The purpose of the p is to provide a finite field. For example, let's use some small numbers and a modified version of the elliptic curve equation to illustrate the concept. Let's assume the prime is 11, the base point G is (4, 3) and the elliptic curve equation is y^2 = x^3 + 0. This generates the following points (mod 11):
(4, 3), (8, 6), (1, 9), (5, 1), (9, 4), (2, 7), (6, 10), (10, 2), (3, 5), (7, 8), (0, 0)
However, recall that the elliptic curve equation we chose for this example is: y^2 = x^3 + 0
Thus, the only points that are actually on the curve (mod 11) are (4, 3) and (0, 0). Therefore, "the order n of the generator point G" in this case is 2. Notice that the order is not prime in this case either, so aside from the fact that the numbers are so small it would be trivial to brute force, these would not be good parameters to choose.
If you'd like to see code that implements secp256k1 with comments, feel free to take a look at
https://github.com/conformal/btcec/ which is one of the core packages from
https://github.com/conformal/btcd.
