1 (mod n)Highly secure symmetric cryptosystems can be constructed but all share, at the very least, one fundamental weakness - how do you keep the secret key secret? By the definition of a symmetric cipher, both the sender (Alice) and the receiver (Bob) must have the same key. This means that it must somehow be distributed to both parties in such a way that it is not compromised. In other words, we need a secure channel to transmit the key over - but if that channel itself relies on a symmetric cipher, how did the keys for that cipher get distributed? At some point, at least one secret key had to be transmitted over a secure channel that did not require a previously existing shared secret.
Conceptually, the simplest solution to this distribution problem is to have Alice and Bob physically get together in a location where they are confident that no one (Eve) is eavesdropping on their conversation and exchange their secret keys directly. Now they can go their separate ways and transmit messages back and forth at a future time. But what if it is not possible for Alice and Bob to get together beforehand? One way we could get around this is by using a "trusted third party" (Trent) whose role is to convey the necessary keys to Alice and Bob. Perhaps Trent is a courier or perhaps he is someone that has previously established one secret key with Alice and another one with Bob. The mechanics of transmitting the keys that Alice and Bob need may become pretty convoluted, but given enough time and effort, it will be possible to get the keys distributed.
But what if either the time or the effort needed to distribute the secret keys in this fashion is not available? What if Alice and Bob have never previously heard of each other, have no trusted third party they can use, and Alice finds herself in a situation of needing to send Bob a message immediately but securely?
If Alice can establish an open (insecure) communication with Bob, then perhaps the two of them can establish a key that way. Of course, they have to assume that their enemies are listening in to everything they say, but if they are sufficiently circumspect then they may be able to exchange a symmetric key that they can use immediately but that will take their enemies a while to figure out. If it takes their enemies long enough so that any information Alice and Bob share via their new symmetric key stops being of any value before their enemies finish, then they have succeeded in having a secure communication. Remember, secure doesn't mean secure forever, just secure long enough for the intended purpose. One way to do this conceptually is with Merkle's Puzzles. Another way of doing this, which is very practical and used countless times everyday on the Internet, is with Diffie-Hellman Key Exchange.
But what if Alice can't even establish an insecure communication link with Bob? What if she needs to encrypt the message and send it on its way before Bob is even aware that a message might ever be coming. As remarkable as it may seem at first, this is actually quite possible if Bob has done a bit of legwork ahead of time and made the necessary information available where anyone (Alice, Eve, and everyone else in the world) can access it.
What if Bob could just make up an encryption key and publish it openly for anyone to use at any time they needed to send Bob an encrypted message? If he were to do this, then clearly Alice would easily be able to get the information she needs to encrypt her message. Once she knew that she needed to send Bob a message, she must merely look up Bob's published encryption key. This is the cornerstone of public key cryptography.
"But wait," you might say, "any information that Bob makes publicly available that permits Alice to encrypt her message is also available to Eve and everyone else." That's very true. Eve will be able to do anything with that information that Alice could do - at least anything that only relies on Bob's published information. But keep in mind that Alice and Eve aren't interested in doing the same things - Alice wants to be able to encrypt a message while Eve wants to be able to decrypt a message. Bob doesn't care that Eve has the ability to encrypt messages. If the publicly available information is such that no one other than Bob can decrypt a message that was encrypted using the public information, then life is good. Notice that this means that not even Alice can decrypt the message she encrypted.
Unfortunately, with a symmetric cipher, anyone that has the encryption key also has the decryption key since, by definition, they are the same thing - hence they would be able to use that information to decrypt the message as easily as Bob himself. If we can construct an asymmetric cipher - one in which the information needed to decrypt the message is different from that needed to encrypt it, then public key cryptography becomes possible, at least in theory.
While important, however, simply having an asymmetric cipher is not sufficient. As with a symmetric cipher, it still must be the case that the recovery of the plaintext from the ciphertext must require knowledge of the decryption key. In addition, however, it must also be the case that knowledge of the encryption key cannot be used to gain that knowledge of the decryption key. To get a better feeling for these issues, let's explore some simple asymmetric ciphers that fail to satisfy these additional requirements.
If Alice wants to transmit the number 14 to Bob, she might look up Bob's public key and discover that it is 5. The algorithm in use tells her to construct the ciphertext by multiplying her message by Bob's public key. She does so and gets 70, which she then transmits. Bob, upon receiving the ciphertext, multiplies it by his private key, which is 0.2, and gets 14. He has successfully recovered the plaintext using a different key relying on the following relation:
C = P*e [Encryption Process used by Alice]
P = C*d [Decryption Process used by Bob]
Where, again, P is the plaintext, C is the ciphertext, e is the encryption key, and d is the decryption key..
Hence
P = (P*e)*d
P = P*(e*d)
As is almost certainly already apparent, this cryptosystem defines the decryption key to be the multiplicative inverse (i.e., the reciprocal) of the encryption key.
How secure is this system? Clearly not very secure at all. This cipher fails both of the additional requirements. Even without knowing the decryption key, everyone who knows the algorithm can simply use the encryption key to recover the plaintext! They can do so by dividing the ciphertext by the encryption key. Even if that were not possible, they could still use the encryption key to deduce the decryption key because, in the domain of real numbers, finding the multiplicative inverse of an integer is a trivial thing to do.
Let's milk this example a little further and address another problem with it. In a cryptosystem, we need our work to produce exact results which generally means that we do not want to work with anything other than integers. For this reason, we generally use modular arithmetic and work in a "modulo-n" world where all answers are eventually reduced modulo-n for whatever value of n happens to define that world. For example, Alice might have looked up Bob's public key and found it to be (5, 29). The algorithm now in use tells her to multiply her message by the first number and reduce the result modulo the second number. Her final ciphertext would then be12 since 14*5 (mod 29) is 12. Upon receiving 12, Bob would use his private key, which is (6, 29) to recover the plaintext 14 since 12*6 (mod 29) is 14.
It might appear that deducing the private key (6, 29) from the public key (5, 29) might be difficult, especially if we were to catalog a few other public/private key pairs for this modulus:
At first glance, it appears that there is no simple relationship between one key and it's mate. But this is merely an illusion. What happens if you multiply the first number in the encryption key pair by the first number in the decryption key pair and reduce the result modulo-29 (the shared second number in both key pairs)? In each case, you should get 1 as the answer.
The underlying relationship between the public key (e, n) and the matching private key (d, n) is that we require:
e*d
1 (mod n)
This, by definition, means we are looking for d such that
e*d = 1 + k*n
for some integer k (we don't care what the value of k is, just that it exists).
Notice that our algorithm is really the same as before - the decryption key is simply the multiplicative inverse of the encryption key. The only difference is that we are restricting ourselves to a modulo-n world. In this world, the concept of "division" really doesn't exist and so, at least technically, we can't simply divide the ciphertext by the encryption key to recover the plaintext. Nor can we simply claim that d is equal to 1/e. However, very efficient methods do exist for finding multiplicative inverses in modulo-n worlds. One such method is the Extended Euclidean Algorithm. The existence of such methods means that public/private key pairs based on multiplicative inverses, even those in modulo-n worlds, are not secure.
What other options are there?
Instead of multiplication and its inverse, how about exponentiation and it's inverse (a.k.a., logarithms)?
If we were to try to use exponentiation as the basis for our cipher, we might start with ordinary exponentiation. The most obvious form would be.
C = Pe
Where P is the plaintext and C is the ciphertext.
In the domain of real numbers, this provides no security since:
P = b(log_b(C)/(e))
where the logarithm is taken to the base b.
But, in a modulo-n world, we have
C
Pe (mod n)
and it turns out that taking logarithms in a modulo-n world is a very hard thing to do. Known as the "discrete logarithm problem", to date no one has devised a means of doing so that is significantly more efficient than brute-force trial and error.
But, if the discrete logarithm can't be used to decipher the message, then how will the intended recipient be able to do so? The answer is to exploit the fact that anything raised to the power of one is unchanged. In other words, the underlying relationship that we are going to exploit is the following:
C
Pe (mod n)
P
Cd (mod n)
Hence
P
(Pe)d (mod n)
P
P(ed) (mod n)
This works provided the product of the encryption and decryption keys is unity - in other words, that the encryption and decryption keys are once again multiplicative inverses. But, didn't we just conclude that, even in a modulo-n world, finding the multiplicative inverse of the published encryption key is a straight-forward task? Yes and no. It is straight-forward only if we know which modulo n world we are working in - and, because of the properties of modular exponentiation, the exponents live in a different world than the rest of the relationship! Namely, the exponents are reduced modulo the totient of the modulus of the overall expression, leaving us with
P
P((ed) mod
(n))
(mod n)
So while our public key would include the value of the encryption key and the value of the modulus for the overall relationship, it would not contain the modulus that applies to the exponents. Thus, the attacker can neither undo the encryption process directly (because of the discrete log problem) nor deduce the decryption key (because of not knowing the proper modulus to use in finding the multiplicative inverse of the encryption key). These two problems are believed to be sufficiently difficult that the most common asymmetric cipher in use today, RSA, is based on modular exponentiation.
Recall that the public key is going to consist of the encrypting exponent, e, and the overall modulus, n. The piece of information that an attacker needs to acquire to break our system is the multiplicative inverse of e which they can easily determine if they can determine f(n). However, the totient function requires knowledge not of n, but of its prime factorization. Hence, given n, the attacker must first factor it into its prime constituents. It is believed that, like the discrete logarithm problem, this is a very difficult task.