I've often heard it said that if you're logging in to a website - a bank, GMail, whatever - via HTTPS, that the information you transmit is safe from snooping by 3rd parties. I've always been a little confused as to how this could be possible. 

Sure, I understand fairly well (I think) the idea of encryption, and that without knowing the encryption key people would have a hard time breaking the encryption. However, my understanding is that when an HTTPS connection is established, the encryption key is "discussed" between the various computers involved before the encrypted connection is established. There may be many factors involved in choosing an encryption key, and I know it has to do with an SSL certificate which may come from some other server. I do not know the exact mechanism.

However, it seems to me that if the encryption key must be negotiated between the server and the client before the encryption process can begin, then any attacker with access to the network traffic would also be able to monitor the negotiation for the key, and would therefore know the key used to establish the encryption. This would make the encryption useless if it were true.

It's obvious that this isn't the case, because HTTPS would have no value if it were, and it's widely accepted that HTTPS is a fairly effective security measure. However, I don't get why it isn't true. In short: how is it possible for a client and server to establish an encrypted connection over HTTPS without revealing the encryption key to any observers?

It is the magic of public-key cryptography. Mathematics are involved.

The asymmetric key exchange scheme which is easiest to understand is asymmetric encryption with RSA. Here is an oversimplified description:

Let n be a big integer (say 300 digits); n is chosen such that it is a product of two prime numbers of similar sizes (let's call them p and q). We will then compute things "modulo n": this means that whenever we add or multiply together two integers, we divide the result by n and we keep the remainder (which is between 0 and n-1, necessarily).

Given x, computing x3 modulo n is easy: you multiply x with x and then again with x, and then you divide by n and keep the remainder. Everybody can do that. On the other hand, given x3 modulo n, recovering x seems overly difficult (the best known methods being far too expensive for existing technology) -- unless you know p and q, in which case it becomes easy again. But computing p and q from n seems hard, too (it is the problem known as integer factorization).

So here is what the server and client do:


The server has a n and knows the corresponding p and q (it generated them). The server sends n to the client.
The client chooses a random x and computes x3 modulo n.
The client sends x3 modulo n to the server.
The server uses its knowledge of p and q to recover x.


At that point, both client and server know x. But an eavesdropper saw only n and x3 modulo n; he cannot recompute p, q and/or x from that information. So x is a shared secret between the client and the server. After that this is pretty straightforward symmetric encryption, using x as key.

The certificate is a vessel for the server public key (n). It is used to thwart active attackers who would want to impersonate the server: such an attacker intercepts the communication and sends its value n instead of the server's n. The certificate is signed by a certification authority, so that the client may know that a given n is really the genuine n from the server he wants to talk with. Digital signatures also use asymmetric cryptography, although in a distinct way (for instance, there is also a variant of RSA for digital signatures).
