Cryptography in Computer Science

Dec 2007
What mathematical branch is most included in the cryptography part? Isn't it mostly number theory?

I was interesting how the computer uses numbers to figure out the cryptography. Are there a lot of advanced algorithms programmed in the computer hardwares for the number theory system to work?
Dec 2007
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.
Dec 2007
In cryptography there's a lot of high-level number theory, and more specifically algebraic number theory (finite fields, etc ...). There's quite a lot of complexity theory as well (as the question of security is clearly contingent upon the complexity of the algorithms required to crack the encryption).
Jun 2009
Yeah, It is really helpful to me get knowledge about Crytography. Thanks for sharing.
Feb 2011
That is really a great source of information given, it would be interested to know how cryptography is used in the computers.