Public Key Cryptography
Part of
22C:169, Computer Security Notes
|
Public key or assymetric key cryptography emerged in the 1970's, and it represents a new model. Instead of a single key, there are two keys, one for encryption and one for decryption.
cyphertext = encrypt( plaintext, key1 )
plaintext = decrypt( cyphertext, key2 )
To be interesting, it must be practically impossible to compute one key from the other, so given key2, the only way to find key1 should be trial and error, and visa versa.
The challenge in developing such cyphers, as opposed to finding applications for them, lies in finding trapdoor functions such that, given one of the keys, the plaintext and the cyphertext, the other key cannot be computed.
The cryptosystem now known as RSA was named after Ron Rivest, Adi Shamir and Leonard Adleman who invented it while at MIT in 1977. An equivalent system had actually been invented earlier in the UK, but was classified and may never have been used.
The RSA scheme rests on the fact that it is far harder to factor a number than it is to multiply the factors together to produce that number. We begin with two large prime numbers, p and q and compute their product n=pq.
The function phi(n)=(p-1)(q-1) is very hard to compute, since computing it requires factoring n. This function is called the totient function.
As with Diffie-Hellman key exchange, we use modular exponentiation to encrypt and decrypt. So, given the message m, we compute the cyphertext c=me mod n, where e is the encryption key exponent, and we decrypt this using m=cd mod n, where d is the decryption key exponent. As with Diffie-Hellman key exchange, this works because of the commutativity of modular exponentiation, so in fact, the algorithm works just as well with d and e exchanged.
The public key exponent e must be between 1 and phi(n), and it must be relatively prime to phi(n) (that is, it must have no common factors other than 1). Prime values of e are common. In fact, using a fixed value of e is reasonable, since the prime numbers p and q are the real key to the code.
The private key exponent d must be the multiplicative inverse of p mod phi(n). That is, de mod phi(n)=1, or de=1+k×phi(n) for some value of k.
The message being encrypted must be broken into chunks that are, when treated as integers, less than n. Typically, we bite off the message in fixed size chunks, and we must simply guarantee that the n is larger than the maximum message chunk. Thus, if the message is being chunked into 256 bit blocks, then n must be greater than 2256.
If the modulus is bigger than the largest code value, there will be unused code values. These give an attacker a potential weakness. In addition, the messages 0 and 1 have annoying properties -- they always encrypt to themselves. Typical uses of RSA always add a few bits of random padding to each message block -- added before encryption, removed after decryption, so that these weaknesses will be avoided.
It is quite common to use e=65537, although 3, 5 and 35 are popular. Using small encryption exponents makes the computation faster -- valuable if the encryption is being done on a very weak computer.
With public key cryptography, participants publishes their public keys and keeps their private keys secret. If Alice wants to send a message to Bob, Alice encrypts it with Bob's public key. Only Bob can decrypt the message, because only Bob has the private key.
How does Bob know that the message is authentic? This problem can be solved by having Alice encrypt the message with her private key and then having Bob decrypt the message with Alice's public key. This is the basis of using public-key cryptography for digital signatures.
Notice that public-key cryptography is computationally expensive. As with Diffie Hellman key exchange, it is generally used to communicate the key for a symmetric-key cypher that will be used for the bulk of the message. Now, consider the problem that arises if Alice sends a totally random key to Bob.
If Bob decodes the message holding the random number with the wrong key, he has no way of knowing that the result of this decryption is wrong. All random numbers, when decrypted with any key, still look random. Therefore, a complete scheme using public-key cryptography must involve sending some kind of authentication information in the message that allows the reciever to recognize successful decryption and distinguish it from unsuccessful encryption.
If the message being sent is English text sent in UTF-8 format, using a symmetric key cypher, where the symmetric key is sent using public key cryptography, then failure to use the correct keys will result in the wrong key being used to decrypt the English text. This will result in the text appearing as a random sequence of Unicode characters, obviously wrong. The key here is that English text is redundant. It is the redundancy in the message that allows us to distinguish correctly decrypted messages from incorrectly decrypted messages.
So, if we include redundancy in our messages, public key cryptography allows us to prove that only Alice could have sent the message (because she used her private key to encrypt it) or it allows us to prove that only Bob could recieve the message (because it was encrypted with his public key). If we double-encrypt the message, we have a genuinely secure channel from Alice to Bob, so that nobody can inspect or forge the messages Alice sends to Bob.
Alice needs to know Bob's public key to send him a message, and Bob needs to know Alice's public key in order to establish such a secure channel. How do you distribute public keys? Informally, we said that Alice and Bob publish their keys.
If I want to know for certain that the key I found on the web or in a newspaper is Alice's public key, I must trust the web site or newspaper that I got the key from. That is, I must know that the web site or newspaper is not a forgery. Anyone can print anything they want on newsprint or on the web, so we need a secure link from the publisher to me for me to be sure that nobody is falsifying the publication. In addition, I want the publisher to be very careful, requiring that Alice authenticate herself before placing the advertisement announcing her public key.
We can do this using public key cryptography. The publisher and Alice use a secure channel, and I use a secure channel to get Alice's key from the publisheer. This, though, requires that I know the public key of the publisher in order to securely communicate with the publisher, and this creates an infinite regress. How do I get that key? How does the publisher get Alice's public key?
This is the public-key infrastructure problem. Ever since public key cryptography was first proposed, people have expected the emergence of a public key infrastructure. So far, no universal infrastructure has emerged. There are some specialized areas, however, where such infractructures exist. Typically, they are built based on other authentication methods, such as face-to-face contacts to exchange public keys, and then building on this low-level exchange to build high-level services.
The wikipedia articles are good:
http://en.wikipedia.org/wiki/Public-key_cryptography