Public-key cryptography is a very novel form of cryptography that first became known to the public during the decade of the 1970s. Not only is it novel, its very name seems paradoxical and confusing.
Although cryptographic techniques have other uses besides sending secret messages, such as authentication, and this is especially true of public-key cryptography, sending secret messages is still one of the things public-key cryptography can be used for.
And if a message is secret, that means that the key to unlock it must be a secret, or else anyone could decipher it. That is still just as true for public-key cryptography as it is for the regular kind.
If that's the case, what does the word "public" in public-key cryptography mean?
Normally, with a conventional cryptographic system, if you know both the key for sending a secret message, and the method of encryption in which that key is used, then you also know everything you need to know to decipher secret messages sent with that key and in that system. A few conventional encryption systems are reciprocal, so that exactly the same key and procedure serves for encryption and decryption; but in those that are not reciprocal, the key and procedure for decryption are both still easily derived from those for encryption, and in most cases, only one of the two differs.
A public-key cryptosystem is one where a key, useful for sending messages, can be made public without revealing the still-secret key that allows those messages to be read.
Thus, both you and someone else have the same complete set of instructions to put a message into encrypted form, so that a third person can read it. If you encrypt a message, of course you can recognize your own message in its encrypted form. But you can't perform the inverses of those steps in reverse order to read the messages the other person encrypted. Yet, the person who gave both of you the instructions can read the messages from both of you. This is baffling, and, were it not for the fact that modular exponentiation is perhaps a bit complicated to expect members of an audience, chosen at random, to perform on stage, it would qualify as an effective magic trick.
How can this be possible?
A two-part codebook is one where the code groups don't have the same order as the plaintext words and phrases they represent. If you publish only the enciphering half of such a codebook, keeping the deciphering part to yourself, then it is easier to send coded messages to you than it is to read them.
Of course, that doesn't really provide genuine security. But it hints as to how PKC can be possible.
Another example, one of the first PKC concepts expressed in the open literature, goes as follows:
Transmit a large number of encrypted messages to a correspondent. These messages are in a cipher that can be broken, but not without some work. The messages look something like this:
"Key number 2126 is EXVRRQM"
"Key number 1253 is PTXYZLE"
and so on.
The keys for each key number are chosen genuinely at random, so there is no system to crack that would yield all the keys.
You keep a table of what every numbered key is.
The person who wants to send you a message picks any one of your large number of encrypted messages, and breaks it. Then, using the key found inside, he encrypts his message to you, and the precedes it with a note saying: "I am using key number 2126 to encrypt this message".
He only had to decrypt one of the encrypted key messages to send you a message, but anyone who wanted to read it would have to keep decrypting all the messages until he found the right one (which would, of course, on average mean having to decrypt half of them).
So, the principle of PKC is to find some trick that works one way without revealing how to reverse the process. And one good place to look for tricks like that is in higher mathematics, and each of the public-key methods we will look at in the remainder of this section will have had a basis that came from that source.
Still, since the basis of any public-key cryptographic method is, in effect, a trick: a set of instructions to carry out a transformation in one direction that isn't quite informative enough to allow people to carry out that same transformation in the reverse direction, it is reasonable that some people might have felt uneasy about the long-term security of such methods. And, in fact, accounts of the original secret discovery of public-key methods within the British GCHQ note that while those in authority thought the idea novel and interesting, their fear that some "magic screw" might be discovered that would make the security of public-key ciphers fall apart led to these methods not being used.
Considering how effective and useful public-key methods are at this time to the general public, this may seem foolish and wrong-headed, and some have viewed this attitude as such. I, personally, am not so sure that caution regarding the use of public-key methods for otherwise unprotected key distribution should really be viewed as unwarranted. Also, the military has existing channels in place for the distribution of secret keys, and thus the need for the practical benefits of PKC is less pressing for them.
But despite the fact that I think that a certain level of mistrust of public-key methods was justified, I also think that there was a valid reason to use them in military cryptography in a way that would not have catastrophic consequences if the mistrust turned out to be fully justified (that is, if a trivial way to crack RSA, Diffie-Hellman, and the other public-key methods ever were found) and yet which would provide important benefits should public-key methods happen to remain secure. This is described on this page. If a military cipher machine, when first manufactured, thought up its own public/private key pair, and revealed its public key, while keeping its private key a secret within its innards, then when secret keys are distributed to it, those keys could be encrypted, at headquarters, using its public key. This would be a very effective precaution in preventing any personnel involved in key distribution from betraying the keys to the enemy for as long as the public-key method used remained secure; and if those keys were still distributed with the same security precautions as used before the introduction of this innovation, if public-key cryptography turned out to be an insecure passing fad, nothing would have been lost. If anything, there might have been a gain, in that enemy intelligence agencies would not have been likely to pay high prices to spies to obtain then useless keys merely to add to their back intercept piles.
Public-key cryptography is certainly very different from conventional cryptography, and is of general mathematical interest. But it is also of very considerable practical importance.
Without public-key cryptography, you could still send an encrypted E-mail to a friend who was away on vacation, if before he left you had given him a secret key to use. You could also encrypt your E-mails to someone you hadn't met, provided you sent him, or he sent you, a secret key by a more secure method, such as a letter by regular mail. (Of course, letters can be read too by a determined adversary, but exchanging keys even in this simple fashion would keep your communications out of reach of someone who has the opportunity to intercept your E-mail but not the contents of your mailbox.)
With public-key cryptography, however, no resort to an alternative more secure channel of communications for prior setup is required. Instead, encrypted communications can be set up on an impromptu basis, entirely over an insecure medium such as the Internet. It is not an overstatement to claim that public-key cryptography is the factor which changed cryptography from something which was only used by people with either a strong need for secrecy, or an interest in cryptography itself, to something used routinely by many people for such practical purposes as making credit-card purchases over the Internet.
The RSA public-key cryptosystem is a straightforwards example of public-key cryptography: using the same operation, key E transforms plaintext to ciphertext, key D transforms ciphertext to plaintext, but it isn't possible to find D only knowing E; the two prime factors of the modulus used are required.
But there are other ways to send a message from one place to another without prior exchange of a secret key.
The Diffie-Hellman key exchange method relies on a one-way transformation from a private key x to a public key A^x, which has the property that two parties can exchange public keys, and using either private key and the other public key, it is possible to arrive at the same secret session key which no one knowing only the two public keys can derive.
The Massey-Omura cryptosystem is based on Shamir's three-pass protocol, where an encryption method is used such that, after it is applied twice, the two encryptions do not need to be removed in the exact reverse of the order in which they were applied, but can be removed in any order. This allows one party to send an encrypted message, and the recipient can send it back encrypted again, and then the first party can remove his own encryption, sending it back to the recipient as if only the recipient had encrypted it. (While there are many encryption methods that are commutative, most, if used in this way would provide no security whatever, because relationships between the messages sent would reveal the secret keys used.)
Public-key cryptography makes it practical and convenient for parties to set up secure communications with each other over the Internet without any other form of prior contact. Authenticating the identity of each party to the other still does require some setup, but this can be done ahead of time without even directly involving the two parties themselves, by the use of certificates made using digital signatures, another function that public-key cryptography makes possible.
Thus, your browser contains the information that "Key XXXX really is the public key of this digital signature company", and when you order something from a company, that company first provides your browser with a message, enciphered in the secret key corresponding to the public key XXXX, which states that "Key YYYY is really the public key of this merchant, whose website is here". So the prior contact between the digital signature company and the company that wrote the web browser you used is enough to ensure that when your browser is given key YYYY, it is setting up secure communications with the merchant, and not someone impersonating the merchant to steal money from your credit card. You then authenticate yourself to the merchant with information from your credit card, which you got in your mailbox from the credit card company, another form of direct contact.
If public-key cryptography had not been available, therefore, the existing opportunity for direct contact that comes when you recieve a credit card would simply have had to be used more thoroughly. For example, credit-card companies could have additionally issued secret passwords to credit-card holders. After all, the credit card itself is a piece of plastic that has to be sent through the mail, so a password could be sent with the card. Usually, of course, a PIN number for a credit card also used for bank machine access is sent in a separate envelope, to prevent someone stealing one item from a mailbox from having both.
In that situation, purchasing something over the Internet would have involved a special program, provided to you by the credit card company, that communicated over the Internet, perhaps as a browser plug-in. When you visited a merchant's web site, you would use this program to communicate with the merchant's computer, perhaps using a protocol like this:
First, your credit card number (which can't be used by itself to order things, at the least the expiry date is also needed) is sent to the merchant in the clear.
The merchant's computer sends you a random number.
You enter your password on your computer. The password was chosen for you by the credit card company, and part of it has a mathematical relationship with your credit card number, while another part is random.
Your computer sends data to the merchant's computer corresponding to the random part of your password. Also, your software, using your password, the random value from the merchant, and your credit card number, calculates a secret key for communications between you and the merchant.
At the merchant's end, the data corresponding to the random part of your password, the random number sent by the merchant, and your credit card number are enough to allow the same secret key to be calculated, because instead of using software that a hacker might disassemble, the merchant uses electronic equipment in a sealed box provided by the credit card company to do the calculation. How to create that secret key with your whole password is in the program the bank gives out, and is therefore public information, but how to do it with only partial information is secret.
Can this really be done using only conventional secret-key techniques, you might ask, since I haven't gone into all the details? Or is one of the steps above something that requires public-key methods?
PKC isn't needed; this will work without it. The basic principle is that the portion of your password that isn't sent over the Internet to the merchant is an enciphered version of your credit card number. The black box at the merchant's site carries out the encipherment process; having a single plaintext-ciphertext pair for a cipher doesn't automatically break that cipher, so the fact that you know your own password, even if you have disassembled the program you use it with, doesn't let you spend money on other people's credit cards.
Since it's a function of your credit card number only, the merchant's black box can figure it out first, and so, while the software at your end doesn't send it, it does use it as a key to encrypt the other part of your password when sending it (as well as using the random value from the merchant to mask it before encryption, something like an initialization vector). This way, someone having dissassembled the software running on your computer still can't, without knowing your password, decrypt what it sends to the merchant to set up the secret communications between you and the merchant by means of which you prove you are the legitimate user of the credit card. And, in addition, of course, using a value as the key for encryption doesn't automatically make that value public, otherwise no form of conventional secret-key encryption would be possible.
Of course, the password number will be longer than your 11-digit credit card number, and so people won't be able to memorize numbers like that, so there would still be security problems involved in using credit cards over the Internet without public-key cryptography. But it could have been done, had it been necessary, and, in fact, for specialized applications, likely systems like that were in use for certain types of financial transactions by telephone.