It's mostly number theory, with a bit of combinatorics.

the actual CS part of public/private key encryption is easy(tm), but the number theory is interesting.

Basically, the way private key encryption works is you take all the data, encode it using a private hashing function. This hashing function, we'll call it k, has an interesting trait: k(x) = y, k(y) = x (It's a symmetric relation.) So you have two people with the key, and one person sends data, that has been hashed using k. The second person un-hashes it using k.

The problem with this is that it requires both parties to have the key ahead of time; the key must either be sent using a private channel (in which case why do you need a new key?) or a public channel, in which case the key isn't private.

Public key encryption is similar, but there are a few important differences.

Instead, you have two functions, we'll call f and g. f(x)=y and g(y)=x. which measn f(g(x))=g(f(x))=x

You hold onto f, and send out g publicly. Everything you send out that you want to be certifiably from you, you put through f, and you tell anyone who wants to send you data (or read your data) to put it through g.

Here's where it gets interesting.

Person A has private key f, and public key g. Person B has private key j and public key k.

Person A wants to send x to person B, so he applies k to it. k(x)=y, he then applies f to it f(y)=w. Then he sends it to B, along with a *public* message that says "I've sent you data."

Person B then decrypts the data using g. g(w)=y. He then decrypts it again using j. j(y)=x.

Person B then knows two things: It was sent from person A (since only a has access to f), and it couldn't have been read by anyone besides the sender and himself (since it was encrypted with his key *before* being encrypted with f).

Now, generating these functions is where the number theory comes in...

In practice, normally a private key is sent over a "public" encryption, and then data is transfered back and forth over this (now secure) connection.

And I really don't know much beyond that.