Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.
How does it encrypt something with one key and decipher it with another key?
Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure.
One possible design for a public key encryption system is that of a trapdoor permutation. A trapdoor permutation is a mathematical function which is a permutation of some space, such that computing the function in one way is easy, but the reverse is hard, unless you know some information on how the trapdoor permutation was built. Encryption is applying the function on a message, decryption is about using the trapdoor to reverse the function.
For RSA, a well-known asymmetric encryption algorithm, consider a rather big (say 300 digits or more) integer $n$. $n$ is composite: it is the product of two big prime integers $p$ and $q$. There are more such composite integers than there are particles in the observable universe, so there is no problem in generating such an integer. $n$ is called the modulus because we will compute things "modulo $n$". It turns out that:
So the public key is $n$, the trapdoor permutation is raising to the power 3, and the reverse is computing a cube root; knowledge of $p$ and $q$ is the private key. The private key can remain "private" even if the public key is public, because recomputing the private key from the public key is a hard problem.
There is a bit more to RSA than the description above (in particular, RSA does not necessarily uses the power 3), but the gist of the idea is there: a function which is one-way for everybody, except for the one who selected the function in the first place, with a hidden internal structure which he can use to reverse the function.
SSL (now known as TLS) is a more complex beast which usually uses some asymmetric encryption during the initial stages of the connection, so that client and server end up having a "shared secret" (a commonly known sequence of bits); the shared secret is then used to apply conventional encryption and decryption to the rest of the data ("conventional" meaning: same key to encrypt and decrypt).
A lot of answers have said "a mathematical structure" which is absolutely right, but I still see there might be a question: how on earth can one exist? I'll try and fill that gap at a simpler level.
So a simple caeser-shift cipher might look like this: $x+7$. In our really simplistic, dangerous example, the "key" here is $7$. If I have some encrypted text, I know that by subtracting $7$, I get back to $x$. Therefore, this is a really simple example of a symmetric cipher, because what I do one way also allows me to undo it.
As you might have noticed, most domains in cryptography are finite - for example, there are only 26 letters in the alphabet. At some point you need to "wrap around". Mathematics provides us with a technique to do this called modulo arithmetic. Essentially, under a modulus, you can think "if I divide this by the modulus, the number I have is the remainder". some examples:
$4 = 4 \mod 7$
$8 = 1 \mod 7$ (8/7 = 1 remainder 1)
$4+7 = 4 \mod 7$ (11/7 = 1 remainder 4)
$-3 = 4 \mod 7$ (not so hard... what happens when you add 7 to -3?)
As you can see, arithmetic holds under modulo. Undergraduate mathematics courses rigorously establish these truths and if you're interested, read up on Number and Group theory. The next step is to understand that multiplication also holds:
and so on. Multiplication in mathematics often throws up some problems when it comes to inverses - for example, how do I go from 1 back to 5? I can multiply by 5. How do I go back to 2 from 1? Multiply by 2. These examples are not quite right in terms of what I wanted to show, so here are some more:
With these examples, I've shown that you can go from 6 to 4 and back to 6 using multiplication, but by multiplying by different things.
This is one, very simple way to create such a mathematical structure. The genius of RSA is choosing the numbers involved in such a way that one can easily determine how to get to an encrypted value, but not back again. I've explained it fully in another answer; however, in essence, it is simply a more complicated version of what we've done here. The clever part is understanding those structures and which choices of numbers make good/bad keys and which work/do not.
But you're telling me multiplication is hard to undo: what about division?
Firstly, it really depends on circumstances. Under some circumstances, like the trivial example I present above, finding an inverse or even using division is easy. It's important to think about what division means. In a rational (any number you can write as a fraction) field, multiplicative inverses exist in the form $p * (1/p)$ (as well as $p*q = 1$).
However, when considering RSA, note that encryption is $t\times t\times \ldots = t^e = c \mod n$ for some public key $e$. So to compute the inverse, we'd need to compute $c \times (1/t) \times (1/t) \times \ldots = c \times (1/t)^e \mod n$. The reason for this is that each multiplication of $t$ needs to be undone by an inverse $(1/t)$ but it should be clear that if we only have the ciphertext $c$, we don't know $t$ to compute $1/t$.
So our next possible route is to compute $c^{1/e}$ as $t^{e*1/e} = t$. This is equivalent to computing the eth-square root of $c$ (for example, $x^{1/2} = \sqrt{x}$) which is hard to do when under a modulus of the size that RSA requires you use - under certain circumstances. Under others, it's known as the "cube root" attack: see this presentation and this one.
Other public key crypto systems use similar observations - for example, Diffie-Hellman relies on this property: $$a^x = b \mod n$$ Under certain cases of n (for example $(\mathbb{Z}_p, \times )$ i.e. when n is prime and we are interested only in multiplication and therefore a is greater or equal to 1) this is hard to reverse. This forms the basis of a number of other public cryptosystems.
The "How" is already explained well by others, but as far I can see, nobody wrote about "What does asymmetric encryption do?".
It does not, as many think, magically allow two parties Alice and Bob to communicate securely over a public channel.
Instead, given an authentic channel from Alice to Bob at any time, public key cryptography allows to convert subsequently a public channel from Bob to Alice into a secret channel.
In contrast conventional secret key cryptography cannot exploit authentic channels unless they are also secret. Given a secret (but maybe not authentic) channel from Alice to Bob, any time later a public channel from Bob to Alice can be made authentic using secret key cryptography (MAC), but this channel can only be secret if the channel from Alice to Bob was authentic. (For Completeness: The main purpose of secret key cryptography is to convert a public channel from Alice to Bob into a secret channel, if there was a secret channel from Alice to Bob before.)
At a basic level, the client (i.e. your browser) and the server negotiate a key exchange algorithm to derive a random session key and then they use that private key to encrypt traffic with a symmetric algorithm.
There's a lot of detail to the process and I wrote about this extensively on my blog: The First Few Milliseconds of an HTTPS Connection
The simplest way to explain it is that the two keys have a special mathematical relationship that allows one (the secret or private key) to undo what the other (the public key) does.
All asymmetric encryption schemes require some operation that cannot be easily reversed unless you have some secret piece of knowledge. With that piece of knowledge, the operation can be reversed.
One common encryption scheme uses the following relationships:
Given very large numbers m and n, pick a number p, compute:
s = p m modulo n
Now try to reverse that operation and get p from s, m and n. Given p, m, and n, calculating s is easy, but given m, n, and s, calculating p is very hard.Given two very large prime numbers, m and n, compute:
k = m x n
Now try to reverse that operation and get m and n from k. Multiplication is simple. Factoring very large near primes is very hard.
Asymmetric(-key) encryption — also known as public-key encryption — uses two different keys at once: a combination of a private key and a public key. The private key is known only to you, while the public key can be published to be seen by anyone who wants to communicate securely with you.
To decode an encrypted message, a computer must use its own private key and the public key, provided by the originating computer. Even though a message sent from one computer to another won't be secure (since the public key used for encryption is published and available to anyone), anyone who picks up the public keys can't use them without the related private keys.
The key pair is based on big (long) prime numbers. What makes public-key encryption secure, is that there is essentially an infinite number of prime numbers available… which theoretically means that there are nearly infinite possibilities for keys.
If you would like to dive into it a bit deeper, you should look at some well-known examples of public-key cryptography… like (as one example of many) the Diffie–Hellman key exchange.
I am studying the mathematics behind modern cryptography from the excellent text An Introduction to Mathematical Cryptography. Here is their explanation of the same:
Suppose Alice is someone who wants to engage in secret communication with multiple people, one of them being Bob. Eve is our regular attacker, always trying to get behind the encryption schemes and extract the plaintext. An abstraction of how public key cryptography would help Alice and Bob to communicate securely is as follows.
Alice places a safe out there in the open. Everyone can send her messages by dropping pieces of paper inside a slot on the safe. However, only Alice has the needed key to open the safe and extract the messages.
Here, the safe represents the public key of Alice, visible to everyone. The messages once inserted in the slot and inside the safe, represent the plaintext being operated upon by both Alice's public key and Bob's (and all others who might send messages to her) private key. Alice opening the safe with the key represents Alice using her own private key to decrypt the ciphertext. Sure enough, in PKC, the receiver's public key is visible to everyone, while both the sender and receiver must maintain their private key secret.
I guess the use of trapdoor functions and the actual mathematics behind PKC is already well explained by some of the other answers. But this analogy helped me understand the concept of the public and private keys.
There are 2 keys mathematicly related to each other . These work with a so called trapdoor function = very easy on the one side very hard on the other . eg : multiply 2 big numbers together is easy . Finding out the prime numbers they consist of is vcery hard ( nearly impossibe ) . In RSA this works like that . In ECC things are a bit different . The encryption algo uses This public key to encrypt something . Only the related private key can decrypt it . ( the maths behind it are very complex )
