Private and Public Keys

Question

I have a very basic understanding of encryption and the encapsulation process, but for the life of me I can't grasp how public keys and private keys work, how they're made, and how they're exchanged. Can anyone break it down to a basic level, or point me in the direction of material that explains it Barney style. Thanks in advance.

Answer 1

How they work

Public and private keys work as follows. Every party who wants to communicate with others generates a private key which they keep secret. From that private key, they derive a public key, which they publish for anyone to see.

For example, if we have three agents, Alice, Bob, and Charlie, they will all have a secret key S_A, S_B, and S_C and a public key each, P_A, P_B, and P_C.

If Alice wishes to encrypt a message to Bob, she uses Bob's public key for encrypting the message. To decrypt the message encrypted with his public key, Bob must use his respective secret key.

How they are made

You don't need to understand how public and private keys are made to understand how to use public-key cryptography. It is only necessary to understand the following basic concept: While there is a one-to-one correspondence between a public and a secret key, it is computationally easy to go from the private key to the public key, while it is computationally hard to go from the public key to the private key.

Such problems form the basis of asymmetric cryptography and are abundant in computer science. For example, the factoring problem has this asymmetry. If I give you two prime numbers p and q (the private key), you can readily evaluate their product n = pq (the public key). However, if I give you the public key and I tell you it's the product of two large primes, it is hard for you to find these two primes even though there's only one unique solution. The factoring problem is in fact used in the RSA cryptosystem. Other problems that have this asymmetric property are problems on lattices and the discrete logarithm problem in finite groups.

How they are exchanged

Exchanging public keys is easy. Public keys can simply be published, as they are not secret. For example, they can be published on a newspaper, spoken over the phone, sent on an email, or uploaded to public key servers.

How does asymmetric encryption work?

This is a more complicated question that you don't need to understand to move on and use public-key cryptography. The math is somewhat convoluted. It is also specific to various cryptosystems. The easiest to understand is the RSA cryptosystem. To understand it, you need to study some basic algorithms and facts such as the Fundamental theorem of arithmetic, the Extended Euclidean Algorithm, the Miller-Rabin primality test, Fermat's Little Theorem and its extension Euler's theorem. Following this knowledge, Wikipedia's explanation of RSA can be understood without much effort.